hzh0425 commented 3 years ago

前言

我已和@fengjiachun 老师讨论过该优化方案,并会在暑期开始研发若方案有任何问题,请帮忙指正,谢谢!

一背景

状态机复制(State Machine Replication)是一种众所周知的实现容错服务的方法，提供高可用性和强一致性。

然而,SMR的缺陷也很明显:其无法提供高吞吐量。这种限制源于通用状态机复制技术的基本假设，即所有副本按照相同的总顺序依次执行请求，以确保副本之间的一致性。因此,我们有必要去探究如何并行化SMR,以从根本上解决问题。同时,该并行化方法不能对原有的共识算法有太多的变更。

解决的方案主要有两个方面:

状态机分区:每个状态机负责一定范围内的数据,也即Multi-Raft的处理方式。
并行处理:降低传统SMR对顺序执行的限制,构建一套请求依赖检测程序,以便能并行化处理提交的任务。这也是本文想要探讨之处。

下文将按照循序渐进的方式探讨Parallel SMR:

首先会讨论传统的SMR架构
然后引申出并行化SMR架构。
接着对该并行化SMR架构进行利弊分析,进而提出高性能并行化SMR架构的优化之处。

文章的结尾给出了参考论文的链接

实际上,该改进不仅仅运用于raft中,只要是基于一致性状态机的共识算法,都可以运用下文提到的改进方案,以从根本上提高系统的吞吐量

二并行SMR设计架构

1.传统SMR架构

如图为传统SMR的处理方式,总共分为三层:

服务器代理:接收客户端请求
共识层: 通过共识算法确定请求的复制过程和执行顺序,以保证一致性和高可用性,典型的如raft和paxos
状态机:按顺序依次执行由共识层提交的请求

性能分析:

通过上述的状态机架构分析,我们可以发现,阻碍状态机高吞吐量的根本原因在于状态机是依次执行提交的请求的,这显然违背了多核CPU时代的初衷,无法更好的利用服务器的CPU资源

2.并行化SMR架构

2.1架构简述

如图所示,Parallel SMR,就是在共识层和状态机之间加入一个Parallelizer并行调度器,并且状态机不再是单线程执行,而是用一个线程池执行任务

Parallelizer的作用: 检测任务之间的依赖性,构建任务依赖图

如果两个任务没有依赖,则可以提交到线程池中并行执行
如果两个任务存在依赖,则需要顺序执行

为了更好的描述,上述的依赖关系和执行顺序,可以利用拓扑结构来表述,如图:

任务a,c,e没有依赖项(也即没有入边),因此可以并行执行
任务a,b,d是互相依赖的,因此只能顺序执行

那么,如何确定任务是否有依赖呢?论文[1]中提到了一种简单的检测方式:

例如一个kv存储系统,对于两次请求,如果这两次请求没有涉及相同的key,那就是无依赖的,反之就是有依赖(后文有更好的检测方式)

2.2接口定义

以下为Parallel SMR所定义的接口:

Parallelizer.insert():由共识层调用,请求在依赖关系图中插入一个结点。Parallelizer会对该结点与所有未执行完成的其他结点进行依赖关系的分析,若该结点有传入边,也即有其他依赖的结点,则该节点会进入阻塞等待的状态
Parallelizer.next_request():状态机调用，以返回一个就绪请求。如果一个请求在依赖关系图中没有任何传入边，那么它就准备好了。如果没有准备好的请求，这个调用会阻塞，直到它返回一个准备好的请求
Parallelizer.remove_request():在请求执行完成并向客户端发送应答后，由状态机调用。请求Parallelizer删除与此请求相对应的节点以及该节点的所有输出边。因此，一些被阻塞的请求可能会转换到就绪状态。

2.3运作流程

ok,现在我们来简单描述一下Parallel SMR的整体运作方式:

Client: submit a request
Consensus algorithm: replicate the Log and commit Log
Apply Log -> Parallelizer.insert() : 依赖检测,构建依赖拓扑图
Parallelizer.next_request() : 状态机线程池获取依赖图中准备就绪的任务,并执行任务,最后返回结果给客户端
Parallelizer.remove_request(): 状态机线程池请求删除执行完的任务

2.4一致性验证

显然,对于并行化状态机,我们最关心的问题是,这能否保证系统的线性一致性,以下为论文[1]中提到的验证逻辑的总结

