可靠分布式系统-paxos的直观解释 - OpenACID Blog

[giscus[bot]]

可靠分布式系统-paxos的直观解释 - OpenACID Blog

没有paxos的一堆机器, 只能叫做分布式; 有paxos协同才叫分布式系统. 咱得把paxos聊开了聊透了

https://blog.openacid.com/algo/paxos/

[ClSlaid]

精彩

[wodeqiangne]

请问下slide-09到slide-10之间，有一个改变是，从client只和一个server交互，并且由改server复制分发到其他server节点，变成了client直接和所有server交互，这个改变对后面的结论推导有影响吗

[drmingdrmer]

slide 9和10 还没开始将paxos呢...列了几个常见的模型. 对后面没影响.

[sin-coder]

是不是 MySQL 半同步复制也可以理解为多数派读写的一个🌰呢

[drmingdrmer]

嗯呐

[sin-coder]

感谢xp老师 收益匪浅

[drmingdrmer]

哈哈哈 你都有收益了? 我还没有收益 🤔

[MrLiukang]

🐂

[tenwz]

感谢作者

[junli1026]

感谢xp老师！
请教个问题，slide-34，classic PAXOS 有冲突的情况下，X 第一次失败，然后increase rnd(我理解为version），尝试第二次。 这时候为什么是“修复”而不是去“覆盖”呢？毕竟这时候 rnd=3是一个最高的版本。

[junli1026]

我换一个问法，如果这时候是Z (不是X）来写，
Phase 1: 发送 Round=3， 收到（v=“y", vround=2) (v="x", vround=1)
Phase 2， 应该是发送 （v=“y", vround=3) 还是 （v=“z", vround=3) ？

[ningowo]

我觉得是发送 （v=“y", vround=3)。有个地方我也是刚想明白，不完全确定但应该是这样的：如果在phase1期间遇到更大的rnd，这一轮的实际值就被更大的抢走了，此时只是帮着把最大的更新到其他acceptor。如果小的proposer想再把自己的值进行更新，需要重新进行一轮phase1，看看能不能抢到最大的rnd。

[drmingdrmer]

我换一个问法，如果这时候是Z (不是X）来写， Phase (相) 1: 发送 Round=3， 收到（v=“y", vround=2) (v="x", vround=1) Phase (相) 2， 应该是发送 （v=“y", vround=3) 还是 （v=“z", vround=3) ？

是发（v=“y", vround=3). 只要在phase-1看到了其他值, 那么proposer就需要假设这个值是已经committed的, 即之前被acceptor多数派接受了, 于是根据不能修改已提交的值的原则, 它就不能写y以外的值.

(貌似我之前漏掉了这个消息🤔

[SolarZone]

老师你好，我疑惑的点是在，在实际的业务场景中，一个值肯定会被多次修改，不可能说第一次被修改成功后，后续就不能再修改了。这与不能修改已提交的值的原则相违背。请问这个应该如何解释呢？是否可以理解为，v指的其实是某个值的一个版本，当这个值的这个版本被确定后就无法被修改，业务场景中后续的修改其实是set了这个值的新版本

[drmingdrmer]

是否可以理解为，v指的其实是某个值的一个版本，当这个值的这个版本被确定后就无法被修改，业务场景中后续的修改其实是set了这个值的新版本

嗯, 就是这样的:D

[LotusMoonChen]

xp大佬 麻烦问下 假如说有这么一种情况 proposer x先进行phase1阶段 在1，2节点上写入了rnd 为1 但是在进行phase2的时候 proposerX只写入了 acceptor就挂掉了了 现在的情况是 acceptor1上 存的是 last_rnd = 1, vrnd = 1, v = x 但是在acceptor2上 存的是 last_rnd = 1, vrnd = 0, v = null, 这时候 proposer Y 进行多数派读 读的是 acceptor2， 3 因为这时候Y的rnd是2，所以propser Y进行phase1 的时候 将acceptr2， 3写入last_rnd = 2, 然后在phase2 的时候写入acceptor 2，和 3 ，假如这时候proposer在写入了acceptor之后就故障了，这时，acceptor1上存的是last_rnd = 1, vrnd = 1, v = x acceptor2上存的是last_rnd = 2, vrnd = 0, v = null acceptor3上存的是 last_rnd = 2, vrnd = 2, v = Y， 这时候如果进行多数派读的时候，选取acceptor1，2和选取acceptor2，3 拿到的值不就不一样了嘛，这时候如何保证一致性

[drmingdrmer]

是的.

除非读的时候访问的quorum都返回同样的值. 这时可以保证之后的读也肯定读到相同的值.

[LotusMoonChen]

明白了 感谢大佬

[tailwolf]

这里我还是有个疑问，按照层主的这种场景，读的时候重新走一遍paxos，比如执行proposerZ修复之前的不一致，但这时会有两种情况：

1.假如读到acceptor1，2，重新走一遍paxos。acceptor2的last_rnd最大，所以选取acceptor2的v，但由于v=null，所以把节点的值修复成Z。

2.假如读到acceptor2，3，重新走一遍paxos。acceptor2，3的last_rnd都相同，但是v不同，一个为null，一个为Y，这时取哪个值去修复呢？
2.1.假如选取v=Y去修复，又有个问题，这是不是说明修复的过程中，读取到大多数节点不同，修复的值就不同，这种情况是允许的吗？

[drmingdrmer]

2. 必须选Y, 必须选vrnd较大的, 较小的一定不是已完成提交的, 较大的是可能完成提交的.
   2.1 是的, 修复出来的结果可能不同, 分布式一致性算法只要求完成提交的总是能被读到, 如果某个场景下能修复出多个值, 说明这多个值都没有到达提交的条件, 即复制到半数以上的节点. 所以并没有破坏一致性的要求.

[tailwolf]

了解了，感谢大佬

[wangqiim]

好像漏掉了get的过程

[drmingdrmer]

观测即修改, get也是走一次paxos来读.

[ningowo]

以前只看到xp的ppt，勉强理解了一下但没完全懂。现在再次学习，感觉看这篇文章突然清晰好多，完全理解了哈哈哈。就是信息量还是大的，优化部分休息一下晚点再看。作者nb！就喜欢这样说人话的讲解，努力向你学习~

[stg609]

很精彩，但有个疑问：
slide11 中提到 “一个要进行读取a的客户端如果联系到了node-1和node-2, 它将看到2条不同的数据.”, 根据 slide 10 中对 “多数派读” 的定义（每次读取数据都必须检查半数以上的机器上是否有这条数据.），那客户端就不应读取到2条不同的数据，因为这两个数据都不符合“半数以上"。

[drmingdrmer]

多数派读是指"联系到半数以上的服务器节点", 不是指能读到半数以上个某条数据的副本.

[Big-Wuu]

大佬，想问下：rnd全局唯一可以理解，但一定要单调递增吗？可以只有偏序关系吗？
比如文中的(round, serverId)，两个不同的proposer分别使用(1, 1)和(1, 2)作为rnd，acceptor把这两个请求看作是并发的，在phase-1阶段，只有rnd大于last_rnd时才更新，比如先后接到(1, 1)和(1, 2)，那么拒绝掉(1, 2)。感觉这样好像也可以？

[Big-Wuu]

写错了... (round-1, serverId-A) <= (round-2, serverId-B) <=> round-1 < round-2 or 相等

[drmingdrmer]

(round-1, serverId-A) <= (round-2, serverId-B) <=> round-1 < round-2 or 相等

这个应该是一个全序关系: 因为任意2个(round,server_id)都有一个大小关系. X<=Y 或 X >=Y.

但这个全序关系不去考虑server-id的话, 会让2个proposer产生相同的rnd.导致acceptor无法区分2个不同的proposer.

标准paxos里定义的rnd是: rnd{n: u64, server_id: u64} 这样的, 比较关系是 rnd₁ < rnd₂ === rnd₁.n < rnd₂.n || (rnd₁.n == rnd₂.n && rnd₁.server_id < rnd₂.server_id).

[Big-Wuu]

(round-1, serverId-A) <= (round-2, serverId-B) <=> round-1 < round-2 or 相等

我可能没写全，“相等”是想说完全相等，也就是rnd₁ <= rnd₂ === rnd₁.n < rnd₂.n || (rnd₁.n == rnd₂.n && rnd₁.server_id == rnd₂.server_id)。这样(1,1)<=(1,2)和(1,2)<=(1,1)都不成立。

[drmingdrmer]

明白了, 如果是这个设定你应该是差不多独立发明了raft. :D

raft里的偏序关系是 rnd:{term: u64, voted_for: Option<server_id>}(虽然paper里没有明确这么描述出来, 但逻辑是这样的), term 不同时直接由term决定大小, 同一个term内, 投票给server-x就不能再投票给server-y, 除非server-x和y是一样的. 这就是说它建立了一个偏序关系, 跟你的设定几乎完全一样. (除了raft的voted_for也可能为nil)

[Big-Wuu]

我昨晚又看了您的abstract-paxos那篇文章，看到这块时大为震撼，很有帮助，准备再多看两遍~

[comicchang]

ppt做的很棒，但是博客图片中的文字混合了中文字型和日文字型，强迫症很难受

[ye-xiaowei]

xp大佬，slide-09 中提到a,b,c 三个请求，如果是三节点的半同步会变成 abc，ab, ac 等master节点挂了会有不一致的问题，那如果要求按照顺序复制呢就是说必须abc、ab，不允许ac。那半同步是不是没有其他问题了

[drmingdrmer]

那如果要求按照顺序复制呢就是说必须abc、ab，不允许ac。那半同步是不是没有其他问题了

半同步复制这里没有限制更多条件所以不好说. 要达到"没有其他问题"的要求, 实际上就是把它改进成一个raft了.
这里你要求不出现ac, 也就是提供了raft中的日志必须连续的要求.
要达到强一致, 至少还需要另外2个条件:

• 数据写到多数派才看做是提交了; 新的master必须拥有一个多数派中所有的日志;
• 有个vote, 也就是paxos的选主的过程

[ye-xiaowei]

这两个条件我要是不去满足多数派是不是也能够达到强一致，比如：假设有5节点，有选举机制，有三种身份 master、follower、learner。master和follower都是通过选举出来的，没选举的叫learner。master 1个，follower n个。

1. 必须在主节点读写
2. 必须同步到follower才算操作完成。
3. master挂了从follower选举，follower挂了从learner选举

是不是只要我master和follower别都挂了就能保证强一致性。这是我瞎想的但是好像也没啥毛病

[drmingdrmer]

说的太简单了我无法判断 😭, 例如写几份, 如何选举这些都没有讲.

不过如果一个分布式系统, 提供强一致, 并且不依赖外部时钟, 一定是paxos同构的(如果提供多条日志写那就是几乎raft同构的).

[ye-xiaowei]

好像确实越说越想raft了hhhhh

[from-Pb2Ag]

老师您好, 文章非常具有启发性! 但是Slide34~35我有个问题还是不太明白:

如果client x目的是想让"x"复制到多数机器上达成共识, 那么当phase1-B结束后它收到了{{v="y", vrand=2}, {v="x", vrand=1}}两条记录后, 选择去"修复"v="y", 那么就这个过程而言. "x"永远不可能被commit并达成共识啊. 那如果client x还想让"x"复制到多数机器上达成共识, 是不是只能去开一个新的paxos实例 (这是不是和上面网友说的"set这个值的新版本"比较一致?)?

还是说client x的目的不是set成自己希望的值, 而是让系统就某个值 (在一个特定的版本上) 达成共识?

[drmingdrmer]

"x"永远不可能被commit并达成共识啊.

是的, 这时这个paxos 实例没法写x了.

那如果client x还想让"x"复制到多数机器上达成共识, 是不是只能去开一个新的paxos实例

是的, 只能在另外一个实例中写入x的值

还是说client x的目的不是set成自己希望的值, 而是让系统就某个值 (在一个特定的版本上) 达成共识?

client x的目的是写入自己希望的值x, 但是如果有其他值了, 就必须写这个其他值, 放弃自己要写的x. 然后在另外一个paxos实例中再次尝试写入x

[from-Pb2Ag]

感谢老师, 这次懂很多了!!!!

[xxxuuu]

老师您好，有两个地方比较疑惑：

1. 文中貌似没有提到 Acceptor 上的 v 和 vrnd 是否会进行清理及其时机。如果每次写入后都会记录 vrnd 和 v 的话，这样的话不就是后续每一轮提议中 Proposer 都会重复执行同一个 v 的恢复流程了吗？
2. 如果某个 Acceptor X 长时间 down 后，在 Proposer 执行恢复时，看起来会直接写入最新 rnd 的 v，这里中间 rnd 的 v 就被跳过了？对比来说 Raft 在恢复时会按顺序 apply log，更有全序广播的概念，这是否是需要应用层自己来实现？

[drmingdrmer]

Paxos 是一个单值的算法, 只记录一对(vrnd,v). 所以也不存在清理的问题了.