Storage Engines: B-Trees vs LSM Trees

Marlow Books is an online bookshop run by four people that exists only in this course. Just after four on the last Friday in June, the founder shipped the thing the two buyers had wanted since lesson 010 built the publisher page: a filter on that page for titles the shop actually has on a shelf.

They did it properly, too.

CREATE INDEX books_instock_idx
    ON books (publisher_id, published_at)
 WHERE stock > 0;

A partial index, the shape lesson 040 used for unsent outbox rows: index what you query and ignore the rest. Four and a half megabytes instead of the thirty five that lesson 010's full index costs, because only about a hundred and sixty thousand of the 1.2 million titles have any stock. The filtered page went from nine hundred milliseconds to four. By every standard the founder had been taught, including mine, that was a good Friday afternoon.

The 06:00 distributor import has printed its own duration at the end of its log since some bad morning years ago. For three years it said about twenty seconds. Saturday's said two minutes and fifty one seconds, and so did Sunday's, and on Monday the founder went looking.

The statement had always been in the slow query log, because an update across eight thousand rows was never going to finish inside lesson 010's two hundred millisecond threshold. Nothing in the plan had changed either: same rows, same lookups, same order. The change was further right, in the part of EXPLAIN (ANALYZE, BUFFERS) that lesson 010 taught them to read and nobody ever reads to the end of.

Buffers: shared hit=24196 read=108 dirtied=17480 written=16104

The Friday before, that line said dirtied=7012.

Eight thousand rows, each getting a new stock level that fits in four bytes. Thirty two kilobytes of actual news. A hundred and forty three megabytes of write ahead log.

Monday evening the founder added one line to the import, the last line here:

UPDATE books
   SET stock = v.stock
  FROM distributor_feed v
 WHERE books.isbn = v.isbn
   AND books.stock IS DISTINCT FROM v.stock;

Of the eight thousand rows in the daily feed, about nine hundred carry a stock level different from the one the shop already had. The other seven thousand one hundred were being rewritten every morning to the value they already held. Tuesday's import took eighteen seconds and dirtied three thousand seven hundred pages, which is less than the shop was paying before the index existed.

The index did not create that ratio. It only ended a discount Marlow had been getting for a year without knowing it, and the discount has a name.

The unit is a page, so nothing you write is small

Lesson 010 established the fact this whole lesson sits on: Postgres stores rows in 8 kilobyte pages and reads a whole page even when it wants one row. Marlow's books row is about two hundred bytes for the columns anybody queries, so forty rows to a page and thirty thousand pages for 1.2 million titles, 240 megabytes.

Inside the page there is a small header, a line pointer per row at the front, the rows themselves packed from the back, and free space in the middle. Two consequences fall out of that. A row cannot be larger than a page, which is why lesson 016's out of line storage, which Postgres calls TOAST, exists at all: a 180 kilobyte cover becomes about ninety chunk rows in a side table. And stock lives in the same 8 kilobytes as the title, the publisher and the price, which is why a four byte change is never a four byte write.

Writing works the same way, which is the half nobody thinks about. To change four bytes in the middle of a page the engine reads the 8 kilobyte page into memory, edits it there, and writes the whole page back. There is no instruction anywhere in the stack for "change these four bytes on disk". A file system will not do it, and nor will the SSD underneath: flash is programmed in pages of a few kilobytes and erased in blocks of a few megabytes, so the drive puts your page somewhere else and collects the garbage later. Your amplification rides on the drive's own.

So price Marlow's morning, as lesson 012 already did for the replica. Eight thousand rows scattered over thirty thousand pages, through lesson 010's dart model, which in letters is P times one minus e to the minus M over P: thirty thousand times one minus e to the minus eight thousand over thirty thousand, which is about seven thousand distinct pages.

Each of those pages gets written twice: once into the write ahead log, because Postgres will not change a page in its own file until the change is safely in the log, and once to the page's home in the table when a checkpoint gets round to it. The log is the expensive half. The first time a page is touched after a checkpoint, Postgres logs the entire 8 kilobyte image of it rather than a description of the edit, so that a crash mid-write cannot leave a half written page nobody can interpret. Nothing else touches the catalogue at six in the morning, so all seven thousand are first touches.

Seven thousand pages times 8 kilobytes is fifty seven megabytes of log for thirty two kilobytes of new stock levels. One thousand seven hundred and fifty to one, on a good morning, before the index.

