数据库视角下的区块链技术

1 overview

本文关注数据库视角下的区块链技术。

首先，我们来看一下数据库和区块链的定义。数据库是数据管理的产物，而数据管理则是数据库的核心任务。当数据规模变得很大、用户变得更多时，单一节点的数据库满足不了用户的需求。分布式数据库便应运而生，目的是存储更多的数据，提供更大的吞吐量。区块链的本质特征是去中心化。区块链技术是一种以密码学技术为基础、以去中心化或多中心化的方式对数据进行存储和管理，从而在不依赖可信中心机构的情况下提供“可信数据”的技术。

从定义上来看，分布式数据库和区块链有相同之处。两者均涉及到数据存储和管理，并涉及到多个节点。在这个意义上，区块链满足分布式数据库的定义，换句话说，区块链是一种分布式数据库。

当然，两者也有明显的区别。一般的分布式数据库存在一个可信中心，要求多个节点协调工作提供更大的吞吐量。区块链的本质特征是去中心化。在不依赖可信中心机构的情况下，区块链要能够提供“可信数据”。总结成一句话，分布式数据库关注性能，而区块链关注的是安全。

从发展趋势看，要想得到更加广泛应用，区块链技术需要借鉴分布式数据库多年来积累的技术。总之，区块链与分布式数据库有很强的关联性。在本文，我们将从数据库的角度来看待区块链。

2 data management

提起数据库，我首先想到的是关系数据库。关系数据库应该是目前使用最广泛的一种数据库之一，它使用了关系模型。在关系模型下，数据存储在了一张张表中，对进行数据的操作，也就是对表进行操作。

在本质上，区块链也是一种特殊的分布式数据库。在区块链中，数据是怎样被组织存储的？在本节，我们通过介绍Hash Chain和Merkle Tree这两个数据结构来回答这个问题。

2.1 Hash Chain

Hash Chain的一个显著特征是，链接列表中的指针不仅包括下一个旧块的标识符，还包括该旧块的哈希。当添加一个块到Hash Chain中时，需要上一个块的地址和上一个块的哈希写入到当前的块中。不难发现，在Hash Chain中，如果任一块的哈希值发生变化，则其后所有节点的哈希值都会变化。

顾名思义，区块链是数据块的链接列表。在区块链中，数据以固定大小的块(block)作为基本储存的单元，一个block中存储多条数据。通过使用Hash Chain，所有的block被组织成一条链。

为什么区块链要使用Hash Chain？在Hash Chain中，如果一个block中的数据被更改，则其后所有节点的哈希值都会变化，这也意味着其后所有节点的数据都要被重写，这就保证了区块链中的数据不会被篡改。因此，区块链是一个 append-only 的数据库。

2.2 Merkle Tree

Merkle Tree由一个根节点（root）、一组中间节点和一组叶节点（leaf）组成。叶节点（leaf）包含存储数据，中间节点是它的两个孩子节点内容的哈希值，根节点也是由它的两个子节点内容的哈希值组成。Merkle Tree也称哈希树。

类似于Hash Chain，Merkle Tree具备防篡改的特性。如果某一个叶子节点中的数据被更改，则一定会传导到根节点，即根节点中的哈希值会改变。

Merkle Tree的效率高于Hash Chain。因为Merkle Tree使用了树形结构, 其查询和更改的时间复杂度为 $O (l o g (n))$ 。

区块链中使用Merkle Tree，主要是为了提升系统的运行效率和可扩展性，使得区块头只需包含根哈希值而不必封装所有底层数据。如下图，比特币系统使用了Hash Chain和Merkle Tree相结合的数据结构。在比特币的系统中，每个block中的数据均使用一个Merkle Tree来维护，而Hash Chain中仅包含Block header。block header保存着对应的Merkle Tree的根哈希值、上一个block的地址和上一个block对应的block header哈希。

3 Sharding

在分布式数据库中，分片技术是提高可扩展性的一项关键技术。通过将数据分散的交给不同节点处理，分布式系统可以达到 scale-out 的效果。也就是说，随着用户和数据量的不断增多，系统整体的吞吐量也随之接近线性增长，分片本身带来的 overhead 几乎可以忽略不计。

然而，区块链中很难应用分片技术。在区块链中，每一个节点均是不可信的。如果在区块链中应用分片技术，那么整个系统的安全性都无法得到保证，也就无从谈起去中心化了。

4 replication

在分布式系统中，至少一个结点出故障的概率远大于单结点系统。因此，分布式系统要求同一数据至少在2个结点有复本，这就涉及到了数据复制，比如，主从数据复制。

