Kyoto Cabinet之kchashdb

对Embeddable data storage engines比较感兴趣,之前也只精读了leveldb,泛读了rocksdb的代码,这俩都是LSM Tree的实现,感觉还是有点窄,所以一直想找基于B+Tree实现的引擎看看,晦涩的lmdb给我看的半死,不爽,然后读了一个还在开发中的B+tree实现的引擎(传送门),实现比较清晰不过感觉这就是写着玩的没有生产环境的验证,还是不爽,所以找到了Kyoto Cabinet,在看treedb之前,发现它有基于hash实现的内存和文件的引擎,比较好奇所以先看了下kccachedb(基于内存)和kchashdb(基于文件),测了下性能还不错,这里简单总结一下

KCcachedb

这个就是基于内存hash,实现的和redis、mc差不多,这里就不展开介绍了,总结一下它的优缺点吧

优点:

  1. 支持多进程读、多线程安全
  2. ACID
  3. read uncommitted的隔离(不知道算优点还是缺点。。。)
  4. 支持很多接口,set、get、remove、set_bulkget_bulkremove_bulk、add、cas、append、replace、increment、increment_double、copy、synchronize、dump_snapshot

缺点:

  1. 内存管理没有mc做的好,感觉就没做什么内存管理
  2. bucket不能动态扩展,用LRU来做淘汰

KChashdb

介绍

这个是基于文件实现的hash,文件结构也不复杂,主要分为Header、FreeBlockPool、Buckets section、Records section,如下图所示

前三部分定长不会动态调整,

  1. Header记录着一些元信息,如选项、bucket个数、checksum、flag等等

  2. FreeBlockPool保存着可以被回收使用的record的offset和size,不过这些信息也存储在内存的std::set当中,在使用的时候只需要通过upper_bound来匹配出最合适的FreeBlock即可,在close或者synchronize时会将这些信息dump到文件FreeBlock,当以Writer身份打开文件的时候会把文件中FreeBlockPool的信息恢复到内存std::set中;注:如果程序没有调用close关闭或其他异常关闭,下次打开时会进organize_file,把修复的record写入到新的db文件中,老的FreeBlock直接抛弃。即使使用ONOREPAIR标志打开,也是直接抛弃老的FreeBlock

  3. Bucket section是定长的bucket数组,每个元素大小首次可配,4B或者6B,里面存的是该bucket的top record地址,通过top record往下走就可以遍历同样hash值的record

  4. Records section保存着一条条Record,每条Record都有一个header,其中psize是padding的大小,如果等于UINT16MAX则代表这个record是被删掉了,left和right是在发生碰撞之后接着查找用的,这里处理普通的链式之外,也可以支持二分查找树以加快查找速度