The clock is the one link in this chain that is not a page count: two and a half times the pages took eight and a half times the time, and nothing above derives the difference. The dirtied counts are the evidence. The seconds are what made somebody look.

Write amplification is that ratio of log to news: bytes the engine writes divided by bytes you asked it to store. Its cousin read amplification is pages touched divided by pages you needed, which lesson 010 measured at twenty six thousand pages for sixty thousand wanted rows. Two structures make opposite bets about those two nouns, and both of them are probably running in your company tonight.

The B-tree, and the one number that decides what a write costs

An index is a sorted copy of some columns. A B-tree is how that sort gets kept while the table changes under it: a shallow tree of those same 8 kilobyte pages, where every page holds many keys in order, each interior key pointing at a page one level down.

The arithmetic is why it won. Lesson 010 priced an entry in Marlow's composite index at twenty eight bytes, key plus header plus pointer, so a leaf page holds about two hundred and ninety of them and a bit less in practice, because a B-tree deliberately leaves a tenth of each page empty so that an insert need not split it. Call it two hundred and sixty. The 1.2 million titles need four and a half thousand leaf pages. One level up, a page of boundary keys and pointers covers four hundred leaves, so twelve pages cover all of them, and one root page covers the twelve.

root       [ 11 boundary keys ]                        1 page
              |          |
interior   [ 400 keys ]  [ 400 keys ] ...             12 pages
              |
leaves     [ 260 entries in key order, each            4,500 pages
             pointing at one row ]

Three levels, which is the number lesson 010 published. Any key in the catalogue is three page reads away, two of which are the root and an interior page that every query in the shop has already pulled into memory. A point read is one random page, a hundred microseconds on lesson 002's ladder. Add a hundredfold more titles and you add one level.

Now write to it. An insert puts one twenty eight byte entry into exactly one leaf, which means reading that leaf, editing it, logging all 8 kilobytes of it and writing it back. If the leaf is full it splits: two half empty pages, a new entry in the parent, and once in a while that cascades to the root. Dirty one page, log eight kilobytes, and your entry was twenty eight bytes. That is a write amplification of two hundred and ninety if the page is flushed with only your entry on it.

It almost never is, and the reason is the only number that matters here.

A page that stays in memory absorbs every entry that lands in it before anybody writes it, and there are two ways to arrange that. Marlow's whole composite index is thirty five megabytes inside an 8 gigabyte buffer pool, so every leaf it owns is resident and no insert there ever waits for a page read. Which buys less than it sounds like. Eight thousand entries scattered over four and a half thousand leaves dirty most of them at about two entries a page, so this index's amplification on an import morning is a hundred and forty, not one. Keeping your insertions clustered in a few pages is the other way, and it is the only one that reaches one and the only one that survives the index outgrowing the memory. Get neither and you pay a page read and a page write per entry, which is amplification near two hundred and ninety.

What has to fit in memory is not the index, it is the set of pages you are writing into. Those are different quantities and only one of them is in your monitoring.

Galewatch, which collects a reading every two seconds from each of its wind turbines, is the case where that distinction is worth real money. Its hot table is keyed on (turbine_id, recorded_at), lesson 010's example of correct column order, and a year of readings per machine runs to tens of gigabytes of index on a box with thirty two. The index does not fit. The insertion points do: every turbine's readings arrive in time order, so each turbine appends to the end of its own key range, and a farm of sixty turbines has sixty leaf pages open at any moment. Half a megabyte of hot pages, each filling with two hundred and sixty entries at a reading every two seconds, so a given leaf is written about once every nine minutes.

Give the same table a random primary key, a UUID per reading, and every insert now lands on a cold leaf nobody is holding. Same rows, same rate, two orders of magnitude more I/O. This is the single most expensive table design mistake I know of that passes code review, because the schema looks tidier than the one that works.

Every update is an insert, which is why your database needs a cleaner

Back to the seventeen thousand pages, because I have only accounted for seven thousand of them.

Lesson 010 established that Postgres never modifies a row in place: an update writes a new version of the row and leaves the old one present but dead. Lesson 015's transactions and lesson 039's commit log are what make that work. Each version carries the id of the transaction that created it and, once superseded, of the one that replaced it, and a reader checks those ids against the commit log and its own snapshot to decide what it may see. That is multi version concurrency control, and a reader never waits for a writer because the version it is allowed to see is still sitting on the page. It is also the mechanism under lesson 015's cheapest fix: when buyer B's UPDATE ... WHERE stock > 0 waits for buyer A's lock and then re-checks its own condition, the row it re-checks against is the new version.

