云存储多异构文件联合延迟尾概率凸优化分析

许小媛，李海波，黄 黎，2

1.江苏开放大学 信息工程学院，南京210017

2.南京航空航天大学 计算机科学与技术学院，南京211106

由于大数据分析和云计算[1]等新兴应用的出现，如今的分布式存储系统通常存储数PB[2]的数据。因此，这些系统正在从完全数据复制过渡到使用擦除代码在多台机器和机架上编码和分发数据块，以便在系统出现故障的情况下更有效地利用存储空间，同时保持高可靠性。结果表明，由于存储空间和数据中心占用空间较小，与重复编码相比，使用擦除编码[3]可以降低存储成本50%以上。

对于擦除编码存储系统，文件被编码成多个大小相等的数据块，允许从任何子集进行重建。因此，重建文件需要从不同的服务器获取不同的块，这导致尾部延迟显著增加，因为在这样的系统中，服务延迟是由最热的存储节点以最高的拥塞和最慢的速度决定的，这实际上成了性能瓶颈[4]。文献[5]指出尽管存在负载平衡和资源管理等机制，但对大型存储系统的评估表明，延迟性能具有高度的随机性。文献[6]指出擦除编码数据存储系统的总体响应时间由所需并行作业的长尾分布控制，每个作业可能有多个并行任务。文献[7]指出尽管最近在提供平均服务延迟的界限方面取得了一些研究进展，但对于擦除编码存储系统中的尾延迟知之甚少。文献[8]中描述了具有独立指数服务时间的相同服务器的基于复制的系统的平均服务延迟。基于擦除编码的系统的问题仍然是一个开放的问题。为了提供同构文件的平均服务延迟上限，文献[9]提出Fork-join队列分析通过将每个文件请求分叉到所有存储节点来提供平均服务延迟的上限。文献[10]提出基于排队论分析的块调度策略，它只允许缓冲区头部的第一个请求向前移动。然而，由于状态爆炸问题，这两种方法都无法量化尾部延迟，因为相应队列模型的状态不仅必须封装当前系统的快照（包括块放置和排队请求），而且还必须封装单个节点处理块请求的过去历史。随后，利用顺序统计分析和概率请求调度策略，在文献[11]中给出了任意服务时间分布和异构文件的平均延迟界限。文献[12]基于复制系统的大量服务器限制，使用具有均匀概率和指数服务时间的概率调度来显示与复制相比擦除编码的延迟性能的改进。文献[13]分析了不同基于队列的调度策略，假设在随机块放置的情况下，服务器之间的负载是对称的。虽然降低平均延迟被发现对降低延迟包络有积极影响，但量化和优化擦除编码存储的尾部延迟仍然是开放问题。

本文提出一种分析框架来量化分布式存储系统中使用擦除码来存储文件的尾部延迟。这个问题具有挑战性：（1）最慢的存储节点的性能会严重影响尾部延迟；（2）需要动态解决一个联合块调度问题，以决定为每个文件请求服务分配块服务器；（3）由于块访问的依赖性和干扰，共享存储服务器上不同文件的时间问题更加复杂。

1 系统模型

考虑由m个异构服务器组成的数据中心[14]，表示为M=1,2,…,m，也称为存储节点。采取分布式存储一组r文件，索引为i=1,2,…,r，将每个文件i划分为ki个固定大小的数据块，然后使用(ni,ki)MDS擦除代码对其进行编码，以生成与文件i相同大小的ni个不同数据块。编码块被分配并存储在ni个不同的存储节点上，由一组Si个存储节点表示，满足条件Si⊆M和ni=|Si|。使用(ni,ki)MDS擦除代码可从ni数据块中的ki任何子集重建文件，同时还引入了ni ki的冗余因子。因此，在每个文件请求到达时，调度程序选择ki不同的块并检索其以重构所需的文件。图1给出一个有7个节点的分布式存储系统。系统中分别使用（6，4）、（5，3）和（3，2）擦除码存储3个文件。到达系统的文件请求被联合调度以访问ni不同块中的ki，以前的研究主要集中在平均延迟优化上。

图1 分布式存储系统（7节点、3文件）

然而，这两种方法都没有量化尾部延迟，因为相应队列模型的状态不仅必须封装当前系统的快照，包括块放置和排队请求，而且还必须封装单个节点处理块请求历史。这是因为生成的队列的马尔可夫链表示需要对每个状态进行封装：（2）队列中每个批的状态；（1）将块请求精确分配给存储节点，因为节点由多个异构文件共享。这会导致状态爆炸问题，因为实际的存储系统通常处理大量的文件和节点。截至目前，量化擦除编码存储系统的尾部延迟仍然是开放问题，因为在联合请求调度方面存在挑战以及散乱片段对热存储节点的依赖性。考虑存储3个文件的擦除编码存储系统，如图1所示。很容易看出，以相同的概率访问可用块的简单调度策略会导致较高的尾部延迟，这是由性能最低的热存储节点（在本例中为节点1和5）决定的。然而，负载平衡每个服务器处理的请求数量的策略并不一定优化所有文件的尾部延迟，这些文件使用不同的擦除代码，从而对服务延迟产生不同的影响。假设来自所有存储节点的块传输时间具有相同分布，使用（6，4）代码的文件1仍然可能比使用（3，2）代码的文件3具有更高的尾部延迟，因为每个文件请求的服务时间由4个选定块（而不是2个选定块）中最慢的一个决定。

