How databases write fast: LSM trees and Bloom filters

The interviewer says: "You must store 10,000 rider locations every second. Why would you pick a store built for heavy writing, and not a normal relational database?" A follow-up often comes: "That store keeps data in many files. How does a read find one key without opening them all?"

A weak answer is "it is faster for writes", with no reason. A strong answer says that a write goes to a log and to memory first. Data reaches the disk in sorted files that never change, and a small filter lets a read skip files. It also says what this costs.

At SDE-1 level, explain why adding to the end of a file is fast. At SDE-2 level, walk the write path and the read path. At SDE-3 level, also compare the ways to merge files and name the three kinds of extra work.

A shopkeeper has a stock book sorted by item name. To record a sale the clean way, she finds the right page, erases the old number and writes the new one. She walks to a different page for each sale.

A faster way: she writes each sale on a pad at the counter, one line after another. When the pad is full, she sorts its lines, copies them into a clean booklet, and puts it on a shelf. She never changes a booklet again. To find one item, she looks at the pad, then at the booklets from the newest to the oldest. At night she merges small booklets into one big sorted booklet, and drops old lines that a newer line has replaced. On each booklet cover, a small card lists items that are definitely not inside, so she skips most booklets.

Many write-heavy databases work like this. The design is called a log-structured merge tree (LSM tree).

Why a B-tree write costs more

In lesson 20, a B-tree keeps its entries in sorted pages. A write finds the right page and changes it in place. A page is 8 KB (in Postgres), even if the row is only 100 bytes. If keys arrive in random order, each write touches a different page. A disk is faster when it writes one long run, which is a long stretch of data in order. It is slower with many small pieces in many places.

The write path

1. Append to the commit log. As in lesson 21, the store writes the change to a log on disk, so a crash cannot lose it. Many stores wait for the disk before "done"; some let you choose. The log only adds to the end of a file, so it is one long run.
2. Insert into the memtable. The memtable is a table in memory that keeps its keys in sorted order.
3. Say "done". The write cost one append and one memory insert. It did not search any file.
4. Flush. When the memtable reaches its size limit, the store freezes it, and a new memtable takes the new writes. The frozen one is written to disk as an SSTable (sorted string table). This is a file of rows sorted by key, and it never changes after it is written. The matching part of the log can then be deleted.

If the server crashes, the memtable is lost. On restart, the store reads the log and builds the memtable again. The log holds only data that is not yet in an SSTable, so it stays short.

Updates and deletes

Files never change. An update is a new row with the same key. The old row stays in an older file, and the newest row wins. A delete writes a tombstone: a marker that says "this key is deleted". The store cannot erase old rows from old files.

The read path

1. Look in the memtable.
2. Look in the SSTables, from the newest to the oldest. Stop at the first row or tombstone for the key. Inside one file, the rows are sorted, so a small index of keys and file positions leads to the right place.

If the key does not exist, the read checks every file. Each flush adds a file, so reads get slower. Two tools fix this: Bloom filters and compaction.

Bloom filter

A Bloom filter is a small row of bits that answers "is this key in this file?" with "definitely not" or "maybe". Each bit is 0 or 1. The filter has m bits and k hash functions. A hash function turns a value into a number (lesson 43), and "number mod m" (the remainder, lesson 43) gives the place of one bit.

• Add a key: compute k places and set those k bits to 1.
• Check a key: compute the k places. If any bit is 0, the answer is definitely not. If all bits are 1, the answer is maybe.

Different keys can share bits, so "maybe" can be wrong for a key that was never added. That is a false positive. A filter never gives a false negative: a key that was added always finds its bits set. You cannot remove a key from a plain filter. That is fine here, because each SSTable gets its own filter when it is written, and the file never changes.

A tiny example with m = 16 and k = 2 (the places are made up). Add "pizza": places 3 and 9. Add "dosa": places 5 and 12. Check "cola": places 5 and 7. Bit 7 is 0, so cola is definitely not here. Check "idli": places 3 and 12. Both are 1, so the answer is "maybe", but idli was never added. That is a false positive.

With n keys, the false positive rate p is about this, where e is a fixed number, about 2.718:

p = (1 - e^(-k x n / m)) to the power k

Each SSTable has its own filter, and the filters sit in memory. A read checks the filter first and opens the file only on "maybe". A "definitely not" saves a disk read. A "maybe" costs a read that may find nothing.

Compaction

Compaction merges several SSTables into new sorted files. Because every file is sorted, it is one pass. It keeps the newest row of each key, drops old rows, drops tombstones when that is safe, and deletes the old files. Two common ways:

• Size-tiered. When several files have a similar size, merge them into one bigger file. Cassandra, a database with this design, starts a merge at 4 files by default. Data is rewritten less often. But one key can sit in many files, and a big merge needs extra space.
• Leveled. Files sit in levels, and each level is about 10 times bigger than the one above it (the RocksDB default). Inside a level, files do not overlap in key range, except in the newest level. So a read checks at most one file in each other level. Data is rewritten more often.

