Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
91 lines (73 sloc) 4.23 KB

Bitcask

厂里的 BeansDB
里面用的存储模型用的是 Bitcask。 而我刚好要维护 BeansDB 的 Golang
版本,所以看一下这论文,顺便做一下记录。
BeansDB 是我厂大牛
的作品,可惜我来豆厂的时候,Davies 已经去 Databricks 写
Spark 去了
一个 Bitcask
实例可以看成一个目录,目录下面放了数据文件,而每次操作都会写入到
active
的文件中,当这个文件大小达到一个阈值之后,就新建一个文件,之前的文件只读,不可以再写入数据。
+-------------------------+
|                         |
|                         |
| +-------------------+   |
| | active data file  |   |
| |                   |   |
| +--          /------+   |
|    \---------           |
| +--------------------+  |
| | order data file    |  |
| +--------------------+  |
| +--------------------+  |
| | order data file    |  |
| +--------------------+  |
| +--------------------+  |
| | order data file    |  |
| +--------------------+  |
| +--------------------+  |
| | order data file    |  |
| +--------------------+  |
|                         |
+-------------------------+

状态为 active 的文件在写入的时候,只能在文件尾部做 append 操作,这样可以减少不必要的磁盘检索。

每一条 K/V 数据的格式也非常简单

      |---------------------CRC converage -----------------------------------------|

                       size of
                  +-----------------+
                  |                 |
                  |                \|/
+-----------------+----------------------------------------------------------------+
| crc | tstamp | k|z | value_sz | key      | value                                 |
+----------------------------------------------------------------------------------+
                          |                                      /|\
                          |                                       |
                          +---------------------------------------+
                                   size of
这样,每次写入,都是将一条新的记录 append 到状态为 active
的文件中。即便是 删除 操作也是追加一条特殊的记录。
当写入操作完成之后,需要更新保存在 内存 中的一个 keydir
哈希树。keydir 里面保存着每一个 key 对应的文件,已经这个 key
在文件中的偏移量。
+-------------------------------------------------------------------+
|      +----------------------------------------------------------+ |
| key -|file_id | value_sz | value_pos | tstamp                   | |
|      +----------------------------------------------------------+ |
|                                                                   |
|      +----------------------------------------------------------+ |
| key -|file_id | value_sz | value_pos | tstamp                   | |
|      +----------------------------------------------------------+ |
|                                                                   |
|      +----------------------------------------------------------+ |
| key -|file_id | value_sz | value_pos | tstamp                   | |
|      +----------------------------------------------------------+ |
+-------------------------------------------------------------------+
value_post --> 值的位置

发生一次写入操作时, keydir 会随着本地数据的写入而自动更新。老的数据还会保存在硬盘上面,但是之后的读操作都是使用新的 keydir ,后面我们会看见 merge 操作最终会把旧数据移走。