Bitcask

on technology

今天比较颓废, 各种看剧煮饭shopping被理发小哥调戏.

为了挽救没有学习的无力感, 决定花二十分钟写一段代码.

按照 bitcask paper的说明, 大概写了下实现 https://gist.github.com/soasme/8617918 省掉了锁, 用dict代替内存的key索引做了下简化.

bitcask 是种日志型的键值数据库. 大意是说: 写不修改, 写只追加. 读只取最后追加的那条数据. (时不时有人说丢数据, 就是用这种办法找回数据的吧. 说某月某日某时某分的数据, 去找下那时候的日志就好了) 老日志定期合并下舍弃不要(或者过期)的数据就好了.

时间复杂度 O(1). 具体到操作

  • 读操作是一次内存查找文件及位置长度, 一次文件io读(读操作可以直接seek到具体的位置)
  • 写操作是一次文件io顺序写, 一次内存位置更新

beansdb用 hash tree 做了索引上的优化. (https://github.com/douban/beansdb/blob/20d1de5bbb86700719c900d132f4036fbeaf0ae8/src/bitcask.c#L415)

关于优缺点, 可在Davies的日记里看: http://www.douban.com/note/122507891/ bitcask原始本尊: (有c/erlang): https://github.com/basho/bitcask