來自南加州大學和Facebook的7名作者共同完成了論文《 XORing Elephants: Novel Erasure Code for Big Data》。論文作者開發了Erasure Code家族的新成員——Locally Repairable Codes(即本地副本存儲，以下簡稱LRC，它基于XOR。)，明顯減少修復數據時的I/O和網絡流量。他們將這些編碼應用在新的Hadoop組件中，并稱之為 HDFS–Xorbas，并在Amazon AWS上和Facebook內部做了測試。

從Reed Solomon code到LRC

大約十年前，業界開始采用 Reed Solomon code對數據分發兩份或三份，替代傳統的RAID5或RAID6。由于采用了廉價的磁盤替代昂貴的存儲陣列，所以這種方法非常經濟。Reed Solomon code和XOR都是Erasure Code的分支。其中，XOR只允許丟失一塊數據，而Reed Solomon code可以容忍丟失多塊數據。

但標準的Reed Solomon code并不能很好的解決超大規模Hadoop負載。因為數據修復的時間和花費(主要為I/O和網絡流量)成本較高。同時，在一段時間內，指數級增長的數據超出了互聯網公司的基礎設施能力。三副本有時候也不能滿足更高的可靠性需求。

現在，這些互聯網巨頭設計的存儲系統標準為：即便四個存儲對象同時失效(這些對象包括磁盤、服務器、節點，甚至整個數據中心)，也不能失去任何數據(目前Reed Solomon code是采用(10,4)策略，即10個數據塊生成4個校驗文件，可以容忍丟失4塊數據。)。從這篇論文來看，Facebook采用Erasure Code方式后，相對于Reed Solomon code只需要60%的I/O和網絡流量。

論文作者分析了Facebook的Hadoop集群中的3000個節點，涉及45PB數據。這些數據平均每天有22個節點失效，有些時候一天的失效節點超過100個，見圖1。

圖1：日節點失效圖

Hadoop集群的網絡經常被被動占用，幾個活躍的磁盤就可以占滿1Gb帶寬，修復失效數據產生的擁堵是不可能忽略不計的。一個理想的存儲方案不僅要保證存儲效率，還要減少修復數據所需的流量。

LRC測試結果的主要指標：

——磁盤I/O和網絡流量比Reed Solomon code減少一半;

——LRC比Reed Solomon code多占用14%的存儲空間;

——修復時間大幅縮短;

——更強的可靠性;

——對網絡流量需求降低將實現適當的數據物理分布，甚至跨數據中心分布。

表1：LRC與Reed Solomon code、傳統Hadoop三副本策略對比。LRC比Reed Solomon code的無故障運行時間提升兩個數量級，修復流量減少一半。

圖2：LRC與Reed Solomon code在多節點、多數據塊失效的情況下，HDFS讀取數據量、網絡流量和修復時間的對比，LRC基本上比Reed Solomon code節省一半資源。

包括 HDFS-3544在內，業界正在不斷追求高可靠下對網絡帶寬的節省方法，這對于互聯網巨頭和云計算基礎架構服務商而言的意義不言而喻。由南加州大學、韋恩州立大學和微軟共同參與的《 Simple Regenerating Codes》也在朝這個方向努力。值得注意的是，前文所說的LRC、HDFS-3544和《Simple Regenerating Codes》都是通過增加本地數據，來減少修復數據需要的網絡流量。

在 ATC2012上，微軟Azure工程師Cheng Huang和他的同事分享了《 Erasure Coding in Windows Azure Storage》。Cheng Huang表示，微軟在Azure上也使用了LRC技術。 這里可以看到Cheng Huang此次分享視頻。另外，Cheng Huang也參與了《Simple Regenerating Codes》。

在國內，Azure在世紀互聯北京、上海的兩個數據中心部署了服務。在接受CSDN采訪時，微軟云計算與服務器事業部總經理嚴治慶 透露：

Windwos Azure上的數據要存放6份，即使是虛機的本地存儲也不例外。在中國，沒有一家公有云計算的公司愿意去承諾三個9這樣的 SLA，但微軟會承諾3個9或更高。

關于HDFS–Xorbas、LRC和GFS2

目前，HDFS–Xorbas基于Facebook的HDFS-RAID版Hadoop( GitHub入口、 Apache入口)修改而來，并在 GitHub上托管代碼。

HDFS–Xorbas項目由 Maheswaran Sathiamoorthy維護，他是一名南加州大學謝明電子工程部的候選教授。咨詢公司TechnoQWAN創始人Robin Harris在 文章中表示：論文中的幾名作者已經創立了公司。

論文作者之一的 Dhruba Borthakur是Facebook的Hadoop工程師，他在2009年的一篇 博客中對Erasure Code進行了介紹：

我知道使用Erasure Code的想法來自 DiskReduce，這是一幫來自卡內基梅隆大學的家伙搞出來的。于是我借用了這個想法，并在Apache Hadoop上增加了這一功能 HDFS-503。

Dhruba強調，HDFS Erasure Code只是在HDFS之上的代碼，并沒有對HDFS內部代碼進行修改。這樣做的原因是HDFS代碼已經十分復雜，不想自找麻煩把它弄的更復雜。

Dhruba還在Hadoop Summit 2012中的一個關于HDFS的 研討會上談到了HDFS-RAID在Facebook內部運行的情況。數據工程師 梁堰波在 博客中分享了Dhruba的觀點：

存放在HDFS上的數據分為熱數據和冷數據兩種。熱數據一般是存放三備份，因為這些數據經常會被用到，所以多備份除了高效冗余外還能起到負載均衡的作用。對于冷數據，并非一定要在HDFS里面保存3個副本。Dhruba介紹了兩種不同的RAID方案，對于不太冷的數據塊A/B/C,通過XOR方式產生校驗數據塊，原來的數據塊A/B/C各保留2個副本，校驗數據塊也有兩個副本。這樣，副本系數就從3減小到了2.6(理論值)。

對于很冷的數據，方案更加激進，由10個數據塊通過Reed Solomon code生成4個校驗文件，對于原來的數據塊，只保留一個副本，校驗數據塊有2份副本。這樣，副本系數就降到了1.2。

梁堰波在 博客分享了Dhruba介紹的分布式RAID文件系統實現原理，在2009年Dhruba的博客中也對此進行了介紹，可以分別查閱。

當然，Hadoop不過是GFS的開源實現，那么Google是如何解決數據修復帶來的高成本呢?在Google GFS2(Colossus)中使用了Reed Solomon code來復制。在Google去年發表的《 Spanner: Google's Globally-Distributed Database》( CSDN摘譯稿)中透露：

Reed Solomon code可以將原先的3副本減小到1.5副本，提高寫入性能，降低延遲。

但是關于GFS2的信息，Google透露非常有限。Google首席工程師Andrew Fikes在Faculty Summit 2010會議上分享了《 Google的存儲架構挑戰》，他談到了Google為什么使用Reed Solomon code，并列舉了以下理由：

——成本。特別是跨集群的數據拷貝。

——提升平均無故障時間(MTTF)。

——更靈活的成本控制和可用性選擇。