BeansDB学习笔记
http://www.douban.com/note/122507891/
同时InfoQ中还有刘洪清大哥的演讲视频及资料：http://www.infoq.com/cn/presentations/lhq-beansdb-design-implementation
BeansDB是一个简化了的Dynamo系统，适合存储多个小文件。它的结构个人认为可以分成下面的部分：一致性协议，同步算法，客户端代理，底层存储。
BeansDB实现的是弱一致——豆瓣的用户上传照片后一般不会做改动，弱一致就够了，所以不看它的一致性协议；同样的原因，不看它的sync流程（没时间看。。。），不看Proxy部分（只有100多行吧，对异常处理应该不是太完善），个人感觉应该是类似于ClientManager之类的东西，在弱一致性下实现的应该对最终一致的实现没有多大的启发。这样，到头来对BeansDB的研读就退化成为对底层存储——仍旧是KV数据存储的研究。
BeansDB的存储使用了BitCask算法。关于BitCask的详细介绍可以参看这里： http://blog.nosqlfan.com/html/955.html
BitCask可以分为三部分：存储在内存中的索引，持久化的数据——包括多个已经被持久化不会改变的数据文件和一个当前将内存中数据内容flush的文件，然后，根据原论文的推荐，还需要一个状态文件——用于实现内存索引的序列化，使得重启时可以使用反序列化的功能迅速构建原索引。
BitCask与GDBM的数据存储方式最大的不同就是它采用日志型日志，这样对数据的删除可以看做是对数据的插入——诸如GDBM中对文件空白处的处理可以留给以后一起处理，或者不做处理。这种lazy的思想采用以空间换时间的策略，从而可以避免随机写带来的性能上的损耗。
BitCask中内存索引在BeansDB中被实现为一个HashTree。使用HashTree有以下的几点好处：
1.HashTree实现简单，查找高效，而且BeansDB加入了对HashNode的merge和split的伸缩策略，是查找更快速。
2.HashTree的状态节点类似于二次哈希对dir的扩充，一个数据节点的分裂不会影响其它数据节点的查找
3.HashTree采用分节点存储使得整个索引存储形成一种分层结构，这有助于在sync时快速定位到不同的数据节点，同时也避免了对无关节点的sync，节约了时间，值得借鉴。
BeansDB使用了Leader/Follower的线程模型替代以往的生产者消费者模型，也是需要学习的。
对BitCask的实现分别被存放在htree.c——用来实现内存索引HashTree，record.c——用来实现对datafile和hintfile的操作，bitcask.c——用来定义BitCask的基本操作。
下面详细讲述一下BitCask的工作流程，其中用到的组件有：多个older datafile，及其对应的hintfile，还有一个active datafile，以及存储其中键值的cur_tree，最后还有一个tree，用来存储所有的键值，包括older datafile和cur_tree中的所有键值。
1.首先需要打开BitCask。
1.1扫描目录下的所有older datafile（打开时不存在active datafile）
1.1.1如果它有对应的hintfile，那么扫描这个hintfile中的键值，加入到tree中
1.2.1否则扫描datafile生成一棵HTree，根据这棵HTree生成hintfile文件，并把HTree中的键值存入tree中
1.2datafile是按照序号递增的方式命名的，这样扫描结束后，我们就会记录下总共有多少个datafile，并将最后一个datafile设置成为active datafile。新建一个HTree——curr_tree，作为active datafile的内存索引。
2.首先应该介绍查找的流程，直接从tree中查找，如果这个value存在的话，我们可以得到这个value所在的文件名和它在文件中的偏移。这时需要根据这两个信息分情况查找，具体步骤在bitcask.c的bc_get函数中。
3.然后是插入，删除和更新操作。这三种操作都被看做是插入操作，放到active datafile中。但是由于我们使用了version，所以需要先在tree中查找这个key对应的version，然后根据特定的version比较原则来判断下一步到底如何处理。详细的比较情形可以参见源码剖析对bitcask.c的剖析。
4.在3中的删除和更新操作都有可能造成older datafile中一些value值过期无用。为了节省文件空间，我们需要进行定期的GC，将原来文件中无效的数据清除掉。这通过比较tree和hintfile的HTree来决定。如果hintfile中的键值跟tree中的键值不同，那么认定value值被更改——或者被删除，或者被重新安排到了其它文件的其它地方。如果满足一定的条件，则根据tree中对value的记录重新建立datafile文件以及与之对应的hintfile文件。
5.使用完后对BitCask进行close操作，一般需要GC。