Idempotency Deduplication of Retried Requests

mediumPROReliability & Failure HandlingAI AgentsAI Agents 1

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

Input

print(dedupe_requests([{"idempotency_key":"a","result":1},{"idempotency_key":"a","result":99}]))

Output

[{'result': 1, 'replay': False}, {'result': 1, 'replay': True}]

Reasoning

Initialize an empty store to track committed idempotency keys and their associated results.
Process the first request with key "a" and result 1: since "a" is not in the store, commit result 1 to the store and record the response as {"result": 1, "replay": False}.
Process the second request with key "a" and result 99: since "a" is already in the store, retrieve the stored result 1 and record the response as {"result": 1, "replay": True}, ignoring the new result 99.
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.

Learn this in

Multi-Agent Coordination & Failure ModesAgent Engineering Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primerPREVIEW

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 = [].

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results