vlambda博客
学习文章列表

一、CAP理论

在分布式中有一个经典的cap理论：在一个分布式系统中，可能出现网络故障或者服务器宕机的情况，我们只能保证一致性（Consistency）、可用性（Availability）、分区容错性（Partition Tolerance）中的两个。

解释：例如我们一个服务有A、B两台服务器，但是他们之间的网络相互不通时（这种情况一定会出现）。

首先一定要保证的是分区容错性，不然数据一部分数据在A，一部分在B，那么数据对于两台服务来说都是不完全的。

然后在CA中：

如果我们保证一致性C，那么就需要停止一台服务器，不然数据在A和在B的状态不一致。此时放弃了可用性

如果我们保证可用性A,（也就是两台服务都使用）用户保存数据时走到啦A，数据在A保存，用户查询时数据在B，那么数据一致性就得不到保证。

　CAP各种使用场景

CAP	适用场景	说明
CA	几乎不存在	在分布式系统中，P是不可避免的 ,除非适用单机，要提升分区可靠性，需要通过提升基础设施的可靠性实现。所以只能在CA之间做选择，这也是众多分布式中间件中CAP中为什么只有CP、AP，没有CA
CP	分布式数据库（Redis、HBase、zk、etcd）	分布式数据库极端情况下优先保证数据一致性
AP	12306购票、淘宝购物	保证服务可用，购票下单后，一段时候后系统提示余票不足

现在互联网一般是牺牲 强一致性 ，保证AP;所谓牺牲 强一致性 并不是完全放弃一致性，是说在一定条件下容许数据出现不一致，能保证 最终数据的一致性 (属于弱一致性的范畴 ) 就可以。

这里我们就引出分布式事务：比较常见的下订单扣库存，订单服务 和库存服务不在一个库中，如何保证订单不超过库存（这就是保证事务的一致性）；

为了解决这个一致性问题，保证CP，提出了两段提交/三段提交等方案(协议中同时假设节点不会发生永久性故障而且任意两个节点都可以互相通信)：

1.1 XA 两阶段提交协议

在分布式系统中，每个节点虽然可以知晓自己的操作的成功或者失败，却无法知道其他节点的操作的成功或失败。

当一个事务跨越多个节点时，为了保持事务的ACID特性，需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交(比如将更新后的数据写入磁盘等等)。

因此，二阶段提交的算法思路可以概括为：

参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。

两段提交，引入了协调者概念（协调者：本身不参与事务执行；参与者：真正执行事务的人）

第一段：准备阶段

第二段：提交阶段

准备阶段：

1. 事务协调者 给 参与者 发送Prepare消息，询问是否可以执行提交操作

2. 参与者 得到Prepare消息之后开始对 询问发起为止的所有事务进行本地操作（操作，但是不提交事务），如果都成功操作了返回成功标志；如果本地操作失败，返回失败信息

提交阶段

1. 事务协调者 拿到参与者的相应之后进行协调，如果有一个参与者失败或者超时，那么向所有参与者发出“终止”消息，所有参与者都事务回滚，释放锁资源。否则所有参与者事务全部进行本地提交（释放锁资源）

两段提交看起来是保证了数据的原子性，也就是一致性。但是还是有问题

缺点

1、同步阻塞问题：就是本地事务执行时，有其他事务提交，那么其他事务会被阻塞，也就是不能保证高并发

2、对于机器故障：

1. 如果是协调者故障，参与者会一致阻塞。

2. 如果是 协调者在第二段提交时发生故障，部分参与者收到啦，部分没有收到，此时会有不一致的数据

3. 协调者和收到确认的参与者都发生啦宕机，事务也会有不确定性。

1.2 三阶段提交协议

因为二段提交的问题，尤其是同步阻塞问题，

1、三段提交对 参与者 也引入了 超时机制，即如果二阶段长时间没有收到 协调者的消息，自动释放资源

2、同时 在第一阶段 再分成两个阶段：

