存储系统容错编码简介课件

1、存储系统容错编码简介第1页，共119页。内容RAID、容错编码Reed-Solomon编码二进制线性码阵列码利用组合数学工具构造容错编码第2页，共119页。内容RAID、容错编码Reed-Solomon编码二进制线性码阵列码利用组合数学工具构造容错编码第3页，共119页。RAIDRedundant Arrays of Inexpensive DisksRedundant Arrays of Independent Disks容量性能可靠性Chen, P. M., Lee, E. K., Gibson, G. A., Katz, R. H., and Patterson, D. A. “RAID

2、: high-performance, reliable secondary storage.” ACM Computing Surveys 26(2), pp. 143-185, June 1994.第4页，共119页。RAID结构Data Stripingstripe unitstripe04KB-14KB8KB-18KB12KB-112KB16KB-116KB20KB-1第5页，共119页。RAID结构Redundancy04KB-1第6页，共119页。RAID结构编码：d1 XOR d2 XOR XOR dn = p解码：di = p XOR d1 XOR XOR di-1 XOR d

3、i-1 解码：pnew = p XOR diold XOR dinew第7页，共119页。RAID结构data unit、parity unitRAID5：更新负载均匀分布第8页，共119页。RAID结构第9页，共119页。RAID5的读写第10页，共119页。RAID5的读写第11页，共119页。RAID5布局Edward K. Lee, Randy H. Katz, “The Performance of Parity Placements in Disk Arrays”, IEEE Transactions on Computers, vol. 42 no. 6, pp. 651-664

4、, 1993.第12页，共119页。RAID5布局第13页，共119页。RAID5布局第14页，共119页。RAID0Hui-I Hsiao and David J. DeWitt, “Chained declustering: A new availability strategy for multiprocessor database machines”, Technical Report CS TR 854, University of Wisconsin, Madison, June 1989. 第15页，共119页。RAID0Gang Wang, Xiaoguang Liu, She

5、ng Lin, Guangjun Xie, Jing Liu, “Constructing Double- and Triple-erasure-correcting Codes with High Availability Using Mirroring and Parity Approaches”, ICPADS2007.第16页，共119页。What is an Erasure Code?J. S. Plank, “Erasure Codes for Storage Applications”, Tutorial of the 4th Usenix Conference on File

6、and Storage Technologies, San Francisco, CA, Dec, 2005.第17页，共119页。When are they useful?Anytime you need to tolerate failures.第18页，共119页。When are they useful?Anytime you need to tolerate failures.第19页，共119页。When are they useful?Anytime you need to tolerate failures.第20页，共119页。When are they useful?Any

7、time you need to tolerate failures.第21页，共119页。When are they useful?Anytime you need to tolerate failures.第22页，共119页。When are they useful?Anytime you need to tolerate failures.第23页，共119页。When are they useful?Anytime you need to tolerate failures.第24页，共119页。Terms & DefinitionsNumber of data disks:nNum

8、ber of coding disks:mRate of a code:R = n/(n+m)Identifiable Failure: “Erasure”第25页，共119页。The problem, once again第26页，共119页。Issues with Erasure CodingPerformanceEncodingTypically O(mn), but not always.UpdateTypically O(m), but not always.DecodingTypically O(mn), but not always.第27页，共119页。Issues with

9、Erasure CodingSpace UsageQuantified by two of four:Data Devices:nCoding Devices:mSum of Devices:(n+m)Rate:R = n/(n+m)Higher rates are more space efficient,but less fault-tolerant.第28页，共119页。Issues with Erasure CodingFlexibilityCan you arbitrarily add data / coding nodes?(Can you change the rate)?How

10、 does this impact failure coverage?第29页，共119页。Trivial Example: ReplicationMDSExtremely fast encoding/decoding/update.Rate: R = 1/(m+1) - Very space inefficientThere are many replication/based systems(P2P especially).第30页，共119页。Less Trivial Example: Simple ParityPatterson D A, Gibson G A, Katz R H, “

11、A case for redundant arrays of inexpensive disks (RAID)”, ACM International Conference on Management of Data, Chicago, ACM Press, 1988, pp. 109-116.P. M. Chen, E. K. Lee, G. A. Gibson, R. H. Katz, and D. A. Patterson. RAID: High-performance, reliable secondary storage. ACM Computing Surveys, 26(2):1

