1、现代计算机Modern Computer第 28 卷 第 24 期2022年12月25日文章编号:1007-1423（2022）24-0022-07DOI:10.3969/j.issn.1007-1423.2022.24.0040引言为了应对爆炸性的数据增长，如今的存储系统通常在多个地理位置部署数千个商品存储节点或服务器，以提供大规模的存储服务。这些系统通常构建在常见的组件上，这些组件更容易发生故障。软件故障、机器重启、维护停机、电源故障也可能使数据随时不可用，因此这些系统应保证数据的可靠和持久存储。为了在发生故障时保持数据的可靠性和可用性，传统的分布式存储系统通常采用冗余技术，如三副本1-2
2、。当数据量较小时，冗余方法直接有效；然而，在大型数据中心，复制带来的200%的存储开销是巨大的，无法接受。作为一种折衷方案，纠删码是一种存储高效的容错技术，可以提供相同或更高级别的可靠性，同时需要更少的数据冗余2。因此，纠删码变得越来越流行，并被包括 Microsoft3和Facebook4在内的企业广泛采用。为了响应不同的访问特性5和满足动态可靠性要求6，现代存储系统需要纠删码具备自适应功能。自适应纠删码，指的是编码参数和编解码方案随着各类要求的变化。我们认为自适应纠删码在以下场景中是至关重要的。（1）适应倾斜和动态的工作负载。实际存储系统中的工作负载是非常倾斜和动态的。倾斜意味着一小部分热
3、数据被频繁访问，而大部分冷数据很少被访问，而动态属性意味着数据热度是随时间变化的。为了兼顾高访问性能和高存储效率，实际的存储系统可以使用高冗余纠删码存储热数据以获得高性能，同时使用低冗余纠删码存储冷数据以获得低成本持久化。当数据热度变化时，执行自适应以更新编码参数或者更改编解码方案7。（2）适应不同的可靠性。不同生命周期的数据需要不同程度的可靠性，因此存储系统需要动态调整编码参数以满足不同的可靠性需求。此外，磁盘可靠性会随着磁盘的老化而变化。为了在存储开销和容错之间提供有效的权衡，大型数据中心应该弹性调整编码参数6。（3）生成宽条带。最近的工作探索了用于纠删码存储的宽条带，以抑制条带中奇偶校验
4、块的比例，从而实现极大的存储节省5。为了有分布式存储系统中自适应纠删码的研究综述陈欢华（广州软件学院网络中心，广州510990）摘要：随着海量存储系统的发展和在复杂环境中的应用，存储系统所面临数据丢失的风险也不断提升，因此存储系统中数据的可靠性受到了严重的挑战，成为了当前学术界和工业界关注的一大热点。为了解决该问题，海量数据存储系统通常使用具有低存储成本的纠删码技术。海量数据存储系统需要满足海量用户复杂多变的存储需求，以及提供高可用的存储服务，而这给海量数据存储系统中纠删码技术带来了关键性科学问题，即，纠删码的存储扩展性能较低与频繁变化的存储扩展需求之间的矛盾。为此，针对基于纠删码的海量数据存
5、储系统，围绕存储扩展和数据修复的性能开展了一个综述性的研究。首先介绍了当前典型和常见的具有自适应特性的纠删码技术的发展现状，然后从评价纠删码性能的各项重要指标的角度详细地对比和分析了现有的纠删码技术，最后指出了现有自适应纠删码的不足和可能的改进见解。关键词：分布式存储系统；纠删码；自适应；冗余转换；码转换基金项目：广州软件学院科研项目（ky202210）22陈欢华：分布式存储系统中自适应纠删码的研究综述第24期效地支持宽条带，存储系统可以为新写入的数据部署具有适度低冗余的窄条带，然后将老化的数据转换为具有极低冗余度的宽条带8。本文将通过介绍一些典型和常用的自适应纠删码来展示当前自适应纠删码研究
6、的现状，并从评价这些码的各项重要指标的角度比较和分析现有的自适应纠删码，指出当前存储系统自适应纠删码研究中尚未解决的难题以及未来可能的研究方向。1基本概念为了便于理解，通常将一个服务器称为一个节点，下面对本文出现的相关概念给出如下说明。a）数据块：编码的最小数据单元。通常，系统将用户的原始数据划分成k个数据块。b）校验块：指原始数据块经过编码运算得到的冗余块，块的大小与数据块大小相同。c）条带：指多个数据块与其对应的校验块所构成的块集合。d）辅助节点：指参与数据修复的可用节点。辅助节点读取本地数据后通过网络传输给其他节点来参与数据重建。e）机架：若干个服务器和存储设备的集合。数据服务器和同一机
7、架中的存储设备之间的访问速度非常高，而机架间的访问速度则较慢。2存储系统中的纠删码2 2.1 1基础纠删码基础纠删码2 2.1 1.1 1RSRS（ReedSolomonReedSolomon）码码9 9RS 码可用两个可配置的参数k和m构造，用 RS()k,m表示。RS()k,m将k个数据块作为输入进行编码，生成m个奇偶校验块，使得任意k+m个数据和奇偶校验块中的k个足以重建原始的k个数据块。一起编码的k+m个数据和奇偶校验块共同形成一个条带。一个实际的存储系统包含多个独立编码的条带。它将k+m个块的每个条带分布在k+m个节点上，以容忍任何m个节点故障。图 1 给出了()k,m=（4,2）的
8、RS示例。RS码的存储开销小，但其修复开销高。修复任何一个故障块，均需从其余k个可用节点中读取k个块，然后经过计算得到。它的通信开销是故障块大小的k倍。图 1RS（4，2）示例图2 2.1 1.2 2HHHH（HitchhikerHitchhiker）码码1010图 2 显示了 HH（6,3）码的示例。在HH()k,m码中，每个条带分为两个子条带（a=ai和b=bi）。每个条带中有k个数据块和m个奇偶校验块，每个块分别由a和b中的一个符号共同组成，因此每个子条带中有k个数据符号和m个奇偶符号。编码时，对同一子条带的数据进行RS()k,m编码，得到 RS 码的奇偶符号。然后，将子条带a中的k个数
9、据符号分成m-1个组，每个组中的数据符号经过按位异或得到组内的校验符号。然后，将各个组中的校验符号和子条带b经过RS编码得到的奇偶块进行按位异或，以此得到子条带b最终的校验符号。当有一个数据块故障时，HH 码可以运行快速解码过程来恢复丢失的数据块。请注意，子带b中的一个奇偶校验符号仍保留为RS奇偶校验符号。该符号仅足以恢复子条带b中丢失的一个数据符号。假设子条a中的丢失符号在对应于奇偶校验符号bk+i+1的组Gi中。在完整的子带b的帮助下，可以计算组Gi的 XOR和。这意味着可以只读取该组中的其他数据符号来恢复子条带a中丢失的符号。整个过程只需要读取k+k/(m-1)k个符号。当m 2时，有k
10、+k/(m-1)=km/(m-1)k，这意味着与普通解码过程相比，快速解码过程可以减少网络带宽和磁盘I/O的使用。23现代计算机2022年图 2HH（6,3）示例图2 2.1 1.3 3 LRCLRC(Locally Repairable CoLocally Repairable Codesdes)码码 4 4 LRC可用3个参数()k,l,g构造，意味着有k个数据块，l个本地奇偶校验块和g个全局奇偶校验块。一起编码的k+l+g个数据/奇偶校验块的集合称为条带，大型存储系统通常包含多个独立编码的条带。在LRC中，LRC 将k个数据块分成l个大小相等的组。它根据每组k/l数据块计算 XOR 和以
11、形成l个本地奇偶校验块。它还从所有k个数据块中计算g个全局奇偶校验块，计算方法同RS码。设b是编码成本地奇偶校验块的数据块的数量，即b=k/l。我们将b个数据块及其对应的本地奇偶校验块的集合称为本地组。图 3给出了(k,l,g)=(6,2,2)的LRC示例。图 3LRC（6，2，2）示例图在修复任何不可用的数据块时，LRC 检索同一本地组的其他可用块，而不是k个块，故LRC将通信开销降为故障块大小的b倍。2 2.2 2自适应纠删码自适应纠删码2.2.1HACFS7HACFS使用来自同一码系列的两种不同纠删码。即，使用具有低恢复成本的快速码和具有低存储开销的紧凑码，如图4（a）所示。它利用在 H
12、adoop 工作负载中观察到的数据访问偏差来决定数据块的初始编码。在初始编码之后，HACFS系统通过使用两种新颖的操作在快速码和紧凑码之间转换数据块来动态适应工作负载的变化。将最初用快速码编码的块升级为紧凑码，使 HACFS 系统能够减少存储开销。类似地，将数据块从紧凑码下编码为快速码，使HACFS系统降低整体恢复成本。上码和下码操作非常有效，并且只在两个码之间转换时更新相关的奇偶校验块。2 2.2 2.2 2HeARTHeART1111HeART利用异构级别的可靠性来权衡长期的存储和恢复性能。HeART的基本思想是对高风险数据采用一种恢复速度快的码，在低风险时期采用另一种存储效率高的码，如图
13、4（b）所示。（a）HACFS（b）HeART图 4HACFS和HeART方法的基本框架2 2.2 2.3 3RepairScaleRepairScale1212RepairScale考虑了两组 LRC 参数的变化，以响应工作负载的变化。具体来说，RepairScale考虑了两种 LRC 结构：快速 LRC，它存储更多本地奇偶校验块以获得更高的修复性能（例如，用于热数据），以及紧凑型 LRC，它存储更少的本地奇偶校验块以获得更高的存储效率（例如，对于冷数据）。快速和紧凑的 LRC都存储相同数量的数据块和全局奇偶校验块。执行缩放操作以在快速 LRC 和紧凑 LRC 之间切换，以平衡访问性能和存储
14、效率。从快速 LRC缩放到紧凑 LRC称为上编码，从紧凑 LRC 缩放到快速 LRC 称为下编码。因此，将上行编码成本和下行编码成本定义为分别为上行编码和下行编码传输的跨集群网络流量。图 5 描绘了(k,l,g,c)=(12,6,2,20)的快速LRC 和(k,l,g,c)=(12,2,2,16)的紧凑 LRC 的上编码和下编码。这两个码都部署在分层数据放置下（即，每个块都存储在不同的集群中，参数c指机架数）。上编码操作（从(12,6,2,20)到(12,2,2,16)）将L1和L2跨集群发送到L0以计算新的本地奇偶校验块L0，并将L4和L5跨集群发送到L3计算一个新的本地奇偶校验块L1。因此
15、，上编码成本为4。另外，下编码操作（从（12，2，24陈欢华：分布式存储系统中自适应纠删码的研究综述第24期2，16）到（12，6，2，20）将D2和D3发送到另一个集群以计算L1，并且将D4和D5发送到另一个集群以计算L2。然后它将L1和L2发送到持有L0的集群以计算L0。L3、L4和L5也是如此。总共，下编码成本为12。（a）Upcoding（b）Downcoding图 5快速LRC（12，6，2，20）和紧凑LRC（12，2，2，16）的上下编码示例2 2.2 2.4 4SRSSRS1313SRS 码建立在块到节点映射的解耦之上，通过将 RS 码的k个数据块存储在k个节点中，其中k k。
16、ERS首先计算k和k的最小公倍数LCM，即l=lcm()k,k，并将一个对象划分为l个数据块。然后将l个数据块排列成k个逻辑列，对每k个具有相同逻辑偏移量的数据块进行编码，计算出m个奇偶校验块。最后将l个数据块分布在k个节点上，使得每个节点恰好存储l/k个块，并将奇偶校验块分布在m个节点上。请注意，对于l/k个条带，奇偶校验块放在相同的m个节点上，而对于不同的条带组，则将奇偶校验块放在不同的节点上，以平衡奇偶校验更新的 I/O 开销。由于数据块现在分布在k个节点上，当对象从 RS()k,m转换到 RS()k,m时，SRS 码不需要数据块重定位，如图6所示。图 6SRS（2，1，3）示例图2 2.2 2.5 5ERSERS1414ERS 编码与SRS 编码在以下方面有所不同。首先，ERS 编码在逻辑上将l个数据块按行优先顺序分配到k个节点中，因此引入了大量重叠数据块用于冗余转换（如图7）。此外，ERS编码使用新颖的编码矩阵对每k个数据块进行编码，并根据新颖的放置策略将l个数据块物理分布在k个节点上，以增加重叠数据块的数量。因此，ERS 编码只需要少量的非重叠数据块，并且可以减少奇偶校验块
