纠删码参数自适应匹配问题ECP-AMP实验方案（中）

6.方法设计

6.1.数据获取

为了收集不同的文件大小和纠删码参数对性能指标的影响，本文在Hadoop平台上进行了模拟实验。Hadoop是一种开源的分布式存储和计算框架，它可以支持不同类型的纠删码，并提供了一些应用程序接口和工具来测试和评估纠删码的性能 。

本文选取了以下六个性能指标作为评价纠删码参数选择的依据：

1. 数据冗余度（DR）：表示存储一个文件所需的编码块总数与数据块总数的比值，反映了存储空间的利用率。数据冗余度越小，表示存储空间利用率越高。在具有k个数据块和m个奇偶校验块的存储系统中，冗余度定义为 DR=m/(k+m)。

2. 存储成本（SC）：表示存储一个文件所需的编码块总数与单位编码块价格的乘积，反映了存储费用的开销。存储成本越小，表示存储费用开销越低。在具有k个数据块和m个奇偶校验块的存储系统中，存储成本定义为 SC=（k+m）/m。

3. 传输开销（TO）：传输开销是指纠删码在读写和恢复过程中消耗的网络带宽资源，它反映了纠删码对网络负载的影响。一般来说，传输开销越低，表示网络负载越低。传输成本TO定义为恢复工作负载传输的数据块数。

4. 计算开销（CO）：计算开销是指纠删码在编码和解码过程中消耗的计算资源，它反映了纠删码对系统性能的影响。计算成本定义为GF乘法/异或算法操作数。

5. 可靠性（RE）：表示在任意m个编码块丢失或损坏的情况下，仍然可以恢复原始文件的概率，反映了数据完整性的保障。可靠性越大，表示数据完整性保障越高。
   $RE={\sum }_{i=0}^m{C}_{k+m}^i{p}^i(1-p{)}^{(k+m-i)}$

6. 恢复时间（RT）：表示从任意k个编码块中恢复原始文件所需的时间，反映了数据恢复速度的效率。恢复性能越大，表示数据恢复速度越快。恢复性能 RP 是通过对恢复工作负载进行解码的平均开销（包括计算和访问成本）来衡量的 。

本文选取了以下四个变量作为影响纠删码参数选择的因素：

1. 数据大小（filesize）：表示一个文件占用的字节数，反映了文件内容的规模。文件大小范围为0MB-1GB，每隔10MB取一个值，共有101个值。
2. 数据块个数（k）：表示一个文件被分割成的数据块的个数，反映了文件分割的粒度。数据块个数范围为2-16，每隔1取一个值，共有15个值。
3. 冗余块个数（m）：表示一个文件生成的冗余块的个数，反映了文件编码的冗余度。冗余块个数范围为1-16，每隔1取一个值，共有16个值。
4. 故障编码块个数（m’）：表示一个文件在传输或存储过程中丢失或损坏的编码块的个数，反映了文件遭受的故障程度。故障编码块个数范围为0-m，每隔1取一个值，共有M+1个值。

本文使用了Reed-Solomon纠删码，这是一种现代的软件系统中随处可见的纠删码技术。

为了模拟不同文件大小和不同纠删码参数下的各项性能指标，我们使用了Hadoop软件作为实验平台。Hadoop是一种分布式计算框架，它可以将大量的数据存储在多个节点上，并通过MapReduce模型进行并行处理。Hadoop提供了一个分布式文件系统（HDFS），它可以支持纠删码技术的存储和访问。

我们搭建了一个由32个节点组成的Hadoop集群，每个节点都具有以下配置：

• CPU：Intel Core i7-8700K @ 3.70GHz
• 内存：16GB DDR4
• 硬盘：1TB SATA
• 网络：千兆以太网

我们在每个节点上安装了以下软件：

• 操作系统：Ubuntu 18.04 LTS
• Hadoop版本：3.2.2
• PyCharm版本：17.0.8+7-b1000.8 amd64

我们使用了以下数据集作为实验对象：

