日志型key/value存储模型 Bitcask

Bitcask是一个key-value存储模型，基于hash表结构，并且有个特点，是日志型的数据文件

设计思路非常简洁，值得学习一下 基于Bitcask模型实现的存储系统例如： （1）Riak Erlang编写的高度可扩展的分布式数据存储 （2）beansdb 豆瓣开源数据存储系统

什么是日志型数据文件？

Bitcask模型使用物理文件保存数据，使用了类似日志服务一样的方式，就是只追加，保证文件是一直顺序写入的，写入性能非常好 所以Bitcask模型的文件存储结构非常简单，一直向一个文件中写入，当文件大小达到预定值时，新建一个文件再接着写 就形成了 N个旧文件 + 1个活跃文件 的结构

数据文件中每条数据的结构如下

如何高效读取数据？

Bitcask模型使用了索引哈希表，表中记录了全部的主键和位置信息，哈希表是存放在内存中的 get key 时，从内存的hash表中快速取得key对应的value的位置信息，然后读取数据文件，取得value hash表每条记录的结构

如何处理删除修改数据？

Bitcask模型只支持文件的顺序操作，如何处理修改删除数据呢？ 删除数据 不直接删除记录，而是新增一条相同key的记录，把value设置一个删除的标记 原有记录依然存在于数据文件中，只是更新索引哈希表 修改数据 Bitcask不支持随机写入，修改数据时不会找到目标记录进行修改 还是新增一条相同key的记录，把value设置为新值

如何处理旧数据？

从删除修改数据的处理方式中可以看到，时间一长，肯定会出现大量的无用记录，浪费存储空间 Bitcask会定期进行Marge操作，扫描所有旧数据文件中的数据，生成新的数据文件 扫描时，把已经被置为删除状态的记录直接过滤掉，修改过的数据，只保留时间最近的一条

如何提高重建hash索引表的效率？

Bitcask模型不保证重启时hash表数据不丢 那么启动时重建hash表，就需要整个扫描一遍数据文件，非常耗时 Bitcask模型中包含了一个hint file，目的在于提高重建hash表的速度 hint file 会在Marge操作时产生

hint file 的记录与数据文件的格式基本相同，唯一不同的是value部分，不是记录实际的value值，而是value的位置 这样，重建hash索引表时，不用扫描数据文件了，直接读取hint file就可以了，hint file要比数据文件小很多，所以重建的效率大大提高了

Bitcask模型的整体结构

hash index file 内存中的hash表，记录key和value的位置，用于快速查找 data file 只支持顺序写入，数据大小达标后就新建一个文件，形成 1个活跃文件 + N个旧数据文件 定期对数据文件进行Marge，清理掉无用数据 hint file 相当于存在于DISK中的索引文件，用于在重建hash index file时进行提速，在Marge操作中产生