CAP 原则
一个分布式系统中，Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性），三者不可得兼。
- 一致性（C）：在分布式系统中的所有数据备份，在同一时刻是否同样的值。
- 可用性（A）：保证每个请求不管成功或者失败都有响应。
- 分区容忍性（P）：系统中任意信息的丢失或失败不会影响系统的继续运作。
- CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但放弃P的同时也就意味着放弃了系统的扩展性，也就是分布式节点受限，没办法部署子节点，这是违背分布式系统设计的初衷的。传统的关系型数据库RDBMS：Oracle、MySQL就是CA。
- CP without A：如果不要求A（可用），相当于每个请求都需要在服务器之间保持强一致，而P（分区）会导致同步时间无限延长(也就是等待数据同步完才能正常访问服务)，一旦发生网络故障或者消息丢失等情况，就要牺牲用户的体验，等待所有数据全部一致了之后再让用户访问系统。设计成CP的系统其实不少，最典型的就是分布式数据库，如Redis、HBase等。对于这些分布式数据库来说，数据的一致性是最基本的要求，因为如果连这个标准都达不到，那么直接采用关系型数据库就好，没必要再浪费资源来部署分布式数据库。
- AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。典型的应用就如某米的抢购手机场景，可能前几秒你浏览商品的时候页面提示是有库存的，当你选择完商品准备下单的时候，系统提示你下单失败，商品已售完。这其实就是先在 A（可用性）方面保证系统可以正常的服务，然后在数据的一致性方面做了些牺牲，虽然多少会影响一些用户体验，但也不至于造成用户购物流程的严重阻塞。
ACID 原则
数据库事务
原子性(Atomicity)：是指一个事务要么全部执行，要么不执行。
- 比如你从取款机取钱，这个事务可以分成两个步骤：1划卡，2出钱。不可能划了卡，而钱却没出来。这两步必须同时完成，要么就不完成。
一致性(Consistency)：是指事务的运行并不改变数据库中数据的一致性。
例如，完整性约束了a+b=10，一个事务改变了a，那么b也应该随之改变。
独立性(Isolation）也称作隔离性，是指两个以上的事务不会出现交错执行的状态。因为这样可能会导致数据不一致，更加具体的来讲，就是事务之间的操作是独立的。
持久性(Durability）：指事务执行成功以后，该事务对数据库所作的更改便是持久的保存在数据库之中，不会无缘无故的回滚。
BASE 原则
BASE是 Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终一致性）三个短语的简写，BASE是对CAP中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的结论，是基于CAP定理逐步演化而来的，其核心思想是即使无法做到强一致性（Strong consistency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性（Eventual consistency）。接下来我们着重对BASE中的三要素进行详细讲解。
基本可用
基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性——但请注意，这绝不等价于系统不可用，以下两个就是“基本可用”的典型例子。
- 响应时间上的损失：正常情况下，一个在线搜索引擎需要0.5秒内返回给用户相应的查询结果，但由于出现异常（比如系统部分机房发生断电或断网故障），查询结果的响应时间增加到了1~2秒。
- 功能上的损失：正常情况下，在一个电子商务网站上进行购物，消费者几乎能够顺利地完成每一笔订单，但是在一些节日大促购物高峰的时候，由于消费者的购物行为激增，为了保护购物系统的稳定性，部分消费者可能会被引导到一个降级页面。
弱状态
也称为软状态，和硬状态相对，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据听不的过程存在延时。
最终一致性
最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性
因果一致性是指，如果进程A在更新完某个数据项后通知了进程B，那么进程B之后对该数据项的访问都应该能够获取到进程A更新后的最新值，并且如果进程B要对该数据项进行更新操作的话，务必基于进程A更新后的最新值，即不能发生丢失更新情况。与此同时，与进程A无因果关系的进程C的数据访问则没有这样的限制。
一致性模型
原子一致性（Atomic Consistency）
也称为：强一致性（Strict Consistency）线性一致性（Linearizable Consistency）
两个要求：
- 任何一次读都能读到某个数据的最近一次写的数据。
- 系统中的所有进程，看到的操作顺序，都和全局时钟下的顺序一致。
简言之，在任意时刻，所有节点中的数据是一样的。
例如，对于关系型数据库，要求更新过的数据能被后续的访问都能看到，这是强一致性。
顺序一致性（Sequential Consistency）
两个要求：
- 任何一次读都能读到某个数据的最近一次写的数据。
- 系统的所有进程的顺序一致，而且是合理的。
和原子一致性的区别是，不需要和全局时钟下的顺序一致，错的话一起错，对的话一起对。
不满足原子一致性和顺序一致性，属于弱一致性（Soft Consistency）
最终一致性
弱一致性的一种特殊形式。最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。
与弱一致性的区别
弱一致性即使过了不一致时间窗口，后续的读取也不一定能保证一致。
因果一致性
因果一致性是指，如果进程A在更新完某个数据项后通知了进程B，那么进程B之后对该数据项的访问都应该能够获取到进程A更新后的最新值，并且如果进程B要对该数据项进行更新操作的话，务必基于进程A更新后的最新值，即不能发生丢失更新情况。与此同时，与进程A无因果关系的进程C的数据访问则没有这样的限制。
读己之所写一致性
读己之所写是指，进程A更新一个数据项之后，它自己总是能够访问到更新过的最新值，而不会看到旧值。也就是说，对于单个数据获取者而言，其读取到的数据一定不会比自己上次写入的值旧。因此，读己之所写也可以看作是一种特殊的因果一致性。
会话一致性
会话一致性将对系统数据的访问过程框定在了一个会话当中：系统能保证在同一个有效的会话中实现“读己之所写”的一致性，也就是说，执行更新操作之后，客户端能够在同一个会话中始终读取到该数据项的最新值。
单调一致性
<未知>
单调读一致性
一个进程从系统中读取出一个数据项的某个值后，那么系统对于该进程后续的任何数据访问都不应该返回更旧的值。
单调写一致性
一个系统需要能够保证来自同一个进程的写操作被顺序地执行。
一致性协议
两阶段提交协议
两阶段提交将提交过程划分为连续的两个阶段：表决阶段(Voting)和提交阶段(Commit)。假设在没有故障发生的情形下，两阶段提交协议由下列操作序列构成，如下图所示：
协调者的有限状态机如下图：
如上图所示：协调者初始处于INIT状态，当接收到系统发出的Commit消息后，向参与者多播Vote-request消息后转入WAIT状态，在此进入阻塞状态，因为要等待所有参与者发送返回的消息，当收到所有参与者的返回消息后，如果其中包含Vote-Abort消息，则多播Global-abort消息后转入ABORT状态，否则多播Global-commit消息后转入COMMIT状态。
参与者的有限状态机如下图：
如上图所示：参与者初始处于INIT状态，当接收到Vote-Request消息时，发出Vote-commit会转入READY状态，告诉协调者已经准备做好提交准备，否则就返回一个VOTE-ABORT消息。等待协调者行为，如果收到Global-Abort消息，就会进入Abort状态，如果收到Global-commit消息，就会转入COMMIT状态。
从两者的有限状态机可以看出，在所有可能状态中，存在三个阻塞状态：协调者的WAIT状态，参与者的INIT状态和READY状态。
三阶段提交协议(3PC)
3PC就是在2PC基础上将2PC的提交阶段细分位两个阶段：预提交阶段和提交阶段。
3PC中协调者的有限状态机如下图：
3PC中参与者的有限状态机如下图：
向量时钟协议
通过向量空间祖先继承的关系比较, 使数据保持最终一致性,这就是向量时钟的基本定义。
下面给出一个场景来说明向量时钟的作用：
Vector Clock就是为了解决这种问题而设计的，简单来说，就是为每个商议结果加上一个时间戳，当结果改变时，更新时间戳。所以加上时间戳之后，我们再一次描述上面的场景，如下：
以上这个决策用到了向量时钟，有个图还比较清晰了说明整个过程：
RWN协议
NWR是一种在分布式存储系统中用于控制一致性级别的一种策略。在Amazon的Dynamo云存储系统中，就应用NWR来控制一致性。
让我们先来看看这三个字母的含义：
N：在分布式存储系统中，有多少份备份数据
W：代表一次成功的更新操作要求至少有w份数据写入成功
R： 代表一次成功的读数据操作要求至少有R份数据成功读取
NWR值的不同组合会产生不同的一致性效果，当W+R>N的时候，整个系统对于客户端来讲能保证强一致性。当W+R 以常见的N=3、W=2、R=2为例：
N=3，表示，任何一个对象都必须有三个副本（Replica），W=2表示，对数据的修改操作（Write）只需要在3个Replica中的2个上面完成就返回，R=2表示，从三个对象中要读取到2个数据对象，才能返回。
在分布式系统中，数据的单点是不允许存在的。即线上正常存在的Replica数量是1的情况是非常危险的，因为一旦这个Replica再次错误，就 可能发生数据的永久性错误。假如我们把N设置成为2，那么，只要有一个存储节点发生损坏，就会有单点的存在。所以N必须大于2。N约高，系统的维护和整体 成本就越高。工业界通常把N设置为3。
当W是2、R是2的时候，W+R>N，这种情况对于客户端就是强一致性的。
在上图中，如果R+W>N,则读取操作和写入操作成功的数据一定会有交集（如图中的B），这样就可以保证一定能够读取到最新版本的更新数据，数据的强一致性得到了保证。在满足数据一致性协议的前提下，R或者W设置的越大，则系统延迟越大，因为这取决于最慢的那份备份数据的响应时间。而如果R+W<=N，则无法保证数据的强一致性，因为成功写和成功读集合可能不存在交集，这样读操作无法读取到最新的更新数值，也就无法保证数据的强一致性。
在具体实现系统时，仅仅依靠NWR协议还不能完成一致性保证，因为在上述过程中，当读取到多个备份数据时，需要判断哪些数据是最新的，如何判断数据的新旧？这需要向量时钟来配合，所以对于Dynamo来说，是通过NWR协议结合向量时钟来共同完成一致性保证的。
Gossip 协议
Gossip协议的整体流程非常简单，传输示意图见上图.初始由几个节点发起消息，这几个节点会将消息的更新内容告诉自己周围的节点，收到消息的节点再将这些信息告诉周围的节点。依照这种方式，获得消息的节点会越来越多，总体消息的传输规模会越来越大，消息的传偶速度也越来越快。虽然不是每个节点都能在相同的时间达成一致，但是最终集群中所有节点的信息必然是一致的。Gossip协议确保的是分布式集群的最终一致性。
预先设定好消息更新的周期时间T，以及每个节点每个周期能够传播的周围节点数2，我们可以得到大致的消息更新流程如下：
- 节点A收到新消息并更新
- 节点A将收到的消息传递给与之直接相连的B,C
- B,C各自将新更新的消息传给与之直接相连的两个节点，这些节点不包含A
- 最终集群达成一致
在Gossip算法中，Gossip每次新感染的节点都会至少再感染一个节点，展开来看，这就是一个多叉树的结构，那么依据这个结构，最大的时间复杂度即使一个二叉树的形式，这时整体上达到一致性的速度是log(n).
可见Gossip传播性能还是相当惊人的，著名的Redis数据库便是使用Gossip传播协议保持一致性，Redis最多可支持百万级别的节点，gossip协议在其中起到了重要作用。
Paxos 协议
Paxos一致性算法由分布式领域专家Lamport提出，该算法主要是为了解决分布式一致性问题。作者论文中对于该算法的阐述paxos非常理论化，因而整体概念的理解较为抽象。下面我们以理论和示例相结合的方式解释这个算法。
需要知道的是，一致性算法的最终目的是让各个节点的数据内容达成一致，那么什么情况下可以认为各节点已经成功达成一致了呢？Paxos中的判定方法是如果存在大部分节点共同接收了该更新内容，可以认为本次更新已经达成一致。理清目标后，接下来我们看一下Paxos一致性理论的核心推导部分。
Paxos将节点进程分成"发起者""接收者""学习者"三类，论文称每个发起者发起的新的更新为"提议"，每个提议包含一个数字n和提议内容，算法的实现状态见图1。首先考虑一种特殊情况，如果在最开始的阶段，所有接收者没有收到任何"提议"，这时发起者发出的提议它们是会直接接受的。然而每次更新过程中，可能存在多个发起者发送提议，那么初始阶段可能各个接收者接受不同的提议，进而无法达成一致。这就要求一个接收者能够接受不止一个"提议"。这么一来就可能存在多个"提议"被"选择"(被大部分接收者接受)。既然会出现多个"提议"同时被选择的情况，最终如何达成一致呢？把条件设严格一点，如果后面被"选择"的"提议"内容都和第一个一致，那么无论有多少"提议"，最终不就相当于只有一个被选择了嘛！问题又来了，如何使得后面被选择的"提议"内容都和第一个一致呢？很简单，再把条件设严格一些，如果已经有"提议1"被选择，那么后续发起者发送的新"提议"的内容必须与"提议1"一致。Paxos的核心原理推导到这里就结束了，由此作者给出了一个算法：
发起者：
发送数字为n，内容为v的"提议"的预请求给所有接收者：
从回应中挑出数字小于n且数字最大的"提议"，并将提议内容赋给v
如果回应中没有"提议"，内容v由发起者指定
发送数字为n，内容为v的"提议"的接收请求给所有接收者
接收者：
接收到预请求：
如果预请求的数字n小于已经接收过的预请求的数字n，continue
回应发起者，表明自己不会再接收数字小于n的请求以及收到的数字小于n且数字最大的"提议"
接收到接收请求：
如果没有收到数字比n大的预请求:
接受请求
因为作者在描述Paxos时，列举了希腊城邦选举的例子，所以该算法又被称为希腊城邦算法。我们这里便列举希腊城邦选举的例子，帮助我们理解Paxos算法。城中的一些位高权重的人们("发起者")会提出新的"法案"，这些法案需要立法委员("接收者")达成一致即多数同意才能通过。于是权贵们会预先给立法委员一些金钱，让他们通过自己的法案，这对应的就是"预请求"，如果立法委员已经收到过更高贿赂的"预请求"，他们会拒绝，否则会同意。权贵们贿赂成功后，会告诉立法委员新的法案，在收到新法案之前，如果立法委员没有收到更高的贿赂，他们会选择接受这个法案，否则会拒绝。很关键的一点是，不要忘了我们是一致性协议，不是真正的立法，因此很关键的一点是如果立法委员在接收到更高的贿赂时已经接受了某个法案，那他会告诉贿赂的权贵这个法案的内容，权贵会将自己发起的法案改成该法案的内容，这样才能够迅速达成一致性。
Paxos是非常经典的一致性协议，但是因为过于理论化，难以直接工程化，因此工业界出现了诸多基于Paxos思想出发的变种。虽然这些变种最终很多都和原始的Paxos有比较大的差距，甚至完全演变成了新的协议，但是作为奠基者的Paxos在分布式一致性协议中依然持有不可撼动的地位。
Raft 协议
Raft协议是斯坦福的Diego Ongaro、John Ousterhout两人于2013年提出，作者表示流行的Paxos算法难以理解，且其过于理论化致使直接应用于工程实现时出现很多困难，因此作者希望提出一个能被大众比较容易地理解接受，且易于工程实现的协议。Raft由此应运而生。不得不说，Raft作为一种易于理解，且工程上能够快速实现一个较完整的原型的算法，受到业界的广泛追捧。大量基于Raft的一致性框架层出不穷。那么Raft究竟有哪些特点，它的整体运行逻辑是怎样的，下面讲具体介绍Raft算法。
Raft的算法逻辑主要可以分成两个部分，一个是选举部分，另一个是log传输部分。和Paxos部分不同的是，这里的log是连续并且按序传输的。Raft中定义了一个叫term概念，一个term实际上相当于一个时间片，如下图所示，这个时间片被分成两个部分，第一部分是选举部分，第二部分是传输部分。由此Raft的逻辑也可以分成选举和传输前后两个方面进行讲解。
首先我们介绍选举部分的算法逻辑。在Raft中可以存在多个server，其中每一个server都有机会成为leader，但是真实有效的leader只有一个。于是这个leader的产生需要所有的server去进行竞争。在每个term开始的阶段，众多server需要进行竞选，选出一个有效的leader。每个server被设置了一个300-400ms之间随机的timeout，在如果在timeout内没有收到某一个leader发来的心跳信息，那么这个server就会发起竞选，将自己的term值加一，成为candidate，并寻求其他server的投票。当且仅当某一个candidate收到超过一半的server的票数时，它就成功当选了leader，并开始向每个server发送心跳信息。仅仅这么做其实是存在问题的，如果有多个candidate同时参与竞选，很可能出现选票分散的情况，最终无法选出有效的leader。因而除此之外，Raft还要求如果candidate收到term比自己大的投票请求时将自己的状态修改成follower，这么一来就成了谁的term增加得快的问题，因为timeout是随机的，总会出现更快的server，因此算法最终是收敛的。选举过程的状态图可见下图.
那么当选举成功后，整个集群进入log传输的状态。client会给leader发送需要传输的log，leader收到后在log上附加log的位置索引值和当前term值。这么一来每个log的索引与term值都是独一无二的。leader中会记录所有待传输给server的log索引值，针对于某个server，如果leader现存的索引数目大于待传输值，leader就会向该server传输新的logs。server收到logs后验证第一个log的term是否与自己同索引log的term一致，如果不一致告知leader匹配失败，leader会将传输的索引值减一，再重新传送。如果server验证后发现一致，则删除冲突索引后的所有log，并将新收到的log续借在该索引后面。
总的来看，Raft算法清晰明了，相比于Paxos抽象的理论阐述更易于理解。但是实际上因为Raft论文本身就实现了一个面向工业界的一致性协议原型，实现起来是相对较复杂的，根据论文复现过这个算法的人尤其能体会这一点。
