[發(fā)明專利]一種面向可變長數(shù)據(jù)塊的快速檢索方法

有效

• 申請?zhí)枺?/td>: 202110424974.2
• 申請日: 2021-04-20
• 公開（公告）號: CN113495901B
• 公開（公告）日: 2023-10-13
• 發(fā)明（設(shè)計）人: 徐振楠;呂鑫;吳濤;高晟凱
• 申請（專利權(quán)）人: 河海大學(xué);華能瀾滄江水電股份有限公司;網(wǎng)聯(lián)清算有限公司
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/22;G06F3/06
• 代理公司: 南京縱橫知識產(chǎn)權(quán)代理有限公司 32224
• 代理人: 凌雋宇

本發(fā)明公開了一種面向可變長數(shù)據(jù)塊的快速檢索方法，包括提取數(shù)據(jù)塊長度及部分位置字節(jié)值；構(gòu)建索引樹；計算并比對數(shù)據(jù)塊指紋等步驟；本發(fā)明通過提取可變長的數(shù)據(jù)塊的長度和字節(jié)構(gòu)建索引，實現(xiàn)了先檢索沖突再計算指紋的檢索方式，從而減少指紋計算的過程，提高檢索效率。

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

本發(fā)明涉及數(shù)據(jù)存儲技術(shù)領(lǐng)域，特別涉及一種面向可變長數(shù)據(jù)塊的快速檢索方法。

背景技術(shù)

衡量重復(fù)數(shù)據(jù)刪除能力的一個重要指標(biāo)為系統(tǒng)開銷，系統(tǒng)開銷主要包括指紋計算的開銷和指紋檢索的開銷。在存儲系統(tǒng)中，隨著時間的遷移，所存儲的數(shù)據(jù)會越來越大，此時指紋檢索與比對不僅會占用大量的計算資源，同時也會提高磁盤IO，導(dǎo)致檢索效率降低。因此，檢索效率優(yōu)化是降低系統(tǒng)開銷的主要手段。

檢索效率優(yōu)化目前主要借助的手段有布隆過濾器快速判斷、利用數(shù)據(jù)的局部性預(yù)先加載數(shù)據(jù)、利用數(shù)據(jù)的相似性構(gòu)建分層索引、根據(jù)存儲介質(zhì)的不同優(yōu)化索引結(jié)構(gòu)、根據(jù)存儲的數(shù)據(jù)類型進(jìn)行優(yōu)化索引結(jié)構(gòu)等。

目前，重復(fù)數(shù)據(jù)檢索方式主要是：先計算數(shù)據(jù)塊指紋，然后比對指紋索引表，判斷數(shù)據(jù)塊是否重復(fù)。但是，數(shù)據(jù)塊的指紋一般采用安全哈希函數(shù)如SHA256、SHA-3等，而先計算指紋則會占用大量的計算時間。

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

本發(fā)明的目的在于提出一種面向可變長數(shù)據(jù)塊的快速檢索方法，通過提取可變長的數(shù)據(jù)塊的長度和字節(jié)構(gòu)建索引，實現(xiàn)先檢索沖突再計算指紋的檢索方式，從而減少指紋計算的過程，提高檢索效率。

本發(fā)明采用的技術(shù)方案是：

一種面向可變長數(shù)據(jù)塊的快速檢索方法，包括以下步驟：

步驟S1、讀取一個待檢索的可變長數(shù)據(jù)塊組；

步驟S2.1、輸入一個所述可變長數(shù)據(jù)塊組的數(shù)據(jù)塊；

步驟S2.2、若當(dāng)前輸入為空，則輸出判斷結(jié)果并終止檢索，否則提取當(dāng)前數(shù)據(jù)塊的長度L以及部分位置的字節(jié)值A(chǔ)0、A1、A2、…；

步驟S3、將當(dāng)前數(shù)據(jù)塊長度映射到[0,255]區(qū)間上，并以映射后的值作為索引樹的第一個子節(jié)點，構(gòu)建索引樹；

步驟S4、計算數(shù)據(jù)塊指紋，再比對指紋，將數(shù)據(jù)塊信息添加為當(dāng)前節(jié)點的子節(jié)點，返回步驟S1。

進(jìn)一步的，所述步驟S3，具體為：

步驟S3.1、計算K＝min(L,65536)mod 256，其中，K表示將當(dāng)前數(shù)據(jù)塊長度映射到[0,255]區(qū)間上的值，L表示數(shù)據(jù)塊長度，min(L,65536)表示取L與65536中較小值，用于將長度超過64KB的數(shù)據(jù)塊劃分為同一子節(jié)點，mod表示取模運算；

步驟S3.2、依次以K，A0，A1，A2，…為鍵，構(gòu)建索引樹S-K-A0-A1-A2-…，其中，S表示索引樹的根節(jié)點。

進(jìn)一步的，所述步驟S4，具體為：

步驟S4.1、若當(dāng)前索引下無其他數(shù)據(jù)塊，則當(dāng)前檢測的數(shù)據(jù)塊為唯一塊，返回步驟S2；否則，進(jìn)入步驟S4.2；

步驟S4.2、分別計算當(dāng)前索引下未計算指紋的數(shù)據(jù)塊的指紋和當(dāng)前檢測的數(shù)據(jù)塊的指紋；

步驟S4.3、將當(dāng)前檢測的數(shù)據(jù)塊指紋與索引下其他數(shù)據(jù)塊指紋比對，若存在，則當(dāng)前檢測的數(shù)據(jù)塊為重復(fù)塊，否則為非重復(fù)塊；

步驟S4.4、將數(shù)據(jù)塊信息添加為當(dāng)前節(jié)點的子節(jié)點，返回步驟S2。

進(jìn)一步的，所述數(shù)據(jù)塊指紋為數(shù)據(jù)塊的安全哈希函數(shù)值。

進(jìn)一步的，所述提取的部分位置字節(jié)值定義為第1個字節(jié)值、最后1個字節(jié)值、第[L/2]個字節(jié)值、第2ⁿ個字節(jié)值，其中，L表示數(shù)據(jù)塊長度，n為自然數(shù)且2ⁿ≤L。