LevelDB

Paper

摘要:
Google LevelDB 锁服务

LevelDB

1. Architecture

  • MemTable

    LevelDb 内存中的结构，写入先写入 MemTable ，其数据结构一般采用 skipList(O(log n) 时间复杂度) ，排序规则由用户自定义。

  • Immutable MemTable

    MemTable 达到阈值(4M, default) 会转化为不可变的 MemTable 快照 Immutable MemTable (只读) ，其数据结构和 MemTable 一模一样。

  • sstable

    每当一个不可变的 MemTable 快照被创建时，后台异步线程就会将其持久化到一个 sstable 中。

  • log

    WAL(write-ahead-log)，进程异常可以用来恢复数据。

  • manifest

    每次 leveldb 启动时，都会创建一个新的 manifest 文件，记录每次 合并 变化的内容(增/删了哪些sstable)。

  • current

    记录当前 manifest 文件名

2. Put

无论是 put 、 delete 还是batch操作，leveldb 底层都是以 batch 作为执行实例。

1
2
3
4
5
6
7
// Batch is a write batch.
type Batch struct {
	data  []byte
	index []batchIndex
	// internalLen is sums of key/value pair length plus 8-bytes internal key.
	internalLen int
}

leveldb的写入是类似线程组的模式，各个线程会将任务其放入队列中，拿到锁的线程会批量取任务然后合并后写入。

3. Read

读取流程比较简单，按照 Memtable –> Immutable –> sstable(level0~7)

对于文件的读取，每次读取会减少其 score，具体作用可以看 Major Compaction 的过程四。

4. Compaction

4.1 Minor Compaction

内存的持久化在 leveldb 称为 Minor Compaction ，每次 minor compaction 都会产出一个 level 0层的 sstable，多个文件中可能会存在数据 overlap。

因为 minor compaction 必须要在短时间完成(阻塞写入操作)，因此其优先级要比 Major Compaction 更高，在进行 minor compaction 时会暂停 Major Compaction

overlap，因为内存的 memtable 是按照阈值分割的，所以可能出现一个数据存在多个文件中

4.2 Major Compaction

随着 level 0层的 sstable 越来越多，导致查询越来越慢，leveldb 会将 level 0层的文件进行归并到 level 1层，这个操作称为 Major Compaction 。

当用户写入的速度始终大于 Major Compaction 时，会导致 level 0层的文件数量越来越多，读取性能持续拉胯，leveldb 为此设计了一种平衡策略:

  • 当 level 0层文件数量超过阈值1(8,default)时，减缓写入速度
  • 当 level 0层文件数量超过阈值2(12,default)时，写入暂停，直到 Major Compaction 完成

Major Compaction 触发条件：

  1. level 0层文件数量超过阈值
  2. level i层总大小超过阈值
  3. 某个文件读取次数过多

4.2.1 过程一、寻找原始输入文件

采用轮换的方法选择文件，第一批选完会记录其最大key，下一次从这个key后的文件开始，如下图中选中了黄色区域。

4.2.2 过程二、扩大输入文件

在当前层继续寻找与过程一原始输入文件有重叠的文件，如下图中选中了蓝色区域。

4.2.3 过程三、多路归并

将选中的文件集合，进行冗余清理、归并排序到原始输入文件的下一个level (如下图是归并到 level 1中的红色区域)。

4.2.4 过程四、计算积分

  • 计分规则1：
  1. level 0层，score = level 0层文件总数 / 4
  2. level i层，score = level i层文件总数据量 / level i层数据最大量

根据得分来选择合并的 level

  • 计分规则2：

为每个新的 sstable 文件维护初始分数为 100，每查一次该文件就减一，递减到0会被标记为待合并。