会遇到如下的两个问题：生产线上用一台服务器来提供数据服务的时候。一台服务器的性能缺乏以提供足够的能力服务于所有的网络请求。造成服务不可用或是数据丢失。总是害怕我这台服务器停机。加入更多的机器来分担性能上的问题，于是不得不对我服务器进行扩展。以及来解决单点故障问题。通常，会通过两种手段来扩展我数据服务：

数据分区：就是把数据分块放在不同的服务器上（如：uid%16一致性哈希等），提供相当的服务。数据镜像：让所有的服务器都有相同的数据。无法解决数据丢失的问题，对于第一种情况。单台服务器出问题时，会有局部数据丢失。所以，数据服务的高可用性只能通过第二种方法来完成—数据的冗余存储（一般工业界认为比较平安的备份数应该是3份，如：Hadoop和Dynamo但是加入更多的机器，会让我数据服务变得很复杂，尤其是跨服务器的事务处理，也就是跨服务器的数据一致性。这个是一个很难的问题。让我用最经典的UseCaseA帐号向B帐号汇钱”来说明一下，熟悉RDBMS事务的都知道从帐号A帐号B需要6个操作：

从A帐号中把余额读出来。

对A帐号做减法操作。

把结果写回A帐号中。

从B帐号中把余额读出来。

对B帐号做加法操作。

把结果写回B帐号中。

这6件事，为了数据的一致性。要么都成功做完，要么都不成功，而且这个操作的过程中，对AB帐号的其它访问必需锁死，所谓锁死就是要排除其它读写操作，不然会有脏数据的问题，这就是事务。那么，加入了更多的机器后，这个事情会变得复杂起来：如果A扣钱成功了但B加钱不成功，数据分区的方案中：如果A帐号和B帐号的数据不在同一台服务器上怎么办？需要一个跨机器的事务处理。也就是说。还要把A操作给回滚回去。这在跨机器的情况下，就变得比较复杂了

数据镜像中，数据镜像的方案中：A帐号和B帐号间的汇款是可以在一台机器上完成的但是别忘了有多台机器存在A帐号和B帐号的副本。如果对A帐号的汇钱有两个并发操作（要汇给B和C这两个操作发生在不同 两台服务器上怎么办？也就是说。不同的服务器上对同一个数据的写操作怎么保证其一致性，保证数据不冲突？

还要考虑性能的因素，同时。如果不考虑性能的话，事务得到保证并不困难，系统慢一点就行了除了考虑性能外，还要考虑可用性，也就是说，一台机器没了数据不丢失，服务可由别的机器继续提供。于是需要重点考虑下面的这么几个情况：

1容灾：数据不丢、结点的Failover

2数据的一致性：事务处理

3性能：吞吐量 响应时间

要解决数据不丢，前面说过。只能通过数据冗余的方法，就算是数据分区，每个区也需要进行数据冗余处理。这就是数据副本：当出现某个节点的数据丢失时 可以从副本读到数据副本是分布式系统解决数据丢失异常的唯一手段。所以，这篇文章中，简单起见，只讨论在数据冗余情况下考虑数据的一致性和性能的问题。简单说来：

就得写多份数据，要想让数据有高可用性，写多份的问题会导致数据一致性的问题。数据一致性的问题又会引发性能问题

按下了葫芦起了瓢。这就是软件开发。

简单说有三种类型（当然，说起数据一致性来说。如果细分的话，还有很多一致性模型，如：顺序一致性，FIFO一致性，会话一致性，单读一致性，单写一致性，但为了本文的简单易读，只说下面三种），读操作在数据副本上可能读出来，1Weak弱一致性：当你写入一个新值后。也可能读不出来。比方：某些cach系统，网络游戏其它玩家的数据和你没什么关系，VOIP这样的系统，或是百度搜索引擎（呵呵），有可能读不出来，2Eventual最终一致性：当你写入一个新值后。但在某个时间窗口之后保证最终能读出来。比方：DNS电子邮件、AmazonS3Googl搜索引擎这样的系统。

