基于貪婪算法的網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法

熊國棟

（荊楚理工學(xué)院計(jì)算機(jī)工程學(xué)院 湖北 荊門 448000）

0 引言

在網(wǎng)絡(luò)數(shù)據(jù)集成化的背景下，數(shù)據(jù)量增長的規(guī)模日益壯大，因此對應(yīng)的數(shù)據(jù)分級儲存方法也面臨著更多挑戰(zhàn)[1]。異端服務(wù)器存儲的模式，會對網(wǎng)絡(luò)數(shù)據(jù)管理的權(quán)限造成影響[2]。分級儲存方式則能夠更好地實(shí)現(xiàn)負(fù)載均衡，實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)資源調(diào)度。在傳統(tǒng)的存儲模式中對單機(jī)服務(wù)器的容量性能要求較高，一旦出現(xiàn)站點(diǎn)失效等故障則整個平臺的集群存儲模式也將遭到破壞。此外，利用外接擴(kuò)容的方式無法滿足網(wǎng)絡(luò)數(shù)據(jù)的分級儲存需求。

袁志琴等[3]通過歐式距離對數(shù)據(jù)進(jìn)行空間劃分，利用空間數(shù)據(jù)區(qū)域生長的方法解決數(shù)據(jù)密度聚類問題，采用規(guī)則對簇進(jìn)行合并，實(shí)現(xiàn)數(shù)據(jù)的分級聚類。黃永生[4]采用模糊綜合評價法評價數(shù)據(jù)價值，根據(jù)價值評估結(jié)果，通過固定閾值法和高低水位法實(shí)現(xiàn)數(shù)據(jù)分級與儲存。但上述方法在進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)分級存儲的過程中，是分別將數(shù)據(jù)分配到網(wǎng)絡(luò)節(jié)點(diǎn)中的，增加了網(wǎng)絡(luò)數(shù)據(jù)檢索的延遲時間，導(dǎo)致時間開銷性能較差。

因此，為解決上述方法存在的不足，本文將貪婪算法應(yīng)用到網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法中，對此展開相關(guān)研究。

1 構(gòu)建網(wǎng)絡(luò)數(shù)據(jù)包捕獲模型

當(dāng)網(wǎng)絡(luò)數(shù)據(jù)途經(jīng)對應(yīng)的計(jì)算機(jī)設(shè)備時，可先在網(wǎng)絡(luò)端口中判斷網(wǎng)絡(luò)數(shù)據(jù)的應(yīng)用價值[5]。再通過額外配置旁路端口的方式，將數(shù)據(jù)包進(jìn)行過濾處理，并按照分級儲存規(guī)則，同時匹配安全數(shù)據(jù)。為了避免數(shù)據(jù)包丟失，結(jié)合貪婪算法，實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)由內(nèi)核態(tài)至用戶態(tài)的轉(zhuǎn)變。在數(shù)據(jù)分級儲存的過程中，零拷貝技術(shù)也能在一定程度上提高數(shù)據(jù)包的處理能力。同時，可以選擇直接從存儲器等設(shè)備中捕獲網(wǎng)絡(luò)數(shù)據(jù)包，并開設(shè)切換緩存區(qū)的通道，在途經(jīng)緩沖區(qū)后自行將數(shù)據(jù)發(fā)送到存儲空間[6]。在此基礎(chǔ)上，數(shù)據(jù)包捕獲間隔的表達(dá)式為

式（1）中：?為數(shù)據(jù)包間隔大小；r為網(wǎng)絡(luò)編碼塊要素的空間分布面積；δ為網(wǎng)絡(luò)數(shù)據(jù)集合。當(dāng)出現(xiàn)創(chuàng)建新資源需求時，可以通過數(shù)據(jù)讀寫的方式創(chuàng)建原始數(shù)據(jù)的副本，并在多個端口之間進(jìn)行數(shù)據(jù)共享[7]。對于規(guī)模較大的數(shù)據(jù)包，則可以選擇二次分割。出于捕獲數(shù)據(jù)包的目的將存儲操作的分類，編寫步驟推遲到最后歸類的環(huán)節(jié)。為了減少分級儲存對網(wǎng)絡(luò)資源的消耗，需要保證數(shù)據(jù)本身的應(yīng)用態(tài)和內(nèi)核態(tài)不遭受破壞。因此要想實(shí)現(xiàn)物理層與應(yīng)用層之間的跨級儲存，應(yīng)處理好數(shù)據(jù)幀與網(wǎng)絡(luò)節(jié)點(diǎn)之間的關(guān)系。在應(yīng)用層中創(chuàng)建一個虛擬空間，并通過直接關(guān)聯(lián)的方式，以傳輸協(xié)議作為通信介質(zhì)，將網(wǎng)絡(luò)數(shù)據(jù)包的特征，映射到虛擬空間中[8]。

