秒懂比特元 | 比特元MVCCKVDB与传统区块链Merkle Tree数据存储方式对比

最早的区块链项目比特币，为解决分布式数据库的一致性验证问题，在“简化区块链支付验证”的过程中，引入了默克尔树（Merkle Tree）数据存储技术。

默克尔树架构图

默克尔树特点

1）默克尔树可以实现数据验证和同步的数据结构。一般由SHA-2和MD5等hash算法来实现。默克尔树环环相扣，hash算法几乎无法反向推导，通过实现只验证默克尔树根哈希的方式，有效的简化区块链数据验证。

2）主网应用于分布式系统中，如比特币、以太坊等区块链网络

3）Merkle Tree的叶子节点的在区块链网络中主要是交易生成的哈希值。

4）非叶子节点的value是根据它下面所有的叶子节点值，然后按照Hash算法计算而得出的。

默克尔树在区块链应用中的缺点

区块链在实际应用中往往需要面对数据的更新和插入，而默克尔树在执行更新操作时，效率往往比较低下。

图1和图2是默克尔树实现数据更新的一种形式：

图1

首先插入数据块0后(考虑数据块的位置)，Merkle Tree的结构是这样的：

图2

因为默克尔树中的所有的叶子节点都是相互关联的，我们在对数据更新的过程中往往是牵一发而动全身。由于默克尔树数据架构的特性，在区块链实际应用过程中，发送数据更新就面临数据结构的重构，使得公链执行效率十分地下，做很多无用功。

除了数据更改，在数据查询方面也效率低下：举个例子，一个20 层的默克尔树，查询一个叶子节点的数据需要进行 20 次读操作来完成，导致数据查询的效率仅为普通数据库的查询效率的 1/20，对于每秒能完成 10 万次读操作的系统，每秒仅能读取 5000 笔交易的数据，大幅限制了系统的读取性能。写数据时，同样要加载树型分支上的多个节点数据，并最终要在更新以后写入到磁盘，这里面的操作消耗也是比较大的。

比特元MVCCKVDB 的存储方式的优化解决方案

对于传统区块链默克尔树的数据架构存储数据的方式，在区块链领域发展中存在诸多限制。针对以上默克尔树在应用中存在的问题，比特元区块链率先创新实现了 MVCCKVDB（多版本 KV 数据存储），进行问题优化和解决。

比特元借鉴了数据库设计中的 MVCC 理念（Multi-Version Concurrency Control 多版本并发控制），设计了独创的 KVMVCC 的数据存储格式，用于改善 MAVL 或者默克尔树结构中存在的低效的问题，更好的满足区块链数据增长到一定规模后的保持较高的数据读写性能。

KVMVCC 的数据存储格式的思路如下：

Hash 计算： statehash=hash（prevstatehash，KVSet，height），包含了前一区块的状态 Hash 信息，本区块的状态数据 KVSet 信息，本区块的高度信息（也就是版本信息）。

有以下对应关系会被存储到每个节点的数据库中：

hash->height(version)

height(version)->hash

key:height(version)->value

lastest:key->value

在区块链数据验证方面：对于特定高度 height 的KVSet ，可以根据前一区块的hash值 prevstatehash、KVSet、height 进行 Hash 运算，如果 hash 值相符，则数据未被篡改，否则，数据被改动或者数据有误（高度有误，或者 KVSet 数据有误）。

对于最新版本数据的维护方面：特别的，当对于最新区块的 key、value 值进行存储时，同时保留（新增 key）或者更新（已经有历史版本的 key）key:latest->value 的映射关系到本地 key-value 数据库中存储。当需要获得最新的批量数据时，可以根据 latest 前缀（可以自定义）来批量查询最新数据，实现和传统数据库一样的执行效率。

在数据查询方面：根据 statehash 可以查找到对应的 height（version），根据 height 可以查找到对应高度时，具体 key 值对应的 value 值。由于通常的 key-value 数据库可以很好的支持前缀匹配查询，查询效率会比较高，远高于默克尔树存储结构的查询。

比特元官网：www.bityuan.com

比特元开源地址：https://github.com/33cn/chain33

文章参考：https://blog.csdn.net/wo541075754/article/details/54632929