分布式系统的事务处理

更多左耳朵耗子的独家干货，请订阅极客时间出品的陈皓全年专栏《左耳听风》，一次订阅、永久阅读。即日起，戳此订阅立享以下两大福利：

福利一：原价 ¥199/ 年，极客时间新用户注册立减 ¥30

福利二：每邀请一位好友购买，你可获得36 元现金返现，多邀多得，上不封顶，立即提现（提现流程：极客时间服务号- 我的- 现金奖励提现）

InfoQ 编辑注：本文来自阿里巴巴北京研发中心、商家业务部任资深专家陈皓自己的博客（ http://coolshell.cn/articles/10910.html），在本人许可下，由 InfoQ 中文站进行转载，在这里给大家分享。本文讨论了在数据冗余情况下考虑数据的一致性和性能的问题。

当我们在生产线上用一台服务器来提供数据服务的时候，我会遇到如下的两个问题：

1）一台服务器的性能不足以提供足够的能力服务于所有的网络请求。

2）我们总是害怕我们的这台服务器停机，造成服务不可用或是数据丢失。

于是我们不得不对我们的服务器进行扩展，加入更多的机器来分担性能上的问题，以及来解决单点故障问题。 通常，我们会通过两种手段来扩展我们的数据服务：

1）数据分区：就是把数据分块放在不同的服务器上（如：uid % 16，一致性哈希等）。

2）数据镜像：让所有的服务器都有相同的数据，提供相当的服务。

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

1. 从 A 帐号中把余额读出来。
2. 对 A 帐号做减法操作。
3. 把结果写回 A 帐号中。
4. 从 B 帐号中把余额读出来。
5. 对 B 帐号做加法操作。
6. 把结果写回 B 帐号中。

为了数据的一致性，这 6 件事，要么都成功做完，要么都不成功，而且这个操作的过程中，对 A、B 帐号的其它访问必需锁死，所谓锁死就是要排除其它的读写操作，不然会有脏数据的问题，这就是事务。那么，我们在加入了更多的机器后，这个事情会变得复杂起来：

1）在数据分区的方案中：如果 A 帐号和 B 帐号的数据不在同一台服务器上怎么办？我们需要一个跨机器的事务处理。也就是说，如果 A 的扣钱成功了，但 B 的加钱不成功，我们还要把 A 的操作给回滚回去。这在跨机器的情况下，就变得比较复杂了。

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

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

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

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

3）性能：吞吐量 、 响应时间

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

1）要想让数据有高可用性，就得写多份数据。

2）写多份的问题会导致数据一致性的问题。

3）数据一致性的问题又会引发性能问题

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

一致性模型

说起数据一致性来说，简单说有三种类型（当然，如果细分的话，还有很多一致性模型，如：顺序一致性，FIFO 一致性，会话一致性，单读一致性，单写一致性，但为了本文的简单易读，我只说下面三种）：

1）Weak 弱一致性：当你写入一个新值后，读操作在数据副本上可能读出来，也可能读不出来。比如：某些 cache 系统，网络游戏其它玩家的数据和你没什么关系，VOIP 这样的系统，或是百度搜索引擎（呵呵）。

2）Eventually 最终一致性：当你写入一个新值后，有可能读不出来，但在某个时间窗口之后保证最终能读出来。比如：DNS，电子邮件、Amazon S3，Google 搜索引擎这样的系统。

3）Strong 强一致性：新的数据一旦写入，在任意副本任意时刻都能读到新值。比如：文件系统，RDBMS，Azure Table 都是强一致性的。

从这三种一致型的模型上来说，我们可以看到，Weak 和 Eventually 一般来说是异步冗余的，而 Strong 一般来说是同步冗余的，异步的通常意味着更好的性能，但也意味着更复杂的状态控制。同步意味着简单，但也意味着性能下降。 好，让我们由浅入深，一步一步地来看有哪些技术：

Master-Slave

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

1）读写请求都由 Master 负责。

2）写请求写到 Master 上后，由 Master 同步到 Slave 上。

