分布式｜算法再认识

CAP理论是Eric Brewer教授在2000年提出的，是描述分布式一致性的三个维度，分别是指：

（1）一致性（Consistency）

每次读操作都能保证返回的是最新数据；在分布式系统中，如果能针对一个数据项的更新执行成功后，所有的请求都可以读到其最新的值，这样的系统就被认为具有严格的一致性。

（2）可用性（Availablity）

任何一个没有发生故障的节点，会在合理的时间内返回一个正常的结果，也就是对于每一个请求总能够在有限时间内返回结果。

（3）分区容忍性（Partition-torlerance）

当节点间出现网络分区，照样可以提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。那么，什么是网络分区呢？分区是系统中可能发生的故障之一，可能有节点暂时无法提供服务：发生了像长时间GC、CPU死循环、链接池耗尽或者是网络通信故障等问题。

CAP指出，一个分布式系统只能满足三项中的两项而不可能满足全部三项。举例来看：如下图所示，假设有五个节点：n1~n5 ，因网络分区故障被分成两组：[n1、n2]和[n3~n5]，那么当n1处理客户端请求时（为了支持"容忍网络分区"，即支持 P）：

如果要保证C(一致性)，那么它需要把消息复制到所有节点，但是网络分区导致无法成功复制到n3~n5，所以它只能返回"处理失败"的结果给客户端。（这时系统就处于不可用状态，即丧失了A）
如果要保证可用性A，那么n1就只能把消息复制到n2，而不用复制到n3~n5(或者无视复制失败/超时)，但n3同时也可能在处理客户端请求，n3也为了保证A而做了同样的处理。那么 [n1、n2]和[n3~n5]的状态就不一致了，于是就丧失了C(一致性)。
如果不容忍网络分区，则P（分区容忍性）不能满足。

既然CAP理论无法全部满足，为了指导工业实现，就需要降低标准，因此出现了BASE理论。

BASE理论是eBay的架构师Dan Pritchett提出的，它的思想是：“即使无法做到强一致性，但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性” 。

BASE理论有三项指标：

基本可用（Basically Available）：是指分布式系统在出现不可预知故障的时候，允许损失部分可用性：比如响应时间、功能降级等；
软状态（ Soft State）：也称为弱状态，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点之间进行数据同步的过程存在延时；
最终一致性（ Eventual Consistency）：强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达成一致的状态。

BASE理论面向的是大型高可用、可扩展的分布式系统。BASE通过牺牲强一致性来获得可用性，并允许数据短时间内的不一致，但是最终达到一致状态。

Raft 特性：

强领导者（Strong Leader）：Raft 使用一种比其他算法更强的领导形式。例如，日志条目只从领导者发送向其他服务器。这样就简化了对日志复制的管理，使得 Raft 更易于理解。
领导选取（Leader Selection）：Raft 使用随机定时器来选取领导者。这种方式仅仅是在所有算法都需要实现的心跳机制上增加了一点变化，它使得在解决冲突时更简单和快速。
成员变化（Membership Change）：Raft 为了调整集群中成员关系使用了新的联合一致性（joint consensus）的方法，这种方法中大多数不同配置的机器在转换关系的时候会交迭（overlap）。这使得在配置改变的时候，集群能够继续操作。

Raft与Multi-Paxos中相似的概念：

Raft与Multi-Paxos的不同：

基于Paxos协议的数据同步与传统主备方式最大的区别在于：Paxos只需超过半数的副本在线且相互通信正常，就可以保证服务的持续可用，且数据不丢失。

0 人点赞