A tombstone is safe to drop only when the merge includes every older file that could hold the key. If the data also has copies on other servers (lesson 39), one copy may be offline and could bring the old row back. So Cassandra keeps tombstones for 10 days by default.

Three kinds of extra work

• Write amplification: bytes written to disk divided by bytes that the app wrote.
• Read amplification: how many files one read must check.
• Space amplification: disk used divided by the size of the live data.

Compaction lowers the second and third, but raises the first. You cannot make all three small. If compaction falls behind, files pile up and reads slow down, and some stores then slow down writes on purpose.

SwadKart stores rider locations (lesson 17). Assumptions (made up to teach with): 10,000 writes a second, each row 100 bytes. The memtable limit is 64 MB (64,000,000 bytes). Filters use 10 bits per key and 7 hash functions. A page is 8,192 bytes (lesson 20).

Step 1: a B-tree, worst case. Every row lands on a different page. 10,000 x 8,192 bytes = 81,920,000 bytes, about 82 MB a second of random page writes. The data is 10,000 x 100 = 1,000,000 bytes = 1 MB a second. So 8,192 / 100 = 81.92, about 82 times (rounded) more bytes than the data.

Step 2: the LSM write path. The log takes 1 MB a second, in one long run. The memtable holds 64,000,000 / 100 = 640,000 rows. It fills in 640,000 / 10,000 = 64 seconds. Each flush writes 64 MB in one long run, which is 1 MB a second more. One flush replaces up to 640,000 page writes. Each write waits only for a log append and a memory insert.

Step 3: files after one hour, with no compaction. 3,600 / 64 = 56.25, so 56 files of 64 MB. Check: 10,000 x 100 x 3,600 = 3,600,000,000 bytes = 3.6 GB, and 56 x 64 MB = 3,584 MB.

Step 4: Bloom filters. Each file holds 640,000 keys. 640,000 x 10 bits = 6,400,000 bits = 800,000 bytes = 800 KB. For 56 files: 56 x 800,000 = 44,800,000 bytes = 44.8 MB, which is 44.8 / 3,600 = 1.2% of the data. With 10 bits and 7 hashes, p = (1 - e^(-0.7)) to the power 7 = 0.5034 to the power 7 = 0.0082. We round up to 1% for easy arithmetic.

A key in no file: without filters, 56 files. With filters, 56 x 0.01 = 0.56 files (0.46 with the exact rate). That is 56 / 0.56 = 100 times fewer. This answers the predict box.

Step 5: one compaction. Three files, oldest first. File 1: a=1, b=2, c=3. File 2: b=20, d=4. File 3: c deleted (a tombstone), e=5. That is 3 + 2 + 2 = 7 entries. The merge reads all three in key order. For b, the newest value is 20. For c, the newest entry is the tombstone, and the merge includes every older file, so c and its tombstone both go. The new file is a=1, b=20, d=4, e=5: 4 entries.

Step 6: the cost of compaction. This is a simple model, not a measurement. Assume 64 GB of data, which is 64 GB / 64 MB = 1,000 flushed files.

• Size-tiered, merging 4 files at a time: 64 MB, 256 MB, 1 GB, 4 GB, 16 GB, 64 GB. That is 5 merges, because 4 to the power 5 = 1,024. Each byte is rewritten about 5 times: 5 MB a second for our 1 MB a second.
• Leveled, with levels of 640 MB, 6.4 GB and 64 GB: 3 levels. In each level a byte is merged with about 10 times its size, so about 10 x 3 = 30 rewrites: 30 MB a second.
• Add the log and the flush (2 MB a second). The totals are about 7 and 32 MB a second, mostly in long runs. The B-tree worst case was 82 MB a second in random places.
• Space: a last size-tiered merge of 4 files of 16 GB reads 64 GB and writes up to 64 GB. So it needs up to 128 GB at once.

• An LSM tree solves heavy writing: a log append and a memory insert, and long runs for the disk. It costs reads that check several places, background compaction (5 to 30 rewrites per byte in the model), and extra space during merges. I would change to a B-tree when reads are much more common than writes.
• A Bloom filter solves useless file reads: 56 became 0.56. It costs 10 bits of memory per key (44.8 MB here). It does not help a key that exists, or a range read. I would add bits when false positives cost too much.
• Size-tiered rewrites less. Leveled reads faster. I would choose leveled when reads matter most.

"An LSM tree is always faster than a B-tree." It is faster for writes. A read may check several files, and compaction uses the disk.

"A Bloom filter tells me that a key is in the file." It says "definitely not" or "maybe". Only "definitely not" is always right.

"Deleting a key frees its space at once." A delete adds a tombstone, which is more data. The old rows go only when compaction merges the files.

1. Name the steps of the write path in order. What can a Bloom filter answer, and which of its two answers is always correct?
2. A store gets 20,000 writes a second of 200 bytes each. The memtable limit is 128 MB (128,000,000 bytes). (a) How many rows fit in a memtable? (b) How often does a flush happen? (c) How many files exist after one hour with no compaction? (d) With 10 bits per key, how large is one filter?
3. A team deletes 1 TB of old rows to free disk space. Disk use does not fall, and some reads get slower. Why? What happens next?