从 Master 同步到 Slave 上，你可以使用异步，也可以使用同步，可以使用 Master 来 push，也可以使用 Slave 来 pull。 通常来说是 Slave 来周期性的 pull，所以，是最终一致性。这个设计的问题是，如果 Master 在 pull 周期内垮掉了，那么会导致这个时间片内的数据丢失。如果你不想让数据丢掉，Slave 只能成为 Read-Only 的方式等 Master 恢复。

当然，如果你可以容忍数据丢掉的话，你可以马上让 Slave 代替 Master 工作（对于只负责计算的节点来说，没有数据一致性和数据丢失的问题，Master-Slave 的方式就可以解决单点问题了） 当然，Master Slave 也可以是强一致性的， 比如：当我们写 Master 的时候，Master 负责先写自己，等成功后，再写 Slave，两者都成功后返回成功，整个过程是同步的，如果写 Slave 失败了，那么两种方法，一种是标记 Slave 不可用报错并继续服务（等 Slave 恢复后同步 Master 的数据，可以有多个 Slave，这样少一个，还有备份，就像前面说的写三份那样），另一种是回滚自己并返回写失败。（注：一般不先写 Slave，因为如果写 Master 自己失败后，还要回滚 Slave，此时如果回滚 Slave 失败，就得手工订正数据了）你可以看到，如果 Master-Slave 需要做成强一致性有多复杂。

Master-Master

Master-Master，又叫 Multi-master ，是指一个系统存在两个或多个 Master，每个 Master 都提供 read-write 服务。这个模型是 Master-Slave 的加强版，数据间同步一般是通过 Master 间的异步完成，所以是最终一致性。 Master-Master 的好处是，一台 Master 挂了，别的 Master 可以正常做读写服务，他和 Master-Slave 一样，当数据没有被复制到别的 Master 上时，数据会丢失。很多数据库都支持 Master-Master 的 Replication 的机制。

另外，如果多个 Master 对同一个数据进行修改的时候，这个模型的恶梦就出现了——对数据间的冲突合并，这并不是一件容易的事情。看看 Dynamo 的 Vector Clock 的设计（记录数据的版本号和修改者）就知道这个事并不那么简单，而且 Dynamo 对数据冲突这个事是交给用户自己搞的。就像我们的 SVN 源码冲突一样，对于同一行代码的冲突，只能交给开发者自己来处理。（在本文后后面会讨论一下 Dynamo 的 Vector Clock）

Two/Three Phase Commit

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

第一阶段：

1. 协调者会问所有的参与者节点，是否可以执行提交操作。
2. 各个参与者开始事务执行的准备工作：如：为资源上锁，预留资源，写 undo/redo log……
3. 参与者响应协调者，如果事务的准备工作成功，则回应“可以提交”，否则回应“拒绝提交”。

第二阶段：

• 如果所有的参与者都回应“可以提交”，那么，协调者向所有的参与者发送“正式提交”的命令。参与者完成正式提交，并释放所有资源，然后回应“完成”，协调者收集各节点的“完成”回应后结束这个 Global Transaction。

• 如果有一个参与者回应“拒绝提交”，那么，协调者向所有的参与者发送“回滚操作”，并释放所有资源，然后回应“回滚完成”，协调者收集各节点的“回滚”回应后，取消这个 Global Transaction。

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

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

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

这是多么经典的一个两阶段提交的事务处理。 另外，我们也可以看到其中的一些问题， A）其中一个是同步阻塞操作，这个事情必然会非常大地影响性能。 B）另一个主要的问题是在 TimeOut 上，比如，

1）如果第一阶段中，参与者没有收到询问请求，或是参与者的回应没有到达协调者。那么，需要协调者做超时处理，一旦超时，可以当作失败，也可以重试。

2）如果第二阶段中，正式提交发出后，如果有的参与者没有收到，或是参与者提交 / 回滚后的确认信息没有返回，一旦参与者的回应超时，要么重试，要么把那个参与者标记为问题节点剔除整个集群，这样可以保证服务节点都是数据一致性的。

3）糟糕的情况是，第二阶段中，如果参与者收不到协调者的 commit/fallback 指令，参与者将处于“状态未知”阶段，参与者完全不知道要怎么办，比如：如果所有的参与者完成第一阶段的回复后（可能全部 yes，可能全部 no，可能部分 yes 部分 no），如果协调者在这个时候挂掉了。那么所有的节点完全不知道怎么办（问别的参与者都不行）。为了一致性，要么死等协调者，要么重发第一阶段的 yes/no 命令。

