海量存储系列十五

接上，我们继续来探讨数据一致性这个问题。

谈到数据完整性和数据可用性问题的第二个方法。

 

简单回溯上一次的异步模式。

好处是性能，坏处是丢数据。但其实不会丢很多，所以大部分业务是可以接受一年丢几条记录这种case的。所以这也是大部分业务主要在跑的模型。

 

那么，对于一些对数据丢失case要求较高的业务，有什么办法能够保持数据的绝对安全呢？

这就要涉及到第一个关键的技术了：两段提交协议。

 

两段提交协议，其实是个非常简单的协议，有两种主要的子实现，能够分别的针对两种不同的场景，当年我还是花了很久的时间才把这些事情联系到一起的，所以我也希望能够在这里把看似完全不一样的东西联系到一起，让后面的人少走弯路 : )

 

需求：保证两个节点能够保证，能够拥有同一个状态。

下面来做一些分析，从最简单的开始，看看最小需求是什么：

 

我们假定有两个节点：A节点和B节点，他们之间要保证数据的一致，所谓一致，就是A:0的时候，b的那个数据最终也会变为B。请注意“最终”两字，很关键，后面分析的时候也会深入探讨。

 

“同一个状态”，如果要保证这一点，最简单的做法，就是，写A以后，再去写B. 用简化的语言来说，就是Commit A -> Commit B.

 

这时候需要面临以下几个问题，（我们在这里只丢问题，和解决路径，不会展开，因为展开会导致整个逻辑结构过于复杂）

 

一．如果有两个client，他们都要更新A节点和B节点，那么这时候就面临了一个问题，他们的更新顺序可能是完全不同的。举个例子，Client1 发送了一个数据的版本0给A和B.而Client 2 发送了一个数据的版本0’给B和A，很容易可以想到，假定数据在同一个时间更新，那么这两个更新的版本到达A和B的时间可能是不同的，这就导致一些不可预估的错误，如A是0版本的数据，而B则是0’版本的数据。这种情况肯定是做不到一致性的。

 

为了解决这个问题，有无数种模型。。。他们主要是：

第一种：有一台机器是主机，其他机器都从唯一的主机上拉取已经被排好序的数据。

第二种：vector clock.维持多个版本，利用多版本来判断数据是否发生了冲突。

第三种：维持全局时间序，出现冲突的时候，last write win.

第四种：使用事务提交方式，利用锁来防止出现这种冲突。

第五种：使用MVCC的方式，申请全局序号，一切数据更新的先后顺序关系，以全局序号为准。

 

二．Commit A后，如果发生网络问题或者其他问题，数据还没有更新到B的时候，A挂了，并且不幸的是，A挂之前，A里面的最新版本的数据还被外部用户读到了，这时候还是会悲剧的。想想吧，某日你中了500w ,人家把钱打到了你银行的户头，然后那台机器出现了上面说道的这种问题，你在第一天还能看到自己的500w..下一次刷新的时候却没了。。。

为了解决这个问题，我们就需要引入一个两段提交的优化版本，来处理这个问题了，在以前的文章中，我们其实已经讲过两段提交了。

http://qing.weibo.com/1765738567/693f0847330007ay.html

两段提交的核心，其实是在A和B更新的时候，对A和B都加一把锁，让其他人不能看到中间状态过程，然后，只有在全部提交后，才算整个事务的提交成功。流程是

Prepare A (lock)->Prepare B (lock) ->commit A(unlock) -> commit B(unlock)

但在所有场景中都使用以上的流程，实际上是很高消耗的了。比如：

“第一种：有一台机器是主机，其他机器都从唯一的主机上拉取已经被排好序的数据。”

在这种场景中，实际上A和B机器是不会产生数据冲突的，所以四步的流程明显会变得很重。解决这个问题的方法是，在不会出现数据冲突的地方，可以对两段提交进行一次优化，去掉一次prepare ,对应在上面流程，就是去掉Prepare B(lock)这个过程，将流程简化为 PA-> CB -> CA。

 

好了，赶紧收回来。。不能在这里再次深入下去了，原因是，每个东西展开都能写个千把字，而且因素与因素相互关系相互影响，不是简单地树形结构，从这里展开说出去，这样会让整个文章结构出现问题。

 

那么，写了上面的这些东西，核心的地方是希望能够引出以下的几个关键的因素，他们的true or false 直接决定了很多种不同的存储产品的核心不同点哦 :)

一，是否有主机概念？

二，是否要保证数据不丢？

三，读取是否要求高可用？

四，延迟要求？

五，写入是否要求高可用？

 

明眼人一看，这是啥？哈哈 CAP的变种么不是，没错的，CAP就是描述这类现象的一个英文缩写而已…

 

回到同步模式：为了解决CA->CB中出现的问题，我们就要演进我们的架构，到第二级别：

 

先来讨论有主机结构的,保证数据不丢的方案，目前这种有主机结构的是最为主流的一种模式，使用的人，就我所知有：zoo keeper, mongoDB , bdb java edition etc.在淘宝内部也有一些人在研究让mysql的semi-replication也能做到类似效果，这里我们期待他们的成果。

 

