基于一致性哈希算法的区块链优化模型

苏畅

摘要：近些年来，区块链技术凭借着其去中心化的优势实现了安全的点对点交易、协调与协作。然而随之而来的也有区块链运作效率低下，浪费大量时间和空间的问题。本文拟通过一致性哈希算法（Consistent Hashing）对区块链运行中出现的问题进行了研究和优化，较好地解决了区块链存储空间问题、重复验证问题和数据分层管理问题。有效节约了网络存储资源。从而在保证区块链运转安全，可靠之外提供了更加高效的运行模型。

关键词：区块链技术;运作效率;一致性哈希算法;区块链存储

中图分类号：TP311        文献标识码：A

文章编号：1009-3044（2019）14-0163-03

1 研究背景

狭义讲，区块链是一种按照时间顺序将数据区块以顺序相连的方式组合成的一种链式数据结构，并以密码学方式保证的不可篡改和不可伪造的分布式账本。区块链技术有效地解决了拜占庭将军问题中的共识问题，实现了节点在无须互相信任的情况下能够完成去中心化的点对点交易。但随之而来的也有区块链运作效率低下，浪费大量时间和空间等问题。为了更好的优化区块链技术存储方式，我们展开了调查、分析与研究。

2 区块链运行原理探究

区块链作为一种较为安全可靠的网上交易和存储模式，被广泛地运用在各种商业及金融领域。区块链系统大约每十分钟将全网产生的所有交易存储到一个区块中。由于区块链节点之间是对等而互不信任的关系，区块链使用了工作量证明（Proof-of-Work）。这使得生成的区块具有较高的价值和可信任性。最终当一个区块生成成功时向全网广播，使得每个电脑上都有一份完整区块链的拷贝。从而实现了节点在无须互相信任的情况下能够完成去中心化的点对点交易的过程。

3 区块链运行过程中的弊端

从上述区块链运行原理中可以看出，区块链在运行过程中具有十分高的安全性和稳定性，但是也存在以下几个问题：

1）区块链占用的网络存储资源十分大，这让主区块链在每一个节点中都存在一份备份变得越来越不实际。

2）当我们需要对新交易进行检验时，每个节点认证交易都需要对历史区块进行大量访问。而全网中所有的节点都需要对重复的交易或区块进行验证，缺乏恰当的合作方式。

綜上，提出一种优化存储与计算的区块链模型刻不容缓。

4 一致性哈希算法原理与应用探究

一致性哈希算法是哈希算法的一种扩展。该算法实现了为服务器和存储信息均实时变化的情况下较为合理地分配网络缓存。接下来我们将简要介绍一致性哈希算法：

1） 一致性哈希算法首先将服务器特征信息通过哈希函数映射到一个环上，并按照顺时针将信息存储到距离其最近的服务器上（如图1，其中S代表服务器，A代表信息，虚线为存储关系）。由于哈希函数的随机性，每个服务器期望存储的信息个数均相同。

2）如果服务器的个数增加时（如图2，S3服务器为新增服务器），为了维护每个元素均存储于顺时针遇到的第一个服务器的原则，在S3右边和S2左边的所有数据（如A2）均需要从原服务器（S1）转移到新增的服务器（S3）。而如果服务器个数减少，只需要将要删除的服务器中的全部元素转移到顺时针遇到的下一个服务器即可。

分析算法效率可知：每个服务器平均存储的信息量为信息总数除以服务器总数，同时在服务器变动时也只需要移动一个服务器中的信息。因此一致性哈希算法是一种高效而合理地分配网络存储资源的优秀算法，这为本文基于一致性哈希算法的区块链优化模型的提出提供了正常高效运转的基石。

5 基于一致性哈希算法的区块链的优化模型

本模型继承了区块链分布式存储的方法，拟建立用户节点和服务节点两种类型节点。其中用户节点数量庞大、容易变动、安全等级低且存储和计算能力均比较弱。而服务节点则具有运算能力强、存储空间大和连接稳定等特点。

基于上述不同节点的特点，本模型将在每个服务节点上存储整个主区块链的备份并在服务节点上建立数据结构快速查找索引。而用户节点只根据网络要求在用户节点上存储少量区块数据，同时用户节点的验证、计算等工作也将分摊一部分到服务节点。

下面将详细介绍模型中节点的任务以及在实际情况中的模型的运转流程。

1） 当用户节点上线时，需要先搜寻一个服务节点作为自己的服务节点。并将自己的特征标识+当前时间+环内节点最后一个通过验证的区块输入哈希函数并作为自己的在环上的位置（如图3）。这样决定节点位置可以保证位置定时刷新且无法被预测。当节点移动时，节点存储信息利用一致性哈希算法移动。

2）当区块链中有新的区块产生的时候，首先由服务节点计算出区块的哈希值并将其通过一致性哈希算法映射到该服务器管理的环中。（如图4，绿色为区块的映射位置，蓝色为用户节点的映射位置）并根据当前网络安全程度、对信息来源可靠性的分析和当前在线节点个数，自动地沿着顺时针方向寻找若干个节点（如标星节点）并令这些节点对该新生成的区块进行校验与认证。标星节点验证完毕则视为该服务区对该区块验证成功。由于一致性哈希具有的随机性质，其过程可以等价于在该服务区中随机抽取若干个节点进行验证工作。这使得少数的节点可以使用较少的工作量代替大多数节点验证，同时由于系统的随机性质使得这些节点难以被预测和攻击。从而使这些节点的验证具有代表性。

