1 详情

生词表

  学术科研领域有一些词语比较陌生，记录一些遇到的生词。

纠删码（erasure code）

翻译软件经常将 erasure code 翻译为可擦除码，其实有更专业的术语叫“纠删码”。

  组成原理中遇到的海明码和CRC 冗余校验编码都属于纠删码。具体地说，纠删码是在 $k$ 位原始数据上增加 $r$ 位校验位生成的，具有一定容错能力的 $n=k+r$ 位编码。

RS 码

  RS 码（Reed-Solomon 码，里德-所罗门码）是一个典型的纠删码。基础原理是线性代数。
  若有 $k$ 个原始数据块 $D _ 1,\cdots,D _ k$，记数据矩阵 $\boldsymbol D=[D _ 1,D _ 2,\cdots,D _ k]^\mathrm T$，我们可以构造一个特殊的矩阵 $\boldsymbol B$： $$\boldsymbol B =\left[\begin{matrix}\boldsymbol I _ {k\times k}\\ \boldsymbol V _ {r\times k}\end{matrix}\right]= \left[\begin{matrix}1&0&\cdots&0\\0&1&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&1\\v _ {1,1}&v _ {1,2}&\cdots&v _ {1,k}\\v _ {2,1}&v _ {2,2}&\cdots&v _ {2,k}\\\vdots&\vdots&\ddots&\vdots\\v _ {r,1} & v _ {r,2}&\cdots&v _ {r,k}\end{matrix}\right]$$

矩阵 $\boldsymbol V$ 的选择，要满足 $\boldsymbol B$ 的任意 $k$ 行都是线性无关的。可以选择 Vandermonde 矩阵(1)。

1. $$\boldsymbol V _ {r\times k} = \begin{bmatrix}1&1&1&\cdots&1\\1&a _ 1&a _ 1^2&\cdots& a _ 1^{k-1}\\1&a _ 2&a _ 2^2&\cdots&a _ 2^{k-1}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&a _ {r-1}&a _ {r-1}^2&\cdots&a _ {r-1}^{k-1}\end{bmatrix}$$

  然后通过 $\boldsymbol P=\boldsymbol V\boldsymbol D$ 可以得到 $r=n-k$ 个校验块 $P _ 1,\cdots,P _ r$。实际存储时将校验块和数据块一起存储，即存储 $\begin{bmatrix}\boldsymbol D\\\boldsymbol P\end{bmatrix}$。
  当存储数据发生至多 $r$ 个错误，且已知具体是哪 $r$ 个错误时，就可以从 $\begin{bmatrix}\boldsymbol D\\\boldsymbol P\end{bmatrix}$ 摘取正确无误的 $k$ 行，根据 $\boldsymbol B$ 中对应行，通过矩阵求逆还原出 $\boldsymbol D$。具体可以参考这篇博客。

RAID

  Redundant Array of Independent（旧称 Inexpensive） Disks，即独立磁盘冗余阵列，其实就是用多个独立的磁盘组成在一起形成一个大的磁盘系统，从而实现比单块磁盘更好的存储性能和更高的可靠性。

• RAID 0：每个磁盘各存各的，没有校验块。
  优点：存储性能高。
  缺点：没有检错纠错能力，可靠性差。
• RAID 1：同一个数据块有两个备份。
  优点：具有检错能力。
  缺点：存储性能折半，且没有纠错能力（一旦出错，不知道是哪个备份错）。
• RAID 3：使用奇偶校验码，有一个校验块。
  优点：具有检错能力，在已知错误磁盘的情况下可以纠错 $1$ 块磁盘。
  缺点：纠错能力太差，且一个校验块承担大量读写操作容易损坏。

文献

NCScale: Toward Optimal Storage Scaling via Network Coding	在线阅读	下载
LogECMem: Coupling Erasure-Coded In-memory Key-Value Stores with Parity Logging	在线阅读	下载