De-duplicating client commands in a Raft-backed KV store
Part 4 of this series built a replicated key/value database on top of Raft and exposed a consistency problem: client retries can cause a command to be applied more than once. This post closes that gap by adding client IDs and per-request sequence numbers, then using them to de-duplicate commands as they flow through the Raft log.
A motivating example: APPEND
Before diving into the fix, we need an operation that makes duplicate execution visible. The KV store from Part 4 supports PUT(k,v), GET(k), and CAS(k, cmp, v). We'll add APPEND(k,v), which concatenates v onto the current value of key k, or behaves like PUT(k,v) if the key doesn't exist.
The problem appears immediately with retries. Suppose a client sends APPEND("x","bar") to a leader that commits the entry but crashes before responding. The client retries against a new leader, and the append executes a second time, leaving "foobarbar" in the database instead of "foobar".
The issue isn't the retry itself — retries are unavoidable when a client can't distinguish "request lost" from "response lost." The real deficiency is that the state machine has no way to recognize that a retried command is the same logical operation it already executed.
The de-duplication design
Section 8 of the Raft paper calls this out directly: a leader can crash after committing a log entry but before responding to the client, and the client's retry with a new leader causes double execution. The paper prescribes the standard solution: clients attach unique serial numbers to commands, and the state machine tracks the latest serial number seen from each client along with the associated response. A command whose serial number matches one already executed gets an immediate response without re-execution.
Implementing this requires two identifiers on every command:
- A globally unique client ID, assigned when the client is created
- A per-client command ID, monotonically increasing
Monotonicity matters: the state machine only needs to remember the highest ID seen from each client. Any incoming command with an ID equal to or lower than that high-water mark is a duplicate.
Client-side changes
Two fields are added to the KVClient struct:
// clientID is a unique identifier for a client; it's managed internally // in this file by incrementing the clientCount global. clientID int64 // requestID is a unique identifier for a request a specific client makes; // each client manages its own requestID, and increments it monotonically and // atomically each time the user asks to send a new request. requestID atomic.Int64
The client ID is drawn from a package-level atomic counter at construction time:
func New(serviceAddrs []string) *KVClient {
return &KVClient{
// ... other fields
clientID: clientCount.Add(1),
}
}
// clientCount is used to assign unique identifiers to distinct clients.
var clientCount atomic.Int64
Auto-incrementing integers are sufficient for tests; production code would likely use UUIDs.
requestID tracks the last command sent. Each new API call — for example, Append — increments it before building the request:
// Append the value to the key in the store. Returns an error, or
// (prevValue, keyFound, false), where keyFound specifies whether the key was
// found in the store prior to this command, and prevValue is its previous
// value if it was found.
func (c *KVClient) Append(ctx context.Context, key string, value string) (string, bool, error) {
appendReq := api.AppendRequest{
Key: key,
Value: value,
ClientID: c.clientID,
RequestID: c.requestID.Add(1),
}
var appendResp api.AppendResponse
err := c.send(ctx, "append", appendReq, &appendResp)
return appendResp.PrevValue, appendResp.KeyFound, err
}
The two IDs travel inside the HTTP request body:
type AppendRequest struct {
Key string
Value string
ClientID int64
RequestID int64
}
All other client methods are modified the same way. Retry logic in the shared send method is unchanged: it keeps resending the same command with the same client and request IDs.
Service-side de-duplication
The service now tracks per-client state. A new field on KVService holds the map:
// lastRequestIDPerClient helps de-duplicate client requests. It stores the // last request ID that was applied by the updater per client; the assumption // is that client IDs are unique (keys in this map), and for each client the // requests IDs (values in this map) are unique and monotonically increasing. lastRequestIDPerClient map[int64]int64
The Command struct — the payload submitted to the Raft log — gains the same two identifying fields:
// ClientID and RequestID uniquely identify the request+client. ClientID, RequestID int64 // IsDuplicate is used to mark the command as a duplicate by the updater. When // the updater notices a command that has a client+request ID that has already // been executed, the command is not applied to the datastore; instead, // IsDuplicate is set to true. IsDuplicate bool
The core logic lives in the runUpdater goroutine, which applies committed commands to the state machine:
func (kvs *KVService) runUpdater() {
go func() {
for entry := range kvs.commitChan {
cmd := entry.Command.(Command)
// Duplicate command detection.
// Only accept this request if its ID is higher than the last request from
// this client.
lastReqID, ok := kvs.lastRequestIDPerClient[cmd.ClientID]
if ok && lastReqID >= cmd.RequestID {
kvs.kvlog("duplicate request id=%v, from client id=%v", cmd.RequestID, cmd.ClientID)
// Duplicate: this request ID was already applied in the past!
cmd = Command{
Kind: cmd.Kind,
IsDuplicate: true,
}
} else {
kvs.lastRequestIDPerClient[cmd.ClientID] = cmd.RequestID
switch cmd.Kind {
case CommandGet:
cmd.ResultValue, cmd.ResultFound = kvs.ds.Get(cmd.Key)
case CommandPut:
cmd.ResultValue, cmd.ResultFound = kvs.ds.Put(cmd.Key, cmd.Value)
case CommandAppend:
cmd.ResultValue, cmd.ResultFound = kvs.ds.Append(cmd.Key, cmd.Value)
case CommandCAS:
cmd.ResultValue, cmd.ResultFound = kvs.ds.CAS(cmd.Key, cmd.CompareValue, cmd.Value)
default:
panic(fmt.Errorf("unexpected command %v", cmd))
}
}
// Forward this command to the subscriber interested in its index, and
// close the subscription - it's single-use.
if sub := kvs.popCommitSubscription(entry.Index); sub != nil {
sub <- cmd
close(sub)
}
}
}()
}
The monotonic ID assumption keeps this state O(1) per client. When the updater sees a request that matches or trails the last applied ID for that client, it marks the command as a duplicate instead of applying it. The HTTP handlers must then react; handleAppend, for example, returns a distinct API status for duplicates:
sub := kvs.createCommitSubscription(logIndex)
select {
case commitCmd := <-sub:
if commitCmd.ServiceID == kvs.id {
if commitCmd.IsDuplicate {
kvs.sendHTTPResponse(w, api.AppendResponse{
RespStatus: api.StatusDuplicateRequest,
})
} else {
kvs.sendHTTPResponse(w, api.AppendResponse{
RespStatus: api.StatusOK,
KeyFound: commitCmd.ResultFound,
PrevValue: commitCmd.ResultValue,
})
}
} else {
kvs.sendHTTPResponse(w, api.AppendResponse{RespStatus: api.StatusFailedCommit})
}
case <-req.Context().Done():
return
}
The client treats api.StatusDuplicateRequest as an error and surfaces it. A useful exercise is changing duplicate handling to return the original command's result as a success — that requires recording each request's outcome alongside the client's last ID.
Consistency restored
Part 4 established that the KV service is strict serializable, but noted that adding client retries broke linearizability: from the client's perspective, a retried command could appear to execute twice. With de-duplication, that hole is closed. A retried command that was already committed is never applied again, so the entire system — client included — is strict serializable once more.
Delivery semantics
Without client retries, the underlying Raft protocol gives at-most-once delivery: a command is applied at most once, but may not be applied at all if the cluster can't reach consensus. At-most-once suffices for telemetry or logging, but not for a KV store meant to underpin other applications.
Adding retries moves the system to at-least-once semantics — assuming failures are eventually repaired, the client keeps trying until the command is acknowledged. That guarantee alone allows duplicates when failures strike between commit and response.
De-duplication is what converts at-least-once into exactly-once under realistic failure assumptions: as long as network and hardware failures are transient, a command is applied exactly once to the database, or the client gets an error. This is the same technique used elsewhere — Ron Garret's essay on exactly-once delivery observes that you can build exactly-once atop at-least-once, and the Kafka project applied essentially the same client-ID-plus-sequence-number scheme to achieve exactly-once semantics. Designing Data-Intensive Applications covers the general engineering problem in chapter 12.
Lost updates and retries
Retries without de-duplication are not safe even for operations that appear idempotent at first glance. Consider a simple register keyed "foo" with a default value of 0:
- Client A issues
PUT('foo',1). The leader commits it but crashes before replying. Client A keeps retrying. - A new leader is elected. Client C reads the register and gets 1.
- Client B issues a new
PUT('foo',2)through the new leader, which is committed. - Client C now reads 2.
- Client A's retry reaches the new leader, which commits another instance of
PUT('foo',1), overwriting the value 2. Another read by client C returns 1.
This sequence is not linearizable. Since operation (2) returned 1, operation (1) must have completed before (2). Operation (4)'s result implies (3) happened after (1). Step (5) then violates linearizability.
This is the classic lost update failure: the PUT(2) write is visible only briefly, then erased by the retried PUT(1). The key distinction is that an operation like PUT is only idempotent in isolation. Once its executions interleave with other writes, the result of applying it twice is not the same as applying it once—the second execution can clobber an intervening update.
Real-world occurrence
This is not a purely theoretical concern. etcd, a Raft-based KV store widely used in Kubernetes, has hit exactly this problem in its client libraries. The service itself provides strict serializability, but some clients automatically retry on failure without de-duplication.
A Jepsen analysis of jetcd, a Java client, found that its automatic retry mechanism caused loss of linearizability and recommended disabling retries. The issue has also been discussed extensively with etcd developers in this GitHub issue, with additional context in another thread.
It is easy to assume that set(x, 5) is idempotent because applying it twice in a row still produces the state x = 5. However, this operation is not longer idempotent if its executions are interleaved with other writes—then, it leads to lost update.
Safe retries in versioned stores
etcd does not support operations like APPEND, but its data store is versioned, which enables a safer write pattern. An application can use a compare-and-swap style check to ensure no concurrent modifications have occurred before applying a write:
1. Read revision --> $rev
2. TXN
if mod_revision(k) == $rev
PUT(k, v)
Such a write only assigns store(k)=v if nothing else has changed the database in the meantime. Because every successful write bumps the store's revision, the lost-update scenario cannot happen. If the operation fails—due to a crash or a revision mismatch—it can be safely retried; the concern is liveness, not safety.
This series covered building a full Raft consensus module in Go plus a strictly serializable KV database on top of it. Questions and comments are welcome via email or GitHub issues.
