漫谈分布式系统（十二）：弱一致性也有用武之地

这是《漫谈分布式系统》系列的第 12 篇，预计会写 30 篇左右。每篇文末有为懒人准备的 TL;DR，还有给勤奋者的关联阅读。扫描文末二维码，关注公众号，听我娓娓道来。也欢迎转发朋友圈分享给更多人。

先污染后治理的一致性

前面几篇文章，大致介绍了几种预防类的分布式数据一致性算法，包括单主同步、2PC/3PC、Quorum 类（Paxos/Raft/ZAB）等。

这类算法为了追求强一致性，都一定程度牺牲了性能和可用性。

但性能和可用性也是非常重要的，太慢的系统，或者失去可用性的系统，很多时候都是无法接受的。

而反过来，有时候，强一致性却并不是必须的。

这篇文章，我们就一起看下，第二种分布式数据一致性算法 -- 先污染后治理 类算法，及其实际应用场景。

弱一致性模型

预防类的一致性算法，想要提供的是强一致性保证，整个系统始终像一个单副本（single-copy）系统一样。

而先污染后整理的一致性算法，提供的是弱一致性，允许系统出现某不一致，对外也体现为一个多副本（multi-copy）的分布式系统。

当然，弱一致性也只是妥协，并且是局部或暂时的妥协。从应用的角度看，自然还是希望得到一致性结果的。

粗略的看，弱一致性可以分为以下几种模型：

• 以客户端为中心的一致性（Client-Centric Consistency）

• 最终一致性（Eventural Consistency）

• 因果一致性（Causal Consistency）

第一种，以客户端为中心的一致性，说难听点，是一种推卸责任的一致性。

在这个模型下，分布式系统不能说弃不一致性不顾，但至少没有承担主要作用，而是把责任丢给了客户端。

客户端需要自己维护一个数据缓存，来保存从服务端读到的不同版本的数据。当读请求指向旧副本时，直接使用缓存中的数据。

很显然， 这个模型只是尽力去避免读到旧数据，不能保证每次读到的真的就是最新的数据。

第二种，最终一致性，是一种很玄学的一致性。

这个模型提供的是一个非常弱的保证： 虽然过程中数据会出现分歧，但最终会达到一致。

但是究竟多久叫「最终」？没有标准答案。

看起来，像前面文章提到的单主同步模型一样，又是一种「尽可能」（best-effort）的一致性，只不过这次体现在时间上。

虽然很玄，但在现实系统面对的性能和可用性高压下，却得到了非常广泛的实现和应用。

第三种，因果一致性，是一种有说服力的一致性。

在这个模型下，分布式系统尝试提供的保证是， 如果事件 B 的发生必须以事件 A 发生为前提，或者说 B 发生在 A 之后，那系统将收敛于 B。

这就解决了类似我们前面文章举过的 答案比问题先出现 的怪异情况。

因果一致性固然没有强一致性好，但从实用的角度说，对很多时候对应用而言已经够用了。

从实现上看，因果一致性，可以看做一种特殊的最终一致性。

上面列的三种分类只是示例，并不是说没有其他的分法，我们有些基本的认识即可，不必在概念上过多纠结。

冲突解决

既然弱一致性允许出现冲突，又想要尽量保证一致性，那解决冲突就成了核心问题。

下面就一起看下几种典型的冲突解决办法。

Last Write Wins

采用这个方法，系统总是用更新的数据覆盖旧数据。

这是个非常常见的办法，在单机系统里就是这么干的。

但是单机系统的顺序性是非常好确定的，所有事件都在同一个地方排好队按顺序处理。

但是分布式系统却是分散的，又怎么去定义谁是 first 谁是 last 呢？

最常见的办法有两种：

• 一种是给每个事件一个时间戳，通过时间戳来比较先后。

• 另一种是给每个事件一个递增的标识，通过比较标识大小确定先后，本质上和时间戳一样。

这两种办法都很常见，但也都各有弱点。

• 机器时钟很难保证全局同步（后续文章会细说）。

• 全局标识引入共识问题和性能压力。

所以， Last Write Wins 提供的一致性并不一定正确，因为对新旧的判断可能不准，存在旧数据覆盖新数据的可能。

