海量數(shù)據(jù)歸檔系統(tǒng)數(shù)據(jù)壓縮算法選擇方法研究

郭 靜

(中國電子科學(xué)研究院，北京 100041)

0 引 言

隨著信息技術(shù)的不斷發(fā)展，數(shù)據(jù)資源已成為不同行業(yè)、單位提升其業(yè)務(wù)水平的重要資產(chǎn)。這些數(shù)據(jù)資源中不僅包含著高頻訪問的實(shí)時(shí)數(shù)據(jù)，也包含了大量低頻使用的歷史數(shù)據(jù)信息。為節(jié)約數(shù)據(jù)管理成本，數(shù)據(jù)歸檔系統(tǒng)[1-6]便成為了保留海量歷史數(shù)據(jù)的重要場所。然而，隨著大數(shù)據(jù)時(shí)代的到來，歸檔系統(tǒng)應(yīng)對(duì)的數(shù)據(jù)規(guī)模正在呈現(xiàn)爆炸性增長，實(shí)現(xiàn)海量歷史信息的管理，使系統(tǒng)滿足大容量、高效率、易于回取等特性已成為海量數(shù)據(jù)歸檔系統(tǒng)的重要挑戰(zhàn)。為應(yīng)對(duì)海量數(shù)據(jù)的挑戰(zhàn)，重復(fù)數(shù)據(jù)刪除技術(shù)[7-9]和數(shù)據(jù)壓縮技術(shù)[10,11]，已成為提升數(shù)據(jù)歸檔系統(tǒng)存儲(chǔ)管理能力的重要手段。

為實(shí)現(xiàn)海量數(shù)據(jù)的歸檔管理，選擇恰當(dāng)?shù)臄?shù)據(jù)壓縮算法已成為提升歸檔系統(tǒng)存儲(chǔ)管理能力的重要前提。目前許多學(xué)者對(duì)數(shù)據(jù)壓縮算法展開了大量的研究[12-15]，但是仍沒有解決歸檔系統(tǒng)選擇數(shù)據(jù)壓縮算法問題。由于算法選擇問題涉及內(nèi)容復(fù)雜，全面定量評(píng)估算法對(duì)系統(tǒng)的影響困難等因素的存在，致使選擇面臨下列挑戰(zhàn)。(1)由于增加數(shù)據(jù)壓縮算法會(huì)對(duì)歸檔系統(tǒng)的硬件使用、歸檔業(yè)務(wù)流程等多方面引起變化，如何選擇一些綜合評(píng)價(jià)指標(biāo)來反映算法對(duì)系統(tǒng)的影響是一個(gè)挑戰(zhàn)。(2)由于不同數(shù)據(jù)壓縮算法在數(shù)據(jù)壓縮比例、壓縮解壓時(shí)間、處理內(nèi)存需求、實(shí)現(xiàn)復(fù)雜度等方面優(yōu)劣各異，不同算法對(duì)歸檔系統(tǒng)的影響各有優(yōu)勢(shì)，直接選擇算法困難。(3)由于歸檔數(shù)據(jù)內(nèi)容具有動(dòng)態(tài)性，致使部分評(píng)價(jià)因素只能由帶有一定不確定性語言等級(jí)來進(jìn)行描述，無法直接采用量化方法對(duì)選擇問題求解。

為解決上述問題，本文分析歸檔系統(tǒng)的業(yè)務(wù)特點(diǎn)，融合數(shù)據(jù)壓縮算法的關(guān)鍵特性，對(duì)數(shù)據(jù)壓縮算法選擇問題建模，并設(shè)計(jì)求解方法。在建模上，綜合考慮算法成本、歸檔業(yè)務(wù)要求、對(duì)系統(tǒng)處理能力和可靠性的影響，以及系統(tǒng)存儲(chǔ)能力的提升效果等因素，將問題建模成帶約束的多目標(biāo)優(yōu)化問題。在求解時(shí)，方法首先對(duì)候選壓縮算法進(jìn)行初步篩選，過濾不滿足歸檔業(yè)務(wù)要求和劣質(zhì)的候選算法，約簡決策屬性。然后，分析剩余候選算法的數(shù)量和決策屬性的唯一性，利用不同的策略對(duì)問題求解。其中，針對(duì)多個(gè)剩余候選方案和多種決策屬性的情況，在評(píng)估決策屬性的重要程度和歸一化處理后，利用TOPSIS方法[16]選擇最優(yōu)壓縮算法。最后，通過用例展示了數(shù)據(jù)壓縮算法的選擇過程。

