海量存储机群系统中提高系统MTTF的设计和分析

摘  要：当今，机群系统被广泛地应用于海量存储系统。对数据有高可靠性要求的应用，如何提高系统MTTF是人们研究的主要问题。本文提出了一个新的动态备份策略，"并行数据备份策略"，通过详细的理论分析，指出该策略可显著地提高系统MTTF；还通过仿真实验，验证了其效果。
关键词：海量存储;机群系统;平均故障前时间

1 引言

在过去几年里，机群系统被广泛地应用于海量存储系统，比如，著名的Google文件系统就包含上千个基于linux的计算机。这样做的好处有三个。第一，由于每个节点都是大批量生产的，整个系统的价格可以很低。第二，通过增减节点，系统可以简单地进行扩展。第三，通过在互相独立的节点上备份数据，可以显著地提高系统中数据的可靠性。

对存储系统来说，系统的平均故障前时间（MTTF）是指系统中出现某个数据因所有的备份都丢失，而导致该数据无法挽回地丢失所需的平均时间。对于有较高数据可靠性要求的系统，系统的MTTF是衡量系统性能的一个重要指标。提高系统MTTF的一个方法就是   提高数据的备份数。备份数的选择需要综合考虑，因为选择过低的备份数，系统的MTTF不能满足要求；而选择过高的备份数，系统的存储资源就被浪费，特别是当系统中包含大量数据的时候。另一个方面，考虑到机群系统中节点会不断失效，因此还必须对备份数因节点失效而降低的数据进行动态备份，以提高系统MTTF。本文提出了一个新的动态备份策略，"并行数据备份策略"，理论分析了其性能，并进行了仿真实验。

2系统结构和动态备份策略                                 

整个系统的构成情况如下。机群系统包含n个节点。系统中的所有对象状态以状态块为单元进行组织。系统中存储的互不相同的状态块总数正比与节点总数。每个状态块有m个备份。同一个状态块的备份不能在一个节点上，以保证可靠性；一个节点可以同时存储许多个状态块的备份。每个正常节点都会失效。

在出现一个节点失效后，系统的动态备份策略为：1）为失效节点上的每个状态块，选择一对源节点和目标节点，源节点包含该状态块，目标节点不包含；2）让这些状态块，同时在各对应源节点和目标节点之间开始转移，直至转移完毕。其中，各状态块的源节点和目标节点的选择应尽可能互不重合，以使尽可能多的状态块转移可并发进行。另外，这个备份策略也意味着每个状态块的备份可存储于任一节点上。下面，通过建立数学模型，理论估计该动态备份策略下的系统MTTF。

3理论分析

考虑用Markov过程来描述这个模型。为此，做如下假设。节点的失效速率服从指数分布，均值为l。由于系统中节点数目巨大，所以在一个节点失效后，其上的状态块完全可以找到互不重复的源节点和目标节点，状态块转移可以并发进行，可设转移速率服从指数分布，均值为lb。另外，考虑到系统中的节点数目巨大，可以认为系统在出现某状态块无法挽回丢失时，系统中正常工作的节点数依然维持在较高水平，与起始时的节点数n在同一个数量级。因此，可近似认为系统中节点数始终为n。于是，取有几个失效节点上的状态块正在进行转移为研究对象，可得状态转移图如图1。其中，m为每个状态块的原备份数；ai表示当一个有n个节点的系统中有（i-1）个失效节点上的状态块正在进行转移时无状态块丢失，而再失效一个节点发生一状态块丢失的概率；状态i'（i>=m）表示系统中出现某状态块无法挽回地丢失。

图1 系统的状态转移过程

因此，目标就化为系统进入状态i'的均值时间。这个系统可以近似看成一个状态数为无穷的一维生灭过程。要求解进入状态i'的瞬态概率，将涉及解一个含无穷多等式的微分方程组，这是很复杂的。但根据以往求一维生灭过程的稳态解的经验知道，  。因此，如果ln-1/mn很小，那随着n的增加，Pn将急速下降。于是，当n增加到一定值时，可以忽略其后的状态。对一个典型的含1000个节点的机群系统，若节点的MTTF为一天，则系统中出现某节点失效的速率约为0.011/秒；而一个状态块的平均转移时间可以在10秒钟左右，即，转移速率为0.1/秒；这两个速率之比约为0.1。因此，可以忽略系统中n>=m的状态，而把系统进入状态m'的均值时间作为系统的MTTF。

下面，以m=3为例，求系统进入状态m'的均值时间E3(T)。由一维生灭过程的瞬态分析，可得以下方程组。其中，Pi(t)表示在t时刻系统处于状态i的概率。

这是一个四元常系数线性微分方程组，可通过消元法消为一元线性微分方程，解之，然后可以求出其他各元的解。再根据边界条件，可以求出各解中的系数。系统的边界条件为

   。 。

而E3(T)可表示为：

。。

为了求出E3(T)的具体值，还必须求出a3的值。限于篇幅，不加证明的给出如下求am的定理。

定理：如果一个拥有n个节点的机群系统，含kn个互不相同的数据块，每个数据块都有m个备份，每个备份随机地分布于机群系统中不同的节点上，那么当系统中出现有s-1个节点失效的时候，无数据块丢失；而当系统中出现有s个节点失效的时候，系统中出现某个数据块无法挽回地丢失的概率为， 其中， 并且s>=1。

根据此定理，求出当n=1000, m=3, k=100时a3=0.0006。

