英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

不规则部分重复编码在异构云存储中的优化

摘要—本文针对异构云存储系统提出了一个灵活的不规则模型，并研究了如何将修复故障节点的成本降至最低。部分重复编码最初是为同类存储系统的最小化修复带宽而设计的，现在被推广到不规则部分重复编码，它适用于异构环境。码结构和相关的存储分配可以通过求解整数线性规划问题来获得。对于中等规模的网络，提出了一种启发式算法，并通过计算机仿真表明该算法接近最优。

索引术语—云存储、分布式存储系统、不规则部分重复编码、再生码

I .导言

云存储是一种新的数据存储模式。它允许用户随时随地访问数据。像谷歌和苹果这样的公司通过他们的联网数据中心提供这项服务。这种体系结构被称为分布式存储系统(DSS)。分布式存储系统中的存储节点通常不可靠，容易出现故障。当出现故障时，新来者需要通过从幸存的存储节点中检索数据来修复丢失的数据(称为帮助节点)，从而保持分布式存储系统的可靠性。此外，分布式存储系统应该能够提供数据可用性，使用户能够在任何地方以低延迟访问他们的数据。

为了提供可靠性和可用性，通常使用复制编码或里德-所罗门(RS)码等纠删码。虽然在节点修复期间复制需要较少的网络带宽，但就存储空间而言，RS码更高效。2007年，迪马科斯等人指出，在存储空间和修复带宽之间有一个根本性的权衡[1]。权衡曲线上的点可以通过一类称为再生码的码来实现，这类码基于网络编码的概念。在他们的公式中，新来者能够通过连接到任何幸存的存储节点来恢复丢失的数据，并且数据收集器能够通过以下方式来检索数据对象：从n个存储节点中的任意k个节点下载数据。我们称这种分布式存储模型为常规模型。从那时起，许多实现折衷曲线上的点的码已经被构造(例如，[2]、[3]、[4]、[5]）。

再生码的设计原理是最小化修复带宽。然而，这些码在修复期间通常会导致高磁盘输入/输出访问，因为帮助节点需要读取其存储的数据，并将其线性组合以形成新的数据包发送给新来者。需要读取的存储数据通常比发送给新来者的数据要多得多。因此，磁盘访问带宽成为系统瓶颈。在[6]中，修复问题被以不同的方式考虑。它旨在当节点故障的数量小于MDS码的容错能力时，最小化要访问的信息量。文献[7]考虑了另一种方法。它提出了一种新的码，由一个外部最大距离可分码和一个内部部分重复(FR)码连接而成。我们称之为MDS-FR码。该码是最小带宽再生(MBR)码，这意味着它最小化了系统的修复带宽。此外，它还有很好的未编码修复属性:助手节点只需要读取它需要转发给新来者的确切数据量，而无需任何处理。换句话说，它同时最小化了修复带宽和磁盘访问带宽。虽然[7]中的FR码的原始构造是基于正则图和斯坦纳系统，但是也存在基于二分图[8]、随机算法[9]、可分解设计[10]和关联矩阵[11]的其他构造。请注意，上面提到的作品并不严格遵循常规模型，因为它们有不同的设计考虑。另一个值得注意的例子是局部修复码[12]，[13]，[14]，其目的是减少修复期间需要联系的节点数量。

本文主要研究异构分布式存储系统。例子包括异构数据中心、对等云存储系统(如太空猴)[15]、对等辅助云存储系统和一些有线或无线缓存系统[16]、[17]。在这些应用中，存储节点和网络链路是异构的，这意味着与不同存储节点相关联的存储容量和成本可能不相同，并且每对存储节点之间的通信链路在带宽、通信成本和传输速率方面可能具有不同的特性。此外，一些存储节点也可能没有直接连接。在这样的环境中，新的问题出现了。在研究[18]中，存储分配问题，重点是如何在存储节点上分配给定的存储预算，以便成功恢复的概率最大化，在。在[19]中考虑了存储节点具有不同下载成本的分布式存储系统。在具有存储成本的分布式存储系统中，如何在存储节点之间分配存储容量以使总存储成本最小化在[20]中进行了研究。在[21]中，考虑了带宽异构性，以证明树形结构再生拓扑是减少再生时间的有效拓扑。在功能修复模型下，链路成本和网络拓扑的影响在[22]中被共同考虑，而信息论研究在[23]中被执行。

为了解决异构云存储系统的设计问题，我们建立了一个灵活的模型，称为不规则模型，其中底层网络的拓扑结构可以是任意的，允许不同存储节点的存储容量和成本不同，并且通信链路的带宽和成本不必相同。通过引入修复覆盖和检索集的概念，放松了常规模型中数据修复和数据检索的限制。我们使用术语修复覆盖来指用于数据修复的覆盖网络的结构。请注意，它在[7]中被称为修复表。在[7]的工作中，对于单个故障情况，修复覆盖被限制为每个顶点具有度d的规则图，并且该图是随机生成的。在本文中，我们不限制修复覆盖图是一个正则图。对于多重故障的一般情况，文献[7]中的维修覆盖层是斯坦纳系统。然而，施泰纳系统的存在要求系统参数满足某些特定条件，这使得系统设计缺乏灵活性。本文用超图来模拟修复覆盖层，它存在于任意系统参数下，与Steiner系统相比易于构造。

回想一下，文献[7]中使用的码是外部MDS码和内部FR码的级联。我们称这种结构为MDS-FR码。我们扩展了这个概念，并使用不规则分数重复(IFR)码作为内部码。虽然它保留了理想的未修复编码特性，但它进一步允许系统设计中更大的灵活性。当分布式存储系统和底层网络是异构的时，可以通过解决优化问题来构造IFR码并使其适应给定的环境，从而进一步减少修复带宽。在我们的公式中，我们通过正确选择MDS-IFR码来最小化系统修复成本。这个问题被证明是一个整数线性规划问题。当存储节点数量较少时，可以在合理的时间内找到最佳解决方案。对于较大的网络，我们将问题分解为子问题，并提出启发式解决方案。对于较小的网络规模，我们的启发式算法通过与最优ILP方法进行比较，显示出接近最优。

本文的其余部分组织如下。第二节给出了一个例子。第三节陈述了我们的分布式存储系统的不规则模型。在第四节中，我们描述了MDS-IFR码的构造及其与中继覆盖概念的关系。在第五节中，我们将维修成本最小化问题表述为整数线性问题。在第六节中，我们描述了如何找到码的存储修复折衷。在第七节中，我们设计启发式算法来寻找次优修复覆盖和检索集。第八节提供了我们的模拟结果。我们在第九节结束了论文。

二.动机范例

常规模型假设新来者能够通过联系任何d个幸存的存储节点来替换故障存储节点，并且数据收集器能够通过从n个存储节点中的任意k个节点下载数据来检索存储的数据对象。然而，在某些实际情况下，新成员和每个幸存的存储节点之间的通信成本是不同的。此外，数据收集器和n个存储节点中的每一个之间的距离和传输速率随着数据收集器的位置而变化。新来者要联系的d个幸存节点和数据收集器要联系的k个存储节点不必是任意的。为新来者确定一些辅助节点集(称为辅助节点集)和为数据收集器确定n个存储节点的一些子集(称为检索集)是合理的。所有n个存储节点的帮助集集合定义了修复覆盖。因此，我们基于修复覆盖和检索集的概念修改数据修复和数据检索机制。我们只要求新来者可以通过联系其任何一个助手集中的存储节点来重建相应的故障节点，并且数据收集器可以通过联系任何一个检索集中的存储节点来检索数据对象。

考虑一个分布式存储系统，它可以容忍具有以下参数的单个故障:n = 6，d = k = 2。由四个数据包组成的数据对象将存储在这个分布式存储系统中。对于常规模型，功能修复下的存储量和修复带宽之间的相应折衷在图1中示出，其中可行区域被示为阴影区域。请注意，权衡曲线上的所有点都是通过数据对象中包含的数据包数量来标准化的。折衷曲线以下的点不可能通过功能修复来实现。显然，它们也不能通过精确修复来实现。

现在我们考虑不规则模型，它包括修复覆盖和检索集的概念。我们要求检索集的数量足够大。在这个例子中，我们要求至少有9个检索集。假设所选择的修复覆盖图，用tau;表示，是一个有六个节点的环，如图2(a)(实线)所示。我们展示了如何基于修复覆盖来构造MDS-FR码。由四个分组组成的数据对象首先被编码成六个分组，F₁，F₂，...，F₆通过一个(6，4)-MDS码。然后，6节点环中的每条边都与一个编码包相关联。如图2(a)所示，每个节点存储与其入射边相关联的两个分组。因此，六个存储节点中的每一个的存储量是2。在此示例中，每个存储节点都有一个辅助集，新来者可以通过连接到其辅助集中的d = 2个节点(即环中的两个相邻节点)而不是任何d = 2个幸存节点来恢复丢失的数据。由于每个新加入者从其两个辅助节点中的每一个下载一个数据包来恢复丢失的数据，所以故障节点的修复带宽为2。假设节点3失败。

图1.存储量和修复带宽之间的权衡(n = 6，d = 2，k = 2)

1. (b)

(c) (d)

图2.为不规则模型构造MDS-FR码和MDS-IFR码的示例

新来者可以通过分别从其两个辅助节点2和4下载编码分组F₂和F₃来替换它，如图2(b)所示。至于数据检索，我们可以有九个基数k = 2的检索集，它们被列为R₁ = {1，3},R₂ = {1，4},R₃ = {1，5},R₄ = {2，4},R₅ = {2，5},R₆ = {2，6},R₇ = {3，5},R₈ = {3，6}和R₉ = {4，6}。数据收集器可以通过连接到九个检索集中的任意一个中的k = 2个存储节点来重建数据对象。在按原始数据对象的包的数量归一化之后，每个存储节点的存储量是0.5，并且每个故障节点的修复带宽也是0.5。这一点也绘制在图1中，它低于常规模型的折衷曲线。从图1中，我们可以看到，在每个节点的存储量相同的情况下，修复带宽减少了50%，这表明如果放松数据修复和数据检索的限制，潜在的增益可能是巨大的。

在不规则模型中，允许不同的存储节点具有不同的存储成本，并且允许不同的链路具有不同的通信成本。在图2(c)中给出了具有存储成本和通信成本的不规则模型，其中节点i具有(每分组)存储成本s_i，并且连接节点i和节点j的链路具有(每分组)通信成本c_ij。对于FR码和IFR码，我们假设分配给边{i，j} isin; tau;的包的数量是beta;_ij，并且存储在节点i中的包的数量是alpha;_i。然后，总存储成本可以被获得为P_i=1 alpha;_is_i，并且所有可能的单个节点故障的总修复成本可以被计算为P_i=1 P {i,j}isin;tau; c_ijbeta;_ij。如果我们使用与之前相同的MDS-FR码，则六个存储节点的总存储成本是2 P_i=1 s_i = 34，因为每个节点存储2个分组，并且所有可能的单个节点故障的总修复成本可以计算为(c₁₂ c₁₆) (c₁₂ c₂₃) (c₂₃ c₃₄) (c₃₄ c₄₅) (c₄₅ c₅₆) (c₅₆ c₁₆)= 36，其中求和的六个分量分别对应于节点1到节点6的修复成本。如果我们使用MDS-IFR码，我们首先使用(7，4)-MDS码将数据对象编码成七个数据包。

然后，我们将编码数据包F₁分配给边{1，2}，F₂分配给边{2，3}，F₃分配给边{3，4}，F₄、F₅和F₆分配给边{5，6}，F₇分配给边{1，6}。如图2(d)所示，每个节点然后存储与其入射边相关联的分组。在本例中，新来者可以通过仅连接到一个节点或两个节点来恢复丢失的数据，具体取决于哪个节点出现故障。这与MDS-FR码形成了对比，在MDS-FR码中，新成员总是连接到正好是d的节点。例如，如果节点4失败，新来者可以通过从节点3下载包F₃来替换它。至于数据检索，我们可以有十个基数为k = 2的检索集，它们被列为R₁ = {1，3},R₂ = {1，5},R₃ = {1，6},R₄ = {2，5},R₅ = {2，6},R₆ = {3，5},R₇ = {3，6},R₈ = {4，5},R₉ = {4，6}和R₁₀ = {5，6}。六个节点的总存储成本是2s₁ 2s₂ 2s₃ s₄ 3s₅ 4s₆ = 33，并且所有可能的单个节点故障的总修复成本可以计算为(c₁₂ c₁₆) (c₁₂ c₂₃) (c₂₃ c₃₄) c₃₄ 3c₅₆ (3c₅₆ c₁₆)= 22，其中总和的六个分量分别对应于节点1到节点6的修复成本。通过与MDS-FR编码的比

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[237186]，资料为PDF文档或Word文档，PDF文档可免费转换为Word