Bitcask[1]是又一种存储引擎数据结构。与LSM-tree一样，bitcask转随机写为顺序写，具有更好的写性能；与LSM-tree的有序结构不同，bitcask不对kv排序，使用hash表做索引加速read，当然也不就无法支持range query(scan)。

对于一个Bitcask实例，任一时刻，只有一个文件可以进行写入，如下图中active data file，当active data file达到一定的size，即被close变成immutable older data file，并open一个新的文件作为active data file。active data file写入只能append，即只有顺序写，充分利用顺序写比随机写快的性质，这一点与LevelDB一样。

data file的格式可以看成一组kv的list，每个kv的格式如下图，比较简单。

为支持get(key)，Bitcask在内存中维护一个hashtable，称为keydir，记录每个key最新的value在磁盘上的位置(file_id+offset)及size。

因为bitcask总是追加记录，需要额外的过程来执行compaction(bitcask称为merge)，删除无效的key/value。

Merge过程遍历所有的immutable data files，只保留每个key最新版本的value，生成新的merged data file。同时，还会为每个merged data file生成一个对应的hint file，记录了merge后各value的位置信息，用于构造keydir。

就这么简单。

References