海量数据归档系统数据压缩算法选择方法研究

2019-12-23郭静

中国电子科学研究院学报 2019年7期

郭静

(中国电子科学研究院，北京 100041)

0 引言

随着信息技术的不断发展，数据资源已成为不同行业、单位提升其业务水平的重要资产。这些数据资源中不仅包含着高频访问的实时数据，也包含了大量低频使用的历史数据信息。为节约数据管理成本，数据归档系统[1-6]便成为了保留海量历史数据的重要场所。然而，随着大数据时代的到来，归档系统应对的数据规模正在呈现爆炸性增长，实现海量历史信息的管理，使系统满足大容量、高效率、易于回取等特性已成为海量数据归档系统的重要挑战。为应对海量数据的挑战，重复数据删除技术[7-9]和数据压缩技术[10,11]，已成为提升数据归档系统存储管理能力的重要手段。

为实现海量数据的归档管理，选择恰当的数据压缩算法已成为提升归档系统存储管理能力的重要前提。目前许多学者对数据压缩算法展开了大量的研究[12-15]，但是仍没有解决归档系统选择数据压缩算法问题。由于算法选择问题涉及内容复杂，全面定量评估算法对系统的影响困难等因素的存在，致使选择面临下列挑战。(1)由于增加数据压缩算法会对归档系统的硬件使用、归档业务流程等多方面引起变化，如何选择一些综合评价指标来反映算法对系统的影响是一个挑战。(2)由于不同数据压缩算法在数据压缩比例、压缩解压时间、处理内存需求、实现复杂度等方面优劣各异，不同算法对归档系统的影响各有优势，直接选择算法困难。(3)由于归档数据内容具有动态性，致使部分评价因素只能由带有一定不确定性语言等级来进行描述，无法直接采用量化方法对选择问题求解。

为解决上述问题，本文分析归档系统的业务特点，融合数据压缩算法的关键特性，对数据压缩算法选择问题建模，并设计求解方法。在建模上，综合考虑算法成本、归档业务要求、对系统处理能力和可靠性的影响，以及系统存储能力的提升效果等因素，将问题建模成带约束的多目标优化问题。在求解时，方法首先对候选压缩算法进行初步筛选，过滤不满足归档业务要求和劣质的候选算法，约简决策属性。然后，分析剩余候选算法的数量和决策属性的唯一性，利用不同的策略对问题求解。其中，针对多个剩余候选方案和多种决策属性的情况，在评估决策属性的重要程度和归一化处理后，利用TOPSIS方法[16]选择最优压缩算法。最后，通过用例展示了数据压缩算法的选择过程。

1 选择算法的主要因素

数据压缩算法能有效提升归档系统对海量数据的管理能力，算法选择时需要考虑以下主要因素。

(1)算法成本

为实现海量数据的存储管理，数据管理单位需要花费一定量时间，投入人员或经费为归档系统增加相应的压缩模块。由于不同数据压缩算法的复杂程度及花费可能具有一定差异，为此，选择算法要考虑成本因素。成本是指因归档系统增加数据压缩算法所产生的综合代价，主要内容包括：人员成本、时间成本、费用等要素。

(2)对系统处理能力的影响

归档系统应用数据压缩算法存储更多数据的同时，数据压缩操作和数据解压操作也会消耗更多的CPU资源，系统需要更多时间来完成数据归档和数据回取。由于不同数据压缩算法处理数据的时间(数据压缩时间和数据解压时间)不同，为此，选择算法需要考虑对系统处理能力的影响。即：考虑归档系统采用不同算法的归档效率和数据回取效率。

(3)对系统可靠性的影响

归档系统在应用数据压缩算法后，系统的负载能力将发生变化。在原始硬件的条件下，由于增加了数据压缩算法，系统需要使用更多的CPU和内存资源完成归档和回取处理，系统负载能力将有所增加，影响系统的可靠性。由于不同数据压缩算法所需的内存与计算资源不同，归档系统的负载将有所差异，继而对可靠性产生不同影响。为此，算法选择需要考虑其对系统可靠性的影响。

