大厂面试题精选:线性一致性本质这么回答就对了

知识地图:并发

把面试陪练你会越战越勇，大厂面试题精每周一更新

本系列大约1万字左右，为了节约你的宝贵时间，总结成三页PPT

看完后拉倒文章末尾，先点赞，在阅读

你的点赞是我最大的写作动力！

总结1-组队学习，打boss

问题1我的思考：

总结1-什么是线性一致性问题1我的回答：

总结3-并发领域

正式开始

一、为什么要回答，通过模拟面试驱动，提前练习。

面试官：谈谈你对分布式线性一致性理解

为了让激发你探索欲望，先拿出思考 60 秒下这个问题，期间。

暂停手机滑动
停敲击键盘
更不需要上网查询
这里上来不会直接给出答案

你可以趁着下面时间想一样

中午倒茶水时间
在中午吃饭路上
下午溜达时候

想不出来没有任何关系，就当一60秒放松，

这个不需要背诵，甚至花时间探索，我帮助你研究一些没用知识，

60 秒思考结束

先说什么公式，

如果2 个操A,B并发执行，
他们执行顺序执行不是唯一的，可能AB 或者 BA

就是这么简单，开始。

二、先定义清楚问题是什么，学习路径

1.1 目标与学习方法：

✅ 目标：了解基本概念

1. 什么是顺序一致性

2. 什么线程一致性

3. 顺序一致性与线程一致性他们之间区别？

4. 在工程实践中，做哪些优化（未完待续）

✅ 学习方法

阅读陈东明老师的«分布式系统与一致性»
阅读唐伟志老师的 «深入理解分布式存储系统»
了解TiKV/Etcd源码实现过程，先模仿在创造。

动手练习写无锁LRU 队列

阅读：C++并发编程实战，java并发编程实战

提交 pr,提交 pr（最关键关键一步）

1.2 分布式一致性常概念上常见误区

一致性虽然是我们非常常用的一个词，这个词有太多的含义，

在使用得非常容易混淆概念。

什么是—致性这个问题,会发现不同的人给出的不同的答案

有人会说是CAP定理里面的一致性
有人会提到数据库事务ACID中的一致性
更有甚者会说Paxos或Raft算法中的一致性

通过阅读清楚地知道三者都都不是一致性范围。

个人感受：共识（Consensus）不等于一致性（Consistency）

要指出一个错误观点即把Paxos或Raft称作分布式一直致性算法

完全是中文翻译导致的错误它们的英文单词并不一样，本文Paxos/Raft统称共识算法

一致性则侧重于研究副本最终的稳定状态
共识问题可以用数学语言来准确描述 —个分布式系统包含′!个进程,记为｛0,1’2’…’′′ˉl｝每个进程都有一个初始值，程之间互相通信,设计—种共识算法使得尽管出现故障但进程 ,间仍能协商出某个不可撤销的最终决定值
大白话：

举个生活中的例子’小明和小王出去聚会’

小明问:“小王’我们喝点什么吧?

”小王:“喝咖啡怎么样? ’

’小明; “好啊’那就来杯咖啡,

在上面的场景中,

小王提议喝一杯咖啡,小明表示接受小王的提议,两人就“喝杯咖啡”

这个问题达成共识’

并根据这个结果采取行动

这就是生活中常见的共识

本文重点不是解释共识算法

个人感受：不是ACID中概念上的一致性（Consistency）

ACID的致性属于数据库领域的概念主要是指数据的一致性没有被破坏,

这种一致性要求不仅指常见的数据库完整性约柬

例如用户可以指定数据库字段A和B必须满足A＋B＝l00·

这类一致性不属于本文章一致性讨论范畴

需要指出的是’经常会有人将隔离性也纳入一致性有点类似，但是不完全一样

1.3 一致性模型到到底是什么

一致性模型（与副本有着密切关系）就是指,在并发编程中,系统和开发者之间的一种约定如果开发者遵循某些规则

那么开发者执行读操作或写操作的结果是可预测的

目前一共有超过50种一致性模型，本文一致性模型是

分布式—致性验证框架Jepsen定义的文一致性模型（TIDB 使用 Jepsen 来进行一致性验证）

来自官网 https://jepsen.io/consistency/model

