提高数据去重系统可扩展性的容错编码方法、装置及系统

摘要

本发明公开了一种提高数据去重系统可扩展性的容错编码方法、装置及系统，属于计算机存储领域，包括：在数据去重系统中新增Δk个节点时，将每k+Δk个具有局部性关联的容器划分为一个关联容器组，并将编码方式从RS(k,m)扩展为RS(k+Δk,m)；对于每一个关联容器组G，将其中的Δk个容器中的共Δk×k个数据块均匀地迁移到新增节点中；对于关联容器组G中每一个未迁移的容器C，从每一个新增节点中选取一个数据块与容器C中的数据块组合，按照RS(k+Δk,m)计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′并存储到节点中，由组合得到的k+Δk个数据块及校验块PC1′～PCm′构成一个新的条带；从节点中删除中各容器的旧校验块。本发明能够有效提高数据去重系统的可扩展性。

权利要求

1.一种提高数据去重系统可扩展性的容错编码方法，所述数据去重系统中，每个容器由k个数据块组成，并且每个容器中的k个数据块按照RS(k,m)编码方式编码后产生m个校验块；每个容器中的k个数据块及编码产生的m个校验块构成一个条带，且分别存储在不同的k+m个节点上；其特征在于，所述提高数据去重系统可扩展性的容错编码方法包括：在所述数据去重系统中新增Δk个节点时，将每k+Δk个具有局部性关联的容器划分为一个关联容器组，并将编码方式从RS(k,m)扩展为RS(k+Δk,m)；

对于每一个关联容器组G，选取其中的Δk个容器作为待迁移容器，将待迁移容器中的共Δk×k个数据块均匀地迁移到Δk个新增节点中；对于所述关联容器组G中每一个未迁移的容器C，从每一个新增节点中选取一个数据块与所述容器C中的数据块组合，得到k+Δk个数据块，按照扩展之后的编码方式计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′，并将校验块PC1′～PCm′存储到节点中，由组合得到的k+Δk个数据块及校验块PC1′～PCm′构成一个新的条带；从节点中删除所述关联容器组G中各容器的旧校验块；

其中，k、Δk和m均为正整数；RS(k,m)和RS(k+Δk,m)均为纠删码编码方式，RS(k,m)对k个数据块编码产生m个校验块，RS(k+Δk,m)对k+Δk个数据块编码产生m个校验块。

2.如权利要求1所述的提高数据去重系统可扩展性的容错编码方法，其特征在于，对于所述关联容器组G，选取待迁移容器的方式为：按照碎片化程度从高到低的顺序对所述关联容器组G中的容器进行排序；

将排序结果中碎片化程度最高的前Δk个容器作为待迁移容器。

3.如权利要求2所述的提高数据去重系统可扩展性的容错编码方法，其特征在于，容器中数据块所关联的文件数量越多，该容器的碎片化程度越高。

4.如权利要求1所述的提高数据去重系统可扩展性的容错编码方法，其特征在于，划分关联容器组的方式为：

对于每一个容器，获得其中各数据块所关联的文件id，并将其中占比最高的文件id作为该容器的关联性id；

将关联性id相同的容器作为具有局部性关联的容器；

将每k+Δk个具有局部性关联的容器划分为一个关联容器组。

5.如权利要求1所述的提高数据去重系统可扩展性的容错编码方法，其特征在于，按照扩展之后的编码方式计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′，包括：分别获得编码方式在扩展前、后对应的编码矩阵，通过矩阵变换得到校验块PC1′～PCm′与容器C的旧校验块PC1～PCm以及迁移的数据块之间的关系f；

读取节点中存储的容器C的旧校验块PC1～PCm以及相应的迁移的数据块，将所读取的数据块按照所述关系f计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′。

6.如权利要求1‑5任一项所述的提高数据去重系统可扩展性的容错编码方法，其特征在于，还包括：

在系统扩展完成后，发生降级读时，定位失效数据块所属的条带，并从该条带中读取k+Δk个未失效的编码块，按照扩展之后的编码方式对所读取的编码块进行解码操作，修复出失效数据块；

