Zander Alastor's blog
では、ゲームを始めましょう
GO FOR IT !
学习笔记

quorum与paxos与raft

Zander Alastor 2024 年 09 月 6日

总结

  • quorum问题: 脏读 -> 多数派读解决
  • 多数派读写问题: 丢失修改(未提交数据覆盖已提交数据) -> paxos解决
  • paxos问题: 活锁 -> multi-paxos解决
  • multi-paxos问题: 数据可用性低(没有数据追赶) -> raft解决

quorum

1. quorum是什么

quorum是一个利用投票机制保证数据冗余以及强一致性的算法.

与多数派读写的区别在于, 多数派读时要求读取到占多数的相同数据才认定是最新成功提交的数据; 而quorum读取超过半数的容灾单元至少能读到一个最新数据, 数据新旧的区分没有规定, 可以采用版本号等方式.

2. quorum解决什么问题

分布式系统中需要冗余数据保证数据可靠性, 如果没有[[数据冗余]], 搭载数据的节点掉线就会导致数据无法访问.

3. quorum如何解决问题

quorum要求每次写入时超过半数容灾单元成功写入, 即可认为写入操作成功. 牺牲一定读操作性能, 每次读取超过半数的冗杂单元就能保证至少读到一个最新数据.

但是纯粹的多数派决议会引入新的问题, quorum制定了投票机制进行解决.

3.1. 投票机制

3.1.1. 投票机制是什么

投票机制是保证数据写入串行化以及针对同一数据不会同时发生读写操作而制定规则.

3.1.2. 投票机制解决什么问题

如果仅仅采用普通多数派决议方案, 当数据写入如果没有串行化, 也就是并发执行时, 会导致如下问题, 假设一个场景:

有A, B, C三台容灾单元, 此时客户端发来三个提案, 针对同一个变量x进行写入:

  1. 提案一: 写入x=1
  2. 提案二: 写入x=2
  3. 提案三: 写入x=3
    三个提案同时并发提交申请, 由于网络传输存在延迟, 这时可能发生如下先后顺序:
  4. 提案一x=1写入容灾单元B, 提案x=1还没有满足多数派写入, 等待其他节点回应
  5. 提案二x=2写入B, C, x=2覆盖了B上的x=1, 提案x=2满足多数派写入, 返回提案通过
  6. x=3写入C, A, x=3覆盖了C上的x=2, 提案x=3满足多数派写入, 返回提案通过
  7. 迟到的提案一x=1写入A, 其中x=1覆盖了A上的x=3, 提案x=1满足多数派写入, 返回提案通过
    三个提案都返回写入成功, 但是三台容灾单元上分别存储了x=1, x=2, x=3.
    进行多数派读写时发现读不出任何数据, 任何一个提案都不满足多数派读取.
    导致了三个提案都返回写入成功, 却无法正确读取其中任何一个提案提交的数据.

同一条数据同时发生读写, 会发生以下问题, 考虑一个场景:

有A, B, C三台容灾单元, 同时针对数据x进行读写请求, 原始数据如下:

  1. A, B上x=1, C上x=3
  2. 写入x=2, 将x=2写入B
  3. 同时发生读取请求, 读取到A, B, C上分别是x=1, x=2, x=3, 读取失败
    如果在读取与写入并行发生时就阻止其中一个操作, 那么另一个操作只需要等待重试;
    但是并发执行读写时, 读取操作要等待完全部容灾单元回应后才能发现数据不满足多数派读, 造成了额外的开销.

3.1.3. 投票机制如何解决问题

quorum规定了一个投票机制, 要求如下:

  • 每个容灾单元针对一条数据持有一票, 每次读写某一数据需要投票决策.
  • 针对一个数据的投票限制如下:
    1. 写入准许票数 > 容灾单元数/2
    2. 读取准许票数 > 容灾单元数 - 写入准许票数

这两个规定中, 第一点限制要求了每次写入操作需要获得超过半数的容灾单元投票准许, 保证了同一数据写入的串行化; 第二点限制保证了针对同一数据, 读取操作和写入操作不会同时发生.

paxos

1. paxos是什么

paxos是采用三段式提交(Three-Phase Commit)的多数派决议来保证数据一致性的算法.

基础的paxos协议存在活锁问题, 由后续multi-paxos通过串行化解决.

2. paxos解决什么问题