协调者 给参与者发送 CanCommit命令，参与者告诉协调者是否可以执行

如果有超时或者 不可以的回复，那么调度者发送中断。

如果都回复Y那么调度者发送 doCommit，所有参与者提交事务。

完成事务

如何解决的：

但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。

2pc/3pc 都有一个单个调度者 发生故障的问题，针对这个问题，如何解决共识性问题？

对于共识性问题，我们分为存在欺骗可能的 拜占庭问题（拜占庭容错，即存在恶意指令，最终也能正确执行），和非拜占庭问题（认为所有的节点都可信任）

拜占庭将军问题

详细知识点【https://www.cnblogs.com/aspirant/p/13321816.html】

这是 莱斯利·兰伯特（Leslie Lamport）提出的：

11个拜占庭军队去攻打一个强大的帝国，这个帝国可以抵御5个军队的进攻，但是抵御不了6个军队。由于某种原因 这11个军队需要各自分开，只能通过通信配合作战（这就是我们常说的去中心化）

1. 如果其中没有叛徒，所有军队 进攻和撤退都可以 一致化，

2. 如果其中有叛徒呢？

   假如有两个叛徒 他们跟5位判断进攻的将军说, 我们支持进攻, 那么这5位将军统计发现7位支持进攻, 4位支持撤退, 将发动进攻. 又跟4位撤退的将军说, 我们支持撤退, 一统计, 5票进攻, 6票撤退, 立马撤退. 这场战争必输无疑了.

在打仗的时候，拜占庭军队内所有将军必需达成一致的共识，才能更好地赢得胜利。但是，在军队内有可能存有叛徒，扰乱将军们的决定。

这时候，在已知有成员不可靠的情况下，其余忠诚的将军需要在不受叛徒或间谍的影响下达成一致的协议。

总结归纳得出一个结论：当有t 个叛徒时，总数为 n ≥ 3t+1 才有解决方案

口头协议算法

首先口头协议定义：

A1. 任何已经发送的消息都将被正确传达;

A2. 消息的接收者知道是谁发送了消息;

A3. 消息的缺席可以被检测。

我们知道存在一个叛将时，必须再增加3个忠将才能达到最终的行动一致。为加深理解，我们将利用3个忠将1个叛将的场景对口信消息型解决方案进行推导。

在口信消息型解决方案中，首先发送消息的将军称为指挥官，其余将军称为副官。

对于3忠1叛的场景需要进行两轮作战信息协商，如果没有收到作战信息那么默认撤退。

一 、对于指挥者为忠将：

指挥者发送进攻命令，第二轮中，副将在进行作战协商，2个副将依据指挥者说是进攻，1个说撤退，最终2:1 进攻达成一致

二、对于指挥者为叛将

指挥者对一个副将发送进攻命令，但是另两个是撤退。第二轮中 副将的讨论 最终撤退，达成一致。

由此我们可以看出当叛徒为m ，只有不少于3m+1,那么才能达到一致性，但是这个m是已知的，而且m 决定 递归讨论的次数（如果有2个叛徒，需要三轮作战讨论才行）这样显然实现很困难

书面协议算法

在口头协议的前提上加两条

A4. 忠诚将军的签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现；

A5. 任何人都能验证将军签名的真伪。

基于签名消息的定义，我们可以知道，签名消息无法被伪造或者篡改。

我们同样以3三将军问题为例进行推导

一、如果A向B、C 发送进攻，C修改了A的消息，那么B会发现，此时执行A的消息。

二、叛将率先发起作战协商的场景， C向A发送进攻，向B发送撤退，A收到B 的撤退发现C 给自己的和B的不一样，此时先处理C叛将在进行协商作战。

但是我们普通的分布式系统并不会有大量被控制发出错误指令的现象，更多的是服务宕机或者网络造成的一致性问题。

此时的共识问题就是非拜占庭问题

PAXOS

参看知识博客【https://blog.csdn.net/breakout_alex/article/details/107504300】

提出三个角色：

