🧭
区块链技术指南
  • 前言
  • 修订记录
  • 如何贡献
  • 区块链的诞生
    • 记账科技的千年演化
    • 分布式记账与区块链
    • 集大成者的比特币
    • 区块链的商业价值
    • 本章小结
  • 核心技术概览
    • 定义与原理
    • 技术的演化与分类
    • 关键问题和挑战
    • 趋势与展望
    • 认识上的误区
    • 本章小结
  • 典型应用场景
    • 应用场景概览
    • 金融服务
    • 征信管理
    • 权属管理与溯源
    • 资源共享
    • 物流与供应链
    • 物联网
    • 数字艺术品和 NFT
    • 其它场景
    • 本章小结
  • 分布式系统核心技术
    • 一致性问题
    • 共识算法
    • FLP 不可能原理
    • CAP 原理
    • ACID 原则与多阶段提交
    • Paxos 算法与 Raft 算法
    • 拜占庭问题与算法
    • 可靠性指标
    • 本章小结
  • 密码学与安全技术
    • 密码学简史
    • Hash 算法与数字摘要
    • 加解密算法
    • 消息认证码与数字签名
    • 数字证书
    • PKI 体系
    • Merkle 树结构
    • Bloom Filter 结构
    • 同态加密
    • 其它技术
    • 本章小结
  • 比特币 —— 初露锋芒的区块链
    • 比特币项目简介
    • 比特币诞生背景
    • 工作原理
    • 挖矿过程
    • 共识机制
    • 闪电网络
    • 侧链
    • 热门问题
    • 相关工具
    • 本章小结
  • 以太坊 —— 挣脱加密货币的枷锁
    • 以太坊项目简介
    • 核心概念
    • 主要设计
    • 相关工具
    • 安装客户端
    • 使用智能合约
    • 智能合约案例:投票
    • 本章小结
  • 超级账本 —— 面向企业的分布式账本
    • 超级账本项目简介
    • 社区组织结构
    • 顶级项目介绍
    • 开发必备工具
    • 贡献代码
    • 本章小结
  • Fabric 安装与部署
    • 简介
    • 本地编译组件
    • 容器方式获取
    • 本地方式启动 Fabric 网络
    • 容器方式启动 Fabric 网络
    • 本章小结
  • 管理 Fabric 网络
    • 简介
    • 使用通道
    • 管理节点
    • 管理链上代码
    • 监听网络事件
    • 自动发现网络信息
    • 使用运维服务
    • 如何升级网络版本
    • 使用 SDK
    • 注意事项与最佳实践
    • 本章小结
  • 智能合约开发
    • 简介
    • 链码概念与结构
    • 示例一:信息公证
    • 示例二:交易资产
    • 示例三:数字货币发行与管理
    • 示例四:学历认证
    • 示例五:社区能源共享
    • 小结
  • Fabric 架构与设计
    • 简介
    • 架构设计
    • 消息协议
    • 小结
  • 区块链服务平台设计
    • 简介
    • IBM Bluemix 云区块链服务
    • 微软 Azure 云区块链服务
    • 使用超级账本 Cello 搭建区块链服务
    • 本章小结
  • 性能与评测
    • 简介
    • Hyperledger Fabric v0.6
    • 小结
  • 附录
    • 术语
    • 常见问题
    • Go 语言开发相关
      • 安装与配置 Golang 环境
      • 编辑器与 IDE
      • 高效开发工具
      • 依赖管理
    • ProtoBuf 与 gRPC
    • 参考资源链接
由 GitBook 提供支持
在本页
  • Paxos 算法
  • 基本原理
  • 单个提案者+多接受者
  • 多个提案者+单个接受者
  • 多个提案者+多个接受者
  • 两阶段的提交
  • Raft 算法

这有帮助吗?

在GitHub上编辑
  1. 分布式系统核心技术

Paxos 算法与 Raft 算法

上一页ACID 原则与多阶段提交下一页拜占庭问题与算法

最后更新于3年前

这有帮助吗?

Paxos 问题是指分布式的系统中存在故障(crash fault),但不存在恶意(corrupt)节点的场景(即可能消息丢失或重复,但无错误消息)下如何达成共识。这也是分布式共识领域最为常见的问题。因为最早是 Leslie Lamport 用 Paxos 岛的故事对该算法进行描述的,因而得名。解决 Paxos 问题的算法主要有 Paxos 系列算法和 Raft 算法。

Paxos 算法

1988 年,Brian M. Oki 和 Barbara H. Liskov 在论文《Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems》中首次提出了解决 Paxos 问题的算法。

