LSM - log-structured merge tree

  • 1 Sorted String Table (SSTable)
    • Get
    • Durability
    • Immutable Sorted file, Blocks + Index (k -> block offset)
  • 2
    • Put
    • Durability
    • Immutable Log: Put -> Log.Back
  • 3
    • MemTable - in memory - SkipList Put: Put_log + Put_memtable
Get --------------+
                  |
Put ---+          |
       |          V
RAM    | +----> MemTable   BlockCache
       | |        |        |
-------|-|--------|--------|--
       V |        V        |
DISK   Log      SSTable * * * (not many)
  • Delete -> tombstones
  • SSTable += Bloom Filter!

Writes

  • Append to Log
  • Dump MemTable
  • Merge SSTables

Impl

Snapshot

  • enumerate Put’s $\rightarrow$ sequence number
  • Get snapshot $\sim$ read sequence number
  • snapshot.Get(k) $\sim$ memtable.Get(k, s)