Proposer：只要 Proposer 发的提案被半数以上 Acceptor 接受，Proposer 就认为该提案里的 value 被选定了。Acceptor：只要 Acceptor 接受了某个提案，Acceptor 就认为该提案里的 value 被选定了。Learner：Acceptor 告诉 Learner 哪个 value 被选定，Learner 就认为那个 value 被选定。

流程：

第一阶段：

1. Proposer 生成一个全局唯一并且是递增的Proposal ID【N】，向所有的 Acceptor 发送请求（这里不带内容）

2. Acceptor 接受到 Prepare请求（Proposer 发送的 【N】），并判断：

1. 如果 N 大于等于目前已通过Accept（第二阶段）的ID，那么回复 Proposer  并将自己通过 第二阶段的 最大ID的value值 发送过去，没有则返回空

2. 如果N 小于目前已知的ID，那么不回复或者回复失败。

此时Acceptor 不再接受比 此【N】小的其他的提案（Prepare请求）。

3. Proposer 判断收到Acceptor 回复的数量，如果超过一半，认为是成功的，那么就发送一个针对[N,V]提案的 Accept 请求给半数以上的Acceptor 。注意：V 就是收到的响应中编号最大的提案的 value，如果响应中不包含任何提案，那么 V 就由 Proposer 自己决定。

第二阶段：

1. 如果Acceptor 收到一个针对编号为 N 的提案的 Accept 请求，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就接受该提案

2. 发送Learner 执行

                                                        图片来源网络

缺点

在这个算法中有个问题：注意红字部分，

我们可以想一下，如果有两个顺序的提案，在第一个提案 还没到第二阶段的时候，另一个提案通过了Acceptor（Acceptor 只保证不比N小的 ProposalID）,那么因为Acceptor 对比【N】大的提案作出了响应，此时一个提案到达第二个阶段时会被忽略，那么第一个提案会重新生成一个新的ProposalID，导致第二个提案也通不过 第二阶段，此时就是循环导致 活锁。

附Paxos算法推导过程【https://www.youtube.com/watch?v=JEpsBg0AO6o】【https://www.cnblogs.com/linbingdong/p/6253479.html】

Paxos算法的设计过程就是从正确性开始的，对于分布式一致性问题，很多进程提出（Propose）不同的值，共识算法保证最终只有其中一个值被选定，Safety表述如下：

• 只有被提出（Propose）的值才可能被最终选定（Chosen）。

• 只有一个值会被选定（Chosen）。

• 进程只会获知到已经确认被选定（Chosen）的值。

Paxos以这几条约束作为出发点进行设计，只要算法最终满足这几点，正确性就不需要证明了。Paxos算法中共分为三种参与者：Proposer、Acceptor以及Learner，通常实现中每个进程都同时扮演这三个角色。

Proposers向Acceptors提出Proposal，为了保证最多只有一个值被选定（Chosen），Proposal必须被超过一半的Acceptors所接受（Accept），且每个Acceptor只能接受一个值。

为了保证正常运行（必须有值被接受），所以Paxos算法中：

P1：Acceptor必须接受（Accept）它所收到的第一个Proposal。

先来先服务，合情合理。但这样产生一个问题，如果多个Proposers同时提出Proposal，很可能会导致无法达成一致，因为没有Propopal被超过一半Acceptors的接受，因此，Acceptor必须能够接受多个Proposal，不同的Proposal由不同的编号进行区分，当某个Proposal被超过一半的Acceptors接受后，这个Proposal就被选定了。

既然允许Acceptors接受多个Proposal就有可能出现多个不同值都被最终选定的情况，这违背了Safety要求，为了保证Safety要求，Paxos进一步提出：

P2：如果值为v的Proposal被选定（Chosen），则任何被选定（Chosen）的具有更高编号的Proposal值也一定为v。

只要算法同时满足P1和P2，就保证了Safety。P2是一个比较宽泛的约定，完全没有算法细节，我们对其进一步延伸：

