基于民航数据特性的重删固定长度分块方法

丁建立，李 慧，曹卫东

（中国民航大学计算机科学与技术学院，天津 300300）

近年来，随着民航业的迅速发展，机场在中小城市的普及和机票价格的降低使得越来越多的人会选择乘机出行[1]。这就导致机场和航空公司的数据库中记录乘客乘机信息的数据量越来越庞大。某民航单位提供的数据显示，部分数据库仅2015—2016年就产生了7.32 GB 数据，其中重复数据占40%～52%。大量重复数据使民航数据库在容灾备份时数据的复制、传输和恢复时间过长[2]，占用了过多的网络带宽。由于需要更大的存储空间来存储数据，系统在扩展时需要更多复杂的操作，增加维护难度，且数据库存储数据的成本也会增加。在民航数据库容灾备份时，需要删除大量的重复数据来提高容灾备份的效率。因此，针对重复数据删除技术的研究是非常有意义的。

关于如何处理重复数据带来的数据冗余问题，早期的解决方法主要有字节压缩[3]和差量压缩[4]，但由于方法的编码、计算及I/O 开销较大，压缩率十分有限。ALACC 方法[5]能够动态分配一定内存给块缓存，提高了重复数据删除过程中的数据吞吐量，但这种方法只适配于具有固定内存大小的重删系统，灵活性不高。廖海生[6]提出的数据容灾系统，能从文件夹的子层级查找出冗余数据，存储数据所需空间随之减少，但这种方法首先需要对文件进行分级，而民航备份系统中的数据文件包含关系十分复杂，在文件分级时会占用很多内存和CPU 空间，降低了重删效率。张甲燃[7]和韩英杰[8]在数据索引层面进行一定改进，前者将新文件当作滑动校验码值去匹配多个索引，节省了网络数据流量；后者增加取样过程，不断计算滑动窗口的哈希值，再从中筛选出最小值作为样本，重删速度更快，占用内存空间也更少，但民航备份系统中的数据数量多且单条数据很短，这两种方法产生的大量滑动校验码值或哈希样本值的计算和存储会浪费较多的系统资源。阎芳[9]提出一种面向分块的交叉分组数据组织方法，调整磁盘水平分组和垂直分组的大小，使I/O 请求集中在某个磁盘水平分组，其他分组的磁盘进入待机模式，降低了存储能耗，但这种方法只对连续数据访问模式有效，在民航备份系统中，数据的大量不连续访问会增加校验磁盘切换次数，增加了时间开销和硬件损耗。

综上所述，针对上述几种方法应用于民航备份系统中存在的问题，提出了一种基于民航数据特性的重删固定长度分块方法，该方法在分块逻辑上进行了改进，能够在一定程度上缩短分块时间，提高重删效率。

1 相关技术与方法概述

1.1 重复数据删除技术

重复数据删除技术的基本原理[10]是将备份数据流按照算法切割成数据块，将切割好的数据块内容与数据库中的数据内容进行匹配，如果匹配成功，则说明数据块中的内容与数据库中的内容相同，则该部分内容为重复数据。

重复数据删除的过程[11]分为4 个阶段：输入备份数据流、生成块序列、计算指纹序列、输出单一副本序列。在容灾备份时，重复数据删除系统首先会接收来自用户的备份数据流，将需要备份的数据流按照一定规则处理成备份数据块，再使用适合的算法计算其指纹值，生成一个指纹序列，通过比较这个指纹序列来判断这些数据是否为重复数据。若在比较过程中，重复数据删除系统确定了这些数据是重复数据，则只保留单一的副本序列，重复的数据序列将会被系统删除。

1.2 分块方法

1.2.1 固定长度分块方法

重复数据删除技术研究中最早提出的分块方法是固定长度分块方法[12]。固定长度分块方法主要步骤如下：

（1）将需要备份的数据流文件输入备份系统，备份系统将数据流分为等长的块，称为“数据块”，再采用指纹计算方法计算每个块的指纹，如SHA-1 算法；

