DAG的基本概念和技术 | P2P对等网络

3 P2P网络拓扑构建与维护技术

P2P网络的最大特点和难点，在于它极大的动态性：不断有新节点加入、旧节点离开、节点失效等情况发生。 面对这样一个动态环境，P2P网络需要一套健全、可行的方法来处理这些情况：在新节点加人时通知其他节点新成员的到来，在旧节点离开时通知其他节点老成员的离去，而最难的是需要高效、合理地检测到节点失效并及时修复P2P网络。下面介绍基于Gossip的P2P网络拓扑构建和维护技术。

Gossip算法又被称为反熵（Anti-Entropy），熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致，这充分说明了Gossip的特点：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点，也可能仅知道几个邻居节点，只要这些节可以通过网络连通，最终他们的状态都是一致的，当然这也是疫情传播的特点。

要注意到的一点是，即使有的节点因宕机而重启，有新节点加入，但经过一段时间后，这些节点的状态也会与其他节点达成一致，也就是说，Gossip天然具有分布式容错的优点。Gossip是一个带冗余的容错算法，更进一步，Gossip是一个最终一致性算法。虽然无法保证在某个时刻所有节点状态一致，但可以保证在”最终“所有节点一致，“最终”是一个现实中存在，但理论上无法证明的时间点。因为Gossip不要求节点知道所有其他节点，因此又具有去中心化的特点，节点之间完全对等，不需要任何的中心节点。实际上Gossip可以用于众多能接受“最终一致性”的领域：失败检测、路由同步、Pub/Sub、动态负载均衡。

Gossip假定同步会按照一个固定进度表执行，每个节点定期随机或是按照某种规则选择另外一个节点交换数据，消除差异。有三种类型的反熵协议：推（push），拉（pull）和推/拉（push/pull）混合（如图 2–12所示）。

l push: A节点将数据(key,value,version)及对应的版本号推送给B节点，B节点更新A中比自己新的数据

l pull：A仅将数据key,version推送给B，B将本地比A新的数据（Key,value,version）推送给A，A更新本地

l push/pull：与pull类似，只是多了一步，A再将本地比B新的数据推送给B，B更新本地

图 2–12三种类型的反熵协议

如果把两个节点数据同步一次定义为一个周期，则在一个周期内，push需通信1次，pull需2次，push/pull则需3次，从效果上来讲，push/pull最好，理论上一个周期内可以使两个节点完全一致，push/pull的收敛速度是最快的。假设每个节点通信周期都能选择（感染）一个新节点，则Gossip算法退化为一个二分查找过程，每个周期构成一个平衡二叉树，收敛速度为O(N2)，对应的时间开销则为O(log N)。这也是Gossip理论上最优的收敛速度。但在实际情况中最优收敛速度是很难达到的，假设某个节点在第i个周期被感染的概率为pi,第i+1个周期被感染的概率为pi+1，则pull的方式:

而push为：

显然pull的收敛速度大于push，而每个节点在每个周期被感染的概率都是固定的p(0<p<1)，因此Gossip算法是基于p的平方收敛，也成为概率收敛，这在众多的一致性算法中是非常独特的。

Gossip算法还需要考虑协调机制，即是讨论在每次2个节点通信时，如何交换数据能达到最快的一致性，也即消除两个节点的不一致性。上面所讲的push、pull等是通信方式，协调是在通信方式下的数据交换机制。协调所面临的最大问题是，因为受限于网络负载，不可能每次都把一个节点上的数据发送给另外一个节点，也即每个Gossip的消息大小都有上限。在有限的空间上有效率地交换所有的消息是协调要解决的主要问题。

总结来看， Gossip是一种去中心化、容错而又最终一致性的绝妙算法，其收敛性不但得到证明还具有指数级的收敛速度。 使用Gossip的系统可以很容易的把Server扩展到更多的节点，满足弹性扩展轻而易举。唯一的缺点是收敛是最终一致性，不适用那些强一致性的场景。

博士。资深区块链技术专家和网络安全专家，从事区块链技术研究与应用近10年，对DAG技术有深入研究，基于DAG技术的明星区块链项目InterValue的创始人兼CEO。
西安电子科技大学区块链应用与评测实验室副主任、浙江大学计算机学院区块链研究中心特聘研究员、湘江区块链研究院副院长、矩阵数字经济智库专家成员。
此外，他还是北京理工大学机电学院特聘研究员、湘潭大学硕士生导师、湖南宸瀚信息科技有限公司董事长、哈希奈特（北京）科技股份有限公司董事长、四川宸瀚信息科技有限公司董事长、浙江物信科技有限公司董事长。