1、可以通過糾刪碼實現(xiàn)數(shù)據(jù)的可用性(例如 Reed-Solomon codes41)，其主要是將數(shù)據(jù)段編碼為奇偶校驗段，使得數(shù)據(jù)段和奇偶校驗段的自己可以完全重建原始數(shù)據(jù)，糾刪碼可以多個結(jié)點故障，相比較與多副本，同時還可以減少開銷。以前的研究探索都是通過最小化以優(yōu)化恢復(fù)策略。一類方法是基于糾刪碼最小化I/O(例如26，30，42，53，55)，另一類方法是基于再生碼最小化帶寬(即恢復(fù)過程中通過網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量)，其中每個幸存的結(jié)點對的數(shù)據(jù)進行編碼并發(fā)送編碼后的數(shù)據(jù)用于恢復(fù)。雖然單結(jié)點故障在分布式系統(tǒng)39是常見的，但是在實踐中，結(jié)點故障往往是相關(guān)和并發(fā)的，就如在集群(例如 14,43)和廣域設(shè)置(例如

2、6, 20, 33)中提到的那樣。為了提供并發(fā)錯誤的容錯機制，數(shù)據(jù)通常使用高度冗余進行保護，例如，Cleversafe7，是一個商業(yè)廣域設(shè)置系統(tǒng)，它采用每 10 個數(shù)據(jù)段編碼編碼出 6 個奇偶校驗段。另外一些一些廣域系統(tǒng)，例如 OceanStore 和 CFS8，在雙冗余(就是原始空間的兩倍)上部署糾刪碼技術(shù)。作為概念的證明，選擇了Hadoop 分布式文件系統(tǒng)(HDFS)49為基礎(chǔ)，這也與稱為HDFS-RAID22的基于糾刪碼 HDFS 模塊一致。每個集合中的 n 個段分布在 n 上節(jié)點。為了負(fù)載平衡的原因，數(shù)據(jù)/奇偶校驗節(jié)點被輪流使用，使得數(shù)據(jù)和奇偶校驗段在節(jié)點上均勻分布30，36。關(guān)注雙冗

3、余 n=2k 的情況，這也被視為是最先進的分布式系統(tǒng)，如 OceanStore31和 CFS8。盡管對于（n，k）比較大的情況，冗余開銷高于傳統(tǒng) RAID-5 和 RAID-6 編碼，但它仍然低于在實際系統(tǒng)（如 GFS15和 HDFS49）中使用的傳統(tǒng) 3 備份。幸運的是，在實際部署中，即使系統(tǒng)包含大量節(jié)點，條帶大小 n 總是被限制為一個相當(dāng)小的值，以避免額外的編碼開銷30，36。對于實現(xiàn)的每個代碼，添加XOR 變換3MapReduce9是在 HDFS 上運行的一個重要的數(shù)據(jù)處理的框架。最小化 I / O 幾個研究集中在最小化在糾刪碼中恢復(fù)單個故障所需的 I/O。他們的方法主要集中在磁盤陣列系

4、統(tǒng)，其中磁盤是瓶頸。53，55的作者提出了 RAID-6 代碼的最佳單一故障恢復(fù)。Khan et al.30表明，找到任意糾刪碼的最佳恢復(fù)解決方案是 NP-hard 問題。注意，上述解決方案相對于常規(guī)恢復(fù)的性能增益通常小于 30，而再生碼在單個故障恢復(fù)中獲得高得多的增益（見第 5 節(jié)）。13，26，34，423 的作者已經(jīng)提出了在恢復(fù)丟失的數(shù)據(jù)時減少帶寬和 I/O 的本地恢復(fù)代碼。他們評估云系統(tǒng)模擬器（例如34），Azure（例如26）和 HDFS（例如13，42）。值得注意的是，本地恢復(fù)編碼是添加額外奇偶校驗數(shù)據(jù)到器用以獲得更好的恢復(fù)性能的非 MDS 編碼。所有這些研究集中在優(yōu)化單一故障恢復(fù)