任意副本任意时刻都能读到新值，比方：文件系统，3Strong强一致性：新的数据一旦写入。RDBMSAzureTabl都是强一致性的可以看到Weak和Eventual一般来说是异步冗余的而Strong一般来说是同步冗余的异步的通 常意味着更好的性能，从这三种一致型的模型上来说。但也意味着更复杂的状态控制。同步意味着简单，但也意味着性能下降。好，让我由浅入深，一步一步地来看有哪些技术：

Master-Slave，对于这种加构，首先是Master-Slav结构。Slave一般是Master备份。这样的系统中，一般是如下设计的

读写请求都由Master负责。由Master同步到Slave上。写请求写到Master上后。可以使用异步，从Master同步到Slave上。也可以使用同步，可以使用Master来push也可以使用Slave来pull通常来说是Slave来周期性的pull所以，最终一致性。这个设计的问题是如果Masterpull周期内垮掉了那么会导致这个时间片内的数 据丢失。如果你不想让数据丢掉，Slave只能成为Read-Onli方式等Master恢复。如果你可以容忍数据丢掉的话，当然。可以马上让Slave代替Master工作（对于只负责计算的结点来说，没有数据一致性和数据丢失的问 题，Master-Slav方式就可以解决单点问题了MasterSlave也可以是强一致性的比方：当我写Master时候，Master负责先写自己，等成功后，再写Slave两者都胜利后返回成功，整个过程是同步的如果写Slave失 败了那么两种方法，一种是标志Slave不可用报错并继续服务（等Slave恢复后同步Master数据，可以有多个Slave这样少一个，还有备 份，就像前面说的写三份那样）另一种是回滚自己并返回写失败。注：一般不先写Slave因为如果写Master自己失败后，还要回滚Slave此 时如果回滚Slave失败，就得手工订正数据了可以看到如果Master-Slav需要做成强一致性有多复杂。

数据间同步一 般是通过Master间的异步完成，Master-Mast又叫Multi-mast指一个系统存在两个或多个Master每个Master都提供read-writ服务。这个模型是Master-Slav加强版。所以是最终一致性。Master-Mast好处是一台Master挂了别的Master可以正常做读写服务，和Master-Slav一样，当数据没有被复制 别的Master上时，数据会丢失。很多数据库都支持Master-MastReplic机制。如果多个Master对同一个数据进行修改的时候，另外。这个模型的恶梦就出现了对数据间的抵触合并，这并不是一件容易的事情。看看 DynamoVectorClock设计（记录数据的版本号和修改者）就知道这个事并不那么简单，而且Dynamo对数据抵触这个事是交给用户自己搞的就像我SVN源码冲 突一样，对于同一行代码的抵触，只能交给开发者自己来处理。本文后后面会讨论一下DynamoVectorClock

每个节点虽然可以知晓自己的操作时胜利或者失败，这个协议的缩写又叫2PC中文叫两阶段提交。分布式系统中。却无法知道其他节点的操作的胜利或失败。当一个事务跨越多个节点时，为了坚持事务的ACID特性，需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)操作结果并最终指示这些节点是否要把操作结果进行真正的提交(比如将更新后的数据写入磁盘等等)两阶段提交的算法如下：

第一阶段：

否可以执行提交操作。协调者会问所有的参与者结点。预留资源，各个参与者开始事务执行的准备工作：如：为资源上锁。写undo/redolog，如果事务的准备工作胜利，参与者响应协调者。则回应“可以提交”否则回应“拒绝提交”

第二阶段：