其中，编码块为条带中的数据块或校验块。

7.一种提高数据去重系统可扩展性的容错编码装置，所述数据去重系统中，每个容器由k个数据块组成，并且每个容器中的k个数据块按照RS(k,m)编码方式编码后产生m个校验块；每个容器中的k个数据块及编码产生的m个校验块构成一个条带，且分别存储在不同的k+m个节点上；其特征在于，所述提高数据去重系统可扩展性的容错编码装置包括：关联容器组划分模块、数据块迁移模块、扩展编码模块以及垃圾回收模块；

所述关联容器组划分模块，用于在所述数据去重系统中新增Δk个节点时，将每k+Δk个具有局部性关联的容器划分为一个关联容器组，并将编码方式从RS(k,m)扩展为RS(k+Δk,m)；

所述数据块迁移模块，用于对于每一个关联容器组G，选取其中的Δk个容器作为待迁移容器，将待迁移容器中的共Δk×k个数据块均匀地迁移到Δk个新增节点中；

所述扩展编码模块，用于对于所述关联容器组G中每一个未迁移的容器C，从每一个新增节点中选取一个数据块与所述容器C中的数据块组合，得到k+Δk个数据块，按照扩展之后的编码方式计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′，并将校验块PC1′～PCm′存储到节点中，由组合得到的k+Δk个数据块及校验块PC1′～PCm′构成一个新的条带；

所述垃圾回收模块，用于从节点中删除所述关联容器组G中各容器的旧校验块；

其中，k、Δk和m均为正整数；RS(k,m)和RS(k+Δk,m)均为纠删码编码方式，RS(k,m)对k个数据块编码产生m个校验块，RS(k+Δk,m)对k+Δk个数据块编码产生m个校验块。

8.一种数据去重系统，所述数据去重系统中，每个容器由k个数据块组成，并且每个容器中的k个数据块按照RS(k,m)编码方式编码后产生m个校验块；每个容器中的k个数据块及编码产生的m个校验块构成一个条带，且分别存储在不同的k+m个节点上；其特征在于，所述数据去重系统包括权利要求7所述的提高数据去重系统可扩展性的容错编码装置。

说明书

提高数据去重系统可扩展性的容错编码方法、装置及系统

技术领域

[0001] 本发明属于计算机存储领域，更具体地，涉及一种提高数据去重系统可扩展性的容错编码方法、装置及系统。

背景技术

[0002] 随着云计算与大数据等技术飞速发展，全球各类存储数据量的爆炸增长，这使得现代数据中心同时面临两个严峻的挑战，降低存储成本和提高数据的可靠性。对于存储成
本的问题，目前业界常见的解决方法是通过数据去重的方法降低数据冗余，减少存储开销，
具体地，它首先将备份文件流划分为一组固定大小或变化大小的数据块，将可变长度数据
块打包成固定大小的容器，然后利用哈希算法计算每个块的指纹以唯一地表示该块。如果
新的块指纹与指纹数据库中的指纹之一相同，则认为它是重复的。只有非冗余块存储在磁
盘中，将其指纹存储在指纹数据库中。数据去重可以有效降低数据冗余，但是减少数据冗余
带来的问题是数据的可靠性进一步下降，纠删码因其良好的存储效率和高可靠性，常常被
应用于去重系统，来提高去重系统可靠性。

[0003] 目前，围绕去重系统中的容器这一数据结构有两种引入纠删码的方式。一类是容器间编码，即把容器作为编码数据块进行编码；另一类是容器内编码，即把容器作为编码条
带，划分为大小相同的编码块在进行编码。这两类编码分别在存储利用率、降级读性能和弹
性机制上作了权衡，其中容器内编码在牺牲了扩展性能的条件下，存储利用率和降级读性
能均有较大幅度提升。然而，随着传统数据中心向云存储的迁移，云数据中心正在成为新的
核心，到2025年，全球存储数据的49％将驻留在公有云环境中。对于云环境来说，随着存储
规模的改变自由伸缩集群的灵活弹性机制是其重要特性，而目前已有的去重系统的容错编
码均难以做到兼顾高可用和高可扩展性。