（2）计算出来的数据块指纹值与索引表中已存的指纹值进行比较，若比较结果一致，则匹配成功，该数据块即为重复数据块，丢弃或删除即可；否则说明为新数据，需要将其备份到数据库中，同时该数据块的指纹值需要存储到索引表中，以供下次比较指纹值时使用。

固定长度的分块方法操作简单、易实现，同时对设备要求不高，但对数据的修改位置十分敏感[13]。当修改的数据在备份文件的头部时，固定长度分块方法会将文件分割成与原文件基本不同的数据块。新的指纹值与原始数据指纹值基本不会相同，备份系统会把只发生了很少字节变化的文件当成全新文件进行存储，备份系统的效率大幅降低。

1.2.2 可变长度分块方法

可变长度分块方法，又称为基于内容可变长度分块（CDC，content-defined chunking）。这种方法的实现依赖于Rabin 指纹算法[14]。Rabin 指纹算法能够根据前一个数据块的指纹快速得到滑动窗口后下一个数据块的指纹。

在Rabin 指纹算法中，设定了一个固定窗口在文件上滑动，另外有2 个预设值D 和r，这两个值均为整数且r ＜D。将固定窗口滑动到某一位置k 时，用哈希算法计算出固定窗口内数据内容的指纹值f，只有满足f mod D=r 时，当前的位置k 才可以界定为数据块的边界，窗口滑动距离就是数据块的大小。然后继续将窗口向右滑动，重复计算指纹和匹配的过程，直到找到所有的数据块边界。如图1 所示。

图1 Rabin 指纹算法示意图Fig.1 Schematic diagram of Rabin fingerprint algorithm

可变长度分块方法的主要步骤如下：

（1）输入需要备份的数据流文件后，首先从文件头部开始生成一个长度固定的滑动窗口，计算该窗口的指纹值，如果这个指纹值满足Rabin 指纹算法的条件，那么窗口当前的位置就是数据块的一个边界；否则，向右滑动一个字节的长度；

（2）一直重复步骤（1），直到整个文件都被分成数据块；

（3）这些数据块的长度可能不同，为每一个数据块计算哈希指纹值，将这些指纹值与数据库中已经存在的哈希值进行对比，如果对比结果相同，则表示数据块重复，需要删除该指纹值代表的数据块；否则是不重复的新数据块，需要进行存储。

在可变长度分块方法中，分块方法更加灵活，即使文件数据中的变化发生在文件头部或中部也能快速找出重复数据。但在可变长度分块方法实现过程中：一方面，不管窗口滑动到哪个位置都需要计算窗口的哈希值，大量的计算会增加系统负担[15]；另一方面，滑动窗口的大小与D 和r 的选值有关[14]。当滑动窗口过小时，则在分块过程中很容易满足f mod D=r 的条件，导致备份文件分块过多，计算出的指纹量也随之增加，增加了系统在计算、存储指纹值过程中的开销；当滑动窗口过大时，则系统分出来的每一个数据块都很大，取一个极端情况，当滑动窗口的大小与备份文件的大小相同时，这种分块方法将毫无意义[16]。

2 基于民航数据特性的分块方法

在民航数据库中，存在许多不同值，但数据类型相同的数据。通过对大量的民航数据分析发现，一个民航数据文件流数据头的几个固定长度字段能够表示这个文件流接下来一段数据的类型，因此，称这种特性为民航数据的类型一致性。下面将举例来说明类型一致性，如图2 所示。

图2 民航数据的类型一致性Fig.2 Type consistency of civil aviation data

图2 中，备份的文件流进入备份系统后，首先会将文件流头部的几个字节提取出来，识别数据类型后将这个数据文件归类，再根据数据类型计算出对应的文件类型ID 值，最后在分块策略索引表中索引ID 值对应的偏移量值完成分块。