两段提交最大的问题就是第 3）项，如果第一阶段完成后，参与者在第二阶没有收到决策，那么数据节点会进入“不知所措”的状态，这个状态会 block 住整个事务。也就是说，协调者 Coordinator 对于事务的完成非常重要，Coordinator 的可用性是个关键。 因些，我们引入三段提交，三段提交在 Wikipedia 上的描述如下，他把二段提交的第一个段 break 成了两段：询问，然后再锁资源。最后真正提交。三段提交的示意图如下：

三段提交的核心理念是：在询问的时候并不锁定资源，除非所有人都同意了，才开始锁资源。

理论上来说，如果第一阶段所有的节点返回成功，那么有理由相信成功提交的概率很大。这样一来，可以降低参与者 Cohorts 的状态未知的概率。也就是说，一旦参与者收到了 PreCommit，意味他知道大家其实都同意修改了。这一点很重要。下面我们来看一下 3PC 的状态迁移图：（注意图中的虚线，那些 F,T 是 Failuer 或 Timeout，其中的：状态含义是 q – Query，a – Abort，w – Wait，p – PreCommit，c – Commit）

从上图的状态变化图我们可以从虚线（那些 F,T 是 Failuer 或 Timeout）看到——如果节点处在 P 状态（PreCommit）的时候发生了 F/T 的问题，三段提交比两段提交的好处是，三段提交可以继续直接把状态变成 C 状态（Commit），而两段提交则不知所措。

其实，三段提交是一个很复杂的事情，实现起来相当难，而且也有一些问题。

看到这里，我相信你有很多很多的问题，你一定在思考 2PC/3PC 中各种各样的失败场景，你会发现 Timeout 是个非常难处理的事情，因为网络上的 Timeout 在很多时候让你无所适从，你也不知道对方是做了还是没有做。于是你好好的一个状态机就因为 Timeout 成了个摆设。

一个网络服务会有三种状态：1）Success，2）Failure，3）Timeout，第三个绝对是恶梦，尤其在你需要维护状态的时候。

Two Generals Problem（两将军问题）

Two Generals Problem 两将军问题是这么一个思维性实验问题： 有两支军队，它们分别有一位将军领导，现在准备攻击一座修筑了防御工事的城市。这两支军队都驻扎在那座城市的附近，分占一座山头。一道山谷把两座山分隔开来，并且两位将军唯一的通信方式就是派各自的信使来往于山谷两边。不幸的是，这个山谷已经被那座城市的保卫者占领，并且存在一种可能，那就是任何被派出的信使通过山谷是会被捕。 请注意，虽然两位将军已经就攻击那座城市达成共识，但在他们各自占领山头阵地之前，并没有就进攻时间达成共识。两位将军必须让自己的军队同时进攻城市才能取得成功。因此，他们必须互相沟通，以确定一个时间来攻击，并同意就在那时攻击。如果只有一个将军进行攻击，那么这将是一个灾难性的失败。 这个思维实验就包括考虑他们如何去做这件事情。下面是我们的思考：

1）第一位将军先发送一段消息“让我们在上午 9 点开始进攻”。然而，一旦信使被派遣，他是否通过了山谷，第一位将军就不得而知了。任何一点的不确定性都会使得第一位将军攻击犹豫，因为如果第二位将军不能在同一时刻发动攻击，那座城市的驻军就会击退他的军队的进攻，导致他的军队被摧毁。

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

3）于是，似乎我们还要让第一位将军再发送一条确认消息——“我收到了你的确认”。然而，如果这位信使被抓怎么办呢？

4）这样一来，是不是我们还要第二位将军发送一个“确认收到你的确认”的信息。

靠，于是你会发现，这事情很快就发展成为不管发送多少个确认消息，都没有办法来保证两位将军有足够的自信自己的信使没有被敌军捕获。

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

这个实验意在阐明：试图通过建立在一个不可靠的连接上的交流来协调一项行动的隐患和设计上的巨大挑战。

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

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

Paxos 算法

Wikipedia 上的各种 Paxos 算法的描述非常详细，大家可以去围观一下。

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

