开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 区块链 -> SDPaxos详解 -> 正文阅读

[区块链]SDPaxos详解

SDPaxos详解

背景
算法实现
可能的疑问
- 为什么SDPaoxs中C-instance和O-instance都不需要`Prepare`阶段

背景

目前强leader以及leaderless型的共识算法在地域分布式的应用下存在一定程度上的劣势。如，强leader的raft采用一个领导者来处理来自客户端的请求并提出提案，在这种模式下，leader的负载会远比其它副本大，非同地域的客户端也需要进行一次广域的连接才能请求到leader；而leaderless模式下的共识算法允许每个副本都可以提出提案，客户端通过就近选择副本消除了地域分布式的应用下物理长距离交互的问题，但由于每个副本都被允许在自己的paxos实例域中提交命令，因此需要在全局视角上对这些不同实例域中的instance进行排序以得到真正的状态机日志。目前的排序方式主要包括静态排序以及动态排序，如下图。
在这里插入图片描述
静态排序通过提前为每个副本分配全局的日志槽来实现不同副本实例域中instance间的排序，如图(a)，副本R0被分配了全局日志的1、4号槽，R1被分配了全局日志的2、5号槽，R2被分配了全局日志的3、6号槽。然而，这种方式会使整个程序以最慢副本（straggler）的速度运行。如图（a），虽然槽2、3、6都已经提交了command，但由于副本R0提议的进度慢，所以预先分配给R0的1号槽位始终没有被提交，这就导致后面的A、B、C命令无法apply，阻塞了整个apply的流程，虽然Mencius算法针对这个情况进行了优化，可以跳过straggler迟迟没有commit的槽，但这样做会产生额外的开销（询问是否能跳过这个槽）。

动态排序则是通过command间的依赖关系来进行全局实例域上的排序，这样做的好处是可以不必纠结不相互依赖的命令间的执行顺序，不同副本间即使不相互依赖的命令的执行顺序有一定的差异，也不会导致最终不同副本间状态的不一致。但由于每个副本都只能维护自己视角下的依赖关系，这难免会出现不同副本下依赖冲突的问题，如图（b），有个副本的依赖关系是A->C，另一个副本的依赖关系使B->C，此时则会需要额外的开销进行副本间依赖关系的补全（也就是epaxos中的slow path），经计算得到新的依赖关系(A, B)->C（依赖计算会导致副本cpu开销提高），之后才能决定全局实例域上的顺序（由于命令A、B无依赖关系，所以它们之间的执行顺序并不重要）。

Mencius（静态排序）和EPaxos（动态排序）需要额外的开销来处理来维护全局实例域的正确性的根本原因是，在提出一个新命令时，没有任何一个副本能够精确地知道其它副本的状态（它们已经提交了多少个命令或它们正在提交哪些命令），所以该类算法就只能通过额外的开销弥补该问题。

针对上述问题，SDPaxos通过一种半分离的模式旨在：

提供最小化的往返次数，以实现低广域延迟；
提供跨副本的负载平衡，以实现高吞吐量；
提供对掉队和竞争的强性能稳定性。

算法实现

提交

在SDPaxos中，主要包括三种角色：普通副本（Replica）、命令leader（Command leader）以及排序器（Sequencer）。任意Replica都可以接收来自客户端的写请求，接收客户端写请求的Replica成为该请求对应命令的Command leader，任一Replica都有可能在视图转换（View change）后成为Sequencer（通过选举）。

SDPaxos将一个command的提交分为两个部分：复制客户端请求的command给多副本以及将该command分配给有序的全局日志槽，这两个部分都是通过paxos过程实现的。
在这里插入图片描述

在每个副本中都维护着所有副本的C-instance的实例域，用于对某副本下的实例域中的实例序列达成共识。如上图中黄色框内的第一行（A、C那行），为副本R0的C-instance实例域，用于对R0的C-instance实例达成共识。当R0接收到客户端写请求成为command leader时，会广播携带n（副本编号）以及i（实例序号）的accept请求，其它副本收到该accept请求后会根据n和i找到该实例的所在域以及所在位置（该accept请求对应的实例应该是黄框中第一行的第三个，即命令C后面）。因此，副本中记录实例的数据结构应该是map[int]instance[]类型的，key为副本编号，value为key对应副本的C-instance域的实例序列

