Doing it twice should be safe (idempotency)

In a real system, the same request often arrives twice. A user taps "Pay" two times. An app retries after a timeout. A payment provider sends the same notice again. The interviewer asks: "A customer was charged twice. How do you stop that from happening?"

A weak answer says "check if the payment already exists, and then create it". That check has a gap, and two copies that arrive together both pass it. A strong answer gives every action a unique key. It saves the key and the result in the same database transaction, and it lets the database refuse a second copy.

At SDE-1 level you should explain why a retry can create a duplicate. At SDE-2 level you should design the key, the table and the order of steps. At SDE-3 level you should also handle the work that happens outside your database, and say how long keys are kept.

Quick recap (lessons 54, 58 and 60). A retry sends a request again after a timeout, because a timeout means "no answer", not "not done". A queue holds messages. A consumer takes a message, does the job, and then sends an ack, which means "I finished". If the consumer crashes before the ack, the message comes again. If it acks first and then crashes, the job is lost: this is at-most-once. If it works first and then acks, the job can run twice: this is at-least-once. Exactly-once in effect means at-least-once plus skipping repeats.

Think about a lift button. You press it once, and the lift comes. If you press it five times, the lift still comes once. Pressing again does not change the result. A doorbell is different. Every press rings the bell again.

A request or a message is idempotent if handling it many times leaves the system in the same state as handling it once (lesson 9). Setting a value is idempotent: "set the quantity to 2". Adding is not: "add 1", "charge Rs 500", "send an SMS", "create an order".

Why duplicates arrive

1. The user taps twice.
2. The app or a server retries after a timeout (lesson 54).
3. A message is delivered again after a crash or a slow ack (lesson 60).
4. A sender such as a payment provider sends a notice again when your reply is slow. Such a notice is a webhook: a request that another service sends to your server to say that something happened.

You cannot stop these, so you make the receiver safe.

Way 1: make the action idempotent by its shape

Some changes are safe by design. Compare:

• balance = balance + 500 is not idempotent. Run it twice and the balance grows twice.
• UPDATE orders SET status = 'paid' WHERE id = 7 AND status = 'pending' is idempotent. The second run finds no pending row and changes nothing.

Use this when the change can be written as "set to", or as "change if it is still in the old state" (lesson 22). It is free. But many actions, such as adding money, cannot be written like this.

Way 2: an idempotency key

An idempotency key is a unique value that names one action, and the receiver uses it to recognise a repeat. The client makes the key once, when the user starts the action. It is usually a random value such as a UUID (lesson 23). The client sends it in a header named Idempotency-Key, and sends the same key in every retry of that action.

The server keeps a table of keys. Each row holds the key, a hash of the request body (a short fingerprint of it), and the saved response. The server follows these rules:

1. New key: do the work, save the response, and return it.
2. Same key, same body, work finished: do not do the work. Return the saved response. This includes a saved error.
3. Same key, different body: this is a mistake in the client. Refuse with a 4xx error, for example 422.
4. Same key while the first request is still running: refuse with 409 Conflict (lesson 9), or wait for it.

Stripe's API works like this. It saves the status and body of the first request, and returns them for a repeat with the same key. It may remove a key after 24 hours.

Way 3: a unique constraint

How does the server know a key is new? A "look and then insert" has a gap (lesson 22). Two copies that arrive together both look, both see "not found", and both do the work.

The fix is to let the database decide. A unique constraint (lesson 22) allows each key only once. The insert of the key is the check. The database lets only one insert win. A second insert for the same key waits for the first transaction to end. If the first one commits, the second does nothing. If the first one rolls back, the second goes ahead.

The key and the work must go in one transaction (lesson 21):

def credit(payment_id, user_id, amount):
    with db.transaction():
        inserted = db.execute(
            "INSERT INTO processed (payment_id) VALUES (%s) ON CONFLICT DO NOTHING",
            payment_id).rowcount          # 1 if new, 0 if the ID was already saved
        if inserted == 1:
            db.execute("UPDATE wallets SET balance = balance + %s WHERE user_id = %s",
                       amount, user_id)

(db is a made-up helper.) If the program crashes before the commit, both the key and the credit are undone, so a retry works. After the commit, both exist, so a repeat does nothing. Suppose the key were saved in a separate step. A crash between the two steps would leave a credit with no key, or a key with no credit.

