Reed-Solomon 是

目前工业界最常用的纠删码（Erasure Code）之一，本文主要讲述其在存储领域如何进行数据容错，并且附带简要实现思路。

Reed-Solomon 原理

Reed-Solomon 通过数据冗余实现容错，并且根据冗余数据的大小实现与其一致的容错。

比如我有两个数字 1 和 2，那么可以通过构造出 3 = 1 + 2，并将其存储起来，就能在某个数字丢失的时候将 3 取出并恢复原来的数字。假设数字 1 丢失了，那么可以通过 3-2 = 1 的方式重新得到正确的数据。

上面通过简单相加的过程实现了最简单的数据冗余，但怎么实现更强的容错呢？我们可以设定不一样的系数。比如令 x = 1, y = 2，那么可以通过构造不同的系数得到不同的冗余数据，下面随便举几个例子。

$$0 \times x + 0 \times y = 0$$ $$0 \times x + 1 \times y = 2$$ $$1 \times x + 0 \times y = 1$$ $$1 \times x + 2 \times y = 5$$ $$2 \times x + 1 \times y = 4$$

当 x 丢失的时候，我们可以发现公式 1、2 无法为重构 x 提供帮助的，因为其系数为 0，冗余的值与 x 线性无关。

所以，正常情况下，我们需要尽可能地保证方程要包含所有数据块的信息。

P.S. XORing Elephants: Novel Erasure Codes for Big Data 论文中的 LRCs 能够通过构造两个半数线性无关的行列式，通过 14%的追加冗余，提高近乎两倍的数据恢复效率

但是我们需要对现实中计算机存储的数据冗余，这又要如何做到呢？

首先，我们知道计算机存储的数据都是由 0 和 1 组成的，因此可以对文件读进内存，并且以 byte 为单位对数据本身进行计算。

RS 的冗余计算方式是将文件切成 K 个数据块（data shards），假设 N 个数据块排成一列，通过对数据从开头到结尾进行多项式计算来生成 M 个校验块（parity shards），这样得到的校验块就包含了 N 个数据块的信息。

刚刚提到的“对数据从开头到结尾进行多项式计算”，其实就是用线性代数的知识对矩阵进行简单的加减乘除。

首先是编码矩阵的选取，常见的有 Vandermonde 和 Cauchy，klauspost/rs 的默认实现是 Vandermonde 矩阵，通过将其与上半部分（k*k）的逆矩阵相乘得到（k* k）的单位矩阵和（m*k）的下半部分矩阵。