An index entry points at a physical row location, so a new version at a new location needs a new entry in every index on the table. Every index, not only the ones holding the column you changed, because what changed is where the row lives.

Which is the Friday afternoon, in one sentence. Postgres has an exception called a heap only tuple: if no indexed column changed and the page has room, the new version goes on the same page, chained to the old one, and no index is touched at all. Lesson 010 described it without giving it a name, and said what would end it. For a year, stock was in no index, so eight thousand updates a morning dirtied seven thousand heap pages and zero index pages. The new index is partial, and a column named in an index's WHERE clause counts as indexed for this purpose even though its values are not stored in the index. If your version disagrees about that case, a plain index on stock does the same thing beyond argument.

So the morning's eight thousand updates became eight thousand entries in each of four indexes: the primary key, lesson 010's composite, the published_at index lesson 010 built in a panic and which the planner has never used, and the new one, which takes an entry only for a row that still has stock to show. Through indexes of three and a half thousand, four and a half thousand, three thousand two hundred and five hundred pages, by the same dart arithmetic, they touch about ten thousand four hundred pages between them. Whatever the full text search over descriptions and reviews is built on is deliberately not in that total, because an inverted index's entry for one row is not one entry and lesson 045 owns why. If it lives on this table, every figure here is an underestimate.

Lesson 010 said indexing stock would cost eight thousand index updates a morning. The real figure is eight thousand times the number of indexes on the table, and the sharpest part of the bill went to an index nobody queries. A bill with no service attached, lesson 010 called it, costing twenty five megabytes of disk. It now also costs three thousand pages every morning, inside an index the planner will not open.

Then there is the cleaning. Lesson 011 did that arithmetic: autovacuum fires when dead rows pass fifty plus a fifth of the table, which for 1.2 million rows is 240,050, about a month of mornings. Vacuum reclaims them, and the part worth knowing is that it cannot finish inside the table. A dead version with index entries pointing at it has to stay, as a stub, until every index has been cleaned of it, so a real vacuum of books now reads four indexes end to end. A heap only update leaves nothing like that behind. The founder's index turned a job that tidied up after itself into one that books a monthly appointment with every index on the table, and lesson 011 already told us what that appointment does to a long report running on the replica.

MySQL's InnoDB takes the other road, updating the row in place and keeping old versions in a separate undo log, and pays for it with a purge thread and a history list that grows while any transaction stays open. Same bill, different handwriting.

The LSM tree, from the other end

Start from the opposite instinct. If a random write to a page is the expensive thing, do not do any.

A log structured merge tree buffers writes in a sorted structure in memory, called the memtable, and when it is full it writes the whole thing out as one sorted file and starts a new one. That file, a sorted run usually called an SSTable, is never modified again. Deletes and updates are new entries in a later run. Reads consult the memtable and then the runs.

Durability still costs what it costs. A memtable is memory, so an LSM still writes a write ahead log on the way in, exactly as Postgres does. What the LSM removes is the random page write, not the log.

Reads got harder. A key might be in the memtable, or in any run, and the engine does not know which, so a point lookup can touch many files. The fix is a bloom filter per run: a small bit array that can say "definitely not here" and "probably here", with no false negatives. Ten bits of filter per key buys about a one percent false positive rate, so a read checks the filters, skips almost every run without any I/O, and touches one. For one of Galewatch's machines holding a year, about a billion readings, that is 1.3 gigabytes of filter you want resident in memory and nobody budgeted for.

And the runs pile up, so they have to be merged. Compaction is a background job that reads several runs and writes one, dropping superseded versions and deleted keys as it goes. Give each level roughly ten times the capacity of the one above and a byte gets rewritten about ten times on its way through each level, since it is merged with the nine or so bytes already sitting in its key range. Four levels of that is a write amplification somewhere between thirty and fifty.

Which looks worse than a B-tree until you remember what a B-tree's number actually was.

A B-tree charges between one and two hundred and ninety, decided by your key order and your memory, and it will not tell you which you are paying. An LSM charges its thirty to fifty flat, whatever your keys look like. A B-tree charges by key order; an LSM charges a flat rate. For Galewatch's time ordered readings the B-tree is paying something near one, so an LSM would be about forty times worse on writes. For a table of randomly keyed rows that does not fit in memory, the B-tree is paying two hundred and ninety and the LSM is about seven times better. The LSM did not make writes fast. It made them predictable, which is a different and often more useful thing.

