[發(fā)明專利]使用索引劃分和協(xié)調(diào)來進(jìn)行數(shù)據(jù)去重復(fù)

有效

• 申請(qǐng)?zhí)枺?/td>: 201110445282.2
• 申請(qǐng)日: 2011-12-27
• 公開（公告）號(hào): CN102591946B
• 公開（公告）日: 2018-06-12
• 發(fā)明（設(shè)計(jì)）人: J·李;S·森古普塔;R·卡拉赫;R·N·德塞;P·A·奧爾泰安;J·R·本頓
• 申請(qǐng)（專利權(quán)）人: 微軟技術(shù)許可有限責(zé)任公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 上海專利商標(biāo)事務(wù)所有限公司 31100
• 代理人: 陳斌

本發(fā)明涉及使用索引劃分和協(xié)調(diào)來進(jìn)行數(shù)據(jù)去重復(fù)。所公開的主題涉及將散列索引服務(wù)的索引劃分為子空間索引的數(shù)據(jù)去重復(fù)技術(shù)，其中少于整個(gè)散列索引服務(wù)的索引被高速緩存以節(jié)省存儲(chǔ)器。該子空間索引被訪問以確定數(shù)據(jù)塊是否已經(jīng)存在或需要被索引和存儲(chǔ)。可基于與要索引的數(shù)據(jù)相關(guān)聯(lián)的準(zhǔn)則(諸如文件類型、數(shù)據(jù)類型、最后使用時(shí)間等)將該索引分成各個(gè)子空間。還描述了子空間協(xié)調(diào)，其中檢測(cè)子空間中的重復(fù)條目以從該去重復(fù)系統(tǒng)中移除條目和塊。子空間協(xié)調(diào)可在非高峰時(shí)間、當(dāng)更多系統(tǒng)資源可用時(shí)執(zhí)行，而如果需要資源則可中斷協(xié)調(diào)。要協(xié)調(diào)的子空間可以基于相似度，包括簽名的相似度，每個(gè)簽名緊湊地表示該子空間的散列。

技術(shù)領(lǐng)域

本發(fā)明涉及使用索引劃分和協(xié)調(diào)進(jìn)行數(shù)據(jù)去重復(fù)。

背景技術(shù)

數(shù)據(jù)去重復(fù)(有時(shí)也稱為數(shù)據(jù)優(yōu)化)指的是減少需要被存儲(chǔ)在磁盤上或通過網(wǎng)絡(luò)進(jìn)行傳送的數(shù)據(jù)的物理字節(jié)量，而不會(huì)損害原始數(shù)據(jù)的保真性和完整性，即字節(jié)上的減少是無損的并且原始數(shù)據(jù)可被完全恢復(fù)。通過減少存儲(chǔ)和/或傳送數(shù)據(jù)所需的資源，數(shù)據(jù)去重復(fù)因此導(dǎo)致(用于存儲(chǔ)和網(wǎng)絡(luò)傳輸?shù)?硬件成本以及數(shù)據(jù)管理成本(例如，備份)的節(jié)約。隨著數(shù)字存儲(chǔ)的數(shù)據(jù)的數(shù)量增長(zhǎng)，這些成本節(jié)約變得重要。

數(shù)據(jù)去重復(fù)通常使用用于消除持久存儲(chǔ)的文件內(nèi)部及其之間的冗余性的技術(shù)的組合。一種技術(shù)用于標(biāo)識(shí)一個(gè)或多個(gè)文件中的數(shù)據(jù)的相同區(qū)域，并在物理上只存儲(chǔ)一個(gè)唯一區(qū)域(塊)，而與文件相關(guān)聯(lián)地維持對(duì)該塊的指針。另一技術(shù)是例如通過存儲(chǔ)經(jīng)壓縮的塊來將數(shù)據(jù)去重復(fù)與壓縮混合。

為了標(biāo)識(shí)這些塊，存儲(chǔ)這些塊的服務(wù)器維持在該系統(tǒng)中這些塊的散列的散列索引服務(wù)。散列不具有位置性(locality)，即，同一個(gè)文件中的各塊的塊散列是不相關(guān)的，對(duì)于給定塊的內(nèi)容的任何編輯創(chuàng)建非常不同的(不相關(guān)的)散列值。因此，傳統(tǒng)的數(shù)據(jù)庫(kù)技術(shù)，諸如B樹索引，導(dǎo)致索引服務(wù)較差的性能。在存儲(chǔ)器中維持整個(gè)索引提供較好的性能，但是耗費(fèi)太多資源。服務(wù)器存儲(chǔ)器資源為其他服務(wù)器應(yīng)用(如，在主數(shù)據(jù)去重復(fù)情形中)所需要，且用于高速緩存。

之前的面向備份的數(shù)據(jù)去重復(fù)優(yōu)化依靠前瞻高速緩存(look-ahead cache)來減少在服務(wù)器上訪問該索引所使用的資源量。然而，數(shù)據(jù)去重復(fù)不再受限于數(shù)據(jù)備份的情形，且發(fā)展為像其他存儲(chǔ)器設(shè)備那樣被用作被訪問的主數(shù)據(jù)存儲(chǔ)器群集。僅使用前瞻高速緩存來減少資源使用并不是適當(dāng)?shù)慕鉀Q方案。

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

提供本發(fā)明內(nèi)容以便以簡(jiǎn)化形式介紹將在以下的具體實(shí)施方式中進(jìn)一步描述的一些代表性概念。本發(fā)明內(nèi)容不旨在標(biāo)識(shí)出所要求保護(hù)的主題的關(guān)鍵特征或必要特征，也不旨在以限制所要求保護(hù)的主題的范圍的任何方式來使用。

簡(jiǎn)言之，此處所描述的主題的各方面涉及去重復(fù)技術(shù)，通過該去重復(fù)技術(shù)將散列索引服務(wù)的索引劃分為各個(gè)子空間索引，以使得一次將少于散列索引服務(wù)的所索引的數(shù)據(jù)集的整個(gè)范圍加載到存儲(chǔ)器中，從而節(jié)省可用存儲(chǔ)器。

當(dāng)要被去重復(fù)的數(shù)據(jù)被接收并分塊(chunk)，并且有可能還被壓縮時(shí)，子空間索引確定對(duì)該塊計(jì)算的散列值是否與主存儲(chǔ)器(例如，RAM)高速緩存中的條目的散列值相匹配。如果是，則返回可用于定位現(xiàn)有塊的信息，否則該塊作為新塊存儲(chǔ)在塊存儲(chǔ)中，并且對(duì)應(yīng)于該散列值的條目與對(duì)該塊的引用相關(guān)聯(lián)地被添加到該子空間索引。

在一方面，可基于一個(gè)或多個(gè)準(zhǔn)則來將散列索引服務(wù)劃分成多個(gè)子空間索引，該準(zhǔn)則可與要被去重復(fù)的數(shù)據(jù)如何劃分相對(duì)應(yīng)。示例分割/劃分準(zhǔn)則包括數(shù)據(jù)的文件類型、數(shù)據(jù)類型、位置、創(chuàng)建該數(shù)據(jù)的應(yīng)用、文件使用模式數(shù)據(jù)、文件訪問模式數(shù)據(jù)、文件所有者、文件用戶類型、名字空間、文件內(nèi)容、文件元數(shù)據(jù)、學(xué)習(xí)到的準(zhǔn)則或自適應(yīng)準(zhǔn)則、或可被推斷為該文件的特征的任何其他類型的信息、以及這些的任何組合。