Bitcask

A Log-Structured Fast KV Store

学习Bitcask的缘由是在Rust中文社区看到了一名高中生正在用Rust实现一个Key-Value数据库系统：Dorea，抱着学习的心态下载了这个项目研究了一下，这个数据库系统使用的存储方案是一个基于hash表结构和key-value的日志型存储模型，名为Bitcask。

Bitcask起源于一篇同名的数据库模型论文，这篇论文阅读起来没有什么障碍，读完很快就可以理解。豆瓣在2018年就已经基于Bitcask开发了适合于豆瓣使用场景的海量小文件存储系统BeansDB，并成功应用于应用于生产环境，类似的项目还有使用Go语言开发的RoseDB（未应用于生产环境）。

下面记录一下我对Bitcask的理解，后续会考虑将其应用到Dorea的开发中。

---

论文地址：Bitcask- A Log-Structured Hash Table for Fast KeyValue Data

---

日志型的数据文件

所谓日志型，就是Append only，所有写操作只允许追加新的数据而不允许修改老的数据，就像我们的各种服务器日志一样。

在Bitcask模型中，数据只增不减地写入文件中，每个文件有一定的大小限制，当文件大小达到到相应的限制时，就会产生一个新的文件并在新的文件中继续进行追加，而老的文件将只读不写。在任意时刻，只有一个文件是可以写入的，Bitcask模型中将当前可以写入的文件称为为Active Data File，而其他的已经达到限制大小的文件，称为Old Data File。

文件中的数据结构非常简单，每一条数据的结构分别为Key，Value，Key Size，Value Size，Timestamp，Crc校验值，一条条这样格式的数据就组成了数据文件：

如果数据文件这样持续的存下去，是会无限膨胀的，为了解决个问题，Bitcask有一个定期的Merge操作，定期将所有Old Data File中的数据扫描一遍并生成新的Data File（没有包括Active Data File 是因为它还在不停写入），这里的Merge其实就是将同一个Key的多个数据只保留最新的一个。每次Merge后，新生成的数据文件就不再有冗余数据了。

基于Hash Table的索引数据

上面讲到的是数据文件，日志类型的数据文件会让我们的写入操作非常快，日志型的优势之一是将磁盘当作磁带，顺序读写的效率非常高，但是如果在这样的日志型数据上使用Key值进行顺序查找，是一件非常低效的事情，所以需要使用一些方法来提高查找效率。

在Bitcask模型中，使用了一个基于Hash Table的索引数据结构，除了存储在磁盘上的数据文件，还有另外一块数据，那就是存储在内存中的Hash Table，Hash Table的作用是通过Key值快速的定位到Value的位置。Hash Table的结构大致如下图所示：

Hash Table对应的这个结构中包括了三个用于定位数据Value的信息，分别是文件Id号(FILEID)，Value值在文件中的位置（VPOS），Value值的大小（VSZ），于是我们通过读取FILEID对应文件的VPOS开始的VSZ个字节，就可以得到我们需要的Value值。

使用Hint File对索引进行持久化

我们称其为索引的Hash Table，是存储在内存中的，Bitcask模型中并不保证在断电或重启后的Hash Table中的索引数据不丢失。

因此，我们每次启动时需要整个扫描一遍我们的数据文件，重建Hash Table索引，如果数据文件很大，这个重建的过程将非常耗时。因此Bitcask模型中包含了一个称作Hint File的部分，目的在于提高重建Hash Table索引的速度。

上面讲到在Old Data File进行merge操作时，会产生新的Data File，而Bitcask模型实际还建议同时生成一个Hint File，这个Hint File中每一项的数据结构，与Data file中的数据结构非常相似，不同的是他并不存储具体的Value值，而是存储Value的位置（像在Hash Table中的一样）,Hint File包含Key、Key Size、Value Size、Value Position、Timestamp。

这样，在重建Hash Table时，就不需要再扫描所有Data File文件，而只需要将Hint File中的数据一行行读取即可，这样就可以大大提高重启数据库的速度。

更多资料

Bitcask - A Log-Structured Fast KV Store

Dorea Database