一种面向云存储的复制状态机模块化框架设计方法

摘要

本发明在分析用于当前云存储环境下多副本容错的复制状态机所存在的可扩展问题的基础上，通过对构成复制状态机的一致性协议及相关实现机制进行功能划分，提出了复制状态机的模块化框架。复制状态机模块化框架抽象了一系列同类解决方案的公共模块，即一致性协议排序、协议执行与故障检测、通信机制等。框架设计的关键在于功能划分与模块化，其灵活性体现在对实现这些功能模块的服务器集合的灵活配置。利用本发明的框架及其规范，复制状态机设计者们可以针对具体的资源约束/优化目标灵活地实例化新的复制状态机及其一致性协议，以满足特定的性能优化与负载均衡的要求，并应用于特定的云存储环境。

说明书

技术领域

本发明属于云存储副本复制容错技术领域，具体涉及一种基于一致性协议的复制状态机模块化框架的设计方法。

背景技术

状态机复制是一种众所周知的技术，它通过将确定性的服务复制到副本上并且在不牺牲强一致性的情况下提供容错。一个复制状态机通常包含一组副本，它们的执行随着一系列预定顺序的一致性协议实例进行，这里每个实例的输出是所有副本就某个确定性请求达成的一致决议。通过以相同的顺序执行被输出的确定性请求，所有非故障副本将在相同的状态序列中进行转换，从而保证了各个副本在状态上的一致。以leader为中心的一致性协议是复制状态机中应用极为广泛的协议。

为了提供一致的性能和高可用性，复制状态机被广泛应用于云端大量的存储服务(如现有的Megastore、PNUTS等)中。然而，随着需求的多样化发展和技术进步的加快，云环境正变得越来越复杂。为了适应复杂云环境下各种存储应用的需求，传统的复制状态机亟需得以改进。

当前，许多解决方案针对具体的优化目标提出了对复制状态机的扩展；而需要强一致性保证的云服务则从资源约束的角度出发，通过优化一致性协议来达到改善复制状态机的目的。虽然针对资源约束/优化目标所设计的复制状态机其表现形式不同，但它们都涉及对一致性协议，尤其是以leader为中心的一致性协议的调整。许多复制状态机通过在多个进程间分摊leader的负载或轮换leader角色而改善复制状态机的执行效率和性能。

虽然在复制状态机的设计上存在不同的方案。但是针对资源约束/优化目标提出一种灵活、普遍适用的复制状态机设计方法对于研究复制状态机优化设计和扩展云端存储服务而言意义重大。它基于如下两方面的考虑：一方面，虽然可以针对具体的资源约束/优化目标为不同的应用设计特定于应用的复制状态机及其相应的一致性协议，但是这种设计方式很不灵活，它要求对每种场景重新思考设计，增加了复制状态机设计者们的工作负担。另一方面，尽管针对具体资源约束/优化目标的解决方案存在一定的差异，但它们通常拥有类似的设计思路。复制状态机中一致性协议执行的负载划分与结果合并是很多解决方案中共有的功能和阶段。对这些共性的抽象与整合是有可能的，并且其规范化对此后具体环境下的设计提供了指导。

本发明从模块划分的角度出发，在一致性协议的协商与执行业已划分的基础上，关注“将协商进一步划分为局部排序与全局合并”的优化方式，构造直观的复制状态机模块化框架。在此基础上，本发明为框架中局部排序和全局合并模块的设计实现提供了规范化的映射定义，并为复制状态机及其一致性协议的执行制定了统一的框架协议。

发明内容

本发明的目的是为针对各种具体资源约束/优化目标的复制状态机及其一致性协议的设计和实现提供一种直观的、灵活的、规范化的设计方法。复制状态机的设计者们通过利用本发明所提供的模块化框架及其设计流程，并结合其所附加的模块实现规范与执行协议，就可以方便地得到适应于特定要求的复制状态机及其一致性协议。

本发明通过如下技术方案实现。

一种面向云存储的复制状态机模块化框架设计方法，首先明确复制状态机所适用的模型，所述模型包括通信模型、故障模型、执行模型；在确定模型的基础上划分复制状态机的一级模块，所述模块包括通信机制模块、一致性协议、模块执行模块；进一步在一致性协议模块中针对所定义的三个模型选择适当的一致性协议；然后根据设计需求，将一致性协议模块划分为三个子模块，所述子模块包括排序子模块、合并子模块、故障检测子模块；根据所采用的一致性协议，对复制状态机所处理的状态全集即被访问的数据进行划分；接着，对应于划分的状态，定义排序子模块、合并子模块的映射关系；在上述子模块进行物理配置后，启动子模块的执行；将其生成的结果作为执行模块的输入，最终形成的结果即为复制状态机的输出。

