LSM- Write Heavy Databases:

Introduction:

Let’s think about what is the fasted way to write large datasets?. As we know the problem of disks being slow for random operations, but fast when accessed sequentially. If we append in a file or similar to how logging works. This idea of storing data into append-only logs is the basic idea behind LSM trees.

A log-structured merge-tree (LSM tree) is a data structure typically used when dealing with a write-heavy workload.

Log-Structured Merge is an important technique used in many modern data stores like BigTable, Cassandra, HBase, Riak, MongoDB 3.0(Wired Tiger).

What is an LSM Tree?

An LSM tree comprises of two or more levels of tree-like data structures. The simplest versions contain of two levels C0 and C1.

• first level is called the memtable and resides completely in-memory.
• Second level is called as SStables it's large in size and is stored in a disk.

First level or Memtable:

• The underlying data structure is some form of a sorted tree like a red-black tree.
• So whenever writes come in, the data is added to this tree.

• Once writes get stored in this red-black tree until the tree reaches a its threshold thenit is flushed to disk as a segment on disk in sorted order which is know SStable
• This allows us to write the segment file as a single sequential write even though the inserts may occur in any order.

Second level or SStable:

• Once Memtable start growing and reaches its threshold then these sorted keys are written into disk in same order known as SSTables or “String Sorted Tables” .
• SSTables are used to store key-value pairs in immutable log segments in the order sorted by string.
• Lookups can be very efficient even if full hash index is not present.
• Range queries are possible

How reading works?

As of now we have seen and focus only on write path, let’s see how reads works

• In case of reading, given key is first looked up in the memtable.
• In case of key is not present in Memtable, It uses sparse index (in memory index in elastic search it used to call it as inverted index).
• Key is sorted and key is binary search to fetch the segments depending upon the status of the compaction.

• In case of key is not present it still need to scan all segments.
• To speed up in case of key is not present it uses bloom filter. where it check if the key is not present no need to scan all segments.

Advantages of LSM tree

• LSM Trees can handle very high write throughput
• LSM Trees can be compressed better and thus result into smaller log segment files.

Disadvantages of LSM Tree

1. Compaction process sometime interfere with the performance of ongoing reads and writes.
2. Although use of bloom filter some how increase the performance in case of key not present, but if key exist then each key may exist at multiple places and thus checking if a key doesn’t exist needs all segments to be scanned.

That’s It

Happy learning

Images which are used are copied from google, used just for reference not personal benefit.