LESSON 2.3: IDEMPOTENCY KEYS — Deep Dive into Distributed Deduplication

INTRODUCTION

In Lesson 2.1, you learned that POST is not inherently idempotent, and that open banking mandates a client‑supplied idempotency key to prevent duplicate payments and consent creations. In Lesson 2.2, you declared the x-idempotency-key header in your OpenAPI contract. Now, in Lesson 2.3, we go deep into the engine room—implementing a production‑grade idempotency store that survives network partitions, Redis failovers, and 25 RPS concurrent bursts.

This lesson is quantitative and algorithmic. You will learn why atomic Lua scripts are superior to simple SET NX (they prevent race conditions), how to handle the 409 Conflict response when a TPP accidentally reuses a key with a different payload, and what retry backoff strategy (exponential with jitter) minimises thundering herds. We will also calculate the durability vs. availability trade‑off: storing idempotency keys synchronously (strong consistency, higher latency) vs. asynchronously (eventual consistency, lower latency, but risk of duplicates).

By the end, you will be able to implement a distributed idempotency service that guarantees exactly‑once semantics for payment initiation, meeting PSD2 Article 66’s requirement that “the payment transaction shall not be executed more than once.”

LEARNING OBJECTIVES

Implement the Redis Lua atomic script for idempotent POST—using SET NX with a TTL of 86,400 seconds (24 hours) and a SHA‑256 hash of the canonicalised JSON payload to detect payload drift.
Calculate the duplicate detection window—deriving the required TTL from the OBIE’s 24‑hour idempotency window, the ASPSP’s internal settlement latency (≤2 seconds for Pix, ≤30 seconds for SEPA), and the TPP’s maximum retry interval (exponential backoff up to 30 seconds).
Design the 409 Conflict response flow—including the x-idempotency-key in the error payload, returning the Location of the previously created resource, and logging the mismatch for fraud detection.
Quantify the latency budget for idempotency checking—measuring Redis cluster round‑trip time (≤2ms in the same AZ), Lua script execution time (≤0.5ms), and network jitter—and ensuring the total ≤5ms to stay within the 850ms p95 budget.
Construct a retry strategy for TPPs—implementing exponential backoff with jitter (base 2, max 30s, jitter ±20%) to avoid thundering herds when an idempotency key expires or the ASPSP returns 429 Too Many Requests.

PART 1: THE ATOMIC IDEMPOTENCY STORE — Redis Lua Deep Dive

1.1 Why Lua? The Race Condition Problem

Consider a naive implementation using GET + SET (two separate Redis commands):

Thread A: GET(key) → nil
Thread B: GET(key) → nil
Thread A: SET(key, hash1)
Thread B: SET(key, hash2)  # Overwrites Thread A!

Result: Two concurrent requests with the same idempotency key but different payloads. Thread B overwrites Thread A’s record. The ASPSP processes both payments → duplicate execution.

Solution: An atomic Lua script that checks and sets in a single, uninterruptible operation.

1.2 The Production‑Grade Lua Script

-- idempotency.lua
-- KEYS[1] = idempotency key (e.g., "idempotent:payment:pay-001")
-- ARGV[1] = SHA-256 hash of canonicalised JSON payload
-- ARGV[2] = TTL in seconds (86400 = 24 hours)
-- ARGV[3] = current timestamp (for audit logging)

local key = KEYS[1]
local payload_hash = ARGV[1]
local ttl = tonumber(ARGV[2])
local timestamp = ARGV[3]

-- 1. Check if key exists
local stored = redis.call('GET', key)

if stored == false then
    -- 2. First time: store the hash with TTL
    redis.call('SET', key, payload_hash, 'EX', ttl)
    -- 3. Store metadata for audit (creation time, status)
    redis.call('HSET', key .. ':meta', 'created_at', timestamp, 'status', 'PENDING')
    return {'stored', payload_hash}
else
    -- 4. Key exists: compare hashes
    if stored == payload_hash then
        -- 5. Same payload → duplicate, return OK
        return {'duplicate_ok', stored}
    else
        -- 6. Different payload → conflict
        return {'duplicate_conflict', stored}
    end
end

Atomicity guarantee: Redis executes this script atomically—no other command can interleave. The GET and SET are a single transaction.

1.3 Calling the Lua Script from Python (Production Code)

import hashlib
import json
import redis
import time

