博客

Paxos

两阶段协议和三阶段协议并不能保证数据的一致性，Paxos算法需要解决的问题是如何在一个可能发生异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生什么异常，都不会破坏整个系统的一致性。

前言

拜占庭帝国有许多支军队，不同军队的将军之间必须制订一个统一的行动计划，从而做出进攻或者撤退的决定，同时，各个将军在地理上都是被分隔开来的，只能依靠军队的通讯员来进行通讯。然而，在所有的通讯员中可能会存在叛徒，这些叛徒可以任意篡改消息，从而达到欺骗将军的目的。


这就是著名的“拜占廷将军问题”

。从理论上来说，在分布式计算领域，试图在异步系统和不可靠的通道上来达到一致性状态是不可能的，因此在对一致性的研究过程中，都往往假设信道是可靠的。而事实上，大多数系统都是部署在同一个局域网中的，因此消息被篡改的情况非常罕见;另一方面，由于硬件和网络原因而造成的消息不完整问题只需一套简单的校验算法即可避免—一因此，在实际工程实践中，可以假设不存在拜占庭问题，也即假设所有消息都是完整的，没有被篡改的。那么，在这种情况下需要什么样的算法来保证一致性呢？

一、背景

假设有一组可以提出提案的进程集合，那么对于一个一致性算法来说需要保证以下几点:

• 在这些被提出的提案中，只有一个会被选定。
• 如果没有提案被提出，那么就不会有被选定的提案。
• 当一个提案被选定后，进程应该可以获取被选定的提案信息

对于一致性来说，安全性（ Safety）需求如下:

• 只有被提出的提案才能被选定（ Chosen）。
• 只能有一个值被选定。
• 如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个。

在对 Paxos算法的讲解过程中，我们不去精确地定义其活性（ Liveness）需求，从整体上来说， Paxos算法的目标就是要保证最终有一个提案会被选定，当提案被选定后，进程最终也能获取到被选定的提案

在该一致性算法中，有三种参与角色，我们用

Proposer、 Acceptor和 Learner

来表示。

在具体的实现中，一个进程可能充当不止一种角色，在这里我们并不关心进程如何映射

到各种角色。假设不同参与者之间可以通过收发消息来进行通信，那么

二、一致性

一致性模型：

 - 弱一致性：最终一致性
 - 强一致性：同步；Paxos；Raft；ZAB；

数据不能存在单个节点上；所以需要对每个操作对副本集群进行更新，也就是state machine replication 的共识算法；Paxos是一个共识算法；

强一致性的算法——主从同步

主从同步复制：

 1. Master接收写请求
 2. Master复制日志至slave
 3. Master等待，知道所有的从库返回

问题：一个节点失败，Master阻塞，导致震哥哥集群不可用，保证了一致性，但是可用性却大大降低。

强一致性的算法——多数派

基本思想：
每次写入都保证写入大于N/2个节点，每次读保证从大于N/2个节点读；

问题：在并发环境下，无法保证系统的正确性，顺序非常重要；

强一致性的算法——Basice Paxos

以法律制定为背景：

角色：
client：民众
prposer：议员，接收client的请求，发生冲突的时候进行冲突解决
accpetor：提议投票和接收者
learner：提议接收者，backup，备份，不参与投票

阶段：

• prepare：properser提出一个提案，编号为N,此N大于这个proposer之前提出提案编号。请求accept的quorum接受；
• promise：如果N大于此前acceptor之前接受的任何填编号，则接受，否则拒绝
• accept：如果达到了多数派，proposer会发出acceptor请求，此请求包含提案编号N,以及提案内容
• accepted：如果此accepto在此期间没有收到任何编号大于N的提案，则接受此提案的内容

同学聚会出去玩
Client: 提出问题 咱们下面要去哪里玩呢
Propose： 鬼点子王 A B ... 开始发表意见/提案（ID自增长）
Acceptor： 嗯嗯,不错,这个也不错呢,这个也不错, 点子的接受者,但是接受的方式很简单 谁的点子是最新提出的就听投谁的（事务ID / 提案ID）
Learner：没有主见的家伙,很随意,什么都是随便阿随便,然后埋头玩手机的那群人,只等着他们讨论结束跟着他们混

提案通过很简单 过半就行
A开始提案A1 - 先去吃饭吧, 然后Acceptosr开始投票,嗯嗯.不错不错,可以可以,,,还没有过半通过
这时候
B又开始新提案B2  去看电影吧  然后Acceptor又开始新一轮投票 因为B提案ID比A的大 所以大家都比较接受B的题按

	如果投票过半那就直接按B提案大家一起去看电影 然后跟旁边的几个玩手机的说 咱们去看电影吧 然后大家就一起去看电影了
	如果投票没过半A那家伙不甘心肚子饿了就是想去吃饭又提出提案A3 大家又开始投票
	B也不甘示弱也提案B4 这样两个人没完没了的 大家都被弄晕了
	
	冲突要打架了,所以才有了老师后面说的等个时间
	A提案的时候  B也想提案不过得先等个10s 要是10S内大家都过半A的提议 那就听A的去吃饭 如果10S还没过半那就执行B的提案
	

问题：潜在问题，多个proposer带来活锁； 提案A先请求，紧接着被提案B打断，这时候提案C又重新请求，提案B又被打断； 工业界解决：随机时间休眠；

强一致性的算法——Multi Paxos

只有一个proposer,可以解决活锁的问题

角色：
client：民众
prposer（leader）：议员，接收client的请求，发生冲突的时候进行冲突解决
accpetor：提议投票和接收者
learner：提议接收者，backup，备份，不参与投票

基本流程：



进一步简化角色：proposer和acceptor进行合并；

强一致性的算法——Raft

可以理解为multi paxos的简化版本；

把达到共识划分为三个子问题：

• Leader Election：timeout选leader
• Log Replication：心跳机制，先写日志再commit
• Safety：失败，发生分区
  
  重定义角色：
• leader：整个集群只有一个leader；
• follower：只会从leader同步日志；
• candidate（临时角色）：节点竞选leader前的状态

在竞选leader的时候，如果刚开始所有人都投自己，所以会出现平票的情况，
会给所有candidate设置一个随机的timeout，率先苏醒的节点去请求其他节点，
其他节点就必须把票投给该节点；

一致性并不代表完全正确；

三个可能的情况：成功，失败，unknown

强一致性的算法——ZAB

可以理解为multi paxos的简化版本,基本与raft相同；

把达到共识划分为三个子问题：

• Leader Election：timeout选leader
• Log Replication：心跳机制，先写日志再commit
• Safety：失败，发生分区
  
  重定义角色：
• leader：整个集群只有一个leader；
• follower：只会从leader同步日志；
• candidate（临时角色）：节点竞选leader前的状态

总结

提示：这里对文章进行总结：

例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。