Contenu source (brut)
<p>Every database eventually faces the same problem: applications insist on writing randomly while disks, even the fastest on the market, prefer sequential writes. </p><p>The log-structured merge tree (LSM) is one of the two great answers to this problem, and it is the answer that RocksDB chose.</p><p>The <a href="https://www.helius.dev/blog/what-is-rocksdb" rel="noopener noreferrer" target="_blank"><span style="text-decoration: underline">first article in this series</span></a> introduces the LSM tree, while this article gives it the full treatment: what the structure is, what actually happens to a write between the function call and the file on disk, and why the design wins on modern hardware. </p><h2>What is an LSM tree?</h2><p>A log-structured merge tree (LSM) is a data structure that buffers incoming writes in memory and merges them onto disk in sorted, immutable batches. It <em>never </em>modifies data in place. Instead, it accumulates changes and defers the work of organizing, trading read-side simplicity for write throughput.</p><p>The LSM tree was formalized in a 1996 paper by Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil titled <a href="https://link.springer.com/article/10.1007/s002360050048" rel="noopener noreferrer" target="_blank"><span style="text-decoration: underline"><em>The log-structured merge-tree (LSM-tree)</em></span></a>. It spent about a decade as a relatively obscure academic structure before Google’s BigTable built its storage layer on the concept. Bigtable’s design begat LevelDB, LevelDB begat RocksDB, and some flavor of LSM tree sits underneath most of the systems built for heavy ingest. </p><p>The name suggests a single tree, which is very misleading. </p><p>An LSM tree is better understood as a choreography of three components:</p><p></p><ul class="list-bullet"><li value=1>A <strong>memtable</strong>: an in-memory buffer holding the most recent writes</li><li value=2>A <strong>write-ahead log</strong><em><strong> </strong></em><strong>(WAL)</strong>: an append-only file on disk that makes those writes durable</li><li value=3>A growing collection of <strong>sorted string table files (SSTs)</strong>: immutable, sorted files that hold everything older</li></ul><p></p><p>Nearly everything interesting about LSM behavior follows from how data moves between these three components. All of that movement begins with a single, deceptively simple function call, typically referred to as a <em>put</em>.</p><h2>What is a put? </h2><p><a href="https://github.com/facebook/rocksdb/wiki/Basic-Operations#reads" rel="noopener noreferrer" target="_blank"><span style="text-decoration: underline"><strong>Put</strong></span></a><strong> </strong>is a convenience wrapper that, internally, constructs a <strong>WriteBatch </strong>containing exactly one record and hands it to <strong>Write()</strong>, which handles mutations. </p><p>The natural place to start is <strong>Put(key, value)</strong>, but, strictly speaking, RocksDB has no such operation. Every write is a batch, and a lone put is simply a batch of one. Atomic multi-key writes come for free in RocksDB because this is a native operation.</p><p>A <strong>WriteBatch</strong> is a compact byte string with a fixed shape. That is, a 12-byte header holding an 8-byte sequence number and a 4-byte record count, followed by the records themselves. Each record is a one-byte type tag, a length-prefixed key, and, for writes, a length-prefixed value.</p><p>The claim from the first article in this series—keys and values are arbitrary byte arrays—becomes literal. The batch encoding neither knows nor cares what the bytes mean. The only structure imposed is the length prefixes. </p><p>Every batch is stamped with a monotonically increasing counter known as a<strong> sequence number</strong>. It establishes a total order over every write the database has ever accepted. Sequence numbers are what make snapshots, consistent reads, and crash recovery possible. The WAL is replayable because every record in it knows its place in line.</p><h3>Put, Delete, Merge</h3><p>An important thing to note is that a <strong>Put </strong>is <strong>kTypeValue </strong>and a <strong>Delete </strong>is <strong>kTypeDeletion</strong>, which means a delete is not a removal. Instead, it is a write—a tombstone—that records the fact of deletion, with the actual reclamation deferred to compaction.</p><p><strong>Put </strong>and <strong>Delete </strong>share the <strong>WriteBatch </strong>format with <strong>kTypeMerge</strong>, written by the <strong>Merge </strong>operation. Merge exists because read-modify-write is poison for a write-optimized store. Incrementing a counter with <strong>Put</strong> requires reading the current value, adding one, and writing the result back. That accounts for two traversals of the database to change a single number, with the read paying the full cost of the read path. </p><p>Merge skips the read entirely. </p><p>Instead, it appends an operand (i.e., a description of the change, such as “add one”) and returns. Nothing is computed at write time. The database folds operands into a final value later using an application-provided merge operator, either when the key is next read or when compaction encounters the chain.</p><p>Deletes defer reclamation whereas merges defer computation. </p><p>The LSM tree’s entire personality is visible in these three type tags: every mutation, including the ones that logically depend on existing state, becomes a blind append. In an LSM tree, everything is an append. </p><h2>The LSM Tree Write Path Explained</h2><img src="/_next/image?url=/api/media/file/the-write-path-flow.png&w=3840&q=90" alt="The write path flow for an LSM tree" /><p>The clearest way to understand LSM trees is to follow a single <strong>Put(key, value) </strong>from a function call to disk.</p><h3>Step One: The Write-Ahead Log</h3><p>The write is first appended to the WAL. This append happens before touching the memtable, and this ordering forms the durability contract. That is, once the WAL append completes, the write exists on disk in a form that survives a crash, even though it has not yet been organized for reading.</p><p>Appending to a log is the cheapest possible disk operation, which is the entire point. Durability is bought at sequential-write prices.</p><p>RocksDB batches concurrent writes into group commits to amortize cost further, and the <strong>sync </strong>option controls whether it flushes the append through the OS page cache to stable storage before the call returns.</p><h3>Step Two: The Memtable</h3><p>With durability secured, the write is inserted into the memtable. By default, RocksDB’s memtable is a skiplist. It uses a skiplist because the memtable needs to absorb concurrent writes and hand back its contents in sorted key order, both for reads and for the later flush.</p><p>A skiplist supports lock-free concurrent inserts while keeping everything sorted at all times. It is the data-structure equivalent of filing paperwork as it arrives, rather than letting it pile up.</p><h3>Step Three: The Memtable Fills</h3><p>The memtable grows until it hits a configured threshold (i.e., <strong>write_buffer_size</strong>), which defaults to 64 MB. At this point, it is marked immutable, a fresh empty memtable is swapped in, and incoming writes continue without interruption. The full, frozen memtable waits its turn to be flushed in the background. </p><p>Writes never block on the flush itself.</p><h3>Step Four: The Flush</h3><p>A background thread writes the immutable memtable out to disk as an <strong>SST file</strong> in level 0 (L0) of the tree. Since the skiplist is already sorted, the flush is a single sequential pass that walks the entries in order and writes them out.</p><p>The memtable’s job is done, and the corresponding WAL entries can eventually be discarded. The data now survives on disk in its permanent, readable form.</p><h4>What is inside an SST file?</h4><p>Th
