Content #

既然线性一致性不够完美，那么有没有不依赖绝对时间的方法呢？

当然是有的，这就是因果一致性（Causal Consistency）。

因果一致性的基础是偏序关系，也就是说，部分事件顺序是可以比较的。至少一个节点内部的事件是可以排序的，依靠节点的本地时钟就行了；节点间如果发生通讯，则参与通讯的两个事件也是可以排序的，接收方的事件一定晚于调用方的事件。

基于这种偏序关系，Leslie Lamport 在论文“Time, Clocks, and the Ordering of Events in a Distributed System”中提出了逻辑时钟的概念。

借助逻辑时钟仍然可以建立全序关系，当然这个全序关系是不够精确的。因为如果两个事件并不相关，那么逻辑时钟给出的大小关系是没有意义的。

多数观点认为，因果一致性弱于线性一致性，但在并发性能上具有优势，也足以处理多数的异常现象，所以因果一致性也在工业界得到了应用。

具体到分布式数据库领域，CockroachDB 和 YugabyteDB 都在设计中采用了逻辑混合时钟（Hybrid Logical Clocks），这个方案源自 Lamport 的逻辑时钟，也取得了不错的效果。因此，这两个产品都没有实现线性一致性，而是接近于因果一致性，其中 CockroachDB 将自己的一致性模型称为“No Stale Reads”。

Viewpoints #

From #

02｜强一致性：那么多数据一致性模型，究竟有啥不一样？

Links #

Content #

在“前缀一致性”的案例中，问题与答案之间存在一种显式声明，但在现实中，多数场景的因果关系更加复杂，也不可能要求全部做显式声明。

比如对于分布式数据库来说，它无法要求应用系统在每次变更操作时附带声明一下，这次变更是因为读取了哪些数据而导致的。

那么，在显式声明无法奏效的情况下，如何寻找因果关系呢？

不知道你有没有听过这句话，“你所经历的一切，造就了现在的你。”是不是有一点哲学的味道？一切对原因的推测都是主观的，之前发生的一切都可能是原因。

所以，更可靠的方式是将自然语意的因果关系转变为事件发生的先后顺序。

线性一致性（Linearizability）就是建立在事件的先后顺序之上的。在线性一致性下，整个系统表现得好像只有一个副本，所有操作被记录在一条时间线上，并且被原子化，这样任意两个事件都可以比较先后顺序。

这些事件一起构成的集合，在数学上称为具有“全序关系”的集合，而“全序”也称为“线性序”。我想，线性一致性大概就是因此得名。

但是，集群中的各个节点不能做到真正的时钟同步，这样节点有各自的时间线。那么，如何将操作记录在一条时间线上呢？这就需要一个绝对时间，也就是全局时钟。

从产品层面看，主流分布式数据库大多以实现线性一致性为目标，在设计之初或演进过程中纷纷引入了全局时钟，比如 Spanner、TiDB、OceanBase、GoldenDB 和巨杉等等。

工程实现上，多数产品采用单点授时（TSO），也就是从一台时间服务器获取时间，同时配有高可靠设计； 而 Spanner 以全球化部署为目标，因为 TSO 有部署范围上的限制，所以 Spanner 的实现方式是通过 GPS 和原子钟实现的全局时钟，也就是 TrueTime，它可以保证在全球范围内任意节点能同时获得的一个绝对时间，误差在 7 毫秒以内。

但是，对于线性一致性，学术界其实是有争议的。反对者的论据来自爱因斯坦的相对论的一个重要结论，“时间是相对的”。没有绝对时间，也就不存在全序的事件顺序，不同的观察者可能对于哪个事件先发生是无法达成一致的。因此，线性一致性是有局限性的。

当然，从工程角度看，因为我们的应用场景都在经典物理学适用范围内，所以线性一致性也是适用的。

Viewpoints #

From #

02｜强一致性：那么多数据一致性模型，究竟有啥不一样？

Links #

Content #

这天小明去看 CBA 总决赛，刚开球小明就拍了一张现场照片发到朋友圈，想要炫耀一下。小红也很喜欢篮球，但临时有事没有去现场，就在评论区问小明：“现在比分是多少？”小明回复：“4:2。”

