Design async batched key-value fetcher
Problem Statement
Design and implement a single-threaded, event-loop based asynchronous key-value fetcher. This fetcher, exposed via a getKeyAsync(key, callback) interface, must efficiently retrieve numeric values for keys from a backend HTTP endpoint while supporting concurrent I/O and intelligent request batching.
Context
Your execution environment is single-threaded and operates on an event loop (e.g., JavaScript/TypeScript). You have access to the following primitives:
httpGetAsync(urlPath, callback): An asynchronous function that performs an HTTP GET request. Thecallbackfunction is invoked ascallback(err, jsonString)upon response or error.parseKvs(jsonString): A utility function that parses a JSON string into aMap<string, number>, representing key-value pairs.
The backend endpoint for fetching values is GET /read?keys=k1,k2,.... It responds with a JSON object mapping each requested key to its numeric value (e.g., { "foo": 12, "bar": 100 }).
Task
Implement the getKeyAsync(key, callback) interface. Your implementation must:
- Batching Window: Consolidate all
getKeyAsyncrequests that arrive within a 100-millisecond window into a single HTTPGET /read?keys=...call. - Key Deduplication: If multiple
getKeyAsynccalls request the same key within a batching window, ensure that the key is included only once in the HTTP request. Each original request's callback must be invoked exactly once with the fetched value. - Consistency: A batch's HTTP response can only fulfill callbacks for requests that were received before that specific batch was dispatched. Requests arriving after a batch has been sent must be processed by a subsequent batch.
- Concurrent Batches: The system must support multiple HTTP requests (batches) being in-flight simultaneously without their responses being mixed or incorrectly correlated with pending callbacks.
- Architectural Definition: Clearly define the necessary data structures (e.g., queues, maps, sets), control flow mechanisms (e.g., timers, scheduling), and the strategy for correlating HTTP responses back to their respective waiting callbacks.
- Robustness: Specify the behavior for edge cases and failure scenarios, including:
- Missing keys in the backend response.
- Partial failures within a batch (e.g., some keys fail, others succeed).
- Timeouts and retry mechanisms.
- Cancellation and backpressure strategies.
- Analysis: Discuss the time and space complexity of your design, identify potential pitfalls related to ordering in a single-threaded asynchronous environment, and outline a brief test plan.
AI interview prep
Core dilemma
Balancing low-latency request aggregation (100ms window) with efficient backend resource utilization (batching) and strict consistency requirements in a single-threaded, asynchronous environment, while handling concurrent in-flight operations and diverse failure modes gracefully.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Design async batched key-value fetcher
Problem Statement
Design and implement a single-threaded, event-loop based asynchronous key-value fetcher. This fetcher, exposed via a getKeyAsync(key, callback) interface, must efficiently retrieve numeric values for keys from a backend HTTP endpoint while supporting concurrent I/O and intelligent request batching.
Context
Your execution environment is single-threaded and operates on an event loop (e.g., JavaScript/TypeScript). You have access to the following primitives:
httpGetAsync(urlPath, callback): An asynchronous function that performs an HTTP GET request. Thecallbackfunction is invoked ascallback(err, jsonString)upon response or error.parseKvs(jsonString): A utility function that parses a JSON string into aMap<string, number>, representing key-value pairs.
The backend endpoint for fetching values is GET /read?keys=k1,k2,.... It responds with a JSON object mapping each requested key to its numeric value (e.g., { "foo": 12, "bar": 100 }).
Task
Implement the getKeyAsync(key, callback) interface. Your implementation must:
- Batching Window: Consolidate all
getKeyAsyncrequests that arrive within a 100-millisecond window into a single HTTPGET /read?keys=...call. - Key Deduplication: If multiple
getKeyAsynccalls request the same key within a batching window, ensure that the key is included only once in the HTTP request. Each original request's callback must be invoked exactly once with the fetched value. - Consistency: A batch's HTTP response can only fulfill callbacks for requests that were received before that specific batch was dispatched. Requests arriving after a batch has been sent must be processed by a subsequent batch.
- Concurrent Batches: The system must support multiple HTTP requests (batches) being in-flight simultaneously without their responses being mixed or incorrectly correlated with pending callbacks.
- Architectural Definition: Clearly define the necessary data structures (e.g., queues, maps, sets), control flow mechanisms (e.g., timers, scheduling), and the strategy for correlating HTTP responses back to their respective waiting callbacks.
- Robustness: Specify the behavior for edge cases and failure scenarios, including:
- Missing keys in the backend response.
- Partial failures within a batch (e.g., some keys fail, others succeed).
- Timeouts and retry mechanisms.
- Cancellation and backpressure strategies.
- Analysis: Discuss the time and space complexity of your design, identify potential pitfalls related to ordering in a single-threaded asynchronous environment, and outline a brief test plan.