This resume is also available in English.

4. Reliability2 / 4 · All columns

Columns › 4. Reliability › Part 14

Idempotency and Distributed Locks

冪等與分散式鎖

Retries and at-least-once delivery make duplicate work the norm. This article uses idempotency keys, unique constraints and dedupe tables so duplicates take effect once, then dissects Redis locks, lease expiry and fencing tokens, and why locks alone cannot protect payments.

  • Go
  • Microservices
In this article
  1. What this article solves
  2. Step 1: First, tell which operations are naturally idempotent
  3. Step 2: Blocking duplicate business records with unique constraints
  4. Step 3: Idempotency keys and a request dedupe table
  5. Step 4: Running idempotency keys in Go
  6. Step 5: At-least-once delivery makes idempotency a necessity
  7. Step 6: Distributed locks and leases
  8. Step 7: Why locks alone can't protect payments: fencing tokens
  9. Common pitfalls
  10. Key takeaways
  11. Next

In the previous article, “Timeouts, Retries and Circuit Breakers”, we taught the order service to time out, retry with backoff and fail fast when downstreams misbehave; this article deals with the side effect retries leave behind: when a request may be sent twice, how do you guarantee the money is charged only once?

What this article solves

Distributed systems have a fact that is hard to accept but must be accepted: the caller often doesn't know whether the other side actually did the work. order calls payment to charge and waits until it times out; there are three possibilities: the request never arrived, the request arrived and is still being processed, or the charge succeeded but the response was lost on the way back. From the caller's point of view, all three look exactly the same.

The previous article said that only idempotent operations can be retried safely. But "don't retry" isn't a solution either: users hit refresh themselves, mobile networks resend automatically, gateways retry and message queues redeliver. In other words, duplicate requests will definitely happen; the only question is whether we are prepared.

The goal of this article is to make "doing it twice" have the same effect as "doing it once", which is what idempotent means. We'll first use database unique constraints and idempotency keys to handle duplicate requests at the API layer, then discuss another tool often used to prevent duplicates: distributed locks. The conclusion up front: locks can reduce concurrent conflicts, but they cannot guarantee correctness on their own; the real guarantee has to come from constraints on the storage side, such as unique indexes, conditional updates and fencing tokens.

MechanismWhat it blocksStrength of guarantee
Unique constraintThe same business record being created twiceStrong, guaranteed by the database
Idempotency key + dedupe tableThe same API request being executed twiceStrong, provided it is in the same transaction as the business write
Distributed lockSeveral instances doing the same thing at onceWeak, there may be two holders after a lease expires
Fencing tokenWrites from an expired lock holderStrong, provided the storage side checks it

Step 1: First, tell which operations are naturally idempotent

The definition of idempotent: executing the same operation once or many times leaves the system in the same final state. Note that it is the "state" that is the same, not the "response"; deleting the same record a second time may return 404, but the database state hasn't changed, so it is still idempotent.

The HTTP specification defines GET, PUT and DELETE as idempotent, and POST as not. But this is only a semantic convention; the implementation is what counts. Taking the order service as an example:

  • PUT /orders/{id}/status setting the status to cancelled: setting it once or ten times gives the same result, naturally idempotent.
  • POST /orders/{id}/items adding an item: each call adds one more, not idempotent.
  • UPDATE inventory SET stock = stock - 1: each call removes one more, not idempotent.
  • UPDATE inventory SET stock = 9 WHERE sku = 'book-1': sets an absolute value, idempotent, but overwrites other people's concurrent updates.

Rewriting a "relative operation" as an "absolute operation" is the first technique for making operations idempotent, but as the last example above shows, it often conflicts with concurrency safety. The second technique is to give every operation a unique identity: the system remembers which identities it has already handled and doesn't handle duplicates again. That identity can be a natural business key (for example, an order can have only one payment), or an idempotency key generated by the caller. The following steps all implement this idea.

Step 2: Blocking duplicate business records with unique constraints