进一步地，定义了作为复制状态机实例运行基础的模型，包括通信模型、故障模型、执行模型；

所述的通信模型指出：根据该设计方法实例化得到的复制状态机实例所适用的通信环境为异步分布式环境，运行与不同服务器上的进程在双向信道上通过消息交换进行通信；消息交互是异步且不可靠的；所交换的消息可能被重复、丢失，但不会被损坏；消息传输延迟、进程相对速率没有限制；

所述的故障模型指出：该设计方法针对的是非拜占庭的场景，即所有服务器都可能发生崩溃并随后恢复其状态，而即使它们发生故障之后也不会表现出拜占庭行为，即无法预测的行为；

所述的执行模型定义了根据该设计方法实例化得到的复制状态机实例所适用的规模和网络范围，既可以运行于广域/局域环境下，也可以运行于跨网络的异构环境；其执行模型包含了服务器的全集和进程的全集；服务器全集提供了运行具体复制状态机的硬件基础设施，进程全集包含了执行复制状态机中一致性协议的参与实体。

进一步地，所述方法划分了模块化框架的多个抽象的功能模块，包括通信机制模块、一致性协议模块、执行模块；

所述通信机制模块封装了复制状态机底层的通信机制；针对云端可能存在的复杂的网络通信环境，复制状态机实例及其运行的一致性协议可以借助于具体的通信机制实现状态机和协议的优化；

所述的一致性协议模块是复制状态机的核心，其具体实现方式对复制状态机实例的性能和负载均衡情况产生显著影响；

所述的执行模块是复制状态机的最终处理模块，该模块处理的对象是合并模块的输出结果；通过使复制状态机各副本按序执行合并模块输出的请求或命令，执行模块保证复制状态机中各副本最终在一致的状态序列上进行转换，从而保证了副本的一致性。

进一步地，所述方法将复制状态机的各个副本上针对其处理对象即请求或命令运行的一致性协议模块作为框架的核心，为模块选择相应的一致性协议并将其相应功能封装到该模块中；所选择的一致性协议的特征是以leader为中心；一致性协议的每个实例针对复制状态机所处理的对象即请求或命令执行，通过一系列一致性协议的执行，这些对象被排序，从而保证复制状态机中各个副本间的状态一致性。

进一步地，所述方法在一致性协议的请求/命令协商与执行功能业已分开的基础上，关注“将协商分为局部排序与全局合并”的优化方式；据此，一致性协议模块又分为排序子模块、合并子模块和故障检测子模块；

所述的排序子模块是一致性协议模块的子模块；该模块处理的对象是复制状态机所处理的对象即请求或命令集合被划分后所得到的部分对象子集；通过排序模块的处理，对象子集被排序成为部分有序序列；由于该子模块由分布的进程子集执行，实现了负载均衡和性能提升；

所述的合并子模块是一致性协议模块的子模块；该模块将排序模块产生的中间结果，即请求或命令的部分有序序列，进行进一步的合并；合并实际上也是某种程度上的排序过程；合并模块产生的结果是复制状态机中所有副本所见到的一致的请求或命令序列；

所述的故障检测子模块是一致性协议模块的子模块，该模块的作用在于通过对故障检测机制或同步机制的定义，确保复制状态机在所处的具体云存储环境中能够顺利运作，不会由于故障的发生而使状态机的运作受到阻塞。

进一步地，所述方法根据资源约束/优化目标的需要，确定是否对复制状态机所处理的对象集合即状态进行划分，作为一致性协议模块处理的输入；通过状态划分，复制状态机的不同状态变量子集可以在不同的服务器子集上得到处理，从而提升复制状态机的处理效率。

进一步地，所述方法为一致性协议模块的子模块进行了配置，配置过程包括了两个部分，即映射定义和故障检测器设定，映射定义必须满足两个属性；

所述映射定义针对排序模块和合并模块的实现，定义了实现这些模块的服务器集合与进程集合之间的映射关系；对映射的配置是复制状态机针对具体的资源约束/优化目标的具体实现手段；通过在模块化框架的各个实例化过程中对映射关系进行具体定义，所得到的复制状态机实例就能够实现性能优化和负载均衡；