本文中使用“概率调度”策略[15]：（1）以预定概率P(Ai)将每批数据块请求（对应于同一文件请求）发送到适当节点集（由文件i的服务器集Ai表示）；（2）每个节点在本地队列中缓冲请求并按顺序处理。可行概率为

的概率调度策略存在于且仅当存在条件概率πi,j∈[0,1],∀i,j满足：

如果j∉Si，则πi,j=0。πi,j是从节点j检索文件i块的概率。因为每个集合Ai都包含ki节点，可得ki,∀i。考虑图1所示的示例。在概率调度下，当文件1请求到达时，随机选择具有已知概率{π1,j,∀j}的可用文件块的k1=4节点，并将一个块请求分派给每个选定的存储节点。然后，每个存储节点独立管理其本地队列，并按顺序继续处理请求。如果文件请求的所有块请求都由单个节点处理，则该文件请求将完成。

本文所用到的变量参数声明如下：r是系统中的文件数，i=1,2,…,r；m是存储节点数是文件i的擦除代码参数；λi是文件i的到达率；πij是从节点j检索文件i块的概率；Li是检索文件i的延迟；x是参数索引延迟尾概率；Qj是节点j的逗留时间；Xj是节点j的块服务时间；Mj(t)是节点j服务时间的矩生成函数；μj是节点j的平均服务时间；Λj是节点j到达率；ρj是节点j的请求强度；Si是来自文件i的块的存储节点集；Ai是用于从文件i提供文件块的节点集是节点j的移动指数分布服务时间参数；ωi是文件i的权重。

2 尾部延迟界限

2.1 任意服务时间分布情形

首先量化具有任意服务时间分布（即任意已知的Xj分布）的擦除编码存储系统的尾延迟。设Qj为块请求在节点j中花费的（随机）时间（逗留时间）。在概率调度下，文件i请求的响应时间（用Li表示）由随机选择的存储节点集Ai处的最大块响应时间确定。

在概率调度下，块请求在节点j处的到达形成速率为的Poisson过程。设为在服务器j处处理单个块的服务时间的矩生成函数。然后，可给出了Qj的Laplace-Stieltjes变换：

式中，ρj=ΛjE[]Xj是节点j的请求强度。此外，使用概率调度将文件i的延迟表示为Li。文件i的延迟尾概率定义为给定x的Li大于或等于x的概率。对于给定的文件i的权重ωi，希望最小化目标由于在一般服务时间分布中很难找到闭式的Pr(Li≥x)，因此在此基础上进一步使用一个上界来代替目标中的Pr(Li≥x)。下面的定理给出了文件延迟尾概率的上界。

定理1对于任意且满足Mj(tj)＜∞和情况下，使用概率调度的文件i，的延迟尾概率上界为：

证明使用概率调度来考虑延迟尾概率的上界，如下所示：

其中，（a）表示从概率调度开始，检索文件的时间是从Ai检索所有块的最大时间。利用马尔可夫引理，可得到使用Pollaczek-Khinchine公式对公式（2）中的Qj进行Laplace变换，并设定S=-tj。然而，只有当时，表达式才是有限的。这证明了定理陈述中的结果。

在某些情况下，力矩生成函数可能不存在，这意味着对于任何tj＞0，都不满足条件在这种情况下，将直接使用Laplace变换在下一个定理中给出另一个上界。

定理2对于任意sj＞0，且文件i，Pr(Li≥x)延迟尾概率上界为：

证明这个结果是定理1的一个变种，其中马尔可夫引理是使用排队等待时间的Laplace变换而不是矩生成函数。

2.2 移动指数时间分布情形

考虑当服务时间分布是移动指数分布时的情况。假设来自服务器j的服务时间分布具有概率密度函数fXj(x)，如下所示：

指数分布是βj=0的特例。力矩生成函数如下：

其中，t＜αj。由此可得以下结果。

推论1对于任，当服务器的服务时间分布为转移指数分布时，文件i的延迟尾概率Pr(Li≥x)上界为：

由于指数分布是移位指数分布的一个特例，可得如下推论。

推论2对于任意当服务器的服务时间分布为指数分布时，文件i的延迟尾概率Pr(Li≥x)上界为：

