什么是顺序一致性，什么是分布式协议

吊打面试官系列:用1 个公式彻底理解线性一致性

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

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

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

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

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

想不出来没有任何关系，就当一60秒放松， 这个不需要背诵，甚至花时间探索，我帮助你研究一些没用知识，

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

策略1：青铜，程小义：

• 思考：工作 10 年竟然无法回答，根本想不起了 后悔，生气 .回答：说想不起来了（无用）
• 思考:有点印象，模糊感觉，说不清楚，回答：然后支支吾吾（无用）

策略 2：黄金,程小义：

• 思考：一切问题都是纸老虎，你相信你可以抓重点，解决主要矛盾，把分布式想象成单节点下多线程，保证并发请下读写数据一致性。
• 回答：线程一致性就是并发情况下，读操作读取读取 写操作写入“最新”数据 ,为了保证并发下线性线性一致性，单节点和多节点 有不同处理方式。。。。。，主要围绕读，写操作展开。

策略 3： 王者，程小义：

• 看论文，参加Tikv比赛，做实验，提交 pr，然后自信回答。
• 看面什么公司，如果滴滴，字节，百度 一面根本不会这样提问，why，互联网主要应用，他们c++ stl 怎么写的，日常for 循环算法写，从熟练到精通，他们工程中遇到问题抽象出来。
• 看面什么公司，传统公司根本提问一致性问题，c++语法 也根本不会，面试 xxx 设计，xxx 如何实现的高大上问题。根本不会循序渐进，不会走，就开始跑这样情况经常出现。

60 秒思考结束

先说什么公式，

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

就是这么简单，开始。

v1.0草稿版本

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

1.1 目标与学习方法 ：

✅ 目标：了解基本概念

1. 什么是顺序一致性

2. 什么线程一致性

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

4. 在工程实践中，做哪些优化 ✅ 学习方法

5. 阅读 陈东明老师的«分布式系统与一致性»

6. 阅读唐伟志老师的 «深入理解分布式存储系统»

7. 了解TiKV/Etcd源码实现过程，先模仿在创造。

4. 动手练习 写无锁LRU 队列 阅读：C++并发编程实战，java并发编程实战

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

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

一致性虽然是我们非常常用的一个词， 但是非常不幸的是，这个词有太多的含义，在使用的非常容易混淆

什么是—致性这个问题,会发现每个人给出的答案都不太-样

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

通过阅读 清楚地知道三者是完全不一样的概念。

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

要指出一个错误观点即把Paxos或Raft称作分布式一直致性算法 完全是中文翻译导致的错误它们的英文单词并不一样，本文Paxos/Raft统称共识算法

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

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

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

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

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

在上面的场景中,

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

这个问题达成共识’

并根据这个结果采取行动

这就是生活中常见的共识

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

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

ACID的致性属于数据库领域的概念 主要是指数据的一致性没有被破坏, 这种一致性要求不仅指常见的数据库完整性约柬

例如用户可以指定数据库字段A和B必须满足A＋B＝l00· 这类一致性不属于本文章一致性讨论范畴

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

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

一致性模型就是指,在并发编程中,系统和开发者之间的一种约定

如果开发者遵循某些规则 那么开发者执行读操作或写操作的结果是可预测的

分布式—致性验证框架Jepsen对一致性模型进行过分类（TIDB 使用 Jepsen 来进行一致性验证） 来自 官网 https://jepsen.io/consistency/models

• Unavailable表示：满足这类—致性模型的系统发生网络分区时为了保证数据一致性和正确性系统会不可用
• StickyAvailable表示：满足这类一致性模型的系统可以容忍部分节点发生故障还未 出现故障的节点仍然可用,但前提是客户端不能将请求发送到不可用的副本节点
• TOtalAVailab 表示: 满足这类—致性模型的系统可用性是最高的即使网络发生严重,分区在没有发生故障的节点上’仍然保证可用。这类—致性模型包括读后写—致性、单调读一致性和单调写一致

翻译：

一致性：

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

参考

• http://www.bailis.org/blog/when-is-acid-acid-rarely/
• https://github.com/ept/hermitage

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

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

• w（a=1）表示将值1写入a中；
• r（a=1）表示读取a，读取到的结果是1；
• abort表示取消这个事务

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

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

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

三、什么是线程一致性

定义

«Linearizability: A Correctness Condition for Concurrent Objects» 地址：https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf

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

给定一个执行历史， 执行历史根据并发操作可以扩展为多个顺序历史， 只要从中找到一个合法的顺序历史，,那么该执行历史就是线性一致性的。

即： 只要我们能够把执行历史转为然后判断顺序历史是否合法, 就能知道这个执行历史是否满足线性一直致性。

维基百科定义：

线性一致性（Linearizability），或称原子一致性或严格一致性指的是程序在执行的历史中在存在可线性化点P的执行模型， 这意味着一个操作将在程序的调用和返回之间的某个点P起作用。 这里“起作用”的意思是被系统中并发运行的所有其他线程所感知。

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

这里需要 补充基本概念

基本概念

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

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

案例1

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

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

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

然后扩展到多个执行顺序

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

非技术解释：

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

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

• 操作必须线性化（即可以插入到一个串行的顺序中），

• 并且线性化点必须落在调用和响应之间

• Client D 的读请求虽然很早发出，但它的响应直到很晚才收到，

• 所以它的线性化点可以放在 B 写操作之前，也可以之后。【并发关系 变成2 个历史顺序，只要一个符合要即可】

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

案例2：

从线性一致性初始论文中找出两个执行历史 请问图中的两个执行历史Hl和H2是否满足线性一致性?

答案:

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

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

如何实现

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

//i是关键变量
int inc_counter()
{
	 lock();
	 i++;
	 int j = i；
	 unlock();
	 return j；
}

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

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

2. 分布式系统

四、什么是 顺序 一致性

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

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