The most reliable deduplication tool is a database unique constraint, because it holds under concurrency too: if two transactions insert the same key at the same time, the database guarantees that only one succeeds. An application-level "check whether it exists, insert if not" is wrong under concurrency: two requests can both find "not there" at the same time and then both insert successfully; “Concurrency Pitfalls: From Data Races to Overselling” has more examples of this kind of problem.

Taking payments as an example, the business rule is "an order has only one successful charge", so write it directly as a constraint: add a unique index on order_id in the payments table. When the payment service receives a duplicate charge request, inserting the payment record fails because of the unique constraint, so the service knows this order has already been processed and simply returns the existing payment result.

Finding a natural business key is the first-choice approach, because it doesn't depend on the caller's cooperation. But not every operation has a natural key, for example "a user creates a new order": the same user may genuinely want to place two identical orders in a row, and the system can't tell from the content whether the second request is a duplicate or a new one. Then the caller has to tell us whether the two requests are the same intent.

Step 3: Idempotency keys and a request dedupe table

An idempotency key is a unique value the caller generates for each "operation intent", usually a UUID, sent in the Idempotency-Key header. The key word is "intent": when the user presses "Place order" once, the front end generates one key; however many times this request is resent because of the network, it carries the same key. Only when the user really wants to place another order is a new key generated.

The server records the keys it has seen in a dedupe table:

-- Idempotency keys are scoped by "user + key" so different users' keys don't collide
CREATE TABLE idempotency_keys (
    user_id      bigint      NOT NULL,
    key          text        NOT NULL,
    request_hash text        NOT NULL,           -- hash of the request body, guarding against the same key with a different body
    status       text        NOT NULL DEFAULT 'processing', -- processing / done
    response     jsonb,                          -- the response once done, replayed verbatim on retries
    created_at   timestamptz NOT NULL DEFAULT now(),
    PRIMARY KEY (user_id, key)
);

-- The business-level natural key: an order can have only one payment
CREATE TABLE payments (
    id         bigserial PRIMARY KEY,
    order_id   text      NOT NULL UNIQUE,
    amount     bigint    NOT NULL,               -- in minor units (cents), consistent with Order.Total
    status     text      NOT NULL
);

-- The first step is always "race to insert"; 0 rows affected means the key already exists
INSERT INTO idempotency_keys (user_id, key, request_hash)
VALUES ($1, $2, $3)
ON CONFLICT (user_id, key) DO NOTHING;

The processing flow splits into four cases:

Client Idempotency-Key Order service insert the key first, then work idempotency_keys PK = idempotency key Insert succeeds this is a new request charge, create order store the response 201 Exists: processing previous one not done must not run again client retries later 409 Exists: completed same body hash no side effects run replay the response same 201 Exists: mismatch the same key used for another body client's mistake 422

Figure: a successful insert means this is a new request and this request is responsible for executing it; if the insert fails, read the existing record and, depending on its status, return 409, replay the original response, or return 422 if the body doesn't match.

  1. Insert succeeds: this is the first time the key has been seen; execute the business logic, and when done set the status to done and store the response.
  2. Exists and in progress: the previous request with the same key is still running (the user double-clicked); return 409 and ask the caller to retry later. It must never be executed again.
  3. Exists and completed: replay the stored response, including status code and body. The caller gets exactly the same result as the first time, and that is complete idempotency.
  4. Exists but the body differs: the same key was used to send a different request, which is the caller's mistake; return 422. Without this check, a reused key would make a second order silently be treated as a replay of the first.

The most crucial design point: the business write and the status update of the idempotency record must be in the same database transaction. If the order is created successfully but the program crashes before updating the idempotency record, the next retry sees processing stuck there; conversely, if you mark the idempotency record done first and then write the order, a failed order write leaves a "completed" key with no order. The transaction approach introduced in “database/sql, Transactions and Connection Pools in Go” comes in handy here: create the order and update the idempotency record within the same *sql.Tx, and commit them together.