class IdempotencyManager:
    REDIS_TTL_SECONDS = 86400  # 24 hours
    REDIS_KEY_PREFIX = "idempotent:payment:"

    def __init__(self, redis_client: redis.Redis):
        self.redis = redis_client
        # Load the Lua script once at startup (cached SHA)
        self.script_sha = self.redis.script_load("""
            local key = KEYS[1]
            local payload_hash = ARGV[1]
            local ttl = tonumber(ARGV[2])
            local timestamp = ARGV[3]
            local stored = redis.call('GET', key)
            if stored == false then
                redis.call('SET', key, payload_hash, 'EX', ttl)
                redis.call('HSET', key .. ':meta', 'created_at', timestamp, 'status', 'PENDING')
                return {'stored', payload_hash}
            else
                if stored == payload_hash then
                    return {'duplicate_ok', stored}
                else
                    return {'duplicate_conflict', stored}
                end
            end
        """)

    def store_or_get(self, idempotency_key: str, request_payload: dict) -> tuple:
        """
        Returns (status, stored_hash_or_error)
        status: 'stored', 'duplicate_ok', 'duplicate_conflict'
        """
        # Canonicalise JSON: sort keys, remove whitespace
        canonical_json = json.dumps(request_payload, sort_keys=True, separators=(',', ':'))
        payload_hash = hashlib.sha256(canonical_json.encode('utf-8')).hexdigest()

        redis_key = f"{self.REDIS_KEY_PREFIX}{idempotency_key}"
        current_timestamp = int(time.time() * 1000)  # milliseconds for audit

        # Execute the cached script (evalsha for performance)
        try:
            result = self.redis.evalsha(
                self.script_sha,
                1,
                redis_key,
                payload_hash,
                self.REDIS_TTL_SECONDS,
                current_timestamp
            )
        except redis.exceptions.NoScriptError:
            # Fallback if script was evicted from Redis cache
            result = self.redis.eval(self.script_sha, 1, redis_key, payload_hash,
                                     self.REDIS_TTL_SECONDS, current_timestamp)

        # Decode result (Redis returns bytes)
        status = result[0].decode('utf-8')
        stored_hash = result[1].decode('utf-8')

        return (status, stored_hash)

1.4 Latency Budget for Idempotency Check

Component	Operation	Latency (p95)
Network	Redis round‑trip (same AZ, direct connect)	1.2ms
Redis	Lua script execution (GET + SET + HSET)	0.4ms
Serialisation	Canonical JSON serialisation + SHA‑256 hash	0.8ms
Total	Idempotency check overhead	≤2.4ms

This is well within the 850ms UK p95 budget. Even under 25 RPS concurrency, Redis handles ~100k ops/sec on a single node—plenty of headroom.

PART 2: HANDLING THE 409 CONFLICT — The Payload Mismatch

2.1 The 409 Conflict Response

If the TPP reuses the same x-idempotency-key with a different payload (e.g., changed amount from €100 to €200), the ASPSP must return 409 Conflict.

OBIE v4.0 Specification (section 3.2.5):

“If the ASPSP receives a request with an idempotency key that has been used before, and the request body differs from the original, the ASPSP MUST return a 409 (Conflict) response.”

Explicit JSON Response:

{
  "ErrorCode": "IDEMPOTENCY_CONFLICT",
  "ErrorDescription": "Idempotency key 'pay-001' already used with different payload.",
  "PreviousResourceUri": "/payments/pay-123",
  "PreviousPayloadHash": "a7f3e8d9c1b2..."
}

2.2 Logging the Conflict for Fraud Detection

Payload mismatches are rare (<0.01% of requests). When they occur, they may indicate:

TPP client bug (reusing a key incorrectly)
Man‑in‑the‑middle attack (attempting to modify a signed payment)
Network corruption (extremely unlikely)

Audit requirement: The ASPSP must log the mismatch with:

idempotency_key
original_hash (stored in Redis)
new_hash (from the conflicting request)
source_ip, timestamp, consent_id

2.3 Code Snippet for Conflict Response

def handle_payment_request(idempotency_key, request_payload):
    status, stored_hash = idempotency_manager.store_or_get(idempotency_key, request_payload)

    if status == 'stored':
        # Process payment (idempotent, first time)
        payment_ref = process_payment(request_payload)
        return 201, {'paymentId': payment_ref, 'status': 'PENDING'}

    elif status == 'duplicate_ok':
        # Replay of identical request → return same response
        payment_ref = get_payment_by_key(idempotency_key)
        return 200, {'paymentId': payment_ref, 'status': 'SETTLED'}

    elif status == 'duplicate_conflict':
        # Payload mismatch → 409 Conflict
        original_payment_ref = get_payment_by_key(idempotency_key)
        return 409, {
            'ErrorCode': 'IDEMPOTENCY_CONFLICT',
            'ErrorDescription': f'Idempotency key {idempotency_key} already used',
            'PreviousResourceUri': f'/payments/{original_payment_ref}',
            'PreviousPayloadHash': stored_hash
        }

Note: The 409 response must not include the original payload (privacy risk). Only the hash and the resource URI are permitted.

PART 3: RETRY BACKOFF STRATEGIES — TPP‑Side Resilience

3.1 Why Exponential Backoff with Jitter?

When an idempotency key expires (after 24 hours) or the ASPSP returns 429 Too Many Requests, the TPP must retry. Without jitter, all TPPs retry at exactly the same interval, creating a thundering herd that overwhelms the API gateway.

