To start, let’s assume that you want to continue storing data in the append-only file written by db_set, and you just want to speed up reads. One way you could do this is by keeping a hash map in memory, mapping every key to the byte offset where the most recent value for that key can be found, as illustrated in Figure 4-1.
Diagram showing how an in-memory hash map indexes keys to byte offsets in a log-structured file storing key-value pairs.
Figure 4-1. Storing a log of key-value pairs in a CSV-like format, indexed with an in-memory hash map
Whenever you append a new key-value pair to the file, you also update the hash map to reflect the offset of the data you just wrote. When you want to look up a value, you use the hash map to find the offset in the log file, seek to that location, and read the value. If that part of the data file is already in the filesystem cache, a read doesn’t require any disk I/O at all.
This approach is much faster, but it still suffers from several problems:
-
You never free up disk space occupied by old log entries that have been overwritten; if you keep writing to the database, you might run out of disk space.
-
The hash map is not persisted, so you have to rebuild it when you restart the database—for example, by scanning the whole log file to find the latest byte offset for each key. This makes restarts slow if you have a lot of data.
-
The hash table must fit in memory. In principle, you could maintain a hash table on disk, but unfortunately it is difficult to make an on-disk hash map perform well. It requires a lot of random access I/O, it’s expensive to grow when it becomes full, and hash collisions require fiddly logic.
-
Range queries are not efficient. For example, you can’t easily scan over all keys from 10000 to 19999—you have to look up each key individually in the hash map.
The SSTable file format
In practice, hash tables are not used very often for database indexes. Instead, it is much more common to keep data in a structure that is sorted by key. One example of such a structure is a Sorted Strings Table, or SSTable for short, as shown in Figure 4-2. This file format also stores key-value pairs, but it ensures that they are sorted by key, and each key appears only once in the file.
Diagram of an SSTable highlighting a sparse index, which maps specific keys to their byte offsets, enabling efficient block access to sorted key-value pairs.
Figure 4-2. An SSTable with a sparse index, allowing queries to jump to the right block
Now, you do not need to keep all the keys in memory. You can group the key-value pairs within an SSTable into blocks of a few kilobytes and then store the first key of each block in the index. This kind of index, which stores only some of the keys, is called sparse. This index is stored in a separate part of the SSTable—for example, using an immutable B-tree, a trie, or another data structure that allows queries to quickly look up a particular key.
In Figure 4-2, for instance, the first key of one block is handbag, and the first key of the next block is handsome. Now say you’re looking for the key handiwork, which doesn’t appear in the sparse index. Because of the sorting, you know that handiwork must appear between handbag and handsome. This means you can seek to the offset for handbag and scan the file from there until you find handiwork (or not, if the key is not present in the file). A block of a few kilobytes can be scanned very quickly.
Each block of records can also be compressed (indicated by the shaded area in Figure 4-2). Besides saving disk space, compression reduces the I/O bandwidth use, at the cost of using a bit more CPU time.
Constructing and merging SSTables
The SSTable file format is better for reading than an append-only log, but it makes writes more difficult. We can’t simply append at the end, because then the file would no longer be sorted (unless the keys happen to be written in ascending order). If we had to rewrite the whole SSTable every time a key was inserted somewhere in the middle, writes would become far too expensive.
We can solve this problem with a log-structured approach, which is a hybrid between an append-only log and a sorted file:
-
When a write comes in, add it to an in-memory ordered map data structure, such as a red–black tree, skip list, or trie. With these data structures, you can insert keys in any order, look them up efficiently, and read them back in sorted order. This in-memory data structure is called the memtable.
-
When the memtable gets bigger than a certain threshold—typically a few megabytes—write it out to disk in sorted order as an SSTable file. We call this new SSTable file the most recent segment of the database, and it is stored as a separate file alongside the older segments. Each segment has a separate index of its contents. While the new segment is being written out to disk, the database can continue writing to a new memtable instance, and the old memtable’s memory is freed when the writing of the SSTable is complete.
-
To read the value for a key, first try to find the key in the memtable and the most recent on-disk segment. If it’s not there, keep looking in the next-older segment until you either find the key or reach the oldest segment. If the key does not appear in any of the segments, it does not exist in the database.
-
From time to time, run a merging and compaction process in the background to combine segment files and to discard overwritten or deleted values.
Merging segments works similarly to the mergesort algorithm. The process is illustrated in Figure 4-3: start reading the input files side by side, look at the first key in each file, copy the lowest key (according to the sort order) to the output file, and repeat. If the same key appears in more than one input file, keep only the more recent value. This produces a new merged segment file, also sorted by key, with one value per key, and it uses minimal memory because we can iterate over the SSTables one key at a time.
To ensure that the data in the memtable is not lost if the database crashes, the storage engine keeps a separate log on disk to which every write is immediately appended. This log is not sorted by key, but that doesn’t matter, because its only purpose is to restore the memtable after a crash. Every time the memtable gets written out to an SSTable, the corresponding part of the log can be discarded.
Diagram illustrating the process of merging several SSTable segments, where keys are compared, the most recent values are retained, and the result is a new sorted segment.
Figure 4-3. Merging several SSTable segments, retaining only the most recent value for each key
If you want to delete a key and its associated value, you have to append a special deletion record called a tombstone to the data file. When log segments are merged, the tombstone tells the merging process to discard any previous values for the deleted key. Once the tombstone is merged into the oldest segment, it can be dropped.
The algorithm described here is essentially what is used in RocksDB, Cassandra, ScyllaDB, and HBase, all of which were inspired by Google’s Bigtable paper (which introduced the terms SSTable and memtable). The algorithm was originally published in 1996 under the name Log-Structured Merge-tree, or LSM-tree, building on earlier work on log-structured filesystems. For this reason, storage engines that are based on the principle of merging and compacting sorted files are often called LSM storage engines.
In LSM storage engines, a segment file is written in one pass (either by writing out the memtable or by merging some existing segments), and thereafter it is immutable. The merging and compaction of segments can be done in a background thread. While the merge is going on, we can still continue to serve reads by using the input segments of the merge (as before, reads first look in the memtable and more recent segment files). When the merging process is complete, we switch read requests to using the new merged segment instead of the input segments, and then the input segment files can be deleted.
The segment files don’t necessarily have to be stored on a local disk; they are also well suited for writing to object storage. SlateDB and Delta Lake take this approach, for example.
Having immutable segment files also simplifies crash recovery. If a crash happens while writing out the memtable or while merging segments, the database can just delete the unfinished SSTable and start afresh. The log that persists writes to the memtable could contain incomplete records if there was a crash halfway through writing a record, or if the disk was full; these issues are typically detected by including checksums in the log and discarding corrupted or incomplete log entries. We will talk more about durability and crash recovery in the related discussion.
Bloom filters
With LSM storage, it can be slow to read a key that was last updated a long time ago, or to attempt to read a key that does not exist, since the storage engine will need to check several segment files. To speed up such reads, LSM storage engines often include a Bloom filter in each segment, which provides a fast but approximate way of checking whether a particular key appears in a particular SSTable.
Figure 4-4 shows an example of a Bloom filter containing two keys and 16 bits (in reality, it would contain more keys and more bits). For every key in the SSTable, we compute a hash function, producing a set of numbers that are then interpreted as indexes into the array of bits. We set the bits corresponding to those indexes to 1 and leave the rest as 0. For example, the key handbag hashes to the numbers (2, 9, 4), so we set the second, ninth, and fourth bits to 1. The bitmap is then stored as part of the SSTable, along with the sparse index of keys. This takes a bit of extra space, but the Bloom filter is generally small compared to the rest of the SSTable.
When we want to know whether a key appears in the SSTable, we compute the same hash of that key as before and check the bits at those indexes. For example, in Figure 4-4, we’re querying the key handheld, which hashes to (6, 11, 2). One of those bits is 1 (namely, bit number 2), while the other two are 0. These checks can be made extremely quickly using the bitwise operations that all CPUs support.
Diagram illustrating a Bloom filter where keys "handbag" and "handoff" set specific bits, and querying "handheld" shows it is not present due to missing set bits.
Figure 4-4. A Bloom filter provides a fast, probabilistic check on whether a particular key exists in a particular SSTable.
If at least one of the bits is 0, we know that the key definitely does not appear in the SSTable. If the bits in the query are all 1s, the key is likely in the SSTable, but it’s also possible that by coincidence all those bits were set to 1 by other keys. This case, where it looks as if a key is present even though it isn’t, is called a false positive.
The probability of false positives depends on the number of keys, the number of bits set per key, and the total number of bits in the Bloom filter. You can use an online calculator tool to work out the right parameters for your application. As a rule of thumb, you need to allocate 10 bits of Bloom filter space for every key in the SSTable to get a false-positive probability of 1%, and the probability is reduced tenfold for every 5 additional bits you allocate per key.
In the context of LSM storage engines, false positives are no problem:
-
If the Bloom filter says that a key is not present, we can safely skip that SSTable, since we can be sure that it doesn’t contain the key.
-
If the Bloom filter says the key is present, we have to consult the sparse index and decode the block of key-value pairs to check whether the key really is there. If it was a false positive, we have done a bit of unnecessary work, but otherwise no harm is done—we just continue the search with the next-oldest segment.
Compaction strategies
An important detail is how the LSM storage chooses when to perform compaction and which SSTables to include in a compaction. Many LSM-based storage systems allow you to configure which compaction strategy to use. Some of the common choices are as follows:
Size-tiered compaction
Newer and smaller SSTables are successively merged into older and larger SSTables. For example, four 256 MB SSTables might be compacted into one 898 MB SSTable (the result is not 1,024 MB because of deletions, overwrites, time-to-live expirations, and so on). The SSTables containing older data can get very large, and merging them requires a lot of temporary disk space. The advantage of this strategy is that it can handle very high write throughput since most data is rewritten only a few times in larger sequential merges.
Leveled compaction
Instead of writing large SSTables, leveled compaction keeps SSTable sizes fixed and groups them into increasing “levels” (referred to as L0, L1, and so on). L0 contains the most recently written data. All levels beyond L0 contain key range–partitioned SSTables. For example, L1 might have two SSTables: the first with keys a–m and the second with n–z. Each level has its own size limit, and each level is larger than the level that precedes it (e.g., L2 will be larger than L1). When a level’s SSTables combine to exceed a maximum size limit, one or more SSTables from level i are merged into level i + 1 and deleted from level i. This approach allows compaction to proceed more incrementally and use less disk space than the size-tiered strategy. Leveled compaction is more efficient for reads than size-tiered compaction because the storage engine needs to read fewer SSTables to check whether they contain the key.
As a rule of thumb, size-tiered compaction performs better if you have mostly writes and few reads, whereas leveled compaction performs better if your workload is dominated by reads. If you write a small number of keys frequently and a large number of keys rarely, then leveled compaction can also be advantageous. Fortunately, most LSM-tree implementations provide a variety of compaction strategies for different workloads.
Even though there are many subtleties, the basic idea of LSM-trees—keeping a cascade of SSTables that are merged in the background—is simple and effective. We discuss their performance characteristics in more detail in “Comparing B-Trees and LSM-Trees”.
Embedded Storage Engines
Many databases run as a service that accepts queries over a network, but there are also embedded databases that don’t expose a network API. Instead, they are libraries that run in the same process as your application code, typically reading and writing files on the local disk, and you interact with them through normal function calls. Examples of embedded storage engines include RocksDB, SQLite, LMDB, DuckDB, and KùzuDB.
Embedded databases are very commonly used in mobile apps to store the local user’s data. On the backend, they can be an appropriate choice if the data is small enough to fit on a single machine and if there are not many concurrent transactions. For example, in a multitenant system in which each tenant is small enough and completely separate from others (i.e., you do not need to run queries that combine data from multiple tenants), you can potentially use a separate embedded database instance per tenant.
The storage and retrieval methods we discuss in this topic are used in both embedded and client/server databases. In the related discussion we will discuss techniques for scaling a database across multiple machines.