要点：

单点到多节点 i++并发方案

1. 只有1个节点，用锁
2. 只有2个节点，一个是客户端，一个存储节点，查询加锁，更新解锁
3. 如果多个节点，通过2轮RPC 执行多数派方式接受一个值（被确定了）。
4. 提案被批准一定不会被修改，意思是可以更高提案编号，但是提案值不变。
5. 提案被被接受，最后可能会被修改，也可能不会被修改，不确定
6. 本文最清楚分析个人认为第二章节 2.3 情况2，根据图片给出观察结果 总结论是对的，然后分析执行过程。

说明：本文先阅读参考网络公开课和 作为学习资料，其中图片来源截图

大纲

• 缘起：OceanBase布道师计划
• 从单机到集群遇到并发问题
• Base Paxos多节点并发场景演示
• Multi-Paxos  多节点并发场景演示

一、缘起：OceanBase布道师计划

没有太多实战经验，为了理清自己的思路，本篇文章采用模拟2人对话方式，如有误，欢迎指正。

一天下午，小王 和老王 在咖啡馆相遇，展开如下讨论

小王：作为一个业余数据库爱好者，没有时间，没精力该怎么学习？

老王皱了一下眉头问：什么是业余数据库爱好者？

小王：就是公司业务不使用数据库，分布式数据库，日常工作不写sql，也不用数据库一些特性。

更不要说研究数据库了，工作一忙就中断,

老王：停，先别考虑困难，说你期望，你目的是什么？假如你克服了苦难，最后效果是什么

小王尴尬一笑回答道：作为一个业余数据库爱好者，我看到一篇文章 2024 OceanBase布道师计划

我想通过1-2个月写并发 的文章，不知道写什么？

老王：谈谈你对并发理解?

小王：

在学习编程语言时候遇到第一个问题单机下多线程i++

伪代码如下

int i =0 //全局变量
inrc()
{
  lock
  i++
 unlock
}

在工作时候遇到服务端存储i，客户端更新方式

伪代码如下

int i = read() //一次tcp调用，通过加锁读方式获最新变量的值
i++
write(i) //一次tcp调用，写完后，然后解锁，这个读写期间都是一直加锁。

老王：Paxos 也是解决数据一致性问题 从paxos入手, 更容易去掉无关干扰, 直达问题本质。

小王同学写到：

作为一个业余数据库爱好者，通过1季至少写1篇并发文章方式，成为贡献者。

二、从单点并发升级到多节点并发

小王点了2杯咖啡，然后问道

OceanBase 使用 分布式共识算法 Multi-Paxos 来保证多数副本之间的强一致以及高可用，

这个是什么含义，怎么想也想不通，尤其解决乱序问题？

老王：在工作中没有接触实际项目，也没有做过设计设计，无法理解也很正常，一分为二，让我们回到过去从自己 可以理部分开始

假设一个系统2个客户端节点，3个存储节点组成，3个存储节点只存储一个变量 i，变量i可以不同的版本 i1,i2..in组成。

• 存储系统使用  多数派策略读写数据  公式：W+R > N
• set(n): 写变量n值到大多数节点，i版本增加。
• get():  根据公式 R >N-W 即可。假如3个节点，主要读超过1节点。 获取变量i最新版本值
• 利用set，get函数实现一个inc（n）对变量i值增加N。很显然 ，inc函数不上原子操作

1. 客户端节点x通过 get 获取当i最新版本值 ver=1，value=2

2. 客户端节点x内存操作 i=2+1 ，这个时候下个版本ver=2

3. 客户端节点x 调用set，i写到大多数节点

旁白：

原子个人理解： 即这些操作在执行过程中不会被其他线程中断 ，其顺序不可以被打乱

第一次听原子是通过一个题目  int i =1 是原子操作吗？i++是原子操作吗？

在cpu执行时

• 第一步，先将 count所在内存的值加载到寄存器；
• 第二步，将寄存器的值自增1；
• 第三步，将寄存器中的值写回内存。

多个线程在执行这上面指令时，某个线程可能会在第一条指令执行完毕后被剥夺CPU时间片，切换到另外一个线程而产生不确定的情况。

在假设存储系统中依然用原子这个词语描述 是

客户端节点视角看  简单理解 多个节点操作，像一个节点一样。