Causal Relationship

如果能维护好事件间的因果关系，就能实现上一节提到的因果一致性了。

version number 是最常见的维护因果关系的办法。

大致思想是， 客户端和服务端都在请求和保存数据时带上版本号，允许多个版本号的数据同时存在，但同一个版本号的数据需要做合并。

以上图为例，看最后一个请求。

Client 1 在上一次请求时，已经从服务端获知现在有两个版本的数据：

• [milk, flour]

• [eggs]

现在想要把 bacon 加到购物车中，则需要在请求内容中合并已知的内容和自己想要提交的内容，再以上次的版本号 3 提交。

而在 Client 1 不知情的情况下， Client 2 在 Client 1 的后两次请求间，已经按类似的方法提交完了请求，并得到了版本号为 4 的回复。

服务端在收到 Client 1 最后的请求后，需要把自己保存的编号为 3 的内容和 Client 1 新提交的编号为 3 的内容做合并，得到编号为 5 的内容。而 Client 2 刚提交的编号为 4 的内容则保持不变。

可以看到，通过这个办法，就很好的维持住了事件的因果先后顺序。

多版本号数据的持续写入和合并，形成了一个个并行又交汇的分支，就像我们用 git 管理代码仓库留下的痕迹一样。

思考一个问题，如果除了往购物车添加商品，还要支持删除商品呢，应该怎么做？

这个时候如果还是简单的合并，就可能会出现删除过的商品又出现的情况。

解决方法也很简单，在操作数据库的业务数据时很常见，就是不真删除，只是标记删除，即所谓 tombstone 。这样在合并的时候，就不会出错了。

另外，为了提升性能和节省空间，服务端可以对 version number 做垃圾回收，比如只保留最新的 5 个版本。

Multi-Replica Causal Relationship

仔细看上面 version numbers 的图，其实是个单机版本的实现。

这个方法在在分布式系统里，依然适用，只是我们需要维护所有副本的 version numbers，也就是需要 version vector （也可以叫 vector clocks ）。

接着上面购物车的例子，Client 1 最后发送的请求可能会是这样：

set key:cart

replica1: {value:[milk,flour,eggs,bacon], version=3}

replica2: {value:[milk,flour,eggs,bacon], version=3}

replica3: {value:[milk,flour,eggs,bacon], version=3}

Automatic Conflict Resolution

上面几种解决冲突的办法，要么自动处理但可能误判，要么需要客户端参与来保证顺序。

有没有什么办法，能自动并且正确地处理冲突呢？

CRDT （Conflict-free Replicated DataTypes） 就是其中的典型。

顾名思义，CRDT 就是一些不会导致冲突的数据类型。这些数据类型具有几个特点：

• 符合结合律，a + (b + c) = (a + b) + c。

• 符合交换律，a + b = b + a。

• 具有幂等性，a + a = a。

其实就是数学里的 semilattice。

符合结合律和交换律，使得消息的顺序不再影响结果；具备幂等性使得故障后的消息重发不会导致重复。满足这两点，消息就能收敛一致 。（其实就是前面文章提到过的 exactly once，可以看到，和数据一致性关系非常紧密，但我们仍然留到后续文章再细说。）

在编程领域，也已经有不少这样的例子，比如 max() 函数，比如 union() 操作等等。

CRDT 就是提供了一系列的数据结构，满足上述三个特性，使得数据自动收敛，或者说没有冲突的可能。这样，我们就可以不用担心数据一致性，只管用就好。

简单挑几个典型的列一下：

• Counters

  • 递增的 counter，最常规的计数器。

• Registers

  • Last Write Wins register，前面提到过，比如基于 timestamp 的实现。

  • Multi-valued register，两个 register，一个用来加，一个用来减，以避免抵消，丢失中间状态。

• Sets

  • 只增的 set，最常规的 set。

  • Two-phase set，两个 set，一个用来添加，一个用来删除，适用于前面提到的购物车的例子。

不难想象，满足上述三个特性的数据结构是有限的，不过对很多应用场景来说已经够用了。

Dynamo

前面大概说了下弱一致性的目标，以及关键的数据冲突怎么解决。现在我们看下现实中的实现。

