【正文】 存儲系統(tǒng)容錯編碼簡介 內容 ?RAID、容錯編碼 ?ReedSolomon編碼 ?二進制線性碼 ?陣列碼 ?利用組合數(shù)學工具構造容錯編碼 內容 ?RAID、容錯編碼 ?ReedSolomon編碼 ?二進制線性碼 ?陣列碼 ?利用組合數(shù)學工具構造容錯編碼 RAID ?Redundant Arrays of Inexpensive Disks Redundant Arrays of Independent Disks ?容量 ?性能 ?可靠性 ? Chen, P. M., Lee, E. K., Gibson, G. A., Katz, R. H., and Patterson, D. A. ―RAID: highperformance, reliable secondary storage.‖ ACM Computing Surveys 26(2), pp. 143185, June 1994. RAID結構 ?Data Striping stripe unit stripe 0~4KB1 4KB~ 8KB1 8KB~ 12KB1 12KB~ 16KB1 16KB~ 20KB1 RAID結構 ?Redundancy 0~4KB1 RAID結構 ? 編碼： d1 XOR d2 XOR … XOR dn = p ? 解碼： di = p XOR d1 XOR … XOR di1 XOR di1 … ? 解碼： pnew = p XOR diold XOR dinew RAID結構 ?data unit、 parity unit ?RAID5：更新負載均勻分布 RAID結構 RAID5的讀寫 RAID5的讀寫 RAID5布局 ? Edward K. Lee, Randy H. Katz, ―The Performance of Parity Placements in Disk Arrays‖, IEEE Transactions on Computers, vol. 42 no. 6, pp. 651664, 1993. RAID5布局 RAID5布局 RAID0 ? HuiI 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. RAID0 ? Gang Wang, Xiaoguang Liu, Sheng Lin, Guangjun Xie, Jing Liu, ―Constructing Double and Tripleerasurecorrecting Codes with High Availability Using Mirroring and Parity Approaches‖, ICPADS2022. What is an Erasure Code? ? J. S. Plank, ―Erasure Codes for Storage Applications‖, Tutorial of the 4th Usenix Conference on File and Storage Technologies, San Francisco, CA, Dec, 2022. When are they useful? ?Anytime you need to tolerate failures. When are they useful? ?Anytime you need to tolerate failures. When are they useful? ?Anytime you need to tolerate failures. When are they useful? ?Anytime you need to tolerate failures. When are they useful? ?Anytime you need to tolerate failures. When are they useful? ?Anytime you need to tolerate failures. When are they useful? ?Anytime you need to tolerate failures. Terms amp。 Definitions ?Number of data disks: n ?Number of coding disks: m ?Rate of a code: R = n/(n+m) ?Identifiable Failure: “Erasure” The problem, once again Issues with Erasure Coding ? Performance ? Encoding ?Typically O(mn), but not always. ? Update ?Typically O(m), but not always. ? Decoding ?Typically O(mn), but not always. Issues with Erasure Coding ?Space Usage ?Quantified by two of four: ?Data Devices: n ?Coding Devices: m ?Sum of Devices: (n+m) ?Rate: R = n/(n+m) ?Higher rates are more space efficient, but less faulttolerant. Issues with Erasure Coding ?Flexibility ?Can you arbitrarily add data / coding nodes? ?(Can you change the rate)? ?How does this impact failure coverage? Trivial Example: Replication ?MDS ?Extremely fast encoding/decoding/update. ?Rate: R = 1/(m+1) Very space inefficient ?There are many replication/based systems ?(P2P especially). Less Trivial Example: Simple Parity ? Patterson D A, Gibson G A, Katz R H, ―A case for redundant arrays of inexpensive disks (RAID)‖, ACM International Conference on Management of Data, Chicago, ACM Press, 1988, pp. 109116. ? P. M. Chen, E. K. Lee, G. A. Gibson, R. H. Katz, and D. A. Patterson. RAID: Highperformance, reliable secondary storage. ACM Computing Surveys, 26(2):145–185, June 1994. Evaluating Parity ?MDS ?Rate: R = n/(n+1) Very space efficient ?Optimal encoding/decoding/update: ?n1 XORs to encode amp。 decode ?2 XORs to update ?Extremely popular (RAID Level 5). ?Downside: m = 1 is limited. Unfortunately ?Those are the last easy things you’ll see. ?For (n 1, m 1), there is no consensus on the best coding technique. ?They all have tradeoffs. Why is this such a pain? ?Coding theory historically has been the purview of coding theorists. ?Their goals have had their roots elsewhere (noisy munication lines, byzantine memory systems, etc). ?They are not systems programmers.