区块链技术中的Merkle树是如何实现优化Gossip协议的？
区块链技术中的Merkle树是如何实现优化Gossip协议的？
大家好，我是程序员牛肉。
如果大家有学过Redis集群的话，就会知道Redis集群正是通过Gossip协议来传递消息的，而Gossip自身也有不少的缺点。
因此我们这篇文章来介绍一下什么是Gossip协议以及基于Merkel树是如何优化Gossip协议的。
现在很多文章都说Gossip是谣言传播机制，事实上这本身就是一种谣言。我们直接从相关论文中寻找答案。
https://bitsavers.trailing-edge.com/pdf/xerox/parc/techReports/CSL-89-1_Epidemic_Algorithms_for_Replicated_Database_Maintenance.pdf Gossip论文链接
Gossip的论文中一共提到了三种消息传播的方式，他们分别是：
直接邮件（Direct Mail）：每当有更新发生时，立即将更新从其发生的站点邮寄到所有其他站点。这种方法及时且相对高效，但由于邮件可能丢失或发送者对其他站点的信息不完整，可靠性不足。
反熵（Anti-Entropy）：每个站点定期随机选择另一个站点，并通过交换数据库内容来解决两者之间的差异。反熵机制非常可靠，因为它确保最终所有站点的数据都会一致，但由于需要比较整个数据库内容，频繁使用会消耗大量资源。
谣言传播（Rumor Mongering）：当一个站点接收到新的更新时，该更新被视为“热点谣言”。持有热点谣言的站点会定期随机选择其他站点，确保这些站点也看到了更新。当一个站点尝试与过多已经了解该更新的站点分享后，便会停止传播这个谣言。谣言传播比反熵更频繁，因为它需要的资源较少，但有可能导致更新无法到达所有站点。
[这也是网上为什么有的文章说Gossip协议不会重复发送消息给同一个节点，有的又说会发送消息给同一个节点的原因。因为不会重复发送给同一个节点的都是反熵机制，而会重复发送消息给同一个节点的是谣言传播机制。而这两种机制都属于Gossip协议的消息传递机制。而本篇中我我们主要聊的是谣言传播这种模式。]
而Redis集群中的Gossip协议采用的是谣言传播机制。Gossip协议用于在Redis集群中的各个节点之间传播状态信息。每个节点都会周期性地与其他节点交换信息，包括节点的健康状态、数据分片的主从关系等。这种机制确保所有节点都能及时了解整个集群的状态变化。
而Gossip协议在Redis集群中的整体运行机制是PingPang机制：
在这一过程中，随着Redis集群的节点数不断增加，Gossip协议所传递的信息量也在不断的变大。假设我们有N个节点，就需要不断的向N-1个节点发送心跳来证明自己活着。并且每一个心跳都需要携带N/10个节点的信息。
[至于为什么每一个心跳都携带N/10个节点的信息而不是N-1个节点的信息，这一点其实作者在源码中有解释：
叽里咕噜的说啥呢这是，作者的意思简而言之就是假设所有的节点都是主节点，选择1/10的比例可以确保在大多数情况下（具体为80%），即使有多个主节点同时失败，也能有效传播故障信息。]
但即使我们已经减少了每次心跳携带的消息数，但随着Redis集群节点的增加，在pingpang中也仍然需要传递海量的数据。
那我们想一想：实在不行就别在日常的PingPang中传输大量数据了呗，改成哈希。两个不同的数据大概率哈希值也是不一样的（可能会存在哈希冲突）。
基于这种思路，那我们可以先传递数据的哈希值。当两个数据的哈希值不一样的情况下，再传递真正的数据来同步两个节点之间的数据。
初版方案已经有了。我们可以再想一想怎么优化？
当前这个方案还是有一个问题就在于：当两个节点的哈希值不一样的时候，节点就要更新所有的数据。可是大部分情况下可能两个节点的大部分信息都是相同的，只是有一点发生了变化而已。
这简单，分块传输嘛，我们只需要比较数据块，哪个数据块不一样我们就改变哪一个块就行了。
而复刻之前的思路，其实这些分的块也不用真实传输，传输这个块对应的Hash数据就好了。
而在这一过程中，我们采用了Merkel树快速验证数据的完整性和一致性。
[Merkel树的本质就是哈希树，他的每一个节点都是由子节点进行哈希得到的。而基于这种性质，在区块链技术中Merkle树经常用来进行交易验证和交易检索。
想要简单了解加密货币的可以看我之前写的这一篇文章：
股市热潮下想投资加密货币？先了解清楚到底什么是加密货币和挖矿吧。
]
我们看一看Merkle树的数据结构：
我们可以把子节点ABCD就理解为同一个数据包下被切分的数据包。基于Merkle这种数据结构，子节点任何细微的变化都会引起头节点的变化。
这样在Ping消息中我们只需要携带对应的上图中的这些节点哈希值。比如4个数据包我们就携带7个哈希值就好了。而当这些哈希都相同的时候，在Pong消息中我们也可以和ping消息一样就传递这些哈希值就好了。基于这种机制我们就大量的节省了PingPong中所需要传递的消息量。
在比较的时候，只需要比较这四个节点信息的哈希值就好了。而之所以要传递剩下的树节点信息，是因为可以校验数据的完整性。
[我们在传递消息中传递新的数据C和对应的根节点。当我们替换完目标树的数据C之后，可以尝试与当前的树节点一路向上进行Hash求最新的根节点值，比较一下传递过来的根节点值和自己计算出来的根节点值是否一样。如果两个根节点的哈希值一样的话，就说明传递过来的C是完整的]
而这种方案我们都能设计出来，就证明他已经不是什么新活了。在美团的公开技术文档中就有过介绍，大家感兴趣的话可以看一下这篇文档：
https://tech.meituan.com/2024/03/15/kv-squirrel-cellar.html 相关公开文档
在这篇文章中就大致介绍了一下他们基于Merkle树对于Gossip协议的优化。
在这里其实我们可以看到一个比较有趣的事情：他们构造的Merkle树和我们的并不完全一样：
[他们的父节点使用两个子节点的哈希值异或得到的，而我们的是两个节点的哈希值相加之后再次哈希。]
这两者有什么区别呢？以下就纯属我个人瞎猜了，大家听个乐子就好。
异或计算是一个很奇妙的计算，它可以相互计算求值。比如你用A和B异或得到C。那么你用C和B异或就可以得到A，用C和A异或就可以得到B。
比如参考上图中的树，如果我们有了V5和Hash（F）的话，我们其实就可以用这两个值进行异或算出来Hash(E)的值应该是多少。这是我们原版的Merkle树所不具备的能力。
基于这种操作，其实相比较原版的Merkle树我们就具有了自上而下的校验手段。
其实这种操作很常见，如果你做过黑马点评的话，就会用到一个数据结构叫做布隆过滤器。而布隆过滤器因为设计问题无法做到删除元素。为了改进这一点，我们设计出了布谷鸟过滤器。
布谷鸟哈希过滤器采用布谷鸟哈希结构。我们将数据进行哈希之后得到一个指纹，放入到这个布谷鸟哈希结构中。
每一个指纹会有两个位置可以放，以此来应对挤占情况。第一个坐标是通过某个哈希函数计算出来，第二个坐标是使用第一个坐标和指纹的哈希做了一个异或操作，进行异或操作是因为异或操作的特性: a^b = c ,c ^ b= a,c^a=b,我们可以快速的互推数据。
换句话说，当在桶中当前数据被挤占的时候，我们直接用当前桶的索引i和存储在桶中的指纹就可以计算出它的备用桶。如果你不了解布谷鸟过滤器，可以看一下我之前写的这一篇文章：
那今天对于区块链技术中的Merkle树是如何实现优化Gossip协议就介绍到这里了。其实讲的比较模糊，只讲了大致思路。
因为我要遵守公司保密，因此就不能和大家分享关于这方面更加详细的信息。欢迎你加入美团来亲自看看我们在这方面到底做了哪些优化。
对于merkle树你有什么想说的嘛？欢迎在评论区留言。
关注我，带你了解更多计算机干货。
end
腾讯云开发者
