likes
comments
collection
share

Bitcask-高吞吐量日志型KV存储模型

作者站长头像
站长
· 阅读数 5

Bitcask是一个基于哈希表结构的高性能日志型KV存储模型

存储结构

Datafiles

在Bitcask模型中，数据文件以日志追加的形式只增不删保存。当单个数据文件的体积增加到一定限制时，会创建一个新的文件用于写入，旧的文件则变为只读不写（Close and immutable datafiles）。在任意时间点，只有一个文件是可写的（Active datafile），而且是顺序追加写入的，这个特点使Bitcask有非常高的读写吞吐量。记录的结构非常简单，包含（CRC，Timestamp，Key-Size，Value-Size，Key，Value），如下图所示（图片引用自arpitbhayani的参考文章，最后附有链接）。 Bitcask-高吞吐量日志型KV存储模型

KeyDir

在只追加的日志数据文件以外，Bitcask在内存中维护一个KeyDir哈希表，其中包含了Key及其对应的数据的元信息（ID，Value-Size，Value-Position，Timestamp）。 Bitcask-高吞吐量日志型KV存储模型

操作

1. 添加键值对：当一个新的键值对被提交，首先数据被追加到Active datafile中，并在KeyDir创建对应的包含偏移量的条目，这两步是原子的，要么都成功，要么都失败。

2. 更新值：当发生值更新时，Bitcask不会删除旧的数据记录，而是追加一个时间更新的数据记录到Active datafile中，并更新KeyDir中的数据记录元信息，这两步也是原子的。

3. 删除记录：当删除键值对时，Bitcask不会删除旧的数据记录，而是添加一个带有删除标记的时间更新的数据记录到Active datafile中，并更新KeyDir中的偏移量信息为悬空。

4. 读取键值对：发起查询请求时，通过KeyDir对应的数据记录元信息（Value-Size，Value-Position）找到最新的记录。

合并压缩

更新和删除操作导致大量的多余磁盘空间消耗，删除操作可能导致KeyDirs中的一些Key悬空无用。因此，经过一定的时间后，Bitcask会由一个异步的进程将较旧的只读日志文件合并压缩为更少的记录数量（移除已经被更新、删除的记录）。合并后的文件结构和现有的文件结构相同。

高性能重启

重启Bitcask的本质是重建KeyDir，这可以通过两种方式来完成。

  1. 读取全部的日志数据文件，重建KeyDir。

  2. 对于每个日志数据文件（特别是close and immutable datafiles），将其KeyDir包含的元信息直接保存为一个提示文件（在合并压缩后创建，或者由异步进程在适当时候创建），这样重建时则只需要读取这个更小的提示文件。即使Bitcask是异常崩溃退出的，来不及为active datafile创建该提示文件，重建时也只需要扫描active datafile即可，close and immutable datafiles的提示文件仍然是可用的。

优缺点

优点

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

缺点

KeyDir维护在内存中，而内存相比于磁盘来说，一般大小更加的有限。 一类可行的解决方案是对Key进行水平分片拓展。

Refs

arpitbhayani.me/blogs/bitca… en.wikipedia.org/wiki/Log-st… riak.com/assets/bitc… en.wikipedia.org/wiki/Bitcas…