用分治思路解决区块链并行化交易问题

当前公有链的痛点之一就是交易的性能瓶颈，这也是当前区块链的研发热点。aelf 区块链网络使用并行化方案突破这一问题，达到了近 1.5 万 tps，也是测试网运行期间开发者关注的重点问题。在本文里他们介绍了该方面的思路。

算法目标是设计一个智能合约并发执行的策略，理想的应用情景是可以在集群环境中获得较好的性能。

目前有两种思路来做到这一点：（1）资源占用隔离；（2）数据库并发控制手段

资源占用隔离的思路主要是先检测到交易会占用什么资源，然后依据这些资源占用的情况，将占用不同资源的交易分开并行执行。一般情况下，资源占用的检测需要以静态分析的形式，在执行智能合约之前进行。

与此相反的是，数据库并发控制手段则会在合约运行的时候来解决并发访问冲突的问题。它使用调度器来接受并处理来自不同合约的数据库请求。当一个新的请求到达时，为了保证合约执行的事务性，调度器会根据“该请求是否与正在执行的其他请求互相冲突”来决定是否要延迟该请求。有时，如果某交易的数据操作违背了事务性的需求，调度器甚至会中止并重启该交易（事务）来修正该问题。

基于要将情景扩展到集群环境的需求，我们选择了资源占用隔离的策略。数据库并发控制手段需要一个中心的调度器来决定请求是否冲突，也就意味着如果我们在不同的集群机器上运行合约，就会在执行之中引入大量的网络开销（因为所有请求都要发送到该调度器），我们很难接受这样大的执行开销。

然而，这两种思路并不是互斥的，我们可以在资源占用隔离之后的交易分组（组内都是互相冲突的交易）内部应用针对智能合约设计的数据库并发控制手段^{[1] [2]} 来进一步增大系统的整体并发度。

我们设计的资源占用隔离策略的步骤如下所示：

步骤 1: 交易分组之间的并行

如图 1 所示，我们根据交易可能访问的资源集合，将交易按照冲突关系分入不同组中，其中每组内部都是互相冲突的交易，而组之间没有任何冲突。如此便可以进行分组之间的完全并行执行而不用担心 race condition 等并发访问错误。

图 1: 将交易进行分组使其可以并行执行

步骤 2: 组内并发执行

注：该部分未进入实际设计，这里仅提供思路

目前我们选择顺序执行一个冲突的交易分组。

区块链中的交易必须事务性、确定性地执行，因此我们必须使用特殊化的并发控制手段来保证正确地执行交易。之所以我们可以结合两种思路的方式提高系统并行度，是来自于“冲突的交易分组最好在同一台机器上执行以避免网络开销”这个观察的。因此，我们就可以只以本地线程间通信的代价引入并发控制手段，这样的开销要比之前提到的集群中 host 之间的网络通信开销小得多。

2.1 将数据分为 3 类

为了区分不同的数据访问的情形，我们将合约的状态数据分为 3 种类型：

1. 只读的账户间共享数据

   定义：指在 1 个 block 执行期间，不会改变的数据

   例子：比如“当前区块高度”，“前一个区块的哈希”或者其他用户自定义的常数

2. 读写的账户间共享数据

   定义：指在 1 个 block 执行期间，可能被多个账户同时读、写的数据

   例子比如在一个投票合约中，“每个候选者的票数”这个状态可能会被多个账户同时修改（因为这些账户都给同一个候选者投了票）

3. 账户相关的数据

   定义：指只会被某个特定账户读、写的数据

   一般情况下都是一个 Map，其中

   （1） 账户地址是 key，状态值是 value

   （2） 一个账户只能访问该 Map 中自己 key 的状态值

   例子：比如一个代币合约，账户的余额的 Map 就是这样的数据。Alice 给 Bob 转账的交易永远不会访问该 Map 中 John 或者其他人的数据。

如此设计的原因是很多智能合约的逻辑都是只和账户相关的，即很多智能合约的方法只会访问账户相关的数据。在这种情况下，“与 Alice、Bob 相关的交易”是可以和“与 Helen 和 Chad 相关的交易”并行执行的（即使它们访问同一个合约的同一个 Map），因为这两个交易访问的是完全不同的数据，互相之间并没有冲突。

在下面的例子中，我们用“a_i”标识读写的账户间共享数据，用“m_i”标识一个账户相关数据。

2.2 合约方法的元数据（Function’s Metadata）

为了获得某交易可能占用的资源集合，我们需要知道每个合约的每个方法分别会占用什么资源。我们使用“合约方法的元数据”来满足这个需求。一个元数据代表着一个合约方法可能会访问的资源（即合约状态数据）的集合。