2 基于貪婪算法優(yōu)化緩存替換流程

貪婪算法主要是通過動態(tài)規(guī)劃的方式進(jìn)行求解，但最終得出的結(jié)果有可能是最優(yōu)選擇的近似解。在實(shí)際的應(yīng)用場景中，貪婪算法往往能夠依據(jù)當(dāng)時的實(shí)際情況，得出解決當(dāng)下問題的最佳結(jié)果。將貪婪算法應(yīng)用在此次網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法的設(shè)計(jì)中，主要是希望能夠得出優(yōu)化緩存替換流程的最優(yōu)解[9]。緩存替換步驟，通常出現(xiàn)在數(shù)據(jù)包傳輸?shù)牧髁康头鍟r段，而對于緩存替換的標(biāo)準(zhǔn)，基本都是網(wǎng)絡(luò)數(shù)據(jù)的儲存容量接近飽和的狀態(tài)。針對不必要替換的網(wǎng)絡(luò)數(shù)據(jù)，則可以略過緩存放置環(huán)節(jié)，直接進(jìn)行數(shù)據(jù)內(nèi)容交付。網(wǎng)絡(luò)數(shù)據(jù)存在緩存替換需求的具體體現(xiàn)，主要是現(xiàn)有網(wǎng)絡(luò)數(shù)據(jù)存在數(shù)據(jù)缺失或者生命周期達(dá)到閾值等情況。在有限的儲存容量條件下，選取合適的緩存替換位置是十分重要的。在分級儲存的場景中，不僅要考慮儲存空間的容量，還要滿足網(wǎng)絡(luò)數(shù)據(jù)對節(jié)點(diǎn)分配屬性的要求。由于網(wǎng)絡(luò)數(shù)據(jù)通常包含相應(yīng)的內(nèi)容流行度，該指標(biāo)能夠直接地體現(xiàn)出網(wǎng)絡(luò)數(shù)據(jù)源需要分級儲存的概率。網(wǎng)絡(luò)數(shù)據(jù)包的流行度計(jì)算公式為

式（2）中：H為網(wǎng)絡(luò)數(shù)據(jù)包緩存替換請求次數(shù)；η為網(wǎng)絡(luò)數(shù)據(jù)包；L為替換請求的總次數(shù)。假設(shè)式（2）的計(jì)算服從齊夫定律分布條件，可將式（2）修改為

式（3）中：T為網(wǎng)絡(luò)數(shù)據(jù)包被用戶（ε）請求訪問的概率；μ為網(wǎng)絡(luò)數(shù)據(jù)包流行度的偏斜率；σ為緩存替換速率。而作為數(shù)據(jù)統(tǒng)計(jì)的關(guān)鍵環(huán)節(jié)，內(nèi)容流行度也集中體現(xiàn)了網(wǎng)絡(luò)數(shù)據(jù)的實(shí)際價值。面對活躍度較高的動態(tài)緩存替換請求，需要額外掌握網(wǎng)絡(luò)數(shù)據(jù)包的衰弱路徑及時變特性。在不同的緩存位置條件下，還要結(jié)合數(shù)據(jù)包的捕獲速率，及時優(yōu)化更新緩存替換流程。基于上描述，完成利用貪婪算法優(yōu)化緩存替換流程的步驟。

3 設(shè)計(jì)數(shù)據(jù)分級儲存模式