12、45185, June 1994.第31页，共119页。Evaluating ParityMDSRate: R = n/(n+1) - Very space efficientOptimal encoding/decoding/update:n-1 XORs to encode & decode2 XORs to updateExtremely popular (RAID Level 5).Downside: m = 1 is limited.第32页，共119页。UnfortunatelyThose are the last easy things youll see.For (n 1, m

13、 1), there is no consensus on the best coding technique.They all have tradeoffs.第33页，共119页。Why is this such a pain?Coding theory historically has been the purview of coding theorists.Their goals have had their roots elsewhere (noisy communication lines, byzantine memory systems, etc).They are not sy

14、stems programmers.(They dont care)第34页，共119页。内容RAID、容错编码Reed-Solomon编码二进制线性码第35页，共119页。内容RAID、容错编码Reed-Solomon编码二进制线性码阵列码利用组合数学工具构造容错编码第36页，共119页。Reed-Solomon CodesThe only MDS coding technique for arbitrary n & m.This means that m erasures are always tolerated.Have been around for decades.Expensive

15、.J. S. Plank. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems. Software Practice& Experience, 27(9):9951012, September 1997.第37页，共119页。Reed-Solomon CodesOperate on binary words of data, composed of w bits, where 2w n+m.第38页，共119页。Reed-Solomon CodesOperate on binary words o

16、f data, composed of w bits, where 2w n+m.第39页，共119页。Reed-Solomon CodesThis means we only have to focus on words, rather than whole devices.Word size is an issue:If n+m 256, we can use bytes as words.If n+m 65,536, we can use shorts as words.第40页，共119页。Reed-Solomon CodesCodes are based on linear alge

17、bra.First, consider the data words as a column vector D:第41页，共119页。Reed-Solomon CodesCodes are based on linear algebra.Next, define an (n+m)*n “Distribution Matrix” B, whose first n rows are the identity matrix:第42页，共119页。Reed-Solomon CodesCodes are based on linear algebra.B*D equals an (n+m)*1 colu

18、mn vector composed ofD and C (the coding words):第43页，共119页。Reed-Solomon CodesThis means that each data and coding word has a corresponding row in the distribution matrix.第44页，共119页。Reed-Solomon CodesSuppose m nodes fail.To decode, we create B by deleting the rows of B that correspond to the failed n

19、odes.第45页，共119页。Reed-Solomon CodesSuppose m nodes fail.To decode, we create B by deleting the rows of B that correspond to the failed nodes.Youll note that B*D equals the survivors.第46页，共119页。Reed-Solomon CodesNow, invert B:第47页，共119页。Reed-Solomon CodesNow, invert B:And multiply both sides of the eq

20、uation by B-1第48页，共119页。Reed-Solomon CodesNow, invert B:And multiply both sides of the equation by B-1Since B-1*B = I, You have just decoded D!第49页，共119页。Reed-Solomon CodesNow, invert B:And multiply both sides of the equation by B-1Since B-1*B = I, You have just decoded D!第50页，共119页。Reed-Solomon Cod

21、esTo Summarize: EncodingCreate distribution matrix B.Multiply B by the data to create coding words.To Summarize: DecodingCreate B by deleting rows of B.Invert B.Multiply B-1 by the surviving words to reconstruct the data.第51页，共119页。Reed-Solomon CodesTwo Final Issues:1: How to create B?All square sub

22、matrices must be invertible.Derive from a Vandermonde MatrixJ. S. Plank and Y. Ding. Note: Correction to the 1997 tutorial on Reed-Solomon coding. Software Practice & Experience, 35(2):189194,2005.#2: Will modular arithmetic work?NO! (no multiplicative inverses)Instead, you must use Galois Field ari

23、thmetic.第52页，共119页。Reed-Solomon Codes(n+m)n的范德蒙矩阵基本变换任意两列可交换 任何一列可以乘以一个非0数 任意两列可做如下变换：Ci=Ci+c*Cj，c非0 第53页，共119页。Reed-Solomon PerformanceEncoding: O(mn)More specifically: mS (n-1)/BXOR + n/BGFMult S = Size of a deviceBXOR = Bandwith of XOR (3 GB/s)BGFMult = Bandwidth of Multiplication over GF(2w)GF(2

24、8): 800 MB/sGF(216): 150 MB/s第54页，共119页。Reed-Solomon PerformanceUpdate: O(m)More specifically: m+1 XORs and m multiplications.第55页，共119页。Reed-Solomon PerformanceDecoding: O(mn) or O(n3)Large devices: dS (n-1)/BXOR + n/BGFMult Where d = number of data devices to reconstruct.Yes, theres a matrix to in

25、vert, but usually thats in the noise because dSn n3.第56页，共119页。Reed-Solomon Bottom LineSpace Efficient: MDSFlexible:Works for any value of n and m.Easy to add/subtract coding devices.Public-domain implementations.Slow:n-way dot product for each coding device.GF multiplication slows things down.第57页，