基于民航数据特性的重删固定长度分块方法中的“固定”一词，与固定长度分块方法中的“固定”一词，并不是同一种含义。在后者中，“固定”指的是数据块大小固定，系统只要按照预设好的数据块大小分块即可。而前者中，“固定”指的是一种相对固定的分块，系统在数据分块时按照分块策略索引表中的偏移量对备份文件进行分块，这些偏移量是根据民航数据特性预先计算出来的，虽然数值不同，但是固定不变的，故称这种分块方法为“基于民航数据特性的重删固定长度分块方法”，以下简称为“民航特性分块方法”。

2.1 分块策略索引表

根据民航数据类型一致性的特点，在民航特性分块方法中为这几个字段单独设置一个分块策略索引表。分块策略索引表中记录着每个数据分块的身份ID及对应的其在文件中的偏移量。分块策略索引表的数据结构如表1 所示。

表1 分块策略索引表的数据结构Tab.1 Data structure of the block strategy index table

只需要在某类数据首次出现时进行滑动分块，并将滑动过程中产生的偏移量记录在分块策略索引表中，当这类数据再次出现时，只需要按照第一次的偏移量记录进行分割，而不必再浪费CPU 资源进行分块。另外，由于相同类型的不同数据会使用同一个数据块身份ID，故分块策略索引表不会记录每一个数据，分块策略索引表也不会过分庞大，索引数据块身份ID 的时间不会过长。

2.2 重复数据删除流程图

图3 是民航特性分块方法的重复数据删除流程图。流程图可分为以下5 个步骤。

步骤1在图3 中，输入需要备份的民航数据流文件。首先备份系统会按照一个预设的值在文件流的头部分割出一个固定大小的数据块，计算这个数据块的指纹值，根据指纹值生成该数据块的身份ID。

图3 民航特性分块方法的重复数据删除流程图Fig.3 Flow chart of deduplication of fixed-length block method based on characteristics of civil aviation data

步骤2得到数据块的身份ID 后，在分块策略索引表中索引数据块身份ID。若能查找到这个身份ID，则按照分块策略索引表中的策略对该数据流的剩余部分进行切割分块，一直切割到数据块的尾部，转步骤4；如果在分块策略索引表中查找不到这个身份ID，则需要为其建立一个新的策略，转步骤3。

步骤3在建立新策略的过程中，首先生成一个滑动窗口，再计算这个窗口的指纹值。若当前位置不满足Rabin 指纹算法的条件，则说明当前位置不是数据块的边界，需要继续向后滑动窗口来寻找数据块的边界位置。当窗口所在位置满足Rabin 指纹算法的条件时才到达了数据块的尾部边界，记录滑动窗口此时的偏移量，方便数据下次出现时能够在分块策略索引表中找到分块策略，快速完成分块操作。

步骤4重复步骤1～3 的过程直到整个备份文件流都完成分块。

步骤5整个备份文件流都完成分块后，开始进行重复数据删除操作。首先为每个数据块计算哈希指纹值，将这些指纹值与数据库中已经存在的哈希值进行对比。如果对比结果相同，则表示数据块重复，需要删除该指纹值代表的数据块；否则为不重复的新数据块，需要进行存储，不存在的数据块需要在索引表中留下其指纹值，方便后续的数据块进行比较。

3 实验结果分析

3.1 实验平台及数据

实验平台的基本配置如表2 所示。

表2 实验平台配置情况Tab.2 Configuration of lab platform

实验中所用数据集为2015年12月至2016年12月某民航单位提供的离港数据库、旅客订座记录（PNR）数据库、客票（ET）数据库、客座率数据库中的部分数据。这4 个数据库中的数据大小分别为382MB、2.74 GB、3.96 GB、236 MB，合计数据量为7.32 GB，包含的数据条目约为23 203 万条。

在实验时，将2015年12月至2016年5月的数据作为数据库中的原有数据，此后2016年6月至12月每月分别使用固定长度分块方法、可变长度分块方法、民航特性分块方法为数据库做一次全量备份，共7 次。

3.2 备份所需时间对比

