bitcask
今天比较颓废, 各种看剧煮饭shopping被理发小哥调戏.
为了挽救没有学习的无力感, 决定花二十分钟写一段代码.
按照 [bitcask paper](http://downloads.basho.com/papers/bitcask-intro.pdf)的说明, 大概写了下实现 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
14.01.25
为了挽救没有学习的无力感, 决定花二十分钟写一段代码.
按照 [bitcask paper](http://downloads.basho.com/papers/bitcask-intro.pdf)的说明, 大概写了下实现 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
14.01.25