在这类解决方案中，主要的做法就是利用两段提交协议的优化版本：PA-> CB -> CA的方案，来实现A和B的强一致的。下面我们针对这一流程进行一些分析。

在PA阶段，数据只对提出修改的人可见，对外部其他用户不可见（所使用的方式主要是copy-on-write 或者直接用锁），所以这时候出现问题，不会对其他人造成影响的，直接回滚即可。

在CB阶段，如果数据更新成功，那么等于事务提交成功，因为如果这时候A机器挂掉，那么B的数据是可以直接可见的。而如果A没有挂掉，这时候A还在PA阶段呢，所以其他人看不见改动，而发起改动的人也没有获取commit 成功的信号。那么如果B挂掉，这时候是有问题的，A的策略只有两种，一类是等待直到成功，一类是等待超时后返回。

 

请各位看客们注意了，这就是两段提交协议最大的问题所在了。无论是一直等待，直到成功，还是等待超时后返回，其实都不安全。如果一直等，那么前端也在一直等，整个业务流程实际上是终止掉的，想想吧，如果您急等着用钱买17架波音呢，但这时候银行提示您，请等待付款，无论付多少次都是同一个提示的时候，您的想法是？。。

所以一般的做法都是等待超时后返回，但这样也带来问题，就是，在这时候机器其实是没有被保护的，存在着理论上丢数据的可能性。但比事务性（也就是pa,pb,ca,cb流程）的两段提交来说，有一个好处是数据的恢复相对的容易，因为只需要从主机拉最新数据就可以了。

 

为了解决两段提交协议在传输过程中出现的B挂掉导致的问题，牛人们就又开始新一轮的研究竞赛，其中呢，有个人在90年的时候提出了一种算法，说是能解决类似问题，但当时没有获得什么影响力，然后他就写了一篇论文，里面描述了一个有一群议员在只有信使进行通知的时候，能够对法令保持一致的理想国。不幸的是，这篇论文因为其晦涩也被丢到了垃圾桶，索性有明眼人发现了其中的价值。又把它找了回来，这论文描述的就是PAXOS,而这悲催的哥们就是Lamport ..

 

好，我们今天以Paxos作为本次文章的结尾吧。

在两段提交协议里面，存在着B机器挂掉导致等待和不安全的问题，那么有没有一种算法，可以保证在任何情况下，数据都可以读写，并且在任何情况下，数据的安全性都可以通过加入更多的机器的方式来提升安全级别呢？（比如，如果用了某种算法，那么就算地球被炸了，只要月球上有机器，数据就不会丢？：）

 

有的，PAXOS or fast PAXOS

 

但PAXOS论文很难懂，我们不用他来说明这个问题，我们以zoo keeper的实现思路，用更简单的话语来尝试说明什么叫zoo keeper.

 

Fast paxos里面有以下几个关键的组成部分:

1. 两段提交协议

这是基石，当然是使用简化版本的，也就是PA-CB-CA的版本的。这是我们能够保证两个机器数据强一致的唯一方法。

1. Paxos算法核心– Leaderelection

Paxos算法的目标，其实就是为了解决任意机器都会挂掉，如何能用一种自动的方式，在挂掉任何几个机器的时候，都能够自动的从剩余的机器里面找到没有任何数据丢失的那几台复制的样板儿，并且以样板儿里面的一台，将整个集群的数据进行恢复，并且不影响前面用户的正常读写。

那我们还是回到两段提交，如果B 没有响应了，如何能够让A正常返回成功呢？两台机器的情况下肯定做不出来，但有一点好的地方，我可以加机器。

 

如果我们把机器加到三台A,B,C，那么其实我就可以很容易的发现，B没返回？那C返回给A说成功，A也是可以返回的。

 

但，到底多少个返回成功才算数呢？这就是paxos的核心了。简单来说，N个里面如果有超过半数返回成功，那么就应该算是成功的了，注意哦，是加了自己的。

如，三个里面两个有最新数据，那么任意一个挂掉，数据不会丢失。

五个里面有三个返回最新数据，那么任意两个挂掉，数据不会丢失.etc…

 

那么在主节点挂掉的时候，请求应该被提交到哪里呢？很简单，因为更新只发生在主节点，由主节点生成一个全局的id号，让其他节点去学习这些带id号的数据更新。那么，假定有五个节点，任意两个挂掉，哪怕挂掉的里面有主节点，这时候也只需要从新从余下的三个里面选出那个id号最大的节点作为主节点，数据就一定是最新的。

 

当然，leader election是paxos协议的核心，对这块感兴趣的，可以具体看一下lamport的论文。

 

这就是paxos..简单来说，可以保证一直提供服务，集群任意节点宕机都不会影响数据的可用性。

可惜，代价是性能。。两段提交协议需要多次网络交互，所以延迟较高，就我们的测试来说，200ms一次提交总还是要的，你可以优化，但在当前网络结构下，延迟就是最大的祸首，CAP的之所以成为定律，原因其实就是网络延迟。。