[發(fā)明專利]使用索引劃分和協(xié)調(diào)來(lái)進(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
• 代理人: 陳斌

1.一種用于數(shù)據(jù)去重復(fù)的方法，包括：

將與子空間相關(guān)聯(lián)的子空間索引(P₁-P_m)從輔助介質(zhì)加載到主存儲(chǔ)器高速緩存中，所述子空間索引包括的索引條目少于散列索引服務(wù)(116)的所有索引條目；

基于簽名相似度將所述子空間與另一子空間進(jìn)行協(xié)調(diào)以移除所述子空間與所述另一子空間之間的至少一個(gè)重復(fù)的索引條目，包括使用相似性度量來(lái)確定所述子空間和所述另一子空間之間的簽名相似度；以及

使用所述子空間索引來(lái)對(duì)數(shù)據(jù)進(jìn)行去重復(fù)，包括將所述數(shù)據(jù)分塊(504)為一個(gè)或多個(gè)塊，以及對(duì)于每個(gè)塊，確定(510)為所述塊計(jì)算的散列值是否與所述主存儲(chǔ)器高速緩存中的索引條目的散列值相匹配，并且如果不匹配，則存儲(chǔ)(518)所述塊并與對(duì)所述塊的引用相關(guān)聯(lián)地將對(duì)應(yīng)于所述散列值的索引條目添加(518)到所述子空間索引中，而如果匹配，則返回(512)能夠用于定位現(xiàn)有的塊的信息。

2.如權(quán)利要求1所述的方法，其特征在于，還包括：將另一子空間索引的至少一部分加載到所述主存儲(chǔ)器高速緩存中，或者基于一個(gè)或多個(gè)準(zhǔn)則將所述散列索引服務(wù)劃分為多個(gè)子空間索引，或者基于將要被去重復(fù)的數(shù)據(jù)的一個(gè)或多個(gè)準(zhǔn)則將所述數(shù)據(jù)劃分為多個(gè)數(shù)據(jù)集，以及將所述散列索引服務(wù)劃分為與所述多個(gè)數(shù)據(jù)集相對(duì)應(yīng)的多個(gè)子空間索引，或者以下各項(xiàng)的任何組合：將另一子空間索引的至少一部分加載到所述主存儲(chǔ)器高速緩存中，或者基于一個(gè)或多個(gè)準(zhǔn)則將所述散列索引服務(wù)劃分為多個(gè)子空間索引，或者基于將要被去重復(fù)的數(shù)據(jù)的一個(gè)或多個(gè)準(zhǔn)則將所述數(shù)據(jù)劃分為多個(gè)數(shù)據(jù)集，以及將所述散列索引服務(wù)劃分為與所述多個(gè)數(shù)據(jù)集相對(duì)應(yīng)的多個(gè)子空間索引。

3.如權(quán)利要求1所述的方法，其特征在于，返回能夠用于定位現(xiàn)有的塊的信息包括返回塊標(biāo)識(shí)符，或返回所述散列值以及所述子空間的標(biāo)識(shí)符，其中所述塊標(biāo)識(shí)符包括對(duì)與所述索引條目相關(guān)聯(lián)的塊的引用。

4.如權(quán)利要求1所述的方法，其特征在于，還包括：基于表示所述子空間的至少一個(gè)簽名以及表示所述另一子空間的至少一個(gè)簽名之間的相似度來(lái)選擇要協(xié)調(diào)的所述另一子空間。

5.一種用于數(shù)據(jù)去重復(fù)的系統(tǒng)，包括：

用于將與子空間相關(guān)聯(lián)的子空間索引(P₁-P_m)從輔助介質(zhì)加載到主存儲(chǔ)器高速緩存中的裝置，所述子空間索引包括的索引條目少于散列索引服務(wù)(116)的所有索引條目；

用于基于簽名相似度將所述子空間與另一子空間進(jìn)行協(xié)調(diào)以移除所述子空間與所述另一子空間之間的至少一個(gè)重復(fù)的索引條目的裝置，包括使用相似性度量來(lái)確定所述子空間和所述另一子空間之間的簽名相似度；以及

用于使用所述子空間索引來(lái)對(duì)數(shù)據(jù)進(jìn)行去重復(fù)的裝置，所述對(duì)數(shù)據(jù)進(jìn)行去重復(fù)包括將所述數(shù)據(jù)分塊(504)為一個(gè)或多個(gè)塊，以及對(duì)于每個(gè)塊，確定(510)為所述塊計(jì)算的散列值是否與所述主存儲(chǔ)器高速緩存中的索引條目的散列值相匹配，并且如果不匹配，則存儲(chǔ)(518)所述塊并與對(duì)所述塊的引用相關(guān)聯(lián)地將對(duì)應(yīng)于所述散列值的索引條目添加(518)到所述子空間索引中，而如果匹配，則返回(512)能夠用于定位現(xiàn)有的塊的信息。

6.如權(quán)利要求5所述的系統(tǒng)，其特征在于，還包括：用于將另一子空間索引的至少一部分加載到所述主存儲(chǔ)器高速緩存中，或者基于一個(gè)或多個(gè)準(zhǔn)則將所述散列索引服務(wù)劃分為多個(gè)子空間索引，或者基于將要被去重復(fù)的數(shù)據(jù)的一個(gè)或多個(gè)準(zhǔn)則將所述數(shù)據(jù)劃分為多個(gè)數(shù)據(jù)集的裝置，以及用于將所述散列索引服務(wù)劃分為與所述多個(gè)數(shù)據(jù)集相對(duì)應(yīng)的多個(gè)子空間索引的裝置，或者用于以下各項(xiàng)的任何組合的裝置：將另一子空間索引的至少一部分加載到所述主存儲(chǔ)器高速緩存中，或者基于一個(gè)或多個(gè)準(zhǔn)則將所述散列索引服務(wù)劃分為多個(gè)子空間索引，或者基于將要被去重復(fù)的數(shù)據(jù)的一個(gè)或多個(gè)準(zhǔn)則將所述數(shù)據(jù)劃分為多個(gè)數(shù)據(jù)集，以及將所述散列索引服務(wù)劃分為與所述多個(gè)數(shù)據(jù)集相對(duì)應(yīng)的多個(gè)子空間索引。

7.如權(quán)利要求5所述的系統(tǒng)，其特征在于，用于返回能夠用于定位現(xiàn)有的塊的信息的裝置包括用于返回塊標(biāo)識(shí)符，或返回所述散列值以及所述子空間的標(biāo)識(shí)符的裝置，其中所述塊標(biāo)識(shí)符包括對(duì)與所述索引條目相關(guān)聯(lián)的塊的引用。