【存储专栏】打破 K/V 存储的性能瓶颈

关注

发布于: 刚刚

【前言】

前文《区块链 ≠ 分布式存储》中，介绍了「区块链系统」和「传统分布式数据库」的异同，并认为“世界状态”的维护是区块链系统或区块链存储模块的核心关注点，而交易数据、账户及其相关数据、交易执行结果三者一同构成账户模型下区块链系统最基本的世界状态。

本文将从数据特点、性能表现、扩展性等方面出发，对区块链存储模块的数据库选型及定向优化进行介绍。

区块链存储模块需要关心的数据类型

【账本数据】

▲ 什么是区块链账本?

通常情况下，区块链账本包含「账户数据」与「合约数据」。

用一个日常的例子来理解账本：在查询银行账户时，我们最关注的可能是当前的余额，但如果要探究当前的余额是经历怎样的变化而来，就需要去查询历史的交易记录。这就体现出了区块链账本的核心含义，即当前的状态（余额）与一组决定该状态的交易，如下图所示：

在区块链中，上述状态代表系统中所有对象的当前状态集合，其往往是一个哈希值，而且当任意一个对象发生改变，该哈希值就会彻底改变。借助该哈希值，我们能非常直观的判断两个区块链节点是否处于相同的状态；而决定状态的交易指的其实就是物理上的区块链，链上存储了所有造成状态改变的交易，不同于世界状态，区块链只能追加而不能被修改。

▲ 如何存储账本?

如果从「数据类型」的角度出发，经过上面的分析我们其实可以看出区块数据其实是一种连续的且只支持末尾追加的结构，因此完全可以充分利用磁盘顺序写入的优势，连续地进行存储（本系列的后续文章将着重介绍：区块链连续型数据的存储）；而对于「状态数据」来说，由于会被频繁地写入和更新，因此从性能角度出发，状态数据更适合基于 LSM-tree 的存储引擎，如以太坊[1]、Hyperledger Fabric[2]等区块链项目均使用 Leveldb 作为默认的状态数据库。

区块链需要保证每一笔交易执行的原子性：一笔交易要么完全执行成功，要么完全执行失败，一旦执行过程中产生了错误，就需要回退掉这笔交易带来的所有状态修改。

以太坊引入了 StateDB 的概念来解决这个问题，即把某一笔交易执行过程中产生的修改缓存在内存数据库中，执行成功后再借助 Leveldb 原子写入的特性进行持久化。

▲ 问题分析

在区块链正常运行的情况下，上述对于账本的存储方式没有任何问题。然而我们知道，在以比特币[3]、以太坊为代表的公链中，出现短暂的链分叉是非常普遍的现象（如下图所示），节点可以根据预设的协议（如比特币的最长链原则）进行自动恢复；而即使在使用了拜占庭容错类算法的联盟链中，在算法层面不可能发生分叉，但仍然可能出现某个节点因为写入过程宕机、拜占庭行为、系统资源或硬件故障等原因造成执行失败或数据不一致的问题，从而也产生了分叉的现象，为了保证系统的鲁棒性和逻辑的完备性，在联盟链中也需要对分叉的状态进行数据恢复的机制。

下图表示整个区块链处于分叉的状态，五角星区块代表了上一次全网一致的状态，正三角形和倒三角形分别表示了当前两个不同的状态。

经过上面的介绍，我们若要进行数据的恢复，让整个系统恢复一致，需要那些异常节点：

1）回滚掉分叉点之后的区块和交易；

2）撤回这些交易对状态数据库造成的影响。

前者的实现可以非常简单，若我们通过 KV 数据库来存储区块和交易数据，那么我们可以根据对应区块号或者交易哈希来进行删除操作，若通过连续型数据库来进行追加式的存储，直接进行类似文件的截断即可；而对于后者，状态数据的键与区块号或交易并没有任何绑定关系，某笔交易造成某些键值的修改是散落在整个状态空间的，无法进行简单的回退。

在以太坊[1]StateDB 中引入了修改集（Journal）的结构，借助于修改集我们可以完成状态数据的回退。修改集是一个记录每次修改操作的数据结构。以以太坊为例，若 Jackson 和 Zoey 各自都有 10 个代币，在执行完一条“Jackson 给 Zoey 转账 5 个代币”后，会为这两个人各自生成一条修改集（如下图所示）。

