CAP

  • Consistency 当一个系统在数据一致的状态下执行更新操作后，应该保证系统的数据处于一致的状态。

  • Availability 提供的服务必须处于可用状态。两个维度，有限时间内和返回结果

  • Partition tolerance 分布式系统在遇到任何网络分区故障的时候，仍然需要能够保证对外提供满足一致性和可用性的服务。 网络分区是指在分布式系统个中，不同的节点分布在不同的子网络，一些特殊原因导致子网络之间网络不联通，各个系统的网络环境被切分成了若干个孤立区域。

BASE

Base available, soft state, eventually consisten

  • Base available 出现部分障碍时，损失部分可用性。相应时间上损失和功能上损失

  • soft state 允许数据存在中间状态，并认为该中间状态存在不影响整体可用性。

  • eventually consisten 系统中所有数据副本，在经过一段时间同步后，最终到达一个一致状态。

  1. 因果一致性
  2. 读已之所写
  3. 会话一致性
  4. 单调读一致性
  5. 单调写一致性

2PC

阶段一: 提交事物请求 协调者向事务参与者发送事务内容，各个参与者尝试执行此事务，单并不提交，并将结果返回给协调者。

阶段二: 执行事物提交 如果所有参与者都全部执行成功，并收到成功请求，就向所有参与者发送提交请求。否则发送回滚请求。

原理简单，实现方便 同步阻塞，单点问题，脑裂。

3PC

阶段一: CanCommit 协调者向所有参与者发送事务内容，如果参与者认为可以数理执行事务，反馈Yes，否则反馈No.

阶段二: PreCommit 如果协调者收到的都是Yes，向所有参与者发送PreCommit请求，参与者收到PreComit后，执行事务并不提交，并将结果返回给协调者。 如果收到No或者超时，中断事务。

阶段三: doCommit 协调者发送提交请求。

Paxos算法

拜占庭将军问题: 信息在从服务器A->服务器B发送的过程中有可能被篡改。

分布式算法的两个重要属性

  • 安全性 保证永远不会发生的事情
  • 活性 最终一定会发生的事情

讲解一下我理解的Paxos算法，首先Paxos算法是一个复杂的算法，不要期望像快排那样三言两语的说清楚，首先放空一下大脑，留出一个小时的时间来学习。 Paxos是一个一致性算法，目的就是在一堆服务器中通过协议使状态保持一致，所以Paxos算法是在很多服务器之间使用的。由于服务器集群一般处于内网内，安全程度较高，所以只考虑信息的延迟和丢失而不考虑篡改。

推导

Paxos算法中有三个角色proposer, acceptor, learner. proposer用于提出议案(即一个状态说明)，acceptor可以接收proposer提出的议案，paxos算法主要用于proposer和accetpor之间，所以先不讲解learner算法。

我们的目的是:

  • 在所有提出的议案中，只有一个被选定。
  • 如果没有议案被提出，则不会有议案被选定。

安全性需求如下:

  • 只有被提出的议案才可以被选定
  • 如果某个服务器认为某个议案被选定，则这个议案必须被选定。

分析: 实现只有一个被选定的议案最简单的方式就是只允许一个acceptor，并且只接收第一个议案，但是一旦这个accepor宕机后，整个服务就会丢失。所以需要有多个acceptor。 在多个acceptor情况下，我们先假设1. 一个acceptor最多批准一个议案，并且2. 多于半数accetpor接收了某个议案，则这个议案被批准。我们现在来看一看假设是否可以满足需求。

  1. 如果只有一个议案被提出，仍然可以选出一个议案。 可以得到:

P1: 一个Acceptor必须批准它收到的第一个议案。 然而，这就导致一个新问题，没有议案得到足够多的批准。考虑n个proposer对n个acceptor提出了n个议案的情况。

所以推翻我们的假设1，即每个acceptor可以批准不止一个议案。 我们现在假设每个议案都有一个全局唯一的编号和一个不唯一的内容，即[编号，Value]可以代表一个议案。回到目的1,这里只有一个被选定，代表的是Value而不是议案了。

  1. 根据我们的目的1，只有一个被选定 由题意得:

P2: 如果编号为m,Value值为V0的议案被选定了，所有比编号m更高的且被选定的议案，Value也应该是V0. 由于每一个被选定的议案，都必须预先被批准。

所以如下推论

