漫谈分布式系统(十二):弱一致性也有用武之地

这是《漫谈分布式系统》系列的第 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 实现分布式事务。虽然在数据库领域得到了广泛应用,但缺点也很明显。

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

原创不易

关注/分享/赞赏

给我坚持的动力

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章