Database Internals — Episode 1

Alexey introduces himself: fifteen-odd years in development, about nine in architecture, the last five managing teams, and the book Alexander suggested, in his words, blew his mind. Part one is about storage engines, part two about distributed systems, and the first chapter sets the questions for the whole conversation: store in memory or on disk, orient by rows or by columns, how to split data across data files and index files. Row stores are the familiar relational databases: a whole row lies in one big file, and nothing comes out without indexes; column stores keep each column in its own file, which gives analytics fast aggregates and excellent compression. The author separately warns not to confuse them with wide-column stores, where a key and a timestamp span several different columns; Alexey admits he never fully understood the benefit. Alexander reminds that Petrov is one of Cassandra's maintainers, and part two will show it.

The book separates in-memory and disk-based engines: in memory you are spared many problems that appear as soon as data has to persist — hence the fork between combining data with the index and keeping them apart. Clustered versus non-clustered indexes is a classic interview question, and one of the hosts recalls answering on Stack Overflow about one database's clustered index when the question was about another. The participants recall a contractor who, relaunching a fat database, hung indexes everywhere: three months to untangle, and the fix had to work without downtime. Secondary indexes often point not at data but at the primary key — many engines create a hidden one by default if none is declared — so that deletes and updates do not break references. The three knobs the author uses to describe any engine: buffering, mutability, and ordering. The closer data lies together, the fewer spindle moves, and ordering matters on SSDs too; append-only structures never rewrite the old and simplify indexes; both the OS and the database keep buffers for hot pages. The book is fresh: in English it appeared around 2020, by the speaker's reckoning, and the translation in 2021 or 2022.

One of the hosts leads chapter two: the author starts with the binary search tree and its pathology — sorted input degrades the tree into a list with linear search; rotations rebalance it, but for disk a binary tree is still unfit: hopping between nodes is expensive, you want wide, shallow trees where a node is a whole page and most queries — ranges — are read locally. Alexey explains why: memory serves data by address, disk by blocks; the minimal unit read is a page, pages gather into blocks, blocks into flash cells; a write smaller than a page still takes a page, and a write of two and a half pages is padded with zeros, which affects SSD wear. A listener, Andrey, notes in the chat that ordering matters above all for sequential range reads, and Alexey agrees, adding that at petabyte scale the difference is seconds and minutes.

The host explains the B-tree through a library cabinet: shelf, drawer, card — every level narrows down, and the cards in a drawer are already sorted; separator keys on top, pointers to the next level or to data below. Search complexity is logarithmic, and the chat promptly corrects the base: not two but the fanout, which Alexander calls immaterial for the asymptotics. The participants liked the Winnie-the-Pooh epigraph to the chapter. The hard part begins with inserts and deletes: when a page overflows, a split happens that may climb to the root and rebuild the tree at the moment of insertion, and on deletion neighbouring pages whose element count falls below the threshold are merged with the parent's link moved. The participants note that the implementation mechanics are non-trivial and return to the first diagram: concurrent inserts are held together by the lock manager and the transaction manager.

Chapter three is about how all of it lies in bytes: big- and little-endian byte order, primitives (a float is a 23-bit fraction, an 8-bit exponent, and a sign), Pascal-style strings with the length in front versus strings stored as a plain array of characters, bit masks and flags. Records with fixed-size fields are simple, while variable fields give birth to slotted pages: pointers at the start of the page, cells from the end, free space between. Alexey shares an insight: he recently studied a Cisco binary protocol, and it is built exactly like slotted pages — the people who designed it clearly knew how data is stored on disk, and the book explained why the protocol is so elaborate. Then fragmentation, the free list, and the first-fit and best-fit strategies; cells lie in a page unordered, and order comes from the sorted pointers. In real systems the index and the data usually live in separate files and run into file-system limits instead; the chat brings up TOAST in PostgreSQL for large values.

Vova adds from the end of the chapter format versioning — Cassandra writes a version prefix into files — and checksums: disks do not always write honestly, and he recalls a story from an SRE book he has recently started reading, free on its site, where corrupted bits were recovered by flipping them one by one until the checksum matched. The fourth and hardest chapter gets six minutes: one of the participants found a repository where most of the chapter is implemented in Go and got as far as splits himself in one night — enough to see it is interesting, but the book alone is not enough for your own implementation. The techniques: sibling links for range traversal, the high key as a lid on a subtree, overflow pages for long values, breadcrumbs for the way back, background rebalancing, right-most append for monotonically growing keys, compression with an unpredictable remainder of space, and vacuum as the fight against entropy. The hosts sum up: four chapters in an hour is too fast, and the previous book, by their reckoning, took half a year to record; next come storage abstractions, B-tree variants, and transactions. Alexey thanks the club: without it he would not have reached this book.