1 選擇算法的主要因素

數(shù)據(jù)壓縮算法能有效提升歸檔系統(tǒng)對(duì)海量數(shù)據(jù)的管理能力，算法選擇時(shí)需要考慮以下主要因素。

(1)算法成本

為實(shí)現(xiàn)海量數(shù)據(jù)的存儲(chǔ)管理，數(shù)據(jù)管理單位需要花費(fèi)一定量時(shí)間，投入人員或經(jīng)費(fèi)為歸檔系統(tǒng)增加相應(yīng)的壓縮模塊。由于不同數(shù)據(jù)壓縮算法的復(fù)雜程度及花費(fèi)可能具有一定差異，為此，選擇算法要考慮成本因素。成本是指因歸檔系統(tǒng)增加數(shù)據(jù)壓縮算法所產(chǎn)生的綜合代價(jià)，主要內(nèi)容包括：人員成本、時(shí)間成本、費(fèi)用等要素。

(2)對(duì)系統(tǒng)處理能力的影響

歸檔系統(tǒng)應(yīng)用數(shù)據(jù)壓縮算法存儲(chǔ)更多數(shù)據(jù)的同時(shí)，數(shù)據(jù)壓縮操作和數(shù)據(jù)解壓操作也會(huì)消耗更多的CPU資源，系統(tǒng)需要更多時(shí)間來完成數(shù)據(jù)歸檔和數(shù)據(jù)回取。由于不同數(shù)據(jù)壓縮算法處理數(shù)據(jù)的時(shí)間(數(shù)據(jù)壓縮時(shí)間和數(shù)據(jù)解壓時(shí)間)不同，為此，選擇算法需要考慮對(duì)系統(tǒng)處理能力的影響。即：考慮歸檔系統(tǒng)采用不同算法的歸檔效率和數(shù)據(jù)回取效率。

(3)對(duì)系統(tǒng)可靠性的影響

歸檔系統(tǒng)在應(yīng)用數(shù)據(jù)壓縮算法后，系統(tǒng)的負(fù)載能力將發(fā)生變化。在原始硬件的條件下，由于增加了數(shù)據(jù)壓縮算法，系統(tǒng)需要使用更多的CPU和內(nèi)存資源完成歸檔和回取處理，系統(tǒng)負(fù)載能力將有所增加，影響系統(tǒng)的可靠性。由于不同數(shù)據(jù)壓縮算法所需的內(nèi)存與計(jì)算資源不同，歸檔系統(tǒng)的負(fù)載將有所差異，繼而對(duì)可靠性產(chǎn)生不同影響。為此，算法選擇需要考慮其對(duì)系統(tǒng)可靠性的影響。

(4)提升系統(tǒng)存儲(chǔ)能力的效果

數(shù)據(jù)壓縮算法可以有效減少數(shù)據(jù)存儲(chǔ)的空間，從而實(shí)現(xiàn)歸檔系統(tǒng)存儲(chǔ)能力的提升。由于不同算法對(duì)數(shù)據(jù)的壓縮比例有所不同，不同算法對(duì)歸檔系統(tǒng)存儲(chǔ)能力的提升效果也會(huì)有所差異。為此，算法選擇需要考慮其對(duì)系統(tǒng)存儲(chǔ)能力的提升效果。

基于上述因素，為歸檔系統(tǒng)選擇最優(yōu)數(shù)據(jù)壓縮算法，應(yīng)該花費(fèi)最低成本，最大程度提升歸檔系統(tǒng)的存儲(chǔ)能力，最小程度影響系統(tǒng)的處理能力和可靠性。然而，不同算法在壓縮時(shí)間、解壓時(shí)間、數(shù)據(jù)壓縮比上各有優(yōu)劣，直接選擇最優(yōu)壓縮算法困難。

2 算法選擇問題建模

為歸檔系統(tǒng)選擇合適的數(shù)據(jù)壓縮算法是實(shí)現(xiàn)海量數(shù)據(jù)歸檔管理的關(guān)鍵，本文綜合分析上述因素，對(duì)算法選擇問題建模。模型以算法成本、對(duì)系統(tǒng)處理能力的影響、對(duì)系統(tǒng)可靠性的影響和提升系統(tǒng)存儲(chǔ)能力的效果為決策因素，將算法選擇問題表示成多目標(biāo)優(yōu)化問題。具體如下：