(4)提升系统存储能力的效果

数据压缩算法可以有效减少数据存储的空间，从而实现归档系统存储能力的提升。由于不同算法对数据的压缩比例有所不同，不同算法对归档系统存储能力的提升效果也会有所差异。为此，算法选择需要考虑其对系统存储能力的提升效果。

基于上述因素，为归档系统选择最优数据压缩算法，应该花费最低成本，最大程度提升归档系统的存储能力，最小程度影响系统的处理能力和可靠性。然而，不同算法在压缩时间、解压时间、数据压缩比上各有优劣，直接选择最优压缩算法困难。

2 算法选择问题建模

为归档系统选择合适的数据压缩算法是实现海量数据归档管理的关键，本文综合分析上述因素，对算法选择问题建模。模型以算法成本、对系统处理能力的影响、对系统可靠性的影响和提升系统存储能力的效果为决策因素，将算法选择问题表示成多目标优化问题。具体如下：

算法成本：主要由费用、人员投入和时间花费所组成。其中，费用是指归档系统增加压缩算法的花费估算总和，其涵盖增加压缩算法使归档流程再造的开发费用和压缩算法本身的专利费等，一般为定量值；人员投入是指归档系统增加数据压缩算法所需投入的人员数量，其取值为整数；时间花费是指归档系统增加压缩算法所需的总时长，其取值通常为区间数。

对系统处理能力的影响：主要反映为归档效率和回取效率，二者情况可通过测试计算和测试评估获得。其中，归档效率为归档系统平均每分钟可归档数据的规模，其取值为定量值，决策时要保证归档效率满足业务要求，确保数据处理不积压；回取效率可由归档系统回取目标数据的时间来反映，由于回取效率与回取目标数据以及数据在存储介质分布情况相关，精确计算回取效率取值困难，为此，回取效率情况可根据算法解压数据的时间采用定性评估方法获得，划分成九个等级(即：极高、很高、高、较高、一般、较低、低、很低、极低)。

对系统可靠性的影响：主要通过分析归档系统的负载变化获得，简称为可靠性影响程度。通过综合分析当前归档系统的资源使用率以及算法处理数据的资源需求，评估获得对系统可靠性的影响，具体可分为五个等级(即：大、较大、中、较小、小)。

系统存储能力的提升效果：主要通过分析算法压缩归档数据的平均压缩比例获得，简称为存储提升效果。算法平均压缩比例越大，则系统存储能力提升效果越好。由于归档数据内容具有一定动态性，提升效果将采用定性评估获得，根据算法压缩比例的测试结果，系统存储能力的提升效果可分为九个等级(即：极好、很好、好、较好、一般、较差、差、很差、极差)。

基于上述描述，算法选择的决策因素情况及其包含决策属性的符号化表示如下：

表1 决策因素情况的符号化表示

海量数据归档系统数据压缩算法选择问题：已知归档系统有n个候选数据压缩算法L={l1，l2，…，ln}可用于提升系统的数据管理能力。为保证归档数据不积压，系统要求归档效率大于am。专家根据候选算法的压缩比、压缩内存、解压内存、压缩时间、解压时间、专利费等情况，通过测试评估获得了候选算法的成本(费用S、投入人员数量C和时间花费T)，对系统处理能力的影响(归档效率A和回取效率R)，对系统可靠性的影响I，以及系统存储能力的提升效果E。该问题就是要从候选算法中选择一种算法满足归档效率要求，并且在决策属性{S、C、T、A、R、I、E}上整体最优。

3 问题求解

3.1 问题分析

通过上述建模过程可以看出海量数据归档系统数据压缩算法选择问题是一个带约束的多目标优化问题，问题求解存在以下挑战。

(1)决策属性的类型复杂，决策属性既有定量的数值，又有定性的语言评价，直接选择困难。