3）当一个区块最终接入主区块链后，服务节点需要将这个区块加入主区块链。同时，服务器将这个经过认证的区块再次经过哈希映射在环上，并使得顺时针若干个节点存储区块的备份文件。当节点需要读取某区块时，服务器将通过快速索引优先返回本地储存的区块链信息，同时该节点将随机选择1～2个存储了所需区块的节点，使其发送校验信息到请求节点进行比对和认证。从而在保证读取效率的情况下尽可能保证数据不会被篡改。

4）服务器需要定期对本地的数据和所有节点中缓存的数据进行查验比较。如果发现了数据缺失或者数据不相同则通过网络向其他服务节点获取更加可靠的区块链。这样就可以避免由于本地错误或其他原因导致数据遗失和破坏，同时也使得入侵者难以对数据进行攻击和破坏。

综上，该模型在提升了区块链的工作效率和优化区块链占用的存储的同时，有着一套较为可行的防攻击和安全维护机制，使得模型稳定、高效而可靠。

6 针对实例的进一步优化

区块链技术除了应用在金融领域，在网络电子商务中也有广泛应用。由于网上的厂商相对买家和卖家来说较为固定，所以可以在区块链网络中担任服务节点的角色。而买卖双方具有流动性大，变化迅速等特点，在网络中扮演用户节点的角色会比较合适。

在实际的网上交易中，一个交易单往往包含大量的信息。因此，我们可以按照数据的重要程度给数据分级，并将不同层级的交易单信息进行分片式存储与管理。对于重要的数据，系统要求工作量证明难度更高、在认证时需要得到更多的用户节点的认可，以及存储时在多个不同的节点上保存备份文件以防篡改和丢失。而对于相对次要的数据，则可以适当地降低提供工作量证明的难度，在存储时减少备份数量。

至此，优化模型的原理与概况基本阐述完毕，下表1为传统区块链与优化模型的优劣比较：

7 验证数据与探究结果

通过自行编写区块链程序和本文中优化模型的程序、搭建小型网络进行模拟测试，我们得到了以下若干实验数据，并进行了对比分析。

实验采用控制变量法，测试了若干个因素对程序的时间效率以及空间效率的影响。首先控制处理数据大小不变，控制PoW相对于网络节点总算力难度不变，改变网络中节点的数量，测得程序运行时所使用物理内存空间以及虚拟内存空间如表2：（注：其中内存占用为网络中所有节点内存占用的平均值）

通过上述实验数据我们可以看出以下几个结论：①优化模型在面对同样大小的数据时，其处理所用内存空间相对于普通区块链来说具有较大的优势。②对于优化模型，节点数的增加反而使得内存空间变少，因此在实际网络中运行时优化模型也会具有更大的存储优势。

接着控制上述变量不变情况下，探究节点变化对算法运行时间的影响，测得数据如表3：

由表中净运行时间的对比可见，节点数增加时，原区块链算法的净运行时间基本呈线性增长，而优化模型的净运行时间则随着节点个数的增多快速下降。这主要是因为通过网络中服务节点的合理调度，优化模型较好地分配了各个节点的计算资源，使得节点消耗的运算资源大幅度减少。但在处理过程中，优化模型所需要的总处理时间要略多于原区块链的处理时间。

接下来我们控制节点数量不变（始终为4），通过改变数据规模获得相关信息。通过实验测得在改变数据规模的情况下，程序运行时间和占用内存如表4：

通过比较我们发现，在数据规模变化时各个算法的时间基本呈现出线性增长，但是优化模型所用总时间相对于原区块链所用总时间仍有一定差距。但是对比算法净运行时间和内存效率，我们可以发现优化模型在不同的数据规模之下仍然拥有更加高效的净处理时间和内存使用量，这进一步体现出了优化模型调配网络计算、存储资源的优越性。

综上，本文提出的基于一致性哈希算法的区块链优化模型具有十分优秀的存储效率，具有优秀的存储容量可扩展性。同时本文模型在处理的时间效率上也与普通区块链差距不大，单个节点的工作量大幅降低。

8 结语

在当今信息爆炸式增长的时代，区块链也难免存在着存储和计算效率的问题。本文通过对一致性哈希算法和区块链相关技术的有效结合，成功创立了基于一致性哈希算法的区块链优化模型。该模型从区块链存储，区块链运算和数据分级管理等多個方面对现有区块链进行补充和优化，弥补了区块链存储与计算方面的不足。同时模型提出了服务器定期自动核查、同步的方式来确保区块链的安全运行，极大程度上防止了外来攻击对重要数据的破坏与篡改。其优异的性能和可靠的安全性，使该模型在现代信息社会具有重要的现实意义。

参考文献：

[1] 贾大宇，信俊昌，王之琼，等.区块链的存储容量可扩展模型[J].计算机科学与探索，2017（9）.

[2] 郝琨，信俊昌，黄达，等.去中心化的分布式存储模型[J].计算机工程与应用，2017（12）.

[3] Tim Roughgarden Gregory Valiant.CS168：The Modern Algorithmic Toolbox Lecture #1： Introduction and Consistent Hashing.2018-04-02

[4] 邱宁佳，胡小娟，王鹏，等. 一致性哈希的数据集群存储优化策略研究[J].信息与控制，2016（12）.

【通联编辑：唐一东】