in LevelDB 分布式数据库 ~ read.

LevelDB组件-MemTable

LevelDB组件

MemTable

MemTable,内存表。每个 LevelDB 实例最多会维护两个 MemTable: mem_imm_。mem_ 可以读写,imm_ 只读。

最新写入的数据都会保存到 mem_ 中。当 mem_ 的大小超过 write_buffer_size 时,将其切换成 imm_,并生成新的 mem_。 后台线程会将 imm_ compact 成 SSTable 保存在磁盘上。

如果前台的写入速度很快,有可能出现 mem_ 的大小已经超过 write_buffer_size,但是前一个 imm_ 还没有被 compact 到磁盘上,无法切换 MemTable,此时就会出现 stall write(阻塞写请求)

leveldb::MemTable 基本接口:

数据格式

MemTable 中保存的数据是 key 和 value 编码成的一个字符串,由四个部分组成:

  1. klength: 变长的 32 位整数(varint 的编码),表示 internal key 的长度。
  2. internal key: 长度为 klength 的字符串。
  3. vlength: 变长的 32 位整数,表示 value 的长度。
  4. value: 长度为 vlength 的字符串。
  5. SequenceNumber:每个键值对的版本信息,更新一个key时,不会覆盖之前的值,而是创建一个新版本,便于snapshot
  6. ValueType:一个字节的enum,0-删除,1-插入/更新

MemTable 的 KeyComparator 负责从 memkey 中提取出 internalkey,最终排序逻辑是使用 InternalKeyComparator 进行比较,排序规则如下:

  1. 优先按照 user key 进行排序。
  2. User key 相同的按照 seq 降序排序。
  3. User key 和 seq 相同的按照 type 降序排序。

所以,在一个 MemTable 中,相同的 user key 的多个版本,新的排在前面,旧的排在后面。

Varint编码原理

摘自文章 http://atwoodwang.com/2020/leveldb_varint/

Varint 编码中,除了最后一个字节外,每个字节都设置了最高有效位(most significant bit - msb)。

msb 为 1 则表明后面的字节还是属于当前数据的,如果是 0 那么这是当前数据的最后一个字节数据。每个字节的低 7 位用于以 7 位为一组存储数字的二进制补码表示,最低有效组在前,或者叫最低有效字节在前,因为 varint 编码后数据的字节是按照小端序 (Little Endian) 排列的.

我们来通过解码一个 varint 的数据来熟悉 varint 编码的原理.

比如整数 1, 在 varint 编码后只需要一个字节,为:

0000 0001

第一位为 0, 表示这个字节已经是当前数据的最后一个字节了,后面 7 位二进制位 000 0001, 代表 1. 所以这个数为 1.

再举一个例子,300 在 varint 编码后需要 2 个字节,为:

1010 1100 0000 0010

先看第一个字节,最高位为 1, 代表后面一个字节也是当前数据的一部分。然后看第二个字节,最高位为 0, 代表这个字节是当前数据的最后一个字节。所以我们知道,这个数据一共占用了两个字节。然后把每个字节的最高位去掉,分别为 010 1100000 0010. 因为存储是用小端存储的,所以在解码时,最低有效组应该在前面,所以两个字节拼在一起是 000 0010 010 1100, 即 100101100. 这就是 300 的二进制表示.

LevelDB 中,所有的数字都是以字符数组的形式存储的。

内存分配

Arena

MemTable 通过 Arena 进行内存分配和使用统计。Arena 其实就是一个简化的内存池。它只提供分配内存的接口,不提供释放内存的接口。只有当整个 Arena 对象销毁的时候才会将之前申请的内存释放掉。 Arena 提供了两个内存分配接口:

![ArenaClass](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-memtable.md/309472414214139.png =612x)

  1. Allocate(size_t bytes)
  2. AllocateAligned(size_t bytes)

一般情况下,Allocate 每次从操作系统申请一块大小为 kBlockSize 的内存,默认是 4KB。之后,在 block 剩余内存足够的情况下,内存申请都可以直接从这个 block 划一部分出去(参考代码)。如果 block 剩余的内存不够,并且申请的内存大于 kBlockSize / 4,则直接 new 一块内存给这个请求(参考代码),避免造成太多的内部碎片。否则,就直接再申请一个 block,并从这个 block 划分一部分(参考代码)。

因为 SkipList 中会涉及一些原子操作,所以 AllocateAligned 分配的内存需要和指针的大小(一般是 8 字节)对齐。其他逻辑和 Allocate 一样。

跳表

SkipList 跳跃链表

跳表实现MemTable的按Key有序存储。

Skiplist 的效率可以和 AVL 树,红黑树媲美,平均 O (logN), 最坏 O (N) 的查询效率,但是用 Skiplist 实现比平衡树实现简单许多,所以很多程序用跳跃链表来代替平衡树。

特点

  1. 插入一个元素
  2. 删除一个元素
  3. 查找一个元素
  4. 有序输出所有元素
  5. 按照范围区间查找元素(比如查找值在 [100, 356] 之间的数据)

1-4 红黑树与跳表的时间复杂度基本一致,第5种场景,红黑树性能就不如跳表,用跳表可以在原始链表中直接遍历。

原理

  • 有序单链表:

![orgList](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-memtable.md/61674715233294.png =799x)

查找元素 10,从链表头开始,依次查找;

  • 增加一层索引:

假设每两个元素,增加一级索引

![oneList](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-memtable.md/20955015212946.png =799x)

查找元素 10, 从一级索引链表头开始,1 -> 4 -> 7 -> 9 -> 10;

  • 增加二层索引:

对一层索引,假设每两个元素,增加一级索引

![towList](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-memtable.md/574005315211392.png =799x)

查找元素 10, 从二级索引链表头开始,1 -> 7 -> 9 -> 10;

  • skiplist:

![skiplist](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-memtable.md/441490316241210.png =840x)

索引高度越高,空间复杂度越大,单级别索引粒度越大,查找性能越差,这两个阈值需要使用时协调,最终产生一个高度增长概率

B+Tree VS SkipList

LSM-Tree的 LevelDB/Redis 采用SkipList,Mysql采用B+Tree;

SkipList用于内存,保证内存有序,便于查询;

B+Tree用于磁盘,磁盘需尽可能减少查询,每次查询尽量多的获取数据至内存中,而B+Tree的每个节点存储了很多的数据,可以满足减少磁盘读写的需要。

LevelDB SkipList

LevelDB 的 SkipList 支持无锁的一写多读,并且只支持查找和插入。

  • Node

两个成员:

  • key

    SkipList的Node的key, 包含用户定义的key+value,即,开头提到的MemTable的数据格式

  • std::atomic<Node*> next_[1]

    即原始链表中,每个Node的层级的Node,初始1层,数组元素为1,依实际层数情况分配新Node内存。

  • SkipList

![skipListClass](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-memtable.md/334471917220144.png =603x)

参考连接:http://atwoodwang.com/2020/leveldb_skiplist/

MemTable

结合最前面MemTable的图,与SkipList,重新建立对应关系,如下图:

![MemTableStruct](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-memtable.md/332175517230368.png =852x)

源码参考:http://atwoodwang.com/2020/leveldb_memtable/