这是《漫谈分布式系统》系列的第 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 在上一次请求时，已经从服务端获知现在有两个版本的数据：
现在想要把 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。
这是《漫谈分布式系统》系列的第 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 在上一次请求时，已经从服务端获知现在有两个版本的数据：
现在想要把 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。
这是《漫谈分布式系统》系列的第 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 在上一次请求时，已经从服务端获知现在有两个版本的数据：
现在想要把 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。