[0004] 因此如何保证容器内编码的降级读性能及存储开销，并在不破坏去重系统局部性特征的情况下，提升系统的可扩展性，即随着存储规模的改变自由伸缩集群，是十分有意义
的。

发明内容

[0005] 针对现有技术的缺陷和改进需求，本发明提供了一种提高数据去重系统可扩展性的容错编码方法、装置及系统，其目的在于，提高数据去重系统的可扩展性。

[0006] 为实现上述目的，按照本发明的一个方面，提供了一种提高数据去重系统可扩展性的容错编码方法，数据去重系统中，每个容器由k个数据块组成，并且每个容器中的k个数
据块按照RS(k,m)编码方式编码后产生m个校验块；每个容器中的k个数据块及编码产生的m
个校验块构成一个条带，且分别存储在不同的k+m个节点上；该提高数据去重系统中可扩展
性的容错编码方法包括：

[0007] 在数据去重系统中新增Δk个节点时，将每k+Δk个具有局部性关联的容器划分为一个关联容器组，并将编码方式从RS(k,m)扩展为RS(k+Δk,m)；

[0008] 对于每一个关联容器组G，选取其中的Δk个容器作为待迁移容器，将待迁移容器中的共Δk×k个数据块均匀地迁移到Δk个新增节点中；对于关联容器组G中每一个未迁移
的容器C，从每一个新增节点中选取一个数据块与容器C中的数据块组合，得到k+Δk个数据
块，按照扩展之后的编码方式计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′，并
将校验块PC1′～PCm′存储到节点中，由组合得到的k+Δk个数据块及校验块PC1′～PCm′构成一
个新的条带；从节点中删除关联容器组G中各容器的旧校验块；

[0009] 其中，k、Δk和m均为正整数；RS(k,m)和RS(k+Δk,m)均为纠删码编码方式，RS(k,m)对k个数据块编码产生m个校验块，RS(k+Δk,m)对k+Δk个数据块编码产生m个校验块。

[0010] 进一步地，对于关联容器组G，选取待迁移容器的方式为：

[0011] 按照碎片化程度从高到低的顺序对关联容器组G中的容器进行排序；

[0012] 将排序结果中碎片化程度最高的前Δk个容器作为待迁移容器。

[0013] 进一步地，容器中数据块所关联的文件数量越多，该容器的碎片化程度越高。

[0014] 进一步地，划分关联容器组的方式为：

[0015] 对于每一个容器，获得其中各数据块所关联的文件id，并将其中占比最高的文件id作为该容器的关联性id；

[0016] 将关联性id相同的容器作为具有局部性关联的容器；

[0017] 将每k+Δk个具有局部性关联的容器划分为一个关联容器组。

[0018] 进一步地，按照扩展之后的编码方式计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′，包括：

[0019] 分别获得编码方式在扩展前、后对应的编码矩阵，通过矩阵变换得到校验块PC1′～PCm′与容器C的旧校验块PC1～PCm以及迁移的数据块之间的关系f；

[0020] 读取节点中存储的容器C的旧校验块PC1～PCm以及相应的迁移的数据块，将所读取的数据块按照关系f计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′。

[0021] 进一步地，本发明提供的提高数据去重系统可扩展性的容错编码系统，还包括：

[0022] 在系统扩展完成后，发生降级读时，定位失效数据块所属的条带，并从该条带中读取k+Δk个未失效的编码块，按照扩展之后的编码方式对所读取的编码块进行解码操作，修
复出失效数据块；

[0023] 其中，编码块为条带中的数据块或校验块。

[0024] 按照本发明的另一个方面，提供了一种提高数据去重系统可扩展性的容错编码装置，数据去重系统中，每个容器由k个数据块组成，并且每个容器中的k个数据块按照RS(k,
m)编码方式编码后产生m个校验块；每个容器中的k个数据块及编码产生的m个校验块构成
一个条带，且分别存储在不同的k+m个节点上；该提高数据去重系统中可扩展性的容错编码
装置包括：关联容器组划分模块、数据块迁移模块、扩展编码模块以及垃圾回收模块；