When the business logic needs to call another service (such as charging), it can no longer be in the same transaction as the local database. Then you pass idempotency down: when the order service calls the payment service, it also sends an idempotency key (which can be derived from the order number, such as charge:{order_id}), so the payment service deduplicates on its own. Idempotency is a property that is passed all the way down; if any layer breaks the chain, retries can cause duplicates.

There are two more practical details. First, when processing fails you have to decide what to do with the idempotency record: if the failure left no side effects (for example, argument validation failed), you can delete the record so the caller can retry with the same key; if it may have left side effects, store the failure response to avoid retries causing inconsistency. Second, processing records need a timeout mechanism, otherwise a program crash leaves that key stuck forever; a common approach is to record the start time and allow a takeover after a certain period (the takeover must be able to safely re-execute or query the downstream's real state). The idempotency records themselves also need a retention period, for example cleared after one day to one week, and the period must cover every possible retry window of the caller.

Step 4: Running idempotency keys in Go

The program below simulates the dedupe table in memory, demonstrating five concurrent requests with the same key, one later retry, and the same key with a different body; at the end the program also previews the fencing token discussed in Step 7:

package main

import (
	"crypto/sha256"
	"encoding/hex"
	"errors"
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

var (
	ErrInProgress = errors.New("409: a request with the same idempotency key is still being processed")
	ErrKeyReused  = errors.New("422: idempotency key reused with a different body")
	ErrStaleFence = errors.New("rejected: stale fencing token")
)

// ---------- Idempotency keys: simulating the idempotency_keys table in the database ----------

type record struct {
	reqHash  string
	done     bool
	response string
}

type IdemStore struct {
	mu   sync.Mutex
	rows map[string]*record // primary key = idempotency key, equivalent to a UNIQUE constraint
}

// Begin tries to "insert" a row; success means this request is mine to execute
func (s *IdemStore) Begin(key, reqHash string) (replay string, mine bool, err error) {
	s.mu.Lock()
	defer s.mu.Unlock()
	r, ok := s.rows[key]
	if !ok {
		s.rows[key] = &record{reqHash: reqHash}
		return "", true, nil
	}
	if r.reqHash != reqHash {
		return "", false, ErrKeyReused
	}
	if !r.done {
		return "", false, ErrInProgress
	}
	return r.response, false, nil
}

func (s *IdemStore) Finish(key, response string) {
	s.mu.Lock()
	defer s.mu.Unlock()
	s.rows[key].done, s.rows[key].response = true, response
}

func hash(body string) string {
	sum := sha256.Sum256([]byte(body))
	return hex.EncodeToString(sum[:8])
}

var charges atomic.Int64 // number of actual charges

func placeOrder(s *IdemStore, key, body string) (string, error) {
	replay, mine, err := s.Begin(key, hash(body))
	if err != nil {
		return "", err
	}
	if !mine {
		return replay + " (replay)", nil
	}
	charges.Add(1)                    // the side effect happens only here, once
	time.Sleep(20 * time.Millisecond) // simulate the time taken to call the payment service
	resp := "201 order A-1001 created"
	s.Finish(key, resp)
	return resp, nil
}

// ---------- Fencing token: simulating the protected resource ----------

type Ledger struct {
	mu        sync.Mutex
	lastFence int64
	balance   int
}

func (l *Ledger) Write(fence int64, delta int) error {
	l.mu.Lock()
	defer l.mu.Unlock()
	if fence <= l.lastFence {
		return fmt.Errorf("%w: got %d, already seen %d", ErrStaleFence, fence, l.lastFence)
	}
	l.lastFence = fence
	l.balance += delta
	return nil
}

func main() {
	s := &IdemStore{rows: map[string]*record{}}
	body := `{"sku":"book-1","qty":1}`

	// The user clicks five times, and five requests arrive at once carrying the same idempotency key
	var wg sync.WaitGroup
	for i := range 5 {
		wg.Add(1)
		go func() {
			defer wg.Done()
			resp, err := placeOrder(s, "key-7f3a", body)
			fmt.Printf("concurrent request %d: resp=%q err=%v\n", i, resp, err)
		}()
	}
	wg.Wait()

	resp, err := placeOrder(s, "key-7f3a", body)
	fmt.Printf("later retry: resp=%q err=%v\n", resp, err)
	_, err = placeOrder(s, "key-7f3a", `{"sku":"book-2","qty":9}`)
	fmt.Printf("same key, different body: err=%v\n", err)
	fmt.Printf("actual charges: %d\n", charges.Load())

	// Client A stalls after getting token 33 (e.g. a GC pause), its lease expires, and B gets 34
	l := &Ledger{}
	fmt.Println("B writes:", l.Write(34, -100))
	fmt.Println("A writes after waking:", l.Write(33, -100))
	fmt.Println("balance:", l.balance)
}

The output is as follows (the order of the concurrent requests differs on every run):

concurrent request 3: resp="" err=409: a request with the same idempotency key is still being processed
concurrent request 1: resp="" err=409: a request with the same idempotency key is still being processed
concurrent request 2: resp="" err=409: a request with the same idempotency key is still being processed
concurrent request 0: resp="" err=409: a request with the same idempotency key is still being processed
concurrent request 4: resp="201 order A-1001 created" err=<nil>
later retry: resp="201 order A-1001 created (replay)" err=<nil>
same key, different body: err=422: idempotency key reused with a different body
actual charges: 1
B writes: <nil>
A writes after waking: rejected: stale fencing token: got 33, already seen 34
balance: -100

The map plus mutex in IdemStore.Begin plays the role of INSERT ... ON CONFLICT DO NOTHING: check and insert are a single indivisible action. In a real system this guarantee comes from the database's unique constraint, so even if the order service runs ten instances, only one request can insert successfully. This is the key point: the correctness of idempotency keys comes from an atomic operation on shared storage, not from state in the application's memory.

Step 5: At-least-once delivery makes idempotency a necessity

Besides API retries, another source of duplicates is messages. The next article, “Message Queues and Event-Driven Design”, covers this in detail; here we establish one idea first: message systems have roughly three delivery semantics.

SemanticsMeaningCost
At-most-onceMay be lost, never duplicatedAcknowledge first, then process; if processing fails, the message is lost
At-least-onceNever lost, may be duplicatedProcess, then acknowledge; a crash before acknowledging causes redelivery
Exactly-onceNeither lost nor duplicatedAcross systems it can only be "simulated" with idempotency

Most businesses choose at-least-once, because a lost payment event is harder to remedy than one processed twice. And "exactly-once" is fundamentally impossible across a network and multiple systems: if a consumer finishes processing a message and crashes before acknowledging it, the message system cannot know whether processing actually completed. Kafka's exactly-once semantics refer to the closed loop inside Kafka of "read, process, write back to Kafka"; as soon as a side effect lands outside Kafka (writing to a database, calling a payment gateway), you're back to application-level idempotency.

So what the industry commonly calls "exactly-once" is more precisely effectively-once: delivery is at-least-once, processing is idempotent, and together the final effect is equivalent to exactly-once. Consumers implement idempotency the same way as APIs: use the event ID as the dedupe key and record "this event has been processed" in the same transaction as the business processing. This table is often called an inbox, and it appears again in “Distributed Transactions: Sagas and the Outbox Pattern”.

Step 6: Distributed locks and leases

Having covered idempotency, let's look at another tool often used to "avoid duplicates": distributed locks. A typical requirement: the order service runs several instances, a reconciliation job must run once every early morning, and you want only one instance to do it; or a cancellation and a payment callback for the same order arrive at the same time, and you want them processed one after the other.

The standard way to implement a lock with Redis is SET key token NX PX ttl: NX means set only if the key doesn't exist, and PX sets a millisecond expiry. There are three details here, and you can't do without any of them:

  1. There must be an expiry (a lease). If the instance holding the lock crashes, the lock doesn't disappear by itself; without an expiry the resource is locked forever.
  2. The value must be a random token. When unlocking, you must confirm "this lock is still mine" before deleting it; otherwise, if A's lock expires and B gets it, A runs DEL after finishing and deletes B's lock.
  3. Check and delete must be atomic. "GET to compare the token, then DEL if it matches" is two commands that can be interleaved, so use a Lua script to do it in one go on the Redis side.
// Snippet: using github.com/redis/go-redis/v9
package lock

import (
	"context"
	"crypto/rand"
	"encoding/hex"
	"errors"
	"time"

	"github.com/redis/go-redis/v9"
)

var ErrNotAcquired = errors.New("lock: not acquired")

// Increment the fencing counter while acquiring the lock; both keys use the same hash tag so they land in the same slot under Redis Cluster
var acquireScript = redis.NewScript(`
if redis.call("SET", KEYS[1], ARGV[1], "NX", "PX", ARGV[2]) then
  return redis.call("INCR", KEYS[2])
end
return 0`)

// Delete only if the token matches, to avoid deleting someone else's lock
var releaseScript = redis.NewScript(`
if redis.call("GET", KEYS[1]) == ARGV[1] then
  return redis.call("DEL", KEYS[1])
end
return 0`)

type Lock struct {
	rdb   *redis.Client
	key   string
	token string
	Fence int64 // handed to the protected resource to check
}

func Acquire(ctx context.Context, rdb *redis.Client, name string, ttl time.Duration) (*Lock, error) {
	b := make([]byte, 16)
	if _, err := rand.Read(b); err != nil {
		return nil, err
	}
	key := "{lock:" + name + "}"
	token := hex.EncodeToString(b)
	fence, err := acquireScript.Run(ctx, rdb, []string{key, key + ":fence"}, token, ttl.Milliseconds()).Int64()
	if err != nil {
		return nil, err
	}
	if fence == 0 {
		return nil, ErrNotAcquired
	}
	return &Lock{rdb: rdb, key: key, token: token, Fence: fence}, nil
}

func (l *Lock) Release(ctx context.Context) error {
	return releaseScript.Run(ctx, l.rdb, []string{l.key}, l.token).Err()
}

On a single Redis node this implementation is a correct "best-effort" lock. But look back at the first detail and the problem appears: leases expire, and the holder doesn't necessarily know its lease has expired.

Step 7: Why locks alone can't protect payments: fencing tokens

Imagine this scenario: client A gets the lock with a ten-second lease. A starts processing but hits a very long pause; it might be a garbage-collection pause, the operating system swapping the process out of memory, the virtual machine being migrated, or simply a network packet being delayed for a long time. During the pause the lease expires, client B gets the same lock, starts processing and writes. Then A wakes up; it doesn't know how long it slept, believes it still holds the lock, and writes too. Now both "holders" have written, and the lock has done nothing at all.

Could A check whether it still holds the lock before writing? That doesn't help: there is always a gap between the check and the write, and a pause can happen between any two lines of code. This is the core argument Martin Kleppmann made when analysing distributed locks: in a system with process pauses and network delays, time-based leases cannot guarantee mutual exclusion on their own.

His proposed solution is the fencing token: every time the lock service grants a lock, it attaches a monotonically increasing number. The holder must include this number when writing to the protected resource, and the resource side remembers the largest value it has seen and rejects any token smaller than (or equal to) it.

Client A Lock service Client B get lock GC pause / network delay A's lease (PX 10s) expires B's lease token 33 token 34 write (34) OK wakes, writes (33) Store: remembers the highest token seen = 34 33 ≤ 34 → reject A's stale write

Figure: A pauses after getting token 33, its lease expires, and B gets 34 and writes successfully; when A wakes up and writes with 33, the store rejects it because it has already seen 34.

Note that the source of the guarantee has moved: it is no longer "the lock guarantees only one writer" but "the store guarantees that a stale holder can't write". In a database, this needs only a conditional update:

-- The protected resource remembers the largest fencing token itself
ALTER TABLE inventory_reservations ADD COLUMN last_fence bigint NOT NULL DEFAULT 0;

UPDATE inventory_reservations
SET    quantity = $2,
       last_fence = $3
WHERE  order_id = $1
  AND  last_fence < $3;   -- 0 rows affected → the token is stale and this write is rejected

This also answers the question in the heading. Taking payments as an example, a lock can only "reduce" the probability of two instances charging at the same time; when the lock fails because its lease expired, what actually blocks a duplicate charge is the payment service's idempotency key and the unique constraint on payments.order_id. An external payment gateway won't check fencing tokens for you, so for external charges the idempotency key is the only reliable line of defence.

There are two more limitations of Redis to know about. First, primary–replica setups use asynchronous replication: if the primary grants a lock and crashes before replicating it, the lock is gone once the replica is promoted, and another client can acquire it again; the fencing counter may also go backwards as a result, so where strictness is required the counter should come from a linearisable source, such as a database sequence or an etcd revision. Second, the Redlock algorithm proposed by Redis uses voting across several independent nodes to reduce this risk, but Kleppmann points out that it relies on the assumptions that "clock drift is bounded and pauses are bounded", and it provides no fencing token, so it isn't suitable where correctness matters. The author of Redis has a different view, and the debate is worth reading; the practical consensus is roughly:

  • For efficiency (avoiding doing the same expensive but harmless work twice, such as rebuilding a cache): a single-node Redis lock is enough, and the occasional failure just wastes a few resources.
  • For correctness (where executing twice causes errors, such as charging or deducting stock): don't rely on the lock alone; use database constraints, conditional updates and fencing tokens, or a consensus-based coordination service such as etcd or ZooKeeper, and have the resource side take part in the check.

Common pitfalls

  • Check then insert: an application-level "create if not found" creates both under concurrency; deduplication must rely on a unique constraint or an atomic operation.
  • Keeping idempotency keys only in memory or a local cache: with a multi-instance deployment, a retry that lands on another instance defeats it. Dedupe state must live in storage shared by all instances.
  • The business write and the idempotency record not in the same transaction: a crash leaves an inconsistent state of "done but not recorded" or "recorded but not done".
  • Not comparing the request body: when the same key is sent with a different body and the old response is silently replayed, the second operation simply disappears.
  • Idempotency at only one layer: the order service deduplicates, but it doesn't pass an idempotency key when calling the payment service, so on retry the payment service still charges twice.
  • A lock with no expiry, or a fixed value as the token: the former locks forever when the holder crashes; the latter lets A mistakenly delete B's lock.
  • Thinking it's safe to check the lock is still held: a pause between the check and the write can't be avoided; have the resource side reject stale writes with a fencing token.
  • Using a Redis lock where correctness matters: asynchronous replication and lease expiry can both make the lock fail; payments and inventory must rely on database constraints and idempotency.
  • Treating "exactly-once" as something the message system does for you: side effects across systems can only achieve effectively-once through idempotent consumption.

Key takeaways

  • Duplicate requests will happen; the goal is to make "doing it twice" have the same effect as "doing it once".
  • Prefer natural business keys plus unique constraints; where there is no natural key, have the caller generate an idempotency key representing one operation intent.
  • The dedupe table must record the request hash, status and response; return 409 while in progress, replay the response once completed, and return 422 when the body doesn't match.
  • Put the business write and the idempotency record in the same transaction; across services, pass the idempotency key all the way down.
  • At-least-once delivery plus idempotent processing is the practical form of "exactly-once".
  • Redis locks need SET NX PX, a random token and atomic Lua unlocking; but a lease can expire without the holder knowing.
  • Fencing tokens move the guarantee to the resource side; for operations where correctness matters, the last line of defence is database constraints and idempotency, not locks.

Next

Idempotency makes duplicate messages no longer frightening, but orders, inventory and payments still call each other synchronously, so if any one service slows down the whole order flow gets stuck. The next article, “Message Queues and Event-Driven Design”, turns parts of the flow into asynchronous events and covers partitions, consumer groups, redelivery and dead-letter queues.