26、共119页。Cauchy Reed-Solomon CodesJ. Blomer, M. Kalfane, M. Karpinski, R. Karp, M. Luby, and D. Zuckerman. An XOR-based erasure-resilient coding scheme. Technical Report TR-95-048, International Computer Science Institute, August 1995. #1: Use a Cauchy matrix instead of a Vandermonde matrix: Invert in

27、O(n2).#2: Use neat projection to convert Galois Field multiplications into XORs.Kind of subtle, so well go over it.第58页，共119页。Cauchy Reed-Solomon Codes取GF(2w)中m+n个不同元素，构成X=x1, , xm，Y=y1, , ym Cauchy矩阵：元素(i, j)为1/(xi+yj)GF(2w)上运算第59页，共119页。Cauchy Reed-Solomon Codes例：X=1, 2，Y=0, 3, 4, 5, 6 第60页，共119页。

28、Cauchy Reed-Solomon Codes第61页，共119页。Cauchy Reed-Solomon Codesn、m固定，w增长，GC的优势明显第62页，共119页。参考文献参考资料J. S. Plank. Enumeration of optimal and good Cauchy matrices for Reed-Solomon coding. Technical Report CS-05-570, University of Tennessee, December 2005.通信协议避免重新发送L. Rizzo. Effective erasure codes for re

29、liable computer communication protocols. ACM SIGCOMM Computer Communication Review, 27(2):2436, 1997.L. Rizzo and L. Vicisano. RMDP: an FEC-based reliable multicast protocol for wireless environments. Mobile Computer and Communication Review, 2(2), April 1998.第63页，共119页。参考文献已经正在成为IETF标准M. Luby, L. V

30、icisano, J. Gemmell, L. Rizo, M. Handley, and J. Crowcroft. Forward error correction (FEC) building block. IETF RFC 3452 (/rfc/rfc3452.txt), December 2002.M. Luby, L. Vicisano, J. Gemmell, L. Rizo, M. Handley, and J. Crowcroft. The use of forward error correction(FEC) in reliable multicast. IETF RFC

31、 3453 (/rfc/rfc3453.txt), December 2002.加密C. S. Jutla. Encryption modes with almost free message integrity. Lecture Notes in Computer Science, 2045, 2001.第64页，共119页。参考文献分布式数据结构W. Litwin and T. Schwarz. Lh*rs: a high-availability scalable distributed data structure using Reed Solomon codes. In Procee

32、dings of the 2000 ACM SIGMOD International Conference on Management of Data, pages 237248. ACM Press, 2000.降低无线通信能耗P. J. M. Havinga. Energy efficiency of error correction on wireless systems, 1999.广域网、对等网存储系统J. Kubiatowicz, D. Bindel, Y. Chen, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon

33、, W. Weimer, C. Wells, and B. Zhao. Oceanstore: An architecture for global-scale persistent storage. In Proceedings of ACM ASPLOS. ACM, November 2000.第65页，共119页。参考文献用于cache而不是冗余J. Byers, M. Luby, M. Mitzenmacher, and A. Rege. A digital fountain approach to reliable distribution of bulk data. In ACM

34、SIGCOMM 98, pages 5667, Vancouver, August 1998.J.W. Byers, M. Luby, and M. Mitzenmacher. Accessing multiple mirror sites in parallel: Using tornado codes to speed up downloads. In IEEE INFOCOM, pages 275283, New York, NY, March 1999.I. T. Rowstron and P. Druschel. Storage management and caching in P

35、AST, a large-scale, persistent peer-topeer storage utility. In Symposium on Operating Systems Principles, pages 188201, 2001.第66页，共119页。参考文献Tornado码M. Luby, M. Mitzenmacher, and A. Shokrollahi. Analysis of random processes via and-or tree evaluation. In 9th Annual ACM-SIAM Symposium on Discrete Algo

36、rithms, January 1998.M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, and V. Stemann. Practical loss-resilient codes. In 29th Annual ACM Symposium on Theory of Computing, pages 150159, 1997.M. Luby. Benchmark comparisons of erasure codes. /luby/erasure.html, 2002.（性能比RS码好）第67页，共119页。参考文献传统单节点用

37、于容错和提高性能S. Frolund, A. Merchant, Y. Saito, S. Spence, and A. Veitch. A decentralized algorithm for erasure-coded virtual disks. In DSN-04: International Conference on Dependable Systems and Networks, Florence, Italy, 2004. IEEE.G. R. Goodson, J. J. Wylie, G. R. Ganger, and M. K. Reiter. Efficient by