P2a: 如果[m, Vm]被选定了，那么所有比编号M0更高，且被Acceptor批准的议案，Value也必须是V0。

P2a可以推导出P2, 但是P2不一定能推导出P2a.但是我们的目的只需满足P2就可以了，所以如果满足P2a，一定满足P2，至于我们为什么要继续推导P2a，因为P2很难在工程上直接实现，所以要继续推导，下同

对于每一个被批准的议案，必须预先被提出。 所以得到如下推论

P2b: 如果一个议案[m, Vm]被选定之后，任何proposer产生的编号更高的议案，值必须是V0。

但是当一个议案被选定后，在没有通信的情况下，对于某个proposer，很难知道议案已经被选定。 所以Paxos作者就提出了以下推论，真是不懂是怎么想出来的

P2c: 对于任意的n和Vn,如果议案[n, Vn]被提出，存在一个由半数以上的Acceptors组成的集合S，满足下面两个条件中的一个 1.S中不存在任何批准过编号小于n的议案Acceptor。 2.S中所有Accetpor批准过的小于n的议案中，编号最大的议案的Value值是Vn。

如果满足P2c，就可以得到P2b。下面来证明P2c => P2b。 如果P2c => P2b，将其逆反得到 非P2b => 非P2c。

如果一个议案[m, Vm]被选定后，proposer产生一个一个[n, Vn]的议案， n=m+1,且Vn != Vm。由于Vm已经得到多数Acceptor批准，所以不存在这样一个集合， 该集合中不存在任何批准过编号小于n的议案的Acceptor,因为两个多数Acceptor至少有一个重合。同理也不存在满足条件2的集合。得证!

到这里推导已经停止，因为P2c已经可以从工程上实现，它规定了如何产生一个议案。 对于产生的每个议案[m, Vm]，需满足以下条件 存在一个超过半数的Acceptor集合S

  1. 要么S中没有Acceptor批准过的编号小于m的任何议案.
  2. 要么S中所有Acceptor批准的所有编号小于m的议案中，编号最大的议案的Value为Vm.

基于P2c，有如下议案生成算法

  1. Proposer选择一个新的议案编号n,向某个Acceptor发送请求，要求该Acceptor做出如下回应.
  • 保证proposer不再批准任何编号小于n的议案。
  • 如果Acceptor批准过任何议案，就向proposer反馈已经批准的编号小于n的最大编号的议案。 将该请求称为编号n议案的prepare请求。
  1. 如果propser收到来自半数以上的acceptor的结果，就产生编号为n，Value为Vn的议案，这里Vn从所有相应结果的编号中取编号最大的议案的Value值，如果Acceptor没有返回任何Value，此时Value就可以有proposer自己选择。

议案生成之后，proposer向半数以上的Acceptor发送此议案，有如下议案批准算法 Acceptor批准议案 一个Acceptor可以收到两类请求

  1. prepare请求: Acceptor可以在任意时刻相应一个prepare请求。

  2. accept请求: 在不违背Accept现有承诺的情况下，可以响应Accept请求。

优化

Acceptor只需记住它已经批准的议案的最大编号和它已经做出Prepare请求相应的议案的最大编号

综述

  • 阶段一
  1. Proposer 选择一个议案编号n，然后向Acceptor某个超过半数的子集成员发送编号为n的prepare请求。
  2. 如果一个Acceptor收到编号为n的prepare请求，且n大于该Acceptor已经相应的所有Prepare请求编号，它就会将它已经批准过的最大编号的议案作为相应反馈给Propser，同时该Accepotor承诺不再批准编号小于n的议案。
  • 阶段二
  1. 如果Proposer收到半数以上的Acceptor的关于编号为n的prepare请求，它从这些请求中选取编号最大的议案Value值作为Vn,如果没有，Value可以是任意值。
  2. 如果Acceptor收到[n, Vn]请求，只要该Acceptor尚未对编号大于n的Prepare请求作出相应，就通过这个议案。

议案获取

极端情况

Proposer P1提出编号为1的议案，进入第二阶段。Proposer P2提出编号为2的议案，进入第二阶段。然后P1在第二阶段的Accept请求被忽略，提出编号为3的议案，所以P2的Accept请求被忽略，如此往复，导致进入死循环状态。

为了避免陷入死循环，选择一个主Proposer，只有主Proposer才可以提出议案。只要主Proposer提出一个编号更高的议案，该议案将会获得批准。