BitCask论文翻译/笔记

博主：鲨鱼辣椒
发布时间：2024 年 01 月 11 日
1777 次浏览
暂无评论
3016字数
分类：阅读

## 翻译

论文来源：[bitcask-intro.pdf (riak.com)](https://riak.com/assets/bitcask-intro.pdf)

### 背景介绍

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进行写入。您可以将该进程有效地视为“数据库服务器”。在任何时候，该目录中都有一个文件由服务器进行写入操作。当该文件达到一定大小时，它将被关闭，并创建一个新的**活动文件**。<span style='color:#FFA500'>一旦文件被关闭，无论是出于有意还是由于服务器退出，它都被视为不可变的，并且永远不会被再次打开进行写入。</span>
![bitcask on disk](https://vip.helloimg.com/images/2024/01/16/oIpuLD.png)

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

#### keydir

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

![keydir](https://vip.helloimg.com/images/2024/01/16/oIzGct.png)
一开始我觉得上面这张图就是对`bitcask`中哈希表存储内容的正确理解，但是后来觉得下面这个图才是，因为哈希表的`value`存储的应该是`entry`的信息，而不是`entry`中value的信息。原论文中的图有比较大的迷惑性。
![keydir](https://vip.helloimg.com/images/2024/01/16/oIzo3v.png)

#### 数据写入与读取

数据的写入其实在上面两节已经介绍过了，为了方便理解记忆就再总结一下。
写入很简单，就是往`bitcask`中追加一条`entry`，然后更新`keydir`（原子操作），将刚刚新增的`entry`的信息存储起来，就像下面这样：
![存储](https://vip.helloimg.com/images/2024/01/20/oIk3Su.png)

数据的读取流程则是先拿着`key`去`keydir`中取出相应的`entry`信息，然后根据`entry`中提供的信息去`data file`中取出`key`对应的`value`，就像下面这样：
![读取](https://vip.helloimg.com/images/2024/01/20/oIg8yA.png)

#### 数据合并

因为`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 file`中`entry`的`value`存储的是数据的位置。

![entry对比](https://vip.helloimg.com/images/2024/01/20/oIrnaC.png)

### 结束

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

最后修改：2024 年 01 月 20 日

如果觉得我的文章对你有用，请随意赞赏

此处评论已关闭