How Databases Scale Writes: The Power of the Log

1. Introduction: The Database Write Bottleneck

When an application client sends information to a server, the server must write to a database to maintain state. At a low level, databases are specialized data structures designed to speed up queries. Traditionally, databases rely on a data structure called a B+ Tree (a variation of a binary search tree with multiple paths branching from each node).

The B+ Tree is widely preferred because it provides efficient insertion and search times, both operating at logarithmic complexity:

• Search Time: $O(\log n)$
• Insertion Time: $O(\log n)$

However, as write volumes skyrocket at modern web scale, traditional B+ Trees hit performance ceilings due to high I/O overhead and random disk access patterns.

Client
   |
   | sends SQL INSERT / UPDATE
   v
Server processes request
   |
   | writes to underlying B+ Tree
   v
Database requires synchronous disk I/O + returns individual ACK

2. Why Do We Need Write Optimization?

Every standard SQL command (such as an INSERT) maps to a structural modification in the underlying B+ Tree. Each of these operations traditionally requires:

1. Network Bandwidth & Headers: Sending separate packets for individual requests.
2. Synchronous Disk I/O: Modifying pages scattered across disk blocks.
3. Acknowledgment Overhead: Waiting for the database to confirm each transaction individually.

To scale database write throughput, we must minimize unnecessary data exchanges, reduce redundant round-trip acknowledgments, and cut down expensive random I/O calls.

3. The Core Mental Model: The Linked List vs. The Log

If you want the absolute fastest data structure for raw write operations, computer science points to a linked list.

Real-Life Analogy: The Append-Only Ledger

Think of a physical accounting logbook or a journal. When a new transaction occurs, you don't flip back to the middle of the book to insert it alphabetically; you simply open the page to the very end (the tail) and write the new entry on the next available line. This is an $O(1)$ constant-time append operation.

A Log embodies this linked-list philosophy. It is exceptionally fast for write operations because new data is appended sequentially.

4. The Trade-Off: Fast Writes vs. Slow Reads

While logs offer unmatched write performance, they introduce a severe drawback: read performance is catastrophically slow.

• Write Performance ($O(1)$): New records are simply appended to the tail of the log in memory and flushed sequentially to disk.
• Read Performance ($O(n)$): If you need to find a specific record, you cannot jump directly to an index; you must scan sequentially through the entire log from start to finish.

At massive web scale (e.g., Facebook-scale feeds), slow reads are completely unacceptable. If users must wait 30 seconds for a newsfeed query to scan a sequential log, the system fails. We need a design that gives us fast writes (like a log) without sacrificing read speeds.

5. Bridging the Gap: Sorted Arrays and Log-Structured Merge (LSM) Trees

To make read operations fast, data needs to be organized in a sorted structure (such as a sorted array or tree) which allows for binary search in $O(\log n)$ time.

However, maintaining a sorted array in memory during writes is prohibitively expensive because inserting into the middle of a sorted array requires shifting elements ($O(n)$).

The LSM Tree Solution

The breakthrough is a hybrid architecture known as the Log-Structured Merge Tree (LSM Tree):

1. In-Memory Buffer (Log/MemTable): Capture incoming writes rapidly in a sequential append-only log in memory.
2. Sequential Flushes: Once the memory buffer hits a threshold, flush the data down to disk in a sorted fashion.

6. Mechanics of the LSM Write and Flush Workflow

Let's examine how records flow from the server into persistent storage:

1. MemTable Append: New records (e.g., records 12, 17, 19, 23, 31, 47) arrive and are appended to the in-memory log.
2. Threshold Flush: When the memory buffer fills up, the database sorts the records and flushes them to disk as a immutable chunk.
3. Avoiding Immediate In-Place Sorting: If new incoming writes arrive, the database does not force an expensive in-place sort of the entire multi-gigabyte database file. Instead, it creates a new sorted chunk.

7. The Read Amplification Problem & Compaction

As more chunks accumulate on disk, read queries must check multiple files. If you have $N$ records divided into chunks of size $K$, a read operation might need to binary-search across multiple files, degrading read performance.

Background Compaction (Merge Sort)

To keep read times fast, the database runs a background process called Compaction. Compaction merges multiple smaller sorted chunks into larger sorted chunks using a standard Merge Sort algorithm.

Mathematical Comparison of Search Operations

• Unmerged Chunks (e.g., 3 chunks of size 6 = 18 records):
  • Binary search cost per chunk: $\log_2(6) \approx 3$ operations.
  • Worst-case search across 3 chunks: $3 \times 3 = 9$ operations.
• Merged Chunk (Single sorted array of size 12):
  • Binary search cost: $\log_2(12) \approx 3.5$ to $4$ operations.
  • Clear computational savings achieved by background compaction, trading background CPU/IO for faster read queries.

As data grows, the database maintains a tiered hierarchy of sorted blocks (e.g., blocks of size 6, 12, 24, and so on), continually merging them in the background.

8. Optimizing Reads with Bloom Filters

Even with compaction, searching across multiple disk chunks can result in unnecessary disk reads if a key does not exist in a particular chunk. To solve this, LSM storage engines employ Bloom Filters.

What is a Bloom Filter?

A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set.

• False Positives are Possible: A Bloom filter may tell you "Yes, the record probably exists in this chunk" when it actually does not.
• False Negatives are Impossible: If a Bloom filter says "The record does not exist in this chunk", it is 100% guaranteed not to be there.

By placing a Bloom filter in memory in front of every disk chunk, the database can instantly skip disk chunks that definitely do not contain the target key, drastically reducing unnecessary I/O during read queries.

9. Key Database Terminology Summary

10. Summary and Key Takeaways

• The Write Bottleneck: Traditional B+ Trees require random disk I/O and synchronous acknowledgments, slowing down high-throughput write workloads.
• The Power of the Log: Linked lists and logs provide optimal $O(1)$ write performance by appending data sequentially without random disk seeks.
• The Read Dilemma: Pure logs suffer from slow $O(n)$ sequential reads, making them impractical for production read-heavy applications like newsfeeds.
• The LSM Tree Solution: Combines the best of both worlds by pairing an in-memory append log with background-sorted disk files.
• SSTables on Disk: Flushed memory buffers are organized into Sorted String Tables (SSTables), allowing $O(\log n)$ binary searches.
• Background Compaction: The database continuously merges smaller sorted chunks into larger sorted arrays in the background to control read amplification.
• Probabilistic Acceleration: Bloom filters prevent wasted disk reads by instantly ruling out chunks that do not contain the requested key.