[0025] 关联容器组划分模块，用于在数据去重系统中新增Δk个节点时，将每k+Δk个具有局部性关联的容器划分为一个关联容器组，并将编码方式从RS(k,m)扩展为RS(k+Δk,
m)；

[0026] 数据块迁移模块，用于对于每一个关联容器组G，选取其中的Δk个容器作为待迁移容器，将待迁移容器中的共Δk×k个数据块均匀地迁移到Δk个新增节点中；

[0027] 扩展编码模块，用于对于关联容器组G中每一个未迁移的容器C，从每一个新增节点中选取一个数据块与容器C中的数据块组合，得到k+Δk个数据块，按照扩展之后的编码
方式计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′，并将校验块PC1′～PCm′存储到
节点中，由组合得到的k+Δk个数据块及校验块PC1′～PCm′构成一个新的条带；

[0028] 垃圾回收模块，用于从节点中删除关联容器组G中各容器的旧校验块；

[0029] 其中，k、Δk和m均为正整数；RS(k,m)和RS(k+Δk,m)均为纠删码编码方式，RS(k,m)对k个数据块编码产生m个校验块，RS(k+Δk,m)对k+Δk个数据块编码产生m个校验块。

[0030] 按照本发明的又一个方面，提供了一种数据去重系统，该数据去重系统中，每个容器由k个数据块组成，并且每个容器中的k个数据块按照RS(k,m)编码方式编码后产生m个校
验块；每个容器中的k个数据块及编码产生的m个校验块构成一个条带，且分别存储在不同
的k+m个节点上；该数据去重系统包括本发明所提供的上述提高数据去重系统可扩展性的
容错编码装置。

[0031] 总体而言，通过本发明所构思的以上技术方案，能够取得以下有益效果：

[0032] (1)本发明根据数据去重之后产生的容器之间的局部性关系，在数据去重系统发生扩展时，只对部分容器中的数据块进行迁移，具体来说，将每k+Δk个具有局部性关联的
容器划分为一个关联容器组，按照关联容器组进行数据块迁移，且每个关联容器组中仅迁
移Δk个容器中的数据块；数据迁移之后，由迁移数据块与未迁移容器中的数据块组合并重
新编码为新的条带，由此能够有效减少网络带宽和磁盘I/O的开销，快速完成系统扩展，同
时也避免了系统扩展时条带中编码块大小改变对读写性能产生的影响，从而有效提高数据
去重系统的可扩展性。

[0033] (2)本发明按照容器中数据块与文件的关联关系划分关联容器组，并通过将同一关联容器组中的数据块进行迁移和重组，保留了容器的局部性关系，能够对数据去重系统
产生的去重碎片进行处理，将同一文件的分块进行聚合，利用数据局部性提高数据去重系
统的读性能。

附图说明

[0034] 图1为本发明实施例所提供的提高数据去重系统可扩展性的方法示意图。

具体实施方式

[0035] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并
不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要
彼此之间未构成冲突就可以相互组合。

[0036] 在本发明中，本发明及附图中的术语“第一”、“第二”等(如果存在)是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。

[0037] 与普通的数据不同，备份数据流具有一些独特的局部性特征，例如，对于一个每周进行全量备份的数据中心来说，其中大部分的数据写入的顺序和上一版本的备份都是相同
的，因此在去重时，一个数据块的重复也就意味着往往其上下文的若干个数据库也是重复
的，因此DDFS等数据去重系统引入容器来保留这种局部性关系，通过对多个数据块的聚合，
以此减少去重过程中反复的磁盘I/O。