P2a：如果值为v的Proposal被选定（Chosen），则对所有的Acceptors，它们接受（Accept）的任何具有更高编号的Proposal值也一定为v。

如果满足P2a则一定满足P2，显然，因为只有首先被接受才有可能被最终选定。但是P2a依然难以实现，因为acceptor很有可能并不知道之前被选定的Proposal（恰好不在接受它的多数派中），因此进一步延伸：

P2b：如果值为v的Proposal被选定（Chosen），则对所有的Proposer，它们提出的的任何具有更高编号的Proposal值也一定为v。

更进一步的：

P2c：为了提出值为v且编号为n的Proposal，必须存在一个包含超过一半Acceptors的集合S，满足(1) 没有任何S中的Acceptors曾经接受（Accept）过编号比n小的Proposal，或者(2) v和S中的Acceptors所接受过(Accept)的编号最大且小于n的Proposal值一致。

满足P2c即满足P2b即满足P2a即满足P2。至此Paxos提出了Proposer的执行流程，以满足P2c：

1. Proposer选择一个新的编号n，向超过一半的Acceptors发送请求消息，Acceptor回复: (a)承诺不会接受编号比n小的proposal，以及(b)它所接受过的编号比n小的最大Proposal（如果有）。该请求称为Prepare请求。

2. 如果Proposer收到超过一半Acceptors的回复，它就可以提出Proposal，Proposal的值为收到回复中编号最大的Proposal的值，如果没有这样的值，则可以自由提出任何值。

3. 向收到回复的Acceptors发送Accept请求，请求对方接受提出的Proposal。

仔细品味Proposer的执行流程，其完全吻合P2c中的要求，但你可能也发现了，当多个Proposer同时运行时，有可能出现没有任何Proposal可以成功被接受的情况（编号递增的交替完成第一步），这就是Paxos算法的Liveness问题，或者叫“活锁”，论文中建议通过对Proposers引入选主算法选出Distinguished Proposer来全权负责提出Proposal来解决这个问题，但是即使在出现多个Proposers同时提出Proposal的情况时，Paxos算法也可以保证Safety。

接下来看看Acceptors的执行过程，和我们对P2做的事情一样，我们对P1进行延伸：

P1a：Acceptor可以接受（Accept）编号为n的Proposal当且仅当它没有回复过一个具有更大编号的Prepare消息。

易见，P1a包含了P1，对于Acceptors：

1. 当收到Prepare请求时，如果其编号n大于之前所收到的Prepare消息，则回复。

2. 当收到Accept请求时，仅当它没有回复过一个具有更大编号的Prepare消息，接受该Proposal并回复。

以上涵盖了满足P1a和P2b的一套完整一致性算法。

面试精简答案：Paxos算法解决的是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各个节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能够得到一个一致的状态。为了保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。zookeeper使用的zab算法是该算法的一个实现。在Paxos算法中，有三种角色：Proposer (提议者),Acceptor（接受者），Learners（记录员）

RAFT

不同于paxos从分布式的一致性推导出来，raft是从多副本中推出来的。raft和paxos实现了相同的功能，只不过raft使用了更强的假设

Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：

• Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。

• Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。

• Candidate：Leader选举过程中的临时角色。

其他名称：

term ：任期。每更换一次Leader 那么 term+1;

heartbeat：心跳，比term 要短。

流程

1. 选举Leader：Leader 会在每个term 内向Follower 发送多次heartbeat（心跳），如果在一个term内没有收到Leader 的heartbeat消息，那么Follower 就认为Leader已经挂掉了，会变成Candidate 角色，向其他Follower发送选举请求

   在raft论文《In Search of an Understandable Consensus Algorithm (Extended Version)》中，

   每个server启动的时候都有一个选举超时延迟，这个选举超时延迟是随机生成的处于某一范围内的值，

   因此该延迟短的server先发起竞选——变为candidate,term+1,向其他server发送请求投票RPC，

   因为其最先发起竞选，term最大，因此能被选为leader。