所述的两个属性作为具体复制状态机实例优化的基本属性，即服务器群组不相交属性以及进程集群相交属性；服务器群组不相交属性保证复制状态机的处理对象命令或请求集合被划分成的子集合可以被分配到不相交的服务器群组上并发运行，从而提高了性能；进程集群相交属性保证执行一致性协议的进程可以根据资源状态运行在指定的服务器上，从而均衡了负载；

所述故障检测器设定的目的是为了保证复制状态机中一致性协议的良好运行，针对故障模型并根据所选择的协议进一步设置了复制状态机中所采用的故障检测器。

进一步地，所述方法进一步指定了执行模块的实现，执行模块采用适当的进程集合，对已配置的一致性协议模块的输出结果进行执行，执行模块执行后，复制状态机的各个副本将按照相同的状态序列实现一致的状态转换。

与现有技术相比，本发明具有如下优点和技术效果：

本发明为复制状态机的设计者们提供一种直观的、灵活的、规范化的设计手段，统一设计流程，提高设计效率，并最终使复制状态机及其一致性协议的优化实现更加方便。利用本发明的框架，复制状态机设计者们可以针对具体的资源约束/优化目标灵活地实例化新的复制状态机及其一致性协议，以满足特定的性能优化与负载均衡的要求，并最终应用于特定的云存储环境。

附图说明

图1为复制状态机模块化框架设计方法的流程。

图2为复制状态机模块化框架。

图3为复制状态机模块化框架的操作协议架构。

具体实施方式

以下结合附图和实例对本发明的具体实施作进一步说明。

面向云存储的复制状态机模块化框架设计方法规范了设计的流程步骤。附图1介绍了复制状态机模块化框架设计方法的流程，关键点的相关说明如下：

为了进行复制状态机模块化框架的设计，本发明基于如下三个模型，即模块的执行模型、通信模型及故障模型。它们是模块化框架构建的基础：执行模型定义了执行复制状态机的环境与参与者对象(服务器与进程)；通信模型定义了复制状态机中各个参与者对象的底层通信方式(异步环境)；故障模型定义了复制状态机所适用的参与者对象(非拜占庭服务器与进程)。

执行模型：本发明关注基于功能划分和集合映射的优化方式，并未指定系统的规模和网络的范围。根据框架实例化得到的复制状态机实例可能运行于广域/局域环境下，也可能运行于跨网络的异构环境。框架的执行模型包含一个服务器全集S和一个进程全集P。

通信模型：本发明采用了适用于复杂云环境的异步分布式模型。运行于不同服务器上的进程在双向信道上通过消息交换进行通信。消息的交互是异步且不可靠的；它们可能被重复、丢失，但不会被损坏。消息传输延迟没有上界。在相对进程速率上也没有限制。

故障模型：本发明采用非拜占庭故障模型。即所有服务器都可能发生崩溃并随后恢复其状态。不过，即使发生故障后它们也不会表现出拜占庭式行为。

本发明将复制状态机中一致性协议各个执行阶段对应的行为或功能抽象为独立的模块，提出了以一致性协议为核心的复制状态机模块化框架。在该框架中，局部排序、全局合并、故障检测及通信机制等功能被划分为独立的模块。这种划分方式使复制状态机的结构更加清晰，有利于对具体复制状态机的实现和进一步优化。模块化框架为复制状态机的具体设计提供了方便、灵活的支持。遵循这一框架，复制状态机的设计者们就可以非常直观地明确其设计方案中各个模块的具体配置内容。

模块是对复制状态机某种功能的抽象。一个复制状态机模块化框架是对一系列针对不同资源约束/优化目标进行优化的复制状态机实例及其一致性协议的功能抽象和概括，它是包含了复制状态机各种功能模块的集合。我们在附图2中给出了复制状态机模块化框架的构成。各模块的功能说明如下。

1.通信机制模块：通信网络是复制状态机运行的载体。云端的网络和通信环境是复杂的，它会对复制状态机及其一致性协议的设计产生显著影响。尽管执行模型中的进程必需建立彼此间的逻辑点对点通信，但在不同网络条件下其实现手段(如，采用TCP还是UDP，单播还是多播)却不尽相同，这往往与复制状态机及其一致性协议的资源约束/优化目标有关。

2.一致性协议模块：抽象一致性协议模块显然是复制状态机模块化抽象框架的主要部分，它包括排序、合并和故障检测三个子模块。其中排序子模块和合并子模块的功能是由相应的进程群组实现的。