command在副本实例域中的instance被称为C-instance，而command在全局日志中的位置信息保存在的instance被称为O-instance。同时，C-instance的paxos过程都会带上C-的前缀，如C-instance的paxos过程中的accept请求被称为C-accept，O-instance的paxos过程同理。

首先我们来看一下最基础的SDPaxos在5副本下的算法流程，如下图：
在这里插入图片描述

R0接收到来自客户端的写请求后，成为该请求command的Command leader，并向包含Sequencer的majority的副本发送C-accept请求，此时，该command是R0处理的第i个command；
若接收到R0发来的C-accept请求的副本发现该请求的ballot大于自己所见过的最大的ballot，则会向R0发送C-ACK响应，以表示自己接受该提案；与此同时，接收到C-accept请求的Sequencer R2会开始O-instance的paxos过程，当i不小于R0在全局日志中被分配的槽的个数时，尝试将全局日志的第j个槽分配给R0，向包含R0的majority个副本发送O-accept请求，并且在向R0发送的O-accept请求中会同时携带O-ACK请求；
接收到O-accept请求的副本在发现该请求的ballot大于自己所见过的最大的ballot时，发送O-ACK响应给R0（注意是R0）；
当R0接收到majority个副本的C-ACK响应以及majority个副本的O-ACK响应后，向所有的副本发送C-commit请求以及O-commit请求，此时，该命令进入ready状态（当一个命令处于ready状态时，对应command leader便可安全地响应客户端）。

此时，全局日志上的第j个槽被分配给R0的实例域上的第i个instance。

在第2步中，Sequencer R2将O-accept和O-ACK一起发送给Command leader R0是因为，为了将命令和排序两部分的paxos过程进行重叠，R2替R0开始O-instance的paxos过程，所以后续副本的O-ACK是发送给R0的，R2将O-accept和O-ACK一起发送给R0单纯就是因为R2对R0进行排序的应答。在整个集群中，谁发送accept请求以及谁接收ACK响应实际上并不关键，只要保证集群中的quorum接受了该命令，该命令就可以被提交。

此外，如果Command leader没有将C-accept发送到Sequencer，则需要额外的一个C-request请求发送到Sequencer以开始O-instance的paxos过程。

在最基本的SDPaxos流程中，顺利的情况下完成一次日志的提交需要1.5次信息的交互。SDPaxos在异步无序的通讯模型中，可以在副本数为N=2F+1的集群中容忍F个副本的非拜占庭错误，这是比较常规的共识算法的一致性保证。为了保证副本达成共识的开销不会太大，通常设置可以忍受一到两个副本的错误，也就是3副本或5副本的集群，SDPaxos针对此进行了优化，实现了完整的SDPaxos。通常情况下，在5副本以下的分布式系统中或在command leader为sequencer的情况下，一个命令的提交只需要1次信息的交互；而在5副本以上的分布式系统中且command leader不为sequencer时，一个命令的提交则需要1.5次信息的交互。

完整的SDPaxos流程如下：

C-instance 阶段
1. 当副本Rn接收到客户端发来的携带命令α的请求：
  - Rn发送C-accept(n, i, α, balloti)请求给至少majority的副本；
  - 如果sequencer没有接收到C-accept请求，则需要额外发送一个C-request(n, i)请求给sequencer；
  - Rn实例域下C-instance的计数i+1；
2. 当任意副本R接收到C-accept(n, i, α, balloti)请求请求后：
  - 发送C-ACK(n, i, α, balloti)给副本Rn；
3. 当副本Rn接收到来自majority的副本的C-ACK：
  - 提交C_ni，然后广播C-commit(n, i, α, balloti);

C_ni指的是副本Rn实例域上的第i个C-instance

O-instance 阶段
1. 当sequencer Rm接收到来自Rn的C-accept(n, i, α, balloti)或者C-request(n, i)请求：
  - 如果i大于Rn在全局日志中被分配的槽的个数，则发送O-accept(j, n, ballotj)给包括Rn的majority个副本（j为尝试分配给Rn的全局日志槽的索引）；
  - O-instance实例域上的计数j+1；
2. 当任意副本R接收到O-accept(j, n, ballotj)请求：
  - 发送O-ACK(j, n, ballotj)给副本Rn；

