MVCC store

Source: server/storage/mvcc/.

Purpose

mvcc is etcd's user-facing data layer. Every key holds a history of revisions, not a single value. Reads can specify a revision to time-travel; watchers stream every event after a chosen revision; compactions discard history older than a chosen point. The same package owns the watcher implementation.

Directory layout

server/storage/mvcc/
├── kv.go, kv_view.go         # KV interface and read/write views
├── kvstore.go                # store struct, currentRev, compactMainRev
├── kvstore_txn.go            # store TXNs
├── kvstore_compaction.go     # compaction worker
├── store.go                  # public Store factory
├── revision.go               # main+sub revision arithmetic
├── index.go, key_index.go    # in-memory btree mapping key -> revisions
├── watchable_store.go        # adds watch fan-out on top of store
├── watchable_store_txn.go
├── watcher.go, watcher_group.go
├── hash.go                   # MVCC hashing for cluster-wide consistency check
├── metrics.go, metrics_txn.go
├── testutil/
└── ...

Key abstractions

Symbol	File	Description
KV interface	server/storage/mvcc/kv.go	The contract every EtcdServer uses for storage
store	server/storage/mvcc/kvstore.go	Bbolt-backed implementation; tracks currentRev, compactMainRev
index (treeIndex)	server/storage/mvcc/index.go	In-memory btree of keyIndex per key
keyIndex	server/storage/mvcc/key_index.go	Per-key revision history with generations
revision	server/storage/mvcc/revision.go	{main, sub} 16-byte encoded
watchableStore	server/storage/mvcc/watchable_store.go	Adds synced/unsynced watcher groups + sync goroutine
watcherGroup	server/storage/mvcc/watcher_group.go	Interval-tree of watchers indexed by key range
HashStorage	server/storage/mvcc/hash.go	Periodically computes and stores hashes of the keyspace for corruption detection

Sentinels:

• ErrCompacted — requested revision is older than compactMainRev.
• ErrFutureRev — requested revision is greater than currentRev.

How it works

graph TD
    txn[Apply Txn] --> w[Write txn]
    w --> idx[treeIndex.Put / Tombstone]
    w --> backend[(bbolt backend)]
    backend --> w
    idx --> w
    w --> hash[HashStorage]
    w --> notify[watchableStore.notify]
    notify --> watchers[active watchers]

A write transaction:

1. Acquires store.mu and store.revMu.
2. Bumps currentRev (main increments, sub increments per op within the txn).
3. Encodes each new value into bbolt under the bucket key <main>_<sub> and updates the in-memory index.
4. Computes a watcher delta and publishes events to watchableStore.

A read transaction snapshots the current revision and reads from bbolt at that snapshot. Range queries traverse the in-memory index in the requested key range and pull values from bbolt.

Compaction runs in the background:

1. The compactor (server/etcdserver/api/v3compactor/) calls store.Compact(rev).
2. The store walks the index, marks revisions <= rev as removable, and removes them in batches (defaultCompactionBatchLimit = 1000).
3. The work yields between batches via a FIFO scheduler from pkg/schedule to avoid blocking writes.

Watch fan-out

watchableStore keeps two groups:

• synced — caught up with currentRev; receive events via notify.
• unsynced — replaying older revisions; the syncWatchersLoop pumps them forward.

Watcher cancellation, fragmentation, and progress notifications are handled by watcher.go / watcher_group.go. The interval tree from pkg/adt/ makes range overlap checks O(log n).

Hashing

HashStorage keeps a rolling hash of the keyspace for cluster-wide corruption detection. The compactor and the membership system kick consistency checks via server/etcdserver/corrupt.go.

Integration points

• Backend: server/storage/backend/ (bbolt) for the actual persistence.
• Lease: each KV may attach a lease ID; deletion of a lease drives mvcc.DeleteRange for all keys.
• Apply: server/etcdserver/apply/ and server/etcdserver/txn/ drive every mutation.
• Watch RPC: server/etcdserver/api/v3rpc/watch.go translates mvcc.WatchStream into the gRPC Watch service.
• Compactor: server/etcdserver/api/v3compactor/ drives periodic + revision-based compaction.

Entry points for modification

• New range option (e.g. count-only behavior) → kvstore_txn.go::Range and kv.go::RangeOptions.
• New watcher capability → watcher.go, watchable_store.go, plus the gRPC handler.
• Tuning compaction → constants in kvstore.go (defaultCompactionBatchLimit, defaultCompactionSleepInterval).
• Hashing changes need careful coordination — see Documentation/postmortems/ for what happens when they go wrong.