【正文】 碼， (p1)*(p1)的數(shù)據(jù)陣列， p為素?cái)?shù) ? 校驗(yàn)相關(guān) ——水平校驗(yàn)單元作為 “ 數(shù)據(jù) ” 參與對角線校驗(yàn) 陣列碼和線性碼的關(guān)系 00 01 02 03 04 10 11 12 13 14 20 21 22 23 24 30 31 32 33 34 40 41 42 43 44 Q0 Q1 Q2 Q3 Q4 P0 P1 P2 P3 P4 Liberation碼 J. S. Plank, ―The RAID6 Liberation Codes‖, 6th USENIX Conference on File and Storage Technologies, San Francisco, 2022, pp. 97–110. ?編碼矩陣 1的個數(shù)最少，但不意味著校驗(yàn)計(jì)算性能最優(yōu) 其他水平碼 Cheng Huang, Lihao Xu, ―STAR: An Efficient Coding Scheme for 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. ?雙容錯 MDS垂直碼 ?基于完全圖的完全 1因子分解（ P1F） ?無素?cái)?shù)限制 ——圖論領(lǐng)域的一個猜測：對所有偶數(shù) n， Kn存在 P1F，每個 P1F又能構(gòu)造兩個規(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, . ?雙容錯 “ 垂直碼 ” ——每個磁盤都是既放置數(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%！ ? 條紋組小，局部性好，分布式存儲系統(tǒng)下故障模式性能好 ? 也是搜索可行編碼，最高容錯 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。06), Philadelphia, PA, USA, Jun, 2022, pp. 217226. ?非 MDS混合碼 HoVer Codes ?一些例子 內(nèi)容 ?RAID、容錯編碼 ?ReedSolomon編碼 ?二進(jìn)制線性碼 ?陣列碼 ?利用組合數(shù)學(xué)工具構(gòu)造容錯編碼 內(nèi)容 ?RAID、容錯編碼 ?ReedSolomon編碼 ?二進(jìn)制線性碼 ?陣列碼 ?利用組合數(shù)學(xué)工具構(gòu)造容錯編碼 雙容錯編碼的圖表示 Zhou Jie,Wang Gang, Liu Xiaoguang, Liu Jing, ―The Study of Graph Depositions and Placement of Parity and Data to Tolerate Two Failures in Disk Arrays: Conditions and Existance,‖ Chinese Journal of Computer, Vol. 26, No. 10, Oct, 2022, . ? 簡單圖表示雙容錯線性碼 ? 頂點(diǎn)：校驗(yàn)單元（校驗(yàn)組） ? 邊：數(shù)據(jù)單元 v1 v2 v3 w1 w2 w3 雙容錯編碼的圖表示 ?圖劃分表示陣列碼 disk0 disk1 disk2 disk3 disk4 判斷雙容錯性質(zhì) ?兩個故障盤構(gòu)成帶兩端點(diǎn)的封閉路 disk0 disk1 A unrecoverable 2erasure CPSS 判斷雙容錯性質(zhì)（二） ?兩個故障盤構(gòu)成圈 disk2 disk3 A unrecoverable 2erasure CDSS 拉丁方 ? n*n矩陣，元素出自一個 n元集合，每行 /列沒有重復(fù)元 ? 漢密爾頓拉丁方：任何兩列 /行 /符號構(gòu)成漢密爾頓圈 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 PIHLatin Gang Wang, Sheng Lin, Xiaoguang Liu, Guangjun Xie, Jing Liu, ―Combinatorial Constructions of MultiErasureCorrecting Codes with Independent Parity Symbols for Storage Systems,‖ IEEE PRDC 2022, Melbourne, Victoria, Austrilia, Dec, 2022, pp. 6168. ?推廣 EVENODD，無素?cái)?shù)限制 PDHLatin Wang Gang, Liu Xiaoguang, Lin Sheng, Xie Guangjun, Liu Jing, ―Generalizing RDP Codes Using the Combinatorial Method,‖ (to appear) IEEE NCA 2022, Cambridge, MA, USA, July, 2022. ?推廣 RDP，無素?cái)?shù)限制 ?有利于校驗(yàn)計(jì)算性能 其他一些工作 ?用容錯編碼提高 P2P系統(tǒng)可用性 Guangping Xu, Gang Wang, Jing Liu, ―A hybrid redundancy approach for data availability in structured P2P work systems,‖ IEEE PRDC 2022, Melbourne, Victoria, Austrilia, Dec, 2022, pp. 195199. ?用容錯編碼實(shí)現(xiàn) MPI并行程序容錯計(jì)算 ?用 GPU加速容錯編碼計(jì)算性能