(1)排序子模块：该模块抽象了局部排序功能。在具体的一致性协议中它是由多个排序群组对发送给它们的那部分请求进行排序来实现的。注意，在本发明中不考虑在一致性协议中使用批处理的情况，因为它是独立于框架的技术。

(2)合并子模块：任何通过划分请求序列的协议都必须将多个决议流合并为一个全序，这就是合并模块所抽象的功能。合并功能在不同的一致性协议中可以通过不同的方式来实现，如合并群组对有序请求序列进行进一步的排序或按照某种预定义顺序进行合并。

资源约束/优化目标将影响对上述两个模块的实例化，这种实例化就是从进程全集到服务器全集的映射。

(3)故障检测子模块：分布式异步一致性协议通常都采用一个故障检测器来绕过FLP不可能性结论。不同的一致性协议可能采用不同的故障检测器。故障检测模块抽象如下功能，即确保能够及时识别协议执行过程中可能影响其活性的故障进程并提供某种应对的机制。这类机制包括leader选举或skip机制。前者避免故障leader阻碍协议向前推进，后者还可防止慢速进程对协议性能的影响。

3.执行模块：如此前所述，协商与执行被分开。因此执行模块独立于代表协商功能的抽象一致性协议模块而存在，它抽象了被排序请求的最终执行。

本实例提出的复制状态机模块化框架为针对具体资源约束/优化目标进行的复制状态机优化设计提供给了基础支撑。利用本发明的框架，可以直观而灵活地实现对具体复制状态机实例的设计。所设计的复制状态机的性能提升主要体现在对资源的高效利用和负载的均衡分摊上，这两方面的优化可以通过对实际执行协议的进程全集的良好分组并在服务器全集上的合理分布来实现。不同类型的进程群组承担不同的任务或处理不同的对象。有利于资源的高效利用，而其在服务器全集上的合理分布有利于负载均衡。由于排序任务被划分，由不同分组得到的部分有序序列在提交前必须被合并(在某种意义上也是一种排序形式)，它们最终由执行进程获取并执行。

对于复制状态机的具体实现而言，为了满足具体的资源约束/优化目标，其中各个模块的实现至关重要。复制状态机高效实现的关键在于针对局部排序和全局合并模块所设置的、从进程全集到服务器全集的映射，这也是复制状态机及其一致性协议得以优化的关键。简单地说，映射实际上是具有不同功能和负载的执行进程在物理服务器上的具体分配。这样，一个被划分为不同执行阶段的一致性协议就可以通过负载(即局部排序或全局合并)均衡分摊和资源(如CPU、网络和磁盘等)高效利用而实现对复制状态机及其一致性协议的优化。

为了方便地表述从进程全集到服务器全集的分配，本发明结合进程群组和服务器集群的属性，定义了两个全集间的抽象映射关系，使得复制状态机设计者可以基于这一抽象的映射关系派生出其特定于具体设计的配置关系。

本发明对框架的实例化是通过集合来描述的。集合是具有某些共享特征的元素的组合。描述涉及两种集合，即服务器的集合以及进程的集合。

定义1：服务器全集是由参与到复制状态机运行的所有物理服务器组成的集合，表示为S。令|S|＝m,m≥3,m∈N。

定义2：进程全集是由服务器全集中所有服务器上运行的、具体执行复制状态机各项功能的所有进程组成的集合，表示为P。令这里P_i是每台服务器上的进程数。

根据功能划分，复制状态机通常包含三类执行某种具体操作的执行进程，即排序进程、合并进程和执行进程。相同类型的进程一起组成了实现协议某种功能的进程集合。在本发明中，这样的一个进程集合被称为一个进程群组或群组。这样，我们得到了进行请求排序的排序群组(即排序进程集合，表示为O)，合并多个请求的合并群组(即合并进程集合，表示为M)以及最终执行请求的执行群组(即执行进程集合，表示为E)。注意，具体的复制状态机实例可能根据资源约束/优化目标将负载分摊给多个同类群组。在本发明中，我们将所有相同类型的群组的全体称为群组全集。因此我们得到了相应的排序群组全集(表示为G_O，G_O＝∪{O_i})、合并群组全集(G_M，G_M＝∪{M_i})和执行群组全集(G_E，G_E＝∪{E_i})。这些群组全集通常对应于模块化抽象框架中的模块。

