Intro to LSM Tree

Introduction

Log-Structured Merge-Tree (LSM tree) is an append-only, key-value data structure that provides high write throughput. Write throughput is the amount of data that can be written to a storage system over a period of time. The LSM tree is used by various databases including Apache Cassandra, LevelDB, and RocksDB just to name a few.

On a high level, an LSM tree appends all incoming data then uses merge sort to handle deduplication and deletions. Underlying the LSM tree are a few in-memory and on-disk data structures which will be explained in the following sections. The post follows a write into SSTables and through compaction, then covers reads and deletes, and ends with research on persistent deletes at Boston University’s DiSC Lab.

Sorted String Table (SSTable)

SSTable is a disk-based data structure consisting of a sorted, immutable sequence of key-value pairs. The sortedness allows for efficient data retrieval using algorithms like binary search.

Initially, incoming writes are buffered in a sorted, in-memory data structure called a Memtable. Once the Memtable reaches a configurable threshold, it is flushed to disk to become a new SSTable. Transactions are also appended to a Commit log or Write Ahead Log (WAL) file to recover from a crash and ensure durability. As more SSTables are added and a certain threshold is reached, the SSTables are merged via compaction to form a larger SSTable. Note that updates to a given key will just append the new key value, while older entries are eventually removed during compaction.

Here’s how a handful of writes flow through this path, from the WAL and Memtable all the way to SSTables and compaction:

Compaction

Compaction can be thought of as garbage collection for the LSM tree. It removes keys that are duplicated and/or marked for deletion. Under the hood, it uses a multiway merge to combine several SSTables into one. Since each input is sorted, the merge compares the next unread key in each SSTable, writes out the smallest, and advances within the SSTable it came from. When the same key appears in multiple inputs, only the newest entry is kept.

In most implementations, a dedicated background thread is used to perform compaction. There are many ways to customize how and when compaction gets triggered with different tradeoffs. Below are two classic compaction strategies.

Leveled and Size-Tiered Compaction

To see where each strategy spends its merging effort, below is the same three flushes fed into a leveled tree and a tiered tree side by side:

Compaction Triggers

The two main compaction strategies discussed so far are leveled compaction, which is triggered when a level is saturated, and tiered compaction, which is triggered when the number of sorted runs reaches a threshold $T$. However, modern storage engines support additional compaction triggers. For instance, RocksDB’s Universal Compaction estimates the tree’s overall space amplification and triggers compaction when it exceeds a threshold. Alternatively, compaction could be invoked based on the age of a file, i.e., how long it has existed in a particular level. Age-based triggers already exist in production engines, and delete-aware variants based on tombstone age are an active area of research (more details in the last section). The table below summarizes the compaction triggers used by several production storage engines.

Partial Compaction

Leveled compaction can lead to cascading compactions, which results in high latency spikes, write stalls, and unpredictable system performance overall. Partial compaction aims to mitigate this by executing compaction with file-level granularity. The compaction condition/trigger remains unchanged, but the compaction routine selects a subset of files from the current and next level with overlapping key ranges to merge. By breaking down compaction into smaller units, the cost is amortized, leading to more predictable and consistent system performance.

A comparison of full and partial compaction (starting from the same full level) is shown below:

The table below shows the compaction granularity used by several production storage engines. Leveled engines typically compact at file granularity, while tiered engines merge whole sorted runs.

Data Movement Policy

Partial compaction requires choosing which data files to compact.

Here are several policies (non-exhaustive), each with its own strengths:

1. Round robin (LevelDB’s approach)
2. Least overlap with the next level (improve write amplification)
3. Coldest file (improve read throughput)
4. File with most tombstones (improve space amplification)

The table below shows which policies several production storage engines use. Engines that compact an entire level or sorted run at once have no file to choose.

Reading data

All reads in an LSM tree are first served from the Memtable. If the key is not found, it is then looked up in SSTables by level until the key is found. Otherwise, a null value is returned.

Since a key may live in any of several sorted runs, a read may need to probe multiple SSTables, leading to extraneous I/Os. Below are two main strategies to optimize read performance.

Bloom Filter

A Bloom filter is a probabilistic data structure that provides an efficient way to verify that an entry is certainly not in a set. Bloom filters are kept in memory and checked before accessing disk to reduce (expensive) disk reads. To check a key, the filter hashes it to several positions in a bit array. If any corresponding bit is 0, the key is definitely absent (how Bloom filters work). If all corresponding bits are 1, the key may be present, and only then will the SSTable be searched. Note that standard Bloom filters only help point queries, i.e., getting the value of a specific key, and cannot determine the presence of a key range. Variants exist for range queries: RocksDB’s prefix Bloom filters speed up scans over keys sharing a prefix, and SuRF checks whether a range may contain keys.

Sparse Index / Fence Pointers

As the size of deeper levels increases, even using binary search to find a key can become expensive, since each step of a binary search on disk costs an I/O. To put this into perspective, RocksDB reports that close to 90% of storage data resides in the last level (Dong et al., 2017). Fence pointers, which together form a sparse index, mitigate the potentially large read cost by keeping a subset of keys in each SSTable mapped in-memory. With this key mapping, ranges can be quickly skipped, narrowing the search to one block and cutting lookup time.

