[發(fā)明專(zhuān)利]用于對(duì)網(wǎng)絡(luò)編碼的分布式存儲(chǔ)進(jìn)行重復(fù)數(shù)據(jù)刪除的系統(tǒng)及相關(guān)技術(shù)

有效

• 申請(qǐng)?zhí)枺?/td>: 201880068242.0
• 申請(qǐng)日: 2018-11-08
• 公開(kāi)（公告）號(hào): CN111247509B
• 公開(kāi)（公告）日: 2023-10-24
• 發(fā)明（設(shè)計(jì)）人: M·梅達(dá)爾;P·納拉亞南穆?tīng)柕?/a>;V·阿伯德拉施托夫
• 申請(qǐng)（專(zhuān)利權(quán)）人: 麻省理工學(xué)院
• 主分類(lèi)號(hào): G06F3/06
• 分類(lèi)號(hào): G06F3/06;H04L41/12;H04L61/103;H04L9/40;H04L61/5007;G06F21/62;H04L101/686
• 代理公司: 永新專(zhuān)利商標(biāo)代理有限公司 72002
• 代理人: 劉瑜

提出了用于對(duì)文件進(jìn)行編碼和對(duì)文件的編碼分組進(jìn)行重復(fù)數(shù)據(jù)刪除的方法。編碼方法包括：識(shí)別要被存儲(chǔ)的文件；對(duì)該文件進(jìn)行編碼以生成多個(gè)編碼分組；生成與該文件相關(guān)聯(lián)的散列碼；將多個(gè)編碼分組分發(fā)到多個(gè)存儲(chǔ)節(jié)點(diǎn)；以及將與該文件相關(guān)聯(lián)的散列碼存儲(chǔ)在散列服務(wù)器中。重復(fù)數(shù)據(jù)刪除方法包括：在存儲(chǔ)節(jié)點(diǎn)處接收編碼分組；從散列服務(wù)器取回與編碼分組相對(duì)應(yīng)的散列碼；基于散列碼確定編碼分組是否已被存儲(chǔ)在存儲(chǔ)節(jié)點(diǎn)中；響應(yīng)于編碼分組已被存儲(chǔ)的確定，丟棄編碼分組；以及響應(yīng)于編碼分組尚未被存儲(chǔ)的確定，將編碼分組存儲(chǔ)在存儲(chǔ)節(jié)點(diǎn)中。

背景技術(shù)

如本領(lǐng)域中已知的，分布式存儲(chǔ)系統(tǒng)包括許多節(jié)點(diǎn)，其中可以存儲(chǔ)數(shù)據(jù)或文件。在操作中，可以將要被存儲(chǔ)的數(shù)據(jù)或文件劃分(或“分割”)成多個(gè)片段，這些片段可以被稱(chēng)為分組(在本文中有時(shí)也稱(chēng)為“塊”或“組塊”)。分布式存儲(chǔ)系統(tǒng)中的每個(gè)節(jié)點(diǎn)可以存儲(chǔ)這樣的分組中的一個(gè)或多個(gè)。這樣，可以在多個(gè)不同的存儲(chǔ)節(jié)點(diǎn)之間分發(fā)數(shù)據(jù)或文件。

存儲(chǔ)節(jié)點(diǎn)之間沒(méi)有協(xié)調(diào)來(lái)決定文件或數(shù)據(jù)的哪些片段存儲(chǔ)在哪些節(jié)點(diǎn)中。因此，一個(gè)以上的存儲(chǔ)節(jié)點(diǎn)可以接收具有相同內(nèi)容的分組。

眾所周知，重復(fù)數(shù)據(jù)刪除(de-duplication)是一種壓縮技術(shù)，用于消除存儲(chǔ)系統(tǒng)中存儲(chǔ)的數(shù)據(jù)分組在各種文件上的冗余副本。常規(guī)地，重復(fù)數(shù)據(jù)刪除過(guò)程發(fā)生在“原始”數(shù)據(jù)域中(即，簡(jiǎn)單地比較兩個(gè)文件)。重復(fù)數(shù)據(jù)刪除在所有現(xiàn)代數(shù)據(jù)中心中被執(zhí)行。重復(fù)數(shù)據(jù)刪除軟件經(jīng)常由針對(duì)數(shù)據(jù)中心開(kāi)發(fā)軟件的供應(yīng)商提供。人們經(jīng)常區(qū)分源重復(fù)數(shù)據(jù)刪除和目標(biāo)重復(fù)數(shù)據(jù)刪除。目標(biāo)重復(fù)數(shù)據(jù)刪除在進(jìn)行備份的數(shù)據(jù)中心中被執(zhí)行。考慮到備份的數(shù)據(jù)量，重復(fù)數(shù)據(jù)刪除的效率將在確定操作成本方面發(fā)揮重要作用。