这里不用一致描述，ACID中有约束一致性，CAP中也有线性一致性等描述不同稍微概念上区别。

小王同学提问1 ：read 大多数节点 保证获取最新值，write操作写大多数节点不一定正确？

如果有2个并发的客户端x,y同时做这个inc的操作, 一个加1操作，一个加2操作

最终期望i看出5，但是历史执行顺序看，结果不是5，更新操作 遇到并发怎么处理？

小王同学提问2 :  如果让y更新识别到x已经更新值？

上面例子，因为 更新读（先读后更新没有使用加锁方式），y在知set之前

需要使用一次多数派策略去取查询 别到x是否更 新值？

同样遇到x也使用多数派策略去取查询 别到y已经更新值？

还是不行，同样遇到并发问题？

图片来源： 可靠分布式系统-paxos的直观解释.pdf

老王喝了一口咖啡回答到：

提问1只有1个操作 set，客户端x执行set，客户端y执行set出现问题。

提问2只有2个操作，先get查询判断假设没有变化，然后set，

客户端x在执行set之后，客户端y执行set出现问题。

这说明什么

1. 更新前检查：通过在更新前 做检查判断这个方式不能100%预防这个情况。
2. 更新后检查：这里假设是什么，x更新之后，不能允许y在更新，y一个更新就出错。

必须允许这个情况发生， 聪明你想到 乐观锁类似用法，就是遇到变化就回滚。

这里不进行回滚操作。请看3

1. 在此回到我们目的，假设系统值存储一个值，这个值 有2个情况（没有写入，写入）

我们目的确定一个值，并且这个值被确定后不会修改，并没有规定一定是x更新的，或者y更新的。

并发情况，无人能保证这个顺序。我期望结果是，

• 客户端x，客户端y 都执行更新读，从时间先后顺序上， 只允许最后一个完成 更新读取 的进程可以进行后续写入, 同时拒绝之前做过 更新读 的进程写入原来权限，然后更新最新的值。
• 假如 客户端x 先更新成功，客户端y更新 时候按照x更新的值（这里假设只更新一个值，这个值有没有更新它当前节点一定知道，其他节点通过步骤1查询时候返回）。
• 假如客户端y先更新成功， 客户端x更新 时候按照y更新的值（这里假设只更新一个值，这个值有没有更新它当前节点一定知道，其他节点通过步骤1查询时候返回） 在更新一次

满足 确定一个值，并且这个值被确定后不会修改，并且还有允许冲突发生。

这个小王 根据上面对话个人理解，并完整流程描述，方面就是为通过例子看并发场景何为 simple paxos算法做准备

你是否有点看的不明白。这个图片可能演示更清楚

三、Base Paxos多节点并发场景演示

小王提问：通过上面例子 ，很容易理解，只要一个存储节点 接受一个变量值i，其他节点都按照这个值存储，这个方式真可行吗，这个方式扩展5个节点依然可以吗？

老王说：通过下面三个例子对比说明一下，再次之前 重新假设一下目前系统设计。（也可以跳过直接看例子）

Basic Paxos 通过2次RPC确定一个值，第一次RPC发送是案编号，第二次RPC发送提案编号和提案值。

提案编号表达方式： n 是单调递增，server_id 节点编号

提议者（preoposer），接受者（acceptor），学习者（这里不讨论该角）简单理解都是节点

Base Paxos 算法主要包含2个阶段，每个阶段分为 a,b c 3个部分，分别对应 RPc请求阶段，处理阶段，和响应 阶段（个人理解）

步骤如下：

第一阶段

1. 第一次RPC请求，叫做Prepare阶段，也称 phase 1 a ，

提议者收到客户端请求后，选择最新提案编号n=n+1，然后广播给大多数节点

伪代码 ：prepare（n）

2. 第一次RPC响应 叫做promise阶段，也称phase 1 b

如果提案编号n大于之前所接受的全部提案编号，返回接受新的提案编号。

并返回上次接受到的提案编号 和提案值。不然拒绝

伪代码：

if n >minProposal(目前接受到最大提案)

minProposal =n

//如果没有接受过说明是空值

reutrn promise（n,acceptedProposal,acceptedvalue）

1. 第2次RPC请求，叫做Accept阶段，也称 phase 2 a

如果过半数节点同意，提议者发起Accept（n,value),注意 这次一定 有2个参数， 提案编号，和提案值