比较有名的的弱一致性系统有 Amazon 的 Dynamo、Facebook 的 Cassandra、Linkedin 的 Voldemort 等。

Cassandra 和 Voldemort 都基于 Dynamo 的设计思想实现，因此，我们以 Dynamo 为例了解下。

数据定位

读写数据的第一步就是定位到数据。

Dynamo 没有采用中心化的元数据存储方案，而是使用一致性哈希（consistent hashing）来提高数据分区（partitioning）和定位的性能。

如上图所示，在 3 副本的情况下，key K 对应的数据会在节点 B、C 和 D 上都保存一份。B、C 和 D 就叫 key k 的 preference list，其中第一位的 B 是 coordinator，负责响应客户端的读写请求，以及把数据复制给顺时针后续的 C 和 D。

一致性哈希相比普通哈希的好处很明显，当有节点加入或移除时，只会影响到相邻的节点，不会导致所有节点上的数据重新分布。这样，系统的扩展性（scalability）就好多了。

但原生的一致性哈希还不够好：

• 节点位置的随机性，导致了数据和负载的不均衡。

• 机器性能的差异没有得到体现。

因此，Dynao 在原生一致性哈希的基础上做了一些改进：

• 把物理节点按性能差异拆分为不同数量的虚拟节点，再由虚拟节点组成一致性哈希环。

• 将一致性哈希环等分成 M 个大小相等的区域，每个节点平均分担这些区域。

这两个改进，使得机器性能和数据存储都均匀的分布，充分地打散了负载的压力。

短时故障恢复

Dynamo 从实践中总结出，机器短时故障是更频繁的，而永久故障是相对少的。因此采用了不同的处理策略。

对短时故障，采用 gossip + hinted handoff 的方法处理。

由于采用了去中心化的架构，Dynamo 系统中没有哪个地方能维护成员信息。

因此，当出现节点的短暂失联和恢复，或者有计划的扩容时，采用 gossip 协议来同步状态。

gossip，顾名思义，就像绯闻和小道消息的传播方式一样，点对点逐渐扩散开来。

每个节点隔一段时间都随机挑选一个节点，同步成员信息。可以看到，成员信息这个数据，通过 gossip 协议也将达到最终一致性。

成员信息变化解决了，接着就是成员变化期间的数据同步。

当由于节点故障导致满足不了写副本数要求时，Dynamo 会另外挑选一个节点暂时存放这份数据。

被选中暂存的节点，会单独开辟空间临时存在这份数据，并保留故障节点的元信息作为 hint。当故障节点恢复后，再把暂存的数据移交（handoff）过去。

可以看到，hinted handoff 既保证了数据持久性要求，又没有打破一致性哈希的要求，是应对短时故障的好方法。

永久故障恢复

而对永久故障，就不能采用短时故障的方法了，否则临时数据越来越多，危害节点稳定性。

当新节点加入后，需要从其他节点同步自己在一致性哈希环中负责的数据。由于可能存在数据不一致，Dynamo 采用反信息熵（anti-entropy）的策略来做数据同步过程中的一致性检查。

具体实现上，使用 Merkle 树来处理来对比数据，以减少实际传输的数据量。

如上图所示，Merkle 是一个多层的树形结构，父节点保存子节点的 hash 值。每个 Dynamo 节点都会对自己负责的每个 key range 创建一颗这样的树。

当做数据同步或者一致性检查时，只需要从上往下逐层对比 hash 值，就能找到具体的差异数据。然后只需要传输差异的部分，就能尽快地达到节点间的数据一致。

这种增量传输差异数据的方式，自然比全量传输要快得多。

读写模式

为了追求性能和可用性，Dynamo 采用了类似前面文章提到过的 leaderless 的读写模式，任意节点都可以接受任意 key 的请求。

典型的，客户端有两种方式来发送读写请求：

• 客户端发给一个负载均衡器，负载均衡器再根据负载转发给某个节点，这个节点如果不在 prefrence list 的前几个，则会将请求转发给对应的 coordinator。

• 客户端如果知道了数据分区情况，直接发给对应的 coordinator。

