Log-Structured Merge Trees

Author
Recent Posts

Ankit Verma

Geek is the best word, I can find to describe Ankit. Bringing more than a decade extensive experience of the industry, he never sits back and relaxes, always experiments with technology advancements, but at the same time, he is a good father, husband,son, brother and a fantastic friend. A bit introvert Ankit takes sometimes to open up.

When not doing programming software, he will be programming family outing.

Concept of LSM and SST Tables

Lets first see how the writes are handled in LSM and SST tables

WAL (Write ahead Log)

WAL is used for state management so that if any durability issue arises then the previous state can be obtained using WAL logs

Memtable :

This will contain an SSTable record of data. The only thing to remember in this is that SSTable records are immutable.

SST Tables

They will contain appended stream of record which are appended based on the timestamp. These streams of records are sorted based on the primary key.

Compaction

Compact the records based on timestamp and latest values

Now lets us see how read had been handled in LSM

Bloom filter :

Bloom filter is a concept that gives the predictive cache if read value exists in SSTables or not

Examples of Database that uses this kind of implementation are MongoDB and Cassandra

References