刘桂华

摘要：随着数据爆炸性的增加，传统的存储系统已经不能适应存储海量数据需要，而分布式系统能够可靠并且高效地存储海量数据，是存储系统的发展方向。为了解决分布式存储系统中的节点故障导致的数据失效问题，该文研究了副本冗余策略和纠删码策略两种用于数据维护的方案，结合这两种数据冗余方案各自的优点，设计了一种将两种策略结合的数据冗余策略，效果良好。

关键词：分布式存储系统；数据失效；数据维护；数据冗余

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）18-0005-02

1数据冗余策略

为解决节点失效导致数据损失这个问题，数据冗余策略被提出，冗余可以提高数据可用性和可靠性，同时也是容错的前提条件。数据冗余方案主要描述重复数据的组织形式[7，8]。数据冗余方案可以分为两类：一类是副本冗余方案，另一类是纠删码方案。

1.1副本冗余策略

分布式存储系统中，冗余副本技术是一种最常用的分布式数据管理机制[9]。副本冗余方案也称为数据复制方案，是指将系统中的各个数据块复制为多份并保存在不同的地方。这样当某个节点失效导致存储在该节点上的数据不可用时，仍然可以访问存储在别处的数据块来获取相应的信息。副本的数目越多，整个系统越可靠，但是副本数量的增加势必增加额外的系统资源消耗如存储空间[10]，比如一个原始数据块的大小是1GB，采用数据复制方案，每个数据块复制k份，那么存储系统就需要消耗k GB的存储空间。一般的存储系统很难支撑如此大的存储开支。副本冗余策略简单易用，因此应用广泛。但是其消耗存储空间过大的缺点限制了其的使用。当前对副本冗余方案的研究主要在如何实现各个副本一致性方面。

1.2纠删码策略

纠删码是另一种重要的数据冗余方案。纠删码方案的基本思想是，首先将原始数据分为k份，然后在对k份数据进行编码，得到另外n-k份数据，然后将总共为n份的数据发给不同的节点。在这n份数据中，只要其中任意的k份数据，就可以解析出原始数据。

从纠删码基本的形态来看，它是k个数据块加上m个校验块的结构，其中数据和校验的k和m值都能够按照一定的规则设定。在1～m个数据块（无论数据或校验块）损坏的情况下，整体数据仍然可以通过剩余数据块上的数据进行解析，得到整体数据，从而使整体数据不会丢失，存储系统仍然可以使用。也就是说一定数量的节点失效并不会造成用户数据的丢失[12]。

从数学的角度上，可以描述为：将文件F看作（F1，F2，.....Fk）的一个集合，ai（ai1，ai2，...，aik）是一个由n个线性无关的向量组成的向量组，令

Ci=ai1*F1+ai2*F2+...+aik*Fk

用A表示aij（1<=i<=n，1<=j<=k），则有

A*F=C，即公式（1）：

其中C就是编码后的冗余数据集合，其中的m=n-k个数据块为冗余数据。只要C中剩余的数据块大于等于k个，即使损失了一部分数据块，那么通过剩下的数据块仍然可以恢复出原文件。令C中丢失了ci行，则在A中删除对应的ai行，得到A1，由于A中的向量线性无关，所以A1可逆，解析过程如公式（2）。

纠删码具有随意k份文件就能解析出原文件的特性，在分布式存储系统中，纠删码的功能主要有两个，分别是数据重构和数据维护。数据重构是对冗余数据进行解码，从而获得原始数据。数据维护是对失效的数据进行修复。

纠删码是一种保护存储系统中数据的一种机制，能够容忍系统内一定存储节点的失效而不影响系统数据的完整性。采用纠删码方案的存储系统有一定的容错能力，但是当失效的数据块达到一定的数量时，数据将无法恢复。因此系统需要及时地对失效的数据进行恢复。传统的纠删码维护方案是先恢复原始数据，再通过对原始数据的线性组合得到失效的冗余数据。因此，每一个数据块的失效，就需要下载k份数据块进行恢复，那么系统的维护通信开销就将非常巨大，对某些低速网络而言，这种开销可能是无法容忍的。纠删码机制虽然能够节省存储开销，但造成了读数据性能的下降[13]，在使用纠删码维护策略的系统中会经常出现用户访问延迟的现象。

1.3副本冗余策略和纠删码策略的比较