在以太坊中，通过修改集的撤销（Undo）和重做（Redo）可以实现状态的回滚和重做，同样以上述转账为例，当这笔交易需要被回滚时，可以从修改集中得到“Jackson 在转账前的余额为 10，Bob 在转账前的余额为 10”这个信息，通过进行修改集的撤销从而恢复至交易前的状态；而若需要重放这笔交易时，无须重新使用虚拟机执行交易，而是通过修改集内的值进行赋值即可。

因此当我们要回滚某个区块时，我们可以取出该区块执行过程中产生的所有修改集，并且逐一撤销，并将得到的结果写入底层数据库，最终完成本次回滚。

上述流程逻辑上看没有任何问题，但在底层数据库的角度而言，这样的回滚方式则显得效率低下。

首先，我们在执行交易时，需要对交易的每次修改都生成对应的修改集，且这份修改集要随着区块一起持久化存储，以防日后可能出现的分叉事件，这显然是对执行与存储资源的一种消耗，尤其是在使用智能合约的场景，一笔合约交易可能会造成无数的对象修改，从而产生无数的修改集；
其次，对于 LSM-tree 来说，删除或者更新一条数据也是以插入新数据的方式完成的，只有当后台进行归并操作并发现某一轮归并出现了重复的 key 时，才会根据记录的新旧来删除或更新数据，因此 Undo 修改集的方式会加剧 LSM-tree 的存储空间放大问题。

▲ 如何优化

上节提到，无论是公链还是联盟链都需要完备的应对分叉的逻辑，但并非所有的区块都有被回滚的风险，如比特币中一个被确认一个小时或六个区块之后的区块几乎不存在被回滚的风险，如 PBFT 算法中经过 Checkpoint 确认的区块也不存在回滚的风险，以此作为出发点，我们可以参考 StateDB 的思想：只持久化那些不可能再被回滚的区块，而采用缓存的方式存储有回滚风险的区块。

在所有的 LSM-tree 的实现中，均将整棵树分成了内存和磁盘两部分（如下图）。如在 LevelDB 中拥有一个 MemTable 和一个 Immutable 作为写缓存来实现异步地磁盘写入；而 RocksDB 更为灵活，使得内存的 MemTable 数量可配，进一步提高写入速度。针对回滚的场景，我们可以对 MemTable 进行定向的优化。

MemTable 是以大小进行划分的，现在我们将其以 PBFT 算法中的的 Checkpoint 进行划分，即每个 MemTable 中保存的是若干个同属于一个 Checkpoint 的区块，而从 MemTable 写入磁盘的时机也不再是大小超过阈值，而是共识经过了 Checkpoint 检查，确定全网有 Quorum 个节点处于一致的状态，才通知存储模块进行持久化，在这种方式下，所有持久化的数据将不再有被回滚的可能，如下图所示的 LSM-tree 的内存部分包含了 3 个 Checkpoint 的 MemTable，它们将根据共识的状态被确定性地写入磁盘。值得一提的是，为了控制内存的占用，传统 LSM-tree 中的 MemTable 大小是可配的，一旦超过阈值即触发刷盘，而在我们的方案中，得益于 PBFT 算法 Watermark 的限制，内存占用也是受限制的。

在这种情况下如何进行状态数据的回滚呢？

在上图中，磁盘部分的数据是不可能再被回滚掉的，那么如果经过共识 Checkpoint 比对发现 12 号区块发生了分叉，我们如何回滚掉 12 号区块呢？在 Leveldb 中 MemTable 是一张跳表，我们无法从中剥离出 12 号区块相关的数据。此时就需要利用 Leveldb 中的预写日志了（Write Ahead Log，WAL），WAL 是为了防止数据写入内存后的宕机丢失而存在的，即数据一定是先被写入磁盘，才会写入内存。而 Leveldb 中的 WAL 是按照 MemTable 进行组织的，一个 MemTable 对应着一个 WAL，若我们可以以区块为划分来组织 WAL，就可以解决上述回滚掉 12 号区块的问题，即直接删除 11-12 这张 MemTable，随后将 11 号区块的 WAL 重新写入新的 MemTable，最后删除 12 号区块的 WAL。

经过上述的定向改造，回滚状态数据库几乎已经完全是内存操作了，且我们不再需要额外的修改集来完成回滚操作。

【索引数据】

▲ 什么是区块链索引？

交易（Transaction）是区块链中最基本也是最重要的数据结构。每笔交易中都封装了一次对区块链账本的操作，经过验证的合法交易将会被执行并保存在区块链中；而区块（Block）是存储交易及相关元数据的数据结构。交易由交易哈希唯一标识，而区块可由区块号或区块哈希唯一标识（不考虑分叉的情况）。