（建议阅读三遍）

Jepsen 是一款用于系统测试的开源软件库，致力于提高分布式数据库、队列、共识系统等的安全性，还可以用于评估分布式系统的正确性，对系统进行一致性验证。

Jepsen已经成功验证了很多分布式系统，包括mysql-cluster、ZooKeeper、Elasticsearch等。

Jepsen的分析报告就曾指出，etcd 3.4.3版本的文档存在对一致性错误的表述2，文档将顺序一致性称为强一致性，很明显，顺序一致性并不是强一致性。不过笔者发现，etcd在后续版本的文档中纠正了这个错误。

In this reference guide, we provide basic definitions, intuitive explanations, and theoretical underpinnings of various consistency models for engineers and academics alike.

在本参考指南中，我们为工程师和学者提供了各种一致性模型的基本定义、直观的解释和理论基础。

Distributed systems are a type of concurrent system, and much of the literature on concurrency control applies directly to distributed systems.

Indeed, most of the concepts we’re going to discuss were originally formulated for single-node concurrent systems.

There are, however, some important differences in availability and performance.

分布式系统是一种并发系统，

许多关于并发控制的文献直接适用于分布式系统。
事实上，我们将要讨论的大多数概念最初都是为单节点并发系统制定的

但是，在可用性和性能方面_存在一些重要差异。

A consistency model_ is a set of **histories**.

We use consistency models to define which histories are “good”, or “legal” in a system.

一致性模型是一组历史记录。

我们使用一致性模型来定义系统中哪些历史是“好的”或“合法的”

图1-本文重点右面的线性，顺序一致性

Unavailable表示：满足这类—致性模型的系统发生网络分区时为了保证数据一致性和正确性系统会不可用
StickyAvailable表示：满足这类一致性模型的系统可以容忍部分节点发生故障还未

出现故障的节点仍然可用,但前提是客户端不能将请求发送到不可用的副本节点

TOtalAVailab 表示: 满足这类—致性模型的系统可用性是最高的即使网络发生严重,分区在没有发生故障的节点上’仍然保证可用。这类—致性模型包括读后写—致性、单调读一致性和单调写一致

翻译：

一致性：

可串行化 / 事务一致性（Serializable）

一致性模型和隔离级别的一个主要区

一致性模型适用于单个操作对象，比如单个数据项或单个变量的读写，该数据可能存在多个副本
而隔离级别通常涉及多个操作对象，比如在并发事务中修改多个数据。

可串行化也分为强一致性和弱一致性,事务隔离级别如下。

| 模型 | 解释 |

| ————————————————————- | —————————————————————— |

| 未提交读 Read Uncommitted (RU) | 最低等级的一致性保证，在事务之中允许读取未提交的数据（Dirty Read） |

| 已提交读 Read Committed (RC) | 在事务中，读取到的数据一定是提交了的，但是不保证这些数据会不会在重复读时发生变化 |

| 可重复读 Repeatable Read (RR) | 在已提交读的基础上，还保证在一个事务中，读取过的数据在重复读中保持不变，但是同样的查询可能会查到新的数据（Phantom Read） |

| 可串行性 Serializability (S) / Serializable consistency | 最高等级的一致性保证，提供和SI同样的保证，但是一般是使用锁而不是快照来实现的，不会在合并修改时发生的错误 |

脏读：

例如，事务T1修改一个数据，事务T2在T1提交或者回滚之前读取到了这个数据。如果T1执行了回滚，那么T2就读取到了一个不存在的值。

在这个例子中，每条虚线表示一个事务，从左到右为时间流逝的方向。

- w（a=1）表示将值1写入a中；

- r（a=1）表示读取a，读取到的结果是1；

- abort表示取消这个事务

不可重复读（non-repeatable read，NRR）

例如，

事务T1读取一个数据，
然后事务T2修改或者删除这个数据并提交。
接下来，如果T1试图再次读取这个数据，
那么它会读取到一个修改过的值，或者发现这个数据已经被删除了。

在这个例子中，commit表示提交事务.

三、什么是线程一致性

线性一致性(Linearizable Consistency)是最强的一致性模型，

通常用Linearizability(可线性化)直接代替LinearizableConsistency，