协调者向所有的参与者发送“正式提交”命令。参与者完成正式提交，如果所有的参与者都回应“可以提交”那么。并释放所有资源，然后回应“完成”协调者收集各结点的完成”回应后结束这个GlobalTransact，协调者向所有的参与者发送“回滚操作”并释放所有资源，如果有一个参与者回应“拒绝提交”那么。然后回应“回滚完成”协调者收集各结点的回滚”回应后，取消这个GlobalTransact，也可以看到2PC这个事是强一致性的算法。前面我讨论过 Master-Slav强一致性战略，可以看到2PC说白了就是第一阶段做Vote第二阶段做决定的一个算法。和2PC有点相似，只不过2PC更为激进一些—先尝试再提交。2PC用的比较多的一些系统设计中，会串联一系列的调用，比方：A->B->C->D每一步都会分配一些资源或改写一些数据。比方我B2C网上购物的下单操作在后台会有一系列的流程需要做。如果我一步一步地做，就会出现这样的问 题，如果某一步做不下去了那么前面每一次所分配的资源需要做反向操作把他都回收掉，所以，操作起来比较复杂。现在很多处置流程（Workflow都 会借鉴2PC这个算法，使用 try->confirm流程来确保整个流程的能够胜利完成。举个通俗的例子，西方教堂结婚的时候，都有这样的桥段：

1牧师分别问新郎和新娘：否愿意…不管生老病死…询问阶段）

2当新郎和新娘都回答愿意后（锁定一生的资源）牧师就会说：宣布你事务提交）

也可以看到其中的一些问题，这是多么经典的一个两阶段提交的事务处理。另外。A其中一个是同步阻塞操作，这个事情肯定会非常大地影响性能。B另一个主要的问题是TimeOut上，比方参与者没有收到询问请求，如果第一阶段中。或是参与者的回应没有到达协调者。那么，需要协调者做超时处理，一旦超时，可以当作失败，也可以重试。正式提交发出后，如果第二阶段中。如果有的参与者没有收到或是参与者提交/回滚后的确认信息没有返回，一旦参与者的回应超时，要么重试，要么把那个参与者标志为问题结点剔除整个集群，这样可以保证服务结点都是数据一致性的。如果参与者收不到协调者的commit/fallback指令，3糟糕的情况是第二阶段中。参与者将处于“状态未知”阶段，参与者完全不知道要怎么办，比方：如果所有的参与者完成第一阶段的回复后（可能全部 ye可能全部no可能局部ye局部no如果协调者在这个时候挂掉了那么所有的结点完全不知道怎么办（问别的参与者都不行）为了一致性，要 么死等协调者，要么重发第一阶段的yes/no命令。

如果第一阶段完成后，两段提交最大的问题就是第3项。参与者在第二阶没有收到决策，那么数据结点会进入“不知所措”状态，这个状态会block住整个事务。也就是说，协调者Coordin对于事务的完成非常重要，Coordin可用性是个关键。因些，引入三段提交，三段提交在Wikipedia上的描述如下，把二段提交的第一个段break成了两段：询问，然后再锁资源。最后真正提交，除非所有人都同意了才开始锁资源。三段提交的核心理念是询问的时候并不锁定资源。

如果第一阶段所有的结点返回成功，那么有理由相信胜利提交的概率很大。这样一 来，可以降低参与者Cohort状态未知的概率。也就是说，一旦参与者收到PreCommit意味他知道大家其实都同意修改了这一点很重要，三段提交比两段提交的好处是三段提交可以继续直接把状态变成C状态（Commit而两段提交则不知所措。从上图的状态变化图我可以从虚线（那些F,TFailuer或Timeout看到如果结点处在P状态（PreCommit时候发生了F/T问题。

三段提交是一个很复杂的事情，其实。实现起来相当难，而且也有一些问题。相信你有很多很多的问题，看到这里。一定在思考2PC/3PC中各种各样的失败场景，会发现Timeout个非常难处理的事情，因为网络上的Timeout很多时候让你无所事从，也不知道对方是做了还是没有做。于是好好的一个状态机就因为Timeout成了个摆设。尤其在需要维护状态的时候。一个网络服务会有三种状态：1Success2Failur3Timeout第三个绝对是恶梦。

