基于彈性并發(fā)的文件校驗(yàn)?zāi)Ｐ廷?/h1>
2020-01-15 06:45:30阮曉龍于冠軍
計(jì)算機(jī)系統(tǒng)應(yīng)用 2020年1期
阮曉龍,于冠軍
1(河南中醫(yī)藥大學(xué) 信息技術(shù)學(xué)院,鄭州 450046)
2(鄭州祺石信息技術(shù)有限公司,鄭州 450008)
互聯(lián)網(wǎng)+時(shí)代下,數(shù)字資源的數(shù)量和種類呈現(xiàn)出爆發(fā)性的增長(zhǎng)趨勢(shì),數(shù)字資源的存儲(chǔ)規(guī)模日漸巨大[1].數(shù)字資源獲取過(guò)程中的漏洞、通信傳播過(guò)程中的數(shù)據(jù)丟失、黑客的惡意攻擊等也隨之增多,數(shù)字資源的存儲(chǔ)普遍存在質(zhì)量問(wèn)題[2],如不能快速驗(yàn)證數(shù)字資源的完整性,將極大的降低資源服務(wù)質(zhì)量,甚至帶來(lái)災(zāi)難性的后果.
內(nèi)容服務(wù)商早期在進(jìn)行文件校驗(yàn)時(shí),通常直接使用Hash算法對(duì)文件進(jìn)行計(jì)算,從而判斷其內(nèi)容是否改變.但隨著數(shù)字資源的不斷增大、網(wǎng)絡(luò)的快速發(fā)展,其效率低下、校驗(yàn)存在限制的特性越來(lái)越突出.
目前針對(duì)解決數(shù)字資源問(wèn)題的相關(guān)技術(shù)手段越來(lái)越多,比如:文獻(xiàn)[3]中Long Wang等人針對(duì)流媒體服務(wù)提出采樣驗(yàn)證、本地文件格式檢查、特定編碼協(xié)議語(yǔ)法驗(yàn)證3種文件完整性驗(yàn)證方法;文獻(xiàn)[4,5]中針對(duì)P2P文件提出了延時(shí)計(jì)算、基于Merkel校驗(yàn)的文件驗(yàn)證方法;文獻(xiàn)[6]中方燕飛等人提出基于多層MD5消息摘要,并行計(jì)算的文件完整性校驗(yàn)方法;文獻(xiàn)[7,8]中張永棠等人提出基于粒度抽樣的文件校驗(yàn)方法,在舍棄一定準(zhǔn)確性將校驗(yàn)安全性能控制在可接受范圍內(nèi)的情況下,大幅提升文件校驗(yàn)效率;文獻(xiàn)[9]中李昊宇等人提出基于B+樹(shù)技術(shù),在云存儲(chǔ)環(huán)境下多副本數(shù)據(jù)的完整性驗(yàn)證方案.
以上的研究在校驗(yàn)效率方面均有有較好的提升,但并沒(méi)有與校驗(yàn)準(zhǔn)確性、服務(wù)器性能做到完全兼顧,也沒(méi)有充分考慮到在不同服務(wù)器下的實(shí)際應(yīng)用.針對(duì)現(xiàn)有方案存在的未能兼容服務(wù)器環(huán)境、準(zhǔn)確性與效率等問(wèn)題,本文提出一種彈性快速的文件校驗(yàn)方法,對(duì)存儲(chǔ)的數(shù)字資源進(jìn)行評(píng)估,從而解決數(shù)字資源的質(zhì)量問(wèn)題,提升文件校驗(yàn)速率,保障數(shù)字資源服務(wù)者的效益.
1 文件校驗(yàn)分析
1.1 分析模型
在介紹本文提出的文件校驗(yàn)?zāi)Ｐ椭?首先需要清楚文件校驗(yàn)耗時(shí)的組成,具體如式(1)所示.
對(duì)于文件來(lái)說(shuō),一次校驗(yàn)耗費(fèi)時(shí)間由文件讀取耗費(fèi)的總時(shí)間t′以及文件Hash計(jì)算耗費(fèi)的總時(shí)間t′′組成,兩者綜合起來(lái)就是決定文件校驗(yàn)耗費(fèi)時(shí)間的主要因素.
在對(duì)文件進(jìn)行Hash計(jì)算時(shí),CPU核心處理能力越好、CPU使用率越高,計(jì)算耗費(fèi)時(shí)間也就越短.但在進(jìn)行Hash計(jì)算的同時(shí)要充分考慮到服務(wù)器的磁盤(pán)I/O效率,一般來(lái)說(shuō)主要通過(guò)磁盤(pán)I/O、內(nèi)存等方式實(shí)現(xiàn)文件的讀取,毫無(wú)疑問(wèn)放在內(nèi)存中進(jìn)行處理是最優(yōu)的選擇,然而對(duì)于大文件來(lái)說(shuō),無(wú)法通過(guò)內(nèi)存映射文件的方式將其直接放置,這時(shí)就需要將文件進(jìn)行切分處理,從而使并發(fā)計(jì)算成為可能.
1.2 分布式校驗(yàn)支持
對(duì)于分布式存儲(chǔ)系統(tǒng)來(lái)說(shuō),其存放資源可能是碎片化、重復(fù)性的,通過(guò)調(diào)配系統(tǒng)將這些資源進(jìn)行集中調(diào)配,為文件校驗(yàn)處理引擎添加校驗(yàn)任務(wù);文件校驗(yàn)引擎根據(jù)派發(fā)的任務(wù),按照校驗(yàn)?zāi)Ｐ瓦M(jìn)行文件校驗(yàn),并將結(jié)果回寫(xiě)至調(diào)配系統(tǒng),從而完成文件的校驗(yàn).本文主要闡明文件校驗(yàn)的算法模型,關(guān)于分布式多系統(tǒng)調(diào)配的業(yè)務(wù)邏輯在此不再做進(jìn)一步的介紹.本文全部實(shí)驗(yàn)均是在單臺(tái)服務(wù)器環(huán)境下進(jìn)行,通過(guò)優(yōu)化單個(gè)節(jié)點(diǎn)的執(zhí)行效率,從而提升整個(gè)系統(tǒng)的運(yùn)行性能.
2 文件完整性校驗(yàn)方法
2.1 文件校驗(yàn)原理
基于上述文件完整性校驗(yàn)方法,綜合其優(yōu)缺點(diǎn),本文提出基于彈性并發(fā)的文件校驗(yàn)?zāi)Ｐ?對(duì)于待校驗(yàn)文件f,將其分為m個(gè)數(shù)據(jù)塊,對(duì)m個(gè)數(shù)據(jù)塊同時(shí)進(jìn)行多并發(fā)切割計(jì)算,然后判斷切割后的數(shù)據(jù)塊是否超出限制長(zhǎng)度l,如果超出則繼續(xù)進(jìn)行遞歸切割計(jì)算,否則直接進(jìn)行Hash計(jì)算,最終得到結(jié)果值為a1;比對(duì)a1、文件隱藏屬性記錄值a2、數(shù)據(jù)庫(kù)記錄值a3三方是否完全相同,若相同則說(shuō)明文件正確,不同則表示該文件已被篡改,其算法流程如圖1所示.
圖1 并發(fā)文件校驗(yàn)算法流程示意圖
本模型使用彈性并發(fā)計(jì)算資源文件,其耗費(fèi)時(shí)間主要由并發(fā)讀取文件耗費(fèi)最長(zhǎng)時(shí)間t′、計(jì)算耗費(fèi)最長(zhǎng)時(shí)間t′′所決定,其具體耗費(fèi)時(shí)間計(jì)算如式(2)、式(3)所示.
其中,n為遞歸次數(shù),tr為每次遞歸切割讀取文件塊所耗費(fèi)的最長(zhǎng)時(shí)間,tj為每次遞歸切割計(jì)算文件塊所耗費(fèi)的最長(zhǎng)時(shí)間.因此,并發(fā)校驗(yàn)文件耗費(fèi)總時(shí)間的計(jì)算公式如式(4)所示.
本文進(jìn)行文件校驗(yàn)時(shí),通過(guò)指針對(duì)待處理文件進(jìn)行讀取,每次讀取指定長(zhǎng)度l,然后將其轉(zhuǎn)存至內(nèi)存中進(jìn)行計(jì)算,計(jì)算完畢則自動(dòng)釋放內(nèi)存,直至全部計(jì)算結(jié)束,因此內(nèi)存占用會(huì)維持在l*并發(fā)數(shù)(以下定義為i)左右.
在操作系統(tǒng)中進(jìn)程是其管理單位,線程則是進(jìn)程的管理單位.不管是在單線程還是多線程中,每個(gè)線程都有一個(gè)程序計(jì)數(shù)器、一組寄存器、堆棧.進(jìn)程進(jìn)行切換的實(shí)質(zhì)就是被中止運(yùn)行進(jìn)程與待運(yùn)行進(jìn)程上下文的切換,在進(jìn)程未占用處理器時(shí),進(jìn)程的上下文存儲(chǔ)在進(jìn)程的私有堆棧中[10].這就像多個(gè)同學(xué)要分時(shí)間使用同一張實(shí)驗(yàn)桌,所謂要回收正在使用同學(xué)的使用權(quán),就是讓其把屬于自己的東西拿走;而賦予某個(gè)同學(xué)實(shí)驗(yàn)桌使用權(quán),只不過(guò)就是讓他把自己的東西放到實(shí)驗(yàn)桌上罷了[11].
與進(jìn)程切換不同,線程的切換開(kāi)銷則小很多,只需要保存和恢復(fù)線程的寄存器內(nèi)存,棧的切換也是通過(guò)寄存器的切換來(lái)完成的.由此可見(jiàn)線程的切換比進(jìn)程的切換代價(jià)要低很多,因此本文使用單進(jìn)程多線程的方式進(jìn)行文件并發(fā)校驗(yàn).
2.2 最優(yōu)并發(fā)數(shù)量
當(dāng)進(jìn)程、線程的乘積大于等于設(shè)備總CPU核心數(shù)時(shí),其處理效率是相對(duì)最優(yōu)的.這是因?yàn)檫M(jìn)程需要一些資源(CPU使用時(shí)間、存儲(chǔ)器、I/O設(shè)備等)才能進(jìn)行工作,且為依序逐一進(jìn)行,也就是說(shuō)每個(gè)CPU核心任何時(shí)間僅能運(yùn)行一項(xiàng)進(jìn)程.因此并發(fā)數(shù)為CPU核心數(shù)時(shí),即可達(dá)到最優(yōu)的程序執(zhí)行效率.繼續(xù)增加并發(fā)數(shù),執(zhí)行效率會(huì)持續(xù)提升,多余的并發(fā)線程將排隊(duì)等待被執(zhí)行.由于本文讀取文件會(huì)占用一定的時(shí)間,為了使CPU始終處于工作狀態(tài),并發(fā)線程數(shù)最好是CPU核心數(shù)的兩倍,最大并發(fā)處理量每次應(yīng)不超過(guò)磁盤(pán)I/O的瓶頸,同時(shí)應(yīng)充分考慮服務(wù)器內(nèi)存容量等資源.
本文使用MD5計(jì)算算法以512 bit為最小單位,因此CPU核心的每個(gè)計(jì)算量應(yīng)為512 bit的倍數(shù),綜合考慮服務(wù)器磁盤(pán)I/O、計(jì)算損耗,每次切割計(jì)算的文件大小不易設(shè)置過(guò)大,應(yīng)根據(jù)業(yè)務(wù)處理實(shí)際情況進(jìn)行設(shè)置,本文將其初始值設(shè)定為10 MB.設(shè)定讀取長(zhǎng)度為l(10 MB),CPU核心數(shù)為c,內(nèi)存容量為m,讀取長(zhǎng)度l、并發(fā)數(shù)i的初始值計(jì)算方法如式(5)、式(6)所示.
當(dāng)內(nèi)存容量m大于2*c*l時(shí),并發(fā)數(shù)i為CPU核心數(shù)的兩倍;當(dāng)m大于等于c*l且小于等于2*c*l時(shí),并發(fā)數(shù)i為c;當(dāng)m小于c*l時(shí),并發(fā)數(shù)i為m除以l的向下整數(shù)商值.因此在進(jìn)行并發(fā)計(jì)算時(shí)首先應(yīng)得到待校驗(yàn)文件大小,當(dāng)其大小不超過(guò)10 MB時(shí)直接進(jìn)行Hash計(jì)算,超過(guò)時(shí)先得到服務(wù)器CPU核心數(shù)量、內(nèi)存容量,然后按照公式創(chuàng)建對(duì)應(yīng)數(shù)量的并發(fā)執(zhí)行文件校驗(yàn).對(duì)于CPU來(lái)說(shuō)每顆核心都要處理10 MB左右大小的數(shù)據(jù),一直遞歸執(zhí)行直到全部計(jì)算完畢為止.
3 實(shí)驗(yàn)結(jié)果與分析
3.1 實(shí)驗(yàn)環(huán)境
本次實(shí)驗(yàn)服務(wù)器資源配置如表1所示.
表1 服務(wù)器配置信息
為排除其它因素對(duì)本次實(shí)驗(yàn)的影響,此次實(shí)驗(yàn)僅保留原生的操作系統(tǒng),不安裝任何軟件/服務(wù)/組件(測(cè)試程序除外),最大程度的減少實(shí)驗(yàn)影響因素.
3.2 實(shí)驗(yàn)結(jié)果
本文提出的文件校驗(yàn)算法模型可根據(jù)服務(wù)器環(huán)境自動(dòng)彈性設(shè)置參數(shù),為驗(yàn)證其靈活性及通用性,本次實(shí)驗(yàn)采用不同存儲(chǔ)規(guī)模的文件進(jìn)行驗(yàn)證,一是使用小文件(1 GB以下)進(jìn)行算法模型驗(yàn)證,二是使用大文件(10 GB)進(jìn)行驗(yàn)證.
通過(guò)實(shí)驗(yàn),得出MD5計(jì)算耗時(shí)是線性變化的,文件越大耗費(fèi)時(shí)間越長(zhǎng),使用傳統(tǒng)MD5校驗(yàn)與本文校驗(yàn)?zāi)Ｐ蛯?duì)比測(cè)試,其實(shí)驗(yàn)結(jié)果如圖2所示.
圖2 傳統(tǒng)MD5與本文校驗(yàn)?zāi)Ｐ陀?jì)算耗時(shí)對(duì)比圖
從圖2可以看出傳統(tǒng)MD5計(jì)算文件大小與耗費(fèi)時(shí)間呈正比關(guān)系,耗費(fèi)時(shí)間隨著文件的增大而線性增加,由于MD5自身以及服務(wù)器內(nèi)存等實(shí)驗(yàn)環(huán)境因素的影響,當(dāng)待校驗(yàn)文件超過(guò)1 GB之后耗費(fèi)時(shí)間遞增,因此以下實(shí)驗(yàn)進(jìn)行對(duì)比時(shí)使用其理論值做比較,實(shí)驗(yàn)結(jié)果如圖3所示.
圖3 傳統(tǒng)MD5理論值與本文校驗(yàn)?zāi)Ｐ陀?jì)算耗時(shí)對(duì)比圖
從上述實(shí)驗(yàn)結(jié)果來(lái)看,當(dāng)待校驗(yàn)文件大小不超過(guò)600 MB時(shí),傳統(tǒng)MD5校驗(yàn)方式比本文校驗(yàn)?zāi)Ｐ秃臅r(shí)要短,這是因?yàn)閷?shí)驗(yàn)時(shí)本文校驗(yàn)?zāi)Ｐ桶宋募懈睢?nèi)存轉(zhuǎn)存等開(kāi)銷.當(dāng)待校驗(yàn)文件超過(guò)600 MB后,本文校驗(yàn)?zāi)Ｐ团c傳統(tǒng)的MD5串行計(jì)算對(duì)比,其計(jì)算效率明顯提高.
下面從服務(wù)器資源占用方面對(duì)其進(jìn)行分析,進(jìn)行文件校驗(yàn)時(shí)本文校驗(yàn)?zāi)Ｐ头?wù)器資源占用情況如表2所示.
從表2中可以看出CPU使用率逐步增高直至穩(wěn)定,內(nèi)存占用大小從c*l左右直至升高到c*l*2左右,其內(nèi)存占用率很低CPU利用率很高,而待校驗(yàn)文件比較小時(shí)CPU利用率比較低,這是由于文件切割耗時(shí)較長(zhǎng),導(dǎo)致了整個(gè)校驗(yàn)時(shí)間耗時(shí)較長(zhǎng).
表2 本文校驗(yàn)?zāi)Ｐ头?wù)器資源占用情況
在小文件處理上本文校驗(yàn)?zāi)Ｐ拖啾扔趥鹘y(tǒng)MD5校驗(yàn)耗時(shí)更長(zhǎng),但在大文件校驗(yàn)中計(jì)算效率十分明顯.由于實(shí)驗(yàn)環(huán)境條件影響,并無(wú)法做到在上萬(wàn)臺(tái)服務(wù)器上運(yùn)行本文校驗(yàn)?zāi)Ｐ?即便如此,通過(guò)在實(shí)驗(yàn)室CPU內(nèi)存2核4 GB、4核8 GB、8核16 GB、16核16 GB等幾種當(dāng)下常見(jiàn)服務(wù)器配置上的運(yùn)行,也能夠很好的印證上面的結(jié)論.
3.3 實(shí)驗(yàn)分析
對(duì)于文件校驗(yàn)來(lái)說(shuō)其優(yōu)劣主要由結(jié)果的正確性、時(shí)間成本、適應(yīng)性、可移植性、魯棒性這5個(gè)方面決定,通過(guò)這些判斷條件能夠很好的評(píng)估文件校驗(yàn)算法模型是否準(zhǔn)確高效.
本文提出的校驗(yàn)?zāi)Ｐ突贛D5算法進(jìn)行優(yōu)化,其本質(zhì)相當(dāng)于對(duì)待校驗(yàn)文件進(jìn)行了一次完整的MD5計(jì)算,得到最終結(jié)果與事實(shí)復(fù)雜度完全相符.在保持計(jì)算復(fù)雜度不變的前提下,使用并發(fā)計(jì)算能夠大大節(jié)約時(shí)間成本.通過(guò)自適應(yīng)彈性并發(fā),可以變相調(diào)節(jié)服務(wù)器磁盤(pán)I/O占用時(shí)間以及CPU核心占用時(shí)間,其幾乎能適應(yīng)所有規(guī)模的文件校驗(yàn)以及各樣服務(wù)器環(huán)境.通過(guò)采用小批量循環(huán)計(jì)算、自適應(yīng)參數(shù)的方式,確保了服務(wù)器資源占用始終處在正常的范圍內(nèi),不會(huì)因磁盤(pán)I/O占用時(shí)間過(guò)長(zhǎng)或者CPU占用時(shí)間過(guò)長(zhǎng)導(dǎo)致系統(tǒng)出現(xiàn)宕機(jī)或假死情況.
為更好的分析本文校驗(yàn)?zāi)Ｐ?將其與傳統(tǒng)MD5、普通多線程、抽樣校驗(yàn)進(jìn)行對(duì)比,對(duì)比結(jié)果如表3所示.
本文校驗(yàn)?zāi)Ｐ拖鄬?duì)于抽樣校驗(yàn),其執(zhí)行效率并不算高,但其準(zhǔn)確性更高,可將其準(zhǔn)確率等同于傳統(tǒng)MD5校驗(yàn)準(zhǔn)確率.相對(duì)于普通多線程校驗(yàn)其最大的特點(diǎn)就是靈活適配服務(wù)器環(huán)境,有效提升文件校驗(yàn)執(zhí)行效率的同時(shí),兼容各種不同容量規(guī)模的數(shù)字資源.無(wú)論是流式碎片還是虛擬機(jī)導(dǎo)出的超大服務(wù)器備份文件,
即便是在服務(wù)器資源配置十分低下的情況下,也能保證高效的執(zhí)行效率,降低服務(wù)器故障、業(yè)務(wù)無(wú)法正常運(yùn)行的風(fēng)險(xiǎn).
表3 不同文件校驗(yàn)?zāi)Ｐ蛯?duì)比
綜合以上實(shí)驗(yàn)及分析,可以認(rèn)為本文校驗(yàn)?zāi)Ｐ妥赃m應(yīng)能力強(qiáng)、能夠有效的提升執(zhí)行效率.
4 結(jié)論與展望
本文提出的一種基于彈性并發(fā)的高效文件校驗(yàn)算法模型,綜合服務(wù)器磁盤(pán)I/O效率、服務(wù)器CPU處理能力,在將服務(wù)器資源占用控制在正常范圍內(nèi)的同時(shí),充分利用CPU核心計(jì)算資源提高校驗(yàn)效率,對(duì)于存儲(chǔ)的資源文件能夠快速進(jìn)行校驗(yàn),確保其完整性.同時(shí)對(duì)于超大文件,比如1 TB大小的文件,利用小批量循環(huán)切割、讀取、計(jì)算的方式極大的降低磁盤(pán)I/O和內(nèi)存的占用.
本文校驗(yàn)?zāi)Ｐ涂蛇m應(yīng)于各種文件校驗(yàn)場(chǎng)景,假如對(duì)文件校驗(yàn)效率要求比較高,則可以使用抽樣校驗(yàn)+本文校驗(yàn)?zāi)Ｐ?在舍棄一定準(zhǔn)確性的前提下,對(duì)抽樣文件彈性并發(fā)校驗(yàn),更進(jìn)一步地提升其計(jì)算效率;如果對(duì)文件準(zhǔn)確性要求比較高,則可以使用本文校驗(yàn)?zāi)Ｐ?MD5結(jié)構(gòu)改造,由于 MD5 算法本身就具備一定的碰撞特性[12],通過(guò)對(duì)MD結(jié)構(gòu)基礎(chǔ)上的改造,在犧牲一部分處理時(shí)間的前提下,能夠有效規(guī)避MD5碰撞問(wèn)題,保障文件校驗(yàn)的準(zhǔn)確性.
猜你喜歡
一半模型童話王國(guó)·奇妙邏輯推理(2024年5期)2024-06-19 16:03:38 記一次有趣的實(shí)驗(yàn)小獼猴智力畫(huà)刊(2022年9期)2022-11-04 02:31:42 重要模型『一線三等角』中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2020年10期)2020-11-26 08:24:50 提升朗讀教學(xué)效率的幾點(diǎn)思考甘肅教育(2020年14期)2020-09-11 07:57:42 重尾非線性自回歸模型自加權(quán)M-估計(jì)的漸近分布數(shù)學(xué)物理學(xué)報(bào)(2020年2期)2020-06-02 11:29:24 做個(gè)怪怪長(zhǎng)實(shí)驗(yàn)小哥白尼(趣味科學(xué))(2019年6期)2019-10-10 01:01:50 3D打印中的模型分割與打包光學(xué)精密工程(2016年6期)2016-11-07 09:07:19 NO與NO2相互轉(zhuǎn)化實(shí)驗(yàn)的改進(jìn)發(fā)明與創(chuàng)新(2016年38期)2016-08-22 03:02:52 實(shí)踐十號(hào)上的19項(xiàng)實(shí)驗(yàn)太空探索(2016年5期)2016-07-12 15:17:55 跟蹤導(dǎo)練（一）2時(shí)代英語(yǔ)·高二(2015年1期)2015-03-16 00:08:11
阮曉龍,于冠軍
1(河南中醫(yī)藥大學(xué) 信息技術(shù)學(xué)院,鄭州 450046)
2(鄭州祺石信息技術(shù)有限公司,鄭州 450008)
互聯(lián)網(wǎng)+時(shí)代下,數(shù)字資源的數(shù)量和種類呈現(xiàn)出爆發(fā)性的增長(zhǎng)趨勢(shì),數(shù)字資源的存儲(chǔ)規(guī)模日漸巨大[1].數(shù)字資源獲取過(guò)程中的漏洞、通信傳播過(guò)程中的數(shù)據(jù)丟失、黑客的惡意攻擊等也隨之增多,數(shù)字資源的存儲(chǔ)普遍存在質(zhì)量問(wèn)題[2],如不能快速驗(yàn)證數(shù)字資源的完整性,將極大的降低資源服務(wù)質(zhì)量,甚至帶來(lái)災(zāi)難性的后果.
內(nèi)容服務(wù)商早期在進(jìn)行文件校驗(yàn)時(shí),通常直接使用Hash算法對(duì)文件進(jìn)行計(jì)算,從而判斷其內(nèi)容是否改變.但隨著數(shù)字資源的不斷增大、網(wǎng)絡(luò)的快速發(fā)展,其效率低下、校驗(yàn)存在限制的特性越來(lái)越突出.
目前針對(duì)解決數(shù)字資源問(wèn)題的相關(guān)技術(shù)手段越來(lái)越多,比如:文獻(xiàn)[3]中Long Wang等人針對(duì)流媒體服務(wù)提出采樣驗(yàn)證、本地文件格式檢查、特定編碼協(xié)議語(yǔ)法驗(yàn)證3種文件完整性驗(yàn)證方法;文獻(xiàn)[4,5]中針對(duì)P2P文件提出了延時(shí)計(jì)算、基于Merkel校驗(yàn)的文件驗(yàn)證方法;文獻(xiàn)[6]中方燕飛等人提出基于多層MD5消息摘要,并行計(jì)算的文件完整性校驗(yàn)方法;文獻(xiàn)[7,8]中張永棠等人提出基于粒度抽樣的文件校驗(yàn)方法,在舍棄一定準(zhǔn)確性將校驗(yàn)安全性能控制在可接受范圍內(nèi)的情況下,大幅提升文件校驗(yàn)效率;文獻(xiàn)[9]中李昊宇等人提出基于B+樹(shù)技術(shù),在云存儲(chǔ)環(huán)境下多副本數(shù)據(jù)的完整性驗(yàn)證方案.
以上的研究在校驗(yàn)效率方面均有有較好的提升,但并沒(méi)有與校驗(yàn)準(zhǔn)確性、服務(wù)器性能做到完全兼顧,也沒(méi)有充分考慮到在不同服務(wù)器下的實(shí)際應(yīng)用.針對(duì)現(xiàn)有方案存在的未能兼容服務(wù)器環(huán)境、準(zhǔn)確性與效率等問(wèn)題,本文提出一種彈性快速的文件校驗(yàn)方法,對(duì)存儲(chǔ)的數(shù)字資源進(jìn)行評(píng)估,從而解決數(shù)字資源的質(zhì)量問(wèn)題,提升文件校驗(yàn)速率,保障數(shù)字資源服務(wù)者的效益.
1 文件校驗(yàn)分析
1.1 分析模型
在介紹本文提出的文件校驗(yàn)?zāi)Ｐ椭?首先需要清楚文件校驗(yàn)耗時(shí)的組成,具體如式(1)所示.
對(duì)于文件來(lái)說(shuō),一次校驗(yàn)耗費(fèi)時(shí)間由文件讀取耗費(fèi)的總時(shí)間t′以及文件Hash計(jì)算耗費(fèi)的總時(shí)間t′′組成,兩者綜合起來(lái)就是決定文件校驗(yàn)耗費(fèi)時(shí)間的主要因素.
在對(duì)文件進(jìn)行Hash計(jì)算時(shí),CPU核心處理能力越好、CPU使用率越高,計(jì)算耗費(fèi)時(shí)間也就越短.但在進(jìn)行Hash計(jì)算的同時(shí)要充分考慮到服務(wù)器的磁盤(pán)I/O效率,一般來(lái)說(shuō)主要通過(guò)磁盤(pán)I/O、內(nèi)存等方式實(shí)現(xiàn)文件的讀取,毫無(wú)疑問(wèn)放在內(nèi)存中進(jìn)行處理是最優(yōu)的選擇,然而對(duì)于大文件來(lái)說(shuō),無(wú)法通過(guò)內(nèi)存映射文件的方式將其直接放置,這時(shí)就需要將文件進(jìn)行切分處理,從而使并發(fā)計(jì)算成為可能.
1.2 分布式校驗(yàn)支持
對(duì)于分布式存儲(chǔ)系統(tǒng)來(lái)說(shuō),其存放資源可能是碎片化、重復(fù)性的,通過(guò)調(diào)配系統(tǒng)將這些資源進(jìn)行集中調(diào)配,為文件校驗(yàn)處理引擎添加校驗(yàn)任務(wù);文件校驗(yàn)引擎根據(jù)派發(fā)的任務(wù),按照校驗(yàn)?zāi)Ｐ瓦M(jìn)行文件校驗(yàn),并將結(jié)果回寫(xiě)至調(diào)配系統(tǒng),從而完成文件的校驗(yàn).本文主要闡明文件校驗(yàn)的算法模型,關(guān)于分布式多系統(tǒng)調(diào)配的業(yè)務(wù)邏輯在此不再做進(jìn)一步的介紹.本文全部實(shí)驗(yàn)均是在單臺(tái)服務(wù)器環(huán)境下進(jìn)行,通過(guò)優(yōu)化單個(gè)節(jié)點(diǎn)的執(zhí)行效率,從而提升整個(gè)系統(tǒng)的運(yùn)行性能.
2 文件完整性校驗(yàn)方法
2.1 文件校驗(yàn)原理
基于上述文件完整性校驗(yàn)方法,綜合其優(yōu)缺點(diǎn),本文提出基于彈性并發(fā)的文件校驗(yàn)?zāi)Ｐ?對(duì)于待校驗(yàn)文件f,將其分為m個(gè)數(shù)據(jù)塊,對(duì)m個(gè)數(shù)據(jù)塊同時(shí)進(jìn)行多并發(fā)切割計(jì)算,然后判斷切割后的數(shù)據(jù)塊是否超出限制長(zhǎng)度l,如果超出則繼續(xù)進(jìn)行遞歸切割計(jì)算,否則直接進(jìn)行Hash計(jì)算,最終得到結(jié)果值為a1;比對(duì)a1、文件隱藏屬性記錄值a2、數(shù)據(jù)庫(kù)記錄值a3三方是否完全相同,若相同則說(shuō)明文件正確,不同則表示該文件已被篡改,其算法流程如圖1所示.
圖1 并發(fā)文件校驗(yàn)算法流程示意圖
本模型使用彈性并發(fā)計(jì)算資源文件,其耗費(fèi)時(shí)間主要由并發(fā)讀取文件耗費(fèi)最長(zhǎng)時(shí)間t′、計(jì)算耗費(fèi)最長(zhǎng)時(shí)間t′′所決定,其具體耗費(fèi)時(shí)間計(jì)算如式(2)、式(3)所示.
其中,n為遞歸次數(shù),tr為每次遞歸切割讀取文件塊所耗費(fèi)的最長(zhǎng)時(shí)間,tj為每次遞歸切割計(jì)算文件塊所耗費(fèi)的最長(zhǎng)時(shí)間.因此,并發(fā)校驗(yàn)文件耗費(fèi)總時(shí)間的計(jì)算公式如式(4)所示.
本文進(jìn)行文件校驗(yàn)時(shí),通過(guò)指針對(duì)待處理文件進(jìn)行讀取,每次讀取指定長(zhǎng)度l,然后將其轉(zhuǎn)存至內(nèi)存中進(jìn)行計(jì)算,計(jì)算完畢則自動(dòng)釋放內(nèi)存,直至全部計(jì)算結(jié)束,因此內(nèi)存占用會(huì)維持在l*并發(fā)數(shù)(以下定義為i)左右.
在操作系統(tǒng)中進(jìn)程是其管理單位,線程則是進(jìn)程的管理單位.不管是在單線程還是多線程中,每個(gè)線程都有一個(gè)程序計(jì)數(shù)器、一組寄存器、堆棧.進(jìn)程進(jìn)行切換的實(shí)質(zhì)就是被中止運(yùn)行進(jìn)程與待運(yùn)行進(jìn)程上下文的切換,在進(jìn)程未占用處理器時(shí),進(jìn)程的上下文存儲(chǔ)在進(jìn)程的私有堆棧中[10].這就像多個(gè)同學(xué)要分時(shí)間使用同一張實(shí)驗(yàn)桌,所謂要回收正在使用同學(xué)的使用權(quán),就是讓其把屬于自己的東西拿走;而賦予某個(gè)同學(xué)實(shí)驗(yàn)桌使用權(quán),只不過(guò)就是讓他把自己的東西放到實(shí)驗(yàn)桌上罷了[11].
與進(jìn)程切換不同,線程的切換開(kāi)銷則小很多,只需要保存和恢復(fù)線程的寄存器內(nèi)存,棧的切換也是通過(guò)寄存器的切換來(lái)完成的.由此可見(jiàn)線程的切換比進(jìn)程的切換代價(jià)要低很多,因此本文使用單進(jìn)程多線程的方式進(jìn)行文件并發(fā)校驗(yàn).
2.2 最優(yōu)并發(fā)數(shù)量
當(dāng)進(jìn)程、線程的乘積大于等于設(shè)備總CPU核心數(shù)時(shí),其處理效率是相對(duì)最優(yōu)的.這是因?yàn)檫M(jìn)程需要一些資源(CPU使用時(shí)間、存儲(chǔ)器、I/O設(shè)備等)才能進(jìn)行工作,且為依序逐一進(jìn)行,也就是說(shuō)每個(gè)CPU核心任何時(shí)間僅能運(yùn)行一項(xiàng)進(jìn)程.因此并發(fā)數(shù)為CPU核心數(shù)時(shí),即可達(dá)到最優(yōu)的程序執(zhí)行效率.繼續(xù)增加并發(fā)數(shù),執(zhí)行效率會(huì)持續(xù)提升,多余的并發(fā)線程將排隊(duì)等待被執(zhí)行.由于本文讀取文件會(huì)占用一定的時(shí)間,為了使CPU始終處于工作狀態(tài),并發(fā)線程數(shù)最好是CPU核心數(shù)的兩倍,最大并發(fā)處理量每次應(yīng)不超過(guò)磁盤(pán)I/O的瓶頸,同時(shí)應(yīng)充分考慮服務(wù)器內(nèi)存容量等資源.
本文使用MD5計(jì)算算法以512 bit為最小單位,因此CPU核心的每個(gè)計(jì)算量應(yīng)為512 bit的倍數(shù),綜合考慮服務(wù)器磁盤(pán)I/O、計(jì)算損耗,每次切割計(jì)算的文件大小不易設(shè)置過(guò)大,應(yīng)根據(jù)業(yè)務(wù)處理實(shí)際情況進(jìn)行設(shè)置,本文將其初始值設(shè)定為10 MB.設(shè)定讀取長(zhǎng)度為l(10 MB),CPU核心數(shù)為c,內(nèi)存容量為m,讀取長(zhǎng)度l、并發(fā)數(shù)i的初始值計(jì)算方法如式(5)、式(6)所示.
當(dāng)內(nèi)存容量m大于2*c*l時(shí),并發(fā)數(shù)i為CPU核心數(shù)的兩倍;當(dāng)m大于等于c*l且小于等于2*c*l時(shí),并發(fā)數(shù)i為c;當(dāng)m小于c*l時(shí),并發(fā)數(shù)i為m除以l的向下整數(shù)商值.因此在進(jìn)行并發(fā)計(jì)算時(shí)首先應(yīng)得到待校驗(yàn)文件大小,當(dāng)其大小不超過(guò)10 MB時(shí)直接進(jìn)行Hash計(jì)算,超過(guò)時(shí)先得到服務(wù)器CPU核心數(shù)量、內(nèi)存容量,然后按照公式創(chuàng)建對(duì)應(yīng)數(shù)量的并發(fā)執(zhí)行文件校驗(yàn).對(duì)于CPU來(lái)說(shuō)每顆核心都要處理10 MB左右大小的數(shù)據(jù),一直遞歸執(zhí)行直到全部計(jì)算完畢為止.
3 實(shí)驗(yàn)結(jié)果與分析
3.1 實(shí)驗(yàn)環(huán)境
本次實(shí)驗(yàn)服務(wù)器資源配置如表1所示.
表1 服務(wù)器配置信息
為排除其它因素對(duì)本次實(shí)驗(yàn)的影響,此次實(shí)驗(yàn)僅保留原生的操作系統(tǒng),不安裝任何軟件/服務(wù)/組件(測(cè)試程序除外),最大程度的減少實(shí)驗(yàn)影響因素.
3.2 實(shí)驗(yàn)結(jié)果
本文提出的文件校驗(yàn)算法模型可根據(jù)服務(wù)器環(huán)境自動(dòng)彈性設(shè)置參數(shù),為驗(yàn)證其靈活性及通用性,本次實(shí)驗(yàn)采用不同存儲(chǔ)規(guī)模的文件進(jìn)行驗(yàn)證,一是使用小文件(1 GB以下)進(jìn)行算法模型驗(yàn)證,二是使用大文件(10 GB)進(jìn)行驗(yàn)證.
通過(guò)實(shí)驗(yàn),得出MD5計(jì)算耗時(shí)是線性變化的,文件越大耗費(fèi)時(shí)間越長(zhǎng),使用傳統(tǒng)MD5校驗(yàn)與本文校驗(yàn)?zāi)Ｐ蛯?duì)比測(cè)試,其實(shí)驗(yàn)結(jié)果如圖2所示.
圖2 傳統(tǒng)MD5與本文校驗(yàn)?zāi)Ｐ陀?jì)算耗時(shí)對(duì)比圖
從圖2可以看出傳統(tǒng)MD5計(jì)算文件大小與耗費(fèi)時(shí)間呈正比關(guān)系,耗費(fèi)時(shí)間隨著文件的增大而線性增加,由于MD5自身以及服務(wù)器內(nèi)存等實(shí)驗(yàn)環(huán)境因素的影響,當(dāng)待校驗(yàn)文件超過(guò)1 GB之后耗費(fèi)時(shí)間遞增,因此以下實(shí)驗(yàn)進(jìn)行對(duì)比時(shí)使用其理論值做比較,實(shí)驗(yàn)結(jié)果如圖3所示.
圖3 傳統(tǒng)MD5理論值與本文校驗(yàn)?zāi)Ｐ陀?jì)算耗時(shí)對(duì)比圖
從上述實(shí)驗(yàn)結(jié)果來(lái)看,當(dāng)待校驗(yàn)文件大小不超過(guò)600 MB時(shí),傳統(tǒng)MD5校驗(yàn)方式比本文校驗(yàn)?zāi)Ｐ秃臅r(shí)要短,這是因?yàn)閷?shí)驗(yàn)時(shí)本文校驗(yàn)?zāi)Ｐ桶宋募懈睢?nèi)存轉(zhuǎn)存等開(kāi)銷.當(dāng)待校驗(yàn)文件超過(guò)600 MB后,本文校驗(yàn)?zāi)Ｐ团c傳統(tǒng)的MD5串行計(jì)算對(duì)比,其計(jì)算效率明顯提高.
下面從服務(wù)器資源占用方面對(duì)其進(jìn)行分析,進(jìn)行文件校驗(yàn)時(shí)本文校驗(yàn)?zāi)Ｐ头?wù)器資源占用情況如表2所示.
從表2中可以看出CPU使用率逐步增高直至穩(wěn)定,內(nèi)存占用大小從c*l左右直至升高到c*l*2左右,其內(nèi)存占用率很低CPU利用率很高,而待校驗(yàn)文件比較小時(shí)CPU利用率比較低,這是由于文件切割耗時(shí)較長(zhǎng),導(dǎo)致了整個(gè)校驗(yàn)時(shí)間耗時(shí)較長(zhǎng).
表2 本文校驗(yàn)?zāi)Ｐ头?wù)器資源占用情況
在小文件處理上本文校驗(yàn)?zāi)Ｐ拖啾扔趥鹘y(tǒng)MD5校驗(yàn)耗時(shí)更長(zhǎng),但在大文件校驗(yàn)中計(jì)算效率十分明顯.由于實(shí)驗(yàn)環(huán)境條件影響,并無(wú)法做到在上萬(wàn)臺(tái)服務(wù)器上運(yùn)行本文校驗(yàn)?zāi)Ｐ?即便如此,通過(guò)在實(shí)驗(yàn)室CPU內(nèi)存2核4 GB、4核8 GB、8核16 GB、16核16 GB等幾種當(dāng)下常見(jiàn)服務(wù)器配置上的運(yùn)行,也能夠很好的印證上面的結(jié)論.
3.3 實(shí)驗(yàn)分析
對(duì)于文件校驗(yàn)來(lái)說(shuō)其優(yōu)劣主要由結(jié)果的正確性、時(shí)間成本、適應(yīng)性、可移植性、魯棒性這5個(gè)方面決定,通過(guò)這些判斷條件能夠很好的評(píng)估文件校驗(yàn)算法模型是否準(zhǔn)確高效.
本文提出的校驗(yàn)?zāi)Ｐ突贛D5算法進(jìn)行優(yōu)化,其本質(zhì)相當(dāng)于對(duì)待校驗(yàn)文件進(jìn)行了一次完整的MD5計(jì)算,得到最終結(jié)果與事實(shí)復(fù)雜度完全相符.在保持計(jì)算復(fù)雜度不變的前提下,使用并發(fā)計(jì)算能夠大大節(jié)約時(shí)間成本.通過(guò)自適應(yīng)彈性并發(fā),可以變相調(diào)節(jié)服務(wù)器磁盤(pán)I/O占用時(shí)間以及CPU核心占用時(shí)間,其幾乎能適應(yīng)所有規(guī)模的文件校驗(yàn)以及各樣服務(wù)器環(huán)境.通過(guò)采用小批量循環(huán)計(jì)算、自適應(yīng)參數(shù)的方式,確保了服務(wù)器資源占用始終處在正常的范圍內(nèi),不會(huì)因磁盤(pán)I/O占用時(shí)間過(guò)長(zhǎng)或者CPU占用時(shí)間過(guò)長(zhǎng)導(dǎo)致系統(tǒng)出現(xiàn)宕機(jī)或假死情況.
為更好的分析本文校驗(yàn)?zāi)Ｐ?將其與傳統(tǒng)MD5、普通多線程、抽樣校驗(yàn)進(jìn)行對(duì)比,對(duì)比結(jié)果如表3所示.
本文校驗(yàn)?zāi)Ｐ拖鄬?duì)于抽樣校驗(yàn),其執(zhí)行效率并不算高,但其準(zhǔn)確性更高,可將其準(zhǔn)確率等同于傳統(tǒng)MD5校驗(yàn)準(zhǔn)確率.相對(duì)于普通多線程校驗(yàn)其最大的特點(diǎn)就是靈活適配服務(wù)器環(huán)境,有效提升文件校驗(yàn)執(zhí)行效率的同時(shí),兼容各種不同容量規(guī)模的數(shù)字資源.無(wú)論是流式碎片還是虛擬機(jī)導(dǎo)出的超大服務(wù)器備份文件,
即便是在服務(wù)器資源配置十分低下的情況下,也能保證高效的執(zhí)行效率,降低服務(wù)器故障、業(yè)務(wù)無(wú)法正常運(yùn)行的風(fēng)險(xiǎn).
表3 不同文件校驗(yàn)?zāi)Ｐ蛯?duì)比
綜合以上實(shí)驗(yàn)及分析,可以認(rèn)為本文校驗(yàn)?zāi)Ｐ妥赃m應(yīng)能力強(qiáng)、能夠有效的提升執(zhí)行效率.
4 結(jié)論與展望
本文提出的一種基于彈性并發(fā)的高效文件校驗(yàn)算法模型,綜合服務(wù)器磁盤(pán)I/O效率、服務(wù)器CPU處理能力,在將服務(wù)器資源占用控制在正常范圍內(nèi)的同時(shí),充分利用CPU核心計(jì)算資源提高校驗(yàn)效率,對(duì)于存儲(chǔ)的資源文件能夠快速進(jìn)行校驗(yàn),確保其完整性.同時(shí)對(duì)于超大文件,比如1 TB大小的文件,利用小批量循環(huán)切割、讀取、計(jì)算的方式極大的降低磁盤(pán)I/O和內(nèi)存的占用.
本文校驗(yàn)?zāi)Ｐ涂蛇m應(yīng)于各種文件校驗(yàn)場(chǎng)景,假如對(duì)文件校驗(yàn)效率要求比較高,則可以使用抽樣校驗(yàn)+本文校驗(yàn)?zāi)Ｐ?在舍棄一定準(zhǔn)確性的前提下,對(duì)抽樣文件彈性并發(fā)校驗(yàn),更進(jìn)一步地提升其計(jì)算效率;如果對(duì)文件準(zhǔn)確性要求比較高,則可以使用本文校驗(yàn)?zāi)Ｐ?MD5結(jié)構(gòu)改造,由于 MD5 算法本身就具備一定的碰撞特性[12],通過(guò)對(duì)MD結(jié)構(gòu)基礎(chǔ)上的改造,在犧牲一部分處理時(shí)間的前提下,能夠有效規(guī)避MD5碰撞問(wèn)題,保障文件校驗(yàn)的準(zhǔn)確性.
猜你喜歡
童話王國(guó)·奇妙邏輯推理(2024年5期)2024-06-19 16:03:38
小獼猴智力畫(huà)刊(2022年9期)2022-11-04 02:31:42
中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2020年10期)2020-11-26 08:24:50
甘肅教育(2020年14期)2020-09-11 07:57:42
數(shù)學(xué)物理學(xué)報(bào)(2020年2期)2020-06-02 11:29:24
小哥白尼(趣味科學(xué))(2019年6期)2019-10-10 01:01:50
光學(xué)精密工程(2016年6期)2016-11-07 09:07:19
發(fā)明與創(chuàng)新(2016年38期)2016-08-22 03:02:52
太空探索(2016年5期)2016-07-12 15:17:55
時(shí)代英語(yǔ)·高二(2015年1期)2015-03-16 00:08:11