5、。的工作在幾個方面與它們不同：（i）再生代碼，即 MDS 代碼，（ii考慮最佳的最小考慮恢復(fù)單個和并發(fā)故障，（iii）實現(xiàn)和執(zhí)試實驗，需要節(jié)點執(zhí)行編碼操作。最小化帶寬。 再生碼11最小化了分布式系統(tǒng)中單個故障恢復(fù)的帶寬。已經(jīng)有許多關(guān)于構(gòu)建再生代碼的理論研究（例如，4，11，35，37，38，44，51，52）。大多數(shù)再生碼構(gòu)造需要幸存節(jié)點在恢復(fù)期間對的數(shù)據(jù)進行編碼。一些再生碼構(gòu)造（例如，23，40，45，54）在恢復(fù)期間消除這種編碼操作，以便最小化 I/O 和帶寬，但是它們做出不同的權(quán)衡(見24中的)。再生碼的實現(xiàn)研究最近受到了研究團體的關(guān)注，如12，23，27，28。注意，研究12，27，2

6、8沒有將再生代碼集成到真正的系統(tǒng)，而 NCCloud23實現(xiàn)了基于非系統(tǒng)化的再生碼的原型。并行恢復(fù)。幾個理論研究（例如，25，29，47，48）基于再生碼來解決并發(fā)故障恢復(fù)，并且它們專注于在新節(jié)點上恢復(fù)丟失的數(shù)據(jù)。他們都考慮一個合作模型，其中新的節(jié)點之間交換他們在恢復(fù)期間從幸存節(jié)點的數(shù)據(jù)。25，29的作者證明合作模型實現(xiàn)了與相同的最佳恢復(fù)帶寬，但它們不提供實現(xiàn)最優(yōu)的再生碼的顯式構(gòu)造。47，48的作者提供了這樣的顯式實現(xiàn)，但是它們集中在有限的參數(shù)上，并且所得到的實現(xiàn)不提供任何超過糾刪碼的帶寬節(jié)省。合作模型的缺點是新節(jié)點需要執(zhí)行操作并在它們之間交換數(shù)據(jù)，并且其實現(xiàn)復(fù)雜性是未知的。相反，CORE 在

7、 relayer 中執(zhí)行所有操作并且更容易實現(xiàn)。高冗余的CORE 在本文中，由于最佳再生碼的基礎(chǔ)結(jié)構(gòu)要求，采用具有相當(dāng)高的冗余（即雙冗余）的MSR代碼。在44中顯示，具有精確恢復(fù)的所有（n，k）線性MSR碼必須滿足條件n 2k 2。其他（n，k）可以通過用于歸檔數(shù)據(jù)23的非系統(tǒng)的再生碼結(jié)構(gòu)11來構(gòu)造，如何擴展CORE的功能再生代碼仍然是一個開放。非MDS碼的并發(fā)恢復(fù)。考慮實現(xiàn)了最小的效率，如MDS編碼（見第2.1節(jié)）的MSR編碼并發(fā)恢復(fù)問題，?？梢钥紤]非MDS代碼，雖然有較高的開銷，但是實現(xiàn)更好的單一故障恢復(fù)性能（例如MBR代碼38和本地恢復(fù)代碼13，26，34，42）。一個開放是如何擴展這些

8、非MDS代碼以支持高效的并發(fā)恢復(fù)。目前在 HDFS 上實現(xiàn) CORE。廣域系統(tǒng)。計劃探索在廣域系統(tǒng)（例如，2，7，8，31）中的 CORE 的實現(xiàn)，其中網(wǎng)絡(luò)帶寬有限并且再生碼的優(yōu)勢應(yīng)該變得更突出。此外，CORE 的一個好處是可以延遲恢復(fù)，直到失敗的節(jié)點數(shù)量達到某個閾值，以避免恢復(fù)在廣域網(wǎng)中常見的瞬態(tài)故障2，6，33。1 R. Ahlswede, N. Cai, S. Li, and R. Yeung. Network Information low. IEEE Trans. onInformation Theory, 46(4):12041216, Jul 2000.2 R. Bhagwan,

9、 K.i, Y. Cheng, S. Savage, and G. Voelker. Total ecall: System Support forAutomated Availability Management. n Proc. of USENIX NSDI, Oct 2004.3 J. Bloemer, M. Kalfane, R. Karp, M. Karpinski, M. Luby, and . Zuckerman. An XOR-basedErasure-Resint Coding Scheme. echnical report, Theernational Computer S

10、cience Institute,erkeley, CA, Aug 1995.4 V. R. Cadambe, C. Huang, and J. Li. Permuion Code: Optimal xact-Repair of a SingleFailed NodeDS Code Based istributed Storage Systems. In Proc. of IEEE ISIT, 2011.5 B. Calder, J. Wang, A. Ogus, N. Nilakantan, A. Skjolsvold, S. McKelvie, Y. Xu, S. Srivastav,J.

