Eaccebbecb0b01b791242ee44fc61829
漫谈分布式系统(12) -- 弱一致性也有用武之地

这是《漫谈分布式系统》系列的第 12 篇,预计会写 30 篇左右。欢迎订阅,听我娓娓道来。也欢迎转发朋友圈分享给更多人。

先污染后治理的一致性

前面几篇文章,大致介绍了几种预防类的分布式数据一致性算法,包括单主同步、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。

top Created with Sketch.