第三节中说到，区块链没有应用分片技术。换句话说，每一个节点保存着所有数据的副本。当新的block存入区块链时，每个节点运行泛洪算法，将新写入的block在网络中广播。每个节点对接收到的block检查，以查看block是否已经接收过，如果未接收过，则将block放入本地缓存，并将其转发给其所有的peer节点。

5 transaction

几乎所有人都会将数据库和事务联系起来。数据库系统要保证事务的ACID性质。上文中提到，区块链是一个 append-only 的数据库。在区块链中，一个事务也就是一笔交易。每隔一段时间，区块链系统会根据共识策略选择若干交易，并将这些交易放到一个block中。然后，通过网络广播，将block写入所有节点的持久化存储中。这个过程满足事务的ACID性质。

6 consensus

在传统的分布式数据库中，存在一个可信中心。分布式数据库只需要容忍节点宕机，主要采用 Raft、Paxos 等经典共识算法。然而，区块链要容忍节点的拜占庭行为，因此不得不采用代价更高的 PBFT、PoW 等共识算法。本节介绍一些常用的共识算法。

6.1 Paxos

简介

Paxos 协议的流程较为复杂，但其基本思想却不难理解，类似于人类社会的投票过程。在 Paxos 协议中，有一组完全对等的参与节点，这组节点各自就某一事件做出决议，如果某个决议获得了超过半数节点的同意则生效。只要有超过一半的节点正常，Paxos 协议就可以工作，能很好对抗宕机、网络分化等异常情况。
Advantages
1. 有坚实的理论研究证明，并为其他非拜占庭共识算法提供了理论基础。
2. 与PBFT等区块链常用共识算法相比，吞吐量更大，即局域网下的吞吐量超过10000 TPS。
Disadvantages
1. 仅有极少数聪明人可以理解这个协议，难以代码实现。
2. 无法在公共网络环境中高效运行，仅适用于节点数较少的场景，如分布式数据库系统。

6.2 Raft

简介

Raft协议是对Paxos协议的改进，它的首要目标就是容易理解。当然，Raft增强了可理解性，在性能、可靠性、可用性方面是不弱于于Paxos。
Advantages
1. 易于理解，且易于代码实现。
2. 与PBFT等区块链常用共识算法相比，吞吐量更大，即局域网下的吞吐量超过10000 TPS。
Disadvantages
1. 无法在公共网络环境中高效运行，仅适用于节点数较少的场景，如分布式数据库系统。

6.3 PoW

简介

POW协议达成共识的依据是工作量。在比特币的系统中，工作量就是计算的哈希的数量。
Advantages
1. 对参与共识节点的数量没有限制，系统中节点可以动态加入/离开，可以适应公有链的开放环境。
2. 安全性。可以容忍大量的恶意节点，任何人都需要获得网络一半以上的算力才可以实现恶意攻击。
Disadvantages
1. 浪费资源。在共识过程中，计算机做了大量的无意义的哈希运算。
2. 效率低下。交易确认缓慢，且存在撤销的可能。

6.4 PBFT

简介

Raft协议是对Paxos协议的改进，它的首要目标就是容易理解。当然，Raft增强了可理解性，在性能、可靠性、可用性方面不弱于于Paxos。
Advantages
1. 高效。在PBFT算法中发一个交易是无需等待确认的，如果一个区块通过PBFT算法被系统认可，那么这个区块就会是最终区块，不会被撤销。因为各个节点达成共识是在同一时刻决定的，也就意味着用PBFT维护的区块链不容易出现分叉，所以也就不用等待确认以保证当前区块所在的链是最长链。
2. 节能。PBFT 算法的共识过程也不需要像 PoW 那样需要耗费大量电能。
Disadvantages
1. 不适用于节点数量过大的区块链，扩展性差。PBFT算法的计算效率依赖于参与协议的节点数量，由于每个副本节点都需要和其它节点进行P2P的共识同步，因此随着节点的增多，性能会下降的很快。
2. 系统中节点是固定的，无法应对公有链的开放环境，只适用于联盟链或私有链环境。

7 concurrency

在数据库领域，为了提高系统的吞吐量，将多个交易或指令并行处理是是非常重要的技术之一。然而，在区块链中，交易仍然是串行执行的。区块链对并行的支持并不好，原因在于在现有的一些区块链中，执行层还不是性能的瓶颈。例如，在比特币中，一个区块的执行时间在毫秒级，相比于 10 分钟的区块产生时间，执行部分几乎可以忽略不计。除此之外，在一些支持智能合约的区块链中，交易之间往往共享合约的状态，为了保证交易执行结果的确定性，串行执行往往是最简单和保险的方式。