The sparse index, containing the key mapping, is typically encoded at the end of the file or as a separate index file. When an SSTable is read, its sparse index is loaded into memory and then used for key lookups during read operations. Since SSTables are immutable, compaction writes fresh sparse indexes for the new SSTables it produces.

Putting the two together, below are two lookups: one key that costs a single disk read, and one that the Bloom filters rule out without ever touching disk:

Block Cache

The block cache keeps recently read data blocks in memory and, optionally, metadata blocks such as Bloom filters and fence pointers. When the block cache is initially empty, it fetches the necessary pages from the on-disk files. It may also prefetch data pages to improve read performance. Reads consult the block cache first and perform disk I/O only if the requested block is not in the cache. Compaction deletes its input SSTables and makes their cached pages useless: reads may miss the cache until it warms up again. Separately, production systems like RocksDB keep a Manifest File, a log of which SSTables live at each level and their key ranges, as shown below.

Deletion

Deletes in LSM trees are realized by inserting a special type of key-value entry, known as a tombstone. Once inserted, a tombstone logically invalidates all entries in a tree that have a matching key, without necessarily disturbing the target entries on disk. The target entries are only guaranteed to be persistently deleted from the data store once the corresponding tombstone reaches the last level of the tree through compactions.

Here’s the journey of a single delete, from the Memtable down to the last level:

Research @ DiSC Lab

At Boston University’s Data-intensive Systems and Computing (DiSC) Lab, research is conducted on all aspects of log-structured systems to optimize performance. The main performance metrics and tradeoffs are listed below.

Read Amplification

Read amplification refers to the number of disk reads per query. As discussed earlier, read optimizations such as Bloom filters and fence pointers reduce read amplification by selectively processing read requests or reducing the search space.

Write Amplification

Write amplification refers to the ratio of the amount of physical data written to the storage device to the amount of logical data written to the database. Different compaction strategies result in different write amplification. In general, write amplification increases as the frequency of compactions increases.

Space Amplification

Space amplification refers to the ratio of the amount of physical data stored on the storage device to the amount of logical data in the database. Similar to write amplification, the compaction strategy has a large effect on space amplification. Size-tiered compaction generally results in higher space amplification compared to leveled compaction. In size-tiered compaction, when an SSTable in the deepest tier becomes very large, compaction requires substantial temporary space, since the input SSTables can only be deleted after the new, larger SSTable is fully written. Overwritten or deleted keys also persist in the SSTable until it is eventually merged, leading to wasted space.

Tradeoffs

There are often tradeoffs between different amplification metrics. For instance, introducing additional metadata to optimize read amplification can lead to increased space amplification. Compression techniques, employed by most storage solutions, help mitigate space amplification. Ultimately, the acceptable tradeoffs depend on the system’s use case. Write-heavy workloads might prioritize minimizing write amplification at the expense of higher read and space amplification. Conversely, read-intensive workloads may favor optimizing read amplification over the other metrics.

What I’m working on

At the DiSC Lab, I am working on extending MySQL to incorporate application support for a novel delete engine called Lethe for LSM trees. Lethe provides persistence guarantees for primary delete operations. The project write-up covers its motivation and progress in full; a short summary follows.

As discussed earlier, deletions in an LSM tree are “lazily” materialized, meaning the “deleted” key is physically removed from the system only during compactions. If a key lives on the last level of the LSM tree, its tombstone will also need to reach the last level for it to be physically removed, requiring compactions through every level. As the size of the tree grows, compaction might be delayed, and the process itself could be time-consuming. This becomes a real problem, as the duration between a deletion request from the client and the actual physical deletion of the key could extend to days or even months. Such a delay poses a considerable privacy risk for companies that have committed to removing personal data within a set period (e.g., 30 days). In cases where company data is compromised, the persistence of user data beyond the stipulated period could result in legal complications.

Lethe caps that wait with a delete persistence threshold (DPT): the longest a deleted key may stay on disk. The project’s SQL extension sets it per table or per statement, e.g. DELETE ... WITH DPT = D for a threshold of D seconds, like 30 days for the example above. To meet it, each level gives a tombstone a share of D,¹ and a file that overstays its share is compacted down right away.

The long-term outcome envisioned for this project is to advocate for integrating the new SQL syntax into ANSI standards, establishing persistent deletes as a foundational capability in SQL. This paradigm shift aims to compel Database Management Systems (DBMS) vendors to natively implement persistent delete functionality. We hope to empower not only database engineers but also SQL users with greater control over their data lifecycles. That increased agency will enable them to meet Service Level Agreements (SLAs) and address various business requirements more effectively, particularly those related to data privacy and protection.

In the current era, emphasis on data security and privacy is paramount. Stringent regulations such as the GDPR and CCPA exist to minimize personal data exposure by delineating strict guidelines for managing user data. Modern data systems must align with these legal frameworks, which are designed to safeguard online privacy rights. I look forward to the successful realization of this project in light of these considerations.

References

What is a SSTable? Definition & FAQs | ScyllaDB

An In-depth Discussion on the LSM Compaction Mechanism

B-Tree vs LSM-Tree

Lethe: Enabling Efficient Deletes in LSMs

SIGMOD 2022: Dissecting, Designing, and Optimizing LSM-based Data Stores (Tutorial)