Two costs of the shape are easy to miss. A range scan gets no help from a bloom filter, because the question is not whether a key is present. Galewatch's panel asks for one turbine over one hour, eighteen hundred consecutive readings, which a B-tree answers by walking a leaf and its neighbours in under ten milliseconds and an LSM answers by opening every level and merging: lesson 010's read amplification, arriving by structure rather than by mistake.

And a delete is a write. The engine stores a marker, a tombstone, and the row underneath it stays on disk until a compaction covering both of them runs. Disk usage goes up when you delete, which is the sentence people do not believe until they watch it happen. The family has a third member for exactly this: space amplification, bytes on disk over bytes of live data. You get to be good at two of the three.

Then the bill arrives when you are busy. Compaction competes for the same disk as your writes, and if it falls behind, the lowest level fills with overlapping runs, every read starts touching all of them, and the engine throttles your writes and then refuses them: RocksDB's level0_slowdown_writes_trigger and level0_stop_writes_trigger, by name. Lesson 041's complaint was that every buffer has a bound and you chose it only if you typed it. A full LSM tree is a bound somebody else typed for you, the second one in this course after TCP's receive window. The catch is when it fires: your worst hour, because your worst hour is how it got behind.

What Galewatch should actually do

At 620 readings a second across the fleet, which is lesson 036's division of lesson 034's 1,240 turbines, no storage engine on earth is stressed. Spread over lesson 031's nineteen machines that is thirty three a second each, and the fattest shard, Kilmore Sands with its hundred and forty turbines, takes lesson 014's seventy. Postgres writes seventy rows a second with one hand. The write path is not where Galewatch's bytes hurt, and a lesson that tells you to swap engines for a rate like that is selling something.

Where it hurts is bytes at rest, and lesson 013 sized the entire shard count from them: a one hour recovery target times a measured 200 megabytes a second gives 720 gigabytes a shard, and 4,500 gigabytes over 720, doubled for growth and rounded to a number a human can operate, is why sixteen machines. Lesson 031 counted the fleet again after Ardnave Point needed a third shard: nineteen Postgres machines, 5.5 terabytes on disk.

Now the thing a B-tree cannot do. A page has to stay randomly updatable in place, so Postgres does not compress one. An LSM's run is written once and never touched again, so block compression is a default rather than an ambition, and for this shape it is enormous. Sort readings by turbine and time and consecutive recorded_at values differ by exactly two seconds: lesson 034 priced a timestamptz column at eight bytes and 428 megabytes a day across the fleet, and stored as a difference that one rounds to nothing. The measurements either side of it move by fractions of a percent between readings.

I am not going to invent your ratio. Two to four times is the range people measure on telemetry of this shape, the honest way to know yours is to compress a day of it, and that is one command and twenty minutes. Take three for the sake of the argument and watch where it lands. Lesson 014 derived a limit that appears in no runbook or contract at Galewatch: 720 gigabytes over five gigabytes a turbine-year is a maximum farm size of a hundred and forty four turbines. At three to one it is four hundred and thirty two. Ardnave Point's three hundred turbines, which lesson 031 priced at 1,500 gigabytes and had to spread over three machines, would have been five hundred gigabytes on one. The dotted power curve lesson 031 opens with, an engineer counting holes in one turbine's readings while hash(serial) % 2 became % 3 across four ingest boxes, happens because a number in the storage layer was three times larger than it had to be.

The engine chose how many machines you bought. Lesson 013 derived a shard count from bytes on a disk and never asked what was writing them, and nothing since has either.

Two caveats. Compression buys the restore only if that 200 megabytes a second was the machine rather than one shared pipe, which lesson 013 said out loud it did not know. June's drill answers it: Kilmore Sands came back in fifty eight minutes with 700 gigabytes while fifteen other shards restored alongside it, 201 megabytes a second on one machine with the rest of the fleet running, so the rate is per machine. And bytes were never the only reason for a machine count. Lesson 042 would ask what the blast radius becomes when one box carries three farms instead of one.

Stagefront, the ticketing service where a stadium show goes on sale at exactly ten in the morning, keeps forty thousand seat rows, which is a rounding error in any engine ever written; its problem was always the two hundred thousand people wanting the same one, and that belongs to lesson 015.

