[發(fā)明專利]一種面向數(shù)據(jù)去重技術(shù)的近似最優(yōu)數(shù)據(jù)碎片塊重寫方法

有效

• 申請?zhí)枺?/td>: 202010748768.2
• 申請日: 2020-07-30
• 公開（公告）號: CN111858574B
• 公開（公告）日: 2022-02-11
• 發(fā)明（設(shè)計）人: 鄧玉輝;張大統(tǒng)
• 申請（專利權(quán)）人: 暨南大學(xué)
• 主分類號: G06F16/215
• 分類號: G06F16/215;G06F9/50
• 代理公司: 廣州市華學(xué)知識產(chǎn)權(quán)代理有限公司 44245
• 代理人: 詹麗紅

1.一種面向數(shù)據(jù)去重技術(shù)的近似最優(yōu)數(shù)據(jù)碎片塊重寫方法，將備份數(shù)據(jù)流劃分為n個數(shù)據(jù)段，每個數(shù)據(jù)段引用若干個容器，每個容器存放1個以上的數(shù)據(jù)塊，數(shù)據(jù)塊分為碎片塊和非碎片塊，其特征在于，所述的重寫方法包括以下步驟：

S1、分配并初始化一塊內(nèi)存空間，其過程如下：

S11、申請分配一塊內(nèi)存空間，將該內(nèi)存空間劃分為多個小內(nèi)存空間，每個小內(nèi)存空間被稱為桶；

S12、按照前后順序依次為每個桶設(shè)置一個綁定值，綁定值由低到高；

S2、初始化i＝1，i＝1,2,…,n，從前i個數(shù)據(jù)段所引用容器中選出最優(yōu)的x個容器，并確定對于數(shù)據(jù)段i的最優(yōu)閾值，過程如下：

S21、計算數(shù)據(jù)段i所引用容器的容器引用率，其中容器引用率表示一個容器被一個數(shù)據(jù)段引用的次數(shù)或頻率；

S22、根據(jù)匹配規(guī)則將數(shù)據(jù)段i所引用的容器放到對應(yīng)的桶中，其中，匹配規(guī)則定義如下：假設(shè)按前后順序有兩個桶A和B，當(dāng)一個容器的容器引用率小于或者等于桶B的綁定值且大于桶A的綁定值時，則判定容器和桶B是匹配的；

S23、從綁定值最低的桶開始遍歷，累加每個桶中存放容器的個數(shù)，直到累加的容器個數(shù)等于x時停止遍歷，所遍歷的容器即為最優(yōu)的x個容器，此時指向的桶的綁定值即為對于數(shù)據(jù)段i的最優(yōu)閾值，對于數(shù)據(jù)段i所引用的容器，若容器引用率小于或等于該最優(yōu)閾值，則為最優(yōu)容器，否則，為次優(yōu)容器；

S3、在數(shù)據(jù)段i所引用的容器中選出部分容器，并重寫這些容器中存放的碎片塊，過程如下：

S31、若采用最優(yōu)重寫策略，選出數(shù)據(jù)段i所引用容器中的最優(yōu)容器，并重寫所選容器中存放的碎片塊；

S32、若采用激進(jìn)重寫策略，選出數(shù)據(jù)段i所引用容器中的最優(yōu)容器后，再選出y個次優(yōu)容器，并重寫所選容器中存放的碎片塊，其中y小于或者等于數(shù)據(jù)段i所引用的次優(yōu)容器的個數(shù)；

S33、返回步驟S21，處理數(shù)據(jù)段i+1，直到完成所有數(shù)據(jù)段的處理。

2.根據(jù)權(quán)利要求1所述的一種面向數(shù)據(jù)去重技術(shù)的近似最優(yōu)數(shù)據(jù)碎片塊重寫方法，其特征在于，根據(jù)策略切換閾值thres選擇所采用的重寫策略，其中thres表示容器的個數(shù)，默認(rèn)情況下使用最優(yōu)重寫策略，當(dāng)containers_select-containers_handlethres時，切換到激進(jìn)重寫策略，其中containers_select表示當(dāng)前累計選擇容器的個數(shù)，containers_handle表示當(dāng)前累計處理容器的個數(shù)，其中處理容器指的是重寫容器中存放的碎片塊。

3.根據(jù)權(quán)利要求1所述的一種面向數(shù)據(jù)去重技術(shù)的近似最優(yōu)數(shù)據(jù)碎片塊重寫方法，其特征在于，所述的內(nèi)存空間為一個哈希桶數(shù)組，數(shù)組元素為哈希桶，即小內(nèi)存空間。

4.根據(jù)權(quán)利要求3所述的一種面向數(shù)據(jù)去重技術(shù)的近似最優(yōu)數(shù)據(jù)碎片塊重寫方法，其特征在于，所述的哈希桶存放容器，是邏輯上的存放，即哈希桶只是用來記錄匹配該哈希桶的累計容器個數(shù)，并不是真實的存放容器。

5.根據(jù)權(quán)利要求1所述的一種面向數(shù)據(jù)去重技術(shù)的近似最優(yōu)數(shù)據(jù)碎片塊重寫方法，其特征在于，x的取值規(guī)則如下：x＝acml-cap*i，其中acml表示前i個數(shù)據(jù)段累計引用容器的個數(shù)，cap為一個預(yù)先設(shè)置的值，表示容器的個數(shù)。

6.根據(jù)權(quán)利要求1所述的一種面向數(shù)據(jù)去重技術(shù)的近似最優(yōu)數(shù)據(jù)碎片塊重寫方法，其特征在于，y的取值規(guī)則如下：y小于或者等于數(shù)據(jù)段i所引用的次優(yōu)容器的個數(shù)；同時還需滿足條件：y≤(sum-cap-z)，其中sum表示該數(shù)據(jù)段i引用容器的個數(shù)，cap為一個預(yù)先設(shè)置的值，表示容器的個數(shù)，z表示數(shù)據(jù)段i所引用的最優(yōu)容器的個數(shù)。