分布式存储的数据可靠性估计 - 模特卡罗法

存储系统的数据可靠性是指在给定的时间（一般取一年）内数据不丢失的概率。利用分布式方法存储的数据，一般可以达到比较高的数据可靠性。比如，亚马逊 S3 存储服务的数据可靠性指标是 11 个 9 ，也就是 99.999999999% 。照此计算，用户存储百亿对象，平均十年可能出现 1 个对象丢失。

对存储系统来说，为了提升数据可靠性，需要存储一定的冗余数据。有了冗余，就有可能在部分数据丢失的情况下，利用剩余数据还原出原始数据。数据冗余的常用方法包括多副本、 RAID 、 EC （ Erasure Coding ，可看做 RAID 的扩展）等。多副本，顾名思义，就是存储系统中存储多份数据，如 3 副本、 4 副本等。本着鸡蛋不放在同一个篮子里的原则，同一份数据的不同副本一般会放在分布式存储系统不同节点的硬盘上。

对一个 3 副本的存储系统来说，发生数据丢失事件，等价于系统中存储某个 3 副本的硬盘同时失效。这是一个小概率事件，因为对于分布式存储来说，系统中任何一块数据失效，都立即会启动数据重构（利用数据冗余性在系统中其他节点上恢复出失效硬盘的所有数据），重构完成后，所有数据又都变成了 3 副本状态。对于分布式系统，其数据重构也是分布式的，所以速度较快，一般数 TB 的硬盘数据可以在小时级的时间内完成重构。如果发生数据丢失，就意味着在一块硬盘未完成数据重构的时间段内，又发生了 2 块硬盘（且均含有第一块失效硬盘中某些数据的副本）失效事件，这肯定是小概率事件。

那么，如何定量估计分布式系统的数据可靠性呢？这里主要有两种方法：蒙特卡洛法和简单估计法。

蒙特卡洛方法是一种统计模拟法。其基本想法是：

1 ：把统计周期（例如一年）划分成若干个时间片（比如 10 分钟 1 片）。

2 ：从第一个时间片开始：根据存储系统中各关键组件（软硬件）的失效特征（失效分布函数）利用计算机随机地生产状态函数，并根据组件的拓扑连接关系和系统逻辑判断在这个时间片上是否发生了数据丢失事件

3 ：重复 2 ，直到最后一个时间片。并计算在统计周期内发生的丢失事件的时间片占比。这个比率就是整个系统的数据可靠性。为了使数据较为准确，实际需要对 1~3 步骤进行大量循环，并统计其算数平均值。

上述过程中，最为关键的是第二步。在这个步骤中，首先要确定造成数据丢失的关键组件。对分布式存储系统来说，造成数据丢失的主要原因是硬件失效（除硬件失效外，软件 Bug 也会造成数据可靠性降低，软件 Bug 不在本文中论述）。硬件失效包括硬盘失效、 CPU 失效、内存失效、 HBA 卡失效（导致其下挂的硬盘失效）、网络异常（交换机失效、网卡失效）等。确定了关键组件后，我们把系统中的每一个关键组件都看出一个独立的对象（比如，一个存储节点包含 24 块硬盘，就要看出 24 个独立的对象）。对于每一个对象，根据其失效分布函数生成在时间片内的状态， 0 或者 1 。其中 0 代表失效， 1 代表正常。同类对象具有相同的失效分布式函数，不同类对象的失效分布函数可以相同也可以不同。常见的失效分布包正态分布、指数分布、 Weibull 分布等。指数分布是可靠性工程中最常用的分布，其特点是失效率为常数。

另外，需要注意的是，分布式存储本身的数据布局影响数据可靠性结果。拿 3 副本举例，假如其采取数据完全打散的布局，则不同节点上任意三块硬盘在恢复周期内同时失效都会引起数据丢失。而如果其数据布局采取部分打散状态，即把数据的 3 副本限制到特定的一组硬盘上，则不同节点上任意三块硬盘在恢复周期内同时失效未必引起数据丢失。所以，在某个时间片上判定数据是否丢失时需要考虑其数据分布策略。

以上是以 3 副本作为例子，对于 EC ，其原理和方法类似，不赘述。

由上面的描述可以看出，蒙特卡洛方法是一种非常灵活的方法。他可以根据策略模拟各种复杂情况。比如，系统中各个部件的失效函数比较复杂的情况（比如硬盘在生命周期内的浴盆曲线模拟）。

模特卡罗方法的缺点也比较明显，因为它是统计方法，所以需要较多的计算量（循环次数），才能达到比较准确的结果。

分布式系统数据可靠性估计的另一类方法是简单估计法，在下一篇文章中介绍。