38、zantine-tolerant erasure-coded storage. In DSN-04: International Conference on Dependable Systems and Networks, Florence, Italy, 2004. IEEE.W.Wilcke et al. The IBM intelligent brick project petabytes and beyond. IBM Journal of Research and Development, to appear, April 2006.归档系统S. Rhea, C. Wells, P.

39、 Eaton, D. Geels, B. Zhao, H. Weatherspoon, and J. Kubiatowicz. Maintenance-free global data storage. IEEE Internet Computing, 5(5):4049, 2001.第68页，共119页。参考文献广域网存储：S. Atchley, S. Soltesz, J. S. Plank, M. Beck, and T. Moore. Fault tolerance in the network storage stack. In IEEE Workshop on Fault-Tole

40、rant Parallel and Distributed Systems, Ft. Lauderdale, FL, April 2002.R. L. Collins and J. S. Plank. Assessing the performance of erasure codes in the wide-area. In DSN-05: International Conference on Dependable Systems and Networks, Yokohama, Japan, 2005.IEEE.H. Xia and A. A. Chien. RobuSTore: Robu

41、st performance for distributed storage systems. Technical Report CS2005-0838, University of California at San Diego, October 2005.第69页，共119页。参考文献对等网：Z. Zhang and Q. Lian. Reperasure: Replication protocol using erasure-code in peer-to-peer storage network. In 21st IEEE Symposium on Reliable Distribut

42、ed Systems (SRDS02), pages 330339, October 2002.J. Li. PeerStreaming: A practical receiver-driven peer-to-peer media streaming system. Technical Report MSR-TR-2004-101, Microsoft Research, September 2004.W. K. Lin, D. M. Chiu, and Y. B. Lee. Erasure code replication revisited. In PTP04: 4th Internat

43、ional Conference on Peer-to-Peer Computing. IEEE, 2004.L. Dairaine, J. Lacan, L. Lancerica, and J. Fimes. Content-access QoS in peer-to-peer networks using a fast MDS erasure code. Computer Communications, 28(15):17781790, September 2005.第70页，共119页。参考文献内容分发系统：J. Byers, M. Luby, M. Mitzenmacher, and

44、A. Rege. A digital fountain approach to reliable distribution of bulk data. In ACM SIGCOMM 98, pages 5667, Vancouver, August 1998.M. Mitzenmacher. Digital fountains: A survey and look forward,.In 2004 IEEE Information Theory Workshop, San Antonio, October 2004.第71页，共119页。内容RAID、容错编码Reed-Solomon编码二进制

45、线性码阵列码利用组合数学工具构造容错编码第72页，共119页。内容RAID、容错编码Reed-Solomon编码二进制线性码阵列码利用组合数学工具构造容错编码第73页，共119页。Binary Linear CodesLisa Hellerstein, Garth A Gibson, Richard M Karp, Randy H Katz, David A Patterson, “Coding techniques for handling failures in large disk arrays”, Algorithmica, vol. 12, no. 2/3, pp. 182-208,

46、 1994. 数据单元划分为重叠的校验组，每个校验组相当于一个RAID4/5第74页，共119页。Binary Linear Codes容错编码评价标准MTTDLcheck disk overheadupdate penaltygroup size扩展性第75页，共119页。t维编码磁盘排列为t维方阵，每维最后一行为校验盘1维：RAID4、RAID5，校验磁盘开销，1/G2维：2/G，但注意，G是校验组大小，不是磁盘数，G2=N，因此是2/sqrt(N)t维：t/G，t/N1/t，t大于3时，冗余率太差 第76页，共119页。t维编码第77页，共119页。校验矩阵表示法数据位和校验位组成一个向

47、量码字parity check matrixH=P | Ic(k + c)，k数据位数，c校验位数I为cc的单位矩阵，P为ck的0/1矩阵表示校验计算公式，对码字X，应有HX=0P的列数据盘，I的列校验盘行校验组元素：1参与校验组，0未参与第78页，共119页。校验矩阵表示法第79页，共119页。容错能力的判定以下命题是等价的H能恢复任何的t擦除故障H能检测任意的t错误任意两个码字的距离distance不相同的位的数目，至少为t+1H的任意t列在GF2上线性无关因此，故障盘是否可恢复对应列是否线性无关！线性无关所有列向量的和或任意非空子集的和不为0 第80页，共119页。校验矩阵还可以表示其他