特点

  1. kchashdb通过mmap的方式打开文件,小于msize偏移的内容可以直接通过memcpy来读写,大于的这只能通过pread和pwrite来读写,msize默认64M,如果db很大但msize配置很小则每次操作会进行多次磁盘读写,性能会有所下降
  2. 对于overwrite的问题,如果oldrecord的size大于newrecord,则直接overwrite就可以,多余的部分加入到FreeBlockPool当中,如果oldrecord的size小于new record直接将oldrecord回收到FreeBlockPool中,new record的插入位置则从FreeBlockPool当中匹配最佳,有则用没有则插入到文件末尾。kchashdb通过apow来尽可能解决overwrite的shiftrecord的问题,如果db操作中有很多overwrite,则可以通过首次配置apow选项,默认是3,也就是8字节对齐,一条record的多余部分会填充上padding,这样实际record占用会大一些,当对此record进行overwrite时,有padding来进行一波缓冲尽可能减少由于size不够用而shiftrecord的几率
  3. kchashdb可以动态合并文件碎片,当overwrite或remove操作一定次数后,会触发从上次偏移量开始向后的碎片合并,具体做法就是shift有效的record,将碎片合并在一起,合并一定数目或扫描一定步长后停止
  4. kchashdb要求必须显式调用close来关闭db,每次open时会在header标记db已打开,如果程序异常退出,下次打开发现标记还是已打开或FATAL的时候则认为文件有损坏的风险,默认进行reorganize_file来重新整理db,具体做法就是从Record section当中遍历所有,将其写到tmp文件然后在改名,如果db特别大的话会很耗时,不过可以在open是通过ONOREPAIR来直接打开跳过修复
  5. Bucket个数在首次打开时配置,后期不可调整,所以不能做类似内存hash的扩容操作,这个是不灵活的点,不过对于文件hash似乎没有什么好的办法来支持bucket扩展,所以需要在使用前评估db大小来确定bucket的个数,官方推荐是records number的1~4倍,假设有100亿,每个最大占6B,则bucket section上来就要占55G的空间,而为了提高访问速度,header,FreeBlockPool,Buckets Section是需要放在内存的,那么这就需要mmap的大小比较大了,至少55G,这还只是在1倍的情况下
  6. FreeBlockPool定长,默认1024,也就是说最多存1024个回收块,如果满了则淘汰一个再插入,这会导致淘汰的回收块不能再被使用,直到碎片整理或文件修复时才合并清除
  7. 冲突解决可以使用二分查找树,不过这样会使每个record的header占用多4到6个字节(right),这样可以解决在冲突较多时查找的效率,不过推荐还是初始设置合理的bucket个数然后使用linear的方式解决冲突以达到空间和时间的最优
  8. 支持事务,可以在open时通过打开OAUTOTRAN选项来是的每一个操作自动是事务,也可以通过begin_transactionend_transaction来显式事务。undolog这里实现的比较简洁,每次操作最多会更新文件的5个地方(Header、oldrecord、buckets section、FreeBlockPool、newrecord),所以undolog第一条一定是备份Header,然后修改文件哪个块(offset、size)之前就将之前块的内容写进log中,然后再真正更新文件内容,如果出错或者abort_transaction,则执行applywal来回滚,事务提交或回滚后truncate unlog,隔离级别是read uncommitted、kc封装了write_fastread_fast来确保在msize以内的用memcpy、以外的用pwrite、pread
  9. 可以配置压缩,大于1K会压缩
  10. 可以根据数据的重要性来配置sync策略:

    1. default risk on process crash: Some records may be missing. risk on system crash: Some records may be missing. performance penalty: none remark: Auto recovery after crash will take time in proportion of the database size.

    2. transaction implicit usage: open(…, BasicDB::OAUTOTRAN); explicit usage: begin_transaction(false); …; end_transaction(true); risk on process crash: none risk on system crash: Some records may be missing. performance penalty: Throughput will be down to about 30% or less.

    3. transaction + synchronize implicit usage: open(…, BasicDB::OAUTOTRAN | BasicDB::OAUTOSYNC); explicit usage: begin_transaction(true); …; end_transaction(true); risk on process crash: none risk on system crash: none performance penalty: Throughput will be down to about 1% or less.

  11. 为了达到性能的最优,需要对参数进行调整,我简单测了一下不同的参数对性能的影响,同样是写1000w条record,每条差不多30B,如下:

    1. 单线程,默认配置(64M msize、100w bucket):59.116s
    2. 4线程,默认配置(64M mszie、100w bucket):47.185s
    3. 单线程,调整bucket(64M msize、2000w bucket):49.579s
    4. 4线程,调整bucket(64M msize、2000w bucket):46.715s
    5. 单线程,调整mszie(8G msize、2000w bucket):12.312s
    6. 4线程,调整msize(8G msize、2000w bucket):11.873s

    可以看到msize越大越好,bucket越多越好,不过即使用默认配置,性能也还说得过去

  12. iterator支持挂回调,这个不错,不过也有hash的通病就是不能有序迭代还有就是不能像leveldb那样基于某个快照来进行迭代,另外每一步迭代都是全局独占写锁阻塞其他操作
  13. 备份:如果确保没有写请求可以直接cp文件来备份,或者使用copy命令来备份。也可以使用dump_snapshot来备份,他会阻住一切请求.如果不想阻住请他请求则可以通过synchronize命令,传一个外部备份脚本来备份。总之kc的备份做的有些繁琐,远不如rocksdb的checkpoint的好

总结

个人感觉kchashdb比较适合用在update、delete操作比较少的场景,因为他的块回收和碎片整理稍微有一些跟不上。总体还好,可以一用^^