上篇文章，我们提到 Paxos 通过 quorum 做数据复制，来达成共识。Dynamo 也采用了类似的方法，只不过，不要求超过半数节点，所以也叫 partial quorum。

设系统节点数为 N，写节点数为 W，读节点数为 R。

客户端需要往 W 个节点写数据，之后再从 R 个节点读数据，当满足 W + R > N 时，写和读覆盖的节点就会有重叠，这样就一定能读到最新的数据，以及发现可能的数据冲突。

W 和 R 具体取多少可以根据需要灵活调整。很明显， W 越大，数据持久性保障越好，但写的越慢；R 越大则读的越慢 。

以常规的 N=3 为例，可以有这么几种选择：

• W = 1，R = 3，读慢写快

• W = 2，R = 2，读写均衡

• W = 3，R = 1，读快写慢

下图是一个真实的 benchmark。其中 Lr 表示 99.9% 的读操作的返回时间，Lw 表示 99.9% 的写操作的返回时间，t 表示数据不一致的持续时间。

以 YMMR 那列为例，对比 (R=1, W=1) 和 (R=2, W=1) 这两行。可以看到，随着 R 的增大，读操作耗时从 5.58 增加到了 32.6，而不一致持续时间从 1364 减少到了 202。

冲突解决

去中心化的架构使得多个节点都可以写，再加上并发写的情况，使得数据冲突在所难免。

Dynamo 采用了上面提到的 vector clocks 来解决数据冲突，这里不再重复。

而前面说过，vector clock 提供的是因果一致性，并不能解决并发写冲突。一旦出现并发写的情况，系统是无法判断谁先谁后，或者应该采用哪个结果的。

此时，如果客户端来查询数据，会出现两种情况：

• 如果查到的数据只有一个，说明没有并发写或已经成功收敛，可以直接使用。

• 而如果查到的数据有多个，说明并发结果无法完全收敛，因此会将多个结果都返回给客户端，由客户端根据应用场景选择需要的那个。

Dynamo 也因为这个遭受过质疑，但这就是牺牲一致性的代价。而 Dynamo 在 Amazon 大量的生产环境的应用，也证明了这个代价是可以接受的。

以上，就是 Dynamo 值得我们关注的重点。下图是 Dynamo 论文里列出的主要问题和解决办法，我们上面都基本涵盖到了。

可以看到，Dynamo 作为弱一致性分布式系统的典型成功例子，除了要解决数据冲突外，还需要做一系列的优化，才能在生产环境得到广泛应用。这也是理论和实践之间需要克服的鸿沟。

TL;DR

• 预防型的强一致性模型，虽然一致性好，但牺牲了性能和可用性。

• 先污染后治理的弱一致性模型，更偏向性能和可用性，一致性则选择事后处理，也得到了广泛的应用。

• 弱一致性模型可以分为客户端为中心的一致性、最终一致性、因果一致性等，其中因果一致性可以看做最终一致性的特例。

• 弱一致性允许分歧，但要能用，还是得解决冲突。

• 常见的解决冲突的办法有 Last Write Wins、version numbers、vector clocks、CRDT。

• Amazon 的 Dynamo 是弱一致性分布式系统的典型例子。

• Dynamo 使用改良后的一致性哈希算法做分区和数据定位。

• Dynamo 使用 gossip + hinted handoff 的办法来处理短时故障。

• Dynamo 使用 Merkle 树这种反熵策略减小数据传输，来实现永久故障恢复。

• Dynamo 使用类似 leaderless 数据复制的 W+R 的方式来做数据读写。

• Dynamo 使用 vector clocks 来解决数据冲突，提供因果一致性。

这篇文章，我们介绍了数据一致性的第二种解决：先污染后治理的弱一致性。并以 Dynamo 为例，了解了一个弱一致性的分布式系统，要在生产环境中得到应用，需要解决哪些问题。

回想系列第 10 篇文章，我们提到了用强一致性的 2PC/3PC 实现分布式事务。虽然在数据库领域得到了广泛应用，但缺点也很明显。

现在我们了解了弱一致性分布式算法，那有没有可能做出基于弱一致性的分布式事务，来解决诸如性能和可用性的问题呢？下一篇，我们就一起看下，分布式事务的另一种可能。