小明的同学，远在加拿大的小刚，却看到了一个奇怪的现象，评论区先出现了小明的回复“4:2。”，而后才刷到小红的评论“现在比分是多少？”。难道小明能够预知未来吗？

这是什么原因呢？我们还是看图说话。

小明和小红的评论分别写入了节点 N1 和 N2，但是它们与 N3 同步数据时，由于网络传输的问题，N3 节点接收数据的顺序与数据写入的顺序并不一致，所以小刚是先看到答案后看到问题。

显然，问题与答案之间是有因果关系的，但这种关系在复制的过程中被忽略了，于是出现了异常。

保持这种因果关系的一致性，被称为前缀读或前缀一致性（Consistent Prefix）。要实现这种一致性，可以考虑在原有的评论数据上增加一种显式的因果关系，这样系统可以据此控制在其他进程的读取顺序。

Viewpoints #

From #

02｜强一致性：那么多数据一致性模型，究竟有啥不一样？

Links #

Content #

小明很喜欢在朋友圈分享自己的生活。这天是小明和女友小红的相识纪念日，小明特意在朋友圈分享了一张两人的情侣照。但是，小明发完朋友圈之后，小红一定能看到照片吗？会不会发生异常呢？

这次确实出问题了。

此时，小红也在刷朋友圈，看到了小明刚刚分享的照片，非常开心。然后，小红收到一条信息，简单回复了一下，又回到朋友圈再次刷新，发现照片竟然不见了！小红很生气，打电话质问小明，为什么这么快就把照片删掉？小明听了一脸蒙，心想我没有删除呀。

你猜这中间发生了什么呢？我用另一张流程图来演示这种异常。

在小明发布照片后的瞬间，小红也刷新了朋友圈，此时读取到副本 R1，所以小红看到了照片；片刻之后，小红再次刷新，此时读取到的副本是 R2，于是照片消失了。小红以为小明删除了照片，但实际上这完全是程序错误造成的，数据向后回滚，出现了“时光倒流”。

想要排除这种异常，系统必须实现单调读一致性（Monotonic Read Consistency）。关于单调读一致性的定义，常见的解释是这样的：一个用户一旦读到某个值，不会读到比这个值更旧的值。

是不是感觉有点蒙？让我来解释一下。

假如，变量 X 被赋值三次，依次是 10、20、30；之后读取变量 X，如果第一次读到了 20，那下一次只有读到 20 或 30 才是合理的。因为在第一次读到 20 的一刻，意味着 10 已经是过期数据，没有意义了。

实现单调读一致性的方式，可以是将用户与副本建立固定的映射关系，比如使用哈希算法将用户 ID 映射到固定副本上，这样避免了在多个副本中切换，也就不会出现上面的异常了。

Viewpoints #

From #

02｜强一致性：那么多数据一致性模型，究竟有啥不一样？

Links #

Content #

首先来说“写后读一致性”（Read after Write Consistency），它也称为“读写一致性”，或“读自己写一致性”（Read My Writes Consistency）。你可能觉得最后一个名字听上去有些奇怪，但它却最准确地描述了这种一致性模型的使用效果。

我还是用一个例子来说明。

小明很喜欢在朋友圈分享自己的生活。这天是小明和女友小红的相识纪念日，小明特意在朋友圈分享了一张两人的情侣照。小明知道小红会很在意，特意又刷新了一下朋友圈，确认照片分享成功。

你是否意识到这个过程中系统已经实现了“写后读一致性”？我画了张流程图来表示这个过程。

小明发布照片的延时极短，用户体验很好。这是因为数据仅被保存在主副本 R1 上，就立即反馈保存成功。而其他副本在后台异步更新，由于网络的关系每个副本更新速度不同，在 T2 时刻上海的两个副本达成一致。从过程来看，这与前面所说的“最终一致性”完全相符。

要特别注意的是，小明有一个再次刷新朋友圈的动作，这时如果访问副本 R2，由于其尚未完成同步，情侣照将会消失，小明就会觉得自己的照片被弄丢了。此处，我们假定系统可以通过某种策略由写入节点的主副本 R1 负责后续的读取操作，这样就实现了写后读一致性，可以保证小明再次读取到照片。