48、指标校验开销：c/k校验组大小：行的权重1的个数更新代价：列的权重一种常见的扩展方式新增加的磁盘全部清0无需重新计算校验，而H相应的增加一列MTTDL用校验矩阵表示比较困难第81页，共119页。重构假定m个盘故障，重排校验矩阵H=A | B，X=d | y，其中B和y对应故障磁盘重构求解yHX=0Ad+By=0求解线性方程组Ad=By此方程组有唯一解（可正确重构）的充要条件是B的各列线性无关无需解整个方程组，抽取出故障校验组对应的行Ad=By，计算y=(B)-1Ad即可 第82页，共119页。双容错和三容错编码 最优冗余full-2和full-3：所有可能的权重为2（3）的列组成的校验矩阵ba

49、d t+1故障：一个数据单元及其t个校验单元高可靠性编码：一个t-erasure-correcting code可恢复除bad t+1故障之外的所有t+1故障图表示法full-2、full-3：完全图二维：完全二部图第83页，共119页。2擦除码对比第84页，共119页。线性码比较第85页，共119页。线性码比较第86页，共119页。t3full-t不具备t容错能力，t维码冗余率太差定理：H=P | I 为校验矩阵，若P的所有列重量为t，且对于P的任意两行，P至多有1列在两行上均为1，则编码能容t错S为P的j列的集合(j2，数据方阵中选取斜率为0、1、t-1这t个方向组织校验组M. Blaum

50、, J. Bruck, and A. Vardy, “MDS array codes with independent parity symbols”, IEEE Trans. on Information Theory, Vol. 42, No. 2, Mar, 1996, pp. 529-542.并非对所有的n、m=t可保证t容错能力，上文中给出了适用的参数第94页，共119页。RDP双容错水平码，(p-1)*(p-1)的数据阵列，p为素数校验相关水平校验单元作为“数据”参与对角线校验第95页，共119页。阵列码和线性码的关系00010203041011121314202122232430

51、313233344041424344Q0Q1Q2Q3Q4P0P1P2P3P4第96页，共119页。Liberation码J. S. Plank, “The RAID-6 Liberation Codes”, 6th USENIX Conference on File and Storage Technologies, San Francisco, 2008, pp. 97110.编码矩阵1的个数最少，但不意味着校验计算性能最优第97页，共119页。其他水平码Cheng Huang, Lihao Xu, “STAR: An Efficient Coding Scheme for Correcti

52、ng Triple Storage Node Failures”, 4th USENIX Conference on File and Storage Technologies San Francisco, 2005, pp. 197-210.Chong-Won Park and Jin-Won Park, “A multiple disk failure recovery scheme in RAID systems,” Journal of Systems Architecture, vol. 50, pp. 169175, 2004.第98页，共119页。B-CODEL. Xu, V.

53、Bohossian, J. Bruck, and D.G. Wagner, Low-Density MDS Codes and Factors of Complete Graphs, IEEE Trans. Information Theory, pages 1817-1826, IEEE, 1999.双容错MDS垂直码基于完全图的完全1-因子分解（P1F）无素数限制图论领域的一个猜测：对所有偶数n，Kn存在P1F，每个P1F又能构造两个规模的B-CODE，所有规模的阵列都能构造B-CODE基于full-2码第99页，共119页。B-CODE第100页，共119页。X-CodeL. Xu an

54、d J. Bruck, “X-Code: MDS Array Codes with Optimal Encoding”, IEEE Trans. on Information Theory, Vol. 45, No. 1, Jan, 1999, pp.272-276.双容错“垂直码”每个磁盘都是既放置数据单元，又放置校验单元EVENODD是“水平码”数据单元和校验单元放置在不同磁盘上校验方向：1和-1第101页，共119页。X-Code结构示意第102页，共119页。其他垂直码RM2：C. Park, “Efficient placement of parity and data to tol

55、erate two disk failures in disk array systems”, IEEE Trans. Parallel Distribut.Syst., vol. 6, no. 11, pp. 1177-1184, 1995.不保证MDS构造方法不是确定的，要进行搜索WEAVER： J. L. Hafner, “WEAVER Codes: Highly Fault Tolerant Erasure Codes for Storage Systems,” FAST-2005: 4th Usenix Conference on File and Storage Technolog

56、ies, December, 2005.非MDS码，冗余率最好50%！条纹组小，局部性好，分布式存储系统下故障模式性能好也是搜索可行编码，最高容错12第103页，共119页。混合码DH1/DH2Nam-Kyu Lee, Sung-Bong Yang, Kyoung-Woo Lee, Efficient parity placement schemes for tolerating up to two disk failures in disk arrays, Journal of Systems Architecture, 2000, 46(15): 1383-1402.DH1第104页，共119页。混合码DH2第105页，共119页。HDD1/HDD2Chih-Shing Tau and Tzone-I Wang, “Efficient parity placement schemes for tolerating triple disk failures in RAID architectures,” i