Raft-Backed Exactly-Once Deduplication Logs

Part of: Consensus Algorithms for Deduplication

The Raft consensus protocol does more than replicate a log — its original paper specifies an explicit mechanism for exactly-once semantics: a session table keyed by client identity and request serial number, stored inside the replicated state machine itself. This page is an implementation runbook for that mechanism applied to idempotency keys, using etcd (Go clientv3, using the store’s revision as a commit-index proxy) and the embeddable hashicorp/raft library. It assumes you already understand the commit-then-execute model and the broader guarantee contract in Distributed Coordination & Locking Strategies.

---

Problem statement and prerequisites

What you are implementing: a replicated dedup log where every idempotency key is committed as a state-machine entry by majority quorum, with client-request-id deduplication happening inside the state machine’s Apply function — not as a separate database lookup bolted on afterward.

Prerequisites:

• A Raft-backed store: either an etcd cluster of 3 nodes or 5 nodes, or an embedded hashicorp/raft group compiled into your service.
• Familiarity with the consensus-backed idempotency guarantee model — specifically linearizable reads and the commit-then-execute ordering.
• Understanding of exactly-once vs. at-least-once delivery semantics, since this pattern is how you actually achieve the “exactly-once” side of that trade-off at the storage layer.
• If you plan to run session-table entries with a bounded lifetime, review lease management and, specifically, implementing lease heartbeat renewal with etcd for how etcd leases interact with key expiry.

---

The session-table mechanism

Raft’s own paper (Ongaro & Ousterhout, Section 8) solves duplicate command execution by having the replicated state machine track, per client, the highest serial number processed and the response returned for it. Applied to idempotency:

• The “client identifier” is your idempotency key (or a client_id + request_id composite for multi-step workflows).
• The “serial number” is a strictly increasing counter the client attaches per logical operation, or simply the idempotency key acting as its own single-use serial.
• The “cached response” is the serialized result of the business logic, stored in the same log entry that recorded the key as seen.

Critically, this check-and-record happens inside the deterministic Apply function that every replica runs identically — not in a side table that could diverge from the replicated log. That is what makes the guarantee exactly-once rather than at-least-once-with-best-effort-dedup: the deduplication decision is part of the same atomic, quorum-committed operation as the state mutation itself.

---

Sequence: committing a dedup entry and replaying after leader change

---

Step-by-step implementation

Step 1 — Model each idempotency key as a session-table entry in the state machine

hashicorp/raft (Go FSM)

type dedupFSM struct {
    mu      sync.Mutex
    session map[string]sessionEntry // key: idempotencyKey
}

type sessionEntry struct {
    Serial   uint64
    Response []byte
    AppliedAt int64 // unix seconds, for retention-window compaction
}

// Apply runs identically and deterministically on every replica.
func (f *dedupFSM) Apply(log *raft.Log) interface{} {
    var cmd struct {
        Key    string
        Serial uint64
        Body   []byte
    }
    if err := json.Unmarshal(log.Data, &cmd); err != nil {
        return err
    }

    f.mu.Lock()
    defer f.mu.Unlock()

    if existing, ok := f.session[cmd.Key]; ok && existing.Serial >= cmd.Serial {
        return existing.Response // duplicate — return cached result, do not re-execute
    }

    response := executeBusinessLogic(cmd.Body) // deterministic, no external side effects here
    f.session[cmd.Key] = sessionEntry{
        Serial:    cmd.Serial,
        Response:  response,
        AppliedAt: time.Now().Unix(),
    }
    return response
}

etcd (Go clientv3, using revision as the commit-index proxy)

etcd does not expose a custom FSM the way hashicorp/raft does, but its atomic transaction primitive gives the same create-if-absent-else-return-existing semantics, with the store’s mod-revision serving as a stand-in for a Raft log index:

cli, _ := clientv3.New(clientv3.Config{
    Endpoints:   []string{"etcd-0:2379", "etcd-1:2379", "etcd-2:2379"},
    DialTimeout: 3 * time.Second,
})

key := "/dedup/session/" + idempotencyKey
txn := cli.Txn(ctx).
    If(clientv3.Compare(clientv3.CreateRevision(key), "=", 0)).
    Then(clientv3.OpPut(key, string(responseBody))).
    Else(clientv3.OpGet(key))

resp, err := txn.Commit()
if err != nil {
    return nil, err
}
if !resp.Succeeded {
    // Key already exists at some earlier revision — duplicate, return cached body.
    return resp.Responses[0].GetResponseRange().Kvs[0].Value, nil
}
// resp.Header.Revision is the etcd store revision this write committed at —
// use it as your commit-index equivalent for read-your-writes checks.
return responseBody, nil

Step 2 — Commit the entry through Raft before executing business logic

For the embedded hashicorp/raft path, submit the command and block for the commit future before treating the request as authoritative:

cmdBytes, _ := json.Marshal(struct {
    Key    string
    Serial uint64
    Body   []byte
}{Key: idempotencyKey, Serial: serial, Body: requestBody})

future := raftNode.Apply(cmdBytes, 5*time.Second)
if err := future.Error(); err != nil {
    return nil, fmt.Errorf("raft apply failed: %w", err)
}
response := future.Response().([]byte)

future.Error() returns non-nil if the local node lost leadership before the entry committed — in that case, the caller must retry against the new leader with the same idempotency key and serial number, not generate a new one.

Step 3 — Serve duplicate detection from a linearizable read

Before proposing a new entry, issue a linearizable read to short-circuit execution entirely when the key is already known, avoiding an unnecessary log append:

func CheckDuplicate(ctx context.Context, cli *clientv3.Client, key string) ([]byte, bool, error) {
    // WithSerializable(false) is the default — this issues a linearizable
    // quorum read, not a stale local read from a follower.
    resp, err := cli.Get(ctx, "/dedup/session/"+key)
    if err != nil {
        return nil, false, err
    }
    if len(resp.Kvs) > 0 {
        return resp.Kvs[0].Value, true, nil
    }
    return nil, false, nil
}

Step 4 — Bound session-table growth with log compaction and a retention window

An unbounded session table eventually exhausts memory on every replica. Snapshot the FSM state periodically and evict entries older than the retention window — but only entries whose age exceeds the maximum possible client retry window, or a legitimate retry will look like a brand-new, never-seen request.

func (f *dedupFSM) Snapshot() (raft.FSMSnapshot, error) {
    f.mu.Lock()
    defer f.mu.Unlock()
    // Copy the full session table into the snapshot — compaction must never
    // silently drop entries the log itself is about to discard.
    copySession := make(map[string]sessionEntry, len(f.session))
    for k, v := range f.session {
        copySession[k] = v
    }
    return &dedupSnapshot{session: copySession}, nil
}

func (f *dedupFSM) EvictExpired(retentionSeconds int64) int {
    f.mu.Lock()
    defer f.mu.Unlock()
    cutoff := time.Now().Unix() - retentionSeconds
    evicted := 0
    for k, v := range f.session {
        if v.AppliedAt < cutoff {
            delete(f.session, k)
            evicted++
        }
    }
    return evicted
}

Run EvictExpired on a schedule with retentionSeconds set to at least 86400 (24 hours) for payment flows, matching the retention guidance already established for consensus-backed idempotency stores. For etcd, attach a lease instead of running a manual sweep:

lease, _ := cli.Grant(ctx, 86400) // 24-hour TTL in seconds
cli.Put(ctx, "/dedup/session/"+idempotencyKey, string(responseBody), clientv3.WithLease(lease.ID))

Step 5 — Verify exactly-once behavior across a leader change

Do not ship this without proving the retry-after-leader-change path actually returns the cached response instead of re-executing. See the verification commands below.

---

Verification and testing

Force a leader change mid-retry-window and confirm no duplicate execution

# Identify the current leader in a 3-node hashicorp/raft or etcd cluster
etcdctl endpoint status --cluster -w table

# Kill the leader process to force an election
kill -9 $(pgrep -f raft-node-leader)

# Confirm a new leader is elected within the election timeout
etcdctl endpoint status --cluster -w table
# Expect exactly one node reporting IS_LEADER=true within ~300-500ms

# Replay the client's original request with the SAME idempotency key
curl -X POST https://api.internal/charge \
  -H "Idempotency-Key: K1" -d '{"amount": 4200}'
# Expect: HTTP 200 with the ORIGINAL cached response body, not a new charge.
# Confirm business-side effect count did not increase:
psql -c "SELECT count(*) FROM charges WHERE idempotency_key = 'K1';"
# Expected: count = 1

Verify session-table entries survive a snapshot/compaction cycle

# Trigger a manual snapshot on hashicorp/raft (exposed via your admin endpoint)
curl -X POST http://raft-node:8080/admin/snapshot

# Restart the node to force state to be rebuilt from the snapshot, not the raw log
systemctl restart raft-node

# Confirm the previously committed key is still recognized as a duplicate
curl -X POST https://api.internal/charge \
  -H "Idempotency-Key: K1" -d '{"amount": 4200}'
# Expected: cached response returned; charges count unchanged

Confirm linearizable reads reject a stale follower

etcdctl get /dedup/session/K1 --consistency=l   # linearizable (default) — authoritative
etcdctl get /dedup/session/K1 --consistency=s   # serializable — may read stale data from a lagging follower
# Compare mod-revision between the two; a mismatch confirms the follower is lagging
# and that --consistency=s must never be used for dedup decisions.

---

Failure scenarios and debugging

---

SRE / observability checklist

1. raft_leader_changes_total — Counter; alert if it exceeds 3 per 5-minute window, which precedes elevated retry-induced latency even when correctness holds.
2. dedup_session_table_size — Gauge tracking in-memory session-table cardinality per node; alert if growth outpaces EvictExpired cadence, signaling a compaction bug.
3. dedup_commit_latency_ms — Histogram (p50/p99) for the full propose-to-commit round trip; alert on p99 above 50 ms for embedded Raft or 8 ms for etcd LAN deployments.
4. dedup_stale_read_total — Counter incremented whenever a duplicate-detection read is served with anything other than linearizable consistency; should always read 0 in production.
5. dedup_premature_eviction_total — Counter; any non-zero value means a legitimate retry was treated as a new request, indicating the retention window is shorter than the client’s actual retry window.
6. Structured log fields on every apply — idempotency_key, serial, raft.term, raft.commit_index, event (committed | duplicate_detected | evicted). Index on idempotency_key for incident triage.

---

Related

• Consensus Algorithms for Deduplication — parent: the commit-then-execute model and linearizability guarantees this Raft session-table pattern implements.
• Coordinating Deduplication with ZooKeeper — sibling: the ZAB-based equivalent using ephemeral-sequential znodes instead of a replicated session table.
• Exactly-Once vs. At-Least-Once Delivery — foundational: the delivery-semantics trade-off this pattern resolves at the storage layer.
• Implementing Lease Heartbeat Renewal with etcd — related: how to keep an etcd lease alive for long-running session-table entries.
• Lock Timeout & Lease Management — related: TTL sizing principles applied here to session-table retention windows.