網(wǎng)絡(luò)數(shù)據(jù)分級儲存，主要就是指在2個及以上的服務(wù)器節(jié)點(diǎn)中進(jìn)行分級儲存。同時，為了最大限度地降低總服務(wù)器的調(diào)度負(fù)擔(dān)，根據(jù)貪婪算法的作用原理，將網(wǎng)絡(luò)數(shù)據(jù)包分割成若干個數(shù)據(jù)集并分別進(jìn)行求解。由于分級儲存的基本原理與分布式存儲具有一定的相似性，因此，在設(shè)計(jì)過程中，需要單獨(dú)提取網(wǎng)絡(luò)數(shù)據(jù)的標(biāo)準(zhǔn)序列。盡管網(wǎng)絡(luò)數(shù)據(jù)的分級儲存位置，不需要與全部的本地節(jié)點(diǎn)相關(guān)聯(lián)，但為了保證數(shù)據(jù)的完整性，還應(yīng)采用網(wǎng)絡(luò)連接的方式設(shè)置網(wǎng)絡(luò)數(shù)據(jù)的讀取通道。同時，出于對儲存空間的負(fù)載均衡性能考慮，如果有數(shù)據(jù)刪除或?qū)傩孕薷牡男枰鸵粩嗵嵘齼Υ娌呗缘募夯潭取Ｒ宰钚』旨墐Υ嫜訒r為目的，針對不同規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)，分別設(shè)立具有獨(dú)立性能的儲存策略。在網(wǎng)絡(luò)數(shù)據(jù)的分級儲存方法中，部分儲存設(shè)備具有相似的運(yùn)行代碼，因此，能夠小范圍地實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)共享。但在相似數(shù)據(jù)源提取的過程中，一旦網(wǎng)絡(luò)節(jié)點(diǎn)出現(xiàn)了數(shù)據(jù)信息交換的現(xiàn)象，就會在無形中增加信令開銷。即便是最終得出了其他層級網(wǎng)絡(luò)數(shù)據(jù)儲存狀態(tài)，也無法以標(biāo)準(zhǔn)形式呈現(xiàn)給其他節(jié)點(diǎn)。在這種情況下就要根據(jù)貪婪算法的最優(yōu)子結(jié)構(gòu)特性，去判斷網(wǎng)絡(luò)數(shù)據(jù)的貪心選擇特性。將網(wǎng)絡(luò)數(shù)據(jù)的分級儲存看作是待解決地輸入問題，并假設(shè)在實(shí)際儲存場景中，儲存設(shè)備的容量無法滿足需求，則得出解決該問題的時間：

式（4）中：k為貪婪算法中的任意常數(shù)；β為節(jié)點(diǎn)數(shù)量；g為分級儲存空間容量集合。將式（4）看作是一個ILP（information leak prevention，信息泄露防護(hù)）問題，得出貪婪算法動態(tài)規(guī)劃路徑：

式（5）中：d為網(wǎng)絡(luò)數(shù)據(jù)的大小；e為儲存設(shè)備的背包容量。通常情況下，網(wǎng)絡(luò)數(shù)據(jù)的儲存節(jié)點(diǎn)所在位置，主要是依據(jù)相鄰節(jié)點(diǎn)的空間信息決定。在此過程中，網(wǎng)絡(luò)數(shù)據(jù)的分級儲存端口，向距離最近的服務(wù)器發(fā)出連接請求。基于此，完成設(shè)計(jì)數(shù)據(jù)分級儲存模式的步驟。

4 實(shí)驗(yàn)分析

4.1 搭建實(shí)驗(yàn)環(huán)境

由于本文設(shè)計(jì)的網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法涉及服務(wù)器和數(shù)據(jù)分層存儲平臺，因此對實(shí)驗(yàn)環(huán)境配置要求較高。根據(jù)實(shí)驗(yàn)需求，搭建實(shí)驗(yàn)環(huán)境：3臺內(nèi)存為16 G及以上的服務(wù)器，硬盤容量不得低于1 TB。CPU選擇INTEL Xeon、操作系統(tǒng)為Ubuntu，配備DPDK-stable和Hadoop 2.7.2及以上版本。在實(shí)驗(yàn)開始之前，要首先保證文中的網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法能夠檢測到完整的數(shù)據(jù)存儲協(xié)議，且錯誤率小于1%。

4.2 實(shí)驗(yàn)結(jié)果

