Idempotency Deduplication of Retried Requests
Problem Statement
Retries can cause the same side-effecting request to run twice. Use idempotency keys to return the first response for any repeated key instead of re-executing.
Background
Each request carries an idempotency_key and a result. Processing in order: the first time a key is seen, its result is committed and returned. Any later request with a key already committed returns the stored result (a replay), regardless of its own result value. Report the response returned for each request and whether it was a replay.
Your Task
def dedupe_requests(requests):
- requests: list of {"idempotency_key": str, "result": any}.
- Return a list of {"result": committed_result, "replay": bool} per request.
Input Format
- requests (list of dicts).
Output Format
- A list of dicts {"result", "replay"}.
Sample
print(dedupe_requests([{"idempotency_key":"a","result":1},{"idempotency_key":"a","result":99}]))
Output:
[{'result': 1, 'replay': False}, {'result': 1, 'replay': True}]
Example:
print(dedupe_requests([{"idempotency_key":"a","result":1},{"idempotency_key":"a","result":99}]))[{'result': 1, 'replay': False}, {'result': 1, 'replay': True}]- Initialize an empty store to track committed idempotency keys and their associated results.
- Process the first request with key
"a"and result1: since"a"is not in the store, commit result1to the store and record the response as{"result": 1, "replay": False}. - Process the second request with key
"a"and result99: since"a"is already in the store, retrieve the stored result1and record the response as{"result": 1, "replay": True}, ignoring the new result99. - The final output is
[{'result': 1, 'replay': False}, {'result': 1, 'replay': True}]
Constraints:
- First occurrence of a key commits and returns its own result (replay False).
- Later occurrences return the committed result (replay True), ignoring their own result.
- Preserve input order.
1. Background Knowledge
Idempotency is a property where performing an operation multiple times has the same effect as performing it once. In distributed systems, network timeouts or client retries often cause the same logical request to be sent multiple times. Without protection, a "charge $10" request sent twice would debit the account twice. An idempotency key is a unique identifier (usually a UUID) generated by the client for each logical operation. The server uses this key to detect duplicates.
The core mechanism is a deduplication store (often a database table or in-memory cache). When a request arrives, the server checks if the key already exists in the store. If it does not, the request is processed, and the resulting response is persisted alongside the key. If the key already exists, the server skips execution and returns the previously stored response. This is often called a replay.
This pattern is critical for reliability because it decouples "at-least-once" delivery (which is easy to guarantee) from "exactly-once" semantics (which is hard). The client can safely retry without fear of side effects, and the server guarantees that the side effect happens at most once per key.
2. Algorithm Approach
This is a classic hash map lookup problem. The algorithm follows a linear scan with constant-time membership checks:
- Initialize an empty dictionary (hash map) to store committed results. The keys are the idempotency_key strings, and the values are the result objects.
- Iterate through the requests list in order.
- For each request, extract the idempotency_key and result.
- Check if the key exists in the dictionary:
- If not present: This is the first occurrence. Store the current result in the dictionary under this key. Mark replay as False.
- If present: This is a duplicate. Retrieve the stored result from the dictionary. Mark replay as True.
- Append the response object {"result":..., "replay":...} to the output list.
- Return the output list.
3. Step-by-Step Strategy
- Step 1: Setup Create an empty dictionary, e.g., store = {}. Create an empty list for the final output, e.g., responses = [].
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.