Gossip 协议简介
【定义】
Gossip protocol，又叫 Epidemic Protocol （流行病协议），也叫“流言算法”、“疫情传播算法”等。其名称已经形象的说明了算法的原理和工作方式。
学习链接
【应用场景】
1. 分布式网络，无集中管理节点；
2. 节点间点对点传播信息。
【典型应用】
1. P2P；
2. Bitcoin；
3. Apache Cassandra、Redis cluster。
Gossip 协议优缺点
| 优点 |
缺点 |
|
简单 |
最终一致性 |
|
1. 扩展性：网络节点可任意增加和修改； 2. 容错性：无中心节点，任意节点宕机 不影响协议运行； 3. 去中心化：任意节点都可以发送消息。 |
1. 需要花费一定时间达到最终一致性； 2. 消息冗余； 3. 不适合超大规模集群（超过1000）； 4. 恶意节点传播垃圾信息。 |
Gossip 模式1 – Direct Mail
【直邮模式】
通知所有邻居更新信息，邻居节点收到消息后不会转发。
【优点】
简单。
【缺点】
1. 难以达到最终一致性
• 节点消息可能丢失（图中黄色节点）；
• 节点可能并没有连接（图中深红色节点）。
2. 容错性低
• 需要缓存发送失败的消息。
3. 种子节点压力大
【应用场景】
社交网络（朋友的朋友并不一定是你的朋友）。
Gossip 模式2 – Anti-Entropy
【反熵模式】
集群中的节点，每隔一段时间随机选择1个节点，互相交换所有数据，然后进行同步，消除数据不一致
【优点】
最终一致性。
【缺点】
1. 信息同步的成本高：
• checksum；
• updated list。
2. 达到最终一致性的耗时较长。
【应用场景】
节点数量不多，实现最终一致性，例如存储系统多副本一致性。
Bully 算法简介
【Bully 算法】
当一个进程发现协调者（或 Leader）不再响应请求时，就判定其出现故障，于是它就发起选举，选出新的协调者，即当前活动进程中进程号
最大者。
Bully 的中文意思是“霸凌”，但实际实现的时候，找最小的节点也可以，关键点在于“最”。
【关键假设】
1. 系统是同步的；
2. 进程在任何时候都可能失败，包括算法在执行的过程中；
3. 进程失败后停止工作，重启后重新工作；
4. 有失败监控者，它可以发现失败的进程；
5. 进程之间消息传递是可靠的；
6. 每一个进程知道自己和其他每一个进程的 ID 以及地址。
Bully 算法选举过程
(1/2)
step0：初始状态，P6 为 Leader；
step1：P6 故障；
step2：P3 检测到 P6 故障，发起选举，向 P4、P5、P6 发送 Election 消息；
step3：P4、P5 回复 P3 Alive 消息，说明自己还活着，P3 退出选举，等待胜利消息。
(2/2)
step4：P4向P5、P6发送 Election 消息；
step5：P5回复P4 Alive 消息，P4退出选举，等待 Victory 消息；
step6：P5向P6发送 Election 消息；
step7：P5未收到 Alive 消息,成功当选，向所有节点发送胜利消息，选举结束。
Raft 算法简介
【Raft 算法】
Raft是一种更为简单方便易于理解的分布式算法，主要解决了分布式中的一致性问题。相比传统的Paxos算法，Raft将大量的计算问题分解成为了一些简单的相对独立的子问题。
【关键点】
1. 容易理解（Raft 作者说几个研究人员研究了1年还不是很明白 Paxos）；
2. 算法明确划分为选举、复制、安全三个子问题。
Raft 实现1 – leader 选举
1.应用程序的客户端只向领导服务器发出请求，并且只从领导服务器获取响应。etcd 的实现
2. 只有在一个领导人成功当选并存活才可用。
Raft 实现2 – 日志复制
State machine replication：复制状态机，复制的是命令而不是数据，典型代表：Raft。
Primary-backup system：主备复制，复制的是命令执行后的数据，典型代表：ZooKeeper 的 ZAB
Raft的实现：
每个节点都有一个状态机和一致性模块，由一致性模块保证分布式一致性，节点之间复制的是 client 发送的命令，无论读写请求都需要进行一致性处理，因此可以容忍非拜占庭故障。
Raft vs ZAB vs Paxos
Raft vs ZooKeeper
1. 如果你想内嵌分布式选举或者一致性功能，或者基于业务特性做一些小调整，选择 Raft，例如 MongoDB、etcd 等；
2. 如果你想实现分布式选举或者一致性，但是不想自己去实现协议代码，选择 ZooKeeper，例如 HDFS、Cassandra 等；
3. 如果你不确定，请选择 ZooKeeper。
总结：
原文始发于微信公众号（二进制跳动）：常见集群算法解析
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/166880.html
