Batch Key Lookups Into One HTTP Request per 100 ms With Callbacks

You are writing client code for a single-threaded, callback-based runtime, similar to a JavaScript event loop. A remote service exposes one batch endpoint that returns the values of several keys at once:

GET /get?keys=key1,key2,...
Response: {"key1": 123, "key2": "abs"}

The runtime provides two primitives:

http_get_request(url, callback) # sends a GET request; when the response arrives, calls callback(response: dict)
set_timeout(callback, ms) # calls callback() once, ms milliseconds from now

Implement start_fetch(key, callback). Callers ask for one key at a time. Your code must not send one HTTP request per call. Instead, it collects the requested keys and sends them to the endpoint as one batch request every 100 ms. When a batch response arrives, every callback that was waiting on a key in that batch must be called.

def start_fetch(key, callback):
 # TODO: implement this
 ...

For example, given this driver:

def main():
 start_fetch("foo", cb1) # t = 0 ms
 start_fetch("bar", cb2) # t = 30 ms
 start_fetch("foo", cb3) # t = 70 ms
 start_fetch("foo", cb4) # t = 120 ms

http_get_request must be called exactly twice. The response to the first request leads to calls of cb1, cb2 and cb3, and the response to the second request leads to the call of cb4.

You may add global state and helper functions. Explain how you schedule the 100 ms flush, and how you store the keys waiting to be sent together with the callbacks waiting on each key.

Constraints and Clarifications

• Assume a single-threaded runtime: start_fetch, timer callbacks and response callbacks each run to completion, one at a time.
• set_timeout(callback, ms) runs callback once, ms milliseconds after set_timeout is called.
• A key can be requested several times before its batch is sent, and every waiting callback must be called. In the example, cb1 and cb3 both wait on "foo".
• A key requested after its batch has been sent belongs to a later batch, even if the earlier request has not been answered yet. That is why cb4 causes a second request.
• A response can arrive at any later time, including after later start_fetch calls or after the next batch has been sent.

Clarifying Questions

• Is the 100 ms window measured from the first key that enters an empty batch, or is it a fixed tick every 100 ms whether or not keys are waiting?
• If a key is requested more than once in a window, should it appear only once in the URL?
• Does the callback given to start_fetch receive only the value of its own key, or the whole response dict?
• What should happen when the request fails or the response omits a requested key?
• Can keys contain commas or other characters that must be URL-encoded?