Query Batching

Problem Statement

The objective here is to optimize query operations by batching multiple smaller queries into single larger ones, which is particularly beneficial when dealing with high latency operations such as network requests. The task involves creating a QueryBatcher class that controls the flow of these batch operations based on a specified 'throttle' time parameter, t. The constructor of this class requires two parameters:

• queryMultiple - An asynchronous function that accepts an array of string keys and returns a Promise which resolves to an array, where each element is the result corresponding to the input element at the same index.
• t - A throttle time in milliseconds that determines the minimum time interval between consecutive batch requests.

The class should also contain a method:

• async getValue(key) - This method takes a single string key and returns a Promise that resolves to the corresponding value. The method queues keys for a batch request which is sent once the throttle time has elapsed since the last batch request, or is immediately sent if it's the first request.

This method ensures efficient handling of simultaneous or closely timed requests by grouping them into batches and sending fewer overall queries, thus potentially reducing the wait time and resource consumption compared to handling each request separately.

Examples

Example 1

Input:

queryMultiple = async function(keys) {
  return keys.map(key => key + '!');
}
t = 100
calls = [
 {"key": "a", "time": 10},
 {"key": "b", "time": 20},
 {"key": "c", "time": 30}
]

Output:

[
 {"resolved": "a!", "time": 10},
 {"resolved": "b!", "time": 110},
 {"resolved": "c!", "time": 110}
]

Explanation:

const batcher = new QueryBatcher(queryMultiple, 100);
setTimeout(() => batcher.getValue('a'), 10); // "a!" at t=10ms
setTimeout(() => batcher.getValue('b'), 20); // "b!" at t=110ms
setTimeout(() => batcher.getValue('c'), 30); // "c!" at t=110ms
queryMultiple simply adds an "!" to the key
At t=10ms, getValue('a') is called, queryMultiple(['a']) is immediately called and the result is immediately returned.
At t=20ms, getValue('b') is called but the query is queued
At t=30ms, getValue('c') is called but the query is queued.
At t=110ms, queryMultiple(['b','c']) is called and the results are immediately returned.

Example 2

Input:

queryMultiple = async function(keys) {
  await new Promise(res => setTimeout(res, 100));
  return keys.map(key => key + '!');
}
t = 100
calls = [
 {"key": "a", "time": 10},
 {"key": "b", "time": 20},
 {"key": "c", "time": 30}
]

Output:

[
 {"resolved": "a!", "time": 110},
 {"resolved": "b!", "time": 210},
 {"resolved": "c!", "time": 210}
]

Explanation:

This example is the same as example 1 except there is a 100ms delay in queryMultiple. The results are the same except the promises resolve 100ms later.

Example 3

Input:

queryMultiple = async function(keys) {
  await new Promise(res => setTimeout(res, keys.length * 100));
  return keys.map(key => key + '!');
}
t = 100
calls = [
 {"key": "a", "time": 10},
 {"key": "b", "time": 20},
 {"key": "c", "time": 30},
 {"key": "d", "time": 40},
 {"key": "e", "time": 250},
 {"key": "f", "time": 300}
]

Output:

[
 {"resolved": "a!", "time": 110},
 {"resolved": "e!", "time": 350},
 {"resolved": "b!", "time": 410},
 {"resolved": "c!", "time": 410},
 {"resolved": "d!", "time": 410},
 {"resolved": "f!", "time": 450}
]

Explanation:

queryMultiple(['a']) is called at t=10ms, it is resolved at t=110ms
queryMultiple(['b', 'c', 'd']) is called at t=110ms, it is resolved at 410ms
queryMultiple(['e']) is called at t=250ms, it is resolved at 350ms
queryMultiple(['f']) is called at t=350ms, it is resolved at 450ms

Constraints

• 0 <= t <= 1000
• 0 <= calls.length <= 10
• 1 <= key.length <= 100
• All keys are unique

Approach and Intuition

The examples provided illustrate the potential scenarios and how the QueryBatcher class behaves with different settings and inputs. Here’s the intuitive breakdown:

1. Initial Call Behavior:

   • When the getValue method is called for the first time, it immediately sends a batch request with the keys gathered up to that point (which, for the first call, is just the one key).

2. Handling Rapid Successive Calls:

   • If subsequent calls to getValue are made within the throttle time t, these keys are queued but not immediately processed. Once the throttle time elapses since the last batch, all queued keys are sent as a new batch.

3. Delays and Multiple Batches:

   • In cases where calls are spread out over a time that exceeds the throttle period, separate batches are sent for each group of calls that happen within their respective throttle windows. This makes it essential that each call or batch respects the throttle time, ensuring that the server or backend isn't overwhelmed with requests at a frequency higher than it can handle efficiently.

From these observations:

• Throttling serves as a mechanism to manage load and performance both on the client (caller) and server side.

• The unique key assumption eliminates the complexity and overhead required to handle duplicate keys in concurrent access scenarios.

• Edge cases to be aware of include:

  • Rapid consecutive calls where the batching function waits until the throttle time elapses before sending off a batch.
  • Handling of slow asynchronous functions (i.e., if queryMultiple itself has a significant delay) and ensuring that this does not interfere with the batching logic.

Solutions

var QueryHandler = function(batchQuery, delay) {
  this.batchQuery = batchQuery;
  this.delay = delay;
  this.isActive = true;
  this.pending = [];
};
    
QueryHandler.prototype.fetchData = function(id) {
  return new Promise((resolve) => {
    if (this.isActive) {
      this.isActive = false;
      this.batchQuery([id]).then(output => resolve(output[0]));
      this.reset();
      return;
    }
    this.pending.push({ id, resolve });
  });
};
    
QueryHandler.prototype.reset = function() {
  setTimeout(() => {
    if (this.pending.length === 0) {
      this.isActive = true;
      return;
    }
    
    const keys = this.pending.map(entry => entry.id);
    const resolutionFuncs = this.pending.map(entry => entry.resolve);
    
    this.pending = [];
    
    this.batchQuery(keys)
      .then(responses => {
        resolutionFuncs.forEach((resolve, index) => {
          resolve(responses[index]);
        });
      });
    
    this.reset();
  }, this.delay);
};