算法成本：主要由費(fèi)用、人員投入和時(shí)間花費(fèi)所組成。其中，費(fèi)用是指歸檔系統(tǒng)增加壓縮算法的花費(fèi)估算總和，其涵蓋增加壓縮算法使歸檔流程再造的開發(fā)費(fèi)用和壓縮算法本身的專利費(fèi)等，一般為定量值；人員投入是指歸檔系統(tǒng)增加數(shù)據(jù)壓縮算法所需投入的人員數(shù)量，其取值為整數(shù)；時(shí)間花費(fèi)是指歸檔系統(tǒng)增加壓縮算法所需的總時(shí)長，其取值通常為區(qū)間數(shù)。

對(duì)系統(tǒng)處理能力的影響：主要反映為歸檔效率和回取效率，二者情況可通過測(cè)試計(jì)算和測(cè)試評(píng)估獲得。其中，歸檔效率為歸檔系統(tǒng)平均每分鐘可歸檔數(shù)據(jù)的規(guī)模，其取值為定量值，決策時(shí)要保證歸檔效率滿足業(yè)務(wù)要求，確保數(shù)據(jù)處理不積壓；回取效率可由歸檔系統(tǒng)回取目標(biāo)數(shù)據(jù)的時(shí)間來反映，由于回取效率與回取目標(biāo)數(shù)據(jù)以及數(shù)據(jù)在存儲(chǔ)介質(zhì)分布情況相關(guān)，精確計(jì)算回取效率取值困難，為此，回取效率情況可根據(jù)算法解壓數(shù)據(jù)的時(shí)間采用定性評(píng)估方法獲得，劃分成九個(gè)等級(jí)(即：極高、很高、高、較高、一般、較低、低、很低、極低)。

對(duì)系統(tǒng)可靠性的影響：主要通過分析歸檔系統(tǒng)的負(fù)載變化獲得，簡稱為可靠性影響程度。通過綜合分析當(dāng)前歸檔系統(tǒng)的資源使用率以及算法處理數(shù)據(jù)的資源需求，評(píng)估獲得對(duì)系統(tǒng)可靠性的影響，具體可分為五個(gè)等級(jí)(即：大、較大、中、較小、小)。

系統(tǒng)存儲(chǔ)能力的提升效果：主要通過分析算法壓縮歸檔數(shù)據(jù)的平均壓縮比例獲得，簡稱為存儲(chǔ)提升效果。算法平均壓縮比例越大，則系統(tǒng)存儲(chǔ)能力提升效果越好。由于歸檔數(shù)據(jù)內(nèi)容具有一定動(dòng)態(tài)性，提升效果將采用定性評(píng)估獲得，根據(jù)算法壓縮比例的測(cè)試結(jié)果，系統(tǒng)存儲(chǔ)能力的提升效果可分為九個(gè)等級(jí)(即：極好、很好、好、較好、一般、較差、差、很差、極差)。

基于上述描述，算法選擇的決策因素情況及其包含決策屬性的符號(hào)化表示如下：

表1 決策因素情況的符號(hào)化表示

海量數(shù)據(jù)歸檔系統(tǒng)數(shù)據(jù)壓縮算法選擇問題：已知?dú)w檔系統(tǒng)有n個(gè)候選數(shù)據(jù)壓縮算法L={l1，l2，…，ln}可用于提升系統(tǒng)的數(shù)據(jù)管理能力。為保證歸檔數(shù)據(jù)不積壓，系統(tǒng)要求歸檔效率大于am。專家根據(jù)候選算法的壓縮比、壓縮內(nèi)存、解壓內(nèi)存、壓縮時(shí)間、解壓時(shí)間、專利費(fèi)等情況，通過測(cè)試評(píng)估獲得了候選算法的成本(費(fèi)用S、投入人員數(shù)量C和時(shí)間花費(fèi)T)，對(duì)系統(tǒng)處理能力的影響(歸檔效率A和回取效率R)，對(duì)系統(tǒng)可靠性的影響I，以及系統(tǒng)存儲(chǔ)能力的提升效果E。該問題就是要從候選算法中選擇一種算法滿足歸檔效率要求，并且在決策屬性{S、C、T、A、R、I、E}上整體最優(yōu)。

3 問題求解

3.1 問題分析

