Modern Databases: Understanding Storage Levels in LSM Trees — Part 4

In one of our previous posts, we explored how LSM Trees use on-disk segment files known as SSTables to store data. However, we didn’t fully cover how these SSTables are arranged on the disk. Most databases built on LSM Trees use some variation of the below to manage SSTables.

LSM Tree

Brief

Now as per our previous post we have understood that LSMTrees dump the MemTable to disk as SSTables when the MemTable exceeds a threshold size.

LSMTrees arrange SSTables into different Levels. Levels help in reducing the number of SSTables that need to be searched for a given key.

The first layer is called as Level-0 and so on we have Level-1, Level-2 etc.

Levels and Compaction

• Level-0: SSTables are created from the in-memory MemTable and can have overlapping key ranges. When the number of SSTables in Level-0 exceeds a certain threshold, they are merged with SSTables in Level L+1.
• Higher Levels: Each SSTable in any level is in a sorted order and which is an intrinsic property of SSTables. When the number of SSTables in a level reaches a threshold, a compaction is triggered. This involves picking an SSTable from Level L and all the overlapping SSTables in Level L+1 and merging to create new SSTables in L+1. SSTables are never modified. New ones are created, making the merge/compaction process fast.

The tiered structure has the following benefits

• Multiple levels could reduce write amplification.
• Handle very large datasets efficiently, as data is progressively compacted and organised into manageable levels. For example only one file from level L is merged with few overlapping files from Level L+1 there by reducing the need to reorganise the other non overlapping ranges in L+1.
• The compaction process uses only bulk reads/writes and minimises expensive seeks.

The number of levels could be database specific. To better understand, let’s discuss how storage levels work in LevelDb, which uses LSM Trees as its underlying storage engine. You can find it here.

SSTable Levels in LevelDB

• A write is first appended to the WAL and then the MemTable is updated. When the WAL exceeds 4MB, the MemTable is dumped as an SSTable in Level-0. A new MemTable and WAL are created post this and the existing ones deleted.
• Level-0 is called as young level.
• When the number of young files exceeds a certain threshold (currently four), the young files are merged together with all of the overlapping Level-1 files to produce a sequence of new Level-1 files.
• As part of compaction files in lower levels are merged with any overlapping files in higher levels to create new files in higher levels.
• Files in Level-0 may have overlapping ranges. Files in higher levels starting from Level-1 have non overlapping ranges.
• The non-overlapping ranges of the SSTables in levels ≥1 are not fixed and are recomputed each time a compaction from Level L to Level L+1 occurs.
• Files in Level-0 are 1MB each and there are 4 files. Hence we have 4 files in total.
• Files in Level-1 and above are 2MB each.
• The total size of a level is (10^L) MB (i.e., 10MB for level-1, 100MB for level-2, …)

Level-0 Compaction

When the log file(WAL) grows above a certain size (4MB by default):

• Write the contents of the previous MemTable to an SSTable.
• Discard the MemTable.
• Delete the old log file and the old MemTable.
• Add the new SSTable to the young (Level-0) level.

Read Operations

• If the key is found in the MemTable, the operation is complete.
• If not, the search continues in the latest segment of Level-0 and so on.
• If the key is not found in Level-0, the search moves to Level-1. Since Level-1 segments are non-overlapping, the search is faster.
• Sparse indexes are used to find the SSTables which bloom filters are used for avoiding expensive disk reads to check if a key is present in an SSTable. This is not a sure shot way and just helps in avoiding expensive IO’s.
• Even if a bloom filter check indicates presence of a key in an SSTable its just a probability and it still might not be present. That is how bloom filters work.

On the number of files in each level, you can read a bit here. The discussion here aims to find alternatives to improve the merging process by creating larger files or sharding files into multiple directories instead of many small files in a single directory assuming the cost of opening many small files in a directory affects performance.

• File System Performance: Some file systems degrade in performance when a single directory contains a large number of files. Sharding distributes the load, potentially avoiding this issue.
• Manageability: It can be easier to manage smaller groups of files spread across directories rather than a single, massive directory.

But as per the tests quoted, the performance that could be achieved with sharding is not that high on modern file systems.