绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
共识算法 之 Multi-Paxos(一)
2019-12-24 10:44:10

1. 算法描述

当前multi-paxos没有权威的文献参考,目前大多采用的参考文献[1]的描述,这里首先给出其翻译版,然后分析其各个模块的细节,Lead election,CommitIndex Advance,Log Replication等。(背景图片来自[2])


1.1. 服务器状态

所有acceptor上面持久化的状态

每个 acceptor上面存放了一个复制日志,日志index (1 <= index <= lastLogIndex)。每个Log Entry 包含如下内容:

**所有proposer上面持久化的状态**

在Proposer里经常改变的


1.2. Prepare RPC (Phase 1)

Request:

Response:

接收者实现:

当接收到 prepare request 后,如果 request. proposalId >= minProposal, 则设置minProposal = request. proposalId。并且保证拒绝所有的 minProposal < request. proposalId 的accept请求。


1.3. Accpet RPC (Phase 2)

Request:

Response:

  • 接收者实现:

如果 proposalId >= minProposalId 就执行如下设置:

acceptedProposal[index] = request. proposalId; acceptedValue[index] = request.value; minProposal = request.proposalId;

对于每一个index < request.commitIndex 的log entry,如果其 acceptedProposal [index] == proposalId ,则可以设置其 acceptedProposal [index] = “无穷大”


1.4. Success (Phase 3)

Request:

Response:

  • 接收者实现:

     设置

     acceptedProposal [index] = “无穷大”

     acceptedValue[index] = request.value;

  • 发送者实现:

      if reply.commitIndex < commitIndex,

      则发送Success(index = reply.commitIndex + 1; value = acceptedValue[reply.commitIndex+1])


1.5. Proposer Algorithm

Write ( inputValue ) -> return bool


Notes

参考文献 [1] 原文中 02.(b) 描述上有错误,整理修正下,是 goto step 7.

这是 multi-paxos 的基本描述,相比 paxos,通过增加 leader 来消除正常情况下的绝大多数的 Prepare 阶段,直接进入 Accept 阶段,实际上熟悉 Raft 的读者可以看出,其 committed index 也是在 accept 阶段 request 来推进的,相比 Raft ,multi-paxos 增加了 success 其实就用于修复日志使用,后面将在(二)篇详细的分析。


参考文献

[1]. paxos-summay. https://ramcloud.stanford.edu/~ongaro/userstudy/paxossummary.pdf

[2]. Implementing Replicated Logs with Paxos. https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pdf...


分享好友

分享这个小栈给你的朋友们,一起进步吧。

分布式存储笔记
创建时间:2019-12-13 16:59:52
分布式与存储技术
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • 暗淡了乌云
    栈主

小栈成员

查看更多
  • bluetooth
  • 栈栈
  • ?
  • R-B
戳我,来吐槽~