已知普通多数派协议存在问题[[quorum与paxos与raft#3.1.2. 投票机制解决什么问题]], 如果在仅仅普通多数派协议基础上添加提案编号也依旧存在问题, 考虑以下场景:

A, B, C三个容灾单元, 此时提出三个提案, 内容都为修改x数值:

  1. 提案一: 编号=1, 修改x=1
  2. 提案二: 编号=2, 修改x=2
  3. 提案三: 编号=3, 修改x=3
    考虑两段式提交, 第一阶段发起提案, 第二阶段接收到提案后立马回应:
  4. 提案一x=1写入A, B, 满足多数派决议, 提案一确认通过
  5. 提案二x=2写入B, C, 满足多数派决议, 提案二确认通过
  6. 提案三x=3写入C, 但发生丢包而未达到A, B, 不满足多数派, 提案三未通过
    对于已经通过的两个提案而言, 由于A, B, C三分别存储的x=1, 2, 3, 读取时会发现尽管有两个修改x的提案通过, 但是读取时无法读到多数派结果, 造成错误.

原因是带编号的多数派协议仅规定只要当前提案编号大于容灾单元曾经接受的最大编号, 就会直接将当前提案写入容灾单元, 可能造成最终不满足多数派决议的脏数据被直接写入节点. (丢失修改)

3. paxos如何解决问题

paxos定义了三种角色, proposer(提议者), acceptor(决议者), learner(学习者).

对于一个proposal(提案), 除了第一阶段(发起阶段), paxos还分为prepare(准备阶段)和accept(批准阶段).

在准备阶段中, 由proposal向所有acceptor发送一个提案编号, 然后等待acceptor回应.
acceptor收到提案编号, 进行比较, 如果该编号大于曾经收到的最大提案编号, 就记录下该编号, 并对这个提案做出承诺: 遇到不大于该提案编号的其他提案会直接拒绝; 否则拒绝这个提案.
如果proposal得到了多数acceptor接受的回应, 进入下一阶段; 否则提案失败.

在批准阶段中, proposal将带有编号的提案发送给所有acceptor, 等待回应.
acceptor接受到带有编号的提案后, 如果编号大于曾经收到的最大编号, 这时才接受提案, 并以leaner身份学习提案; 如果编号不大于曾经收到的最大编号, 就忽略该提案.
proposal收到多数派的acceptor接受回应后, 才认为提案通过.

这里的思路就是, 第一轮准备阶段, 提案本身并不会被执行, 甚至不需要发送, 而是先通过提案编号进行“占坑”, 当“占坑”通过后才进入批准阶段, 发送提案本身.

multi-paxos

1. multi-paxos是什么

multi-paxos是在paxos协议基础上, 添加了leader概念保证决议过程串行化.

multi-paxos作为强一致性协议已经足够完善, 但是没有要求数据追赶, 数据可靠性低于raft.

2. multi-paxos解决什么问题

对于基础的paxos协议, 存在活锁情况, 考虑以下场景:

A, B, C三台容灾单元, 提出两个提案, 内容都为修改x的值, 分别如下:

  1. 提案一, 修改x=1
  2. 提案二, 修改x=2
    姑且忽略具体编号, 假设编号按照以下出现顺序递增:
  3. 提案一, 准备阶段, 得到A, B, C中任意多数派回应, 正要进入批准阶段.
  4. 提案二, 准备阶段, 因为编号更大, 覆盖了A, B, C中多数派的承诺, 正要进入批准阶段.
  5. 提案一因为被截胡, 超时重试, 开启新一轮提案, 内容还是修改x=1, 但是编号更新后增大.
  6. 提案二而后又被更新编号的提案一截胡, 没能等到多数派回应, 同样发起重试.
  7. 如此往复, 提案一与提案二相互截胡, 导致没有任何提案通过多数派批准, 形成活锁.
    即便通过限制重试次数跳出活锁, 但是依旧会造成时间消耗.

3. multi-paxos如何解决问题

multi-paxos增加了leader概念, 通过选举得出一个任期属性的leader, 规定提案只能由leader提出, 其他容灾单元称为follower, 与leader一同进行多数派决议; follower通过定时轮询(心跳)确认leader存活, leader失联后进行重新选举, 每一轮选举的任期递增.

由于选取了一个全权负责提出提案的leader, 所以实现了串行化操作, 并且由于不存在并发, 所以也不需要准备阶段, 每次提案直接进入批准阶段等待多数派回应即可, 就不会发生活锁情况.

接下来介绍一下leader的选举过程:

概念的提出者并没有明确规定选举方式, 一般而言, 可以使用basic-paxos的三段式提交进行leader的选举(因为选举是低频事件, 添加重试次数限制后可以容忍三段式提交的活锁缺陷).

至于leader的任期, 是为了避免网络分区恢复后发生同时存在多个leader的情况. 通过每次提案中带有发起者的任期可以直接让恢复的旧leader接收到新leader提案消息后主动降为follower, 其他容灾单元接收到旧leader的提案后判断出其任期更旧也会进行忽略, 从而避免因为存在多个leader而退化为普通多数派决议.

raft

1. raft是什么

raft与multi-paxos都是能够保证数据一致性的多数派决议方案, 但是raft比multi-paxos更进一步要求了日志序列化, 并保证follower的日志与leader日志达成最终一致性. (数据追赶)

2. raft解决什么问题

对于multi-paxos而言, 每个提案仅需要多数派回应并学习, 也没有要求数据追赶, 这样可能导致如下情况:

A, B, C三台容灾单元, 其中存储的数据如下:

  1. A上存储x=1
  2. B与C上存储x=2
    如果B或C掉线, 就会导致数据x无法读取得到多数派结果, 数据可靠性低.

3. raft如何解决问题

由于leader唯一, 提案串行化执行, 所以leader的日志天然满足序列化.

此外raft规定了follower应该与leader的日志保持一致, 否则不能参与决议, 优先数据追赶.

同时raft对于选举过程增加了额外规定, 保证了选举得出的leader持有最多的日志:

对于选举时, 每个容灾单元仅持有一票, 候选者可以投自己一票, 并向其他容灾单元发出带有自己日志信息的投票请求:
其他容灾单元接收到投票请求时, 判断候选者持有的日志是否不少于于自己, 如果是则投票.
因为日志就是由多数派决议得出的, 所以多数容灾单元都持有最多的日志, 对于非最多日志持有者就不可能在选举中获得多数选票, 保证了选举得出的leader持有最多日志.

此外, raft还引入了随机选举延时(randomized election timeouts), 不同的容灾单元会在leader失联后等待一段随机时间后发起选举请求, 用以错开候选人, 避免选举过程出现平票.

总访问量次 | 访问人数位 | 阅读量