全局日志指的是通过O-instance拼装起来的可以获取完整状态机的日志序列，副本中的C-instance通过O-instance得到自己在全局日志中的位置（O-instance记录了全局日志中的第j个槽被分配给了副本Rn实例域下的第i个C-instance），O-instance组成的日志被称为分配日志（assignment log）

在3副本或大于5副本的分布式系统中，命令达到ready状态的条件
1. 副本Rn收到majority个副本发来的O-ACK消息 -> 提交O_j 然后广播O-commit(j, n, ballotj)消息；
2. 副本Rn已经提交C_ni，且已经至少被分配了i个全局日志槽（至少有i个分配给Rn的O-instance已经被提交） -> 给客户端响应（此时命令进入ready状态）
在5副本的分布式系统中，命令达到ready状态的条件
1. 如果Rn是sequencer：
  - 当接收到majority个副本发送的O-ACK消息时，提交O_j，广播O-commit(j, n, ballotj)消息；
  - 如果Rn已经提交C_ni，且任意O_k（k<=j）都已经被majority个副本接受（O_j代表分配Rn的第i个O-instance） -> 可以给客户端响应（此时命令进入ready状态）
2. 如果Rn不是sequencer：
  - 当接收到sequencer发来的O-ACK消息时，提交O_j，广播O-commit(j, n, ballotj)消息；
  - 如果Rn已经提交C_ni，且任意O_k（k<=j）都已经被它自己以及sequencer接受（O_j代表分配Rn的第i个O-instance） -> 可以给客户端响应（此时命令进入ready状态）

当一个命令处于ready状态时，对应command leader便可安全地响应客户端

根据SDPaxos流程我们可知，C-instance的提交是严格遵循paxos过程来的，而在特殊情况下，O-instance的提交并不严格遵循paoxs过程。在command leader不为sequencer的时候，O-instance提交流程的开始会比C-instance提交流程的开始晚半个交互（0.5 round trip），因为sequencer在收到command leader发来的C-accept或C-request消息后才会开始O-instance的提交流程。

同时，SDPxaos针对目前真实环境中常见的5副本及以下（一般指的是3或5副本）的分布式系统的提交流程进行了优化，实现了正常情况下一次交互（one round trip）便可提交的优化。

SDPaxos的具体时延如下：

1 round trip的情况：
1. 当副本数小于等于5（通常为3或5副本）时
2. 无论多少副本，command leader为sequencer的情况下（此时C-instance和O-instance同时开始，都走paxos过程）
1.5 round trips的情况：
1. 副本数大于5且command leader不为sequencer的情况下

首先，在command leader为sequencer的情况下1次交互便可以完成对客户端的响应，如下图：
在这里插入图片描述

在图中，R0既是sequencer也是command leader，它在接收到客户端的写请求后可以同时开始C-instance与O-instance的流程，C-instance与O-instance都完全遵循paxos的流程，因此在正常情况下一次交互后便可响应给客户端。

其次，在副本数大于5且command leader不为sequencer的情况下需要1.5次交互才可以完成对客户端的响应，如下图：
在这里插入图片描述

该流程与最开始说的最基础的SDPaxos流程是一致的，图中R0为command leader，R3为sequencer，C-instance与O-instance都完全遵循paxos的流程，但O-instance的流程在接收到C-accept或C-request消息后才开始，也就比C-instance的流程晚0.5个交互，所以在一切正常的情况下需要1.5次交互才可以响应给客户端。

接下来是3副本但command leader不为sequencer时的流程，该流程也只需要1次交互便可以完成对客户端的响应，如下图：
在这里插入图片描述

图中R0为command leader，R2为sequencer，C-instance与O-instance也都完全遵循paxos的流程，而O-instance只需要0.5次交互便可完成的原因是，当R2发送给R0 O-ACK消息后，R0和R2就已经达成O-instance的quorum（在本算法中为majority，2/3已经超过了1/2），之后也就可以提交该O-instance了。

最后是5副本但command leader不为sequencer时的流程，优化后，该流程也只需要1次交互便可以完成对客户端的响应，如下图：
在这里插入图片描述

图中R0为command leader，R2为sequencer，在该流程中C-instance执行的是完整的paxos流程，而O-instance不是，sequencer收到C-accept或C-request后只发送给R0副本O-accept以及O-ACK消息，在命令提交时，只有2个副本接受了O-instance，并没有达到SDPaxos中的quorum（在该算法中为majority）。

