Bitcask: A Log-Structured Hash Table for Fast Key/Value Data
awesomepaper
translate
字数2770 2021-03-02

译者注:豆瓣的 beansdb 使用 bitcask 概念 https://github.com/douban/gobeansdb

Bitcask 的起源与 Riak 分布式数据库的历史联系在一起。在 Riak 的 key/value 集群中,每个节点都使用插件化的本地存储;几乎任何 k/v 形式的引擎都可以来用。这种插件化的设计可以使 Riak 并行化使得存储引擎可以在不影响其他代码的情况下单独升级和测试。

已经存在很多这种 key/value 存储引擎,包括但不限于 Berkeley DB,Tokyo Cabinet, Innostore。在评估此类引擎时,我们考虑了许多目标,包括:

实现其中的一些是容易的,但是实现所有特性很难。

就上述所有目标而言,没有现成的 key/value 存储系统。我们就这个问题与 Eric Brewer 进行讨论,他提出了一个关键 idea: hash table log merging: 这样做可能比 LSM-trees 快得多。

这促使我们以全新的视角探索了在 1980 和 1990 年代首次开发的 log-structured file system 中使用的一些技术。这次探索引出了 Bitcask 的发展,实现了所有上述特性。当 Bitcask 被作为 Riak 的底层为目标开发出来后,可以作为一个本地 key/value 存储引擎通用于其他应用。

最终使用的模型非常简单。一个 Bitcask 实例是一个目录,同一时间只有一个操作系统进程写入 Bitcask。你可以将此进程看做 database server。任何时候,只有一个文件是“活动的”,可以被服务器写入。当文件大小达到阈值,就会被关闭,然后一个新的“活动”文件就被创建出来。一旦文件被关闭,或者由于服务器关闭导致文件被关闭,该文件就被视为不可变的,不会再被服务器写入。模型如下图所示:

“活动”文件只能被追加写,这意味着磁盘不需要寻道,数据格式如下:

每次写入,文件尾部被追加一条记录。请注意,删除只是写入一个特殊的逻辑删除值,在下一次归并时会被删除。因此,Bitcask 数据文件就像下面的线性条目序列:

在每次追加后,内存中的数据结构被称为 "keydir" 会被更新。"keydir" 是一个 hash table ,描述了 Bitcask 中每个 key 的位置(固定结构)(file, offset, value size)

(译者注:file_id表示哪个文件,value_pos 表示offset, 以及value size表示从value_pos取多少数据)

当发生写入时,'keydir' 自动根据最新数据更新,老数据仍然存在与硬盘中,但是读取使用 'keydir' 记录的最新版本的数据信息。正如稍后我们看到的,归并过程会删除老数据。

读取数据很简单,不会超过一次硬盘寻道。我们在 'keydir' 中查找数据的 key 位置,然后使用获得的 file_id, value_pos, value_sz 直接读取数据。在很多情况下,操作系统的文件系统预读高速缓存使此操作比预期要快得多,读取过程如下图

这个简单的过程会随着使用时间占用越来越多的存储空间,因为我们一直在写入新数据。一个单独的“归并”进程用来解决这个问题,“归并”进程遍历所有“不活动”数据文件,然后生成一组只包含“活动”数据的文件。

完成此操作之后,我们将在每个数据文件旁创建一个“hint file”,包含对应数据文件的位置和值的大小。

当 Bitcask 被 Erlang 进程打开时,会检查是否已经有其他进程已经打开当前 Bitcask,如果有,就会共享 keydir 信息,如果没有,会扫描所有数据文件,然后重建一个新的 keydir。如果数据文件有 ‘hint file’,可以加速这个重建过程。

上述就是 Bitcask 基本操作。显然,我们没有在这个文档中阐释所有操作细节;我们的目标是帮你了解 Bitcask 的概况。实际上还有一些细节讨论:

总而言之,鉴于最开始阐述的一组要求,Bitcask 是最适合这些要求的产品。