leveldb解析(1)

预写日志

leveldb一次将多个kv值合并为一个record, 写入block中,

一个预写日志文件大小为4MB, 一个block为32kb,

因为record可能比block还大, 需要跨block存储

MemTable

MemTable采用SkipList实现

Skip list 是一种可以用于替代查找树的内存数据结构，

其基本原理是在一个有序的链表之上增加一些索引，

通过一个随机规则（保证一定概率）来“模拟”二分查找。

直观上可以将整个 skip list 看成是一条地铁线。

每个节点就是一个地铁站，比如上图的 1~10。假设 (1) 是始发站，(NIL) 是终点站。这条地铁线有多种快车、慢车的线路，每个条线路经停的地铁站都不一样。比如上图就有四种不同线路（用向右的箭头表示），从上往下：

线路1：只停始发站(1) 和终点站(NIL)

线路2：始发站(1) => (4) => (6) => 终点站(NIL)

线路3：始发站(1) => (3) => (4) => (6) => (9) =>终点站(NIL)

线路4：每一站都停。

注意，skip list 这里的主要成本是经过的站点数量，而在某个站点进行转线的成本是零。我们可以合理转换不同线路来减少经过的站点数量。假如我们要去地铁站(9)，可以先坐线路 2 到地铁站(6)，再转线路 3 到地铁站(9)：经过的站点有 (1)、(4)、(6)、(9)。

定期将Immutable MemTable落入磁盘

SSTable 概览与Data Block

SSTable由DataBlock, MetaBlock, MetaIndexBlock, IndexBlock以及Footer组成

DataBlock按照顺序存储user key user value, MetaBlock 快速查找某个key是否在本sstable中 默认bloom filter, MetaIndexBlock是MetaBlock的索引,IndexBlock DataBlock的索引,Footer 指向MetaIndexBlock的开头和IndexBlock的开头

DataBlock中record中key采用前缀压缩方式, 为了提高查找效率 采用每隔16个key 不压缩, Restart代表了不压缩的节点的索引

SSTable-MetaBlock

MetaBlock,优化SSTable的读取性能

添加元素的方式为定义了 K 个不同的哈希函数，底层位数组的长度为 M,对于每一个被添加至 Bloom Filter 的元素，需要经过 K 次哈希函数的计算，得到 K 个哈希结果。每一个结果都需要被映射到 [0, M-1] 这一区间内，并将位数组对应的位置置为 1。

判断元素是否存在的方式为:对 E 进行 K 次哈希计算，并映射到 [0, M-1] 区间内，如果每一个位置的值都是 1 的话，就认为 E 在这个集合中

SSTable 索引

MetaIndexBlock只保存FilterPolicy以及BlockHandle信息

BlockHandle为每条MetaIndexBlock只需要记录MetaBlock的起始位置和大小

IndexBlock除了记录每个DataBlock的起始和长度 还记录每个block的最长key值,可以方便二分搜索

Footer中两个BlockHandle分别指向MetaIndexBlock和IndexBlock