11、 Wu, H. Simitci, et al. Windows Azure Storage: A Highly Available Cloud Storage Service withStrong Consistency. In Proc. of ACM SOSP, Oct 2011.6 B. C, F. Dabek, A. Haeberlen, E. Sit, H. Weatherspoon, M. Kaashoek, J. Kubiatowicz, andR. Morris. Efficient Replica Maenance for Distributed Storage System

12、s. In Proc. of USENIXNSDI, May 2006.7 Cleversafe. HYPERLINK http:/w/ http:/w.8 F. Dabek, M. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide- Area Cooperative Storagewith CFS. ACM SIGOPS Operating Systems Review, 35(5):202215, Dec 2001.9 J. Dean and S. Ghemawat. MapReduce: Simplified Data Prosing

13、 on Large Clusters. InProc. of USENIX OSDI, Dec 2004.10 G. DeCandia, D. Hastorun, M. Jani, G. Kakulapati, A. Lakshman, A. Pilchin, S.Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazons Highly Available Key-ValueStore. In Proc. Of ACM SOSP, 2007.11 A. Dimakis, P. Godfrey, Y. Wu, M. Wainwrigh

14、t, and K. Ramchandran. Network Coding forDistributed Storage Systems. IEEE Trans. on Information Theory, 56(9):45394551, Sep 2010.12 A. Duminuco and E. Biersack. A Practical Study of Regenerating Codes for Peer-to-PeerBackup Systems. In Proc. of IEEE IC. IEEE, Jun 2009.13 K. Esi, P. Lluis, and A. Da

15、tta. CORE: Cross-Object Redundancy for Efficient DataRepair in Storage Systems. In Proc. Of IEEE BigData, 2013.14 D. Ford, F. Labelle, F. I. Popovici, M. Stokel, V.-A. Truong, L. Barroso, C. Grimes, and S.Quinlan. Availability in Globally Distributed Storage Systems. In Proc. of USENIX OSDI, Oct2010

16、.15 S. Ghemawat, H. Gobioff, and S. Leung. TheFile System. In Proc. of ACM SOSP,Dec 2003.16 K. Greenan. Reliability ander-Efficiency in Erasure-Coded Storage Systems. PhD thesis,University of California, Santa Cruz, 2009.17 K. M. Greenan, E. L. Miller, and T. J. E. Schwarz. Optimizing Galois Field A

17、rithmetic forDiverse Prosor Architectures and Applications. In Proc. of IEEE MASCOTS, 2008.18 K. M. Greenan, J. S. Pl, and J. J. Wy. Meto meaningless: MTTDL, Markovms, and storage system reliability. In Proc. of USENIX HotStorage, 2010.19 Gutenberg.20 A. Haeberlen, A. Mislove, and P. Druschel. Glaci

18、er: Highly Durable, Decentralized StorageDespite Massive Correlated Failures. In Proc. of USENIX NSDI, May 2005.21 J. Hafner, V. Deenadhayalan, K. Rao, and J. Tomlin. Matrix Methods for Lost DataReconstruction in Erasure Codes. In Proc. of USENIX FAST, Dec 2005.22 HDFS-RAID.23 Y. Hu, H. Chen, P. Lee

19、, and Y. Tang. NCCloud: Applying Network Coding for the StorageRepair in a Cloud-of-Clouds. In Proc. Of USENIX FAST, Feb 2012.24 Y. Hu, P. P. C. Lee, and K. W. Shum.ysis and Construction of Functional RegeneratingCodes witcoded Repair for Distributed Storage Systems. In Proc. of IEEE, Apr2013.25 Y.

20、Hu, Y. Xu, X.Wang, C. Zhan, and P. Li. Cooperative Recovery of Distributed StorageSystems from Multiple Losses with Network Coding. IEEE Journal on Selected Areas inCommunications (JSAC), 28(2):268276, Feb 2010.26 C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin. E

21、rasureCoding in Windows Azure Storage. In Proc. of USENIX ATC, Jun 2012.27 Z. Huang, E. Biersack, and Y. Peng. Reducing Repair Traffic in P2P Backup Systems: ExactRegenerating Codes on Hierarchical Codes. ACM Trans. on Storage, 7(3):10, Oct 2011.28 S. Jiekak, A.-M. Kermarrec, N. L. Scouarnec, G. Str

