How MVCC and Transactions Work in RocksDB

Summary

How MVCC and Transactions Work in RocksDB RocksDB is built on an LSM-tree, which never modifies data in-place - every write creates a new version of the key. That's half of what you need to implement Multi-Version Concurrency Control (MVCC). Real-world databases serve many clients reading and writing the same data at the same time. The simplest way to make concurrent access safe is locking (think of a hash map protected with a mutex). This works from the correctness perspective, but makes readers and writers block each other, which can quickly become a performance bottleneck. MVCC solves this problem, allowing readers and writers to proceed concurrently. The idea is that: Writers never modify or delete keys in-place, instead they create new versions of the keys Readers see a consistent view of the data as it existed when the read started - they access older versions of the keys, while writers keep creating new versions independently MVCC is used in many DBs including PostgreSQL, CockroachDB, FoundationDB, MongoDB WiredTiger, and LMDB. Today we'll see how RocksDB implements the other half of MVCC - snapshots that give readers that consistent view, atomic updates and transactions built on top. Versioning Keys All inserts, updates and deletes go through a write buffer (memtable) and then get flushed to disk into an immutable SST (Static Sorted Table) file - you naturally have multiple versions of the same key. Compaction is the garbage collection process that merges SSTs and removes older versions of keys. Let's pretend our database is an insert-only list ordered by key. If we add these key-value pairs dog,a, chipmunk,a, cat,a, raccoon,a, we'll end up with a list that looks like this: It's a toy database, so point lookup queries run by scanning the entire list. Now a query starts, trying to look up dog. While the query is running, a writer proceeds more quickly and overwrites dog with b before the reader reaches it. The reader is still at chipmunk, but the writer alrea...