分别有一位将军领导，TwoGenerProblem两将军问题是这么一个思维性实验问题：有两支军队。现在准备攻击一座修筑了防御工事的乡村。这两支军队都驻扎在那座城市的附近，分占一座山头。一道山谷把两座山分隔开 来，并且两位将军唯一的通信方式就是派各自的信使来往于山谷两边。倒霉的这个山谷已经被那座城市的捍卫者占领，并且存在一种可能，那就是任何被派出的信使通过山谷是会被捕。请注意，虽然两位将军已经就攻击那座乡村达成共识，但在各自占领山头阵地之前，并没有就进攻时间达成共识。两位将军必需让自己的军队同时进攻乡村才干 取得胜利。因此，必需互相沟通，以确定一个时间来攻击，并同意就在那时攻击。如果只有一个将军进行攻击，那么这将是一个灾难性的失败。这个思维实验就包括考虑他如何去做这件事情。下面是思考：一旦信使被派遣，第一位将军先发送一段消息“让我上午9点开始进攻”然而。否通过了山谷，第一位将军就不得而知了任何一点的不确定性都会使得第一位将军攻击犹豫，因为如果第二位将军不能在同一时刻发动攻击，那座城市的驻军就 会击退他军队的进攻，导致他军对被摧毁。

第二位将军就需要发送一个确认回条：收到您的邮件，知道了这一点。并会在9点的攻击。但是如果带着确认消息的信使被抓怎么办？所以第二位将军会犹豫自己的确认消息是否能到达。

如果这位信使被抓怎么办呢？于是似乎我还要让第一位将军再发送一条确认消息—收到确认”然而。不是还要第二位将军发送一个“确认收到确认”信息。这样一来于是会发现，靠。这事情很快就发展成为不管发送多少个确认消息，都没有方法来保证两位将军有足够的自信自己的信使没有被敌军捕获。

就在这篇文章的第73页中一段描述两个黑帮之间的通信中被阐明。1978年，JimGrai数据库操作系统注意事项》一书中（从第465页开始）被命名为两个将军悖论。作为两个将军问题的定义和无解性的证明的来源，这一参考被广泛提 及。这个问题是无解的两 个将军问题和它无解证明首先由E.A .A kkoyunlu,K.Ekanadham和R.V.Huber于1975年在一些限制与折衷的网络通信设 计》一文中发表。

这个实验意在说明：试图通过建立在一个不可靠的连接上的交流来协调一项行动的隐患和设计上的巨大挑战。一个解决两个将军问题的实际方法是使用一个能够接受通信信道不可靠性的方案，从工程上来说。并不试图去消除这个不可靠性，但要将不可靠性削减到一个可以接受的水平。比方，第一位将军排出了100位信使并预计他都被捕的可能性很小。这种情况 下，不管第二位将军是否会攻击或者受到任何消息，第一位将军都会进行攻击。另外，第一位将军可以发送一个消息流，而第二位将军可以对其中的每一条消息发送 一个确认消息，这样如果每条消息都被接收到两位将军会感觉更好。然而我可以从证明中看出，俩都不能肯定这个攻击是可以协调的没有算法可用 比方，收到4条以上的消息就攻击）能够确保防止仅有一方攻击。再者，第一位将军还可以为每条消息编号，说这是1号，2号…直到n号。这种方法能让第二 位将军知道通信信道到底有多可靠，并且返回合适的数量的消息来确保最后一条消息被接收到如果信道是可靠的话，只要一条消息就行了其余的就帮不上什么忙 最后一条和第一条消息丢失的概率是相等的

东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，两将军问题可以扩展成更变态的拜占庭将军问题 ByzantinGenerProblem其故事背景是这样的拜占庭位于现在土耳其的伊斯坦布尔。为了防御目的因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。战争的时候，拜占庭军队内所有将军必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是军队可能有叛徒和敌军间谍，这些叛徒将军们会扰乱 或左右决策的过程。这时候，已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，这就是拜占庭将军问题。