22、aub, and A. Vempen. RegeneratingCodes: A System. ACM SIGOPS Operating Systems Review, 47(2):2332, Jul 2013.29 A. Kermarrec, N. Le Scouarnec, and G. Straub. Repairing Multiple Failures with Coordinatedanptive Regenerating Codes. In Proc. of NetCod, Jun 2011.30 O. Khan, R. Burns, J. Pl, W. Pierce, and

23、 C. Huang. Rethinking Erasure Codes for CloudFile Systems: Minimizing I/O for Recovery and Degraded Reads. In Proc. of USENIX FAST, Feb2012.31 J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S.Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. OceanStore: An

24、Architecture forGlobal-Scale Persistent Storage. In Proc. of ACM ASPLOS-IX, Nov 2000.32 R. Li, J. Lin, and P. P. C. Lee. CORE: Augmenting Regenerating-Coding-Based Recovery forSingle and Concurrent Failures in Distributed Storage Systems. In Proc. of IEEE MSST, May2013.33 S. Nath, H. Yu, P. B. Gibbo

25、ns, and S. Seshan. Subtletiesolerating Correlated Failures inWide-area Storage Systems. In Proc. of USENIX NSDI, May 2006.34 D. Papailiopoulos, J. Luo, A. Dimakis, C. Huang, and J. Li. Simple Regenerating Codes:Network Coding for Cloud Storage. In Proc. of IEEE, Mar 2012.35 D. S. Papailiopoulos, A.

26、G. Dimakis, and V. R. Cadambe. Repair Optimal Erasure Codesthrough Hadamard Designs. In Proc. Of Allerton Conf., 2011.36 J. Pl, J. Luo, C. Schuman, L. Xu, and Z. Wilcox-OHearn.rformance Evaluation andExamination of Open-Source Erasure Coding Libraries for Storage. In Proc. of USENIX FAST,Feb 2009.37

27、 K. Rashmi, N. Shah, and P. Kumar. Optimal Exact-Regenerating Codes for DistributedStorage at the MSR and MBR Pos via a Product-Matrix Construction. IEEE Trans. onInformation Theory, 57(8):52275239, Aug 2011.38 K. Rashmi, N. Shah, P. Kumar, and K. Ramchandran. Explicit Construction of Optimal ExactR

28、egenerating Codes for Distributed Storage. In Proc. of Allerton Conf., Sep 2009.39 K. Rashmi, N. B. Shah, D. Gu, H. Kuang, D. Borkur, and K. Ramchandran. A Solution tothe Network Challenges of Data Recovery in Erasure-Coded Distributed Storage Systems: AStudy on theWSarehouse Cluster. In Proc. of US

29、ENIX HotStorage, 2013.40 K. Rashmi, N. B. Shah, and K. Ramchandran. A Piggybacking Design Framework for Read-and-Download-Efficient Distributed Storage Codes. In Proc. of IEEE ISIT, 2013.41 I. Reed and G. Solomon. Polynomial Codes over Certain Finite Fields. Journal of the Societyfor Industrial and

30、Appd Mathematics, 8(2):300304, Jun 1960.42 M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis, R. Vadali, S. Chen, and D.Borkur. XORing Elephants: Novel Erasure Codes for Big Data. Proc. of VLDB Endowment,2013.43 B. Schroeder and G. A. Gibson. Disk Failureshe Real World: What Does an MTT

31、F of1,000,000 Hours Mean to You? In Proc. Of USENIX FAST, Feb 2007.44 N. Shah, K. Rashmi, P. Kumar, and K. Ramchandran.erference Alignment inRegenerating Codes for Distributed Storage: Nesity and Code Constructions. IEEE Trans. onInformation Theory, 58(99):2134 2158, Apr 2012.45 N. B. Shah. On Minim

32、izing Data-Read and Download for StorageNode Recovery. IEEECommunications Letters, 17(5):964967, 2013.46 N. B. Shah, K. Rashmi, P. V. Kumar, and K. Ramchandran. Explicit Codes MinimizingRepair Bandwidth for Distributed Storage. In IEEE Information Theory Workshop, 2010.47 K. Shum. Cooperative Regenerating Codes for Distributed Storage Systems. In Proc. of IEEEICC, Jun 2011.48 K. Shum and Y. Hu. Exact Minimum-Repair-Bandwidth Cooperative Regenerating Code