分布式算法

• Gossip协议:Redis集群服务端通讯协议

• DHT实现：Kademlia算法

分布式系统算法：Paxos、Raft、ZAB 两军问题与拜占庭将军问题

---

Gossip协议:Redis集群服务端通讯协议

Consensus Algorithm—— Gossip协议

Gossip protocol 也叫 Epidemic Protocol （流行病协议），实际上它还有很多别名，比如：“流言算法”、“疫情传播算法”等。

gossip 协议（gossip protocol）又称 epidemic 协议（epidemic protocol），是基于流行病传播方式的节点或者进程之间信息交换的协议，在分布式系统中被广泛使用，比如我们可以使用 gossip 协议来确保网络中所有节点的数据一样。

Gossip 协议的执行过程：

Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

Gossip 的特点（优势）

可扩展性（Scalable） 去中心化 容错（Fault-tolerance） 健壮性（Robust） 最终一致性（Convergent consistency）

Gossip 的缺陷 1）消息的延迟 2）消息冗余

Gossip 有两种类型： Anti-Entropy（反熵）：以固定的概率传播所有的数据 Rumor-Mongering（谣言传播）：仅传播新到达的数据

Redis Cluster 是一个可以在多个 Redis 节点之间进行数据共享的分布式集群，在服务端，通过节点之间的特殊协议进行通讯，这个特殊协议就充当了中间层的管理部分的通信协议，这个协议称作Gossip流言协议。

Gossip协议的使用 Redis 集群是去中心化的，彼此之间状态同步靠 gossip 协议通信，集群的消息有以下几种类型： 1、Meet 通过「cluster meet ip port」命令，已有集群的节点会向新的节点发送邀请，加入现有集群。 2、Ping 节点每秒会向集群中其他节点发送 ping 消息，消息中带有自己已知的两个节点的地址、槽、状态信息、最后一次通信时间等。 3、Pong 节点收到 ping 消息后会回复 pong 消息，消息中同样带有自己已知的两个节点信息。 4、Fail 节点 ping 不通某节点后，会向集群所有节点广播该节点挂掉的消息。其他节点收到消息后标记已下线。 由于去中心化和通信机制，Redis Cluster 选择了最终一致性和基本可用。

基于Gossip协议的故障检测

集群中的每个节点都会定期地向集群中的其他节点发送PING消息，以此交换各个节点状态信息，检测各个节点状态：在线状态、疑似下线状态PFAIL、已下线状态FAIL。

自己保存信息：当主节点A通过消息得知主节点B认为主节点D进入了疑似下线(PFAIL)状态时,主节点A会在自己的clusterState.nodes字典中找到主节点D所对应的clusterNode结构，并将主节点B的下线报告添加到clusterNode结构的fail_reports链表中，并后续关于结点D疑似下线的状态通过Gossip协议通知其他节点。

一起裁定：如果集群里面，半数以上的主节点都将主节点D报告为疑似下线，那么主节点D将被标记为已下线(FAIL)状态，将主节点D标记为已下线的节点会向集群广播主节点D的FAIL消息，所有收到FAIL消息的节点都会立即更新nodes里面主节点D状态标记为已下线。

最终裁定：将 node 标记为 FAIL 需要满足以下两个条件： 1、有半数以上的主节点将 node 标记为 PFAIL 状态。 2、当前节点也将 node 标记为 PFAIL 状态。

也就是说当前节点发现其他结点疑似挂掉了，那么就写在自己的小本本上，等着通知给其他好基友，让他们自己也看看，最后又一半以上的好基友都认为那个节点挂了，并且那个节点自己也认为自己挂了，那么就是真的挂了，过程还是比较严谨的。

参考 https://zhuanlan.zhihu.com/p/41228196 https://www.jianshu.com/p/133560ef28df https://www.jianshu.com/p/de7b026f4997 https://blog.csdn.net/b6ecl1k7BS8O/article/details/86653449 https://hyperledger-fabric.readthedocs.io/zh_CN/latest/gossip.html

集群版Redis和Gossip协议 https://zhuanlan.zhihu.com/p/72629038 https://juejin.im/post/5dd65d676fb9a05a9a22ac6f

---

DHT实现：Kademlia算法

Kademlia是分布式哈希表/散列表（Distributed Hash Table, DHT）的一种。而DHT是一类去中心化的分布式系统。

Kademlia算法是一种分布式存储及路由的算法。

分布式哈希表（distributed hash table，缩写DHT）是分布式计算系统中的一类，用来将一个键（key）的集合分散到所有在分布式系统中的节点。这里的节点类似哈希表中的存储位置。

使用场景： 分布式哈希表通常是为了拥有大量节点的系统，而且系统的节点常常会加入或离开。

算法的三个参数：keyspace，k和α keyspace -- 即ID有多少位 -- 决定每个节点的通讯录有几层 k -- 每个一层k-bucket里装k个node的信息，即<node ID, IP Adress, port> -- 每次查找node时，返回k个node的信息 -- 对于某个特定的data，离其key最近的k个节点被会要求存储这个data α -- 每次向其他node请求查找某个node时，会向α个node发出请求

节点的指令 Kademlia算法中，每个节点只有4个指令

PING -- 测试一个节点是否在线 STORE -- 要求一个节点存储一份数据 FIND_NODE -- 根据节点ID查找一个节点 FIND_VALUE -- 根据KEY查找一个数据，实则上跟FIND_NODE非常类似

k-bucket的维护及更新机制 每个bucket里的节点都按最后一次接触的时间倒序排列 每次执行四个指令中的任意一个都会触发更新 当一个节点与自己接触时，检查它是否在K-bucket中 -- 如果在，那么将它挪到k-bucket列表的最底（最新） -- 如果不在，PING一下列表最上面（最旧）的一个节点 -- a) 如果PING通了，将旧节点挪到列表最底，并丢弃新节点 -- b) 如果PING不通，删除旧节点，并将新节点加入列表 该机制保证了任意节点加入和离开都不影响整体网络。

总结 Kademlia是分布式哈希表（Distributed Hash Table, DHT）的一种。而DHT是一类去中心化的分布式系统。

在这类系统中，每个节点（node）分别维护一部分的存储内容以及其他节点的路由/地址，使得网络中任何参与者（即节点）发生变更（进入/退出）时，对整个网络造成的影响最小。

DHT可以用于构建更复杂的应用，包括分布式文件系统、点对点技术文件分享系统、合作的网页高速缓存、域名系统以及实时通信等。

Kademlia算法在2002年由Petar Maymounkov 和 David Mazières 所设计，以异或距离来对哈希表进行分层是其特点。Kademlia后来被eMule、BitTorrent等P2P软件采用作为底层算法。Kademlia可以作为信息安全技术的奠基之一。

Kademlia的优点在于： 1、对于任意一个有[ 2(n−1) ,2𝑛)个节点的网络，最多只需要n步搜索即可找到目标节点； 2、K-bucket的更新机制一定程度上保持了网络的活性和安全性。

参考 https://www.jianshu.com/p/f2c31e632f1d https://colobu.com/2018/03/26/distributed-hash-table/ https://zhuanlan.zhihu.com/p/40286711 https://azhuge233.com/kademlia%E7%AE%97%E6%B3%95%E4%B8%8E%E5%88%86%E5%B8%83%E5%BC%8F%E5%93%88%E5%B8%8C%E8%A1%A8dht/ https://program-think.blogspot.com/2017/09/Introduction-DHT-Kademlia-Chord.html

---