bitcask论文翻译/笔记

时间:2024-01-21 08:30:42

翻译

论文来源:bitcask-intro.pdf (riak.com)

背景介绍

Bitcask的起源与Riak分布式数据库的历史紧密相连。在Riak的K/V集群中,每个节点都使用了可插拔的本地存储;几乎任何结构的K/V存储都可以用作每个主机的存储引擎。这种可插拔性使得Riak的处理能够并行化,从而可以在不影响代码库其他部分的情况下改进和测试存储引擎。

有很多类似的本地K/V存储系统,包括但不限于Berkeley DB、Tokyo Cabinet和Innostore。在评估此类存储引擎时,我们想实现的目标包括:

  • 读取或写入每个项目的低延迟
  • 高吞吐量,尤其是在写入随机项目的传入流时
  • 处理比RAM大得多的数据集的能力,无退化
  • 故障友好性,在快速恢复和不丢失数据方面都很好
  • 易于备份和恢复
  • 相对简单、可理解(因而可支持)的代码结构和数据格式
  • 访问负载大或容量大时的可预测行为
  • 允许在Riak中轻松默认使用的许可证

实现其中一些目标并不困难,但是想实现所有目标就不那么容易了。

现有的本地K/V存储系统(包括但不限于作者编写的系统)均未达到上述所有目标。当我们在与Eric Brewer讨论这个问题时,他关于哈希表日志合并的关键见解是:这样做可能会比LSM树更快或更快。

这导致我们以新的视角探索了20世纪80年代和90年代首次开发的日志结构化文件系统所使用的一些技术。这次探索导致了Bitcask的诞生,它是一个能够完全实现上述所有目标的存储系统。虽然Bitcask最初是为了给Riak使用而诞生,但是它的设计很通用,因此也可以作为其他应用程序的本地K/V存储。

模型描述

active data file

最终采用的模型在概念上非常简单。Bitcask实例是一个目录,我们强制规定在给定时间内,只有一个操作系统进程可以打开该Bitcask进行写入。您可以将该进程有效地视为“数据库服务器”。在任何时候,该目录中都有一个文件由服务器进行写入操作。当该文件达到一定大小时,它将被关闭,并创建一个新的活动文件。[font color="#FFA500"]一旦文件被关闭,无论是出于有意还是由于服务器退出,它都被视为不可变的,并且永远不会被再次打开进行写入。[/font]
bitcask on disk

活动文件,也就是上文提到的active data file,只能以追加的方式写入,这意味着顺序写入的同时不需要磁盘寻址。
文件中的每个键值对entry的格式如下:
kv
每次写入时,都只是向active data file追加一个新的entry。删除操作只是写入一个特殊的墓碑值(可以理解为是一个特殊标记),它将在下一次合并时被删除。因此,Bitcask数据文件无非是这些entry的线性序列:
kvs on data file

keydir

active data file中完成追加操作后,接着去内存中更新一个名为keydir的数据结构。keydir是一个哈希表(在本论文中它是一个哈希表,也可以是其他数据结构),它将Bitcask中的每个key映射到一个固定大小的结构,这个结构记录了这个key写在哪个文件、该键在该文件中的偏移量以及大小。

keydir
一开始我觉得上面这张图就是对bitcask中哈希表存储内容的正确理解,但是后来觉得下面这个图才是,因为哈希表的value存储的应该是entry的信息,而不是entry中value的信息。原论文中的图有比较大的迷惑性。
keydir

数据写入与读取

数据的写入其实在上面两节已经介绍过了,为了方便理解记忆就再总结一下。
写入很简单,就是往bitcask中追加一条entry,然后更新keydir(原子操作),将刚刚新增的entry的信息存储起来,就像下面这样:
存储

数据的读取流程则是先拿着keykeydir中取出相应的entry信息,然后根据entry中提供的信息去data file中取出key对应的value,就像下面这样:
读取

数据合并

因为bitcask删除的数据的方式是通过追加一条相同key的entry实现的,所以文件的size会越来越大,就需要定期的合并文件,合并的过程是这样的:

  1. 先遍历所有的old data file,将所有的有效数据进行合并,如果有多个entry含有相同的key,则只保留最新的entry,有点像Redis中的AOF
  2. 合并完成后,old data file会变成merge data file,且数量也会减少,例如10个old data file 合并成5个merge data file
  3. 因为bitcask是在内存中构建索引,也就是之前提到的keydir,构建keydir需要在启动的时候扫描所有的data file,如果数据量很大,那么构建索引的过程就会很耗时,为了解决这个问题,bitcask在合并数据的时候还会为每个merge data file生成一个hint file,这个hint file中存储的也是一堆entry,这些entry的格式和data file中的entry保持一致,唯一的区别就是data file中的entry存储的value是真实数据,而hint fileentryvalue存储的是数据的位置。

entry对比

结束

目前对bitcask的理解也就是这些了,肯定有不准确的地方,想要彻底弄明白也只能自己手搓一个kv存储才行。有任何问题都可以在评论区交流。