本实例将运行排序进程、合并进程、执行进程的执行服务器分别称为排序服务器、合并服务器和执行服务器。由于一台服务器可能运行不同的进程，因此相同的服务器可能既是排序服务器又是合并服务器，甚至还是执行服务器。我们将运行同类进程集合的服务器集合称为一个服务器集群或集群。这样，我们就得到了排序集群(即排序服务器集合，表示为S)、合并集群(合并服务器集合，表示为T)和执行集群(执行服务器集合，表示为U)。在本发明中，我们将相同类型的集群的全体称为集群全集。因此我们得到了相应的排序集群全集(表示为C_O，C_O＝∪{S_i})、合并集群全集(表示为C_M，C_M＝∪{T_i})和执行集群全集(表示为C_E，C_E＝∪{U_i})。

在复制状态机的模块化抽象框架中，以上所述集合具有如下两个属性：

群组不相交属性：

集群相交属性：

根据上文所述，复制状态机模块化抽象框架的核心是排序模块和合并模块。对状态机及其协议的扩展是通过在适当的服务器集合上运行相应的进程集合来实现的。它实际上是进程全集在服务器全集上的合理分配。我们通过定义从集合到集合上的一个抽象的映射来描述两者之间的分配关系。

定义3：令进程全集P中的排序群组全集、合并群组全集、执行群组全集分别为G_O、G_M、G_E，服务器全集S的排序集群全集、合并集群全集、执行集群全集分别为C_O、C_M、C_E，它们遵循群组不相交属性和集群相交属性。定义P到S的一种抽象的映射关系为使得下式成立：

$P\stackrel{M}{\to }S\iff G_O\stackrel{M}{\to }{C}_O,G_M\stackrel{M}{\to }{C}_M,G_E\stackrel{M}{\to }{C}_E$

映射关系表示从符号左侧的集合到右侧的集合上的一种分配关系，代表进程群组运行在服务器集群上。

在复制状态机模块化抽象框架中没有被明确描述的另一个概念是状态，它也会影响状态机实例的设计。本发明中有关于状态的如下定义。

定义4：状态指的是每个服务副本上一组被客户端发送的请求读取和修改的状态变量的全集，表示为V。一个状态全集可以被划分为不同的子集i∈N。这些子集可能相交或也可能不相交。

在复制状态机模块化框架设计与集合、映射定义的基础上，我们规范了运行在复制状态机中的一致性协议应遵守的公共步骤，使其成为具体协议执行的基础性框架算法。它包括了状态划分、映射配置和协议执行三个部分。如附图2所示。具体说明如下。

并非所有优化都需要通过状态划分来实现。对于复制状态机实例而言，是否进行状态划分取决于优化的需要。不过，如果状态划分确实发生，则存在两种情况，即状态分区重叠(存在两个分区可能具有一部分相同的状态变量)和状态分区不重叠(任意两个分区都不具有相同的状态变量)。

配置，包括指定映射和设置故障检测机制，是实现优化的关键。不同的资源约束/优化目标影响了复制状态机实例的配置。指定映射的本质是进程全集在服务器全集上的分配，对特定场景下的性能提高和负载均衡起重要作用；故障检测机制则可根据映射而灵活地进行设置。

协议的执行分为三个阶段，即由执行群组、合并群组和执行群组分别执行的局部排序阶段、全局合并阶段以及最终执行阶段。虽然不同复制状态机实例及其一致性协议实现方式不同，但其执行基本上都涉及以上三个阶段。不同的配置会对局部排序阶段和全局合并阶段产生显著的影响。局部排序阶段形成的有序序列不是最终结果，它会被作为中间结果缓存起来，进而作为全局合并阶段的提案获得全局的一致共识。最终，所有被排序的请求会被提交并在最终执行阶段被执行。

复制状态机的模块化抽象框架必须具有如下目标，即，使可能发生故障的分布式进程以相同的顺序执行相同的请求。为此，其实例必须满足以下的活性属性模块化抽象复制状态机有效性、模块化抽象复制状态机一致性和安全性属性模块化抽象复制状态机完整性、模块化抽象复制状态机全序：

模块化抽象复制状态机有效性：如果任意排序群组中的某个正确的进程提出了一个请求r，则所有正确的合并进程将最终提交r。

模块化抽象复制状态机一致性：如果某个正确的合并进程提交了一个请求r，则所有正确的合并进程最终也会提交r。

模块化抽象复制状态机完整性：任何给定的请求r最多只被每个正确的合并进程提交一次，并且仅当r在之前被提出。

模块化抽象复制状态机全序：如果两个正确的合并进程p和q都提交了请求r₁和r₂，则p在r₂之前提交r₁当且仅当q在r₂之前提交r₁。