区块链遇上分布式数据库

直到比特币诞生十年之后的今天，我们对区块链技术的认识越来越朝着“这不就是一个分布式数据库”的方向发展。事实也是如此，区块链从诞生之初只服务于加密货币，到现在随着智能合约、共识技术的发展，区块链也慢慢被用来服务于通用的数据管理系统。作为这类系统的元老，分布式数据库已经有几十年的发展历史，区块链技术作为后起之秀免不了要向前辈借鉴发展经验，“长大后我就成了你”也就不足为奇了。然而，区块链和分布式数据库两者还是有一些微妙的差异，如何分清这些差异有助于我们深刻理解这两项技术，也有助于我们掌握新技术的发展方向。本文以数据库领域的顶级会议 SIGMOD 今年最新的一篇文章 [1] 为框架，讨论一下区块链和分布式数据库两项技术的异同点，以及在这十年里两者的融合。

区块链

区块链最初只是用来服务加密货币，例如比特币和由此衍生的其它加密货币。从数据结构的角度看，区块链是由区块哈希值链接（除了初始区块以外，每个区块都保存了父区块的哈希值）起来的一串区块，每个区块保存了一部分交易。这一连串的区块就构成了一个交易账本，记录了从第一笔原始交易开始的全部交易历史。从分布式系统的角度来看，区块链解决了公开网络中的拜占庭（存在恶意节点）共识问题。这部分的讨论可以参考我之前的文章：区块链与分布式系统​

在 2014 年，以太坊的出现给区块链带来了智能合约。智能合约的出现，使得区块链上的应用不仅局限于加密货币，还可以支持图灵完全（Turing-complete）的应用计算，这使得区块链逐渐朝着一种通用的去中心化计算平台发展。

区块链技术的发展也使得另一项比区块链的出现还要早 10 年的研究——拜占庭共识焕发了第二春。虽然两者都关注在恶意节点存在的情况下的共识问题，但传统的以PBFT（Practical Byzantine fault-tolerance）为首的这类研究只局限在封闭的网络中，即节点的身份已知，加入和离开都需要权限控制机制。后世为了将这两项技术的研究进行整合和区分，将以比特币、以太坊为首的区块链称为 permissionless blockchain（也就是我们俗称的公链），而将基于 PBFT 或其衍生的 BFT 协议的区块链称为 permissioned blockchain（俗称联盟链）。联盟链由于需要很强的访问控制机制，因此更适用于企业级的应用场景，例如银行、证券机构等。从论文中的下图可以看出公链、联盟链和传统的分布式数据库在安全性和性能上的取舍。公链具有更高的安全性（对节点身份没有要求），但性能较差。分布式数据库是另一个极端，安全假设较强（存在可信中心），因而共识性能较高。联盟链则处于两者之间，节点之间可以相互不信任，但安全假设要求节点身份已知，且至少有一部分节点是正常的，性能相比传统分布式数据库稍差。

分布式数据库

数据库技术作为计算机领域的一项基础技术已经渡过了数十年的春秋。随着人们对大数据处理的需求不断增大，数据库也逐渐向分布式技术发展，我们目前生活中经常接触到的各种互联网应用的背后都离不开大规模的分布式数据库的支持。在这个趋势下，传统的关系数据库无法满足可扩展性的需求，于是新的数据模型例如 NoSQL 和 NewSQL 逐渐涌现了出来。

作为一种更加灵活的数据模型，NoSQL 更倾向于提供可用性，而不是一致性。采用 NoSQL 的数据库可以选择多种不同的一致性等级，不同的等级会导致系统表现不同的性能。用户可以根据实际的使用场景在性能和一致性上进行取舍。NoSQL 的这种设计虽然更加灵活，但加大了上层应用的复杂性，因此一种介于关系数据库与 NoSQL 之间的设计，NewSQL 应运而生。NewSQL 既保留了关系数据库的数据模型以及对 ACID 语义的支持，同时也维持了一定的可扩展性。

区块链 vs. 分布式数据库

区块链和分布式数据库其实并没有本质的不同。更进一步说，我认为区块链只是扩展了分布式数据库的应用场景，并且采用了一系列已有的技术解决了这个新的应用场景所带来的挑战。这个新的应用场景就是跨多个信任域的节点如何有效管理数据。也就是说，在传统的分布式数据库中，所有节点都是由中心化的 coordinator 来管理，节点之间可以毫无保留地互相信任，分布式数据库只需要考虑节点宕机问题。然而当这个 coordinator 缺失，或者参与者由不同的 coordinator 管理的时候，数据库所要考虑的问题就提高了一个难度，因为节点不止可能宕机，还有可能表现各种各样的拜占庭行为。

为了应对新场景带来的挑战，区块链不得不采用一些更加保守的技术（损失了一部分性能），从论文中的下图我们可以略窥一斑。接下来我们从 Replication、Concurrency、Storage、Sharding 这四个维度来看区块链跟传统分布式数据库相比在技术选择上的不同。

Replication

对数据进行复制（replication）是防止节点失效影响的一种最直接和有效的手段。然而 replication 带来的一个严重的问题就是数据一致性问题。解决一致性问题的一个非常经典方式就是状态复制机（state machine replication，SMR），即所有节点起始于相同的状态，维护相同的交易日志，于是只要每个节点按照相同的顺序执行每一笔交易，则每个节点的状态也应该是相同的。

