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

Riak 是一个专一于散布式存储的公司，他们想打造一个新的存储引擎，该引擎要能成功以下几个指标：

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

Bitcask 在概念上十分便捷，一个 Bitcask 实例就是一个目录，并且规则同一时辰只能有一个进程操作该目录，因此你可以把操作该目录的进程看作是数据库主机。

而后不论目录中有多少文件，同一时辰只会有一个生动文件用于主机写入。当该文件的大小到达指定的阈值，它会被封锁，而后创立一个新的生动文件。留意：不论是文件写满了还是主机（进程）分开了，一旦文件被封锁，它就成为了旧的数据文件（不生动）。而旧的数据文件是无法变的，不会再口头写操作。

所以 Bitcask 实例目录就是一个生动文件和多个旧的数据文件的汇合。

主机进程在写入优惠文件时驳回了追加形式（Append Only），从而防止了多余的磁盘寻址。由于写操作没有太多的提升技巧，必定等数据落盘了才算写入成功，所以顺序写是最经常出现、且最有效的提升手腕。虽然机械盘的随机写性能很差，但顺序写的成果还是不错的，Kafka曾经证实了这一点，当然除了顺序写 Kafka 还用了很多其它提升手腕。

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

总共有如下字段：

主机每次写入，都是向生动文件追加这样一条记载。另外删除也是一次性追加写入，只不过写入的是一个不凡的墓碑值（tombstone），用于标志一条记载的删除，所以 Bitcask 在删除数据时属于逻辑删除。当下一次性 merge 的时刻，再口头物理删除。

凡是驳回追加写形式的存储引擎，基本都是这个设计，比如 HBase。假设每次删除都间接驳回物理删除的话，那么速度无法能快。

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

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

以上这些记载要追加写入到磁盘，但内存中雷同要保养一个数据结构，在 Bitcask 外面叫 keydir。那么 keydir 外面存的都是什么呢？

看到这种结构，咱们首先想到 keydir 很或者是经常使用哈希表。没错，官网也介绍驳回哈希表成功，但你选用红黑树、跳表也是可以的，假设你须要有序遍历的话。

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

当主机向文件追加一条记载时，在内存中就会向 keydir 新增一个键值对。那么疑问来了，假设 key 曾经存在了怎样办？

很便捷，key 存在相当于修正，但关于数据文件而言，降级和删除一样，照旧是追加一条新的记载。数据文件在磁盘上，不会间接修正，降级和删除实质上都是写入。只不过删除时，会写入一个不凡的墓碑值，而降级则是写入一条新的个别记载，但记载中的 key 已存在。

记载降级之后，还要保养内存中的 keydir。由于 key 已存在，此时相当于对 keydir 启动降级，会保留新数据的位置信息。

虽然旧数据和新数据都存在于磁盘上，但 keydir 外面只会保留新数据的位置信息，因此任何读取都会经常使用最新的可用版本，而旧数据则会在 merge 的时刻被清算。

那么整个读取环节怎样的呢？示用意如下：

当基于 key 失掉 value 时，会先基于 key 在 keydir 中查找记载的位置信息。经过 file_id 可以定位到数据文件，经过 value_pos 可以定位到记载在数据文件中的偏移量。由于记载的前 4 个字段的大小是固定的，key 的大小可以计算进去，所以 value 的偏移量也能确定，再经过 value_sz 即可将详细的 value 读进去。

这里你兴许猎奇，为啥记载中曾经保留了 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>Bitcask 进程从新启动时要在内存中构建 keydir，假设是基于数据文件构建的话会很慢，而经过 hint 文件就可以极速构建了。由于 hint 文件外面不保留实践数据，它的容量会远比数据文件要小。

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

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

keydir 保留key和value 在磁盘上的位置信息，查找时要先经过 key 拿到位置信息，而后再基于位置信息拿到 value。所以这种设计就使得 Bitcask 必定满足以下几点，才干施展出威力。

到目前为止咱们就说完了 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 官网论文：