霧計(jì)算作為云中心在網(wǎng)絡(luò)邊緣的延伸,將不需要放在云端的數(shù)據(jù)直接進(jìn)行存儲(chǔ)和處理,從而可以快速響應(yīng)底端設(shè)備的需求。為了解決現(xiàn)有方案中頻繁的磁盤輸入和輸出（I/O）,針對(duì)霧節(jié)點(diǎn)中存儲(chǔ)數(shù)據(jù)的冗余問題,提出重復(fù)數(shù)據(jù)刪除方案（DeFog）。利用紅黑樹的快速查找機(jī)制,在內(nèi)存中構(gòu)建數(shù)據(jù)指紋表,通過二次Hash獲得索引表。固定時(shí)刻刷新內(nèi)存中的指紋表保存在磁盤中,日志文件記錄每次數(shù)據(jù)更新,這樣在系統(tǒng)發(fā)生崩潰機(jī)器重啟時(shí),磁盤中的指紋表會(huì)與日志文件合并構(gòu)建更新后的指紋表。通過在標(biāo)準(zhǔn)數(shù)據(jù)集中的實(shí)驗(yàn)與其他方案進(jìn)行對(duì)比,證明了DeFog在查詢效率上提高了54.1%,運(yùn)行時(shí)間降低了42.1%。 

【文章來源】：計(jì)算機(jī)應(yīng)用與軟件. 2020,37(02)北大核心

【文章頁(yè)數(shù)】：8 頁(yè)

【部分圖文】：

系統(tǒng)結(jié)構(gòu)圖

本文提出的數(shù)據(jù)指紋查詢方案,將完整的指紋表保存于內(nèi)存中,將非重復(fù)數(shù)據(jù)塊置于磁盤中。當(dāng)判斷數(shù)據(jù)指紋是否重復(fù)時(shí),可以直接在內(nèi)存中進(jìn)行查詢,無需磁盤I/O讀取。若指紋表中沒有相同指紋,即為非重復(fù)數(shù)據(jù)塊指紋,插入指紋表中。若指紋表中存在相同指紋,將該指紋的數(shù)據(jù)塊與指紋表中相同指紋對(duì)應(yīng)的數(shù)據(jù)塊的循環(huán)冗余碼(CRC)進(jìn)行比較。如果不同,判斷該數(shù)據(jù)塊為非重復(fù)數(shù)據(jù)塊,保存在該指紋的數(shù)據(jù)塊鏈表中;反之,返回該數(shù)據(jù)塊的地址指針。方案流程如圖2所示。3.2 索引表

通過將數(shù)據(jù)指紋進(jìn)行哈希計(jì)算得到索引值(由0到n構(gòu)成的整數(shù))。將數(shù)據(jù)分成非重疊等分?jǐn)?shù)據(jù)塊b1,b2,…,bn。運(yùn)用MD5哈希算法計(jì)算每個(gè)指紋,f1=h(b1),f2=h(b2),…,fn=h(bn)。將數(shù)據(jù)指紋再次進(jìn)行哈希計(jì)算,得到整數(shù)型索引值,i1=h(f1),i2=h(f2),…,in=h(fn)。用戶查詢?nèi)哂鄶?shù)據(jù)塊時(shí),計(jì)算該數(shù)據(jù)塊的索引值,查詢?cè)撍饕迪碌闹讣y表。遍歷索引表的時(shí)間復(fù)雜度為O(1),索引表如圖3所示。3.3 基于紅黑樹的指紋查詢

【參考文獻(xiàn)】：
期刊論文
[1]海量網(wǎng)絡(luò)文本去重系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 湯建明,寇小強(qiáng).  計(jì)算機(jī)應(yīng)用與軟件. 2018(12)
[2]一種基于重復(fù)數(shù)據(jù)刪除的網(wǎng)絡(luò)文件備份系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J]. 孫愛玲,冉祿純.  計(jì)算機(jī)應(yīng)用與軟件. 2014(10)

碩士論文
[1]霧計(jì)算中邊緣節(jié)點(diǎn)存儲(chǔ)優(yōu)化算法設(shè)計(jì)[D]. 魏茂林.浙江工商大學(xué) 2018
[2]基于網(wǎng)絡(luò)虛擬化的霧計(jì)算設(shè)計(jì)與實(shí)現(xiàn)[D]. 李雅軒.天津大學(xué) 2017



本文編號(hào)：3391297