大家可以去围观一下。Wikipedia上的各种Paxo算法的描述非常详细。保证不论发生以上任何异常，Paxo算法解决的问题是一个可能发生上述异常的分布式系统中如何就某个值达成一致。都不会破坏决议的一致性。一个典型的场景是一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他最后能得到一个一致的状态。为保证每个节点执行相同的命令序 列，需要在每一条指令上执行一个「一致性算法」以保证每个节点看到指令一致。一个通用的一致性算法可以应用在许多场景中，分布式计算中的重要问题。从 20世纪80年代起对于一致性算法的研究就没有停止过。

使Lamport八年后1998年重新发表到ACMTransactonComputSystem上（ThePart-TimParliament即便如此paxo算法还是没有得到重视，NotePaxo算法是莱斯利·兰伯特（LesliLamport就是LaTeX中的La此人现在微软研究院）于1990年提出的一种基于消息传送的一致性算法。由于算法难以理解起初并没有 引起人们重视。2001年Lamport觉得同行无法接受他幽默感，于是用容易接受的方法重新表述了一遍（PaxoMadeSimpl可见Lamport对Paxo算法情有独钟。近几年Paxo算法的普遍使用也证明它分布式一致性算法中的重要地位。2006年Googl三篇论 文初现“云”端倪，其中的ChubbiLock服务使用Paxo作为ChubbiCell中的一致性算法，Paxo人气从此一路狂飙。Lamport自己在blog中描写了用9年时间发表这个算法的前前后后）

所有的云服务都基于一个ALFAsyncLockFramework框架实现的这个ALF用的就是Paxo算法。Amazon时候，注：AmazonAWS中。看内部的分享视频时，设计者在内部的PrinciplTalk里说他参考了ZooKeep方法，但他用了另一种比ZooKeep更易读的方式实现了这个算法。Paxo目的让整个集群的结点对某个值的变卦达成一致。Paxo算法基本上来说是个民主选举的算法—大多数的决定会成个整个集 群的统一决定。任何一个点都可以提出要修改某个数据的提案，简单说来。否通过这个提案取决于这个集群中是否有超过半数的结点同意（所以Paxo算法需要集群中的结点是单数）

这个算法有两个阶段（假设这个有三个结点：ABC

第一阶段：Prepar阶段

Paxo算法会有一个SequencNumber可以认为是一个提案号，A 把申请修改的请求PreparRequest发给所有的结点ABC注意。这个数不断递增，而且是唯一的也就是说A和B不可能有相同的提案号）这个提案号会和修改请求一同发出，任何结 点在Prepar阶段”时都会拒绝其值小于当前提案号的请求。所以，结点A向所有结点申请修改请求的时候，需要带一个提案号，越新的提案，这个提案 号就越是最大的

这个结点会回应Ye本结点上最新的被批准提案号）并保证不接收其它<n提案。这样一来，如果接收结点收到提案号n大于其它结点发过来的提案号。结点上在Prepar阶段里总是会对最新的提案做承诺。如果任何一个结点发现存在一个更高编号的提案，优化：上述 prepar过程中。则需要通知 提案人，提醒其中断这次提案。

第二阶段：Accept阶段

需要带上提案号n如果没有逾越半数的话，如果提案者A收到逾越半数的结点返回的Ye然后他就会向所有的结点发布AcceptRequest同样。那就返回失败。如果对于接收的结点来说，当结点们收到AcceptRequest后。n最大的那么，就会修改这个值，如果发现自己有一个更大的提案号，那么，结点就会拒绝修改。

这似乎就是一个“两段提交”优化。其实可以看以2PC/3PC都是分布式一致性算法的残次版本，GooglChubbi作者MikeBurrow说过这个世界上只有一种一致性算法，那就是Paxo其它算法都是残次品。