為了能夠得出此次設(shè)計(jì)網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法的開銷性能，分別選取面向變尺度密度數(shù)據(jù)的分級聚類算法與基于大數(shù)據(jù)分析的負(fù)載平衡數(shù)據(jù)分級存儲方法作為對比方法，與文中的網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法進(jìn)行對比測試。由于網(wǎng)絡(luò)中數(shù)量是從16～8 192不等，出于均衡角度考慮，將實(shí)驗(yàn)條件中的數(shù)據(jù)塊數(shù)量設(shè)置為1 024，以生成Merkle樹延遲開銷時間、數(shù)據(jù)完整性認(rèn)證開銷時間與網(wǎng)絡(luò)數(shù)據(jù)檢索延遲開銷實(shí)踐作為測試指標(biāo)，對比3種網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法的時間開銷性能。生成Merkle樹延遲開銷時間見表1，數(shù)據(jù)完整性認(rèn)證開銷時間見表2，網(wǎng)絡(luò)數(shù)據(jù)檢索延遲開銷時間見表3。

表1 生成Merkle樹延遲開銷時間 單位：ms

表2 數(shù)據(jù)完整性認(rèn)證開銷時間 單位：ms

表3 網(wǎng)絡(luò)數(shù)據(jù)檢索延遲開銷時間 單位：ms

由表1可知，在數(shù)據(jù)塊數(shù)量為1 024時，本文設(shè)計(jì)的網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法，以及另外2種方法生成Merkle樹的平均延遲時間分別為：616.268、899.378、899.030 ms。由此看出，本文設(shè)計(jì)方法的延遲開銷時間最短。這是由于本文設(shè)計(jì)方法在生成Merkle樹開銷方面，將Merkle樹中包含的葉子節(jié)點(diǎn)看作是數(shù)據(jù)碎片，可以根據(jù)實(shí)驗(yàn)數(shù)據(jù)，推測出網(wǎng)絡(luò)數(shù)據(jù)與緩存命中率之間的關(guān)系。

由表2可知，本文設(shè)計(jì)的網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法，以及另外2種方法的數(shù)據(jù)完整性認(rèn)證平均時間分別為：21.780、40.882、49.550 ms。由此看出，本文設(shè)計(jì)方法的數(shù)據(jù)完整性認(rèn)證開銷時間最短，基于大數(shù)據(jù)分析的負(fù)載平衡數(shù)據(jù)分級存儲方法次之，面向變尺度密度數(shù)據(jù)的分級聚類算法最差。說明在驗(yàn)證數(shù)據(jù)完整性層面，設(shè)計(jì)的網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法性能最佳。

由表3可知，本文設(shè)計(jì)的網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法，以及另外2種方法的網(wǎng)絡(luò)數(shù)據(jù)檢索平均延遲時間分別為：51.131、71.511、69.991 ms。說明本文設(shè)計(jì)方法的網(wǎng)絡(luò)數(shù)據(jù)檢索延遲開銷時間最短，數(shù)據(jù)分級儲存效果較好。

5 結(jié)語

綜上所述，面對大量網(wǎng)絡(luò)數(shù)據(jù)在分級儲存時存在時間開銷過大的問題，本文以貪婪算法為技術(shù)基礎(chǔ)，構(gòu)建網(wǎng)絡(luò)數(shù)據(jù)包捕獲模型，優(yōu)化緩存替換流程，設(shè)計(jì)新的數(shù)據(jù)分級儲存模式，完成基于貪婪算法的網(wǎng)絡(luò)數(shù)據(jù)分級儲存方法的設(shè)計(jì)。并通過實(shí)驗(yàn)驗(yàn)證了設(shè)計(jì)方法的延遲開銷時間較短，數(shù)據(jù)完整性認(rèn)證開銷時間較短，網(wǎng)絡(luò)數(shù)據(jù)檢索延遲開銷時間較短，能夠解決網(wǎng)絡(luò)數(shù)據(jù)分級儲存過程中時間開銷過大的問題，數(shù)據(jù)分級儲存效果較好，具有較好的實(shí)際應(yīng)用性能。本文方法的設(shè)計(jì)拓寬了貪婪算法的應(yīng)用場景，同時也豐富了數(shù)據(jù)處理領(lǐng)域的研究成果。未來將把更多的精力放在數(shù)據(jù)處理權(quán)限方面，爭取在專業(yè)方向取得更高的成就。