综上，我们可以发现，在5副本但command leader不为sequencer的情况之外，所有情况下的C-instance和O-instance都是完全遵循paoxs的流程来的，也满足了majority定理，在F个副本宕掉的情况下（总副本数N=2F+1），至少有一个副本保存着instance正确的数据，所以可以通过一轮paxos的Prepare来获取或修复对应的instance，此时数据是安全且可恢复一致的。

而在5副本但command leader不为sequencer的情况下，只有C-instance是遵循paxos的，而O-instance并没有满足majority定理（只有sequencer和command leader接受了该O-instance），所以在满足F副本容错的特殊情况下，可能会丢失O-instance的数据（该O-instance对应的sequencer和command leader宕掉），对此，SDPaxos通过一种新的恢复方式解决了该问题。

容错恢复

当一个副本Rn被怀疑出现故障时（如网络物理隔离、SDPaxos进程被杀等），会选择一个副本初始化恢复进程进行故障恢复，尝试恢复Rn下C-instance实例域中的实例；若Rn为sequencer，则同时需要恢复O-instance实例域中的实例。

C-instance的恢复

由于在SDPaxos的任意情况下C-instance的复制都是完全按照paxos过程执行的，因此某个C-instance（副本Rn的第i个C-instance）的恢复可以直接通过另一个副本对该instance执行Prepare阶段实现。如果提出Prepare请求的副本发现自己记录的Rn实例域下的第i个C-instance是空的（not traced），则会在Prepare请求中携带no-op命令（no-op命令在日志执行获取状态机时并不会改变状态）。

O-instance的恢复

当sequencer故障时，需要重新选出一个新的sequencer，新的sequencer必须恢复这些O-instance来重建分配日志（assignment log）。SDPaxos使用一种基于视图的方法（view-based approach）来确保O-instance的正确恢复。每个副本都记录一个视图编号（view number），以标识它认为它在哪个视图中（view number是根据什么标准设定的？）。每条选举消息都携带sender的视图编号，只有当其视图编号不小于receiver的视图编号时，该条选举消息才有效。

SDPaxos 的 view number 类似 raft 中的 term，在 sequencer 选举中，view number 越大的 replica 更有资格选举成功；但 view number 只在 SDPaxos 的 sequencer 选举中有用

SDPaxos通过执行视图更改（view change）选举新的sequencer。视图更改开始时，副本会增加它的view number，发送V-request消息给其它副本，此时该副本成为候选人（candidate）。V-request在view number的基础上，还包括该副本所有O-instance的Prepare信息（O-prepare(j, bal)）。当一个副本接收到view number大于自身的V-request请求时，该副本将自己的view number更新为V-request的view number，并向V-request的发送方候选人发送vote消息，vote消息携带所有O-instance的O-promise信息用于帮助新的sequencer重建分配日志。候选人收到vote消息消息后，会遍历所有的O-instance，对于某个O-instance a，候选人会从所有为其投票的副本发来的vote消息中获取O实例a对应的O-promise信息，并从中选择ballot最大的消息更新实例a。在此期间，副本只处理视图更改的消息，会忽略客户端的请求。在获得majority的选票后，候选人将被选为新的sequencer，并通知其它副本。

为了保证线性化，新的sequencer不能新收到的命令插入到ready状态的槽之前的空槽中。在3副本或大于5副本的分布式系统中，上述的问题可以通过给分配日志（assignment log）的“孔”(hole)中填充no-cl命令（no-cl = 无command leader，即没有将这个槽分配给任意副本）来解决，当执行全局日志的过程中在分配日志中遇到了no-cl，副本会通过执行no-op命令来保持状态的不变。在O-instance没有被commit的情况下，我们可以安全地propose no-cl命令。

原文中第一句话是“To ensure linearizability, the new sequencer cannot insert a newly-received command to a slot preceding a ready one”。我的理解是在view change后sequencer不能将已经分配给ready状态的C-instance的空的O-instance之前的O-instance新分配给别的副本，不然可能会导致view change前后状态机的不一致，这也侧面说明了分配日志（assignment log）是有孔的

在5副本的情况下，分配日志上的孔可能已经分配给了副本Rm且已提交，Rm是除了旧sequencer和给新sequencer投票的副本之外的副本（也就是故障的副本中除旧sequencer之外的另一个）。
在这里插入图片描述

