Understanding LSM tree

LSM stands for Log Structured Merge trees, its is a type of data structure used by databases like cassandra , scylladb and rocks db to store and serve data. Its takes a very different approach from b-tree based relational DB’s like Postgres.

While btree offer a balanced read and write approach ,LSM trees are optimised for extremely fast ingestion, making it suitable for IOT and storing logs at scale.

Fun fact: MongoDB is a NoSQL db that uses btree (not pure btree but a version of it with its own modifications).

How are writes are fast in LSM trees?

Generated using chat gpt

To understand LSM based DB’s we need to understand the key components of these trees.

1. WAL
2. Memtable
3. SStable
4. Compaction

WAL

Also known as commit log , this is an append only file, it records all the write, update and delete operations happening on the db. To keep the operations extremely fast. WAL is sequential and append only where existing file is simply appended.

Memtable

Its an in-memory data-structure implemented using btree. When a new row is inserted , it is first written in the memory which is an extremely fast operation. Its size is limited but there is no single fixed size for a memtable, it’s configurable, and its size is chosen as a performance trade-off.

Typical size can be 64 to 128 MB. Once the memtable gets filled completely or a certain timeout happens ,the memtable is flushed on disk in a new SStable.

SSTable

An SSTable or Sorted String Table is an immutable on disk data structure used by LSM tree based storage engines to store key value pairs in sorted order Data is written to an SSTable when an in memory memtable is flushed and once created the file is never modified Updates and deletes are handled by writing new versions or tombstones which are later cleaned up during compaction Because SSTables are sorted they support efficient point lookups and range scans and because they are written sequentially they provide high write throughput and good disk efficiency making them a core building block of modern write optimized databases

Compaction

Credits — Scylla DB blog

Compaction is the background process in an LSM tree that merges multiple SSTables into fewer larger ones to maintain sorted order and reclaim space As new data is written older versions of keys and tombstones accumulate across SSTables and compaction rewrites the data so that only the most recent values remain This reduces read amplification controls disk usage and keeps the number of files manageable Compaction also moves data from higher levels to lower levels making data more stable over time and ensuring predictable performance as the system grows.

Putting it all together…

Write

The inserts happen in following order

1. Operations get written to memtable ,this is very fast since inmemory operation.
2. Parallelly the operations get appended to WAL for durability.
3. Periodically or when the memtable runs out of memory the buffer gets flushed into a level 0 SSTable
4. Then in the background the SSTables gets merged and deduped, this operation is similar to merging two halves of arrays in Merge sort algorithm and the process is called as compaction.
5. Eventually the SStables at level m are merged to tables at level m+1 and the level m tables are deleted.
6. Since the tables are immutable hence the key written on the table is never modified , for delete operation it makes another entry in the same table to mark the data as delete. This is also know as tombstone. Eventually after compaction this space is freed and the data gets deleted.

Read

Since the LSM tree based DB’s like cassandra are built for write prioritisation, they make certain tradedoffs when it comes to read operations.

1. The read operation searches in Memtable and sstables on each level.
2. Since there is overlapping key range and its split across different levels in the db, in order to be sure data needs to be looked everywhere.
3. Memtables lookups are fast because its btree and in memory.
4. SStables consist of three parts Index, bloom filters and data. The bloom filters are extremely fast data structures that can say for sure if a key is not present in the sstable. Hence the most of the SStables are skipped using it.
5. Once we know if the key is in the SStable, we use index file , it has the key and address of the data in the data file.
6. When using secondary index , Secondary indexes usually map secondary key → primary key, secondary index files give the address of primary key and the address of primary key is used to lookup the data in the data file. So now it make two hops.

Even with all the disadvantages, even after data being split across multiple tables, we are able to perform read operations in an acceptably fast pace.

Conclusion

Btree offers a balanced read and write performance, while LSM trees are designed for faster writes. Due to random inserts or even large sequential inserts btree faces page splits and parent node update or rewrite which causes write bottlenecks.

In LSM trees because of immutability there is a lot of duplicate data and hence in the shorter duration a lot of extra storage space being used by SStables. Even delete operation causes it to add more space. But this tradeoff offers a very fast storage with durability gurantee is very important for certain use cases like IOT and event logs.