解密存储引擎 bitcask 的设计原理

Riak 是一个专注于分布式存储的公司，他们想打造一个新的存储引擎，该引擎要能实现以下几个目标：

• 读写数据时，延迟要低；

• 高吞吐量；

• 能够在不降低性能的前提下，处理超过内存容量的数据集；

• 具备从崩溃中快速恢复的能力，并且不丢数据；

• 简单的备份和恢复策略；

• 代码结构和数据格式相对简单且易于理解；

• 即使面临大数据集，性能依旧不受影响；

• 拥有简单的授权机制，能够和 Riak 的其它系统轻松集成；

  
  

当时 Riak 团队只能找到满足部分条件的存储引擎，而这不是 Riak 团队想要的，于是他们从头设计了一个存储引擎，也就是 Bitcask。

Bitcask 在概念上非常简单，一个 Bitcask 实例就是一个目录，并且规定同一时刻只能有一个进程操作该目录，因此你可以把操作该目录的进程看作是数据库服务器。

然后不管目录中有多少文件，同一时刻只会有一个活跃文件用于服务器写入。当该文件的大小达到指定的阈值，它会被关闭，然后创建一个新的活跃文件。注意：不管是文件写满了还是服务器（进程）退出了，一旦文件被关闭，它就成为了旧的数据文件（不活跃）。而旧的数据文件是不可变的，不会再执行写操作。

所以 Bitcask 实例目录就是一个活跃文件和多个旧的数据文件的集合。

服务器进程在写入活动文件时采用了追加模式（Append Only），从而避免了多余的磁盘寻址。因为写操作没有太多的优化技巧，必须等数据落盘了才算写入成功，所以顺序写是最常见、且最有效的优化手段。虽然机械盘的随机写性能很差，但顺序写的效果还是不错的，Kafka 已经证明了这一点，当然除了顺序写 Kafka 还用了很多其它优化手段。

那么进程在追加写的时候，写入到文件的数据格式是怎样的呢？

总共有如下字段：

• crc：基于其它字段生成的校验和，用于验证数据的完整性和准确性；

• tstamp：由 32 位整数表示的时间戳，内部使用，不对外暴露；

• ksz：key size，记录了 key 的大小；

• value_sz：value size，记录了 value 的大小；

• key：实际存储的 key；

• value：实际存储的 value；

  
  

服务器每次写入，都是向活跃文件追加这样一条记录。另外删除也是一次追加写入，只不过写入的是一个特殊的墓碑值（tombstone），用于标记一条记录的删除，所以 Bitcask 在删除数据时属于逻辑删除。当下一次 merge 的时候，再执行物理删除。

凡是采用追加写模式的存储引擎，基本都是这个设计，比如 HBase。如果每次删除都直接采用物理删除的话，那么速度不可能快。

因此 Bitcask 数据文件里面存储的就是这些记录的线性序列。

key 和 value 有大有小，但前 4 个字段的大小是固定的，而 ksz 和 value_sz 记录了 key 和 value 的大小。

以上这些记录要追加写入到磁盘，但内存中同样要维护一个数据结构，在 Bitcask 里面叫 keydir。那么 keydir 里面存的都是什么呢？

看到这种结构，我们首先想到 keydir 很可能是使用哈希表。没错，官方也推荐采用哈希表实现，但你选择红黑树、跳表也是可以的，如果你需要有序遍历的话。

解释一下这些字段的含义：

• key：写入的 key；

• file_id：因为数据文件可以有很多，所以要通过 file_id 来标识键值对在哪一个文件中；

• value_sz：value 的大小；

• value_pos：偏移量，注意这个偏移量不是 value 的偏移量，而是 value 所在的整条记录的起始位置的偏移量；

• tstamp：32 位整数表示的时间戳；

当服务器向文件追加一条记录时，在内存中就会向 keydir 新增一个键值对。那么问题来了，如果 key 已经存在了怎么办？

很简单，key 存在相当于修改，但对于数据文件而言，更新和删除一样，依旧是追加一条新的记录。数据文件在磁盘上，不会直接修改，更新和删除本质上都是写入。只不过删除时，会写入一个特殊的墓碑值，而更新则是写入一条新的普通记录，但记录中的 key 已存在。

记录更新之后，还要维护内存中的 keydir。由于 key 已存在，此时相当于对 keydir 进行更新，会保存新数据的位置信息。

尽管旧数据和新数据都存在于磁盘上，但 keydir 里面只会保存新数据的位置信息，因此任何读取都会使用最新的可用版本，而旧数据则会在 merge 的时候被清理。

那么整个读取过程怎样的呢？示意图如下：

当基于 key 获取 value 时，会先基于 key 在 keydir 中查找记录的位置信息。通过 file_id 可以定位到数据文件，通过 value_pos 可以定位到记录在数据文件中的偏移量。由于记录的前 4 个字段的大小是固定的，key 的大小可以计算出来，所以 value 的偏移量也能确定，再通过 value_sz 即可将具体的 value 读出来。

基于 key 获取 value 偏移量是 O(1) 的复杂度，而知道偏移量和大小之后读取 value 的复杂度也是常量级别，并且只需要一次 IO。

这里你也许好奇，为啥记录中已经保存了 value_sz，在 keydir 中还要再保存一次？