之前说过，在5副本的分布式系统中command leader不是sequencer的情况下，为了将latency保持在1 round trip，O-instance的复制并没有按照paxos标准来，只要sequencer和command leader接受了该提议，instance就可以提交。然而在极端情况下，若sequencer和某命令的command leader同时出现故障，该命令就无法通过Prepare过程恢复，如上图第二列R1。但我们可以猜测分配日志的第二个槽很有可能已经被分配给了R1，因为在5副本的情况下，一个O-instance可以被提交意味着至少有两个副本接受了它（sequencer和command leader），在两个副本出现故障但找不到某槽的分配情况时，该槽很有可能被分配给了故障的两个副本的其中之一（R0或R1），但我们知道R0是旧sequencer，我们假设第二个槽分配给了R0，那就说明R0既是sequencer也是command leader，但在这种情况下，O-instance和C-instance是同时开始的，也是遵循paxos过程的，所以应该至少有三个副本接受了这个O-instance（如第一列，第一个槽分配给R0的情况下，有三个副本接受了该提议），与第二个槽的分配请款不可见冲突，所以第二个槽只可能被分配给了R1。

若分配日志允许有孔，则还需考虑第二个槽没有提交的情况。此外，上图的情况比较极端，只有在command leader自己commit，但O-commit广播出现问题才有可能出现，在实际的实现中约束更多，这种情况更难发生，但看起来比较直观

接上文，在5副本的情况下，分配日志上的孔可能已经分配给了副本Rm且已提交，Rm是除了旧sequencer和给新sequencer投票的副本之外的副本。所以我们需要尝试将这些孔分配给Rm，直到Rm被分配了足够装下ready状态命令的槽。我们让每个副本在其vote信息中记录该副本接受的其他副本实例域上的实例的数量N_i，新的sequencer对所有副本发来的vote信息中的N_m的取最大值作为C[m]。C[m]指的是Rm的C实例域下最有可能的ready状态命令的数量。因此，新的sequencer应该在O-instance的孔中提议Rm的ID，直到存在C[m]个分配给Rm的O-instance。但是如果O_j成功提交但其对应的C_mi没有成功提交，则应该将O_j设为no-cl，因此Rm应该被允许accept拥有更高ballot的新sequencer提议的no-cl。

在5副本的分布式系统中，新的sequencer应该确保所有的O-instance都已被视图更改中的majority副本所接受，然后新的sequencer就会将其O-instance的下标计数器设置为第一个空的O-instance处。

以下是O-instance的恢复流程：

输入：C[m]是Rm最有可能被别的副本accept的ready状态命令的数量；O[m]是分配给Rm的全局日志槽的数量

如果是5副本的分布式系统：
- 将Rm的ID提议到第一个空的O-instance（孔），然后O[m] <- O[m]+1
- 直到O[m]>=C[m] 且分配给Rm的第C[m]个槽之前不存在孔
对分配日志上的孔提议no-cl命令

读优化

由于SDPaxos的sequencer具有全局视角，所以读操作并不用作为paxos的实例来执行。

对对象O的读取必须知道在收到读请求之前所有ready状态的对对象O的写命令。我们将某对象的最近更新称为W，分配给W的全局日志槽的索引为i_E。i_E指的是读安全（Safe-to-read）的最早时机，但精准地追踪i_E相对困难，所以我们可以选择一个更往后的时机。我们称i_G为最后一个被分配的全局槽的索引，i_A为最后一个被配给对象O写操作命令的全局槽的索引。i_G等于O-instance的下标计数器-1，总有i_E <= i_A <= i_G，如下图：
在这里插入图片描述

副本会转发R-request(O)请求给sequencer来读取O。sequencer在i_A和i_G之间返回是安全的，但i_A更好，因为可以减少等待无关命令执行的时间。为了实现这种优化，sequencer可以在内存中维护一个叫做历史表（history table）的map用于记录每个对象对应的i_A。同时，副本在C-request请求中也应加上对应的对象。每当sequencer将一个slot分配给对象O的写操作时，将修改历史表中对象O对应的i_A为该槽。如果一个对象在历史表中没有记录，可以直接使用i_G。如果对象数量很大的话，可以在历史表中只记录高热度对象的信息，其它对象直接使用i_G。