• 文件大小范围：0MB-1GB
• 文件类型：文本
• 文件数量：100个

我们将这些文件上传到HDFS中，并对每个文件应用不同的纠删码参数（k,m），其中k的范围为2-16，m的范围为1-16。我们使用了RS纠删码来生成和恢复冗余块。我们修改了Hadoop提供的内置纠删码配置来完成纠删码技术的编码和解码过程。

6.2.CRITIC确定权重

为了综合考虑各项性能指标，我们使用了critic客观权重法为这些指标赋权，计算出每种情况下的综合评分。

CRITIC（CRiteria Importance Through Intercriteria Correlation）方法，旨在确定多准则决策（MCDM，MutltipleCritier Decision Making） 问题中相对重要性的客观权重。它是基于评价指标的对比强度和指标之间的冲突性来综合衡量指标的客观权重。考虑指标变异性大小的同时兼顾指标之间的相关性，并非数字越大就说明越重要，完全利用数据自身的客观属性进行科学评价。

对比强度是指同一个指标各个评价方案之间取值差距的大小，以标准差的形式来表现。标准差越大，说明波动越大，即各方案之间的取值差距越大，权重会越高；

指标之间的冲突性，用相关系数进行表示，若两个指标之间具有较强的正相关，说明其冲突性越小，权重会越低。

对于 CRITIC 法而言，在标准差一定时，指标间冲突性越小，权重也越小；冲突性越大，权重也越大；另外，当两个指标间的正相关程度越大时，（相关系数越接近 1），冲突性越小，这表明这两个指标在评价方案的优劣上反映的信息有较大的相似性。

critic客观权重法的基本思想是：

• 如果一个属性的取值变化越大，说明该属性越能反映决策对象的差异性，因此该属性的权重应该越大。
• 如果一个属性与其他属性的相关性越高，说明该属性越能反映决策对象的整体性，因此该属性的权重应该越大。

6.2.1.归一化处理

步骤一：为了消除不同性能指标的量纲和取值范围的影响，本文对收集的数据进行了归一化处理，使其取值在[0,1]之间。对于正向指标（越大越好），使用以下公式：

对于正向指标：
$x_{ij}^{\prime }=\frac{X_{ij}-min(X_{1j},X_{2j},...,X_{nj})}{max(X_{1j},X_{2j},...,X_{nj})-min(X_{1j},X_{2j},...,X_{nj})}$

对于负向指标：
$x_{ij}^{\prime }=\frac{max(X_{1j},X_{2j},...,X_{nj})-X_{ij}}{max(X_{1j},X_{2j},...,X_{nj})-min(X_{1j},X_{2j},...,X_{nj})}$

其中，x_ij是第i个文件在第j个指标上的原始值，x_ij是第i个文件在第j个指标上的标准化值。

6.2.2指标变异性

步骤二：对于每个指标，计算其差异系数，表示其差异程度。使用以下公式：