进一步量化了任意擦除编码存储系统文件大小和指数服务时间下的服务延迟尾指数。证明了基于概率调度的算法获得了α-1的最优尾指数，其中α＞2是Pareto分布块大小的形状参数。

2.3 加权延迟尾概率优化模型

本节提出一个包含多个异构文件的联合延迟尾概率优化模型。由于的延迟尾概率由给出，因此考虑一个最小化所有文件的加权延迟尾概率的优化，定义为：

式中，ωi是分配给文件i的正向权重。设定从而使到达率较大的文件加权更高，文件i服务时间的延迟尾概率为所提出的延迟尾概率界的目标函数为：

上述约束中，约束①给出在给定调度概率πi,j和到达率λi下每个节点的总到达率Λj；约束②定义了关于参数tj的矩生成函数；约束③定义了服务器的流量强度；约束④～⑥保证调度概率是可行的；根据约束⑨中的技术约束，表面力矩生成函数存在。如果满足约束⑨，则ρj＜1也成立，从而确保存储系统的稳定性（即，在给定到达率和调度概率下，队列长度不会膨胀到无穷大）。注意到tj＞0可以等价地转换为tj≥0（约束⑧），因为tj=0不满足，并且已经被考虑在内。对于π的优化有助于降低加权尾延迟概率，并在选择访问文件的最低队列服务器时提供了显著的灵活性。

备注1由于约束⑨在(π,t)中是非凸的，因此所提出的WLTP优化是非凸的。此外，内容放置S具有整数约束。

2.4 优化问题凸性分析

为得到算法解，证明当其他变量固定时，对于优化变量t和π，问题是单调凸的，这样可以简化优化算法设计，由此可以提出一个交替优化算法来解决这个问题。

定理3对于满足约束①～⑨，在区域t=(t1,t2,…,tm)内，目标函数是凸性的。

证明在求和过程中，该项只依赖于tj值，这表明相对于tj值是凸的。因为这里只有一个索引j，所以这个证明的其余部分可忽略这个子卷积。

因此，F(t)可表示为的

乘积，其中由于满足

约束①～⑨，h(t)＞0。此外，h(t)的所有正导数都是非正的。设w(t)=-h′(t)，则w(t)≥0，w′(t)≥0。由此可得：

进而可得F″(t)计算形式为：

结合h(t)≥0和w′(t)≥0可得在区间t=(t1,t2,…,tm)内，目标函数是凸的。

然后，对定理3进行扩展，验证在区间π=(πij,∀i=1,2,…,r,j=1,2,…,m)上目标函数也是凸的。

定理4对于区间目标函数是凸的。

首先证明Hj在Λj中是单调递增凸函数，Hj可以写成：

因此，Hj是Λj的单调递增凸函数。同时因为Λj是Λj的单调递增凸函数。两项乘积也为凸函数，结论得证。

2.5 优化算法设计

因为目标模型相对于π和t是凸函数，严格的＜约束可以修改为≤足够小约束。约束条件在每个变量中也分别是凸的。现在将开发一个交替最小化算法来解决这个问题。

（1）算法结构。为了描述算法，首先定义三个子问题：

子问题1t优化问题，输入π,S。

约束条件：①～③，⑧～⑨。

子问题2π优化问题，输入t,S。

约束条件：①～⑥，⑨。

子问题3S优化问题，输入t,π。

约束条件：①～⑦。

对于布局子问题（S-优化），考虑对每个文件请求分别使用固定π和t进行S上的优化。首先重写文件i的延迟尾概率，如下所示：

通过将现有πiu分配给具有现有负载的服务器来量化对总延迟尾概率的贡献。Gr上的最小权匹配可找到一个最小化的最优β：

算法1给出了一种求解延迟尾概率问题的算法，其中随机选择文件的放置顺序。其决定被更改的文件的顺序会有所不同。在所提出的算法中，由于存在一个交替最小化的外循环，只需对文件进行一次遍历。由于目标是非负的，并且目标在每次迭代中都是非递增的，所以算法收敛。

算法1延迟尾概率问题的改进算法

3 实验分析

对比算法：（1）预计平等访问概率（PEAP），对于每个文件请求，联合请求调度器以相同的概率选择可用节点。（2）随机预计平等访问概率（PEAP-RP），与PEAP策略相比，块被均匀地随机放置。（3）预计服务费率比例分配（PSPP），联合请求调度器选择访问概率与存储节点的服务速率成比例。此策略根据服务器的服务速率按比例分配服务器。（4）随机预计服务费率比例分配（PSPP-RP），与PSPP策略相比，块被均匀地随机放置。在辅助变量选择上，对加权延迟尾概率进行了优化。

