MemTable, WAL, SSTable, Log Structured Merge(LSM) Trees

submited by

Style Pass

2022-09-26 18:30:09

The MemTable (aka. Memory Table) is the in-memory cache of the latest set of record writes applied to the database before it’s flushed into SSTable or SST files. Simply, it is a container, whether that be a Vector, HashLinkList , RB Tree, SkipList, HashSkipList or any other container, that holds the written records sorted, in total order, by key. By sorting the records, lookups and scans in the MemTable can be done efficiently using a data structure that supports a O(Log N) access pattern.

It serves both read and write – new writes always insert data to memtable, and reads has to query memtable before reading from SST files, because data in memtable is newer. Once a memtable is full, it becomes immutable and replaced by a new memtable. A background thread will flush the content of the memtable into a SST file, after which the memtable can be destroyed.

Skiplist-based memtable provides general good performance to both read and write, random access and sequential scan. Besides, it provides some other useful features that other memtable implementations don’t currently support, like Concurrent Insert and Insert with Hint.