以标准差的形式来表现，S_j表示第j个指标的标准差：
$\{\begin{array}{c}\overline{x_j}=\frac{1}{n}{\sum }_{i=1}^n{x}_{ij}\\ \\ S_j=\sqrt{\frac{1}{n-1}{\sum }_{i=1}^n(x_{ij}-{\bar{x}}_j{)}^2}\end{array}$

在CRITIC法中使用指标差来表示各指标的内取值的差异波动情况，标准差越大表示该指标的数值差异越大，越能放映出更多的信息，该指标本身的评价强度也就越强，应该给该指标分配更多的权重。

6.2.3.指标冲突性

步骤三：对于每两个指标，计算其指标冲突性，表示指标间的相关性程度。使用以下公式：
$R_j={\sum }_{i=1}^p(1-r_{ij})$

以相关系数的形式来表现，r_ij表示评价指标i和j之间的相关系数。

使用相关系数来表示指标间的相关性，与其他指标的相关性越强，则该指标就与其他指标的冲突性越小，反映出相同的信息越多，所能体现的评价内容就越有重复之处，一定程度上也就削弱了该指标的评价强度，应该减少对指标分配的权重。

6.2.4.信息量

步骤四：对于每个指标，计算其信息熵权重，表示其重要程度，使用如下公式：
$C_j=S_j{\sum }_{i=1}^p(1-r_{ij})=S_j\ast R_j$

C_j越大，第j个评价指标在整个评价指标体系的作用越大，就应该给其分配更多的权重。

6.2.5.权重

步骤五：对于每个指标，计算其critic权重，表示其综合影响能力。使用以下公式：
$W_j=\frac{C_j}{{\sum }_{j=1}^p{C}_j}$

所以第j个指标的客观权重W_j

6.2.6.赋值

步骤六：对于每种情况，计算其综合评分，表示其总性能。使用以下公式：
$s_i={\sum }_{j=1}^m{v}_j\ast x_{ij}$

s_i表示第i中情况的综合评分。

得到各个指标使用critic权重法的权重，每个指标会获得一个如下的权重值。

将通过CRITIC方法得到的权重与原指标数据相乘，然后各指标相加得到一个综合指标评分goal，将每组filesize的goal数据做比较，选出最大的goal，然后将所有的filesize都依次得到，形成一张filesize,k,m,goal表，即达成目标。

6.3.DBSCAN聚类算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise），DBSCAN聚类分析是一种基于密度的无监督学习算法，它可以在不需要指定簇的数量的情况下，根据数据点的密度将它们分成不同的簇，并且可以识别出噪声点和异常值。

6.3.1.DBSCAN聚类分析算法的计算公式：

给定一个数据集D={x₁,x₂,…,x_n}，其中x_i是一个d维的向量，表示第i个数据点的特征。DBSCAN聚类分析需要两个参数：ϵ和MinPts，分别表示邻域的半径和最小密度点数。DBSCAN聚类分析的算法步骤如下：

1. 从数据集D中任意选择一个未被访问过的点x_i，标记为已访问。
2. 计算x_i的ϵ-邻域N(x_i)={x_j∈D∣d(x_i,x_j)≤ϵ}，其中d(x_i,x_j)表示x_i和x_j之间的距离。
3. 如果∣N(x_i)∣≥MinPts，则将x_i标记为核心点，并将N(x_i)中的所有未被访问过的点加入一个队列Q，表示它们属于同一个簇C。
4. 如果∣N(x_i)∣<MinPts，则将xi标记为边界点或噪声点，并转到步骤6。
5. 重复以下过程，直到队列Q为空：
   • 从队列Q中弹出一个点x_k，标记为已访问。
   • 计算x_k的ϵ-邻域N(x_k)。
   • 如果∣N(x_k)∣≥MinPts，则将x_k标记为核心点，并将N(x_k)中的所有未被访问过的点加入队列Q，表示它们属于同一个簇C。
   • 如果∣N(x_k)∣<MinPts，则将x_k标记为边界点。
6. 如果数据集D中还有未被访问过的点，转到步骤1，否则结束算法。

6.3.2.现实中部署分组

我现在有一张最佳的file,k,m的表，我已经知道了各个文件大小如何选择数据块k，冗余块m的大小，将会得到最小的存储成本和最高的数据可靠性之间的权衡，但是如果说将这张表直接给公司，让公司给每个边缘服务器都部署上

unique（（k,m））个文件配置显然是不合理的，因为每个配置文件都会生成对应的存储池，存储池的存在本身就会占用服务器的存储成本，如果在每个边缘服务器都生成unique（（k,m））个文件配置对应的存储池，那存储消耗是巨大的，不可取的，故我们给出如下方案。

如，0MB–200MB被分为一大组，即小于140MB的文件的大组文件配置为k,m=（5,3）中，每大组的文件配置按最高的k,m配置向下兼容的方法，剩余数据按类似的方法进行分组，大约分5组即可，分组不能过多，不能超越超越总存储成本。

filesize	k	m	goal
10	2	1	0.86
20	2	2	0.75
30	3	1	0.78
…	…	…	…
190	4	3	0.78
200	5	3	0.92