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