一个请求,如果具有依赖,则所有副本都能利用Parallelizer计算出相同的依赖拓扑图,并以相同的顺序执行
一个请求,不具有依赖请求,也即其对系统状态的修改的时间点不会影响整个系统最终的状态。换句话说,因为独立请求会修改不相交的状态变量集，所以以任何顺序执行独立请求都会使系统处于相同的最终状态。
终上所述,对于一组给定的请求,Parallel SMR所达到的最终状态等同于以可线性化的顺序执行这些请求所达到的最终状态

3.高性能并行化SMR架构

3.1Parallel SMR的弊端

为了并行化独立命令的执行，Parallel SMR向每个副本添加了一个Parallelizer调度器。每个副本上的并行器按总顺序发送命令，检查命令依赖关系，并将它们分发到工作线程池中以供执行。直观地看，如果拓扑图中的命令存在较少的依赖关系,将十分有利于并发执行。然而，在依赖关系图中添加新命令的成本与图中独立于新命令的命令数量成正比。如图，一个新命令g将首先与命令d和f进行比较;如果g与d无关，它将与c和b比较，以此类推。如果g独立于图中的每个命令，则它将与所有顶点进行比较。在高吞吐量状态机复制的上下文中，根据依赖关系图检测每个新命令之间的冲突的开销会严重阻碍性能。因此,接下去,我将描述处理命令依赖关系的更有效的方法。

3.2优化思路

批处理命令:客户端通过客户端代理提交命令，客户端代理将来自不同客户端的命令分组。当代理接收到一批命令的所有响应时，它才可以提交一批新的命令。可以有任意数量的客户端代理，每个代理处理一组客户端。
缩略依赖关系图:调度程序接收批命令并构建一个精简的依赖关系图，其中顶点是命令批，边是由批中的命令引起的依赖关系。更准确地说，如果批命令B(i)早于批命令B(j)之前提交,并且B(j)中至少有一个命令依赖于B(i),则B(i)和B(j)存在一条变
高效的批处理冲突检测:用位图BitMap 扩展每批命令，位图包含批中读和写的变量的摘要。这个想法是，给定两个位图，b(Bi)和b(Bj)，我们希望能够通过比较它们的位图来确定是否有一个命令在批处理Bi中与某些命令在批处理bj中冲突。位图编码可以通过不同的方式实现。例如,在基于jraft实现的rheakv中，每个客户端的操作都包括相应的条目的键。我们通过散列函对键进行映射以创建位图;其中哈希值对应于位图中设置的位。检查两个批次是否包含有冲突的命令,只需将它们的位图按位进行比较即可。

3.3性能取舍

简化的依赖关系图的建立是一个性能的权衡。一方面，批处理减少了处理命令所需的开销(例如，更少的系统调用来交付命令，更少的边来存储图，更少的比较来确定依赖)，这提高了性能。另一方面，简化的依赖关系图减少了并发性。在图2(b)中，独立的命令a和c不能并发的执行,因为批B1中的b依赖于批B2中的d,所以a,b必须在c和d之前执行,这就减少了并发性.

3.4详细算法描述

4.需要做的工作

[ ] 依赖分析调度器,对要提交的分组进行依赖分析
[ ] DAG图调度算法
[ ] 多线程状态机

三参考资料

[1] High Throughput Byzantine Fault Tolerance
[2] Efficient and Deterministic Scheduling for Parallel State Machine Replication
[3] Rethinking State-Machine Replication for Parallelism
[4] Achieving high-throughput State Machine Replication in multi-core systems

killme2008 commented 3 years ago

这个似乎就是 polardb parallel raft 的思路，本质上都是在 apply 阶段将依赖无关的 log 做并行 apply ？

hzh0425 commented 3 years ago

这个似乎就是 polardb parallel raft 的思路，本质上都是在 apply 阶段将依赖无关的 log 做并行 apply ？

我看了一下parallel raft,本质上确实是一样的,将无依赖的log 并行执行但是parallel raft似乎是单个判断依赖的? 我觉得论文[2]里的观点会更好,利用batch+位图进行优化

killme2008 commented 3 years ago

@hzh0425 嗯，那是优化细节上的差异，思路上是一样的。期待你的贡献

sofastack / sofa-jraft

A high-throughput parallelized state machine #614

前言

一背景

二并行SMR设计架构

1.传统SMR架构