Notes：Paxos 算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX 中的”La”，此人现在在微软研究院）于 1990 年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，使 Lamport 在八年后 1998 年重新发表到 ACM Transactions on Computer Systems 上（ The Part-Time Parliament ）。即便如此 paxos 算法还是没有得到重视，2001 年 Lamport 觉得同行无法接受他的幽默感，于是用容易接受的方法重新表述了一遍（ Paxos Made Simple ）。可见 Lamport 对 Paxos 算法情有独钟。近几年 Paxos 算法的普遍使用也证明它在分布式一致性算法中的重要地位。2006 年 Google 的三篇论文初现“云”的端倪，其中的 Chubby Lock 服务使用 Paxos 作为 Chubby Cell 中的一致性算法，Paxos 的人气从此一路狂飙。（Lamport 本人在 他的 blog 中描写了他用 9 年时间发表这个算法的前前后后）

注：Amazon 的 AWS 中，所有的云服务都基于一个 ALF（Async Lock Framework）的框架实现的，这个 ALF 用的就是 Paxos 算法。我在 Amazon 的时候，看内部的分享视频时，设计者在内部的 Principle Talk 里说他参考了 ZooKeeper 的方法，但他用了另一种比 ZooKeeper 更易读的方式实现了这个算法。

简单说来，Paxos 的目的是让整个集群的节点对某个值的变更达成一致。Paxos 算法基本上来说是个民主选举的算法——大多数的决定会成个整个集群的统一决定。任何一个点都可以提出要修改某个数据的提案，是否通过这个提案取决于这个集群中是否有超过半数的节点同意（所以 Paxos 算法需要集群中的节点是单数）。

这个算法有两个阶段（假设这个有三个节点：A，B，C）：

第一阶段：Prepare 阶段

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

如果接收节点收到的提案号 n 大于其它节点发过来的提案号，这个节点会回应 Yes（本节点上最新的被批准提案号），并保证不接收其它 <n 的提案。这样一来，节点上在 Prepare 阶段里总是会对最新的提案做承诺。

优化：在上述 prepare 过程中，如果任何一个节点发现存在一个更高编号的提案，则需要通知 提案人，提醒其中断这次提案。

第二阶段：Accept 阶段

如果提案者 A 收到了超过半数的节点返回的 Yes，然后他就会向所有的节点发布 Accept Request（同样，需要带上提案号 n），如果没有超过半数的话，那就返回失败。

当节点们收到了 Accept Request 后，如果对于接收的节点来说，n 是最大的了，那么，它就会修改这个值，如果发现自己有一个更大的提案号，那么，节点就会拒绝修改。

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

我们还可以看到：对于同一个值的在不同节点的修改提案就算是在接收方被乱序收到也是没有问题的。

关于一些实例，你可以看一下 Wikipedia 中文中的“ Paxos 样例”一节，我在这里就不再多说了。对于 Paxos 算法中的一些异常示例，大家可以自己推导一下。你会发现基本上来说只要保证有半数以上的节点存活，就没有什么问题。

多说一下，自从 Lamport 在 1998 年发表 Paxos 算法后，对 Paxos 的各种改进工作就从未停止，其中动作最大的莫过于 2005 年发表的 Fast Paxos 。无论何种改进，其重点依然是在消息延迟与性能、吞吐量之间作出各种权衡。为了容易地从概念上区分二者，称前者 Classic Paxos，改进后的后者为 Fast Paxos。

总结

下图来自：Google App Engine 的 co-founder Ryan Barrett 在 2009 年的 google i/o 上的演讲《 Transaction Across DataCenter 》（视频： http://www.youtube.com/watch?v=srOgpXECblk ）

前面，我们说过，要想让数据有高可用性，就需要冗余数据写多份。写多份的问题会带来一致性的问题，而一致性的问题又会带来性能问题。从上图我们可以看到，我们基本上来说不可以让所有的项都绿起来，这就是著名的 CAP 理论：一致性，可用性，分区容忍性，你只可能要其中的两个。

NWR 模型

最后我还想提一下 Amazon Dynamo 的 NWR 模型。这个 NWR 模型把 CAP 的选择权交给了用户，让用户自己的选择你的 CAP 中的哪两个。

