Key Value stores are extensively used in storage systems, both on-premise and cloud, to store metadata. Several key value stores such as RocksDB, BigTable, Cassandra are built on top of LSM trees. LSM trees are a widely used data structure for write-heavy workloads.

In this talk, I’d like to present a brief background on LSM trees, the advantages provided by LSM trees for performing faster writes and avoiding random I/O by only supporting sequential writes, and how we can build a key value store using LSM tree levels, that is memory and disk aware.

We will discuss the choice of data structures such as B-Trees, Trie, Skip lists and bloom filters for supporting lookups and reads, and implementation of put, get, get-next, iterate and delete operations in our Key value store, and delve into consistency, crash recovery and rollback of data stored in the key value store.