中文翻译把它们都译作“线性一致性。

线性一致性最开始是由MauriceP.Herlihy与Jeannette M.Wing共同提出的关于并发对象行为正确性的一个模型3，

原始论文中的并发对象主要是讨论单台计算机上的共享变量

虽然线性一致性经常出现在分布式系统的讨论中，

但其实线性一致性是一个并发编程领域的概念，

其涉及领域更为广泛，不只用于分布式系统。

定义

«Linearizability: A Correctness Condition for Concurrent Objects»

地址：https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf

给出线性致性的严格定义是

给定一个执行历史，

执行历史根据并发操作可以扩展为多个顺序历史，

只要从中找到一个合法的顺序历史，,那么该执行历史就是线性一致性的。

即：

只要我们能够把执行历史转为然后判断顺序历史是否合法,

就能知道这个执行历史是否满足线性一直致性。

维基百科定义：

线性一致性（Linearizability），或称原子一致性或严格一致性指的是程序在执行的历史中在存在可线性化点P的执行模型，

这意味着一个操作将在程序的调用和返回之间的某个点P起作用。

这里“起作用”的意思是被系统中并发运行的所有其他线程所感知。

啥玩意，看不懂没关系，太拗口了慢慢往下看，

这里需要补充基本概念

基本概念

Operations：一次操作例如读写操作，发起调用（invocation）事件，返回响应（associated respons）事件
history：历史 A history is a finite sequence of operation invocation and response events.（一个历史是一个由有限个操作的调用事件和返回事件组成的序列）

图 4-就是多个操作组成

3. sequential history：顺序历史(Sequential history)：历史H是顺序的，如果满足以下两个条件：

- H中的第一个成员为调用事件；

- 除了H中的最后一个调用事件之外，H 由相邻的、两两相匹配的调用事件和响应事件组成。

原文：

A history H is sequential if:

(1) The first event of H is an invocation.

(2) Each invocation,except possibly the last,is immediately followed by a matching response.Each response is immediate followed by ainvocation.”

看不懂没关系直接看例子

并发执行与顺序执行

如何达到线性一致

总的来说线性—致性主要有两个约束条件,

第—顺序记录中的任何一次读必须读到最近/最新1次写入的数据;
第二顺序记录要跟全局时钟下的顺序一致。

线性一致性（Linearizability）要求：

所有操作都必须看起来像是在某个瞬间（原子地）完成。
这个瞬间必须位于操作的调用与响应之间。
且整体操作序列与某个串行顺序一致，该顺序要与实际发生时间的先后顺序相

案例1

图 5–历史执行顺序

图表示的行为满足线性一致，为什么

对于同一个对象 x，其初始值为 1
客户端 ABCD 并发地进行了请求，按照真实时间（real-time）顺序
各个事件的发生顺序如上图所示

根据线性一致性定义：上面是4 个客户端，并发执行一个其中要给执行顺序，

然后扩展到多个执行顺序

| — | —- | ————— | ——– | —– | ——— |

| A | 读 | R() → Ok(1) | AB 是并发 | AB｜BA | 一个AB 符合要求 |

| B | 写 | W(2) → Ok() | AB 是并发 | AB｜BA | 一个AB 符合要求 |

| C | 读 | R() → Ok(2) | BC 是先后执行 | BC | 只有一个顺序 |

| D | 读 | R() → Ok(1) | 很早 | 最晚 | ❗返回1 |

客户段 D：为什么返回 1 也合法？

非技术解释：

D 像是打了个很早的电话，但对方很晚才接通（响应）；
在它打电话时，世界还是旧状态（x=1）；
虽然它“听见”消息晚了，但这个电话是早打出去的，所以它看到旧状态也合理。

线性一致性允许的关键在于：

在看这个图，并发关系

操作必须线性化（即可以插入到一个串行的顺序中），
并且线性化点必须落在调用和响应之间
Client D 的读请求虽然很早发出，但它的响应直到很晚才收到，
所以它的线性化点可以放在 B 写操作之前，也可以之后。【并发关系变成2 个历史顺序，只要一个符合要即可】

只要这个“读”在线性时间线上被放在写操作 W(2) 之前，它返回 1 就是合法

|你担心的问题|实际判断标准|

