[發明專利]一種基于全局統計的去碎片方法及系統

有效

• 申請號: 201410089576.X
• 申請日: 2014-03-12
• 公開（公告）號: CN103885859B
• 公開（公告）日: 2017-09-26
• 發明（設計）人: 華宇;馮丹;賴榮譽;夏文;付忞;黃方亭;周玉坤;張宇成
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F11/14
• 分類號: G06F11/14
• 代理公司: 華中科技大學專利中心42201
• 代理人: 梁鵬

技術領域

本發明屬于計算機信息存儲技術領域，更具體地，涉及一種基于全局統計的去碎片方法及系統，主要用于在基于數據去重的云備份系統中實現數據碎片的去除。

背景技術

云備份系統，是使用第三方云存儲服務(如Amazon S3和百度云存儲BCS)代替傳統備份系統的數據中心的一種備份系統。云備份系統將用戶備份的數據存放在第三方的云中，采用第三方的云存儲代替傳統的數據中心有成本低、擴展性強和可靠性高的優勢。隨著云存儲的發展，出現了很多利用第三方云存儲存放數據的備份系統和數據同步工具，且呈越來越流行之勢。

為了能提高數據上傳速度以及節省云存儲成本，大部分云備份系統會采用數據去重技術。數據去重技術能找出備份數據流中的重復數據，這些重復數據不需要被再次存儲，只需要保存對應已存在數據的地址即可。數據去重技術能有效地加快備份速度和節省存儲空間。

由于數據去重技術需要將數據分塊，而默認的平均分塊長度為8KB，若直接以數據塊為單位將數據存儲在云端，會導致數據傳輸效率低下，且會使得存儲請求次數增加，增加云存儲成本(云存儲以請求次數，存儲空間和下載流量計費)。為了提高數據傳輸效率和節省云存儲成本，云備份系統一般將數據塊聚合成段(segment)進行存儲，段長度默認為不大于4MB，在使得段長度大于4MB的那個數據塊寫入前認為段寫滿了。段是系統對云端數據管理的基本單位，系統只能上傳、下載和刪除整個段，而不能下載或者刪除段中的部分數據。

基于重復數據刪除的云備份系統的備份工作過程包括讀數據、分塊、求指紋、去重、寫數據和上傳數據6個步驟。其中分塊之后，使用一定的Hash算法對數據塊求Hash，求得的Hash值就是數據塊的指紋。在去重過程中，使用數據塊的指紋在系統指紋庫中進行查找，若有相同指紋，則說明云端數據中心存在相同的數據塊，即數據塊是重復數據，將數據塊標記為重復數據；否則標記為新數據，且將指紋插入指紋庫中。然后，系統寫數據模塊根據數據塊的去重結果，若是重復數據，則直接保存該重復數據引用的地址；若是新數據則將數據寫入段中，然后保存數據塊地址。最后，上傳數據模塊將段上傳至云端數據中心。

因為數據去重技術使新版本與舊版本共享數據塊，這使得新版本的數據塊分散在各個段中。而且對于一個數據流，重復數據在各個段中的分布長度是不均勻的，有些段中有大量數據被引用，而有些段只有很少量數據被引用。而數據流中存在一些重復數據塊，它們引用的段中被該數據流引用數據量很少，這些重復數據會嚴重影響恢復性能，這是因為為了恢復這些重復數據，需要下載他們引用的段，而這些段中包含大量對此次恢復無效的數據，這些數據會嚴重影響恢復性能。也就是說，隨著版本數的增加，數據流中重復數據的分散程度越來越嚴重，恢復性能會逐漸下降。

發明內容

本發明的目的在于對基于數據去重技術云備份系統中恢復性能隨著版本次數增加而逐漸下降的問題，提出一種去碎片的方法，即找出備份數據流中的數據碎片，并將這些數據碎片和新數據寫入段中，達到去碎片以提高恢復性能的目的。

針對現有技術的以上缺陷或改進需求，本發明提供了一種基于全局統計的去碎片方法，包括以下步驟：

步驟1，確定待備份的數據流中的各重復數據塊，統計各重復數據塊所對應的被引用段中所有被引用數據的長度，得到段引用緩沖區；

步驟2，計算待備份的數據流中的各重復數據塊所對應的被引用段中所有被引用數據的長度與該被引用段的長度的比值，并判斷該比值是否小于設定閾值，若是則將該重復數據塊寫入新建立的段中。

更進一步地，所述步驟1具體包括：

步驟1.1，判斷數據流中的數據塊是否是重復數據，若是則轉入步驟1.2；否則轉入步驟1.5；

步驟1.2，根據該數據塊的引用地址，在段引用緩沖區中查找該數據塊引用地址對應的記錄，若記錄不存在，則轉入步驟1.3；否則轉入步驟1.4；

步驟1.3，在段引用緩沖區中新建記錄，該記錄包括段ID、段長度、被引用數據的長度和段引用率，該記錄的段ID初始化為所述數據塊的引用地址，該記錄的段長度根據所述段ID查詢得到，該記錄的被引用數據的長度初始化為0，該記錄的段引用率初始化為負值；轉入步驟1.4；

步驟1.4，將所述數據塊的長度與該數據塊引用地址對應的記錄的被引用數據的長度相加，并賦值給該數據塊引用地址對應的記錄的被引用數據的長度；轉入步驟1.5；

步驟1.5，將所述數據塊存入去重結果緩沖區中，并判斷數據流中是否還有數據塊，若是則轉入步驟1.1；否則轉入步驟2。