Memtable即内存表，作为数据写入磁盘前的缓冲区，这篇文章讲解其数据格式与实现原理

GoLevelDB —— Memtable

在本章节中我们讲解Memtable的设计与实现。

什么是 Memtable ?

Memtable是写入磁盘前的缓存表，在levelDB中一个DB实例会维护两个Memtable：

• mem：内存表，用于缓存写入的数据；
• imm：只读内存表；

最新写入的数据会被写入到mem中，当mem写满后，将mem置为imm，并开始将imm同步到磁盘。

基于上面的情况，我们的memtable只需要有以下三个接口：

• Insert：插入一条key-value数据；
• Get：通过key获取对应的value；
• Iterator：生成内存表迭代器，用于遍历内存表；

内存表中数据的删除操作，通过特殊的 Insert 操作完成，这个问题我们接下来会继续讨论。

Memtable 中的数据结构.

接下来讨论每条数据如何在内存表中存储的问题。

在上面，我们说了Memtable存储的是Key-Value数据，但实质上，Key与Value不会分开存储，而是会整合成一条Record进行存储，这个Record的整合方法如下：

其中：

• KeyLength：Key部分的字节数；
• KeyData：Key部分的数据；
• sequenceNumber：序列号（全局唯一）；
• valueType：记录类型，有typeDelete, typeData两种，为typeDelete时，这条记录无效；
• ValueLength：Value部分的字节数；
• ValueData：Value部分的数据；

Varint编码

在上面我们可以看到，KeyLength, ValueLenght是通过Varint进行编码的，这里我们简单讲一下什么是Varint以及用它有什么好处；

传统 int 编码存在的问题

首先，Varint的编码方式非常简单，我们以一个32 bits数字为例：

在日常场景中，32 bits能够表示的范围是0 ~ 4294967295，需要消耗4 bytes。

• 可以看出，传统的编码方式存在缺陷 ：我们大多数时候需要表示的数字只需要两个bytes就可以表示清楚，空间浪费很多！

varint 编码解决问题的方法

如果我们读数字的时候能一个byte一个byte的读，读到数字结束就不读了，那就能达到：

• 节约空间；
• 表示原本能够表示的范围；

这两个要求了！

Varint用每一个byte的最高位表示当前byte是否是这个数字的最后一byte，这样就可以达到上面说的效果了。

这种方法在小数字高频出现，大数字低频出现的场景中非常有效；在golang中，只需要使用：binarys.Varint方法就可以实现了；

sequenceNumber & valueType字段意义

• sequenceNumber不由Memtable维护，而是由上层模块传入，该数字全局唯一，随每次插入递增，相当于序列号；

• valueType是用于标记数据是否有效的byte；

到此为止，我们已经了解了Memtable中每条记录长什么样子了；

Memtable 底层数据结构

我们的Memtable需要进行Insert和Get操作，并且充当写磁盘的缓存，因此Memtable需要较高的性能。

目前Insert & Get操作比较快的数据结构有：

• 红黑树：读写稳定O(logN)。我自己的实现
• skiplist：在玄学加持下，读写理论O(logN)。

但是由于红黑树的插入操作需要进行非常复杂的分类讨论，现在的很多开源项目（redis, leveldb等）都选择使用skiplist作为KV存储的底层数据结构；

skiplist 基本原理

skiplist的特性

从图的最左侧看起，这个图展示了一个MaxLevel = 4的skiplist，它是由四层链表组成的。

skiplist的特性可以从两个角度来看：

• 在每一层内从左往右依次递增；
• 从下向上，每一层的元素个数依次递减；

skiplist的查找

我们来看一下在这样的结构下，应该如何查找一个特定的元素：

假设我们需要查询9：

• 我们从header开始，从高层向下层开始遍历；

• 首先我们从最高层开始，能够找到的第一个数字是7，这个数字小于9，所以我们当前节点移动到7；

• 由于L3的下一个节点是空节点，所以不再继续向前，而是查找L2的下一个节点；

• 由于L2的下一个是10，大于我们想要查找的目标，所以也不再继续向前；

• 经过多轮降低Level后，最终在L0找到9；

之所以这样的查找逻辑成立，是因为：对于同一位置的next节点，层数越高，next节点的值一定越大，在第一层找到最后一个节点后，降低Level的实质是对区间进行进一步缩小。

skiplist的插入

看懂了查找后，插入操作就非常简单了，插入只需要使得添加元素后的skiplist满足原有性质即可。

插入值为12的元素时，具体的操作方法如下：

• 随机一个插入元素的层数，在0~3之间；
• 找到需要插入元素的位置（在这里是在10之后，在15之前）；
• 对0~level之间的层数，分别执行链表的插入操作即可；

Memtable 中完成CRUD

通过上面的学习，我们知道Memtable通过封装skiplist以维护Key-Value数据对；在这一节中我们学习leveldb如何通过调整数据顺序完成内存表中数据的增删改查操作；

Memtable 面对的场景

• Memtable是写磁盘前的缓存；
• Memtable只有Insert操作，没有Update，Delete操作，但是有需要实现这样一套功能；

Memtable 解决问题的方法

从skiplist的排序入手

我们已经知道：

• Memtable通过skiplist进行数据存储
• skiplist中的一条数据是key/sequnceNumber/valueType/value组成的；

那么事实上我们可以从skiplist操作时的排序方法入手来解决上面的问题；

构建的排序方法

我们希望：

• 对于相同的Key，使用拥有最新（也就是最大）sequnceNumber的那条记录，这样就能够完使得每次取出的都是对于该key最后一次操作后的结果；
• 取出一条记录后，Memtable能够判断该数据是否被删除；

排序的方法：

• 先取出userkey进行排序；
• 对于userkey相同的，通过sequnceNumber排序；

附加的方法：

• 当valueType为typeDelete时，表示该数据已经被删除；

经过上面的规则，最终的skiplist中顺序排放的元素结构如下：

• 绿色的key1节点的seqNumber较大，通过key1查询时，只会查询到绿色的节点，而不会查询到灰色的节点，这就实现了修改的操作；
• 红色的节点的序列号也较大，同时他的type位被标记为Delete，所以在解析时会被认为已删除；

Iterator 迭代器

最后，我们来了解Memtable的迭代器，这个没啥好讲的，迭代器迭代的对象是skiplist，但是由于存储对象相同，感觉迭代的是Memtable；

iterator有以下操作：

• next：直接在L0访问下一节点实现；
• prev：由于skiplist不是双向链表，需要进行一次搜索，搜索比当前节点小的节点即可；
• seek：找到大于等于key的节点，通过skiplist实现；

还有一些其他操作，都不重要了；

代码: http://www.github.com/goleveldb/goleveldb