[發明專利]一種基于復制和糾刪碼自適應切換的云存儲容錯方法

在審

• 申請號: 201610961439.X
• 申請日: 2016-10-28
• 公開（公告）號: CN107797884A
• 公開（公告）日: 2018-03-13
• 發明（設計）人: 張大方;鄢喜愛;周慧斌
• 申請（專利權）人: 湖南大學
• 主分類號: G06F11/14
• 分類號: G06F11/14;G06F11/10;G06F12/123
• 代理公司: 長沙正奇專利事務所有限責任公司43113
• 代理人: 馬強,王娟

技術領域

本發明涉及一種基于復制和糾刪碼自適應切換的云存儲容錯方法。

背景技術

云存儲為用戶帶來了低廉的運維成本，按需可擴展的性能配置以及更高效的存儲能力，已被越來越多的用戶所接受。然而，由于云存儲環境的復雜性和開放性，數據失效問題也引起了廣大用戶的關注。例如：2011年，阿里云服務器磁盤出現故障，在維護過程中執行重啟操作，導致期間的數據丟失；2012年，谷歌郵箱爆發大規模數據丟失，15萬左右谷歌郵箱用戶數據失效。云存儲系統的首要任務是保證數據的高可用性和高可靠性，必須考慮構建一套高性能低開銷的容錯機制。

容錯的數據冗余方法常用的有副本復制和糾刪碼兩種。隨著數據量的增長，云存儲容錯逐漸由復制向糾刪碼轉變。糾刪碼有效地減少了冗余空間，但解碼復雜，存在更多的延時。由此可見，單一的數據冗余方法已無法滿足不同類型用戶的特定容錯需求，混合數據冗余方法將會成為未來云存儲容錯的研究熱點。

通過混合冗余來實現云存儲容錯的主要文獻有：Fan等人通過跟蹤發現大多數的數據訪問操作發生在數據創建后的較短的一段時間內，針對HDFS系統，將生命周期超過一定期限的文件通過一個后臺進程寫入糾刪碼數據塊，將復制數據塊轉化為糾刪碼數據塊以節省存儲空間，并在此基礎上測試了延遲編碼的時間與帶來的性能損耗之間的關系。微軟研究院的Zhang等人將僅支持復制的HDFS改進為完全支持復制和糾刪碼兩種方式，用戶可根據自己的容錯需求進行容錯方式的選擇，但對于一特定文件仍是單一的數據冗余方法，與時間、空間都不發生關系。Yadi等人提出一種云計算環境副本復制與糾刪碼相結合的容錯方案，采用LRU(Least Recently Used)的方法進行替換，有效地實現了空間與時間的均衡，LRU方法存在時間的局部性，未考慮單位時間內的訪問頻率，而且是一次性永久轉換，可能存在數據的二次污染。Aye等人針對HDFS提出了一種基于糾刪碼的副本復制方法，為增強可靠性，對事先存儲糾刪碼進行hash，再進行副本復制，在訪問延時控制在一定閾值范圍內較完全復制技術節約33％的存儲空間。Roy等人提出了一種柔性的復制糾刪碼方法，對于訪問熱度低的文件，以單一的糾刪碼方式存儲，對于訪問熱度高的文件，為保證高訪問質量，根據訪問熱度動態生成副本，也即對于訪問熱度高的文件是復制塊與糾刪碼塊共存。楊東日等人提出了一種副本復制和糾錯碼融合的云存儲文件系統容錯機制，提出了根 據訪問頻率來選擇容錯方式，并重點分析了系統的可靠性，但未對如何確定文件訪問頻率作過多描述。宋寶燕等人提出了利用RS編碼優化HDFS的存儲容錯策略，并通過改變生成矩陣優化了RS編碼在有限域上的乘法計算難的問題。

Bhagwat等人較早提出根據原始數據塊的等級保存若干副本的容錯方法。基于副本復制的容錯策略簡單、高效，容易實現和部署，由于每個復制數據塊都是一個完整的備份，數據修復效率高，并可以很好地支持并發訪問，因此在實際中得到了廣泛的應用。在GFS和HDFS目前所采用的容錯策略就是副本復制技術。

在基于糾刪碼的存儲容錯系統中，N個存儲節點被分成數據節點和校驗節點兩部分，校驗節點的數據由數據節點計算得來，定義糾刪碼為一個四元組(n,k,w,k’)，n表求數據節點的個數，k表示原始文件分片的個數，n-k表示校驗節點個數，w表示每個數據塊包含的比特數，k’表未任意獲得一個條帶上的k’個數據塊即可修復受損的文件。為了使系統具有最優的存儲效率，糾刪碼須具有MDS屬性，即k＝k’。目前存在很多類型的糾刪碼，例如Reed-Solomon編碼(簡稱RS編碼)、LDPC碼、陣列碼等。

發明內容

本發明所要解決的技術問題是，針對現有技術不足，提供一種基于復制和糾刪碼自適應切換的云存儲容錯方法。

為解決上述技術問題，本發明所采用的技術方案是：一種基于復制和糾刪碼自適應切換的云存儲容錯方法，包括以下步驟：

1)當編號為K的文件被訪問之后，判斷本時間間隔內文件的訪問次數是否高于上一時間間隔內的訪問次數，文件的訪問次數是否高于替換閾值，當文件K在本時間間隔內的訪問次數低于上一時間間隔內的訪問次數時，或訪問次數雖高于上一時間間隔內的訪問次數，但訪問次數低于替換閾值時，仍維持糾刪碼；否則，進入步驟2)；

2)查詢下降集中的最低的訪問次數的文件K'，若文件K的訪問次數高于下降集中最低的訪問次數，則將下降集中最低訪問次數的文件K'移出下降集，并刪除K'的相關副本，對K'做糾刪碼；將文件K放入下降集，并對K文件做3副本復制的容錯方案，將原有糾刪碼刪除；否則，進入步驟3)；