自己写入成功的任何数据，下一刻一定能读取到，其内容保证与自己最后一次写入完全一致，这就是“读自己写一致性”名字的由来。当然，从旁观者角度看，可以称为“读你写一致性”（Read Your Writes Consistency），有些论文确实采用了这个名称。

Viewpoints #

From #

02｜强一致性：那么多数据一致性模型，究竟有啥不一样？

Links #

Content #

论文“The many faces of consistency”中的两个概念，状态一致性（State Consistency）和操作一致性（Operation Consistency）。这不是新的一致性模型，它们只是观察数据一致性的两个视角。

状态视角 #

状态一致性是指，数据所处的客观、实际状态所体现的一致性；

状态视角从状态的视角来看，任何变更操作后，数据只有两种状态，所有副本一致或者不一致。在某些条件下，不一致的状态是暂时，还会转换到一致的状态，而那些永远不一致的情况几乎不会去讨论，所以习惯上大家会把不一致称为“弱一致”。相对的，一致就叫做“强一致”了。

对于最终一致性，你可以这样理解：在主副本执行写操作并反馈成功时，不要求其他副本与主副本保持一致，但在经过一段时间后这些副本最终会追上主副本的进度，重新达到数据状态的一致。

“经过一段时间”到底是多久呢？几秒还是几分钟？如果是一个不确定的数值，怎么在工程中使用呢？这就需要我们从操作视角来分析了。

操作视角 #

操作一致性是指，外部用户通过协议约定的操作，能够读取到的数据一致性。

最终一致性，在语义上包含了很大的不确定性，所以很多时候并不是直接使用，而是加入一些限定条件，也就衍生出了若干种一致性模型。因为它们是在副本不一致的情况下，进行操作层面的封装来对外表现数据的状态，所以都可以纳入操作视角。

五种常见的操作视角下的一致性模型。

Links #

Content #

基本可用是说，当分布式系统在出现不可预知的故障时，允许损失部分功能的可用性，保障核心功能的可用性。就像弹簧一样，遇到外界的压迫，它不是折断，而是变形伸缩，不断适应外力，实现基本的可用。

具体说的话，你可以把基本可用理解成，当系统节点出现大规模故障的时候，比如专线的光纤被挖断、突发流量导致系统过载（出现了突发事件，服务被大量访问），这个时候可以通过服务降级，牺牲部分功能的可用性，保障系统的核心功能可用。

流量削峰 #

就拿 12306 订票系统基本可用的设计为例，这个订票系统在春运期间，因为开始售票后先到先得的缘故，会出现极其海量的请求峰值，如何处理这个问题呢？

咱们可以在不同的时间，出售不同区域的票，将访问请求错开，削弱请求峰值。比如，在春运期间，深圳出发的火车票在 8 点开售，北京出发的火车票在 9 点开售。这就是我们常说的流量削峰。

延迟响应 #

在春运期间，自己提交的购票请求，往往会在队列中排队等待处理，可能几分钟或十几分钟后，系统才开始处理，然后响应处理结果，这就是你熟悉的延迟响应。你看，12306 订票系统在出现超出系统处理能力的突发流量的情况下，会通过牺牲响应时间的可用性，保障核心功能的运行。

体验降级 #

你正负责一个互联网系统，突然出现了网络热点事件，好多用户涌进来，产生了海量的突发流量，系统过载了，大量图片因为网络超时无法显示。那么这个时候你可以通过哪些方法，保障系统的基本可用呢？

相信你马上就能想到体验降级， 比如用小图片来替代原始图片，通过降低图片的清晰度和大小，提升系统的处理能力。

过载保护 #

把接收到的请求放在指定的队列中排队处理，如果请求等待时间超时了（假设是 100ms），这个时候直接拒绝超时请求；再比如队列满了之后，就清除队列中一定数量的排队请求，保护系统不过载，实现系统的基本可用。

总结 #

基本可用在本质上是一种妥协，也就是在出现节点故障或系统过载的时候，通过牺牲非核心功能的可用性，保障核心功能的稳定运行。

