Bitcask与TCHDB实现机制对比

Bitcask和Tokyo Cabinet的TCHDB都是基于hash的key-value存储系统，本文从两者的实现机制上进行简单的对比。

 

Bitcask: http://blog.chinaunix.net/space.php?uid=20196318&do=blog&id=154750

Tokyo Cabinet: http://blog.chinaunix.net/space.php?uid=20196318&do=blog&id=327754

 

对比项	Bitcask	TCHDB
记录存储模式	记录顺序存储，以日志的形式记录	记录可存储在任意空闲位置
空闲空间管理	记录始终在末尾添加，定期的进行merge操作来回收被删除记录的空间。	使用空闲块池来管理所有的空闲空间，当记录删除时回收空间，并在空闲块描述符个数超出阈值时进行连续空闲块的合并。
记录查找 （hash）机制	Bitcask的hash表只存在于内存中，hash冲突采用hash链的方式，并随着系统记录的添加与移除不断更新，为了加速启动时构建hash表的效率，每个记录在添加时同时也会建立一个定长的索引记录来记录其偏移位置，Bitcask通过索引记录能快速的构建hash表。	TCHDB的hash表不只存在于内存，还会存储到硬盘上，每个hash条目的值对应于该桶内第一个记录的偏移位置，其他冲突的记录通过每个记录的hash2、left、right指针（相当于一颗二叉查找树）来进行查找。
put操作	Bitcask每次以追加写的方式添加记录，同时追加记录更新hash表，效率很高。	TCHDB每次需要查找空闲块池定位一个合适的存储区域，然后查找hash表，并要解决hash冲突（可能需要读取多个记录，并修改最后一个记录的left、right）。
get操作	读取hash表，并在冲突链中对比key，找到对应记录的偏移位置并读取。	读取hash表的对应的slot，如果发现key不匹配，则根据key与slot中key的大小，在冲突树上进行查找，可能需要读取出多个记录。
del操作	从hash表和索引记录中删除对应的记录，对应的空间由merge进行回收。	从hash表中删掉对应的项，如果存在hash冲突，需更改冲突树的left、right指针。