1990 年由 Leslie Lamport 在论文《The Part-time Parliament》中提出的 共识算法,在工程角度实现了一种最大化保障分布式系统一致性(存在极小的概率无法实现一致)的机制。Paxos 算法本质上与前者相同,被广泛应用在 Chubby、ZooKeeper 这样的分布式系统中。Leslie Lamport 作为分布式系统领域的早期研究者,因为相关杰出贡献获得了 2013 年度图灵奖。

论文中为了描述问题编造了一个虚构故事:在古代爱琴海的 Paxos 岛,议会如何通过表决来达成共识。议员们通过信使传递消息来对议案进行表决。但议员可能离开,信使可能走丢,甚至重复传递消息。

Paxos 是首个得到证明并被广泛应用的共识算法,其原理类似于 算法,进行了泛化和扩展,通过消息传递来逐步消除系统中的不确定状态。

作为后来很多共识算法(如 Raft、ZAB 等)的基础,Paxos 算法基本思想并不复杂,但最初论文中描述比较难懂,甚至连发表也几经波折。2001 年,Leslie Lamport 还专门发表论文《Paxos Made Simple》进行重新解释。

注:Leslie Lamport 对密码学也有研究,1979 年提出的多 Hash 签名机制,具备抗量子计算攻击特性。

基本原理

算法中存在三种逻辑角色的节点,在实现中同一节点可以担任多个角色:

  • 提案者(Proposer):提出一个提案,等待大家批准(Chosen)为决议(Value)。系统中提案都拥有一个自增的唯一提案号。往往由客户端担任该角色;

  • 接受者(Acceptor):负责对提案进行投票,接受(Accept)提案。往往由服务端担任该角色;

  • 学习者(Learner):获取批准结果,并帮忙传播,不参与投票过程。可为客户端或服务端。

算法需要满足安全性(Safety) 和存活性(Liveness)两方面的约束要求。实际上这两个基础属性也是大部分分布式算法都该考虑的:

  • Safety:保证决议(Value)结果是对的,无歧义的,不会出现错误情况。 * 只有是被提案者提出的提案才可能被最终批准;

    • 在一次执行中,只批准(chosen)一个最终决议。被多数接受(accept)的结果成为决议。

  • Liveness:保证决议过程能在有限时间内完成。

    • 决议总会产生,并且学习者能获得被批准的决议。

基本思路类似两阶段提交:多个提案者先要争取到提案的权利(得到大多数接受者的支持);成功的提案者发送提案给所有人进行确认,得到大部分人确认的提案成为批准的决议。

Paxos 并不保证系统总处在一致的状态。但由于每次达成共识至少有超过一半的节点参与,这样最终整个系统都会获知共识结果。一个潜在的问题是提案者在提案过程中出现故障,这可以通过超时机制来缓解。极为凑巧的情况下,每次新一轮提案的提案者都恰好故障,又或者两个提案者恰好依次提出更新的提案,则导致活锁,系统会永远无法达成共识(实际发生概率很小)。