这里有个问题。提案值怎么选择？

如果 接受者 返回接受的值，选择提案编号最大值，作为本次提案值。

如果没有返回任何提案值，写入可以自行决定。

Base Paxos 强调是，一旦一个值被批准，未来提案必须使用提议相同值。

提案值判断 伪代码：

last =0

循环：

if（acceptedvalue && acceptedProposal >last(上一个节点的)）

v = acceptedvalue

last= acceptedProposal

else：

v= value

第二阶段：

4. 第2次 rpc 提议者请求 发送 accepted（n，value）也称作 phase 2 a

1. 第2次RPC 接受者执行 accepted（n，value），phase 2 b。

如果接受者遇到更大编号提案，大于n，因此拒绝提案，（对比上面并发例子，允许冲突发生，默认后来者更新值。不然接受新的提案，和新的值。更新承诺的最小提案

1. 第2次RPC 响应阶段 phase 2 c。

如果多数派响应并无拒绝，提案被批准，value is chosen

旁白：接受提案只需要一个节点同意，批准提案需要大多数同意。

反过来 已经被批准值，不会被修改，已经接受值 根据实际情况。请看下面三个例子

情况1:提案被批准：

客户端x提案3.1 （3是提案编号，1是服务器id）和客户端提案4.5都被批准，提案值相同的只有一个

客户端x

（1）节点S1 接受客户端X写请求，第一阶段，s1发送prepare（3.1）请求到s1，s2 ，s3到节点

请求接受者对提案编号3.1（提案编号-服务器id）的提案进行投票，

接受者接受提案，因为接受者（s1，s2,s3）没有接受过其他提案，回复同意的响应，并告诉提议者 我之前其他提案

因此s1判断本次 提案编号3.1，提案值 x。

小王个人理解请仔细辨别：

目的是决议出单一的值，这个值2个情况，已经写入，还没有写入。接受者（s1，s2,s3），类似伪代码： if(一个标记判断该值是否写入)

（2） 第二阶段，提议者S1发送 Accept（3.1,X) 到 接受者（s1，s2,s3）,接受者没有接受过更高的提案,

因此他们接受提案3.1，提案值x， 满足超过半数节点接受提案的条件，提案被成功批准。

提案值 从接受到批准过程完成

到这里 s1 s2 s3 完成2个次RPC确定一个值，被确定值不会被修改，后面客户端y 发起更高提案，

但是提案值不会改变。y更新不覆盖之前写入

客户端Y

(1) 第一阶段： 提议者S5，发起更高的提案（4>3）Prepare（4.5）请求

接受者（s1 s2 s3），接受更高的提案4，

Paxos强调：

一个值在提案3的时候已经被批准，大多数接受者必然返回Promise（4,3,X）

未来的提案4必须提议相同的提案值：

提议者对新的提案值 原本的Y替换成被批准的X

Accept（4.5,X）

(2) 第二阶段 提议者S5 发送Accept（4.5,X）请求， 提案编号为新的4.5，但是提案值 X。

之后提案再次被批准 最后结果必然是X。

情况2 提案被接受，提议者可见（运用多数派查询到）

根据上图看到情况2最终结果是：

客户端X，客户度端Y 并发写入，分别对应提议者S1和S5，

最终存储系统 对一个值达成一致 批准X。

满足了 一个值被接受后，有可能不会被修改情况。

情况2推到过程：

根据实际时间顺序

T1: 提议者S1发起提案3.1，但是只有接受这S3.接受，如图 s1 和 s2 有延迟 在未来T3时刻才会到来。

此时没有满足过半接受者接受被批准的条件。

T2:提议者S5发起更高提案4.5，接受者接受新的提案编号，此时只有接受者S3 已经接受了提案值，

S3回复时候必须包含提案3  Promise（4.5,3.1,X)

T3:提议者S5提案编号4 的提案值，选择接受者S3回复的提案值

Accept（4.5,X),依然将提案值 Y替换成X。保证了X 已经被确认，不会被修改

情况2 还说明一个情况 只要一个接受者在第一次RPC 响应返回了提案值，就用它替换。

对应题目，如果只有一个接受了，没有过半同意，下次请求提议者未必请求该节点。这说明并发不可控制部分。

未必每次发都是S1 S2 S3都返回。

