今天我们聊一下分布式共识算法哈. 聊到分布式共识算法, 大家首先肯定会想到的是Raft和ZAB这类强一致性算法, 但这些算法实现都会存在短时无法使用的问题. 现在想给大家介绍一个弱一致性算法, Gossip协议, 适用于AP场景.
Gossip协议在1987年由施乐-帕洛阿尔托研究中心发表ACM上的论文《Epidemic Algorithms for Replicated Database Maintenance》中被提出. 原本用于分布式数据库中节点同步数据使用, 后被广泛用于数据库复制, 信息扩散, 集群成员发现和故障检测等场景.
Gossip协议是基于六度分隔理论哲学的体现, 简单来说, 一个人通过6个中间人可以认识世界任何人. 基于六度分隔理论, 任何消息的转播其实非常迅速, 而且网络交互次数不会很多.
原理
基本思想就是一个节点想要分享一些信息给网络中的其他的节点, 于是随机选择一些节点进行信息传递. 这些收到信息的节点接下来把这些信息传递给其他一些随机选择的节点. 整体过程描述如下:
- 种子节点周期性的散播消息
- 被感染节点随机选择N个邻接节点散播消息
- 节点只接收消息不反馈结果
- 每次散播消息都选择尚未发送过的节点进行散播
- 收到消息的节点不再往发送节点散播: A -> B, 那么B进行散播的时候, 不再发给 A
由上面的过程可以看出, 它可以快速地将信息散播给集群中每个成员，散播速度为 𝑙𝑜𝑔𝑓(𝑁), 其中 f 术语称为 fanout, 代表每次随机传播的成员数, 而 N 代表总共成员数. 例如：𝑙𝑜𝑔4 (40)≈2.66, 也就是大约三轮传播, 或者log4(10000)≈6.67, 就可以让集群达到一致. 可以看到集群节点数量从40增长到10000, 其散播速度变化约为4, 增加并不明显.
消息传播方式
Gossip 协议的消息传播方式有两种:
- Anti-Entropy(反熵传播)是以固定的概率传播所有的数据. 所有参与节点只有两种状态: Suspective(病原), Infective(感染). 这种节点状态又叫做simple epidemics(SI model). 过程是种子节点会把所有的数据都跟其他节点共享, 以便消除节点之间数据的任何不一致, 它可以保证最终, 完全的一致. 缺点是消息数量非常庞大, 且无限制; 通常只用于新加入节点的数据初始化
- Rumor-Mongering(谣言传播)是以固定的概率仅传播新到达的数据. 所有参与节点有三种状态: Suspective(病原), Infective(感染), Removed(愈除). 这种节点状态又叫做complex epidemics(SIR model). 过程是消息只包含最新 update, 谣言消息在某个时间点之后会被标记为 removed, 并且不再被传播. 缺点是系统有一定的概率会不一致, 通常用于节点间数据增量同步
实现
scalecube-cluster提供了轻量级集群成员发现及故障检测, 同时兼容Gossip协议.
总结
Gossip协议特点:
- 去中心化
- 最终一致性协议, 扩展性好, 容错, 适用于AP场景
- 方便地实现弹性集群, 允许节点随时上下线, 提供快捷的失败检测和动态负载均衡等
- FanOut特性, 即使集群节点的数量增加, 每个节点的负载也不会增加很多, 几乎是恒定的
Gossip协议缺点:
- 消息延迟, 因为节点随机向少数几个节点发送消息, 消息最终是通过多个轮次的散播而到达全网
- 消息冗余, 节点定期随机选择周围节点发送消息, 而收到消息的节点也会重复该步骤; 不可避免的引起同一节点消息多次接收, 增加消息处理压力
- 拜占庭问题, 如果有一节点恶意传播信息, 那么集群就会出问题
