Database Internals — Episode 2

The conversation opens on ACID, "worn out but dear", and Grisha picks it up: atomicity — a transaction's operations are inseparable, consistency — invariants hold after every transaction, isolation — concurrent transactions do not affect each other, durability — data survives a crash. The participants liked the author's point that ACID is largely marketing and many databases do not provide honest ACID; one of the hosts recalls Kleppmann's joke about durability — if the data centre burns, the copy must be kept in space — and Grisha notes that the level of trouble we are willing to survive differs. Then the author lists the components without which there are no transactions: the transaction manager, the lock manager, the log manager, and the page cache — Alexander advises keeping the four in mind, and the chapter reads easily. Caches exist at every level, and some databases bypass the file-system cache with a special flag, which Linus Torvalds disliked, but there is no alternative. The buffer pool, Grisha stresses, is not a set of buffers but a queue of pages, and the main question is whom to evict.

Eviction strategies: FIFO, LRU, CLOCK with a reference bit going round, and two-queue schemes like TinyLFU with probation and protected zones, reminiscent of JVM generations; the book advertises the Caffeine library, which implements it. Alexander explains why plain LRU is bad for databases: the top pages of the tree enter the cache first and are always needed, so evicting them by age is wrong. Recovery is the ARIES algorithm of 1992, still in use: pages are flushed to disk with a delay while changes are recorded in the write-ahead log. Three phases after a crash: analysis finds dirty pages and in-flight transactions, redo replays history up to the crash, undo rolls back the unfinished transactions, returning the database not merely to the pre-crash state but to the consistent state promised by the letter C. Grisha clarifies where dirty pages come from — from the page queue, where all writes land while the log manager writes them to disk. Alexander likes that even a crash during recovery is handled: rolled-back transactions are remembered so they are not replayed.

The author divides concurrency control into optimistic — transactions run in parallel and check for conflicts before commit, losers roll back — multi-version with a timestamp per version, and pessimistic with locks. Grisha goes through the anomalies: dirty reads of uncommitted data, non-repeatable reads of one row, and phantoms — a colleague clarifies they show up on a repeated range query; isolation levels from read uncommitted, the fastest, to serializable, the most expensive, and Alexander reminds that the SQL standard fixed the anomalies that seemed important when it was adopted, while there are more — snapshot isolation on top of MVCC gives an anomaly of its own the speaker could not name. Grisha advises reading your database's documentation: repeatable read may be implemented through snapshots or through a stub. Under aggressive contention the optimistic approach turns into a race with one winner and a crowd of losers who retry; the pessimistic one is two-phase locking with a growing and a shrinking phase, shared and exclusive locks, and separately latches on the tree's physical pages.

Chapter six on B-tree variants is the toughest: Grisha admits his eyes ran over the words while his mind wandered; Alexander read the still-unfinished book chapter by chapter on the publisher's platform, stopped at chapter six for a year or so, and beat it only in the Russian version; Vova bought the Russian one and went back to the English because the terminology is more familiar. Vova gives the overview: a B-tree is optimised for reading, while writing means rewriting and splitting pages, hence the variants. Copy-on-write makes the tree immutable: a write copies a branch, switches the pointers, frees the old root — that tree, Vova says, is used by one protocol, and Grisha notes that copying for the sake of atomicity is a popular trick in general. The buffering variant keeps changes in memory and flushes them in batches, as one popular engine does; the Lazy-Adaptive Tree buffers per subtree; FD-trees are a flash variant where immutable sorted runs simplify merges; the remaining variants Vova leaves aside: explaining them would take logarithmic series.

LSM trees, Alexander says, resemble trees little: the two-component variant has one half in memory and one on disk, and the multi-component one the author knows from the inside, because Cassandra is built on it. The structure: a memtable in memory is sorted; when full it is frozen — readable but no longer writable — and flushed to disk as a sorted table; tables accumulate, reads go from the freshest to the oldest, and a separate compaction process merges the levels. Writing is easy and conflict-free, but you pay with read amplification — a key is looked up in several tables — write amplification — compaction rewrites data — and extra space, because one key lies in several tables. A delete is a tombstone: without it the deleted value would reincarnate from older tables during compaction.

A Bloom filter lets you skip tables where a key definitely is not: if the bits for the key's hashes are set, the key may be there, and the false-positive rate depends on the filter's size; a data structure for faster lookups, whose name the speaker could not recall, Alexander first met in this book; then block alignment, Bitcask, WiscKey with an index over a sorted log, SSD handling, and garbage collection — deeper than you need unless you write your own database. The author's closing table sorts the structures by the three knobs — buffering, mutability, ordering — and of these only B-trees and LSM are household names. One of the hosts compares with Kleppmann: he leads in steps from a hash index to SSTables and LSM, and after him you feel you understand databases; Petrov comes from the other side and leaves more questions — both books deserve rereading at different levels. Alexander admits part one was hard going in places — at twenty the engine algorithms would have landed better — while part two, on distributed systems, he read in one go. Next time — distributed systems, leader election, and replication with guests: Kostya Evteev from X5, who built DBaaS at Avito, and Oleg Bondar, who works on databases at Yandex.