You have both already, by the way. Postgres, MySQL's InnoDB, SQLite and MongoDB's WiredTiger in its default configuration are B-trees; RocksDB, LevelDB, Cassandra, ScyllaDB and HBase are LSMs, so you are running one of those inside something and probably did not pick it. My favourite thing in the area is the hybrid nobody advertises: a Postgres GIN index, the kind full text search usually sits on, buffers its insertions in a pending list and merges them later, which is a memtable bolted onto a B-tree by people who hit the random write problem the LSM was invented for.

None of that is yours to choose this week. Everything in the hook is: how many indexes a table carries, whether your keys arrive in order, whether the pages you write into stay in memory, and whether you are writing rows that did not change.

Notice what the founder's one line did to the ratio. Nine hundred rows of real news is 3.6 kilobytes, and the morning still writes thirty megabytes, so the amplification went from four thousand three hundred to one up to about eight thousand to one while the bill fell by nearly four fifths. You cannot manage the ratio. You can only write less.

Recap

The unit is a page, so nothing you write is small. Changing four bytes means reading, editing and writing 8 kilobytes, and logging the whole page image the first time it is touched after a checkpoint. Marlow's thirty two kilobytes of new stock levels cost fifty seven megabytes of log, and a hundred and forty three after one index.

What has to fit in memory is not the index, it is the set of pages you are writing into. An insert into a resident leaf needs no read, and the same insert into a cold one costs a read and a write. What makes the write cheap is sharing the page: Galewatch's sixty turbine farm keeps sixty leaves open taking two hundred and sixty entries each, against tens of gigabytes of index, which is why its B-trees are comfortable at the fleet's six hundred and twenty readings a second.

Every update is an insert, so your database needs a cleaner. A new version needs a new entry in every index on the table, not only the ones holding the column you changed, unless nothing indexed changed and the page has room. That exception was saving Marlow eight thousand entries a morning in each of the three indexes the table already had, and a partial index's WHERE column both ended it and added a fourth.

Vacuum and compaction are the same bill with different handwriting. Both structures keep old versions and need background work to remove them: Postgres cannot free a dead row until every index has been cleaned of it, and an LSM drops superseded versions when it merges runs. Fall behind on either and your reads get slower while your disk gets fuller.

A B-tree charges by key order; an LSM charges a flat rate. One to two hundred and ninety, depending on your keys and your memory and reported nowhere, against a steady thirty to fifty whatever you do. The LSM's trade is predictability, paid for with a bloom filter on every point read and a merge on every range scan.

A full LSM tree is a bound somebody else typed for you. Compaction falling behind throttles and then stops your writes, which is lesson 041's backpressure arriving from inside the database, and arriving in the hour you can least afford it because that is the hour that got it behind.

And the one to carry out of today, which is a line in an import script rather than an architecture: do not write what did not change. Marlow's seven thousand one hundred identical rewrites a morning were pure cost, every morning, for three years.

Check your understanding

1. A colleague wants an index on a new status column so the admin screen can filter by it. The table already has four indexes and takes forty updates a second, almost all to one timestamp column. Say what that index costs per update beyond its own entry, and what you would ask to see before agreeing.

2. Galewatch's panel query over one turbine and one hour returns eighteen hundred rows. Say what that read costs on a B-tree and on an LSM with four levels, which number you would measure first, and why a bloom filter does not appear in either answer.

3. A service writes event rows keyed by a random UUID at four thousand a second, into a table whose index is twelve times the machine's memory. Say what happens per insert, give two fixes that do not involve changing database, and say which one you would refuse.

4. Your LSM store shows pending compactions climbing through the busiest three hours of the day and draining overnight. Writes are fine. Say what you expect to break first, which earlier lesson owns the signal, and whether you would add hardware or shed load.

5. Somebody proposes taking Galewatch from nineteen machines to six on today's compression argument. Give the two numbers you would check first, and name what gets worse even if both come out in your favour.

6. A nightly job updates one million rows of a ten million row table, and in about eighty percent of them the new value equals the old one. The table has three indexes, none containing that column. Say how much of the work one predicate removes, and what you would look at if the job is still slow.

Next lesson

044 Object Storage Internals: How S3-Style Systems Work. Today was about how one machine puts a row on a disk and finds it again; next lesson is about what happens when the disk is somebody else's, the unit is a whole object, and the only index you get is a key.