可靠与可用、共识与一致
保证数据的可靠性，一般采用数据复制(副本)的思想。以同步为代表的数据复制方法，叫做状态转移（State Transfer）。这类方法属于比较符合人类思维的可靠性保障手段，但通常要以牺牲可用性为代价.
系统高可用和高可靠之间的矛盾，是由于增加机器数量反而降低了可用性带来的。为缓解这个矛盾，在分布式系统里主流的数据复制方法，是以操作转移（Operation Transfer）为基础的。我们想要改变数据的状态，除了直接将目标状态赋予它之外，还有另一种常用的方法，就是通过某种操作，把源状态转换为目标状态。
能够使用确定的操作，促使状态间产生确定的转移结果的计算模型，在计算机科学中被称为状态机（State Machine）。
状态机有一个特性：任何初始状态一样的状态机，如果执行的命令序列一样，那么最终达到的状态也一样。在这里我们可以这么理解这个特性，要让多台机器的最终状态一致，只要确保它们的初始状态和接收到的操作指令都是完全一致的就可以。
无论这个操作指令是新增、修改、删除或者其他任何可能的程序行为，都可以理解为要将一连串的操作日志正确地广播给各个分布式节点。
广播指令与指令执行期间，允许系统内部状态存在不一致的情况，也就是不要求所有节点的每一条指令都是同时开始、同步完成的，只要求在此期间的内部状态不能被外部观察到，且当操作指令序列执行完成的时候，所有节点的最终的状态是一致的。这种模型，就是状态机复制（State Machine Replication）。
在分布式环境下，考虑到网络分区现象是不可能消除的，而且可以不必去追求系统内所有节点在任何情况下的数据状态都一致，所以采用的是“少数服从多数”的原则。
也就是说，一旦系统中超过半数的节点完成了状态的转换，就可以认为数据的变化已经被正确地存储在了系统当中。这样就可以容忍少数（通常是不超过半数）的节点失联，使得增加机器数量可以用来提升系统整体的可用性。在分布式中，这种思想被叫做Quorum机制)。
根据这些讨论，我们需要设计出一种算法，能够让分布式系统内部可以暂时容忍存在不同的状态，但最终能够保证大多数节点的状态能够达成一致；同时，能够让分布式系统在外部看来，始终表现出整体一致的结果。
这个让系统各节点不受局部的网络分区、机器崩溃、执行性能或者其他因素影响，能最终表现出整体一致的过程，就是各个节点的协商共识（Consensus）。
这里需要注意的是，共识（Consensus）与一致性（Consistency）是有区别的：一致性指的是数据不同副本之间的差异，而共识是指达成一致性的方法与过程。
Paxos
Basic Paxos算法的工作流程
Paxos算法将分布式系统中的节点分为提案节点、决策节点和记录节点三类。
提案节点：称为Proposer，提出对某个值进行设置操作的节点，设置值这个行为就是提案（Proposal）。值一旦设置成功，就是不会丢失也不可变的。
需要注意的是，Paxos是典型的基于操作转移模型而非状态转移模型来设计的算法，所以这里的“设置值”不要类比成程序中变量的赋值操作，而应该类比成日志记录操作。
决策节点：称为Acceptor，是应答提案的节点，决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受，就意味着这个提案被批准（Accept）。提案被批准，就意味着该值不能再被更改，也不会丢失，且最终所有节点都会接受它。
记录节点：被称为Learner，不参与提案，也不参与决策，只是单纯地从提案、决策节点中学习已经达成共识的提案。比如，少数派节点从网络分区中恢复时，将会进入这种状态。
在使用Paxos算法的分布式系统里，所有的节点都是平等的，它们都可以承担以上某一种或者多种角色。
不过，为了便于确保有明确的多数派，决策节点的数量应该被设定为奇数个，且在系统初始化时，网络中每个节点都知道整个网络所有决策节点的数量、地址等信息。另外，在分布式环境下，如果说各个节点“就某个值（提案）达成一致”，代表的意思就是“不存在某个时刻有一个值为A，另一个时刻这个值又为B的情景”。
整个过程的时序图如下所示：
关于Basic Paxos的文档见: 链接
Multi Paxos
Multi Paxos对Basic Paxos的核心改进是，增加了“选主”的过程：
- 提案节点会通过定时轮询（心跳），确定当前网络中的所有节点里是否存在一个主提案节点；
- 一旦没有发现主节点存在，节点就会在心跳超时后使用Basic Paxos中定义的准备、批准的两轮网络交互过程，向所有其他节点广播自己希望竞选主节点的请求，希望整个分布式系统对“由我作为主节点”这件事情协商达成一致共识；
- 如果得到了决策节点中多数派的批准，便宣告竞选成功。
当选主完成之后，除非主节点失联会发起重新竞选，否则就只有主节点本身才能够提出提案。此时，无论哪个提案节点接收到客户端的操作请求，都会将请求转发给主节点来完成提案，而主节点提案的时候，也就无需再次经过准备过程，因为可以视作是经过选举时的那一次准备之后，后续的提案都是对相同提案ID的一连串的批准过程。
我们也可以通俗地理解为：选主过后，就不会再有其他节点与它竞争，相当于是处于无并发的环境当中进行的有序操作，所以此时系统中要对某个值达成一致，只需要进行一次批准的交互即可。
从整体来看，当节点有了选主机制的支持后，就可以进一步简化节点角色，不必区分提案节点、决策节点和记录节点了，可以统称为“节点”，节点只有主（Leader）和从（Follower）的区别。此时的协商共识的时序图如下
注：三元组(id, i, value)，表示需要给主节点增加一个“任期编号”，这个编号必须是严格单调递增的，以应付主节点陷入网络分区后重新恢复，但另外一部分节点仍然有多数派，且已经完成了重新选主的情况，此时必须以任期编号大的主节点为准。
在这个理解的基础上，我们换一个角度来重新思考“分布式系统中如何对某个值达成一致”这个问题，可以把它分为下面三个子问题来考虑：
- 如何选主（Leader Election）
- 如何把数据复制到各个节点上（Entity Replication）
- 如何保证过程是安全的（Safety）
如何选主
基于Basic Paxos算法，有提案节点发起提案，决策节点选取最大提案ID后，然后接受其节点为提案节点，因此可作为主节点。
如何在网络间复制数据
在正常情况下，当客户端向主节点发起一个操作请求后，比如提出“将某个值设置为X”，数据复制的过程为：
- 主节点将X写入自己的变更日志，但先不提交，接着把变更X的信息在下一次心跳包中广播给所有的从节点，并要求从节点回复“确认收到”的消息；
- 从节点收到信息后，将操作写入自己的变更日志，然后给主节点发送“确认签收”的消息；
- 主节点收到过半数的签收消息后，提交自己的变更、应答客户端并且给从节点广播“可以提交”的消息；
- 从节点收到提交消息后提交自己的变更，数据在节点间的复制宣告完成。
异常情况下，例如网络分区，节点下线，则重新走重新选主，然后重新发起提交，走ACK确认节点数大于一半节点逻辑。
Raft
基于Multi Paxos算法，把共识问题分解为“Leader Election”、“Entity Replication”和“Safety”三个问题来思考、解决的解题思路就是Raft.
参考论文：一种可以让人理解的共识算法（In Search of an Understandable Consensus Algorithm）
Raft是etcd、LogCabin、Consul等重要分布式程序的实现基础。
Gossip协议(流言传播)
Paxos、Raft、ZAB等分布式算法经常会被称作是“强一致性”的分布式共识协议（从系统外部来看，系统整体是强一致性的，尽管内部存在不一致的状态）
Gossip: 一种代表最终一致性的分布式协议, 首先必须强调它所解决的问题并不是直接与Paxos、Raft这些共识算法等价的，只是基于Gossip之上可以通过某些方法去实现与Paxos、Raft相类似的目标而已.（达成最终一致性)
工作流程如下：
- 如果有某一项信息需要在整个网络中的所有节点中传播，那从信息源开始，选择一个固定的传播周期（比如1秒），随机选择与它相连接的k个节点（称为Fan-Out）来传播消息。
- 如果一个节点收到消息后发现这条消息之前没有收到过，就会在下一个周期内，把这条消息发送给除了给它发消息的那个节点之外的相邻的k个节点，直到网络中所有节点都收到了这条消息。尽管这个过程需要一定的时间，但理论上网络的所有节点最终都会拥有相同的消息。
Gossip传播过程的示意图如下所示：
根据示意图和Gossip的过程描述，我们很容易发现，Gossip对网络节点的连通性和稳定性几乎没有任何要求，表现在两个方面：
若有收获，就点个赞吧
0 人点赞