情况3:提案被接受，提议者不可见（运用多数派查询不到）

如上图执行结果：

客户端X，客户度端Y 并发写入，分别对应提议者S1和S5，

S3是是焦点，S3允许接受多个值，因为并发关系，设定接受最后一个更新读请求。

假设的存储系统最后执行 结果是 S1 和S2 接受提案X，S3 S4 S5接受提案Y。

最终提案值Y被批准，没有被破坏

分析如下：

情况3 如上图 S3 没有接受提案编号3.1的值，S1接受了提案3.1, 因此在提案编号4.5

时候，S3 S4 S5 在第一阶段没有返回任何提案信息。S5 自定决提案值Y。

在第二阶段发起Accept（4.5,Y）请求，因为4.5 >3.1

S3 最后拒绝Accept（3.1,X)请求，接受Accept（4.5,Y）请求。

最后结果 S1，S2 接受提案3.1 ，S3，S4，S5 接受提案4.5

最终结果 提案值Y被批准。

老 王：别人都解释很清楚了，直接拿出来更合适

四、Multi-Paxos  多节点并发场景演示

小王：base paxos 一次决策一个值，Multi-Paxos是不是多次运用base paxos决策多个提案呢？如何解决乱序呢

老王：在 并发下执行 执行顺序 无法确定的，

在网络传输中存在消息丢失，乱序情况，因为没有真实案例这里不会详细说明

paxos 执行条件 容忍这些情况发生，不过

现在让我们对系统进行升级 现在假设存储系统3个节点，需要决策很多提案，

这些提案存储到日志中，日志目的是复制状态机。

增加日志index，index代表需要决议的那些值

举例说明：

• s1 s2 s3 组成一个存储集群s3故障，
• 1-7代表日志索引编号。这里说明提案编号没有消失，只是没有显示。
• 提案的值是命令 move add cmp ret都是汇编命令

日志有下面三个状态：

• 已经被批准，例如S1 加粗的 1 ，2， 6 这个位置。（6这个位置奇怪，这个和raft不一样，raft强调是当前index被批准，小于index都会被批准）
• 被接受，但是没有被批准 例如 节点S2中的第4条值为sub的日志。从上帝视角看，s1 和s3还 没有接受，必然不会被批准。
• 空记录，接受者s1 第4，5个位置，没有任何提案，但是同样位置 s2第四个位置，s3第5个位置提案。

至于什么造成的不清楚，工程实践怎么解决不清楚。下面演示的是 在有新的请求情况下 该如何处理

下面演示的是 在有新的请求情况下 该如何处理

客户端发起jump命令请求，s1是提议者 执行步骤

1. 选择一个为提交索引
2. 运行一次Paxos算法，如果该位置有接受提案，先 按照已经有提案提交来同步数据。

重新执行步骤2 。

1. 如果该位置无已经提交的提案，提交请求值。

1. 通过上图观察到 s1 索引 1，2 已经被批准，被批准值不会修改，

索引3 提案值是cmp 被接受，S1第一个没有被批准索引位置是3，没有批准可能被覆盖吗 （这里没有raft 一个位置对应不同值。同一个位置不不同值情况，这里清不清楚）

1. 提议者S1 运用一次Base Paxos 算法 判断， 在位置3 已经有提案，因此选择cmp 继续提交 代替jump命令

让S1，S2，S3 在位置3达成一致 都是cmp

到这里 S1 提交的是cmp命令 不是jump命令 ，因此继续选择索引位置4

1. 接受者 s1 在位置4是空记录，在位置 4运用一次Base Paxos 算法，

在第一次RPC执行过半数Prepare阶段，S2返回已经接受的sub命令。

第二次RPC执行过半数Accept节点，写入sub命令。

位置4达成一致的 sub命令,代替jump命令 ，因此继续下一个索引位置5

5. s1 和 s2 在索引 5都是空记录，但是s3已经故障，不会返回结果。

在第一次RPC执行过半数Prepare阶段 不会返回已经接受提案，

最后第5个位置 在运用一次Base Paxos 算法达成一致的 jump命令

最后响应客户端写入成功。

最后结果：

提议者s1 从3位置开始写入 jump命令，因为"可见到接受到提案"，先遵循这一个重要原理，不断同步原来提案达成一致，

然后最后在位置5达成一致 jump写入成功。

                    图片来源Paxos lecture