CouchBase的新引擎ForestDB

2014年底CouchBase公布了ForestDB的Beta版，将用来作为下一代的存储引擎。仓库star了半年之后才开始来看介绍，感觉还是值得继续关注的项目，倒并不是说用了多么独特的设计，而是作为数据库底层所涵盖的性能，事务，崩溃恢复等等，ForestDB都顾及到了，并且目前已经发布了1.0Beta版。

众所周知，CouchBase是两种存储引擎的混合版：内存Memcached的集群版MemBase以及分布式文档数据库CouchDB。后者是用Erlang写的B-Tree结构的存储引擎。这种混合布局的数据库解决方案还有类似的Aerospike，后者由一个内存Hashtabe再加上专门服务于SSD的持久化引擎Cirusleaf构成。人们常常拿Aerospike和CouchBase来对比，在Aerospike还没有开源的日子里，CouchBase是很多组织的替代方案，然而，或许是由于两者在Benchmark上的巨大差距，促使CouchBase在取得一定商业成功和市场份额之后也决心改进自己的存储引擎解决方案，ForestDB就是努力的结果。从描述上看，ForestDB的原型来自于ACM SIGMOD在2011年举办的编程大赛的获胜者的解决方案。ACM SIGMOD每年都会举办存储引擎开发类的竞赛，2011年的题目是"采用Flash的可持久化内存索引实现"，需要实现者能够提供增删改查以及迭代操作，所有单记录操作必须是ACID的。获胜者采取了如下的混合结构设计：

这个结构跟ForestDB基本完全一致，只是ForestDB让这个设计在工程上更加成熟和稳定。传统的B-Tree的缺点本公众号在之前的文章里已经多次介绍过，不过，ForestDB的目的并不是解决这些缺点(主要是频繁更新之后的树结构退化)，因为在使用SSD后，这些缺点很大程度上已经不是大问题了。ForestDB的设计主要是针对长和可变的Key值进行的优化：数据结构主体是一个Trie树，树的每个节点都是一个B+Tree，因此ForestDB把这种结构称为HB+-trie(Hierarchicial B+-Trie)。HB+-trie会把每个Key切分成固定长度的许多Chunk，每个Chunk默认8字节。如果把每个Chunk看做是一个字母，那么HB+-trie就是一个Trie结构的树，如下图所示。

在检索时，首先拿Key切分后的第一个Chunk来找到对应的B+-tree节点，然后在该子树里继续检索到叶子节点，如果该叶子节点已经可以定位到Value，那么检索结束，否则就根据该节点指针指向的下一个B+-tree继续检索。因此，在进行检索时，以Chunk为单位进行比对，一旦定位到记录，则直接返回而没有必要比较后边的Chunk。

在ForestDB内部，存在2种索引，一种是针对Key的主索引，就采用上述的HB+-trie存储，另一个是自增索引，采用普通B+-tree，因为自增ID大小可控，没必要引入为长记录优化的结构。为了支持ACID，ForestDB也同样采用了WAL日志，并且利用批处理机制避免SSD上常遇到的写入放大：在内存中针对还没有索引的记录维护它们的WAL的ID索引和自增索引。

ForestDB另一个值得称道之处在于Block块设计和文件布局。由于每次IO都是以块为单位进行的，因此文件布局尽可能按照块进行对齐。针对更新的记录，不允许在原块处进行处理，因为那样会打破块对齐的原则，因此都是在把修改后的树节点和记录添加在文件最后：针对B+-Tree的结构这还需要修改一系列节点，包含叶子节点的父节点等等，所有这一系列修改的路径所包含的节点都会添加在数据文件最后。

ForestDB的所有IO都是O_DIRECT标志，意味着操作系统的文件缓存是被bypass掉的，因为ForestDB觉得按照自己的需求设计Block块缓存更可控。

目前，事务隔离级别是RC(Read Committed)和RU(Read Uncommitted)，在以后的版本中ForestDB准备实现Serializable和RR(Repeated Read)隔离级别。由前述的结构可以很显然的推导出事务是基于MVCC实现的。

Benchmark结果：32G内存，512G SSD，Ext4文件系统。1亿条记录，Key大小为32字节，Value为1KB左右。在不同负载情况下，ForestDB不论是插入还是写入性能，或者读写混合负载表现均优于SSD上表现良好的LSM-Tree型日志存储LevelDB和RocksDB，跟LevelDB的最大差距可以达到7倍。