用户在发送交易后，需要向区块链查询交易的上链情况，若系统中只存储了世界状态数据，那么用户对历史数据的查询只能通过遍历所有区块实现，这样的代价和延迟显然是无法接受的。因此为了保证用户的使用体验，区块链往往会提供多种索引方式供用户查询使用，如通过索引快速的确认交易所在的区块，甚至可以更细粒度的直接定位到交易存储于这个区块内的哪个位置。

现阶段的区块链的基础结构较为简单，通常在底层采用单机 K-V 存储引擎，如 LevelDB，RocksDB 等进行数据的持久化存储。这也意味着上述索引数据与所有账本数据一起存储在了同一个数据存储引擎。但是联盟链或私有链通常作为企业级商用系统，整体数据量极大。随着数据量日益增大，数据库存储读写性能将会受到严重影响，区块链基础信息的查询（区块查询、交易查询）的性能也会急剧下降，导致用户查询延迟大幅增加，在延迟要求较高的场景下，这几乎是不可接受的。

我们以以太坊与 Hyperledger Fabric 为例，分析其索引信息的存储方式和大数据量下的索引数据解决方案。

▲ 实例分析之“以太坊”

以太坊[1]中提供了通过交易哈希查询交易、通过区块编号或者区块哈希查询区块的功能。分析源码可知，以太坊中维护了如下的映射关系：

(H) + Block Hash -> Block Number
(h) + Block Number + (n) -> Block Hash
(h) + Block Number + Block Hash -> Block Header
(b) + Block Number + Block Hash -> Block Body
(l) + Tx Hash -> Block Number

以通过交易哈希查询交易为例，根据以上映射关系，首先可通过交易哈希获取包含此交易的区块的编号，根据区块编号获取相应区块哈希，根据区块编号与区块哈希可获取区块体，从而获得此区块包含的所有交易列表，之后遍历交易列表，即可找到目标交易。

以太坊将所有数据都直接存入 LevelDB，其 freezer 会定时从 LevelDB 中将部分数据迁移至 freezerTable，但不包括区块哈希到区块编号的映射与交易哈希到区块编号的映射。从数据量上看，由于一个区块可能包含多笔交易，交易哈希到区块编号索引的数据量最为庞大。

▲ 实例分析之 Hyperledger Fabric

Hyperledger Fabric[2]同样提供了通过交易 ID 查询交易、通过区块编号或者区块哈希查询区块的功能。分析源码可知，Fabric 中维护了如下的映射关系：

(h) + Block Hash -> Block Loc
(n) + Block Number -> Block Loc
(t) + len(TxID) + TxID + Block Number + Tx Number -> TxIDIndexValue

根据以上映射关系，通过交易 ID 查询交易，可根据 txID 建立 iterator 直接查找到 TxIDIndexValue，之后即可根据此结构体获取交易；而通过区块哈希查询区块，可直接获取区块地址，之后可进一步查询获得区块。

Fabric 所维护的索引相较于以太坊要少一些，并且其单独使用了一个 LevelDB 进行索引数据的存储。

▲ 实例分析之问题分析

通过对以太坊和 Hyperledger Fabric 的分析与对比，我们可以发现，以太坊进行了定期的数据迁移以减少线上 LevelDB 数据量，而 Hyperledger Fabric 则进行了分库，使用单独的 LevelDB 进行索引数据的存储。

然而在实际的生产过程中我们可以发现，即便使用一个独立的 LevelDB 作为索引数据库，在数据量增大后，其读写性能的下降也依然是不可接受的。

我们知道，LevelDB 使用了 LSM-Tree 作为底层数据结构来组织数据库，其设计思想中最重要的一点即为，顺序操作的效率远高于随机操作。LSM-Tree 是一种多层级的数据结构，包含一层内存结构与多层磁盘结构，每一层磁盘结构的空间上限呈指数增长。LevelDB 中，数据的插入或更新将被缓存在内存中，当缓存达到预设上限，会将内存中的数据以有序的方式写入磁盘，形成一个 L0 层的 SSTable。随着写入操作的不断进行，L0 层的 SSTable 数量会持续上升，并且 SSTable 之间可能存在重叠部分。在 L0 层的 SSTable 数目或大小达到预设上限后，会进行多路归并操作，即 Compaction，如下图所示，对 L0 层的 SSTable 进行归并，可能还将与 L1 层的 SSTable 进行归并，通过多路归并生成新的 SSTable 文件存入 L1 层。从 L1 层开始，SSTable 之间将不存在重叠部分。