通過上述建模過程可以看出海量數(shù)據(jù)歸檔系統(tǒng)數(shù)據(jù)壓縮算法選擇問題是一個(gè)帶約束的多目標(biāo)優(yōu)化問題，問題求解存在以下挑戰(zhàn)。

(1)決策屬性的類型復(fù)雜，決策屬性既有定量的數(shù)值，又有定性的語言評(píng)價(jià)，直接選擇困難。

(2)多個(gè)決策屬性的目標(biāo)和評(píng)價(jià)標(biāo)準(zhǔn)具有差異，使得比較數(shù)據(jù)壓縮算法之間的優(yōu)劣復(fù)雜。算法選擇既包含最大化目標(biāo)(即，最大化存儲(chǔ)提升效果)，也包括最小化目標(biāo)(即，最小化成本和對(duì)系統(tǒng)的影響)，當(dāng)候選算法數(shù)量較多時(shí)，問題求解難度較大。

(3)不同決策屬性的單位量綱和數(shù)量級(jí)存在差異，綜合評(píng)價(jià)困難。

通過分析得出，問題的求解難度由候選算法的規(guī)模及決策屬性的數(shù)量所共同決定，由于決策屬性類型復(fù)雜、單位量綱和數(shù)量級(jí)差異較大，問題求解復(fù)雜。

3.2 問題求解預(yù)處理

為快速求解問題，本文將對(duì)候選算法和決策屬性進(jìn)行預(yù)處理操作，具體包括：過濾劣質(zhì)候選壓縮算法、約簡決策屬性、模糊化表示定性決策屬性、決策屬性歸一化處理。具體描述如下：

預(yù)處理規(guī)則1：假設(shè)有n個(gè)候選壓縮算法L={l1，l2，…，ln}，如果存在壓縮算法lk在歸檔效率A上不能滿業(yè)務(wù)要求(即，滿足ak小于am)，則壓縮算法lk將被淘汰。

預(yù)處理規(guī)則2：假設(shè)有n個(gè)候選壓縮算法L={l1，l2，…，ln}，如果存在一種壓縮算法lk在決策屬性{S、C、T、A、R、I、E}上均劣于其他候選算法，則壓縮算法lk將被淘汰。

預(yù)處理規(guī)則3：假設(shè)經(jīng)過預(yù)處理規(guī)則1和預(yù)處理規(guī)則2處理后，還剩d個(gè)候選壓縮算法，如果d個(gè)候選壓縮算法在某類決策屬性上的取值均相等，則該決策屬性可以被約簡。

通過預(yù)處理規(guī)則1和預(yù)處理規(guī)則2可以淘汰不滿足業(yè)務(wù)要求和在各項(xiàng)指標(biāo)均不好的候選算法。預(yù)處理規(guī)則3可以約簡決策屬性從而提升選擇效率。

為快速求解問題，本文根據(jù)決策屬性的特點(diǎn)，利用文獻(xiàn)[17]中的模糊數(shù)表達(dá)方式來反映定性決策屬性的不同等級(jí)。假設(shè)決策屬性有q個(gè)等級(jí)，則第j個(gè)等級(jí)對(duì)應(yīng)的三角模糊數(shù)可由公式2表示，其中，等級(jí)越高則決策屬性越好。

(1)

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

(2)

于是回取效率R、可靠性影響程度I、存儲(chǔ)提升效果E可由下列三角模糊數(shù)來表示，具體如表2所示。

表2 定性決策屬性的三角模糊數(shù)表示

經(jīng)過以上預(yù)處理操作，所有決策屬性均被量化表示?？紤]到?jīng)Q策屬性在量綱和數(shù)量級(jí)上的差異，本文利用向量規(guī)范法[18]對(duì)實(shí)數(shù)、區(qū)間數(shù)、三角模糊數(shù)決策屬性進(jìn)行歸一化處理。假設(shè)經(jīng)過預(yù)處理后還剩d個(gè)候選算法，則任意候選算法i對(duì)實(shí)數(shù)、區(qū)間數(shù)、三角模糊數(shù)決策屬性的歸一化方法如下：

(3)

(4)

(5)

(6)

(7)

(8)

3.3 快速求解問題步驟