实现 SMR 的一个关键技术就是共识算法，保证在一定的网络和容错假设下节点之间的数据的一致性和活性。针对不同的网络和容错假设适用的共识算法也不同。在传统的分布式数据库中，只需要容忍节点宕机，主要采用以 Raft、Paxos 等经典共识算法。然而在区块链中，由于要容忍节点的拜占庭行为，因此不得不采用代价更高的 PBFT、PoW 等共识算法。

除了共识算法的不同，区块链和分布式数据库还在 replication 的级别上存在差异，如下图所示。分布式数据库（b）由于可以依赖一个中心化的 coordinator，因此在做复制之前可以首先由 coordinator 将交易分成更细粒度的指令再分发给不同的节点做复制。交易本身并不需要复制到所有节点，负责执行指令的节点也不知道原交易的执行逻辑。然而区块链（a）没有可信赖的中心，于是一般在交易级别做复制，之后再由每个节点执行交易中所包含的所有指令。

Concurrency

为了提高系统的吞吐量，将多个交易或指令并行处理是在数据库领域是非常重要的技术之一。由于不同交易可能在同一个数据对象之上进行操作，因此如何在并行处理的同时保证执行的正确性也就是并行控制（concurrency control）一直是数据库领域的一个研究热点。 并行控制的目标就是使得交易的执行实现一定的“隔离性（isolation）”，也就是说让交易在并行执行的时候好像感受不到其它交易的存在。在性能和正确性之间做取舍可以将数据库分成不同的隔离级别，由低到高分别为 Read uncommitted 、Read committed 、Repeatable read 、Serializable，对应的性能也逐渐下降。产品级别的数据库一般都提供多种隔离级别。

在现有的大部分区块链中，交易仍然是串行执行的。区块链对并行的支持并不好，其中一个原因在于在现有的一些区块链中，执行层还不是瓶颈。例如，在比特币中，一个区块的执行时间在毫秒级，相比于 10 分钟的区块产生时间，执行部分几乎可以忽略不计。除此之外，在一些支持智能合约的区块链中，交易之间往往共享合约的状态，为了保证交易执行结果的确定性（deterministic），串行执行往往是最简单和保险的方式。

Storage

我们都知道区块链是一个 append-only 的账本，包含了从创世区块开始到最新的区块中包含的全部交易历史，这也就导致了很多主流的区块链的存储量动辄就要上百 GB。为了支持真实性验证，区块链一般采用类似 Merkle Tree 的数据结构存储区块中的交易。例如，以太坊采用了 Merkle Patricia Trie（MPT）存储所有账户的状态。然而在大部分的数据库中，除非是有特殊的 provenance 的需求，用户一般只能访问最新的数据。历史数据会以 log 的形式保存一段时间供节点失效恢复的时候使用，但一般会被定期清理掉以节省存储空间。另一方面，由于分布式数据库更在乎性能，因此在建立索引的时候会根据硬件的性质进行特殊的优化。例如，数据在硬盘中一般会以 B+ 树的数据结构存储，而在内存中则用对多核并行和缓存更加友好的 FAST 或 PSL 等结构。

Sharding

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

然而在区块链中引入分片并不简单，主要有两个挑战：第一，如何进行分片？我们都知道区块链需要容忍拜占庭错误，而这依赖于一个大前提，即网络中一定比例的节点是诚实的。例如，在 PoW 中要求总算力的 50% 是诚实的，而 PBFT 则要求超过 2/3 的节点数是诚实的。在将区块链的网络进行分片时就需要保证每个分片的安全假设都是成立的，一旦有一个 shard 的安全前提不成立，那么整个系统的安全性都无法保证。然而由于在分片的时候一般都是随机将节点分配到不同的 shard，这就要求总结点数规模要足够大，而且 shard 的个数不能过多，这样才能保证每个 shard 中有足够数量的节点保证安全前提能够成立。

第二个挑战就是如何保证 shard 之间的原子性，即一笔交易要么在所有 shard 都 commit，要么在所有 shard 都 abort。在传统的分布式数据库中，这一原子性一般由两阶段提交（2 Phase Commit，2PC）协议来保证，其中需要依赖一个中心化的 coordinator 来执行。然而在区块链中，由于没有中心化的 coordinator 存在，则需要引入一些外部的 BFT 协议来统筹 cross-shard 的交易。例如以太坊 2.0中的 Casper 协议 [2]。

走向融合

随着区块链技术逐渐走向落地，无论是工业界还是学术界都在致力于提高区块链的性能，其中借鉴分布式数据库中成熟的技术则是最简单和保险的做法。例如，BlockchainDB [3] 和 FalconDB [4] 就在区块链系统的基础上引入数据库的 feature，使得互不信任的多方可以共同参与维护一个可验证的数据库。

另一方面，区块链所具备的一些安全特性也受到了一些数据库设计者的青睐，使得一些新型的更加追求安全性的数据库也具备了区块链的基因。例如，Blockchain Relational Database [5] 就是在 PostgreSQL 的基础上引入区块链中所具备的去中心化和可追溯的特性所设计的新型关系数据库。

参考文献

[1] Blockchains vs. Distributed Databases: Dichotomy and Fusion: Blockchains vs. Distributed Databases: Dichotomy and Fusion

[2] Casper: ethereum/casper

[3] BlockchainDB - A Shared Database on Blockchains: http://www.vldb.org/pvldb/vol12/p1597-el-hindi.pdf

[4] FalconDB: Blockchain-based Collaborative Database: http://www.cs.utah.edu/~lifeifei/papers/falcondb.pdf

[5] Blockchain Meets Database: Design and Implementation of a Blockchain Relational Database: http://www.vldb.org/pvldb/vol12/p1539-nathan.pdf

本文首发于：https://zhuanlan.zhihu.com/p/372787705