在利用網(wǎng)絡(luò)編碼(例如，隨機(jī)線(xiàn)性網(wǎng)絡(luò)編碼)的分布式存儲(chǔ)系統(tǒng)中，編碼數(shù)據(jù)的片段分布在多個(gè)存儲(chǔ)節(jié)點(diǎn)(即，數(shù)據(jù)中心、服務(wù)器、數(shù)據(jù)存儲(chǔ)系統(tǒng))上。例如，在RAID(獨(dú)立磁盤(pán)冗余陣列)系統(tǒng)中，隨機(jī)線(xiàn)性網(wǎng)絡(luò)碼允許由各種客戶(hù)端對(duì)相同的“數(shù)據(jù)條帶”進(jìn)行不同的編碼。由編碼系數(shù)的不同選擇可以造成客戶(hù)端之間的差異。在這種情況下，當(dāng)存儲(chǔ)系統(tǒng)從不同的客戶(hù)端接收編碼數(shù)據(jù)時(shí)，直接地將任何接收到的數(shù)據(jù)條帶與先前接收到的數(shù)據(jù)條帶進(jìn)行比較的傳統(tǒng)重復(fù)數(shù)據(jù)刪除技術(shù)將失敗，因?yàn)楦鞣N客戶(hù)端使用不同的編碼系數(shù)對(duì)同一條帶進(jìn)行不同的編碼。

解決此問(wèn)題的一個(gè)解決方案是，針對(duì)每個(gè)客戶(hù)端解碼條帶，計(jì)算共同約定的散列函數(shù)，并且在傳輸數(shù)據(jù)分組時(shí)包括散列。然而，這樣的解決方案在客戶(hù)端側(cè)由于額外的計(jì)算需求而產(chǎn)生負(fù)擔(dān)。如果散列函數(shù)帶有安全屬性，則該解決方案也具有安全風(fēng)險(xiǎn)。

另一個(gè)選項(xiàng)是存儲(chǔ)節(jié)點(diǎn)對(duì)其接收到的每個(gè)條帶進(jìn)行解碼，并計(jì)算散列函數(shù)，并且在本地?cái)?shù)據(jù)庫(kù)中搜索匹配。該解決方案的計(jì)算需求也會(huì)給存儲(chǔ)節(jié)點(diǎn)帶來(lái)負(fù)擔(dān)，并且使得此解決方案針對(duì)內(nèi)聯(lián)重復(fù)數(shù)據(jù)刪除策略和后處理重復(fù)數(shù)據(jù)刪除策略都是不切實(shí)際的。

因此，可以看出至少在涉及多個(gè)客戶(hù)端的存儲(chǔ)系統(tǒng)中，出現(xiàn)了針對(duì)在編碼域中進(jìn)行重復(fù)數(shù)據(jù)刪除的需求，其中每個(gè)客戶(hù)端直接將其編碼數(shù)據(jù)(例如，作為例行備份的一部分)卸載到遠(yuǎn)程數(shù)據(jù)中心。如上文所描述的，由于隨機(jī)線(xiàn)性網(wǎng)絡(luò)編碼(RLNC)允許由各種客戶(hù)端對(duì)相同的數(shù)據(jù)條帶進(jìn)行不同的編碼，因此直接將任何接收到的數(shù)據(jù)條帶與先前接收到的數(shù)據(jù)條帶進(jìn)行比較的傳統(tǒng)重復(fù)數(shù)據(jù)刪除技術(shù)失敗。

因此，希望提供一種用于在分布式存儲(chǔ)系統(tǒng)中執(zhí)行重復(fù)數(shù)據(jù)刪除而不要求對(duì)編碼分組進(jìn)行解碼以執(zhí)行重復(fù)數(shù)據(jù)刪除過(guò)程的系統(tǒng)和技術(shù)。

發(fā)明內(nèi)容

在本文描述的概念的一個(gè)方面中，提供了一種散列化系統(tǒng)和技術(shù)，其避免了為了執(zhí)行重復(fù)數(shù)據(jù)刪除而對(duì)每個(gè)接收到的編碼條帶進(jìn)行解碼的需要。

本文描述的散列化技術(shù)避免了為了執(zhí)行重復(fù)數(shù)據(jù)刪除而對(duì)每個(gè)接收到的編碼條帶進(jìn)行解碼的需要，并且因此在實(shí)際實(shí)施方式中可以潛在地節(jié)省大量的計(jì)算資源。

根據(jù)一個(gè)說(shuō)明性實(shí)施例，一種用于對(duì)文件進(jìn)行編碼的方法可以包括：識(shí)別要被存儲(chǔ)的文件；對(duì)該文件進(jìn)行編碼以生成多個(gè)編碼分組；生成與該文件相關(guān)聯(lián)的散列碼；將多個(gè)編碼分組分發(fā)到多個(gè)存儲(chǔ)節(jié)點(diǎn)；以及將與該文件相關(guān)聯(lián)的散列碼存儲(chǔ)在散列服務(wù)器中。