从图1可以看出，数据复制策略把原始数据复制为3份，分配到不同的节点中，当其中任意两个节点失效时，可以从别的存储节点获取响应的数据。而纠删码策略则在原始数据的基础上编码出不同的数据块，在图1的纠删码策略中，任意两个节点失效时，系统也可以根据其他两个节点的数据还原出原始数据。

由图1可知，在同等可靠性的情况下，相比副本方案，纠删码方案将极大地减少数据的存储空间。尤其是在大量数据时，采用纠删码策略所节省的存储空间是很可观的。但是，存储系统需要花费极大开销对失效的数据进行及时修复，而采用副本冗余策略的存储系统在修复时所需要的资源远远小于采用纠删码策略的存储系统。两种策略都有各自的优缺点，副本冗余策略需要更多的存储空间，而纠删码策略需要更大的通信维护量和计算量。如何解决这两种策略所存在的问题，成立当下的难点。

2 改进数据冗余策略方案

2.1副本冗余与纠删码结合策略

原始数据中并不是所有数据被访问的可能性都是相同的，实际情况中往往大部分的访问都集中在一部分数据中，称这部分数据为热门数据，而其余的数据被访问的机会则比较少，称此部分数据为冷门数据。热门数据所在的存储节点会因为频繁地被访问而更加容易失效，而冷门数据所在的存储节点失效的概率则相对小很多。

结合前文中提到的问题，本文结合副本冗余策略和纠删码策略的优势，提出了一种副本与纠删码结合的策略。基本思想是首先将原始数据进行分组，将其中的热门数据块使用副本策略进行存储，即将它们复制为多份并分配到各个节点上；同时，将其中的冷门数据块进行编码，以纠删码的方式进行存储。本策略的工作示意如图2。

2.2数据热度的判断方法

在实际的应用中，各数据块的被访问次数，即数据的热度，与预期值会有差别，并且会随时间变化。本策略设计了判断数据热度的算法，监测各个数据块的热度，如果数据块的实际热度与预期不符合，就对其进行转换。

热度监测的实现方法：选取时间段T为一个周期，在Tn+1时刻对之前的n个周期各个数据块的被访问次数作统计，若是发现某些热门数据的访问量很少或是某些冷门数据的访问量很多，则对热门数据和冷门数据作必要的变换。这种方法缺点是只从n个周期的访问热度角度考虑而忽略了最近时间的访问热度，不够全面。比如有某个数据块，在前（n-3）个周期内都没有被访问，但在最近3个周期内访问次数突然增多，从总体上判断应归为冷门数据，但实际上该数据块并不算冷门数据。针对这个问题，本策略除了对前n个周期的被访问次数进行统计外，还对各数据块最近三个周期的被访问次数进行统计，最后将两者进行加权平均，将结果视为判断是否为热门数据的依据。本策略将前n个周期和最近三个周期的权值比设为4：6。例如某个数据块在前n个周期被访问20次，最近三个周期被访问10次，则可以将m=20*0.4+10*0.6=14作为该数据块的热度。此外，频繁地对热门数据或冷门数据进行转换也会对系统造成极大的开销，因此所得到的结果如果现状差别不是很大，不作调整。

与纠删码策略相比，本策略的优点有：1）由于热门数据采用副本策略，用户可以从多个地方获得所需数据，因此很大程度上解决了用户访问数据延迟的问题。2）当热门数据失效时，系统可以找到相应的副本，然后直接进行复制恢复。不用下载k个数据块进行解析，极大地节省了网络资源和CPU资源；与副本冗余策略相比，本策略避免了为冷门资源分配大量存储空间的情况，使得存储空间的利用率得到很大的提升。

本策略比副本冗余策略更节省存储空间，比纠删码冗余策略则消耗更少的通信维护量和计算量。在实际应用中做到了资源更充分更有效率的利用，取得了比两者都更令人满意的效果。

3总结与展望

本文在仔细研究了副本冗余策略和纠删码策略的基础上，结合了副本冗余策略和纠删码策略的优点，提出了两者相结合的数据冗余策略，并给出了判断数据热度的算法。解决了其他冗余存储系统中的存储量大，通信维护量大，计算量重等问题，为数据冗余策略提供了很有意义的参考。

与此同时，本文所提出的策略还存在一些不足，比如所采用的纠删码算法还可以继续优化，判断数据热度的算法也存在改进的空间。在未来的研究中，将针对这些不足之处作进一步的改进。

参考文献：

[1]王禹.分布式存储系统中的数据冗余与维护技术研究[D].华南理工大学，2011.

[2]黄震.大规模分布式存储系统中数据冗余技术研究[D].国防科学技术大学，2012.