(2)多个决策属性的目标和评价标准具有差异，使得比较数据压缩算法之间的优劣复杂。算法选择既包含最大化目标(即，最大化存储提升效果)，也包括最小化目标(即，最小化成本和对系统的影响)，当候选算法数量较多时，问题求解难度较大。

(3)不同决策属性的单位量纲和数量级存在差异，综合评价困难。

通过分析得出，问题的求解难度由候选算法的规模及决策属性的数量所共同决定，由于决策属性类型复杂、单位量纲和数量级差异较大，问题求解复杂。

3.2 问题求解预处理

为快速求解问题，本文将对候选算法和决策属性进行预处理操作，具体包括：过滤劣质候选压缩算法、约简决策属性、模糊化表示定性决策属性、决策属性归一化处理。具体描述如下：

预处理规则1：假设有n个候选压缩算法L={l1，l2，…，ln}，如果存在压缩算法lk在归档效率A上不能满业务要求(即，满足ak小于am)，则压缩算法lk将被淘汰。

预处理规则2：假设有n个候选压缩算法L={l1，l2，…，ln}，如果存在一种压缩算法lk在决策属性{S、C、T、A、R、I、E}上均劣于其他候选算法，则压缩算法lk将被淘汰。

预处理规则3：假设经过预处理规则1和预处理规则2处理后，还剩d个候选压缩算法，如果d个候选压缩算法在某类决策属性上的取值均相等，则该决策属性可以被约简。

通过预处理规则1和预处理规则2可以淘汰不满足业务要求和在各项指标均不好的候选算法。预处理规则3可以约简决策属性从而提升选择效率。

为快速求解问题，本文根据决策属性的特点，利用文献[17]中的模糊数表达方式来反映定性决策属性的不同等级。假设决策属性有q个等级，则第j个等级对应的三角模糊数可由公式2表示，其中，等级越高则决策属性越好。

(1)

V(q,j)=(f(q,j-2),f(q,j-1),f(q,j))

(2)

于是回取效率R、可靠性影响程度I、存储提升效果E可由下列三角模糊数来表示，具体如表2所示。

表2 定性决策属性的三角模糊数表示

经过以上预处理操作，所有决策属性均被量化表示。考虑到决策属性在量纲和数量级上的差异，本文利用向量规范法[18]对实数、区间数、三角模糊数决策属性进行归一化处理。假设经过预处理后还剩d个候选算法，则任意候选算法i对实数、区间数、三角模糊数决策属性的归一化方法如下：

(3)

(4)

(5)

(6)

(7)

(8)

3.3 快速求解问题步骤

为实现问题的快速求解，本文通过下列步骤来完成数据压缩算法选择。其基本思想是首先利用预处理规则淘汰候选算法集合中的劣解，并约简剩余算法的决策属性。然后，分析剩余候选算法和决策属性的数量，根据其取值，采用不同的策略对算法进行选择。假设有n个候选压缩算法L={l1，l2，…，ln}，则算法选择的具体步骤如下：

(1)分析候选压缩算法L的归档效率，利用预处理规则1删除ak小于am的候选算法，形成新的候选压缩算法集合L1。若L1中剩余候选算法唯一，则该算法就是问题的最优解，否则转步骤(2)。

(2)依次比较L1中的候选算法，利用预处理规则2淘汰在各个决策属性上均劣于其他的候选算法，形成新的候选压缩算法集合L2。若L2剩余候选算法唯一，则该算法就是问题的最优解，否则转步骤(3)。

(3)利用预处理规则3约简L2的决策属性，若经约简后决策属性个数m满足m=1，则该问题已成为单目标决策问题，可直接比较剩余决策属性求解，否则转步骤(4)。

(4)利用公式(3)-(8)对L2的剩余决策属性进行归一化处理获得规范化矩阵W，再转步骤(5)。其中，剩余决策属性个数m满足1

(9)

(5)通过专家评估当前决策属性的重要程度，获得属性权重Y={y1,y2,…,ym}，利用公式(10)计算加权规范矩阵H再转步骤(6)，其中权重Y的和为1。

(10)