经过上文对以太坊与 Hyperledger Fabric 的分析，我们了解到目前区块链中索引信息的键主要有区块编号、区块哈希与交易哈希，而区块哈希和交易哈希是根据区块和交易的内容，通过哈希算法计算得到的无规则字符数组。且交易索引数据（如交易哈希到区块编号）占据的数据量最大。如果插入的数据 key 均为完全随机的字符数组，LevelDB 中每两层的 SSTable 都会存在大量的重叠。在数据量较大且读写频繁的情况下，Compaction 将会频繁发生，且读取索引数据时，可能也需要遍历 L0 层的所有 SSTable 与其余层的对应 SStable，效率同样极低。

▲如何优化

根据上述分析可以知道，引入索引数据后造成性能降低的关键在于完全随机化的键在插入 LSM-tree 后会造成大量的归并操作，使得读写效率急速下降。Hyperledger Fabric 使用独立的数据库存储索引数据，但性能依旧不理想。

或许我们可以更换一下思路。如果问题的关键在于键的随机性，是否可以改造键呢？区块哈希与交易哈希的主要目的在于对区块与哈希进行唯一标识，但我们是否可以对其进行重新设计，使其呈现出一定的顺序性，或者使其本身携带更多信息呢？

区块哈希是根据区块内容利用哈希算法计算得到的，而我们知道区块中必然携带有区块编号信息，如果我们将区块号直接嵌入区块哈希中，就能够将区块哈希到区块编号的索引信息直接编码进区块哈希中，完全去除这部分的索引存储开销。举例而言，如下图所示，区块哈希中的第一个字节为版本信息，后八个字节为区块号，后缀字节为区块内容哈希结果。版本信息的引入可以解决后续可能出现的兼容性问题，如当区块数量增长至超过八字节的时候，可以利用版本信息将区块字段延长至十六个字节。

而交易哈希同样是根据交易内容利用哈希算法计算得到的，而交易中携带有交易的生成时间戳。如下图所示，可以将交易的生成时间编码进入交易哈希，第一个字节为版本信息，后八个字节为交易携带的时间戳信息，后缀字节为交易哈希结果，使交易哈希趋近顺序性。

经过这样的编码，在最理想的情况下，LevelDB 内部的 SSTable 将如下图所示，不会有任何重叠的部分，从而避免 compaction，以实现性能的最优化。

然而在实际生产过程中，交易的打包、执行、存储是无法完全按照交易时间戳顺序进行的，因此实际中 Leveldb 的表现可能为下图所示，L0 层的 SSTable 会有一些重叠，不可避免会产生邻近 SStable 的 compaction，导致额外的性能开销，不过 compaction 不会在过多的 SSTable 之间发生，且基本只可能与 L1 层中最新的 SSTable 进行合并，影响范围就大大降低了。

另外在实际生产过程中我们可以发现，交易数据的访问频次与其时间呈现明显的关系性，新数据更可能成为热点数据，越旧的数据，读取的可能性越低，历史交易数据的访问频次极低。因此，我们可以考虑使用多个数据库存储交易索引数据，每个数据库负责存储某一特定时间范围内的交易索引信息，每一数据库记录该数据库中存储交易的时间戳范围，当最新的数据库存储的数据量达到预设上限，或达到预设的时间戳范围上限，建立新的数据库存储新数据。历史数据库可以在访问频率降低到预设阈值时关闭，在收到查询需求后再启动，减少数据库的资源消耗，更进一步也可以考虑将历史数据库迁移至文件存储。

在这样的设计下，活跃数据库的数据量稳定，索引数据的累计几乎不会导致索引数据读写性能下降。

【小结】

本文是《区块链 ≠ 分布式存储》的续篇，对概述中提到的区块链数据中的索引数据和账本数据的存储及定向优化做了介绍。索引数据库方面，我们从区块链中的数据查询需求出发，以以太坊与 Hyperledger Fabric 为例分析其索引数据的组织与存储方式，进一步分析索引数据膨胀后随机键对于 LevelDB 造成的性能损耗及其原因，并针对此情况提出一套解决方案；账本数据库方面，我们从区块回滚角度出发，基于现有方案的不足提出了新的解决方案。

随着区块链应用生态的日益丰富，区块链需要承载的数据量也将越来越庞大，如何在数据量上升的情况下保证数据库的读写性能是我们需要考虑的问题。根据具体的数据类型，我们不仅可以根据数据特性选取更合适的数据库，还可以对数据进行修饰，也可以对数据库进行定向的改造，来进一步地提高系统性能。

作者简介

吴志强、叶晨宇

趣链科技基础平台部区块链存储研究小组