所谓 NWR 模型。N 代表 N 个备份，W 代表要写入至少 W 份才认为成功，R 表示至少读取 R 个备份。配置的时候要求 W+R > N。 因为 W+R > N， 所以 R > N-W 这个是什么意思呢？就是读取的份数一定要比总备份数减去确保写成功的倍数的差值要大。

也就是说，每次读取，都至少读取到一个最新的版本。从而不会读到一份旧数据。当我们需要高可写的环境的时候，我们可以配置 W = 1 如果 N=3 那么 R = 3。 这个时候只要写任何节点成功就认为成功，但是读的时候必须从所有的节点都读出数据。如果我们要求读的高效率，我们可以配置 W=N R=1。这个时候任何一个节点读成功就认为成功，但是写的时候必须写所有三个节点成功才认为成功。

NWR 模型的一些设置会造成脏数据的问题，因为这很明显不是像 Paxos 一样是一个强一致的东西，所以，可能每次的读写操作都不在同一个节点上，于是会出现一些节点上的数据并不是最新版本，但却进行了最新的操作。

所以，Amazon Dynamo 引了数据版本的设计。也就是说，如果你读出来数据的版本是 v1，当你计算完成后要回填数据后，却发现数据的版本号已经被人更新成了 v2，那么服务器就会拒绝你。版本这个事就像“乐观锁”一样。

但是，对于分布式和 NWR 模型来说，版本也会有恶梦的时候——就是版本冲的问题，比如：我们设置了 N=3 W=1，如果 A 节点上接受了一个值，版本由 v1 -> v2，但还没有来得及同步到节点 B 上（异步的，应该 W=1，写一份就算成功），B 节点上还是 v1 版本，此时，B 节点接到写请求，按道理来说，他需要拒绝掉，但是他一方面并不知道别的节点已经被更新到 v2，另一方面他也无法拒绝，因为 W=1，所以写一分就成功了。于是，出现了严重的版本冲突。

Amazon 的 Dynamo 把版本冲突这个问题巧妙地回避掉了——版本冲这个事交给用户自己来处理。

于是，Dynamo 引入了 Vector Clock（矢量钟？!）这个设计。这个设计让每个节点各自记录自己的版本信息，也就是说，对于同一个数据，需要记录两个事：1）谁更新的我，2）我的版本号是什么。

下面，我们来看一个操作序列：

1）一个写请求，第一次被节点 A 处理了。节点 A 会增加一个版本信息 (A，1)。我们把这个时候的数据记做 D1(A，1)。 然后另外一个对同样 key 的请求还是被 A 处理了于是有 D2(A，2)。这个时候，D2 是可以覆盖 D1 的，不会有冲突产生。

2）现在我们假设 D2 传播到了所有节点 (B 和 C)，B 和 C 收到的数据不是从客户产生的，而是别人复制给他们的，所以他们不产生新的版本信息，所以现在 B 和 C 所持有的数据还是 D2(A，2)。于是 A，B，C 上的数据及其版本号都是一样的。

3）如果我们有一个新的写请求到了 B 节点上，于是 B 节点生成数据 D3(A,2; B,1)，意思是：数据 D 全局版本号为 3，A 升了两新，B 升了一次。这不就是所谓的代码版本的 log 么？

4）如果 D3 没有传播到 C 的时候又一个请求被 C 处理了，于是，以 C 节点上的数据是 D4(A,2; C,1)。

5）好，最精彩的事情来了：如果这个时候来了一个读请求，我们要记得，我们的 W=1 那么 R=N=3，所以 R 会从所有三个节点上读，此时，他会读到三个版本：

• A 节点：D2(A,2)
• B 节点：D3(A,2; B,1);
• C 节点：D4(A,2; C,1)

6）这个时候可以判断出，D2 已经是旧版本（已经包含在 D3/D4 中），可以舍弃。

7）但是 D3 和 D4 是明显的版本冲突。于是，交给调用方自己去做版本冲突处理。就像源代码版本管理一样。

很明显，上述的 Dynamo 的配置用的是 CAP 里的 A 和 P。

我非常推大家都去看看这篇论文：《 Dynamo：Amazon’s Highly Available Key-Value Store 》，如果英文痛苦，你可以看看译文（译者不详）。

转载地址： http://coolshell.cn/articles/10910.html