$$ \begin{bmatrix} 1 & 1 & 1 & \dots & 1 \\ 1 & 2 & 2^2 & \dots & 2^{k-1} \\ 1 & 3 & 3^2 & \dots & 3^{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & k+m & (k+m)^2 & \dots & (k+m)^{k-1} \end{bmatrix} \Longrightarrow \begin{bmatrix} 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 1 \\ \alpha & \beta & \gamma & \dots & \delta \\ \epsilon & \zeta & \eta & \dots & \theta \end{bmatrix} $$

得到编码矩阵后，将其与数据块相乘，就能得到校验块。

但是如果直接相乘，就会导致一个问题：因为 K 个 1byte 数据的行列式计算结果很有可能会大于 1byte，导致校验块的大小不可控。

这个时候就要引入伽罗华域，伽罗华域又名有限域，包含有限个元素，这里我们选取包含 2^8 个元素的伽罗华域，在这个域中，每个元素可以表示为 8bit 的字节，所以校验块的大小不会膨胀。GF(2^8)中的所有多项式都可以通过多项式生成元 g 通过求幂得到。即域中的任意元素 $a \in \lbrace 0, 1, 2, \ldots, 255 \rbrace$，都存在一个 k，使得 a = g^k。为了更方便地在 GF 中进行乘除，我们需要创建两个表：对数表和指数表。对数表可以根据给定的指数查找 GF 中相应的对数；指数表则是反过来，根据对数得到 GF 中对应的指数。

打表：先确定 GF(2^8)的素多项式 $P_8(x) = x^8 + x^4 + x^3 + x^2 + 1 = 285$ 和生成元 $g(x)=2$，而后按顺序递推得到

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

logTable := make([]int, 256)
expTable := make([]int, 256)
logTable[0] = -1 // undefined
expTable[0] = 1 // g^0 = 1
for i := 1; i < 256; i++ {
  expTable[i] = expTable[i-1] << 1 // g = 2
  for expTable[i] >= 256 {         // if expTable[i] bigger than x^8
    expTable[i] ^= 0x11d // P_8(x) = x^8 + x^4 + x^3 + x^2 + 1
  }
  logTable[expTable[i]] = i
}
logTable[1] = 0 // exptable[255]=exptable[0]=1, and g^0 must be 1, so reset logtable[1] = 0

// logTable: -1 0 1 25 2 50 26 198 3 223 51 238 27 104 199 75 4 100 224 14 52 141 239 129 28 193 105 248 200 8 76 113 5 138 101 47 225 36 15 33 53 147 142 218 240 18 130 69 29 181 194 125 106 39 249 185 201 154 9 120 77 228 114 166 6 191 139 98 102 221 48 253 226 152 37 179 16 145 34 136 54 208 148 206 143 150 219 189 241 210 19 92 131 56 70 64 30 66 182 163 195 72 126 110 107 58 40 84 250 133 186 61 202 94 155 159 10 21 121 43 78 212 229 172 115 243 167 87 7 112 192 247 140 128 99 13 103 74 222 237 49 197 254 24 227 165 153 119 38 184 180 124 17 68 146 217 35 32 137 46 55 63 209 91 149 188 207 205 144 135 151 178 220 252 190 97 242 86 211 171 20 42 93 158 132 60 57 83 71 109 65 162 31 45 67 216 183 123 164 118 196 23 73 236 127 12 111 246 108 161 59 82 41 157 85 170 251 96 134 177 187 204 62 90 203 89 95 176 156 169 160 81 11 245 22 235 122 117 44 215 79 174 213 233 230 231 173 232 116 214 244 234 168 80 88 175
// expTable: 1 2 4 8 16 32 64 128 29 58 116 232 205 135 19 38 76 152 45 90 180 117 234 201 143 3 6 12 24 48 96 192 157 39 78 156 37 74 148 53 106 212 181 119 238 193 159 35 70 140 5 10 20 40 80 160 93 186 105 210 185 111 222 161 95 190 97 194 153 47 94 188 101 202 137 15 30 60 120 240 253 231 211 187 107 214 177 127 254 225 223 163 91 182 113 226 217 175 67 134 17 34 68 136 13 26 52 104 208 189 103 206 129 31 62 124 248 237 199 147 59 118 236 197 151 51 102 204 133 23 46 92 184 109 218 169 79 158 33 66 132 21 42 84 168 77 154 41 82 164 85 170 73 146 57 114 228 213 183 115 230 209 191 99 198 145 63 126 252 229 215 179 123 246 241 255 227 219 171 75 150 49 98 196 149 55 110 220 165 87 174 65 130 25 50 100 200 141 7 14 28 56 112 224 221 167 83 166 81 162 89 178 121 242 249 239 195 155 43 86 172 69 138 9 18 36 72 144 61 122 244 245 247 243 251 235 203 139 11 22 44 88 176 125 250 233 207 131 27 54 108 216 173 71 142 1

下面以 ABCDEFGHIJKLNMOP 为例，模拟 RS 生成校验块并在部分数据块丢失的情况下恢复全量数据的过程。

令 K = 4，M = 2，将其切成 4 份，并且读取其 byte，我们可以得到其二进制表示（ASCII）。

$$ \begin{bmatrix} A& B& C& D \\ E& F& G& H \\ I& J& K& L \\ N& M& O& P \\ \end{bmatrix} → \begin{bmatrix} 65 & 66 & 67 & 68 \\ 69 & 70 & 71 & 72 \\ 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ \end{bmatrix} $$

再通过与(4+2,4)的 GF(2^8)编码矩阵相乘，得到校验块 $$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 27 & 28 & 18 & 20 \\ 28 & 27 & 20 & 18 \\ \end{bmatrix}\times \begin{bmatrix} 65 & 66 & 67 & 68 \\ 69 & 70 & 71 & 72 \\ 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ \end{bmatrix}= \begin{bmatrix} 65 & 66 & 67 & 68 \\ 69 & 70 & 71 & 72 \\ 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ 81 & 82 & 83 & 73 \\ 85 & 86 & 87 & 37 \\ \end{bmatrix} $$

令第一和第二个数据块丢失，模拟重构数据块的过程 $$ \begin{bmatrix} 1& 0& 0& 0 \\ 0& 1& 0& 0 \\ 0& 0& 1& 0 \\ 0& 0& 0& 1 \\ 27& 28& 18& 20 \\ 28& 27& 20& 18 \\ \end{bmatrix}× \begin{bmatrix} d_1 \\ d_2 \\ 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ \end{bmatrix}= \begin{bmatrix} d_1 \\ d_2 \\ 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ 81 & 82 & 83 & 73 \\ 85 & 86 & 87 & 37 \\ \end{bmatrix} $$

$$\downarrow$$ $$ \begin{bmatrix} 0& 0& 1& 0 \\ 0& 0& 0& 1 \\ 27& 28& 18& 20 \\ 28& 27& 20& 18 \\ \end{bmatrix}× \begin{bmatrix} d_1 \\ d_2 \\ 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ \end{bmatrix}= \begin{bmatrix} 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ 81 & 82 & 83 & 73 \\ 85 & 86 & 87 & 37 \\ \end{bmatrix} $$ $$\downarrow$$ $$ \begin{bmatrix} d_1 \\ d_2 \\ 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ \end{bmatrix}= \begin{bmatrix} 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ 81 & 82 & 83 & 73 \\ 85 & 86 & 87 & 37 \\ \end{bmatrix}× \begin{bmatrix} 0& 0& 1& 0 \\ 0& 0& 0& 1 \\ 27& 28& 18& 20 \\ 28& 27& 20& 18 \\ \end{bmatrix}^{-1}= \begin{bmatrix} 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ 81 & 82 & 83 & 73 \\ 85 & 86 & 87 & 37 \\ \end{bmatrix}× \begin{bmatrix} 208 & 107 & 104& 210\\ 107 & 208 & 210& 104\\ 1& 0& 0& 0 \\ 0& 1& 0& 0\\ \end{bmatrix}= \begin{bmatrix} 65 & 66 & 67 & 68 \\ 69 & 70 & 71 & 72 \\ 73 & 74 & 75 & 76 \\ 77 & 78 & 79 & 80 \\ \end{bmatrix} $$ $$\downarrow$$ $$ d_1 = [65,66,67,68] $$ $$ d_2 = [69,70,71,72] $$

因此，我们可以通过构造校验块并将每个数据块和校验块分开存储的方式对数据进行容错。

reference

https://drmingdrmer.github.io/tech/distributed/2017/02/01/ec.html

https://www.cnblogs.com/codingtao/p/5916786.html

https://en.wikipedia.org/wiki/Vandermonde_matrix