[發明專利]一種車輛物聯網云存儲系統重復數據刪除方法

在審

• 申請號: 202010950313.9
• 申請日: 2020-09-11
• 公開（公告）號: CN112115108A
• 公開（公告）日: 2020-12-22
• 發明（設計）人: 朱東杰;胡浩;王大方;楊博文;王興成;李旭;黃奐奇
• 申請（專利權）人: 哈爾濱工業大學（威海）;蘇州玄盾汽車科技有限公司
• 主分類號: G06F16/174
• 分類號: G06F16/174;G06F16/13
• 代理公司: 威海科星專利事務所 37202
• 代理人: 宋立國

一種車輛物聯網云存儲系統重復數據刪除方法，涉及信息存儲領域，步驟如下：將固定窗口置于未分塊的起始位置，滑動窗口尋找不小于極大值的字節作為分塊點、生成塊指紋Chunk_fp；記錄滑動窗口內極大值和分塊長度Size_Chunk；重復a、b，直至分塊完成；依次排列三元組數據、建立三元組列表，三元組數據為Size_Chunk+1為下一分塊長度；當有新的數據流輸入時，執行步驟a，在三元組列表中尋找具有相同塊指紋的三元組數據，找到時，將三元組列表中自具有相同塊指紋的三元組數據起向后的各三元組數據中的Size_Chunk+1依次作為對新輸入的數據流分塊的字節長度，對新輸入的數據流進行分塊，直至分塊完成；未找到時，更新三元組列表；本發明分塊速度快，系統數據吞吐率高。

技術領域

本發明涉及信息存儲領域，是一種降低系統資源額外開銷、加快分塊速度，保障重復數據刪除率的同時提高系統數據吞吐率的車輛物聯網云存儲系統重復數據刪除方法。

背景技術

隨著車輛網技術的飛速發展，汽車車輛可以使用車輛網絡與其他公共設施交換相關信息，并將這些信息上傳至云端進行存儲。不同設備之間存在大量的冗余數據，這些數據存儲已經成為云存儲中的嚴峻挑戰。而重復數據刪除技術是一種通過檢測消除冗余數據的技術，已經被廣泛應用于云存儲中。重復數據刪除可以檢測出冗余數據，消除并存儲唯一副本。

塊級重復數據刪除技術將文件分為多個數據塊，對每個塊進行哈希處理(例如MD5,SHA-1,SHA-256)，形成指紋(即哈希摘要)，將其作為唯一塊標識。如果兩個數據塊有相同的指紋，則不予存儲，否則將存儲唯一數據塊。

雖然塊級重復數據刪除系統可以檢測更多的冗余數據，但是需要更多的計算時間，成為了塊級重復數據刪除技術的瓶頸。原因在于塊級重復數據刪除技術分為以下四個階段:(1) 分塊、(2)生成指紋、(3)指紋索引查找、(4)存儲數據；分塊和指紋索引查找占據了塊級重復數據刪除的大部分時間，成為了日益嚴峻的挑戰。目前主流的分塊算法分為固定分塊算法和基于內容分塊算法。固定分塊算法將文件或數據流分割成統一長度的數據塊，優點是計算開銷小，系統數據吞吐率高，但其存在內容偏移、重復數據檢測率低的缺陷，例如，如果在文件的內部任意位置添加或刪除一個字節，所有的塊邊界可能都發生改變，這將影響塊邊界的界定，無法在少量修改的重復文件中找到重復數據塊。而基于內容分塊算法可以有效解決塊偏移問題，算法將滿足預定條件的字節作為塊邊界；基于內容分塊算法可比固定大小分塊算法檢測出更多的冗余數據，但其存在分塊速度慢、系統數據吞吐率低的缺陷。

發明內容

本發明的目的是解決上述現有技術的不足，提供一種降低系統資源額外開銷、加快分塊速度，不存在內容偏移、保障重復數據刪除率的同時提高系統數據吞吐率的車輛物聯網云存儲系統重復數據刪除方法。

本發明解決上述現有技術的不足所采用的技術方案是：

一種車輛物聯網云存儲系統重復數據刪除方法，其特征在于包括如下步驟：

步驟a：將基于內容分塊算法的固定窗口置于數據流的未分塊的起始位置，記錄固定窗口內字節的極大值V_max,基于內容分塊算法的滑動窗口逐字節的尋找大于等于極大值V_max的字節作為分塊點；使用哈希函數對分塊點和前一個分塊點之間的字節內容生成塊指紋Chunk_fp；

步驟b：記錄滑動窗口中字節的極大值記錄步驟a獲得的分塊點和前一個分塊點之間的字節長度Size_Chunk；

步驟c：重復步驟a、步驟b，直至數據流剩余長度小于2KB，不再尋找分塊點，將剩余長度小于2KB的數據作為最后一個分塊，數據流全部分塊完成；