Formula: delay = min(max_delay, base_delay * 2^attempt) + jitter

Where:

base_delay = 100ms (initial retry)
max_delay = 30000ms (30 seconds)
jitter = random(0, 0.2 * delay) (20% randomisation)

3.2 Python Implementation

import random
import time
import requests

class RetryManager:
    BASE_DELAY = 0.1  # 100ms
    MAX_DELAY = 30.0  # 30 seconds
    MAX_ATTEMPTS = 10

    def retry_payment(self, idempotency_key, payload):
        for attempt in range(self.MAX_ATTEMPTS):
            try:
                response = requests.post(
                    'https://api.bank.com/payments',
                    json=payload,
                    headers={'x-idempotency-key': idempotency_key},
                    timeout=5.0
                )

                if response.status_code == 201:
                    return response.json()  # Success

                elif response.status_code == 409:
                    # Conflict → do not retry (client must fix payload)
                    raise IdempotencyConflictError(response.json())

                elif response.status_code == 429:
                    # Rate limited → retry with backoff
                    retry_after = int(response.headers.get('Retry-After', 1))
                    time.sleep(retry_after)
                    continue

                elif response.status_code in (500, 502, 503, 504):
                    # Server error → retry with backoff
                    pass
                else:
                    # Other errors → do not retry
                    raise PaymentError(response.status_code, response.text)

            except requests.exceptions.Timeout:
                # Timeout → retry with backoff
                pass

            except requests.exceptions.ConnectionError:
                # Network error → retry with backoff
                pass

            # Exponential backoff with jitter
            if attempt < self.MAX_ATTEMPTS - 1:
                delay = min(self.MAX_DELAY, self.BASE_DELAY * (2 ** attempt))
                jitter = random.uniform(0, 0.2 * delay)
                time.sleep(delay + jitter)

        raise MaxRetriesExceededError('Payment failed after max retries')

3.3 Latency Impact of Retries

Attempt	Delay (ms)	Cumulative Time
1	100 + 10 (jitter)	110ms
2	200 + 20	330ms
3	400 + 40	770ms
4	800 + 80	1,650ms
5	1600 + 160	3,410ms
6	3200 + 320	6,930ms
7	6400 + 640	13,970ms
8	12800 + 1280	28,050ms
9	25600 + 2560	56,210ms
10	30000 + 3000	89,210ms (≈89s)

Observation: The TPP’s user experience degrades significantly after 5 retries (~3.4s). The TPP should display a “processing” spinner and allow the user to cancel.

PART 4: DURABILITY VS. AVAILABILITY — The Redis Trade‑Off

4.1 The Problem of Redis Failover

Redis, by default, uses asynchronous replication to replicas. If the master fails before replicating the SET command, the replica may not have the idempotency key. When the replica becomes the new master, a subsequent request with the same key will be treated as new—and the payment will be duplicated.

Probability: Low (Redis failover occurs <0.01% of the time), but the impact is critical (financial loss).

4.2 Solutions

Solution	Pros	Cons	Latency Impact
WAIT command	Force synchronous replication to ≥1 replica	Higher latency, reduces availability	+2‑5ms
Redis Cluster with replication	Automatic failover, better durability	Complex configuration	+1‑2ms
Persistent storage fallback (PostgreSQL)	Strong ACID guarantees	Much higher latency (+20ms)	Unacceptable for 850ms budget
Async + idempotency key expiration > settlement window	If key persists longer than the settlement window (24h > 2s), duplicates are impossible	Still vulnerable during failover window	0ms overhead

4.3 Recommended Architecture

Use Redis Cluster with synchronous replication only for idempotency keys, using the WAIT command:

# After SET, wait for replication to at least 1 replica
def store_idempotent_with_wait(self, key, hash, ttl):
    self.redis.set(key, hash, ex=ttl)
    # Wait for replication to at least 1 replica (timeout: 10ms)
    self.redis.execute_command('WAIT', 1, 10)

Latency impact: WAIT 1 10 adds ≤5ms (p95) in the same data center. Total idempotency overhead becomes ≤7.4ms—still within the budget.

CLOSING — OPERATIONAL RISK OF IDEMPOTENCY FAILURE

If the ASPSP fails to enforce idempotency:

Duplicate payments occur → PSUs are debited twice → complaints to the Financial Ombudsman.
Regulatory breach → PSD2 Article 66 (PISP) requires “the payment transaction shall not be executed more than once.” Fines up to €20M.
Reputational damage → TPPs abandon the ASPSP’s API.

Key takeaways:

Redis Lua scripts provide atomic GET‑SET semantics, preventing race conditions.
409 Conflict is returned when the same key is reused with a different payload.
Exponential backoff with jitter prevents thundering herds (max delay: 30s).
Redis WAIT improves durability but adds ≤5ms latency.

Certificate in Open Banking LESSON 2.3: IDEMPOTENCY KEYS — Deep Dive into Distributed Deduplication

Certificate in Open Banking