存儲(chǔ)系統(tǒng)容錯(cuò)編碼簡介-全文預(yù)覽
【正文】 Correcting Triple Storage Node Failures‖, 4th USENIX Conference on File and Storage Technologies San Francisco, 2022, pp. 197210. ChongWon Park and JinWon Park, ―A multiple disk failure recovery scheme in RAID systems,‖ Journal of Systems Architecture, vol. 50, pp. 169–175, 2022. BCODE L. Xu, V. Bohossian, J. Bruck, and . Wagner, LowDensity MDS Codes and Factors of Complete Graphs, IEEE Trans. Information Theory, pages 18171826, IEEE, 1999. ?雙容錯(cuò) MDS垂直碼 ?基于完全圖的完全 1因子分解（ P1F） ?無素?cái)?shù)限制 ——圖論領(lǐng)域的一個(gè)猜測：對所有偶數(shù) n， Kn存在 P1F，每個(gè) P1F又能構(gòu)造兩個(gè)規(guī)模的 BCODE，所有規(guī)模的陣列都能構(gòu)造 BCODE ?基于 full2碼 BCODE XCode L. Xu and J. Bruck, ―XCode: MDS Array Codes with Optimal Encoding‖, IEEE Trans. on Information Theory, Vol. 45, No. 1, Jan, 1999, . ?雙容錯(cuò) “ 垂直碼 ” ——每個(gè)磁盤都是既放置數(shù)據(jù)單元，又放置校驗(yàn)單元 EVENODD是 “ 水平碼 ” ——數(shù)據(jù)單元和校驗(yàn)單元放置在不同磁盤上 ?校驗(yàn)方向： 1和 1 XCode ?結(jié)構(gòu)示意 其他垂直碼 RM2： C. Park, ―Efficient placement of parity and data to tolerate two disk failures in disk array systems‖, IEEE Trans. Parallel ., vol. 6, no. 11, pp. 11771184, 1995. ? 不保證 MDS ? 構(gòu)造方法不是確定的，要進(jìn)行搜索 WEAVER： J. L. Hafner, ―WEAVER Codes: Highly Fault Tolerant Erasure Codes for Storage Systems,‖ FAST2022: 4th Usenix Conference on File and Storage Technologies, December, 2022. ? 非 MDS碼，冗余率最好 50%！ ? 條紋組小，局部性好，分布式存儲(chǔ)系統(tǒng)下故障模式性能好 ? 也是搜索可行編碼，最高容錯(cuò) 12 混合碼 ?DH1/DH2 ? NamKyu Lee, SungBong Yang, KyoungWoo Lee, Efficient parity placement schemes for tolerating up to two disk failures in disk arrays, Journal of Systems Architecture, 2022, 46(15): 13831402. ?DH1 混合碼 ?DH2 HDD1/HDD2 ChihShing Tau and TzoneI Wang, ―Efficient parity placement schemes for tolerating triple disk failures in RAID architectures,‖ in Proceedings of the17th International Conference on Advanced Information Networking and Applications (AINA’03), Xi’an, China, Mar 2022. ?HDD1 HDD1/HDD2 ?HDD2 HoVer Codes James Lee Hafner, HoVer Erasure Codes For Disk Arrays, International Conference on Dependable Systems and Networks (DSN39。 Experience, 27(9):995–1012, September 1997. ReedSolomon Codes ?Operate on binary words of data, posed of w bits, where 2w ≥ n+m. ReedSolomon Codes ?Operate on binary words of data, posed of w bits, where 2w ≥ n+m. ReedSolomon Codes ?This 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. ReedSolomon Codes ?Codes are based on linear algebra. ?First, consider the data words as a column vector D: ReedSolomon Codes ?Codes are based on linear algebra. ?Next, define an (n+m)*n ―Distribution Matrix‖ B, whose first n rows are the identity matrix: ReedSolomon Codes ?Codes are based on linear algebra. ?B*D equals an (n+m)*1 column vector posed of D and C (the coding words): ReedSolomon Codes ?This means that each data and coding word has a corresponding row in the distribution matrix. ReedSolomon Codes ?Suppose m nodes fail. ?To decode, we create B’ by deleting the rows of B that correspond to the failed nodes. ReedSolomon Codes ?Suppose m nodes fail. ?To decode, we create B’ by deleting the rows of B that correspond to the failed nodes. ?You’ll note that B’*D equals the survivors. ReedSolomon Codes ?Now, invert B’: ReedSolomon Codes ?Now, invert B’: ?And multiply both sides of the equation by B’1 ReedSolomon Codes ?Now, invert B’: ?And multiply both sides of the equation by B’1 ?Since B’1*B’ = I, You have just decoded D! ReedSolomon Codes ?Now, invert B’: ?And multiply both sides of the equation by B’1 ?Since B’1*B’ = I, You have just decoded D! ReedSolomon Codes ?To Summarize: Encoding ?Create distribution matrix B. ?Multiply B by the data to create coding words. ?To Summarize: Decoding ?Create B’ by deleting rows of B. ?Invert B’. ?Multiply B’1 by the surviving words to reconstruct the data. ReedSolomon Codes ?Two Final Issues: ?1: How to create B? ?All square submatrices must be invertible. ?Derive from a Vandermonde Matrix J. S. Pl
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1