漫谈分布式系统(14) -- 一致性问题的根源
这是《漫谈分布式系统》系列的第 14 篇，预计会写 30 篇左右。每篇文末有为懒人准备的 TL;DR，还有给勤奋者的关联阅读。扫描文末二维码，关注公众号，听我娓娓道来。也欢迎转发朋友圈分享给更多人。
数据一致性小结
从系列第 8 篇开始引出高可用性和数据副本，接着深入数据一致性问题，这个章节，已经写了 6 篇了。
这块内容涉及的概念、理论都很多，也是分布式系统面临的核心挑战之一。所以，这里有必要先小结下。
首先，为了达到高可用性，唯一的办法就是数据复制（data replication）。当然，数据副本也能带来性能上的提升等其他好处。
对于数据复制主从的选择，我们介绍了 3 种方法：
single leader replication。一个 leader 接受写，多个 follower 作为备份。
multi-leader replication。多个 leader 都能接受写。
leaderless replication。没有 leader，也相当于个个都是 leader。
对于数据复制的时效性，我们也介绍了 3 种方法：
synchronous replication。同步复制，虽然慢，但是稳妥。
asynchronous replication。异步复制，很快，但是会有延迟。
semi-synchronous replication。半同步复制，相对折中，比较稳妥也比较快。
接着，我们发现，多主并发写可能导致数据冲突，异步复制带来的 replication lag 可能导致访问不到最新的数据。也就是说，这类问题可能导致数据一致性问题。
数据一致性问题使得系统变得不可信，会导致很多现实问题，必须要解决。
解决数据一致性的方法可以分为两个大类：
预防类，尽可能防止分歧，提供强一致性，对外看起来像一个 single-copy 的系统，哪怕牺牲可用性和性能（性能也是某种程度的可用性）。
先污染后治理类，允许出现分歧后再收敛，提供弱（最终）一致性，对外就坦然以多节点的分布式系统示众，牺牲一部分一致性，来保证可用性。
预防类的一致性方法，又细分为三类：
单主同步复制。看起来很强的保证，实际上处理不了很多 corner case，只能做到 best-effort guarantee。而这些 corner case 后面隐藏着一个普遍的 CAP 定理。
multi-phase commit。数据复制也可以看做事务的一种，可以用分布式事务解决。典型的有 2PC 和 3PC，但是都解决不了网络分区的问题。
consensus。为了解决网络分区问题，衍生了以 Paxos 为基础的一类算法，包括 Raft、ZAB 等，这类算法的目标是解决所谓共识问题，而数据一致性可以看做是另一个视角的共识。
先污染后治理类的一致方法，又可以分为两类：
以 Dynamo 为典型的提供 probabilistic guarantees 的最终一致性。对有因果先后顺序的事件，可以通过 vector clocks 等手段提供因果一致性。但其他并发写入的事件，就无法确定顺序了，不过很多时候这个顺序也不重要。
以 CRDT 为典型的提供 strong guarantees 的最终一致性。在一些特殊的数据类型及其提供的操作下，事件写入的顺序并不影响最终结果，比如 set 的 union 操作。这类数据结构就可以放开去并发写，不需要节点间的协商，或者说会自动收敛，以达到最终的一致性。当然，这类数据结构是比较有限的，不能满足所有场景的需求。
分布式事务可以用来解决数据一致性问题，但本身也是相对独立和非常重要的应用。而数据一致性又分强和弱两种，那分布式事务也就可以总结为两种实现方式：
ACID on 2PC。以 2PC 为典型的分布式事务，提供标准的 ACID 保证，从 CAP 的角度看，提供强一致性，但可用性（包括性能）不够好（其实某些场景下的一致性也得不到保证）。
BASE。BASE（碱） 理论是 ACID（酸）之外的另一种选择，可以基于 Dynamo 或基于 MQ 实现分布式事务，只追求最终一致性，牺牲无时无刻的强一致性，来换取性能和可用性。
到这里，我们就能汇总起来，从理论上归纳出一些一致性模型。这些模型，本质上来说，是分布式系统对外提供的承诺和保证（guarantee），让外部系统可以在这些保证的基础上使用分布式系统，而不会抱着不切实际的期望、完全黑盒地用。
一致性模型的分类和实现非常多，我们无法也没有必要一一列举。这里只总结下我们前面文章涉及过的主要的模型。
strong consistency models
linerizable consistency，线性一致性，保证 linerizability，全局有序，是最强的一致性，看起来就像单机系统一样。主要实现方式是以 Paxos 为典型的各种共识算法。
sequential consistency，顺序一致性，保证所有节点观察到的顺序一致，但不一定和真实的全局顺序完全一致。sequential consistency 再加上真实且准确的时间属性就等于 linerizable consistency。（注意不要和事务里的 serializability 搞混。）
weak consistency models
client-centric consistency models，客户端中心一致性，不强求服务端完整的一致性，只追求客户端各自的一致性。
read-after-write consistency，自己写的立马就能读。主要实现方式是把请求发给固定的副本。
monotonic reads，不能读到已经读到的数据之前的数据。主要实现方式是客户端缓存。
eventual consistency models，最终一致性，不追求无时无刻的一致，但保证在不确定的时间后，总是能达成一致。无所谓实现方式，自然状态就是这样。更需要关注的是运维效率和冲突的解决。
causal consistency models，因果一致性，有逻辑上因果先后顺序的事件需要保证顺序，其他情况都不保证。主要实现方式是 vector clocks。
一致性问题的根源
从上面的总结不难看出，一致性问题太重要了，影响太大了，为了解决它，我们也想尽了各种办法。
前面我们也提过，产生一致性问题的原因，是我们想要扩展性下的高可用性。但服务器可能宕机甚至无法恢复，于是只能做多副本，多副本间的数据要同步以保证一样，实现的不好，就会出现不一致的情况。
这么看来，服务器故障，就是一致性问题的根源。真的是这样吗？
部分是，但不完全是。
我们退一步，回到最初的单机系统，看看能不能找到问题的根源。
不确定性
在单机系统下，一个程序，接收到一个特定的输入，只会有两个结果。
返回特定的输出。
遇到故障返回错误。
而对于一系列的输入，单机系统会按输入产生的时间顺序处理，得到和输入顺序一样的输出。
所以，单机系统对于特定输入的反馈是确定的（deterministic）。这个确定性体现在两方面：
输出的内容。当发生故障（failure）比如磁盘损坏时，宁愿 crash，也不会给出内容不一样的输出。
输出的顺序。当发生故障时，宁愿终止执行，等恢复后再继续执行，也不会给出顺序不一样的输出。
这种确定性非常重要，是单机系统提供给外界的强力保证，外部系统可以放心大胆的使用单机系统。
同时，这种确定性是个一对一的关系，这就使得反过来，外界也能够通过得到的返回结果，推断出系统的状态。
但是在分布式系统里，为了保证可用性，会允许在出现局部故障（partial failure）后，整个系统继续运转。但 partial failure 发生的数量、位置、持续时间等都是不确定的，这就会让系统处于不确定（nondeterministic）的状态。
外界同样的输入，不再一定能得到同样的输出；也无法再根据输出结果来判断系统的状态。
这个判断没问题，局部故障导致的不确定性，就是数据一致性的根源。但还是有点抽象。往细了挖，到底具体又是什么问题，导致了这种不确定性？
不可靠的网络
看一下上面这张简化的网络拓扑图，抛开角色属性后，分布式系统就是许多节点组成的图（graph）。
这些节点，就像太平洋上的一个个岛一样，孤零零的存在，对外界情况几乎一无所知，只能通过唯一的途径 -- 点对点的网络来探索。
通过网络发出一条消息，如果得到回应，对对方就多一分了解；但如果没有得到回应，却连对方不在线这样的否定判断都做不到。
因为实际的拓扑图更像是这样：
各个节点间并不是直连，而是通过交换机等层级复杂的网络设备连接在一起。这些网络设备（甚至还包括网络线路）也会出现故障、堵塞等问题。
所以，对一个发出网络请求的节点来说，其实有对方节点和网络两个变量存在。
类似逻辑与计算，返回结果为 1 能判断二者都正常，但结果为 0 却会有三种情况：
对方节点不正常但网络正常。
对方节点正常但网络不正常。
对方节点和网络都不正常。
这样，有别于单机系统的一对一关系，就出现了一对多的关系。根据返回结果反推系统状态，就不可能了。
甚至，节点正常还可以细分为 crash 类的真死和 GC 等导致的假死。要分辨这两种情况，只能用超时（timeout）来探活。但超时时间应该设置成多少呢？不同的系统和环境都会有自己并不能百分百保证的经验值，这就是所谓的 unbounded timeout 问题。
这就是分布式系统面临的一大难题 -- 不可靠的网络（unreliable networks）。
不可靠的时钟
而对于一系列消息的顺序问题，不再像单机系统那样有唯一的时间来确定顺序。
通常采用本地时钟（local clock）来保证局部有序，然后全局同步时钟来保证整体有序。但时钟的全局同步是很难做的足够高效的，无论是标准的 NTP，还是自己实现的同步协议。
这也就导致在分布式系统下，很难准确而高效的做到全局有序（total order）。
这就是分布式系统面临的另一大难题 -- 不可靠的时钟（unreliable clocks）。
不止这样，仔细想想，时间到底是什么，又有什么用？甚至，时间是真实存在的吗？
这个问题，可以有很多角度去看，可哲学，可物理等等。
我们从计算机的角度来看看。
现代计算机和编程语言大都采纳 Unix 的做法，以 1970 年 1 月 1 日 0 时 0 分 0 秒为起点开始计时，每过去一秒，计时加 1 或 1000（视数据类型和精度不同），也就是所谓的时间戳（timestamp）。
所以，计算机是以时间戳这个计数（counter）来描述时间的，对人类而言更有可读性的表示年月日的 datetime，只不过是换算过来的展示形式而已。
而既然时间是计数，两者相减很可能也有意义，没错，正是我们熟悉的时间间隔（interval/duration）。
所以，其实时间对我们而言有三个维度的属性:
顺序（order）。描述的是定性的先后关系。
间隔（duration）。描述的是定量的先后关系。
可表述性（interpretation）。是以对人类友好的形式描述距离时间基点的间隔。
对应到分布式系统里：
顺序用来明确事件发生的先后，以确保数据一致性。
间隔用来度量期望事件的边界，比如用来探活的心跳、事件处理的延迟等。
-
可表述性，和其他场景一样，被人类用来对照现实世界。
一旦全局时钟得不到保证，在分布式系统里，可表述性上的偏差倒还好，毕竟人类对时间的感受并不那么敏感。但数据强一致性得不到保证，节点探活也可能误判（受网络和时钟双重影响），带来的后果就可能很严重了。
不可靠的网络和不可靠的时钟，这两大难题，正是分布式系统下数据一致性问题产生的根源。
解决一致性问题的根源
根本原因找到了，解决掉这两个问题，好像就能从根本上解决一致性问题了。
解决不可靠的网络问题
对于不可靠的网络，其实没有简单又根本的办法解决。
对于网络本身，无论是交换机等中转设备，还是光纤线、电话线等传输介质，和服务器一样，从物理上就是会有发生故障的可能，不可能完全避免。
提升硬件稳定性和性能，提高运维效率，当然都能有效提升网络质量，但肯定也不可能彻底解决问题。
所以还是只能通过发请求探索，再根据返回结果来推断对方状态。
而无论你去调节超时探活的时间，还是做多步验证等等，都只能做到尽力保证（best-effort guarantee）。
归根结底，一个节点作为一个孤岛，在分布式系统的海洋里，是很难以一己之力了解到整体情况的。
所以要群策群力，要协作。这也是前面文章提到的各种 quorom 算法的解决思路，就不再赘述了。
解决不可靠的时钟问题
第一个办法，既然时钟这么难保持全局一致，那就绕过去，不用时钟。
反正上一节也讲了，时钟的本质只是计数器而言。大不了换一个计数器。
想想我们在数据一致性上，追求的其实是时间的第一个属性 -- 顺序。既然如此，完全可以用一个自增的 ID 来标识这个顺序，相当于 logical clock。
第一个提出这种办法的，正是大名鼎鼎的 Paxos 的作者 Leslie Lamport，所以这种逻辑时钟也叫做 Lamport timestamp。
但是，即便用了自增 ID，一样需要像时钟那样在节点间协商 ID，或者做一个分发 ID 的中心，但又会拖累性能。
那就再退一步，不追求强一致性。因果一致性在大多数应用场景下，已经够用了。
推导到这里，答案已经呼之欲出了，正是我们前面讲过的 Version Number 和 Vector Clock！
具体细节请回顾之前的文章，这里不重复讲了。
这样虽然能满足大部分场景，但毕竟还有些场景的一致性得不到满足，并且节点探活这种需要时间的 duration 属性的场景，也不能被普通的计数器代替。
于是第二个办法，就是直面并解决问题，弄一个真正全局一致的时间出来。
最具代表性的是 Google 的 TrueTime API：
每个机房都有一些 time master，作为机房内的时钟标准。
每台机器都有一个 time slave daemon，来保证和机房内的 master 的时间同步。
大部分 time master 装备 GPS，从卫星同步时间，避免陆上网络设备的影响。
其余 time master 装备 Atomic Clock，靠原子共振频率确定时间，误差可以做到 2000 万年差一秒。
除了从 GPS 或 Atomic Clock 同步时间，master 间还会相互校正，也会和自己的 local time 对比，异常就把自己踢掉。
slave 每隔 30 秒从多个 master（可能在不同机房） 拉取时间，通过 Marzullo 算法踢掉 liars。
典型设置下，本地时钟会有 200 us/sec 的漂移，再加上 slave 每轮 30 秒的同步间隔，理论上会有最大 6ms 的误差，再加上平均 1ms 左右的传输开销，实际误差区间是 0 -7ms。
上图是 Goolge 在多机房数千台机器下的 benchmark。可以看到，整体误差是可控的，99% 的误差都在 3ms 内。左图在 3 月 31 日 网络优化后，误差进一步下降并稳定下来，99% 误差控制在 1ms 内。右图中间的突刺是由于 2 台 master 计划内的维护导致的。
传统的时钟提供的是确切的时间，但这是错觉，看起来没有误差，但实际上是误差不可控（unbounded time uncertainty）。
TT.now()：TTinterval: [earliest, latest]
TT.after(t)：true if t has defintely passed, t < TT.now()
TT.before(t)：true if t has definitely not arrived, t > TT.now()
而从上面 TrueTime 的主要 API 可以看到，TrueTime 做到的是提供确定范围的时间误差（bounded time uncertainty）保证。
节点间协商一定是有不同的传输和处理开销的，不可能做到绝对的完全一致，但能保证真实时间就在这个极小的区间内。
由于 TrueTime 返回的是一个 interval，所以，为了确保两个时间的先后，必须保证两个 interval 没有重叠（overlap），即 t1.latest < t2.earliest。
TrueTime 在 Goolge Cloud 的分布式数据库 Spanner 中得到大量应用。在 Spanner 中，要保证两个事务的顺序性（serializability），就需要在第一个事务 t1 提交完后，等到 TT.now() > t1.latest 后再提交第二个事务，即所谓 commit wait。
上面提到的两种办法，第一种逻辑时钟有很多场景支持不了，第二种物理时钟太依赖特定硬件。因此，诞生了第三种叫做 Hybrid Time（混合时间） 的实现，结合以 NTP 为基础的物理时钟和自增的逻辑时钟，来综合判断事件顺序。
另外，前面讲逻辑时钟，提到中心化的分发中心可能会拖累性能，但也不是绝对的。如果这个分发中心就只做这一件事，并且服务的节点网络质量良好且稳定，比如都在同一个 IDC 内，那也是可以考虑作为第四种时钟方案的。事实上，在 Google Percolator 中已经有了叫做 Timestamp Oracle 的实现。这里就不展开了，有兴趣的同学可以自己去了解。
TL;DR
这篇文章前半部分总结了最近几篇文章讲过的数据一致性问题，不再重复罗列了。只总结下后半部分内容。
数据一致性问题看起来是服务器故障导致的，实际上是分布式系统的不确定性导致的。
具体来说，不可靠的网络和不可靠的时钟，是导致一致性问题的根源。
解决不可靠的网络问题，Paxos 这类共识算法已经给出了出路。
解决不可靠的时钟问题，可以有以 Vector Clock 为典型的分散逻辑时钟、以 TrueTime API 为典型的新物理时钟、以 Hybrid Time 为例的混合时钟和以 Timestamp Oracle 为例的中心化逻辑时钟。
到这里，数据一致性这个章节就告一段落了。当然，前面埋了好几次 exactly once 的坑，我也没忘，后面适当的地方会捡起来专门讲的。
解决了一致性问题之后，我们是不是就可以高枕无忧地享用分布式系统的扩展性带来的威力了呢？
分布式系统，真的就完全是分布式的吗？
下一篇，我们就一起看下，分布式系统里的中心化问题。
关联阅读
原创不易
关注/分享/赞赏
给我坚持的动力