[paper] I/O-Efficient Scaling Schemes for Distributed Storage Systems with CRS Codes

摘要:

具有CRS代码的分布式存储系统的I / O有效扩展方案

Abstract

由于数据量的爆炸性增长,系统扩展对于分布式存储系统而言必不可少。考虑到大型分布式存储系统中必须有故障保护功能,并且广泛采用柯西·里德-所罗门(Cauchy Reed-Solomon)代码来容忍多个同时发生的节点故障,因此本文研究了使用CRS代码的分布式存储系统的扩展性问题。特别地,我们用优化模型来表示缩放问题,在该模型中,假定缩放后编码矩阵和数据迁移策略都事先未知。为了最大程度地减少I / O开销,我们为CRS代码提出了一个三相优化缩放方案。具体来说,我们首先根据给定的数据迁移策略得出最优的后缩放编码矩阵,然后使用选定的后缩放编码矩阵优化数据迁移过程,最后利用最大距离可分离性(MDS)属性进一步优化设计的数据迁移过程。我们的扩展方案要求最小的数据移动,同时实现均匀的数据分发。而且,与传统的最小数据迁移方案相比,它需要读取更少的数据块,但仍保证了最小量的迁移数据。为了验证我们方案的效率,我们在网络文件系统上实现了该方案。大量实验表明,我们的缩放方案比基本方案使用更少的缩放时间。

Introduction

通常在现代存储系统中部署擦除代码以提供容错能力。 擦除代码相对于复制的优势在于,它们可以在具有相同数量的冗余的情况下实现更高的可靠性,或者为满足相同的可靠性要求而需要较少的冗余。 由于分布式系统中有时会同时发生多个并发节点故障,因此Cauchy Reed-Solomon(CRS)代码旨在承受任意数量的并发节点故障,并且已在学术项目和商业系统中广泛部署。另一方面,需要存储的数据在持续增多,存储系统对于对于存储能力和IO性能有着持续增长的需求,所以就需要经常向存储系统中增加新的设备来提高存储能力和IO性能。因此,容错和存储扩展就成为了目前存储系统中最重要的两个问题

本文研究了CRS编码存储系统中的扩展问题。 容错存储系统的系统扩展可被视为存储系统之上的应用程序。 为了完成扩展过程,必须在旧设备和新添加的设备之间重新平衡原始数据。 此外,在具有冗余机制的存储系统中,还必须相应地更新关联的奇偶校验。 因此,扩展分布式存储系统不可避免地会导致磁盘使用和网络消耗。 现代存储系统已广泛部署在网络资源十分匮乏的多云和数据中心服务中。 因此,执行系统扩展的一个重要目标是最小化I / O和网络传输的数量,以实现快速扩展并允许对前台用户任务进行更灵活的调度。

RAID扩展的方法很多,旨在在扩展过程中最小化迁移的数据量。 在本文的后续部分中,缩放方案称为最小数据迁移方案。 例如,FastScale 旨在最小化RAID-0扩展的迁移I / O。 MiPiL 将最少数量的数据块从旧设备移至新设备,以进行RAID-5扩展。 SDM 根据将来针对各种RAID-6代码的奇偶校验布局,将数据迁移流量最小化。 但是,由于特殊的编码机制,这些方法都不能有效地应用于CRS代码。 有关CRS缩放和常规缩放方法之间差异的更多详细信息,请参见第3节。

为了解决由于CRS代码带来的缩放挑战,我们使用优化模型来制定CRS缩放比例,在该优化模型中,缩放后的编码矩阵和数据迁移策略都应该事先未知。因此,要优化CRS缩放过程,我们必须设计缩放后编码矩阵和数据迁移策略。注意,Jerasure库[9]为编码性能得到优化的CRS代码提供了编码矩阵。因此,通常从Jerasure生成用于实际部署的CRS代码的编码矩阵。对于CRS缩放方案,将给出预缩放编码矩阵,并且可以从Jerasure生成该矩阵。但是,如果缩放后编码矩阵也从Jerasure导出,则I / O开销和网络带宽流量可能会很大。为了解决这一挑战,我们尝试通过三个步骤来最大程度地减少CRS缩放的I / O和网络传输量:(i)我们首先通过朴素的数据迁移,根据预缩放矩阵设计缩放后编码矩阵方案(ii),然后使用选定的后缩放编码矩阵优化数据迁移过程;(iii)最后将最大距离可分离(MDS)属性应用于设计的数据迁移过程,以进一步优化迁移I / Os。本文的主要贡献如下。

  • 我们将CRS代码的缩放过程公式化为由后缩放编码矩阵和数据迁移策略组成的优化模型。基于此模型,我们提出了一种针对CRS代码的三相优化缩放方案。
  • 我们提出了一种有效的方法来设计后缩放编码矩阵,该矩阵优化了CRS缩放的I / O开销和网络流量。
  • 我们提出一种搜索算法来设计有效的在线数据迁移方案,从而进一步降低CRS扩展的I / O成本。
  • 我们开发了一种新方案,与现有的最小数据迁移方案相比,可以进一步减少对数据块的读取,同时仍可以使用奇偶校验块对所需的数据块进行解码,从而确保迁移的数据量最少。通过这种方案,可以进一步降低CRS缩放的I / O成本。
  • 我们在实际的网络文件系统之上实施缩放方案,并通过广泛的评估证明,在实际的系统设置下,我们的缩放方案比过渡方案减少了缩放时间。

Background On CRS Code

首先来看CRS编码的背景。一个使用CRS的存储系统可以被表示成三元组(k, m, w)。存储系统由n = k + m个磁盘组成,其中k个磁盘保存数据块,剩余的m个磁盘存储奇偶校验块。CRS代码类具有所需的属性,即系统可以容忍n个磁盘故障中的任何m个,并且此属性称为“最大距离可分离”属性。 每个磁盘都分成固定大小的条带。 每个条带存储w个数据块或奇偶校验块。 编码在条带内执行。 对于实际部署,数据和奇偶校验磁盘的标识跨不同的条带旋转以减轻可能出现的热点,因为奇偶校验磁盘通常比数据磁盘更多地被访问。

一个CRS编码可以通过一个nw×kw的编码矩阵来表示。它首先通过m × k的柯西矩阵构造一个n × k的分布式编码矩阵。令X = {x0, …, xm-1},Y = {y0, … yk-1},柯西矩阵的第i行第j列的元素为1/(xi + yj)。分布矩阵由前k行的单位矩阵和后m行的柯西矩阵组成。 该算法在GF(2w)上执行,其中加法是简单的按位异或(XOR),而乘法则更复杂,通常使用乘法表或离散对数表来实现