存儲(chǔ)系統(tǒng)容錯(cuò)編碼簡(jiǎn)介-文庫(kù)吧
2025-11-09 08:53 本頁(yè)面
【正文】 ?(They don’t care…) 內(nèi)容 ?RAID、容錯(cuò)編碼 ?ReedSolomon編碼 ?二進(jìn)制線性碼 內(nèi)容 ?RAID、容錯(cuò)編碼 ?ReedSolomon編碼 ?二進(jìn)制線性碼 ?陣列碼 ?利用組合數(shù)學(xué)工具構(gòu)造容錯(cuò)編碼 ReedSolomon Codes ? The only MDS coding technique for arbitrary n amp。 m. ? This means that m erasures are always tolerated. ? Have been around for decades. ? Expensive. J. S. Plank. A tutorial on ReedSolomon coding for faulttolerance in RAIDlike systems. Software – Practiceamp。 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. Plank and Y. Ding. Note: Correction to the 1997 tutorial on ReedSolomon coding. Software – Practice amp。 Experience, 35(2):189–194,2022. ?2: Will modular arithmetic work? ?NO!!!!! (no multiplicative inverses) ?Instead, you must use Galois Field arithmetic. ReedSolomon Codes ?(n+m) n的范德蒙矩陣 ?基本變換 ?任意兩列可交換 ?任何一列可以乘以一個(gè)非 0數(shù) ?任意兩列可做如下變換： Ci=Ci+c*Cj， c非 0 ReedSolomon Performance ? Encoding: O(mn) ? More specifically: mS [ (n1)/BXOR + n/BGFMult ] ? S = Size of a device ? BXOR = Bandwith of XOR (3 GB/s) ? BGFMult = Bandwidth of Multiplication over GF(2w) ?GF(28): 800 MB/s ?GF(216): 150 MB/s ReedSolomon Performance ? Update: O(m) ? More specifically: m+1 XORs and m multiplications. ReedSolomon Performance ? Decoding: O(mn) or O(n3) ? Large devices: dS [ (n1)/BXOR + n/BGFMult ] ? Where d = number of data devices to reconstruct. ? Yes, there’s a matrix to invert, but usually that’s in the noise because dSn n3. ReedSolomon Bottom Line ?Space Efficient: MDS ?Flexible: ?Works for any value of n and m. ?Easy to add/subtract coding devices. ?Publicdomain implementations. ?Slow: ?nway dot product for each coding device. ?GF multiplication slows things down. Cauchy ReedSolomon Codes J. Blomer, M. Kalfane, M. Karpinski, R. Karp, M. Luby, and D. Zuckerman. An XORbased erasureresilient coding scheme. Technical Report TR95048, International Computer Science Institute, August 1995. ?1: Use a Cauchy matrix instead of a Vandermonde matrix: Invert in O(n2). ?2: Use neat projection to convert Galo
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1