Paxos 能保证在超过一半的节点正常工作时,系统总能以较大概率达成共识。读者可以试着自己设计一套非拜占庭容错下基于消息传递的异步共识方案,会发现在满足各种约束情况下,算法过程总会十分类似 Paxos 的过程。这也是为何 Google Chubby 的作者 Mike Burrows 说:“这个世界上只有一种一致性算法,那就是 Paxos(There is only one consensus protocol, and that's Paxos)”。

下面,由简单情况逐步推广到一般情况来探讨算法过程。

单个提案者+多接受者

如果系统中限定只允许某个特定节点是提案者,那么共识结果很容易能达成(只有一个方案,要么达成,要么失败)。提案者只要收到了来自多数接受者的投票,即可认为通过,因为系统中不存在其他的提案。

但此时一旦提案者故障,则整个系统无法工作。

多个提案者+单个接受者

限定某个特定节点作为接受者。这种情况下,共识也很容易达成,接受者收到多个提案,选第一个提案作为决议,发送给其它提案者即可。

缺陷也是容易发生单点故障,包括接受者故障或首个提案者节点故障。

以上两种情形其实类似主从模式,虽然不那么可靠,但因为原理简单而被广泛采用。

当提案者和接受者都推广到多个的情形,会出现一些挑战。

多个提案者+多个接受者

既然限定单提案者或单接受者都会出现故障,那么就得允许出现多个提案者和多个接受者。问题一下子变得复杂了。

一种情况是同一时间片段(如一个提案周期)内只有一个提案者,这时可以退化到单提案者的情形。需要设计一种机制来保障提案者的正确产生,例如按照时间、序列、或者大家猜拳(出一个参数来比较)之类。考虑到分布式系统要处理的工作量很大,这个过程要尽量高效,满足这一条件的机制非常难设计。

另一种情况是允许同一时间片段内可以出现多个提案者。那同一个节点可能收到多份提案,怎么对它们进行区分呢?如果一个节点只接受它收到的首个提案,将导致不同节点可能接受不同的提案。很自然地,提案需要带上不同的序号。节点根据序号来判断接受哪个提案。通常采用递增序号,选择接受序号最大的提案。这是因为旧提案可能基于过期数据,导致失败概率更大。

如何为提案分配序号呢?一种可能方案是每个节点的提案数字区间彼此隔离开,互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。

同时允许多个提案,意味着很可能单个提案人无法集齐足够多的投票;另一方面,提案者即便收到了多数接受者的投票,也不敢说就一定通过。因为在此过程中投票者无法获知其它投票人的结果,也无法确认提案人是否收到了自己的投票。因此,需要实现两个阶段的提交过程。

两阶段的提交

提案者发出提案申请之后,会收到来自接受者的反馈。一种结果是提案被大多数接受者接受了,一种结果是没被接受。没被接受的话,可以过会再重试。即便收到来自大多数接受者的答复,也不能认为就最终确认了。因为这些接受者自己并不知道自己刚答复的提案可以构成大多数的一致意见。

很自然的,需要引入新的一个阶段,即提案者在第一阶段拿到所有的反馈后,需要再次判断这个提案是否得到大多数的支持,如果支持则需要对其进行最终确认。

Paxos 里面对这两个阶段分别命名为准备(Prepare)和提交(Commit)。准备阶段通过锁来解决对哪个提案内容进行确认的问题,提交阶段解决大多数确认最终值的问题。

准备阶段:

  • 提案者向多个接受者发送计划提交的提案编号 n,试探是否可以锁定多数接受者的支持;

  • 接受者 i 收到提案编号 n,检查回复过的提案的最大编号 M_i。如果 n > M_i,则向提案者返回准备接受(accept)提交的最大编号的提案 P_i(如果还未接受过任何提案,则为空),并不再接受小于 n 的提案,同时更新 M_i = n。这一步是让接受者筛选出它收到的最大编号的提案,接下来只接受其后续提交。

提交阶段:

  • 某个提案者如果收到大多数接受者的回复(表示大部分人收到了 n),则准备发出带有 n 的提交消息。如果收到的回复中带有提案 P_i(说明自己看到的信息过期),则替换选编号最大的 P_i 的值为提案值;否则指定一个新提案值。如果没收到大多数回复,则再次发出请求;

  • 接受者 i 收到序号为 n 的提交消息,如果发现 n >= P_i 的序号,则接受提案,并更新 P_i 序号为 n。

一旦多数接受者接受了共同的提案值,则形成决议,成为最终确认。之后可以开始新一轮的提交确认。

需要注意,Paxos 并不一定能保证每一轮都能提交提案。

Raft 算法

Paxos 算法虽然给出了共识设计,但并没有讨论太多实现细节,也并不重视工程上的优化,因此后来在学术界和工程界出现了一些改进工作,包括 Fast Paxos、Multi-Paxos,Zookeeper Atomic Broadcast(ZAB)和 Raft 等。这些算法重点在于改进执行效率和可实现性。

算法包括三种角色:领导者(Leader)、候选者(Candidate) 和跟随者(Follower),每个任期内选举一个全局的领导者。领导者角色十分关键,决定日志(log)的提交。每个日志都会路由到领导者,并且只能由领导者向跟随者单向复制。

典型的过程包括两个主要阶段:

  • 领导者选举:开始所有节点都是跟随者,在随机超时发生后未收到来自领导者或候选者消息,则转变角色为候选者(中间状态),提出选举请求。最近选举阶段(Term)中得票超过一半者被选为领导者;如果未选出,随机超时后进入新的阶段重试。领导者负责从客户端接收请求,并分发到其他节点;

  • 同步日志:领导者会决定系统中最新的日志记录,并强制所有的跟随者来刷新到这个记录,数据的同步是单向的,确保所有节点看到的视图一致。

此外,领导者会定期向所有跟随者发送心跳消息,跟随者如果发现心跳消息超时未收到,则可以认为领导者已经下线,尝试发起新的选举过程。

其中, 算法由斯坦福大学的 Diego Ongaro 和 John Ousterhout 于 2014 年在论文《In Search of an Understandable Consensus Algorithm》中提出,基于 Multi-Paxos 算法进行重新简化设计和实现,提高了工程实践性。Raft 算法的主要设计思想与 ZAB 类似,通过先选出领导节点来简化流程和提高效率。实现上解耦了领导者选举、日志复制和安全方面的需求,并通过约束减少了不确定性的状态空间。

Paxos
两阶段提交
Raft