实验参数：云存储文件数量r=1 000，所有文件大小是200 MB，使用由m=12个分布式节点组成的分布式存储系统中的擦除码（7，4）。考虑块服务时间随速率αj和位移βj服从一个位移指数分布，本文采用12个不同服务速率αj和移位βj的异构存储节点，见表1所示。前250个文件每秒的基本到达率为2/150，后250个文件每秒的基本到达率为4/150，接下来的250个文件是6/150，最后的250个文件是3/150。本文还考虑了文件的权重与到达率成正比。为了初始化算法，对于所有tj=0.01在放置服务器上选择πij=k/n。然而，由于这些π和t的选择可能不可行，将初始化π修改为与上述选择最接近的范数可行解。

表1 异构存储节点参数设定

实验1（加权延迟尾概率）图2中给出本文算法以及对比算法的加权延迟尾概率实验模拟结果。本文算法策略通过提出的在π、t和S上的替代优化算法来求解最优加权延迟尾概率。通过优化t和布局，策略PEAP使用相同的服务器访问概率，向可行区域投射，而策略PSPP根据服务速率在不同服务器上分配块请求。然后，对上述给定的πi,j的值最优地求出t的值。

图2 加权延迟尾概率

根据图2所示实验结果，本文提出的联合优化π、t和S的算法比选取的简单的对比启发式算法可提供显著的性能改进，实验结果显示本文算法的加权延迟尾概率降低了几个数量级。例如，所提算法策略将99%的加权延迟从对比策略中的160 s以上减少到大约20 s。

实验2（到达率影响）接下来将模拟不同的请求到达率对加权延迟尾概率的影响，选择x=50 s。对于λ作为基本到达率，将所有文件的到达率从0.2λ增加到1.4λ，并在图3中绘制加权延迟尾概率。

图3 不同文件到达率的加权延迟尾概率

根据图3结果可知，当延迟尾概率随着到达率的增加而增加时，所提算法为不同的文件分配不同的延迟以保持低加权延迟尾概率。实验结果显示，所提出的算法优于选取的对比实验策略。由于在高到达率下加权延迟尾概率更为显著，因此观察到在图3中PEAP和本文算法策略之间，在最高到达率下延迟尾概率显著提高了约9倍（约0.025到约0.22）。所提策略总是得到最小的延迟。因此，有效地降低高到达率文件的延迟可以降低总加权延迟尾概率。

实验3（文件数量影响）图4给出将文件数量从200变为1 200对加权延迟尾概率的影响。加权延迟尾概率随着文件数量的增加而增加，这会带来更多的工作负载（即更高的到达率）。所提优化算法对新文件和现有文件进行优化，以将总的加权延迟尾概率保持在一个较低的水平。可见所提出的优化策略有效地降低了尾部概率，并且优于所选取的对比算法策略。因此，对所有三个变量π、t和S进行联合优化有助于显著降低尾部概率。

图4 不同文件数的加权延迟尾概率

实验4（文件大小影响）实验模拟中，将文件大小从200 MB更改为700 MB，并在图5中用不同的文件大小绘制最佳加权延迟尾概率。为了获得与默认大小200 MB相比文件大小增加的影响，将参数α和β的值与移动指数服务时间分布中的块大小成比例地增加。随着文件大小的增加，文件的加权尾延迟概率增加，所提算法与对比策略进行了比较，验证了所提优化算法可以显著降低尾延迟。

图5 不同文件大小的加权延迟尾概率

实验5（浪潮云Inspur实验）选取浪潮云Inspur实验平台进行算法性能测试，选取的实验指标为算法云存储冗余度，对比算法仍然选取上述算法，实验参数设置同上。出冗余度（RSR）是考虑异构存储系统冗余节省，在保证数据可用性dˆ的RSR指标定义为：

式中，rhomo和rheter分别为同质系统和异构系统，实验对比结果见表2所示。

表2 浪潮云Inspur实验结果对比

根据表2实验结果，在设定相同的数据可用性指标下，所提算法具有的数据冗余度指标实验结果最低，表明所提算法具有更高的计算效率。同时，随着数据可用性dˆ的增加，浪潮云Inspur实验结果的RSR指标逐渐增大，这表明数据可用性对于冗余度指标，具有直接的影响。

4 结束语

本文的主要贡献概括如下：（1）提出一个分析框架，用于量化和驯服云存储（TTLoC）上的尾延迟、任意擦除编码存储系统和服务时间分布。（2）当数据块传输时间服从移动指数分布时，提出一种加权延迟尾概率优化方法，通过在数据块放置、辅助变量和调度策略三个维度上对系统进行优化，同时最小化所有文件的尾延迟。（3）提出了一个分析框架来量化任意擦除编码存储系统的服务延迟尾指数。（4）提出了一种交替优化算法，它收敛于尾延迟优化的最优解。下一步，计划在真实云环境中开发数据云存储系统平台，验证所提方法相对于所考虑的基线的优越性。