Bitcask - 日志结构的快速 KV 存储


Bitcask 是最高效的嵌入式键值 (KV) 数据库之一,旨在处理生产级流量。向世界介绍 Bitcask 的论文称它是一个用于快速键/值数据的日志结构 哈希表,用更简单的语言来说,这意味着数据将按顺序写入仅附加日志文件,并且会有指针对于每个key指向position其日志条目的。从仅附加日志文件构建 KV 存储似乎是一个非常奇怪的设计选择,但 Bitcask 不仅使其高效,而且还提供了非常高的读写吞吐量。

Bitcask 被引入作为名为Riak的分布式数据库的后端,其中每个节点用于运行一个 Bitcask 实例来保存它负责的数据。在这篇文章中,我们详细研究了 Bitcask 及其设计,并找到了使其如此高效的秘诀。

Bitcask 使用了很多来自日志结构文件系统的原则,并从许多涉及日志文件合并的设计中汲取灵感,例如 - 在 LSM 树中合并。它本质上只是一个仅附加(日志)文件的目录,具有固定结构和内存中索引,其中包含映射到点查找所需的一堆信息的键 - 指的是数据文件中的条目。


当提交一个新的 KV 对以存储在 Bitcask 中时,引擎首先将其附加到活动数据文件,然后在 KeyDir 中创建一个新条目,指定存储值的偏移量和文件。这两个操作都是原子执行的,这意味着要么在两个结构中都进行输入,要么都不进行。
放置一个新的键值对只需要一个原子操作,封装一次磁盘写入和一些内存中访问和更新。由于活动数据文件是仅附加文件,因此磁盘写入操作不必执行任何磁盘寻道,从而使写入操作以最佳速率进行,从而提供高写入吞吐量。

这个KV store不支持开箱即用的partial update,但是支持full value replacement。因此,更新操作与放置一个新的 KV 对非常相似,唯一的变化是不是在 KeyDir 中创建一个条目,而是用新数据文件中的新位置更新现有条目。
与旧值对应的条目现在是悬空的,将在合并和压缩期间明确地被垃圾收集。

删除键是一种特殊操作,其中引擎以原子方式在活动数据文件中附加一个新条目,其值等于逻辑删除值,表示删除,并从内存中的 KeyDir 中删除该条目。墓碑值被选择为非常独特的东西,因此它不会干扰现有的值空间。

删除操作,就像更新操作一样,非常轻量级,需要磁盘写入和内存更新。同样在删除操作中,与已删除键对应的较旧条目将悬空,并将在合并和压缩期间明确地被垃圾收集。

从存储中读取 KV 对需要引擎首先找到数据文件及其中给定键的偏移量;这是使用 KeyDir 完成的。一旦该信息可用,引擎就会从偏移量处的相应数据文件执行一次磁盘读取,以检索日志条目。根据存储的 CRC 检查检索到的值的正确性,然后将该值返回给客户端。
该操作本质上是快速的,因为它只需要一次磁盘读取和一些内存访问,但可以使用文件系统预读缓存使其更快。

正如我们在更新和删除操作期间看到的那样,与键对应的旧条目保持不变并悬空,这导致 Bitcask 消耗大量磁盘空间。为了提高磁盘利用率,引擎有时会将较旧的已关闭数据文件压缩为一个或多个与现有数据文件具有相同结构的合并文件。

合并过程遍历 Bitcask 中的所有不可变文件,并生成一组数据文件,其中仅包含每个当前键的实时和最新版本。这样,新数据文件将忽略未使用和不存在的键,从而节省大量磁盘空间。由于记录现在存在于不同的合并数据文件中并处于新的偏移量,因此它在 KeyDir 中的条目需要原子更新。

Bitcask 的优点和缺点
优势

  • 读取和写入操作的低延迟
  • 高写入吞吐量
  • 单个磁盘寻求检索任何值
  • 可预测的查找和插入性能
  • 崩溃恢复快速且有限
  • 备份很简单 - 只需复制目录就足够了

弱点
KeyDir 始终将所有键保存在内存中,这给系统增加了一个巨大的限制,它需要有足够的内存来包含整个键空间以及文件系统缓冲区等其他必需品。因此,Bitcask 的限制因素是可用于保存 KeyDir 的 RAM 有限。

虽然这个弱点是一个主要的弱点,但解决这个问题的方法相当简单。我们通常可以对键进行分片并水平扩展,而不会丢失很多基本操作,如创建、读取、更新和删除。