根据以上推导，可求出E3(T)在不同条件下的值，得到在n=1000, l=1/(24*3600) (/秒)的配置下，当lb=0.1(/秒)时，E3(T)=319天；当lb=0.05(/秒)时，E3(T)=86天；当lb=0.01(/秒)时，E3(T)=2天。类似地，可求出m=2时系统进入状态m'的均值时间E2(T)，得到在n=1000, l=1/(24*3600) (/秒)的配置下，当lb=0.1(/秒)时，E2(T)=1.3小时；当lb=0.05(/秒)时，E2(T)=0.73小时；当lb=0.01(/秒)时，E2(T)=0.27小时。

分析以上数据可以得到两个结论。第一，三个备份的系统比两个备份的，能显著地提升系统的MTTF。在通常配置下，三个备份的系统的MTTF可达几十天；而两个备份的系统的MTTF只能在1小时左右。第二，数据块的转移时间显著地影响系统的MTTF，转移时间越短，系统的MTTF越长。

4仿真实验

下面，通过仿真实验来验证上面的结论。仿真实验中的主要参数和限制条件如下。状态块总数与节点总数之比为rchunk=100，节点失效速率l=1/（24小时），节点恢复速率m=1/（24小时）。在进行状态转移时，源节点和目标节点的选择策略：源节点，必须包含该状态块的备份，同时其上正在进行拷贝的状态块数目必须最小；目标节点，从所有不含该状态块的备份的节点中随机选取，同时其上所存储的状态块数目不能超过平均值的tcap=1.3。为保证状态块拷贝不影响系统的正常服务，人为限制正在进行拷贝的节点数目不超过机群系统中节点总数的tratio=40%。为了同样的目的，人为限制状态块拷贝只占用网络带宽的一半；若有多个状态块在向外输出，则它们分享带宽。网络带宽为100Mb/s，一个状态块大小为64M。为了使新加入的节点不在短时间里收到大量的新备份，人为限制每个节点正在进行拷贝的状态块数目不超过tcopy=1。实验结果，如图2所表示。这些限制条件均来自实际系统。

图2不同备份数下的系统MTTF       

从图上可以很明显地看到三个特点。第一，在相同节点数目下，备份数越多，系统的MTTF越大，这是所预期的。第二，当节点数目达到1000的时候，在2个备份的情况下，系统MTTF小于1小时；在3个备份的情况下，系统MTTF仍能保持在400小时（约为16天）左右。这些值与前面的理论分析基本一致，数值都在相同的数量级。第三，当备份数只有1或2个的时候，随着节点数的增加，系统MTTF显著下降；而当备份数是3个的时候，随着节点数的增加，系统MTTF基本保持不变。这个现象可以解释如下。首先，当备份数只有1或2个的时候，系统MTTF随着节点数的增加而下降的原因是：当节点数增多时，系统中出现节点失效的可能性就增大。比如，对于一个包含1000个节点的机群系统，若每个节点的失效速率为l，则系统中出现节点失效的速率为1000l。在这样高的失效速率下，很容易发生包含同一个状态块备份的两个节点（当备份数为2时）几乎同时失效。另外，随节点数的增多，状态块的数目也成倍增加，这也增加了系统中出现某状态块丢失的可能性。其次，当备份数有3个的时候，系统MTTF随着节点数的增加能保持稳定的原因是：当节点数增多时，虽然系统中出现某个节点失效的可能性增大，会降低系统MTTF，但另一个能起到相反的作用因素显著表现出来。这个因素就是通过并发拷贝操作，大大降低对象状态转移时间。举个例子。假设一个机群系统有1000个节点，每个节点存储着100个状态块，每个状态块大小为64M。当一个节点失效后，系统就会为其上的100个状态块寻找一对源节点和目标节点进行转移。正常情况下，在100Mb/s的网络里，若只使用一半带宽的话，转移一个状态块需要（64MB*8b/B*2）/(100Mb/s)，即，近似为10秒。那么，转移100个状态块需要1000秒左右，即，近似为15分钟，这是很长的一段时间。但考虑到系统中有1000个节点，很容易找到这样100对源节点和目标节点，它们没有任何两个节点是相同的。在这种情况下，拷贝操作完全可以并发进行，100个状态块可在10秒内拷贝完毕，这是很短的一段时间。

缩短拷贝时间的最大好处是，在拷贝期间发生新节点失效的可能性减小，进而这样就可以减小某个状态块丢失的可能性。为了证明降低拷贝时间的作用，考虑如下对比实验。对于备份数为2和3的那两组实验，将原先的tratio的限制舍弃不用，而限制系统中正在进行拷贝的节点数目的上限为10个。如果实验的结果表明，随节点数的增加，系统MTTF显著降低，那么就证明了降低拷贝时间对提高系统MTTF的作用。图3显示的是得到的实验结果。作为对比，把没有该限制的原实验结果也画在图上，用虚线表示。实验的结果正如所预料的，在两种实验情况下，系统MTTF都随节点数增加，而显著降低。特别地，当节点数为1000时，在备份数为2的情况下，系统MTTF远低于1小时；在备份数为3的情况下，系统MTTF只有2小时左右。这些性能数据，都比原先没有该限制的实验，要低得多。

图3有并发限制与无并发限制的比较

5 结论

本文提出了一个新的动态备份策略，"并行数据备份策略"。研究表明，该策略可显著地提高系统的MTTF。特别地，当系统节点数目达到1000的时候，在3个备份的情况下，系统MTTF仍能保持在几十天的数量级。并且指出该策略的有效性主要来源于通过并发拷贝操作，大大降低了对象状态的转移时间。

本文创新点

本文提出了一个新的动态备份策略，"并行数据备份策略"。通过详细的理论分析和仿真实验，指出该策略可以在系统中当节点数达到成百上千时显著地提高系统的MTTF。该策略若使用在海量存储系统中，可以显著地提高数据的可靠性。