LevelDB is an open source key-value store that originated from Google’s BigTable.
It is an implementation of LSM-tree, and it has received increased attention in both industry and academia.
Figure illustrates the architecture of LevelDB, which consists of two MemTables in main memory
and a set of SSTables in the disk and other auxiliary files,
such as the Manifest file which stores the metadata of SSTables.
LSM Log Structured Merge Tree
MemTable + ImmutableMemTable + SSTables + log(WAL) + metadata-files
When the user inserts a key-value pair into LevelDB, it will be first saved in a log file.
Then it is inserted into a sorted structure in memory, called MemTable,
which holds the most recent updates.
When the size of incoming data items reaches its full capacity,
the MemTable will be transformed into a read-only Immutable MemTable.
A new MemTable will be created to accumulate fresh updates.
MemTable 达到指定容量 ， 转成 只读 MemTable ，生成一个新的 MemTable
At the same time, a background thread begins to dump the Immutable MemTable into the disk
and generate a new Sorted String Table file (SSTable).
后台线程 dump 只读 MemTable 到硬盘 生成 SSTable
Deletes are a special case of update wherein a deletion marker is stored.
An SSTable stores a sequence of data items sorted by their keys.
The set of SSTables are organized into a series of levels, as shown in Figure .
The youngest level, Level 0,is produced by writing the Immutable MemTable from main memory to the disk.
SSTable 按key顺序存储 多个 SSTables 分层组织
最年轻的层 level0 , 由 只读 memtable dump 形成
Thus SSTables in Level 0 could contain overlapping keys.
However, in other levels the key range of SSTables are non-overlapping.
Level 0 的 SSTables 包含重复的 key 重叠 ， 一个key会出现在多个 sstable 中
其他层的 SSTables 不会重叠
Each level has a limit on the maximum number of SSTables, or equivalently,
on the total amount of data because each SSTable has a fixed size in a level.
The limit grows at an exponential rate with the level number.
For example, the maximum amount of data in Level1 will not exceed 10 MB,
and it will not exceed 100 MB for Level 2.
每层都有数量限制 或者 大小限制 ， 限制按指数增长
In order to keep the stored data in an optimized layout,a compaction process will be conducted.
The background compaction thread will monitor the SSTable files.
When the total size of Level L exceeds its limit,
the compaction thread will pick one SSTable from Level L and all overlapping ones from the next Level L+1.
These files are used as inputs to the compaction and are merged together to produce a series of new Level L+1 files.
When the output file has reached the predefined size (2 MB by default), another new SSTable is created.
All inputs will be discarded after the compaction.
后台压缩 ，大小超出 限制 ，启动压缩
挑选 重叠的 SSTable 进行压缩合并
Note that the compaction from Level 0 to Level1 is treated differently than those between other levels.
When the number of SSTables in Level 0 exceeds an upper limit(4 by default), the compaction is triggered.
The compactionmay involve more than one Level 0 file in case some of them overlap with each other.
Level 0 合并 特殊处理 ，SSTables 超过4个 触发合并
By conducting compaction, LevelDB eliminates overwritten values and drops deleted markers.
The compaction operation also ensures that the freshest data reside in the lowest level.
The stale data will gradually move to the higher levels.
压缩 删除 覆盖写的值 和 删除的值 ，保证 新鲜的数据留在 更低的level
The data retrieving, or read operation, is more complicated than the insertion.
When LevelDB receives a Get(Key,Value) request, it will first do a look up in the MemTable,
then in Immutable MemTable, and finally search the SSTables from Level 0 to higher levels in the order until a matched KV data item is found.
Once LevelDB finds the key in a certain level, it will stop its search.
MemTable > Immutable MemTable > level0 > level1 ... > levelN
As we mentioned before,lower levels contain fresher data items.
The new data will be searched earlier than old data.
Similar to compaction, more than one Level 0 file could be searched because of their data overlapping.
A Bloom filter is usually adopted to reduce the I/O cost for reading data blocks that do not contain requested KV items.
布隆过滤器 确认不存在的key 避免 查找不存在的 key