在本节实验中，对使用了3 种方法备份所用的时间进行对比分析。备份时所用时间情况如图4 所示，纵轴的单位为厘秒（10-2s）。

图4月备份所需时间Fig.4 The time required for monthly backups

从图4 中看出：在备份时，固定长度分块方法所用时长最短，可变长度分块方法与民航特性分块方法所需时间差别不大，但后者所用时间基本少于前者；相对于固定长度分块方法，可变长度分块方法备份所需时间是其1.5 ～2.0 倍，民航特性分块方法备份所需时间是其1.2 ～1.8 倍。

在可变长度分块方法中，滑动窗口需要不断滑动，每次滑动后都要计算滑动窗口的指纹值，这一过程消耗的CPU 资源和时间要比另外两种方法都多。在民航特性分块方法中，备份文件被输入系统后，若文件流直接按照策略进行分块，则节省了寻找数据块边界的时间；若文件流需要寻找数据块的边界来进行分块，则该过程消耗了更多时间进行计算操作，因此，这种方法所需的时间要长于固定长度分块方法，但总体比可变长度分块方法用时要短。而在固定长度分块方法中，只需要将每个数据文件按照要求切割成固定大小的数据块即可，而无需其他操作，因此这种分块方法所需的时间远小于另外两种。

虽然固定长度分块方法所需时间最短，但备份所需时间并不是检验一种分块方法好坏的唯一标准，仍需进一步实验来比较这3 种分块方法。

3.3 模拟重删率对比

实验的侧重点在于重复数据删除技术研究中对备份数据流进行分块这一步骤，而不在于最终重复数据删除的具体百分比，所以本节实验将会根据民航数据的特性采用模拟的重删率，而不是真正的重删率，以节约系统资源，减少实验时长而不影响最终效果的呈现。

实验将2016年6月至12月每个月分块后的数据块与原有数据（即2015年12月至2016年5月的数据）分块后的数据块做对比，用每个月的数据块变化的多少来模拟重删率的高低。实验中采用分块后数据块变化数目的对数（以2 为底）再取其倒数来计算模拟重删率。

若某月分块后的数据块变化较多，则说明分块过程中产生的变化较多，表示备份系统效果不佳，模拟重删率越低，即重删率低；若某月分块后的数据块变化较少，则说明分块过程中产生的变化也较少，模拟重删率越高，即重删率高。实验结果如图5 所示。

图5 模拟重删率实验结果Fig.5 Simulation results of deduplication rate experiment

由图5 可知，可变长度分块方法与民航特性分块方法在备份系统备份过程中的效果都很好，固定长度分块方法模拟重删率稍低，但民航特性分块方法始终有着高于另外两种方法的模拟重删率。民航特性分块方法的模拟重删率能达到97.8%～99.3%，比固定长度分块方法高11.8%～12.5%，比可变长度分块方法高2.5%～3.0%。

基于民航数据特性的重删固定长度分块方法数据块的身份ID 能够在分块策略索引表中被找到时，按照策略直接进行分块，这些新的分块相较之前的分块基本不会发生变化，只有当数据块首次出现，为这个数据块添加新的策略时，新的分块相较之前的分块才会发生变化。在固定长度分块方法中，因为这种方法对数据变化的位置十分敏感，文件中的数据发生变化后，从当前数据所在位置向后的所有数据分块都会发生变化[17]。可变长度分块是对内容进行校验来判断分块边界，会将同一类型的不同数据都当作新的数据分块，所以固定长度分块方法的模拟重删率最低。

4 结语

通过分析民航数据的特性，改进了固定长度分块方法和可变长度分块方法，提出了一种基于民航数据特性的重删固定长度分块方法。在分块方法中，设置了一个分块策略索引表，来存放某一类型数据对应的分块切割策略。实验表明，该方法虽然备份时间略长，但模拟重删率比另外两种方法都要高，提高了重复数据删除过程中的分块效果，总体在重删过程中有着较好的表现。