答案是为了减少磁盘 IO，如果 keydir 中不保存的话，那么读 value 之前要先把大小读出来，这样会有一次额外的磁盘 IO。由于记录的前 4 个字段大小固定，key 是已知的，长度也可以计算，那么 value 的偏移量就是已知的。如果 value 的大小再已知的话，那么只用一次 IO 就能把 value 读出来，所以 keydir 中也需要保存一份 value_sz。

所以整个过程还是很好理解的，但我们说了，更新数据和写入数据是一样的，都是往磁盘追加一条记录。虽然内存中 keydir 只会保存新数据的元信息，但磁盘上的数据文件会将旧数据和新数据都保存起来。当然删除也是同理，旧数据不删除，追加一条新记录（特殊的墓碑值）。

因此随着时间的推移，Bitcask 占用的空间一定会越来越大，因为旧数据不会被删除。所以 Bitcask 会定期执行 merge 操作，将无用数据给清理掉。

至于 merge 的过程也很简单，就是遍历所有的旧数据文件（注意是不可变的旧数据文件，活跃文件不会遍历），然后将所有有效（没有被删除）的键的最新版本写入到新的文件中，最后再将旧数据文件删除。

虽然 merge 会创建一组新的文件，但这些文件依旧是旧数据文件，不会被写入。此外 merge 是在后台进行的，不会干扰正常的读写操作。

经过 merge 之后，新创建的数据文件里面保存的都是有效的最新记录，这里的 merge data file 还表示旧的数据文件，只不过是 merge 之后的。然后我们看到 merge 之后，它还会为每个数据文件生成一个 hint 文件，hint 文件里面保存的是记录的一些元信息，比如在数据文件中的位置、value 的大小。

Bitcask 进程重新启动时要在内存中构建 keydir，如果是基于数据文件构建的话会很慢，而通过 hint 文件就可以快速构建了。因为 hint 文件里面不保存实际数据，它的容量会远比数据文件要小。

所以到这里我们可以看出，Bitcask 是纯内存索引，在查找 value 时必须经过内存中的 keydir。因此有人发现了，这不就是将 key 放在内存中，将 value 放在了磁盘中吗？

是的，Bitcask 将 key 和 value 分开存储了：

• 在内存中对 key 创建索引；

• 磁盘文件存储 value 数据；

  
  

keydir 保存 key 和 value 在磁盘上的位置信息，查找时要先通过 key 拿到位置信息，然后再基于位置信息拿到 value。所以这种设计就使得 Bitcask 必须满足以下几点，才能发挥出威力。

• value 的大小一定要比 key 大很多，否则还不如直接用哈希表。另外 value 也不能太大，因为写入是串行的；

• 所有记录的 key 要能全部载入内存；

• 连续写入，随机读取；

到目前为止我们就说完了 Bitcask 到底是什么，它是怎么设计的，然后再来回顾一下 Riak 团队给 Bitcask 设定的目标是否全部实现了。

1）读写低延迟

显然是满足的，因为读写只有一次磁盘 IO。

2）高吞吐量

也是满足的，因为写入数据是顺序写。

3）处理大于 RAM 的数据集且不影响性能

没问题，因为 value 都在磁盘上。但要保证 value 的大小要远超过 key，否则用 Bitcask 没有多大意义。

4）从崩溃中快速恢复

很多存储在写数据之前会先写日志，但在 Bitcask 中写日志和写数据是一码事，所以恢复非常简单，无需进行重放。

5）简单的备份和恢复

备份和恢复非常简单，只需将整个目录拷贝一份即可，因为文件是不可变的，并且都在同一目录下。

6）代码结构和数据格式易于理解

代码结构取决于具体实现，但数据格式确实很好理解。

7）在大数据集下表现良好

根据官方测试，在处理几十 GB 的数据时表现很好，但即便数据量增大，表现也不会有明显变化，只要 keydir 能够完全适应 RAM。当然这个限制也是微不足道的，因为即使有数百万个 key，也用不了 1G 的内存。

当然还是那句话，Bitcask 的适用场景是 value 的大小要远高于 key。

最后是 Bitcask 的一些 API：

bitcask.open(dir_name, mode) - 以指定模式打开一个新的或现有的 Bitcask 存储。

bitcask.open(dir_name) - 以只读模式打开一个新的或现有的 Bitcask 存储。

bitcask.get(key) - 从 Bitcask 数据存储中按 key 检索 value。

bitcask.put(key, value) - 向 Bitcask 数据存储中添加键值对。

bitcask.delete(key) - 从 Bitcask 数据存储中删除一个键值对。

bitcask.list_keys() - 列出 Bitcask 数据存储中的所有键。

bitcask.fold(func) - 遍历 Bitcask 数据存储中的所有键值对。

bitcask.merge(dir_name) - 将 Bitcask 数据存储中的数据文件合并成更紧凑的形式，同时生成 hint 文件，用于进程重启时加速 keydir 的构建。

bitcask.sync() - 将写入强制同步到磁盘。

bitcask.close() - 关闭 Bitcask 数据存储，并将所有待处理的写入（如果有）同步到磁盘。后续进程重启时会创建新的活跃文件，并基于 hint 文件构建索引。

以上就是 Bitcask 的原理与相关细节，感兴趣的话可以考虑使用自己擅长的语言实现一下。

本文来自于 Riak 官方论文：

• https://riak.com/assets/bitcask-intro.pdf