写点什么

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

  • 2018-08-16
  • 本文字数:4672 字

    阅读完需:约 15 分钟

当前公有链的痛点之一就是交易的性能瓶颈,这也是当前区块链的研发热点。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 技术副总裁。具有十年以上的互联网研发及管理经验。曾任阿博茨科技技术负责人,负责中国首个基于区块链的互助平台同心互助,在数据挖掘、数据可视化领域有丰富经验;曾任海豚浏览器服务端研发主管。

感谢徐川对本文的审校。

2018-08-16 18:234679

评论 1 条评论

发布
暂无评论
发现更多内容

线上JAVA应用平稳运行一段时间后出现JVM崩溃问题 | 京东云技术团队

京东科技开发者

Java 定时任务 JVM 企业号11月PK榜

Golang面试题从浅入深高频必刷「2023版」

王中阳Go

Go golang 面试题 大厂面经 最新面试题

安全好用的远程协同运维软件重点推荐-行云管家

行云管家

远程运维 运维软件 远程系统 远程协同 协同运维软件

解决Lightroom无法使用修改照片的问题

Rose

Lightroom Classic 2022 Mac破解软件 Lightroom无法使用 LR2024 Mac中文

极致性能优化:前端SSR渲染利器Qwik.js | 京东云技术团队

京东科技开发者

性能优化 前端 前端性能 企业号11月PK榜 Qwik.js

Office2019 for Mac(办公套件全家桶) v16.78正式激活版

mac

办公软件 苹果mac Windows软件 office 2019

专业fcpx视频剪辑推荐 Final Cut Pro最新激活中文版

mac大玩家j

Mac软件 fcpx插件 视频编辑器

火山引擎云原生存储加速实践

字节跳动云原生计算

大数据 云原生 存储

即时通讯技术文集(第22期):IM安全相关文章(Part1) [共13篇]

JackJiang

网络编程 即时通讯 IM

Mac效率办公软件 Alfred 5中文完美破解版 兼容M1

iMac小白

Alfred 5下载 Alfred 5 Mac Alfred 5破解版

UUID意想不到的block

FunTester

云工作流 CloudFlow 重磅发布,流程式开发让云上应用构建更简单

Serverless Devs

阿里云 Serverless 函数计算FC

专业终端SSH工具 SecureCRT注册码正式版

胖墩儿不胖y

Mac软件 终端SSH仿真工具 终端仿真器

Mac日程管理软件Fantastical 中文破解版 让日程管理更加便捷!

Rose

日程管理App Fantastical Mac中文版 Fantastical下载 Mac日历软件

架构实战营 - 模块四作业

王朝阳

架构实战营

ps2021一键换天空教程

Rose

ps2021破解版 一键换天空 ps2021下载 ps2021天空替换 Photoshop Mac破解版

endnote x9怎么和word关联?Word中用EndNote X9教程

Rose

Word 2021 许可证 endnote x9 文献写作管理软件

调用API接口获取淘宝商品评论:方法与实战

Noah

企业制作网站时为何香港云服务器成为首选?

一只扑棱蛾子

香港云服务器

微前端无界机制浅析 | 京东物流技术团队

京东科技开发者

前端 源码剖析 微前端 无界 企业号11月PK榜

什么是大模型?一文读懂大模型的基本概念

九章云极DataCanvas

Mac窗口管理软件合集|告别混乱屏幕,一切井井有条

Rose

mac窗口管理软件 Mac破解软件 苹果电脑分屏软件 Mac软件下载站

PhotoFoundry for Mac(专业的照片滤镜编辑软件)v1.2激活版

iMac小白

PhotoFoundry下载 PhotoFoundry破解版 PhotoFoundrymac

用友全球司库十问(六)|新一代票据能力如何实现赋能企业票据管理?

用友BIP

全球司库 票据管理

如何使用 Loadgen 来简化 HTTP API 请求的集成测试

极限实验室

集成测试 loadgen 极限科技

商用解决方案助力产业链实现自循环 OpenHarmony技术大会硬件(南向)生态分论坛圆满落幕

科技热闻

助力工业数字化!TDengine 与恩菲 MIM+ 工业互联网平台实现兼容性互认

TDengine

tdengine 时序数据库

如何为Affinity Publisher或Designer创建条形码?

Rose

Affinity Publisher 条形码设计

对话在行人|合众思壮:基于用友BIP重塑业务应用,推进业财融合

用友BIP

对话在行人 数智化领先实践

用分治思路解决区块链并行化交易问题_语言 & 开发_戎朋_InfoQ精选文章