基于向量时钟的对等分布式系统状态一致性算法

摘要

分布式一致性算法是构建高可用系统的基础，它可以使一组机器协同工作犹如一个强化的组合，并且能够容忍其中的一些机器失效。但是，现有的分布式一致性算法都不能同时具备高吞吐、低延迟和高可用性。本文提出一个新的用于状态机复制的分布式一致性算法Veca，尽可能同时满足这些需求。 拜占庭容错算法是构建高可靠系统的基础，区块链应用的流行更使得拜占庭容错算法焕发生机。现有的拜占庭容错算法会引入很大的开销，不能同时具备高吞吐、低延迟和高可用性。本文基于分布式一致性算法Veca提出一个新的用于拜占庭状态机复制的拜占庭容错算法BVeca，尽可能同时满足这些需求。 论文主要的工作和贡献包括： (1)提出一个新的用于状态机复制的分布式一致性算法Veca。Veca是一个无领导者的分布式一致性算法，所有复本都可以在任意时刻并发地提议操作命令。正常情况下每条操作命令都可以在与大多数复本只进行一次网络消息来回通信后被提交。Veca将共识协议与操作命令的排序和执行分开，所有复本可以在任意时刻并发地提交操作命令，无需确定操作命令之间的顺序，但使用向量时钟跟踪记录它们之间的依赖关系。随后的回放阶段将已提交的操作命令按照依赖关系排序并按顺序执行它们。操作命令先乱序提交，然后在所有复本上按相同的顺序执行。系统可在大多数复本可用时提供连续不断的服务； (2)基于分布式一致性算法Veca提出一个新的用于拜占庭状态机复制的拜占庭容错算法BVeca。BVeca是一个无主的拜占庭容错算法，所有复本都可以在任意时刻并发地提议操作命令。正常情况下每条操作命令都可以由一个两阶段的共识协议提交。BVeca将共识协议与操作命令的排序和执行分开，所有复本可以在任意时刻并发地提交操作命令，无需确定操作命令之间的顺序，但使用向量时钟跟踪记录它们之间的依赖关系。随后的回放阶段将已提交的操作命令按照依赖关系排序并按顺序执行它们。操作命令先乱序提交，然后在所有正确的复本上按相同的顺序执行。系统可在少于三分之一的复本出错时提供连续不断的服务； (3)将BVeca算法用于区块链共识，实现一个区块链原型系统，验证本文提出的算法的安全性和有效性。在实验室局域网和亚马逊EC2广域网环境下分别使用多复本状态机模型评估了Veca和BVeca算法的延迟、吞吐量、延迟与吞吐量关系以及可用性。使用Jepsen框架测试验证了Veca和BVeca的容错能力。实验结果表明Veca和BVeca具有很好的性能和容错能力。

目录

第一个书签之前

摘要

ABSTRACT

论文图表索引

第一章 绪论

1

1.1 研究背景

1.1.1 分布式系统模型

1.1.2 分布式一致性

1.1.3 多复本状态机

1.1.4 拜占庭容错

1.1.5 区块链共识

1.2 本文研究内容和工作

1.3 本文组织结构

第二章 研究现状

2.1.1 Paxos

2.1.2 Multi-Paxos

2.1.3 Viewstamped Replication

2.1.4 Zab

2.1.5 Raft

2.1.6 Mencius

2.1.7 EPaxos

2.2 拜占庭容错算法

2.2.1 PBFT

2.2.2 Zyzzyva

2.2.3 hBFT

2.3 区块链共识算法

2.3.1 PoW

2.3.2 PoS

2.3.3 DPoS

2.3.4 PBFT

2.4 研究现状总结

2.4.1 分布式一致性算法总结

2.4.2 拜占庭容错算法总结

2.4.3 区块链共识算法总结

2.5 本章小结

第三章 基于向量时钟的分布式一致性算法

3.1 算法简介

3.2 向量时钟

3.3 算法直观理解

3.4 算法设计

3.4.1 设计假设

3.4.2 设计目标

3.4.3 设计保证

3.4.4 算法概览

3.4.5 操作命令提交协议

3.4.6 操作命令回放算法

3.4.7 失效恢复协议

3.5 算法扩展

3.5.1 集群成员重新配置

3.5.2 空间回收

3.5.3 只读租约

3.5.4 故障下的线性一致性

3.5.5 操作命令回放时的活锁

3.6 性能优化

3.6.3 并行回放

3.7 算法复杂度

3.8 算法正确性

3.9 本章小结

4

4.1 算法简介

4.2 系统模型

4.3 算法设计

4.3.1 设计目标

4.3.2 设计保证

4.3.3 算法概览

4.3.4 客户端行为

4.3.5 操作命令共识协议

4.3.6 操作命令回放算法

4.3.7 失效恢复协议

4.3.8 检查点协议

4.4 性能优化

4.4.1 摘要响应

4.4.2 纠删码

4.4.3 检查点分区

4.5 算法复杂度

4.6 算法正确性

4.6.1 安全性

4.6.2 活性

4.7 区块链原型系统实现

4.7.1 远程过程调用框架

4.7.2 区块链状态机

4.7.3 区块链共识

4.8 本章小结

第五章 实验评估

5.1 实验环境

5.2 Veca评估

5.2.1 延迟

5.2.2 吞吐量

5.2.3 延迟与吞吐量

5.2.4 可用性

5.2.5 容错能力

5.3 BVeca评估

5.3.2 吞吐量

5.3.3 延迟与吞吐量

5.3.4 可用性

5.3.5 容错能力

5.4 本章小结

第六章 总结及未来工作

6.1 总结

6.2 未来工作

致谢

参考文献