ForkBase：一种面向区块链及可分叉应用的高效存储引擎！（附论文）

2018 年 6 月 15 日 云头条

ForkBase是一种数据存储系统，旨在支持需要数据版本控制、分叉和防篡改等功能的应用。一个主要的例子就是区块链系统，但这还可能包括协作应用，比如GoogleDocs。举例说，如今以太坊和HyperLedger的数据结构就直接建立在键值存储系统上。ForkBase力求改而将上述这些属性一路推送到存储层：

一个直接的好处是，它为需要任意组合的上述功能的应用减少了开发工作。另一个好处是，它提供了额外的功能（比如高效的历史查询），根本无需额外成本，帮助应用更好地普及开来。最后，该存储引擎可以利用在应用层很难实现的性能优化。

实际上我们最终得到的是一种建立在底层对象存储系统上的键值存储系统，直接支持版本控制、分叉和篡改证据。ForkBase的核心是一种新颖的索引结构，名为POS-Tree（面向模式的拆分树）。

ForkBase架构

从下往上，ForkBase包括块存储层、表示层和一套数据访问API，块存储层执行分块和重复数据删除，表示层管理版本、分支和防篡改，这套API结合了结构化数据类型和分叉语义。更高级的应用服务（比如访问控制和自定义合并函数）可以实施在API的上面。

ForkBase是一种键值存储系统，其中存储的对象是FObject的实例。

数据版本控制

数据版本控制（保留每一个数据项的完整历史记录，包括任何分支和合并）方面的主要挑战是，管理存储的使用。很显然，重复数据删除大有机会，假设一个版本的内容与下一个版本并不完全改变。

基于增量数据（delta）的重复数据删除功能仅存储版本之间有差异的数据（delta），并通过遵循增量数据链来重构某个特定版本。在这种场景下，你可以尝试调整存储/重构成本取舍。

基于内容的重复数据删除将数据拆分成块，每个块都由其内容（即内容的哈希）作为独特的标识。然后可以检测到同样的数据块，消除冗余副本。

ForkBase选择了在块级进行基于内容的重复数据删除。与文件系统中使用的类似技术相比，ForkBase使用更小的块和可感知数据结构的分块策略。比如说，一个列表只会在元素边界处被拆分，那样根本不需要用多个块来重构列表项。ForkBase可识别许多不同类型的块，每种类型的块都由cid作为独特的标识，cid就是块内容的哈希。

可分块的对象类型（Blob、List、Set和Map）以POS树的形式存储起来。

FObject的uid只是该对象的Meta块的块id的别名。

分叉语义

对分叉的支持基于两个关键操作：分叉和冲突解决。分叉操作创建一个新的分支，分支与其他分支隔离开来的本地修改互相独立发展。ForkBase支持按需求分叉和按冲突分叉。

通过API显式请求按需求分叉，用用户提供的名称加以标记。一旦并发修改同一个数据项，隐式创建按冲突分叉。因Fork-on-Conflict而创建的分支是未标记的，就由其uid来标识。

标记的分支可以与另一个分支合并，由标记或版本作为标识。合并期间检测到冲突时，将返回冲突列表，并要求应用层提供解决方案。有内置的解析函数适用于简单的策略，比如追加、聚合和选择一个。

篡改证据

FObject的uid是对象的值及其衍生历史的独特标识。因此，逻辑对等要求对象不仅有同样的值，还有同样的历史记录。诸版本用加密哈希链连接起来，确保能够检测到企图篡改的任何行为。每个FObject存储它从bases字段获得的之前版本的哈希。

面向模式的拆分树

大型结构化对象通常不会全部访问。相反，它们需要细粒度的访问，比如元素查找、范围查询和更新。这些访问模式需要索引结构（比如B+-tree）很高效。但是现有的索引结构并不适合有许多版本，且版本可以合并的环境。

B+-trees和变体的基于容量的拆分策略对索引的值及其插入顺序非常敏感。这样一来，更难跨版本进行重复数据删除，合并两个版本时也更难发现之间的差异。使用固定大小的节点可以避开插入顺序问题，但由于结构中间的插入，带来了另一个问题：边界移位问题。

研究人员的解决办法就是使用面向模式的拆分树，它支持下列属性：

快速查找和更新
快速确定两棵树之间的差异，然后合并
高效的重复数据删除
篡改证据

树中的每个节点都是一个块（索引块或树叶处的对象块）。查找遵循拆分键指引的一条路径。子节点的cid是其内容的密码哈希，就如默克尔树（Merkle tree）中那样。拥有同样数据的两个对象将有同样的POS树，树比较提供了一种高效的递归解决方案。这里真正的秘诀在于，POS树如何决定在哪里拆分。

其结构受到基于内容的分片的启发，酷似B+-tree和默克尔树的组合。在POS树中，节点（即块）边界被定义为通过对象内容来检测的模式。具体来说，想构建一个节点，我们会从头开始扫描，直到一个预定义模式出现，然后创建新节点来保存扫描的内容。由于叶节点和内部节点的随机性程度不一样，我们为它们定义了不同的模式。

叶节点拆分使用滚动哈希函数来完成。只要滚动哈希中的q最低有效位都是零，模式匹配就会发生。如果模式匹配发生在元素的中间（比如Map的键值对），就会扩展块边界以覆盖整个元素。因此，除最后一个节点以外的每个叶节点都以一个模式结束。

索引拆分使用一种更简单的策略，寻找cid && (2^r -1) == 0的cid模式。可以通过为q和r选择适当的值来配置期望的块大小。为了确保块不会随意增大，可以强迫块处于某个阈值。POS树不是为对象内容仅仅是重复项的序列这种情况设计的――没有模式，所有节点都倾向于最大块大小，边界移位问题又回来了。

ForkBase实战：Hyperledger

论文的第5部分介绍了在ForkBase上构建区块链平台、维基引擎和协作分析应用程序。我在这里只想侧重于区块链使用场合，研究人员将Hyperledger v0.6移植到ForkBase的上面。

将Hyperledger移到ForkBase上只需要18行新的代码，并且从Hyperledger代码库删除1918行代码。（请注意，ForkBase本身大约有3万行代码！）。

另一个好处是，数据现在随时可用于分析。如果是状态扫描查询，我们只要关注存储在最新块中的版本号，即可获得所请求的键的最新Blob对象。之后，我们关注base_version来检索以前的值。如果是块扫描查询，我们关注存储在请求块上的版本号来检索此块的二级Map对象。然后，我们遍历键值元组，并检索相应的Blob对象。

状态扫描（返回特定状态的历史记录）和块扫描（返回特定块的状态值）在最初的Hyperledger代码库中比较慢，该代码库是为快速访问最新状态而设计的。（注意：这似乎要引用HyperLedger的对等事务管理器即PTM组件。Hyperledger还包含被索引的块存储系统）。

在这些扫描操作中，ForkBase显示出最大的性能优势。如果我们考虑延迟和吞吐量，基于ForkBase的Hyperledger实现和基于Rocksdb的Hyperledger实现非常接近。（下图中的ForkBase-KV是Hyperledger使用ForkBase作为纯粹的键值存储系统，并没有充分利用任何高级功能）。