Way 4: an idempotent consumer

A consumer that reads messages (lesson 58) uses the same pattern. It takes the key from the message. A good key is the ID of the thing in the real world, such as the payment ID from the provider. A message ID alone can fail, because a producer that sends again may give the new copy a new message ID. The consumer saves the key with its result in one transaction, and then it acks. A repeat finds the key and is skipped.

Work outside your database

Your transaction can undo database changes. It cannot undo a call to another service, such as a card charge or an SMS. Two rules help:

• Send the same key to the other service. Some payment services, such as Stripe, accept an idempotency key for this reason.
• If the other service has no keys, save your intent in your database first. Before you try again, ask that service whether the first try worked.

How long to keep keys

Keep a key longer than the longest time a repeat can arrive: the client retry window, the message delay, and the provider's resend period. After that, delete old keys. A key that was deleted too early lets a late repeat through.

A wallet app. The user adds Rs 500. The payment provider tells our server about the payment with a webhook.

Assumptions (made up to teach with, not real data):

• 100,000 payments per day, each Rs 500.
• The provider resends once if it gets no 200 reply within 10 seconds.
• The p99 of our endpoint is 12 seconds. A key row is 100 bytes.

Step 1: the size of the problem. A p99 of 12 seconds means that 1% of replies take 12 seconds or more. All of them are above 10 seconds. So at least 1% of 100,000 = 1,000 payments get a second webhook. With no protection, 1,000 x Rs 500 = Rs 500,000 (5 lakh) is added twice each day. This answers the predict box.

Step 2: "look, then insert" is not enough. The first webhook arrives at 0 seconds and needs 12 seconds. The resend arrives at 10 seconds, while the first is still running. The first has not saved its ID yet, so the resend looks at the table and finds nothing. Both credit Rs 500. The user has Rs 1,000.

Step 3: add the unique constraint. The code in Way 3 runs for each webhook, with the provider's payment ID as the key.

• The first webhook inserts the ID and adds Rs 500.
• The second webhook tries to insert the same ID. The database makes it wait for the first transaction. After the commit, the insert does nothing and reports 0 rows, so the code skips the credit.
• The code then returns 200, as it does for a first webhook. The provider stops resending.

The user has Rs 500. Duplicates per day: 0.

Step 4: the cost. One extra insert for each of the 100,000 payments. Storage: 100,000 x 100 bytes = 10,000,000 bytes = 10 MB a day. If we keep keys for 7 days: 7 x 10 MB = 70 MB.

Step 5: the same idea on our own API. The app calls POST /wallet/topup with a key. The call times out after 300 ms. The money was taken, and the answer was lost. The app retries with the same key. The server finds the saved response and returns it. One charge of Rs 500, not two charges (Rs 1,000). If the app made a new key for the retry, the server would see a new action, and the user would pay twice.

• An idempotency key solves double charges from taps, retries and resends. It costs an extra write for each request, a table that grows, and a window for how long keys are kept. I would use it for every action that moves money or sends something to a person.
• A unique constraint solves the gap when two copies arrive at the same time. It costs an error or a wait on the second copy, which the code must handle. I would use it instead of "look, then insert".
• A natural idempotent shape solves the problem with no table. It costs the effort to write the change as "set to". I would use it first, and add keys when I cannot.
• Keeping keys longer solves late repeats. It costs storage. I would keep them longer than the longest resend period.

"I check if the payment exists, and then I create it. That is idempotent." Two copies at the same time both pass the check. Only a unique constraint, inside the transaction, closes the gap.

"Each retry should get a new key, so the server sees it as fresh." Then every retry is a new action, and the user is charged again. Use one key for one user action, the same in every retry.

"The second request should return an error." No. The client may have lost the first answer. It needs the same result. Return the saved response, and treat the repeat as a success.

1. What does an idempotency key do? What should the server return for a repeat with the same key and the same body?
2. A system has 250,000 payments a day of Rs 200 each. 0.8% of them get a second webhook, and there is no protection. How much money is credited twice in a day? If a key row is 120 bytes and keys are kept 7 days, how much storage is needed?
3. Find the flaw. The code runs a SELECT on the table done. If the ID is not found, it adds Rs 500 and then inserts the ID. How can it go wrong in two ways? How do you fix it?