|—|—|

|D 的响应晚于写操作 B，应该看到2|❌ 不成立，因为线性一致性只要求线性化点在调用和响应之间，可以在 B 写入之前|

|D 返回 1 是否违反线性一致性|✅ 不违反，只要我们在线性时间轴中将 D 的读放在写 B 之前|

案例2：

从线性一致性初始论文中找出两个执行历史

请问图中的两个执行历史Hl和H2是否满足线性一致性?

答案:

Hl满足线性一致性
H2不满足线性一致性客户端A最后的write(0) 和客户端 B read(1) 在时间上顺序关系。不满足读取最新写入条件。

个人感受：

一句话概括：在分布式系统上实现寄存器语义，这个单机定义一样，并发执行会有无数历史顺序，从一个历史顺序，推到多个其他执行顺序，只要一个符合要求就满足线性一致性。

总的来说，线性一致性主要有两个约束条件，

第一，顺序记录中的任何一次读必须读到最近一次写入的数据
:第二，顺序记录要跟全局时钟下的顺序一致。
这个第二点是线性一致性非常重要的保证，因此我们不能重排顺序关系的操作，而且还要知道操作之间的先后关系。

如何实现

单机多线程如何实现线程一致性：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21



//i是关键变量

int inc_counter()

{

     lock();

     i++;

     int j = i；

     unlock();

     return j；

}

  

这就是我们最常见的并发编程的线性一致性实现。

还有操作系统都提供了原子比较-交换（CAS）操作。

分布式系统
- 单机并发 CPU级别乱序执行
- 分布式系统无全局时钟，通信延迟高

四、什么是顺序一致性

顺序一致性(Sequential Consistency)是一种比线性一致性弱一些的一致性模型，由LeslieLamport 1979年首次提出的

人们遇到一个陌生的概念时，比较常规的做法是，用自己已知的概念和知识体系来理解这个陌生的概念。

这是一种非常有效的学习方法，但是这里希望读者暂时不要采用这种方法来阅读这一节。比如你之前听说过顺序一致性，或者听说过强一致性、最终一致性等，这里暂时先放下你之前的理解，按照本节的思路（也就是Lamport的思路）来理解顺序一致性

顺序一致性应该是并发编程,顺序一致性应该是并发编程

小提示：

虽然顺序一致性最早是在并发编程领域中提出的，但是它也可以被应用在分布式系统领域中。

顺序一致性同样允许对并发操作历史进行重新排列，但它的约束比线性一致性要弱，顺序一致性只要求同一个客户端(或进程)的操作在排序后保持先后顺序不变，但不同客户端(或进程)之间的先后顺序是可以任意改变的。

按照线性一致性的要求，图3-31中的情况只能得到一种顺序历史，且该顺序历史显然是无法满足线性一致性的。

但顺序一致性可以允许不同客户端之间的操作改变先后顺序,所以图3-31中的执行历史可以重排为如图3-32所示的顺序历史S3。

很明显，图3-32中的顺序历史是合法的，所以该系统满足顺序一致性。由此可见，顺序一致性是比线性一致性要弱一些的一致性模型，满足顺序一致性的模型不一定满足线性一致性的要求。

顺序一致性和线性一致性的主要区别在于没有全局时间的限制，顺序一致性不要求不同客户端之间的操作的顺序一致，只关注局部的顺序。有时顺序一致性往往更实用。例如，在一个社交网络应用中，一个人通常不关心他看到的所有朋友的帖子的顺序，但对于具体的某个朋友，仍然以正确的顺序显示该朋友发的帖子会更符合逻辑。

五、什么是分布式共识算法

未完待续

六、结合开源项目工程优化实践

未完待续

最动人的作品，为自己而写，刚刚好打动别人

我在寻找一位积极上进的小伙伴，

一起参与神奇早起 30 天改变人生计划，发展个人事情，不妨试试

1️⃣ 加入我的技术交流群Offer 来碗里 (回复“面经”获取），一起抱团取暖

2️⃣ 关注公众号:后端开发成长指南(回复“面经”获取）获取过去我全部面试录音和大厂面试复盘攻略

3️⃣ 感兴趣的读者可以通过公众号获取老王的联系方式。

文章目录