1. 如果超过一半的Follower 回复OK，那么就成为Leader,term+1

2. 如果 有人比自己向其他Follower 早发送选举请求，那么其他Follower会拒绝自己的选举请求，选择最早的当Learder

3. 如果票数时一半一半，那么等待Term 超时，进行第二次选举，直到新的Leader 诞生。

2. 写入参数（日志）

   客户端写入只能由Leader 向其他Foller写入

1. Leader接受 用户写入的命令，将操作写入日志

2. Leader向Follower节点发送日志，其他Follower节点如果认为可以，返回Ok

3. Leader 收到超过一半的 OK，认为是成功的，提交事务（先返回客户端ok，在向Follower发送事务提交命令）

4. Leader 向Follower 发送事务提交

问题：

1、但是如果因为某些问题（比如网络隔离），一部分Lollower被隔离了（假设超过一半），此时用户向Leader 写入，Leader 没有收到超过一半的回复，就认为失败。

此时单独隔离的Lollower 应为超过了一半，所以会重新选举出新的Leader ，此时客户在写入时，新Leader会得到一半的回复，此时回复客户完成。

2、等到网络恢复稳定，此时会出现两个Leader ,之前的Leader 收到新的Leader 的heartbeat（心跳），发现这个heartbeat 的term 比自己大，所以老Leader 会卸任，回退同步新Leader的日志。

成员变更问题

成员变更，不能当作普通的一致性算法进行，因为投票系统会发生变化

Leader 发送成员变更的配置，超过半数Follower响应，此时Leader 提交事务，Follower 提交并变更。

但是每个Follower 变更的时间不同导致 会出现 新老配置共存的状态，这个就破坏了高可用。

Raft两阶段成员变更过程如下：

1. Leader收到成员变更请求从Cold切成Cold,new；

2. Leader在本地生成一个新的log entry，其内容是Cold∪Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该log entry复制至Cold∪Cnew中的所有副本。在此之后新的日志同步需要保证得到Cold和Cnew两个多数派的确认；

3. Follower收到Cold∪Cnew的log entry后更新本地日志，并且此时就以该配置作为自己的成员配置；

4. 如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，Leader就提交这条log entry并切换到Cnew；

5. 接下来Leader生成一条新的log entry，其内容是新成员配置Cnew，同样将该log entry写入本地日志，同时复制到Follower上；

6. Follower收到新成员配置Cnew后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置，并且如果发现自己不在Cnew这个成员配置中会自动退出；

7. Leader收到Cnew的多数派确认后，表示成员变更成功，后续的日志只要得到Cnew多数派确认即可。Leader给客户端回复成员变更执行成功。

可从数学上严格证明，只要每次只允许增加或删除一个成员，Cold与Cnew不可能形成两个不相交的多数派。

一阶段成员变更：

• 成员变更限制每次只能增加或删除一个成员（如果要变更多个成员，连续变更多次）。

• 成员变更由Leader发起，Cnew得到多数派确认后，返回客户端成员变更成功。

• 一次成员变更成功前不允许开始下一次成员变更，因此新任Leader在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。

• Leader只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步。

关于redise哨兵模式

想要redis 高可用，需要用到主从模式，但是如果主节点宕机不可用 需要人工修改主节点才能写入

所以引入了哨兵机制，

哨兵机制是怎样判断主节点down调的？

哨兵机制是建立了多个哨兵节点，它们共同监控数据节点的运行状况。同时哨兵节点之间也互相通信。交换对主从节点的监控状况。下面提到两个概念：

主观下线和客观下线：一个哨兵节点判定主节点down掉是主观下线。只有半数个哨兵节点都主观判定主节点down掉，此时多个哨兵节点交换主观判定结果，才会判定主节点客观下线。

基本上哪个哨兵节点最先判断出这个主节点客观下线，就会在各个哨兵节点中发起投票机制，每个哨兵都投自己为领导者。最终被投为领导者的哨兵节点完成主从自动化切换的过程。当判断为主观下线时，不会进行主从切换过程。