為實(shí)現(xiàn)問題的快速求解，本文通過下列步驟來完成數(shù)據(jù)壓縮算法選擇。其基本思想是首先利用預(yù)處理規(guī)則淘汰候選算法集合中的劣解，并約簡剩余算法的決策屬性。然后，分析剩余候選算法和決策屬性的數(shù)量，根據(jù)其取值，采用不同的策略對(duì)算法進(jìn)行選擇。假設(shè)有n個(gè)候選壓縮算法L={l1，l2，…，ln}，則算法選擇的具體步驟如下：

(1)分析候選壓縮算法L的歸檔效率，利用預(yù)處理規(guī)則1刪除ak小于am的候選算法，形成新的候選壓縮算法集合L1。若L1中剩余候選算法唯一，則該算法就是問題的最優(yōu)解，否則轉(zhuǎn)步驟(2)。

(2)依次比較L1中的候選算法，利用預(yù)處理規(guī)則2淘汰在各個(gè)決策屬性上均劣于其他的候選算法，形成新的候選壓縮算法集合L2。若L2剩余候選算法唯一，則該算法就是問題的最優(yōu)解，否則轉(zhuǎn)步驟(3)。

(3)利用預(yù)處理規(guī)則3約簡L2的決策屬性，若經(jīng)約簡后決策屬性個(gè)數(shù)m滿足m=1，則該問題已成為單目標(biāo)決策問題，可直接比較剩余決策屬性求解，否則轉(zhuǎn)步驟(4)。

(4)利用公式(3)-(8)對(duì)L2的剩余決策屬性進(jìn)行歸一化處理獲得規(guī)范化矩陣W，再轉(zhuǎn)步驟(5)。其中，剩余決策屬性個(gè)數(shù)m滿足1

(9)

(5)通過專家評(píng)估當(dāng)前決策屬性的重要程度，獲得屬性權(quán)重Y={y1,y2,…,ym}，利用公式(10)計(jì)算加權(quán)規(guī)范矩陣H再轉(zhuǎn)步驟(6)，其中權(quán)重Y的和為1。

(10)

4 用例分析

為提升數(shù)據(jù)歸檔系統(tǒng)應(yīng)對(duì)海量數(shù)據(jù)的能力，歸檔業(yè)務(wù)人員初步選擇了4種候選數(shù)據(jù)壓縮算法，經(jīng)過測(cè)試評(píng)估獲得4種候選算法在成本、對(duì)系統(tǒng)處理能力的影響、對(duì)系統(tǒng)可靠性的影響和系統(tǒng)存儲(chǔ)能力提升效果等評(píng)估情況，具體見表3。

表3 候選算法的評(píng)估情況

為選擇最優(yōu)算法，用例首先利用預(yù)處理規(guī)則1和預(yù)處理規(guī)則2淘汰候選算法的劣解，利用預(yù)處理規(guī)則3約簡決策屬性。由于剩余候選算法和其決策屬性均不唯一，所以用三角模糊數(shù)表示候選算法的定性決策屬性，然后由專家評(píng)估剩余決策屬性的重要程度后形成下列決策屬性及權(quán)重情況，具體見表4。

表4 候選算法的決策屬性及權(quán)重情況

根據(jù)表4用例經(jīng)過歸一化處理后獲得規(guī)范化矩陣W。

依照決策屬性的權(quán)重情況計(jì)算加權(quán)規(guī)范矩陣H。

根據(jù)H確定正理想解向量A+和負(fù)理想解向量A-，并計(jì)算每個(gè)算法到其距離。

A+=[0.207005977, (0.091168461, 0.141421356, 0.222834406)

(0.245769576,0.333711906,0.455842306)]

A-=[0.151804383, (0.045584231,0.084852814,0.148556271)

(0.163846384,0.238365647,0.341881729)]

表5 候選算法的相對(duì)貼近度

根據(jù)各個(gè)候選算法到正理想解的相對(duì)貼近度，用例將選擇壓縮算法3來提升歸檔系統(tǒng)的存儲(chǔ)能力。

5 結(jié) 語

本文針對(duì)海量數(shù)據(jù)歸檔系統(tǒng)數(shù)據(jù)壓縮算法選擇問題，綜合考慮算法成本、歸檔業(yè)務(wù)要求、對(duì)系統(tǒng)處理能力和可靠性的影響，以及系統(tǒng)存儲(chǔ)能力的提升效果等因素進(jìn)行建模，并設(shè)計(jì)相應(yīng)的方法選擇最優(yōu)數(shù)據(jù)壓縮算法。最后通過用例展示了數(shù)據(jù)壓縮算法的選擇過程。