还可以看到对于同一个值的不同结点的修改提案就算是接收方被乱序收到也是没有问题的，可以看一下Wikipedia中文中的Paxo样例”一节，关于一些实例。这里就不再多说了对于Paxo算法中的一些异常示例，大家可以自己推导一下。会发现基本上来说只要保证有半数以上的结点存活，就没有什么问题。自从Lamport1998年发表Paxo算法后，多说一下。对Paxo各种改进工作就从未停止，其中动作最大的莫过于2005年发表的FastPaxo无论何种改进，其重点依然是消息延迟与性能、吞吐量之间作出各种权衡。为了容易地从概念上区分二者，称前者ClassicPaxo改进后的后者为FastPaxo。说过前面要想让数据有高可用性，就需要冗余数据写多份。写多份的问题会带来一致性的问题，而一致性的问题又会带来性能问题。从上图我可以看到基本上来说不可以让所有的项都绿起来，这就是著名的CA P理论：一致性，可用性，分区容 忍性，只可能要其中的两个。

让用户自己的选择你CA P中的哪两个。最后我还想提一下AmazonDynamoNWR模型。这个NWR模型把CA P选择权交给了用户。W代表要写入至少W份才认为成功，所谓NWR模型。N代表N个备份。R表示至少读取R个备份。配置的时候要求W+R>N因为W+R>N所以 R>N-W这个是什么意思呢？就是读取的份数一定要比总备份数减去确保写成功的倍数的差值要大。

每次读取，也就是说。都至少读取到一个最新的版本。从而不会读到一份旧数据。当我需要高可写的环境的时候，可以配置W=1如果N=3那么R=3这个时候只要写任何节点胜利就认为成功，但是读的时候必需从所有的节点都读出数据。如果我要求读的高效率，可以配置 W=NR=1这个时候任何一个节点读胜利就认为成功，但是写的时候必需写所有三个节点胜利才认为成功。因为这很明显不是像Paxo一样是一个强一致的东西，NWR模型的一些设置会造成脏数据的问题。所以，可能每次的读写操作都不在同一个结点上，于是会出现一些结点上的数据并不是最新版本，但却进行了最新的操作。

AmazonDynamo引了数据版本的设计。也就是说，所以。如果你读出来数据的版本是v1当你计算完成后要回填数据后，却发现数据的版本号已经被人更新成了v2那么服务器就会拒绝你版本这个事就像“乐观锁”一样。版本也会有恶梦的时候—就是版本冲的问题，但是对于分布式和NWR模型来说。比方：设置了N=3W=1如果A结点上接受了一个值，版本由v1->v2但还没有来得及同步到结点B上（异步的应该W=1写一份就算成功）B结点上还是v1版本，此时，B结点接到写请求，按道理来说，需要拒绝 掉，但是一方面并不知道别的结点已经被更新到v2另一方面他也无法拒绝，因为W=1所以写一分就成功了于是呈现了严重的版本抵触。

A mazonDynamo把版本抵触这个问题巧妙地回避掉了版本冲这个事交给用户自己来处理。也就是说，于是Dynamo引入了VectorClock矢量钟？!这个设计。这个设计让每个结点各自记录自己的版本信息。对于同一个数据，需要记录两个事：谁更新的2版本号是什么。来看一个操作序列：第一次被节点A处置了节点A会增加一个版本信息(A1把这个时候的数据记做D1A1然后另外一个对同样kei请求还是被A处置了于是有D2A2这个时候，一个写请求。D2可以覆盖D1不会有冲突产生。

所以现在B和C所持有的数据还是D2A2于是ABC上的数据及其版本号都是一样的2现在假设D2传达到所有节点(B和CB和C收到数据不是从客户产生的而是他人复制给他所以他不产生新的版本信息。于是B结点生成数据D3A,3如果我有一个新的写请求到B结点上。B,1意思是数据D全局版本号为3A升了两新，B升了一次。这不就是所谓的代码版本的log么？2;C,4如果D3没有传达到C时候又一个请求被C处置了于是以C结点上的数据是D4A.1

最精彩的事情来了如果这个时候来了一个读请求，5好。要记得，W=1那么R=N=3所以R会从所有三个节点上读，此时，会读到三个版本：D2已经是旧版本（已经包括在D3/D4中）可以舍弃。这个时候可以判断出。