Viewpoints #

From #

04 | BASE理论：CAP的碱，追求可用性

Links #

Content #

调用 Wait 的时候没有加锁 #

以百米赛跑的程序为例，在调用 cond.Wait 时，把前后的 Lock/Unlock 注释掉:

func main() {
    c := sync.NewCond(&sync.Mutex{})
    var ready int

    for i := 0; i < 10; i++ {
        go func(i int) {
            time.Sleep(time.Duration(rand.Int63n(10)) * time.Second)

            // 加锁更改等待条件
            c.L.Lock()
            ready++
            c.L.Unlock()

            log.Printf("运动员#%d 已准备就绪\n", i)
            // 广播唤醒所有的等待者
            c.Broadcast()
        }(i)
    }

    // c.L.Lock()
    for ready != 10 {
        c.Wait()
        log.Println("裁判员被唤醒一次")
    }
    // c.L.Unlock()

    //所有的运动员是否就绪
    log.Println("所有运动员都准备就绪。比赛开始，3，2，1, ......")
}

再运行程序，就会报释放未加锁的 panic。

出现这个问题的原因在于，cond.Wait 方法的实现是，把当前调用者加入到 notify 队列之中后会释放锁（如果不释放锁，其他 Wait 的调用者就没有机会加入到 notify 队列中了），然后一直等待；等调用者被唤醒之后，又会去争抢这把锁。如果调用 Wait 之前不加锁的话，就有可能 Unlock 一个未加锁的 Locker。所以切记，调用 cond.Wait 方法之前一定要加锁。

Content #

IA-32 处理器支持多任务。在多任务环境下，任务的创建需要分配内存空间；当任务终止后，还要回收它所占用的内存空间。在分段模型下，内存的分配是不定长的，程序大时，就分配一大块内存；程序小时，就分配一小块。时间长了，内存空间就会碎片化，就有可能出现一种情况：内存空间是有的，但都是小块，无法分配给某个任务。

为了解决这个问题，IA-32 处理器支持分页功能，分页功能将物理内存空间划分成逻辑上的页。页的大小是固定的，一般为4KB，通过使用页，可以简化内存管理。如图所示，当页功能开启时，段部件产生的地址就不再是物理地址了，而是线性地址（Linear Address），线性地址还要经页部件转换后，才是物理地址。

线性地址的概念用来描述任务的地址空间。如上图所示，IA-32 处理器上的每个任务都拥有4GB 的虚拟内存空间，这是一段长4GB 的平坦空间，就像一段平直的线段，因此叫线性地址空间。相应地，由段部件产生的地址，就对应着线性地址空间上的每一个点，这就是线性地址。

From #

Links #

Content #

为了解决这个问题，在1996 年的Pentium Pro 处理器上，引入了分支预测技术（Branch Prediction）。分支预测的核心问题是，转移是发生还是不会发生。换句话说，条件转移指令的条件会不会成立。举个例子来说：

jne branch5

在这条指令还没有执行的时候，处理器就必须提前预测相等的条件在这条指令执行的时候是否成立。这当然是很困难的，几乎不可能。想想看，如果能够提前知道结果，还执行这些指令干嘛。

但是，从统计学的角度来看，有些事情一旦出现，下一次还会出现的概率较大。一个典型的例子就是循环，比如下面的程序片断：

xor si, si
lops:
...
cmp si, 20
jnz lops

当jnz 指令第一次执行时，转移一定会发生。那么，处理器就可以预测，下一次它还会转移到标号lops 处，而不是顺序往下执行。事实上，这个预测通常是很准的。

在处理器内部，有一个小容量的高速缓存器，叫分支目标缓存器（Branch Target Buffer，BTB）。当处理器执行了一条分支语句后，它会在BTB 中记录当前指令的地址、分支目标的地址，以及本次分支预测的结果。下一次，在那条转移指令实际执行前，处理器会查找BTB，看有没有最近的转移记录。如果能找到对应的条目，则推测执行和上一次相同的分支，把该分支的指令送入流水线。

当该指令实际执行时，如果预测是失败的，那么，清空流水线，同时刷新BTB 中的记录。这个代价较大。

From #

Links #