元数据包括“调用集合”（calling set）和“资源集合”（resource set）。

• 函数调用集合指每个方法将会调用的“其他的合约方法的集合”。
• 资源集合指该方法会访问的合约状态的集合（目前我们不区分读、写操作）。

我们使用 [合约地址 + 资源名] 的方式来命名资源集合，该名可以看作是该资源（可能是一个变量，也可能是一个资源的集合，如 map、array 等）的唯一 ID。例如，某地址为 0x123 的代币合约有一个 Map 为“BalanceOf”，则其命名方式为“0x123.BalanceOf”。

备注：合约方法的元数据应当是在合约在链上被创建时由静态分析产生，并被持久化到数据库中以待取用。

2.3 如何将交易分组

我们可以根据以下三步对一个区块内的交易进行分组：

1. 根据方法元数据来提取该交易会占用的资源集合
2. 生成一个“资源依赖图”的无向图，在该图中，资源作为结点，每当有一个交易同时访问 2 个资源时，这两个资源的结点之间就会有一条边。
3. 根据资源依赖图将交易分到不同组中，其中组内的交易所访问资源在资源依赖图中处于同一个连通分量。

策略可以用下面的结构表示：

元数据静态分析生成，发现合约方法的占用资源的集合

【静态地，当合约部署到链上时进行】

	|
	|------ 依据元数据分组交易 
		【在执行交易前进行】
		|
		|------ 组内施行并发控制手段（待定）

2.3.1 依据资源集合进行交易分组

基本思路

假设我们有交易“t_1 [Alice, Bob]  {m_1}” and “t_2 [Chad, Helen] {m_1}”，其中 m_1 是账户相关数据。然后交易 t_1 会访问 m_1.Alice 和 m_1.Bob 两个资源，交易 t_2 会访问 m_1.Chad 和 m_1.Helen。因此我们可以并行运行这两个交易，因为它们之间没有资源冲突。

对于访问同一个读写账户共享数据 a_1 的交易，它们会被直接视作冲突的交易并被分入一组，因为不论这些交易的相关账户是什么，它们都可能访问 a_1 这个资源。

分组算法

步骤 1: 针对每一个交易，按照如下规则标记其资源（假设交易 t_i 的相关账户是 Alice 和 Bob）：

1. 如果 t_i 可能访问账户相关资源 m_j，则添加资源”m_j.Alice”和“m_j.Bob”到 t_i 的资源集合中
2. 如果 t_i 可能访问读写账户间共享数据 a_k，则添加资源“a_k”到资源集合中。
3. 如果 t_i 可能访问只读账户间共享数据，跳过。

步骤 1 的示例如图 2 所示:

图 2: 标记账号相关资源

步骤 2: 根据标记的账号相关的资源，分组交易。

正如上面有关资源依赖图的描述，如果我们有一个无向图，其中每个顶点是资源，只要某两个资源被同一个交易访问，这两个资源的顶点之间就有一条边。则对于交易来说，其访问资源属于同一个连通分量的应该被分入同一组中。因此我们使用并查集，用下面 2 步来解决这个问题：

1. 在遍历每个交易的资源集合时，建立冲突交易的资源的超集（superset）。
2. 对每个交易，如果该交易的资源在并查集第 i 个超集内，则该交易应该在第 i 个交易分组中。

图 3 展示了步骤 2 的一个示例。7 个交易根据生成的资源依赖图，被分入 3 个组中。从而不同组的交易不会访问同一个资源。

图 3: 根据账号相关的资源对交易进行分组

2.4 难点

1. 如何在当前合约调用的实现下，实现资源集合的静态分析？
2. 如何让合约开发者可以尽可能地正确地标记 metadata。（编写并发程序很容易出错，而且也很难发现问题、调试。考虑实现一个静态代码分析工具，来尽可能减少开发者出错的空间）。
3. 如何优化分组算法的粒度，保证在一个区块内交易数量极多时，分组占用的时间相对合约执行来说忽略不计。

参考文献

[1] Dickerson, Thomas, et al. "Adding concurrency to smart contracts." Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, 2017.

[2] Zhang, An, and Kunlong Zhang. "Enabling Concurrency on Smart Contracts Using Multiversion Ordering." Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint International Conference on Web and Big Data. Springer, Cham, 2018.

作者介绍

戎朋，aelf 技术副总裁。具有十年以上的互联网研发及管理经验。曾任阿博茨科技技术负责人，负责中国首个基于区块链的互助平台同心互助，在数据挖掘、数据可视化领域有丰富经验；曾任海豚浏览器服务端研发主管。

感谢徐川对本文的审校。