[0038] 在数据去重系统中，每个容器由k个数据块组成，并且每个容器中的k个数据块按照RS(k,m)编码方式编码后产生m个校验块；每个容器中的k个数据块及编码产生的m个校验
块构成一个条带，且分别存储在不同的k+m个节点上；其中，RS(k,m)为一种纠删码编码方
式，采用RS(k,m)对k个数据块编码产生m个校验块，相应地，编码条带的长度为k+m；RS
(Reed‑Solomon)编码是众多纠删码中较为常用的一种编码方式，不失一般性地，以下实施
例中均以RS编码为例进行说明。

[0039] 以下以图1为例，对现有的采用容器内编码的去重系统中的编码机制进行简要说明。如图1所示，在扩展前，该数据去重系统中共包含节点0～节点3这4个节点，并且包含3个
容器，采用RS(2,2)编码方式对各容器中的数据块进行编码，即k＝2，m＝3；第一个容器中包
含数据块D1和D2，编码后产生校验块P1和P2，数据块D1和D2和校验块P1和P2构成一个条带；第
二个容器包含数据块D3和D4，编码后产生校验块P3和P4，数据块D3和D4和校验块P3和P4构成一
个条带；第三个容器包含数据块D5和D6，编码后产生校验块P5和P6，数据块D5和D6和校验块P5
和P6构成一个条带；各条带中不同的编码块(数据块或校验块)分别存储在不同的节点上；
为便于描述，不失一般性地，以下实施例均在图1所示的数据去重系统的基础上实现。

[0040] 为了提高以图1为代表的数据去重系统的可扩展性，本发明提供了一种提高数据去重系统可扩展性的容错编码方法、装置及系统，其整体思路在于：在数据去重系统发生扩
展时，根据容器之间的局部性关系预先将容器分组，并在扩展时根据其局部性关系将数据
块迁移重组为新的编码条带并对校验块执行更新；进一步在系统扩展时优先对产生碎片化
的容器进行处理，从而提高系统的读性能。

[0041] 以下为实施例：

[0042] 实施例一：

[0043] 一种提高数据去重系统可扩展性的容错编码方法，如图1所示，包括：

[0044] 在数据去重系统中新增Δk＝1个节点时，将每k+Δk＝3个具有局部性关联的容器划分为一个关联容器组，并将编码方式从RS(2,2)扩展为RS(3,2)；新增节点为节点4，如图1
所示，将三个容器作为关联容器组，记为G；

[0045] 对于图1中的关联容器组G，选取其中的1个容器，即第三个容器，作为待迁移容器，将待迁移容器中的2个数据块D5和D6均匀地迁移到新增节点中；对于该关联容器组G中每一
个未迁移的容器C，即第一个容器或第二个容器，从每一个新增节点中选取一个数据块与容
器C中的数据块组合，如图1所示，将迁移后的数据块D5与第一个容器中的数据块D1和D2组
合，将迁移后的数据块D6与第二个容器中的数据块D3和D4；对于每一个未迁移的容器C，组合
后得到3个数据块，按照扩展之后的编码方式RS(3,2)计算组合得到的3个数据块对应的校
验块PC1′～PCm′；对于第一个容器，按照RS(3,2)计算的校验块为P1′～P2′，对于第二个容器，
按照RS(3,2)计算的校验块为P3′～P4′；将校验块P1′～P2′分别存储到节点2和节点3中，由
数据块D1、D2和D5，以及校验块P1′～P2′构成一个新条带；将校验块P3′～P4′分别存储到节点
2和节点3中，由数据块D3、D4和D6，以及校验块P3′～P4′构成一个新条带；从节点中删除该关
联容器组G中各容器的旧校验块，即校验块P1～P6。

[0046] 在本实施例中，对于关联容器组G，选取待迁移容器的方式为：

[0047] 按照碎片化程度从高到低的顺序对关联容器组G中的容器进行排序；

[0048] 将排序结果中碎片化程度最高的前Δk个容器作为待迁移容器；

[0049] 其中，容器的碎片化程度可利用容器中数据块所关联的文件数量度量，容器中数据块所关联的文件数量越多，该容器的碎片化程度越高；数据块来自于哪个文件，该数据块
即与该文件相关联。

