BitCask存储引擎

简介

• bitcask是一个日志结构的kv存储引擎, 是分布式键值数据库Riak的存储引擎之一;
• bitcask在内存使用哈希表(keydir), 文件系统上使用特殊格式文件来实现高效的键值存储;

架构

• bitcask架构主要分为两个部分:
  • 内存中使用的是hashtable, key为键值, value为(文件ID, 数据偏移)对;
  • 硬盘中为一系列的日志文件, 日志文件按写入时间有序, 且只用追加删除, 不会修改;

基本流程

写

写操作主要有2步:

1. 先写磁盘文件，
2. 更新内存索引;

读

读流程操作如下:

1. 首先根据用户传入的 key 去内存中的索引中查找数据，如果索引中没找到，说明这条数据记录根本不存在(Bitcask的所有key都会在启动时加载到内存中)，此时返回一个 ErrKeyNotFound。
2. 如果在索引中根据 key 找到了对应的 LogRecordPos, 那么会根据其中的 FileId 字段去判断对应的数据文件是不是活跃文件，如果是直接用活跃文件，如果不是，就去 oldFiles 中找，这时有可能出现数据文件为空的情况，那么会返回 ErrDataFileNotFound 表示文件没找到。
3. 如果找到数据记录所在的数据文件，此时就可以通过 Offset 读处数据并返回， 如果数据已经被标记删除，会返回一个 ErrKeyNotFound。

启动

启动主要分为两步:

1. 加载目录中的数据文件，打开每个文件的文件描述符;
2. 遍历数据文件中的内容，构建内存索引;
   1. Bitcask 会依次从小到大遍历每个文件Id，对应的逻辑是将数据文件从旧到新进行加载

事务处理

垃圾回收

参考

1. https://riak.com/assets/bitcask-intro.pdf
2. https://www.joverflow.cn/posts/bitcask-design1/