Bitcask 学习笔记

BitcaskBasho 公司 设计研发的一款高性能键值数据库,基于日志文件的形式来管理数据,在设计文档中,他们声称实现了数据存储查询的『多快好省』,并且也有许多实践中的案例证明他们确实做到了这一点,例如,豆瓣自主研发的 BeansDB 也在很大程度上借鉴了 Bitcask 的设计思想(他们最近又用 Go 重新实现了一个版本),并用于他们线上服务。文档并不厚,只有简单的六页,所以花一点儿时间通读一遍,学习一下 Bitcask 的设计思路对研究开发自己的存储系统是大有裨益的。

在运行时 Bitcask 把所有数据存在硬盘上,每次写的时候就把数据追加到末尾,所以在性能上能达到媲美内存的速度。 Bitcask 会维护一个 file handler 指向当前正在写的文件,收到写请求就直接把数据追加在当前文件的末尾,而删除动作会写进去一个特殊标记,记录对应的 key 在这次操作中被删除。而读的时候,会根据在内存中维护的一个数据结构找到 key 在文件中的位置,只需要一次硬盘寻址就可以返回结果,从而在读写性能和数据持久化之间找到了一个平衡。

数据结构

文件数据结构

往硬盘文件上写数据时,数据结构的设计是必不可少的,基于此, Bitcask 才能在读写时返回正确的结果,并能确保数据的正确性。

crc
crc
timestamp
timestamp
key size
key size
value size
value size
key
key
value
value
size of
size of
size of
size of
crc coverage
crc coverage
Viewer does not support full SVG 1.1

一条数据的结构很简单,从图中可以看出,开头是对整个数据的校验值,用于保证文件中存的数据是正确的, timestamp 记录写入该数据时的时间,后面两个整型分别存储 key 和 value 的长度,再其后则为真正的 key 和 value 。 Bitcask 的文件内容即为多条这样的数据依次排列在硬盘上,每条新的数据直接追加到末尾。

在读的时候,只需要寻址到数据的位置,由于硬盘的预读机制,通常情况下只需要一次硬盘 IO 即可以获取整条数据并返回。

内存数据结构

硬盘的写问题解决了,还必须要有一个内存中的数据结构来记录一个 key 在文件的哪个位置,这样才能在查询的时候给出正确的值。

key
key
file id
file id
value size
value size
value position
value position
timestamp
timestamp
Viewer does not support full SVG 1.1

Bitcask 在内存中维护这样一个映射结构, key 对应的值有三者必不可少, file id 告诉 Bitcask 去哪个文件中去查询, value position 记录要找的 value 在文件的位置, value size 决定读取多长的字节。

与文件中的数据结构相结合,不难发现查询一个 key 过程为,

key
key
file id
file id
value size
value size
value position
value pos…
timestamp
timestamp
key
key
file id
file id
value size
value size
value position
value pos…
timestamp
timestamp
key
key
file id
file id
value size
value size
value position
value pos…
timestamp
timestamp
key
key
file id
file id
value size
value size
value position
value pos…
timestamp
timestamp
key
key
file id
file id
value size
value size
value position
value pos…
timestamp
timestamp
crc
crc
timestamp
timestamp
key size
key size
value size
value size
key
key
value
value
crc
crc
timestamp
timestamp
key size
key size
value size
value size
key
key
value
value
crc
crc
timestamp
timestamp
key size
key size
value size
value size
key
key
value
value
crc
crc
timestamp
timestamp
key size
key size
value size
value size
key
key
value
value
Older Data File
Older Data File
Older Data File
Older Data File
Older Data File
Older Data File
Active Data File
Active Data File
Get(key)
Get(key)
1
1
2
2
3
3
4
4
Viewer does not support full SVG 1.1

在这个过程中,涉及到硬盘 IO 的只有第三步找到 value 的位置,因此它的查询效率是很高的。

文件管理

考虑到效率,如果一个文件过大,会造成更长的寻址时间,并且 Bitcask 把左右的写记录都放在文件中,如果不进行文件内容的维护,势必会造成大量的冗余数据,造成硬盘空间的浪费和读写效率的下降。

Bitcask 当然考虑到了这些问题,它会根据设置的文件大小自动进行文件的 rotate ,超过一定的大小,会冻结当前文件,将其转为只读模式,并打开一个新文件作为 active file ,之后的写请求都发生在这个新文件上。这样就能保证每个文件的大小不会超过设定的阈值。而至于数据冗余问题, Bitcask 会维护一个 merge 线程将冻结文件中的数据重新读一遍并留下最终的结果。

比如说在文件中有这样一串操作,

set foo bar
set foo baz
set hello world
set fake-key fake-value
del fake-key
del hello

在 merge 之后,产生的新文件的内容为,

set foo baz

foo 只保留最新值,而已经删掉的 fake-keyhello 则被直接删除。同时在 merge 之后会伴随着新生成的文件产生一个 hint 文件,顾名思义,里面包含着利于提高读取效率的数据,

timestamp
timestamp
key size
key size
value size
value size
value position
value position
key
key
Viewer does not support full SVG 1.1

这样可以从 hint 文件直接构建内存中的数据结构,而不用再把新生成的文件再过一遍了。

小结

Bitcask 以其简洁的设计达到了低延迟高吞吐,并且能够处理比内存大得多的数据量,并且由于文件系统的存在,使得备份恢复非常容易,从中我们可以看到了 log 文件在其中发挥的作用,而充分利用文件系统的一个教科书级的大数据服务就是著名的 Kafka。作为个人的学习资料, Bitcask 是一个不可多得的范本。

Bitcask 当然也有它自己的问题,比如说不可避免的文件寻址,不能很方便地进行多机冗余备份,但在今天这样一个分布式的年代,将它部署到多机运行也不是太困难的事情,一个很直觉的想法是利用 ZooKeeperetcd 来管理 meta ,多个机器上的进程间就有了一个互相交流的基础。业界肯定有更成熟的方案,这一部分我还没有去研究了解。

原创文章,转载请注明: 转载自Panda Home

本文链接地址: Bitcask 学习笔记

文章的脚注信息由WordPress的wp-posturl插件自动生成