[0050] 在本实施例中，划分关联容器组的方式为：

[0051] 对于每一个容器，获得其中各数据块所关联的文件id，并将其中占比最高的文件id作为该容器的关联性id；

[0052] 将关联性id相同的容器作为具有局部性关联的容器；

[0053] 将每k+Δk＝3个具有局部性关联的容器划分为一个关联容器组；

[0054] 应当说明的是，当数据去重系统扩展时，如果划分出了多个关联容器组，那么每一个关联容器组内的数据块迁移与扩展编码方式都是一样的，可参考本实施例中对于关联容
器组G的处理方式，在此将不作复述。

[0055] 在本实施例中，按照扩展之后的编码方式计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′，包括：

[0056] 分别获得编码方式在扩展前、后对应的编码矩阵，通过矩阵变换得到校验块PC1′～PCm′与容器C的旧校验块PC1～PCm以及迁移的数据块之间的关系f；

[0057] 图1中，系统扩展前，使用RS(2,2)编码方式，其编码矩阵为

[0058]

[0059] 相应地，

[0060] 系统扩展后，使用RS(3,2)编码方式，其编码矩阵为

[0061]

[0062] 相应地，

[0063] 读取节点中存储的容器C的旧校验块PC1～PCm以及相应的迁移的数据块，将所读取的数据块按照关系f计算组合得到的k+Δk个数据块对应的校验块PC1′～PCm′；

[0064] 在本发明其他的一些实施例中，也可以直接按照扩展之后的编码方式对组合得到的k+Δk个数据块进行编码，产生校验块PC1′～PCm′；不过由于一个条带中，数据块的数量多
于校验块的数量，采用本实施例所提供的方式进行校验块更新，能够减少校验块更新过程
中传输的数据量，从而减少网络带宽和磁盘I/O开销。

[0065] 本实施例所提供的提高数据去重系统可扩展性的容错编码系统，还包括：

[0066] 在系统扩展完成后，发生降级读时，定位失效数据块所属的条带，并从该条带中读取k+Δk＝3个未失效的编码块，按照扩展之后的编码方式RS(3,2)对所读取的编码块进行
解码操作，修复出失效数据块；

[0067] 其中，编码块为条带中的数据块或校验块。

[0068] 实施例二：

[0069] 一种提高数据去重系统可扩展性的容错编码装置，包括：关联容器组划分模块、数据块迁移模块、扩展编码模块以及垃圾回收模块；

[0070] 关联容器组划分模块，用于在数据去重系统中新增1个节点时，将每3个具有局部性关联的容器划分为一个关联容器组，并将编码方式从RS(2,2)扩展为RS(3,2)；

[0071] 数据块迁移模块，用于对于每一个关联容器组G，选取其中的1个容器作为待迁移容器，将待迁移容器中的共2个数据块均匀地迁移到1个新增节点中；

[0072] 扩展编码模块，用于对于关联容器组G中每一个未迁移的容器C，从每一个新增节点中选取一个数据块与容器C中的数据块组合，得到3个数据块，按照扩展之后的编码方式
计算组合得到的3个数据块对应的校验块PC1′～PCm′，并将校验块PC1′～PCm′存储到节点中，
由组合得到的3个数据块及校验块PC1′～PCm′构成一个新的条带；

[0073] 垃圾回收模块，用于从节点中删除关联容器组G中各容器的旧校验块；

[0074] 本实施例中，各模块的具体实施方式，可参考上述实施例一中的描述，在此将不作复述。

[0075] 实施例三：

[0076] 一种数据去重系统，该数据去重系统包括上述实施例二所提供的提高数据去重系统可扩展性的容错编码装置。

[0077] 总体而言，本发明所提供的提高数据去重系统可扩展性的容错编码方法、装置及系统，在发生集群扩展时的扩展效率比传统的容器内编码扩展效率大幅增加，并且在提升
了集群扩展性能的同时，保证了系统的降级读和节点恢复性能，同时与容器间编码相比具
有较低的存储开销。

[0078] 本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含
在本发明的保护范围之内。