重复数据消除存储系统的迁移问题研究

ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月内容、来源和目的：重复数据消除系统ROEI KISOUS和ARIEL KOLIKANT，以色列理工学院计算机科学系ABHINAV DUGGAL，Dell EMC，美国SARAI SHEINVALD，ORT Braude工程学院，以色列GALA YADGAR，以色列理工学院计算机科学系通过引用重复的数据块的唯一副本来替换重复的数据块，从而减小存储在大规模存储系统中的数据的大小这会在包含类似内容的文件之间创建依赖关系，并使系统中的数据管理在本文中，我们将解决数据迁移的问题，即由于系统扩展或维护而导致文件在不同卷之间重新映射对于没有重复数据消除的系统，确定要迁移哪些文件和数据块的挑战已得到广泛研究。但是，在重复数据消除存储环境中，只考虑了简化的迁移方案。在这篇文章中，我们制定了一般的迁移问题，重复数据删除系统作为一个优化问题，其目标是最大限度地减少系统的大小，同时确保存储负载均匀分布在系统的卷和迁移所需的网络流量不超过其分配。然后，我们提出了三种算法生成有效的迁移计划，每一个基于不同的ap-proach和代表一个不同的权衡计算时间和迁移效率。我们的贪婪算法提供了适度的空间节省，但由于其非常短的运行时间而具有吸引力其结果可以通过使用更大的系统表示来改进我们的理论上最优的算法制定的整数线性规划（ILP）的情况下的迁移问题它的迁移计划始终导致更小和更平衡的系统比贪婪的方法，虽然它的运行时间很长，因此，理论上的最佳选择并不总是被发现。我们的聚类算法享有最好的两个世界：其迁移计划是由基于ILP的算法生成的，但它的运行时间更短，有时由一个数量级它可以进一步加速，其结果的质量成本CCS概念：·信息系统→存储管理;分布式存储;其他关键词和短语：数据迁移、数据迁移、容量规划这项研究得到了以色列科学基金会的支持（批准号：807/20）。作者Kisous，A.Kolikant和G.Yadgar，Technion计算机科学系，Technioncampus.technion.ac.il计算机科学A. Duggal，Dell EMC，USA;电子邮件：abhinav. dell.com; S.Sheinvald，ORT Braude工程学院，ORT Braude工程学院，卡米尔，以色列，2161002;电子邮件：sarai. sheinvald@gmail.com。允许制作本作品的全部或部分数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知和完整的引用版权的组成部分，这项工作所拥有的其他人比ACM必须尊重。允许用信用进行提取 复制，或重新发布，张贴在服务器上或重新分发到列表，需要事先特定的许可和/或费用。从permissions@acm.org请求权限。© 2022计算机协会1553-3077/2022/11-ART31 $15.00https://doi.org/10.1145/356502531ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月三十一：2R. Kisous等人ACM参考格式：Roei Kisous，Ariel Kolikant，Abhinav Duggal，Sarai Sheinvald，and Gala Yadgar.2022年TheWhat，TheFrom，and TheTo：The Migration Games in Deduplicated Systems（什么、从哪里来、到哪里去：重复数据消除系统中的迁移游戏）ACM Trans. 存储18，4，第31条（2022年11月），29页。https://doi.org/10.1145/35650251介绍许多大规模存储系统采用数据去重来减小它们存储的数据的大小重复数据消除过程会识别不同文件中的重复数据块，并使用指向系统中存储的数据块的唯一副本的指针替换它们。这种系统尺寸的减小是以增加系统复杂性为代价的。 虽然许多学术研究和商业系统已经解决了重复数据消除存储系统中读取、写入和删除数据的复杂性，但大型系统的高级管理方面，例如容量规划、缓存以及服务质量和成本，仍然需要适应重复数据消除存储[48]。本文重点介绍数据迁移方面，即在不同的重复数据消除域或卷之间重新映射文件。卷可以表示大规模系统中的单个服务器，也可以表示专用于客户或数据集的一组独立服务器由于卷达到其容量限制或系统中形成其他瓶颈，文件可能会被重新映射由于文件之间的数据依赖关系，在选择要迁移的文件时，NTFS引入了新的注意事项：迁移文件时，可能会从其原始卷中删除其中的一些块，而其他块可能仍然属于保留在该卷上的文件。类似地，一些块需要被传输到目标卷，而其他块可能已经存储在那里。有效的迁移计划必须优化几个可能相互冲突的目标：迁移后存储数据的物理大小;系统卷之间的负载平衡，即存储在每个卷上的数据的物理大小;以及迁移本身产生的网络带宽。最近的几项研究解决了重复数据消除系统中数据迁移的特定（简化）情况tems. Harnik等人 [30]解决容量估计问题，并提出了一种用于减小系统大小的贪婪算法。Rangoli[45]是一种用于空间回收的贪婪算法，其中删除一组文件以回收系统的一些容量。GoSeed[43，44]是一种基于整数线性规划（ILP）的 虽然即使是播种问题也被证明是NP难的[43]，但这些研究都没有解决完整数据迁移问题中涉及的冲突目标-最小化系统大小，最小化迁移期间消耗的网络流量和最大化系统中卷之间的负载平衡之间的权衡。在本文中，我们将首次讨论数据迁移的一般情况我们首先以最一般的形式将数据迁移问题公式化，作为一个优化问题，其主要目标是最小化系统的整体大小我们添加了流量和负载平衡考虑作为迁移计划的约束这些约束的执行程度直接影响解决方案空间，从而允许系统管理员对不同的成本进行因此，去重系统中的数据迁移问题映射到在由管理员指定的流量和负载平衡约束内找到要迁移什么、从哪里迁移以及迁移到哪里。然后，我们介绍了三种新的算法生成一个有效的迁移计划。第一个是受[30]中的贪婪迭代过程启发的贪婪算法我们的扩展算法在卷之间均匀分布数据，同时确保迁移流量不会内容、来源和目的：重复数据消除系统中的迁移游戏三十一：3ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月超过最大分配。 通过将此过程分为几个阶段，我们确保分配的流量用于负载平衡和容量减少，在两个可能冲突的目标之间进行平衡。我们的第二个算法的灵感来自于GoSeed基于ILP的方法GoSeed解决了种子问题，其唯一的自然最小化目标是系统大小。相比之下，我们的新算法解决了一般迁移的固有竞争目标（大小，平衡，流量） 我们重新制定的ILP问题的变量和约束条件，表达迁移过程中使用的流量和选择的卷从重新映射文件或重新映射文件到。我们对一般迁移问题的表述自然比播种所需的复杂得多尽管如此，我们还是成功地将其应用于具有数亿块的系统中的数据迁移。我们的第三个算法是基于层次聚类，据我们所知，还没有被应用到重复数据我们将类似的文件分组到集群中，集群的目标数量是系统中卷的数量我们将文件的物理位置纳入到聚类过程中，这样文件之间的相似性表示它们共享的块以及它们的初始位置。 群集根据其上已存储的块分配给卷，迁移计划将每个文件重新映射到分配给其群集的卷。我们实现了我们的三个算法，并在从三个公共数据集创建的六个系统快照上对其进行了评估[6，10，41]。我们的研究结果表明，所有的算法可以成功地减少系统每种算法都有不同的优点：贪婪算法在最短的运行时间（通常是几秒钟）内生成迁移计划，尽管它在系统大小上的减少通常低于其他算法。基于ILP的方法可以有效地利用允许的流量消耗，并随着负载平衡约束的放松而改善然而，它的执行必须在大型问题实例上超时，这通常会阻止它产生最佳迁移计划。 聚类算法的经验达到可比的结果，基于ILP的方法，有时甚至超过他们。它可以在更短的运行时内完成此任务我们总结我们的主要贡献如下。我们将具有重复数据删除的一般迁移问题公式化为优化问题（第3节），并设计和实现了用于生成一般迁移计划的三种算法：贪婪（第4节）和基于ILP（第5节）的方法受到先前研究的启发，而基于聚类（第6节）的方法是全新的。我们在方法上比较我们的算法，以分析每种方法的优点和局限性（第7节）。这篇文章扩展了这项工作的早期出版物，在第20届USENIX文件和存储技术会议（FAST 22）[33]的会议记录中，我们的方法有更多的细节和分析我们所有算法的实现都是开源的，可以在线获得[8]。2背景和相关工作重复数据删除。简而言之，重复数据删除过程将传入数据拆分为固定或可变大小的块，我们称之为块。每个块的内容被哈希以创建指纹，该指纹用于识别重复块并从存储中检索其唯一副本。必须优化此过程的几个方面，以免影响存储系统性能。这些包括分块和指纹[13，39，42，54，55]，索引和查找[14，49，58]，块的有效存储[19，21，34，36，37，49，56]，以及快速文件重建[26，32，35，57]。虽然第一个商业系统使用重复数据删除来备份和归档数据，但重复数据删除现在通常用于高端主存储[11，12]。三十一：4R. Kisous等人ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月图1. 初始系统（a）和备选迁移计划：具有最佳负载平衡（b）、最佳流量（c）和最佳删除（d）。系统中的所有块的大小都为1。分布式重复数据删除系统中的数据迁移在商业和学术研究中引入了许多分布式重复数据删除设计[20，24，29]。我们专注于在每个物理服务器中采用单独指纹索引的设计[17，18，22，23，30]。这种设计选择保持了较小的索引大小和较低的查找成本，便于在服务器级别进行垃圾收集，并简化了客户端逻辑。在此设计中，每个服务器（卷）都是一个单独的重复数据删除域，也就是说，仅在同一卷内识别重复数据块因此，映射到特定卷的文件的配方指向物理存储在该卷中的块重复数据消除系统与传统分布式系统的不同之处在于，即使使用基于内容的分块算法完成重复数据消除，跨卷分条文件也可能会减少重复数据消除。跨集群拆分文件也会使垃圾收集复杂化。此外，许多存储系统（例如，在DataDomain [25]和IBM [30]中）被组织为数据中心或跨数据中心的独立存储集群或“岛”的集合在每个独立的子系统中执行迁移;但是，文件可能会在不同的应用程序之间迁移作为重新平衡整个系统利用率的一种手段例如，如果一个子系统已满，而另一个子系统具有可用容量，则迁移比向已满的子系统添加容量更快且更便宜现有机制通过仅传输文件的元数据和目标子系统中不存在的块来有效地迁移文件 每月迁移与典型备份客户的平均保留期一致。逻辑文件的位置和其块的物理位置的耦合意味着当文件从其卷重新映射时，我们必须确保其所有块都存储在新卷中。同时，文件例如，考虑图1（a）中描述的初始系统，并假设我们将文件F2从卷V2重映射到卷V1，从而得到图1（b）中的替代系统块B1从V2中删除，因为它已经存储在V1中.块B2从V2中删除，但必须复制到V1，因为它在初始系统中不存在块B3也必须复制到V1，但不从V2中删除，因为它也属于F3。最初的系统和这个替代方案的总规模是相同的：九个街区。现有办法。 Harnik等人[30]提出了一种贪婪迭代算法，用于减少具有多个卷的系统中的数据总容量。在每次迭代中，一个文件被重新映射到新卷，并且该过程继续，直到总容量减少预定的删除目标。内容、来源和目的：重复数据消除系统中的迁移游戏三十一：5ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月GoSeed [43，44]解决了一种称为种子的简化数据迁移情况，其中初始系统由映射到单个卷的许多文件组成迁移的目标是通过将文件重新映射到空的目标卷来删除该卷的一 GoSeed将播种问题表述为ILP实例，其解决方案确定哪些文件被重新映射，哪些块从源卷移动到目标卷，以及哪些块被复制以在两个卷上创建副本。 这种方法是可能的存在的开源[4，5，9]和商业[2，3]ILP求解器基于算法的软件工具，有效地解决这个NP难问题。 GoSeed应用于具有数百万个块的实例，具有几种加速算法，其中一些我们适用于广义问题。Rangoli[45]是一种用于空间回收的贪婪算法-数据迁移的另一种特定情况，其中选择一组文件进行删除，以便删除系统物理大小的一部分。与启发我们自己的算法的贪婪和基于ILP的方法不同，Rangoli解决的问题过于简化，无法扩展到一般的迁移。Shilane等人[48]讨论其他数据迁移方案及其在已消除重复数据的系统中产生的复杂性。3动机和问题陈述最大限度地减少迁移流量。高性能存储系统通常会限制其网络带宽中可用于维护任务的部分，例如从故障存储节点重建数据[31，47]。数据迁移自然涉及大量的网络带宽消耗;传统的数据迁移计划和机制努力将其网络需求最小化作为其优化目标之一[15，16，25，38，40，52]。在这项工作中，我们专注于节点之间移动的数据量。节点的物理布局和迁移的精确调度超出了我们当前工作的范围。在重复数据消除存储中，我们区分了与数据迁移相关的两种成本迁移流量是指在迁移过程中在卷之间传输的数据量复制成本是由于将文件重新映射到新卷而创建的重复数据块的总大小 以前的重复数据消除系统中的数据迁移研究没有明确考虑带宽。Harnik等人[30]根本没有提到这一点在GoSeed [43]提出的播种问题中，由于最小化复制成本，迁移流量被隐式地最小化。然而，在一般情况下，迁移流量可能与数据复制量无关。例如，图1（b）中的备选方案1导致在卷之间传输两个块B2和B3，即使B2最终从其源卷中删除相反，图1（c）中的替代迁移计划根本不消耗流量：文件F1被重新映射到V2，V2已经存储了它唯一的块;因此，B1可以简单地从V1中删除。这一备选方案还将系统的大小减少到8个区块，使其在两个目标方面都优于第一备选方案。然而，我们注意到，情况并非总是如此，最小化整个系统的大小和最小化传输的数据量可能是相互冲突的目标。负载平衡。 负载平衡是分布式存储系统的主要目标，它经常与其他目标（如利用率和管理开销）发生冲突[16，46，53]。分布式重复数据删除在最小化总物理数据大小和最大化负载平衡之间引入了固有的权衡：当所有文件都映射到单个卷时，系统的大小最小化，这显然提供了最差的负载平衡。因此，分布式去重系统权衡将文件映射到包含类似文件的卷的益处与在卷之间均匀分布负载的 需要 。 负 载平 衡 可以指负 载的各种度量， 例如每秒输入/输出操作 数（IOPS）、带宽要求或映射到每个卷的文件数。三十一：6R. Kisous等人ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月∈⊆∈∈∈≥≥|| |||| ||⊆ × ×∈{}{}我们遵循以前的工作，目标是在卷之间均匀分配容量负载[18，22]。平衡容量在经过重复数据消除的系统中尤为重要，因为这些系统会将传入文件路由到已包含类似文件的卷。在这样的设计中，存储占用率略高于其他卷的卷可能会由于其更大量的数据“吸引”更多的新文件而迅速过载，等等。 容量负载平衡可以提高网络利用率，并防止特定卷成为瓶颈或耗尽其容量。虽然性能负载平衡不是我们的主要目标，但我们希望通过分配容量来提高我们所有的方法都可以扩展到明确地解决它。在这项工作中，我们使用平衡度量来捕获系统中的负载平衡，这类似于常用的公平性度量[27]-系统中最小卷的大小与最大卷的大小例如，图1（a）中初始系统的平衡是V1/V2=1/5。备选方案1（图1（b））是完全平衡的，平衡=1，而备选方案2（图1（c））的平衡最差：V1/V2=0。问题陈述。在复杂的优化系统中，有各种方法处理相互冲突的目标。这些包括搜索帕累托边界[59]或定义加权个体目标的复合目标函数。我们选择将系统的大小作为主要目标，并将迁移流量和负载平衡作为迁移计划的约束。 我们通过扩展[43]中的播种问题来定义一般迁移问题;因此，为了兼容性，我们重用了他们的一些符号。对于具有一组卷V的存储系统S，设B = b0，b1，. 是存储在系统中的唯一块的集合，并且令size（b）是块b的大小。设F=f0，f1，.，是S中的文件的集合，并且令ISB F V是包含关系，其中（b，f，v）IS意味着文件f被映射到卷V的块包含存储在该卷中的块B我们用bv来表示对于某个文件f，（b，f，v）IS。卷的大小是存储在其中的块的总大小，也就是说，大小（v）=10bv大小（b）。系统的大小是其体积的总大小，即大小（S）=大小（V）=大小（V）。一般的迁移问题是找到一组要迁移的文件FMF、每个文件要迁移到的卷、可以从每个卷删除的块以及应该复制到每个卷的块。应用迁移计划导致新系统SJ。迁移的目标是最小化S j的大小。 这相当于最大化迁移期间可以删除的所有数据块的大小减去必须复制的所有数据块的大小。流量约束指定Tmax-迁移期间允许的最大流量。 它要求添加到卷中的块的总大小不大于Tmax。负载平衡约束决定了容量在卷之间的分布有多均匀。它指定了一个余量0≤μ 1，并要求新系统中每个卷的大小在平均卷大小的μ范围内< 量系统|V|这就相当于要求所有的balance[（尺寸e（SJ）/|V|）×（1−μ）]/[（size（SJ）/|V|）×（1+μ）]，或simply，balance（1−μ）/（1+μ）。例如，对于图1（a）中的初始系统，备选方案1（图1（b））是唯一满足负载平衡约束（对于任何μ）的迁移计划当Tmax低于2/9时，不可能发生迁移 另一方面，如果我们去除负载平衡约束，则最佳迁移计划仅取决于流量约束：例如，备选方案2（图1（c））对于Tmax= 0是最佳的，备选方案3（图1（d））对于Tmax= 3是最佳的。精炼。这个一般化的问题可以用几种简单的方法来细化。例如，我们可以限制可以包括在FM中的文件集、可以从中删除文件的卷集或可以将文件重新映射到的卷集。类似地，我们可以要求从系统中删除一个特定的卷（强制其所有文件被重新映射），或者添加一个空卷我们在评估中展示了其中的一些案例内容、来源和目的：重复数据消除系统中的迁移游戏三十一：7ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月算法1：函数BestRemap（源，目标，流量）1 foreachfilein sourcedo2Ratio=重新映射到tarдet时的空间节省率3T迭代=如果重新映射到tarдet，则传输的块的总大小4端5 使用最低比率和（T迭代流量）<4贪婪Harnik等人的基本贪婪算法[30]迭代每个卷中的所有文件，并计算将单个文件重新映射到每个其他卷的空间节省率：将被复制的块的总大小与将从文件的原始卷中删除的块的总大小之间的比率。在每次迭代中，将重新映射具有最低比率的文件例如，如果将这种基本贪婪算法应用于图1（a）中的初始系统，则它将首先将文件F1重新映射到卷V2，空间节省率为0，从而产生备选方案2（图1（c））。当总容量减少了预定的删除目标时，该过程停止这种算法并不直接适用于一般的迁移问题，因为它没有考虑流量和负载平衡。解决交通限制相对简单。在我们的扩展贪婪算法中，我们将其作为停止条件：当没有文件可以在不超过最大分配流量的情况下重新映射时，迭代停止。 算法1给出了在考虑流量约束的情况下选择要重新映射的文件的伪代码。一个小的挑战是，一个文件可能会在算法的几次迭代中被重新映射，而在最终的迁移计划中，它只会从其原始卷重新映射到其最终目的地。因此，所有单个迭代的流量总和可能（并且实际上）高于执行迁移计划时所需的流量这不会违反流量约束，但会导致算法在利用最大允许流量之前停止因此，我们明确地允许算法使用比原始流量约束多20%的流量，以防止它过早停止在执行迁移计划之前，计算所产生的迁移计划所需的流量因此，如果它违反了原来的交通约束，一个新的计划可以生成的算法没有这种启发式。在我们的评估中，我们包括这个简单的扩展，没有负载平衡约束遵守负载平衡约束更具挑战性。例如，如果基本贪婪算法到达替代方案2（图1（c）），它不能再重新映射任何单个文件到vol-10.0.1，而不增加系统因此，系统将保持不平衡，至少有一个空体积。对该算法的简单扩展可以通过防止文件被重新映射来加强负载平衡约束，如果这增加了系统然而，这种严格的要求可能会排除太多的优化机会例如，对于图1（a）中的初始系统，它将允许将文件F2仅重映射到卷V1，从而导致备选方案1（图1（b））。系统将是完美平衡的，但基本算法将终止，而不会减少其规模。我们用两种主要技术来应对这一挑战 第一种是定义两种迭代类型：一种的目标是平衡系统的负载，另一种的目标是减小其大小。 我们交替执行这些迭代，以避免整个分配的流量仅用于一个目标。 第二种技术是放松早期迭代的负载平衡裕度，并不断收紧它，直到执行结束。这个想法是让早期的迭代更自由地重新映射文件，并确保算法结束时的迭代产生一个平衡的系统。三十一：8R. Kisous等人ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月×≤×≤（）图2. 我们的扩展贪婪算法的概述算法2：GreedyWithLoadBalancing（volumes[]，Tmax，μ，phases）1 Remainin <$= Tmax 1。22 p=13而p相不4T相位=剩余相位/（剩余相位）5μ相位= μ×（1. 5 −2×p）阶段6负载平衡步骤（体积、T相、μ相）7T阶段-=负载平衡步骤中使用的流量8CapacityReductionStep（体积、T相、μ相）9Remainin <$-=阶段中使用的流量10p++11端部图2说明了我们的扩展贪婪算法的过程我们将算法的过程分为几个 1每个阶段都被分配了分配给迁移的流量的偶数部分，并且受到本地负载平衡约束的限制。每个阶段由两个步骤组成2负载平衡步骤迭代地将文件从大卷重新映射到小卷，直到卷大小在为该阶段定义的余量内或其流量耗尽。3容量减少步骤使用剩余的流量来减少系统算法2是我们算法的主要结构每个阶段都受到本地流量和负载平衡约束的限制，这些约束是在阶段开始时计算的阶段流量（T阶段）决定了每个阶段可以使用的最大流量，并且对于所有阶段大致相等。 局部相位裕度（μ相位）确定每个相位中允许的最小和最大体积尺寸。它在第一阶段大于全局裕度μ，并且在每个阶段之前逐渐减小，直到在最后阶段达到μ默认情况下，我们的贪婪算法由p = 5个阶段组成。相位i的相位业务，0 i 0且Large > 1且某些体积违反μ相位时，4个从最小到最大的分拣卷5BestRemap（卷[大]， 体积[小]，剩余<$）6如果没有重新映射，则7小++8如果小==大则9小=1，Larдe-=110端部其他11个12Remainin <$-= BestRemap13端部14的端算法4：CapacityReductionStep（体积，T步，μ相位）1 剩余量<$=T阶跃2whileRemaining> 0do3foreach（target，source）in volumesdo4记录BestRemapBalance（源、目标、剩余、μ相）5端6重新映射所有对中的最佳选项7Remainin <$-= BestRemapBalance使用的流量8如果没有重新映射，则中断;9端部算法5：BestRemapBalance（源、目标、流量、余量）1Leдal=（当前系统大小）/（卷数）2 foreachfilein sourcedo3Ratio=重新映射到tarдet时的空间节省率4T迭代=传输块的总大小5平衡=6（重新映射后的大小（源）>Leдal marдin）和7（重新映射Leдal+marдin后的大小（tarдet））端89 返回具有最低Ratio的文件，其中（T迭代流量）和（Balanced=True）<约束反映在算法5中给出的用于选择要重新映射的最佳文件的不同例程的使用中。注意，容量减少步骤中剩余的业务量取决于初始系统中的不平衡程度 在高度不平衡系统的最极端情况下，负载平衡步骤可能消耗分配给该阶段的所有流量。在这种情况下，容量减少步骤在第一次迭代中停止 对于这种极端情况以外的情况，更高数量的阶段可以转移更多的流量，以减少容量，但由于迭代次数增加，计算时间会更长。三十一：R. Kisous等人ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月∈∈≤。≤∈ ≤ −∈{1}|∈∧∈}∈ ≤∈∈ ∈ ∈ ∈≥(10)联系我们F StBSTbv∈ {}.∈≤5ILP我们基于ILP的方法受到GoSeed [43，44]的启发，专为种子问题设计，其中文件只能从源卷重新映射到空目标卷。GoSeed因此定义了三种类型的变量，其赋值指定（1）文件是否被重映射，(2) 是否在两个卷上复制数据块，以及（3）是否从源删除数据块并将其移动到目标。这些有限的选项导致了一组相当简单的约束，不能直接应用于一般的迁移问题。主要区别在于，我们是否可以从其源卷中删除块的决定不仅取决于最初映射到该卷的文件，还取决于迁移后将重新映射到该卷的文件因此，在我们基于ILP的方法中，每个块传输都被建模为创建该块的副本，并且单独决定是否从其源卷中删除该块问题的约束是在第2节中问题陈述中的 我们将每个卷v的目标大小定义为wv，表示为迁移后系统大小的百分比。默认情况下，wv=1/|V|. 对于每对体积v，u，我们将它们的交集定义为存储在两个体积上的块的集合：交集vu=b b u b v。在指定约束之前计算交点，并在下面的公式中使用以提高可读性。约束用表示在迁移中执行的动作的三种类型的变量来表示：xfst表示文件f是否从其源卷s重新映射到另一个（目标）卷t。cBST表示块B是否从其源卷S复制到另一个（目标）卷T。最后，dbv表示是否从卷v中删除块b。ILP实例的解决方案是将0或1赋值给这些变量。生成的迁移计划重新映射xfst= 1的文件集（对于某个卷t），将cbst= 1的块转移到它们的目标卷，并从它们各自的卷中删除dbv= 1的块。限制和目标。负载平衡迁移的ILP公式由13种约束类型组成。(1) 所有变量都是布尔值：x，c，d0，1。(2) 一个文件最多可以重映射到一个卷：对于卷s中的每个文件f，tVxfst1。(3) 一个块只能从它最初存储的卷中删除或复制：对于每两个卷s，t;如果bgs，则cbst=dbs=0。(4) 只有当包含一个块的所有文件都被重新映射到其他卷时，才能从卷中删除该块：对于每个卷s和每个文件f，使得f s，dbstxfst。(5) 只有当没有包含它的文件被重新映射到这个卷时，才能从卷中删除一个块：对于每两个卷s，t，每个文件f使得f s和f g t，每个块b使得（b，f，s）IS，dbt1 xfst。(6) 将 体积 块 交点 中 的所 有 块视 为 已复 制 ：对 于 每两 个 体积 块 s 、 t和 每个 块b ，Intersectst、cist=1。(7) 当一个文件被重新映射时，它的所有块要么被复制到目标卷，要么最初就在那里（作为交集的一部分）：对于每两个卷s，t和每个块b和文件f，例如（b，f，s）IS，xfstvVcbvt。(8) 一个块只能从一个源卷复制到目标卷：对于每个块b和体积t，s，使得bg与stcbst相交1.(9) 如果卷上没有包含块的文件，则必须删除该块：对于每两个卷s，v和所有文件fs，fvv和所有块b，其中b fs和b fv，dbs1fs（1vxfssv）+fv（xfvvs）。如果没有文件将在目标卷中包含块，则无法将该块复制到目标卷：对于每个卷，t和每个块bgt，则cbst≤s<$f∈s<$b∈fxfst.内容、来源和目的：重复数据消除系统中的迁移游戏三十一：ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月...×≤∈∈（13）–...||× |||| ||| | | || | ||||迁移后：大小（SJ）=v∈VSize（vJ）..b∈v（1 −dbv）×Size（b）+.S.∈V，.bgIntersetsvcbsv×Size（b）. Size（SJ）是系统的大小(11) 文件不能迁移到其初始卷：对于每个文件f和卷v，xfvv=0。(12) 流量限制：所有复制块的大小不大于允许的最大流量：s Vt VbgIntersectstcbstsize（b） Tmax.负载平衡约束：对于每个卷v，（wvμ） Size（S J） Size（vJ） （wv+ μ） Size（S J），其中Size（vJ）是迁移后的卷大小，即，其未删除的块和复制到它的块的总和：Size（vJ）=► 目标：最大化删除的所有块减去复制的所有块的大小之和。这相当于最小化整个系统的大小：Max（b ∈ BSize（b）×s ∈ V [dbs −t ∈ V，bgIntersectstcBST]）。约束12和13制定了流量和负载平衡目标。约束8、9和10确保求解器不会创建块的冗余副本以人为地遵守负载平衡约束。 这类似于防止种子问题中的孤儿块的约束[43，44]。出于评估的目的，我们还将参考没有负载平衡约束的问题的放松形式在该版本中，删除了约束8、9、10和13，大大降低了问题的复杂性。本文中给出的ILP公式是为数据迁移的最一般情况而设计的，在这种情况下，任何文件都可以重新映射到任何卷。实际上，迁移目标可能会限制某些重映射选项，从而可能简化ILP实例。例如，我们可以通过删除xfst和cbst变量来限制文件可以迁移到的卷集，其中t不在此集中。 我们可以类似地限制可以迁移的卷文件集，或者要求重新映射（或不重新映射）一组特定文件。复杂性和运行时间。ILP实例的复杂性取决于B、F和V-分别是数据块、文件和卷的数量。变量的数量为V2F+V2B+V B，对应于变量类型xfst、cbst和dbv。 定义在这些变量上的每个约束都贡献了类似的数量级。一个例外是约束13，它两次重新制定系统大小，以确保每个单独卷的大小在所需的余量内。事实上，没有这个约束的放松公式比完整公式简单得多。我们使用GoSeed建议的两种加速方法来解决ILP问题的高复杂性。第一个是指纹采样，其中该问题是解决了原始系统的块的子集。 这个子集（样本）是通过预处理块指纹并仅包括那些匹配预定义模式的块指纹而生成的。具体地说，如[30]中所建议的，以采样度k生成的样本仅包括其指纹由k个前导零组成的块，从而将问题公式中的块的数量平均减少1/2k。如果文件足够大，示例将包含与原始系统相同的文件集因此，实际系统中的迁移决策遵循为示例中的每个文件所做的决策 我们将在第7节讨论小文件的影响。第二种加速方法是求解器超时，它在预定的运行时间后停止ILP求解器结果，服务器返回一个不一定是最优的可行解ILP问题的可行解决方案可以直接转化为迁移计划，即要迁移的文件及其目标卷的列表因此，即使解决方案不是最优的（由于采样或超时），该过程仍然为原始系统产生有效的计划。我们不重复这些药物有效性的详细分析，这些药物在早期的研究中被证明是有效也就是说，对GoSeed的分析表明，求解器的大部分三十一：R. Kisous等人ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月−{}{}{}表1. 具有四个区块的小系统，指示它们是否根据采样规则块指纹k=1K=2kJ=1kJ=2B1b2b3b401110101001101100111010010110101✓✓✓✗✗✓✗✗✗✓✓✗✗✗✓✗k是基本采样规则中的前导零的数量，内部样本中尾随零的数量太多），并且只要采样度不高于k=13，减小样本大小比在较大样本上运行求解器更长时间更有效我们用扩展的ILP制剂进行的实验证实了这些发现，为了简洁起见省略了这些实验内部取样。 我们介绍了一种新的加速方法，具体到一般的迁移问题。如前所述（并在我们的评估中证明），负载平衡约束显著增加了问题的复杂性 这种复杂性可以通过仅在系统块的子集上定义来降低，但代价是降低了准确性。 回想一下，ILP问题是在原始系统的样本上定义的。 我们创建了一个更小的样本，在这个样本上定义了负载平衡约束。度为kJ的内部采样创建系统的样本，该样本仅包括具有k个前导零和kJ个尾随零的块我们选择对指纹的最低有效位进行采样，以确保该采样独立于生成初始系统快照的采样表1示出了具有四个块（B = b1、b2、b3、b4）的玩具系统及其指纹，以及它们是否包括在初始和内部系统快照中。例如，在初始采样度k = 1和内部采样度KJ= 1的情况下，系统由块Bk=1，KJ=1 = b2，b3组成。在该示例中，将为块Bk=1=b1、b2、b3定义所有约束，但是块b1将不包括在负载平衡约束中在定义此约束时，仅考虑Bk=1，kJ=1中的块，用于计算迁移前后的系统大小及其卷内部抽样可能成为一把双刃剑。尽管线性约束的大小显著减小，但它们的数量保持不变。此外，负载平衡约束变得因此，当求解程序超时时返回的部分解决方案可能更好。但是，搜索最佳解决方案可能需要更长的时间，可能导致服务器在找到它之前超时 我们在第7.4节的评价中证明了这些影响。6聚类概况. 聚类是一种众所周知的基于相似性对对象进行分组的技术[1]。它快速、有效，并且直接适用于我们的领域：如果文件共享其大部分块，则它们是相似的。因此，我们的方法是创建类似文件的集群，并将每个集群分配到一个卷，重新映射那些分配到与其原始位置不同的卷的文件。尽管它的简单性，三个主要的挑战（第1章 第3章）涉及在应用这个想法的一般迁移问题。（第1章）不可预测的交通。 只有在将群集分配给卷后，才能计算迁移计划所需的流量。在进行聚类决策时，它们对整体流量的影响是未知的，因此不能考虑在内。内容、来源和目的：重复数据消除系统中的迁移游戏三十一：ACM Transactions on Storage，Vol.号184、第三十一条。出版日期：2022年11月{}{}{}（Ch 2）不可预测的系统大小。负载平衡约束是根据迁移后系统的大小给出的。但是，需要使用此大小来确保在群集过程中创建的群集在允许的大小范围内。（3）灵敏度高。 文件相似性度量基于每个文件中的精确块集。当此度量应用于存储系统指纹的样本我们通过以下几种方法来应对这些挑战（H1− H4）：（H 1）交通量。 我们定义了一个新的相似性度量文件。此度量是文件内容相似性与新距离度量的加权和，该距离度量