前面我们已经讲了分布式 CAP、BASE 理论及分布式事务的 8 种解决方案，今天我们来聊一聊常见的 4 种分布式算法。
Paxos 算法的业务场景就好比是在一个大公司的董事会选举中心选出新董事长，但这个过程是在乌云密布的风雨天进行，通信极度不稳定，董事们时不时被困在电梯里或是在高尔夫球场打不了电话。
在 Paxos 算法中，每个董事（参与者）都是独立操作的，而这个算法就是确保即便在通信可能失败，董事们也能达成一致。
它通过一系列的提议（proposal）和承诺（promise）来保证最终的一致性。
假设，现在有 3 个董事候选人在争夺董事长职位，用 Paxos 算法来表示这个过程，可分为三个阶段：
当候选董事 A 收到了多数董事会成员的承诺后，它会向那些承诺过的成员发送详细的提案内容。
如果这些董事会成员没有对更高编号的提案做出过承诺，它们就会接受这个提案。
学习阶段（Learn）:
一旦提案被多数董事会成员批准，这个候选人就被选为新董事，每个董事会成员会记录下来这个结果。
此时，所有其他员工或股东都需要知道这个结果，这样新董事的确立就在全公司范围内达到了一致。
在这过程中，Paxos 算法又将系统中的节点分为三类：
图片
提议的时候，包含俩字段：[n, v]，其中 n 为序号，v 为提议值。每个 Aceeptor 在接收提议请求的时候，会比对其中的序号 n：
当一个 Proposer 接收到超过半数的 Aceeptor 响应时，说明该提议值被 Paxos 选择了出来，这时候，由 Acceptor 负责通知给所有的 Learner。
引入主节点，通过竞选来获取主节点。节点分为三类：
想象咱们身处一个居民社区里面，这个社区需要选举出一位业委会主任来负责新年的社区大事，Raft 算法会经历如下 3 个阶段。
Candidate 发送投票消息给其它所有存活节点，其它节点会对其请求进行回复，如果超过半数的节点回复了竞选请求，那么该 Candidate 就会变成 Leader 节点。
新 Leader 周期性发送心跳包给 Follower，Follower 收到心跳包以后重新计时。这时，Leader 如果接收到了客户端请求，会将数据变更写入日志中，并把数据复制到所有 Follower。
当大多数 Follower 进行修改后，将数据变更操作提交。然后，Leader 会通知所有的 Follower 让它们提交修改，此时所有节点的数据达成一致。
每个 Follower 都会接收 Leader 周期性的心跳，一般为 150~300ms，如果一段时间之后还未收到心跳包，Follower 就变为 Candidate，又开始重复第 1）步。
众所周知，八卦是无处不在的！Gossip 算法，顾名思义，正是闲话家常、传闻秘事的大师，就像在某些公司的八卦圈子，你可以在里面听到各种各样奇葩的公司传闻。
Gossip 算法在网络世界中的角色，就像是各个小圈子中的消息传递者。一开始，只有几个人知道秘密，然后开始低声嘀咕，紧接着全场都知道了，传播速度之快，就像病毒一样，所以它又被称为流行病算法。
虽然不是每个圈子都能在相同的时间得知消息，但最终服务器群的所有节点都会知晓同一个事实，Gossip 协议确保的是分布式集群的最终一致性。
Gossip 协议被广泛应用于 P2P 网络，同时一些分布式的数据库，如 Redis 集群的消息同步使用的也是 Gossip 协议，另一个重大应用是被用于比特币的交易信息和区块链里信息的传播。
图片
Gossip 协议在工作时会设定一个周期时间 T，以及每个节点每个周期传播消息的节点数 K，然后，我们就能大致绘出这个八卦圈子的传播路线了：
一致性哈希（Consistent Hashing）算法，乍一听大家可能觉得这是高大上的技术名词，但其实它在分布式系统中无疑是个解决大难题的土方法，就像是中国的传统医术在现代仍能医治各种疑难杂症一样。
这个算法自从 1997 年由麻省理工学院的博士生提出后，就在分布式系统中扮演着至关重要的角色。一致性哈希算法在分布式系统中的地位可比咱们生活中的在线记账软件，解决了数据存放位置的大问题。
传统的哈希算法在节点增减时面临着数据重新分配的巨大代价，就像如果你用纸质的账本，每次账目中间有变动（比如，中间有几天忘了记账）时都得整本重写一遍，想想都头疼。而一致性哈希通过精妙地圆环结构使得节点变动只影响邻近的一小部分数据，大大降低了系统维护的复杂度。
图片
说到一致性哈希算法的基本概念，想象我们有一张圆桌，桌面上标着从 0 到 2^32（假设用的是 32 位的哈希函数）的数字，形成一个闭环：
这个算法的魅力在于，不管你的网络多么巨大，每次添加或删除一个节点，都只涉及到节点旁边的一小部分数据，而不是整个网络。这就像在一个巨大的停车场里找车位，即便是一个区域的停车位满了，你也不用担心其他地区的车位会被迁移。
当然，这个算法也有它的缺点。有时候，所有人似乎都想停在同一个车位上，这就造成了负载不均，即哈希环倾斜的情况。
图片
这时，你可能需要一些“虚拟车位”，也即是虚拟节点，让这个停车场的车辆更加均匀地分布。
这种情况我们可以这么理解：项目中某个区域的缓存快满了怎么办？
那就是加新节点！
图片
为了让缓存数据均匀分布，我们通常会采用哈希后取模的方式来确定数据归属的节点。而在加减节点的过程中，一致性哈希算法可以保证大多数 key 照旧停留在原有的车位上，而不需要把整个车场的车全部重新停一遍。
本文首先从 Paxos 算法说起，其通过提案和承诺机制，巧妙地保证在故障频发的环境下达成一致性。
接着，Raft 算法以其直观的领导选举和日志复制机制，为分布式一致性提供了通俗易懂的实现。
Gossip 算法的非正式信息传播特性，使得数据在节点间传递就像病毒般迅速，确保了数据的最终一致性。
本文链接：http://www.28at.com/showinfo-26-57932-0.html算法江湖：揭秘分布式框架下的四大高手
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
上一篇： 分布式事务框架选择与实践
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号
