-1

我有一些与 RAID 存储结构有关的问题。首先，让我展示一张 RAID 系统的图片。[RAID][1][1]：https://i.stack.imgur.com/Whd6B.png。据我了解，每个磁盘都被分割成多个条带。编码或解码是沿着条带完成的，条带是条带的集合。假设每个条带由 k 个数据条和 t 个奇偶校验条组成。如果我使用基于 GF(2^w) 构建的 Reed-Solomon (RS) 代码，则每个大小为“q”字节的条带将分为 q/k 个符号，每个符号由 w 位组成。

我的问题：

  1. 当我们谈论 RS 编码/解码时，我们是将每个条带视为一个 RS 符号还是将条带中的每个 w 位视为 RS 符号，尽管条带中的每个 w 位都与 GF 中的相同 w 位元素相乘（ 2^w)。描述：
  • 当我在做 RAID 系统的软件实现时，我从每篇研究论文中学到的东西，尤其是这篇论文：“A Performance Evaluation and Exam of Open-Source Erasure
    Coding Libraries For Storage”，是strip, P=[p0,p1,...,p_{t-1}] 计算为矩阵乘法为 P=CxD，其中 D=[d0,d1,...,d_{k-1}] 和C 是 txk 柯西矩阵（我以基于柯西矩阵的编码为例）。
  • 当我阅读另​​一篇专注于 RS 编码的硬件实现的论文时：“A Low Complexity Design of Reed Solomon Code Algorithm for Advanced RAID System”，他们似乎将每个条带称为 RS 符号。我的意思是这怎么可能。假设我们使用 GF(2^8)，条带的大小可以变成只有 8 位吗？或者，在硬件实现中，人们只是简单地使用更高阶的有限域来构建 RAID 系统？
  1. 我有时看到人们将 RAID 存储系统描述为驱动器，其中“每个驱动器分为多个条带”。那么，驱动器和磁盘这两个术语有什么区别？它们可以互换使用吗？
4

1 回答 1

0

每条

每组块可以被认为是一个矩阵，令r = 磁盘数，c = 每个块的#字节，那么矩阵就是一个r行 x c列的矩阵。对矩阵的每一列执行类似 Reed Solomon 的编码和解码，其中矩阵的每一列都被视为r个字节的数组。

开源擦除

擦除编码可能与 Raid 编码不同。擦除编码可以基于修改后的 Vandermonde 矩阵，维基百科称之为原始视图 Reed Solomon 的系统编码的转置：

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Systematic_encoding_procedure:_The_message_as_an_initial_sequence_of_values

如您阅读的论文中所示，擦除也可以基于柯西矩阵。

对于 Raid，对应于 P 奇偶校验的编码矩阵行都是 1 的有效异或，Q 奇偶校验是 2 的幂（在 GF(2^8) 中），R 奇偶校验是 4 的幂，...。与生成奇偶校验（基于生成多项式的余数）的标准 Reed Solomon 不同，Raid 生成校验子。

在所有 3 种情况下，编码矩阵都是由行扩充以编码奇偶校验的单位矩阵，但 Vandermonde、Cauchy 和 Raid 的扩充行不同。

驱动器或磁盘

在这种情况下，它们的含义相同。

编码

令d = 每个条带的数据行数，并且p = 每个条带的奇偶校验行数，然后可以使用编码矩阵的最后p行矩阵乘法来实现编码，一个p乘d编码子矩阵乘以d通过c数据行矩阵。

解码

开源擦除分两步完成。设e = 已擦除数据行数。e擦除的数据行是通过将编码矩阵的前d行对应（相同的行索引）与未擦除的数据行进行重新生成，将d乘以d子矩阵反转，然后反转矩阵的e行对应对擦除的数据行产生一个e乘d矩阵，用于将d乘以c非擦除数据行矩阵以重新生成数据。重新生成数据后，通过重新编码现在重新生成的数据来重新生成任何奇偶校验行。

RAID解码是不同的。如果数据或 P 行中只有一次擦除，则使用 XOR 重新生成已擦除的行。如果在 Q、R、...行中只有一个擦除，则重新编码被擦除的行。对于多行擦除，GF() 代数通常用于重新生成擦除的数据。这也可以通过基于已擦除行的索引的 2 次方创建一个 e 乘 e 矩阵来完成，将e乘以e矩阵反转，然后将反转后的e乘以e乘以第p个编码行的第一个e编码矩阵，然后使用e by c矩阵来重新生成擦除的数据。

请注意，这些解码方法都不是旨在纠正错误和擦除的传统 Reed Solomon 解码方法。修改后的 Vandermonde 矩阵与原始视图系统编码的编码相同，但擦除解码与上述相同。

如果编码是基于 Wiki 所说的“BCH 视图”，那么奇偶校验行是实际奇偶校验（生成多项式的余数），并且在解码过程中会生成e行校验子，一旦生成了e行校验子，那么可以完成像 Raid 这样的擦除数据的再生。我不知道基于“BCH 视图”编码的纠删码。

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Systematic_encoding_procedure

根据评论更新。

Raid（标准版）不使用 Cauchy 矩阵。Raid 也不使用修改后的 Vandermonde 矩阵。Cauchy 和修改后的 Vandermonde 矩阵主要由 jerasure 类型算法使用，而不是 Raid。Raid 编码基于 2 的幂，{1 1 1 1 1 ... } {2 4 8 16 ...}，{4 16 64 ...}。

Raid 是面向字节的，而不是面向位的。“条带”的每一列都被视为一个字节数组。

Raid（和擦除）编码和解码是在矩阵的列上执行的，将每一列视为一个独立的字节数组。

至于在 GF(2^8) 内操作的限制，这将 Raid 限制为 255 个数据驱动器和 255 个奇偶校验（综合症）驱动器。对于数据和奇偶校验，Jerasure 总共限制为 255 个（BCH 视图）或 256 个（原始视图）驱动器。我不知道有任何实现接近这些限制。Raid 6（2 个奇偶校验，P 和 Q）指定最多 32 个驱动器，但这是一个任意选择。一个常见的 jerasure 实现将文件分成 17 个逻辑剥离称为分片并添加 3 个分片以进行奇偶校验，其中每个分片通常存储在不同的 Raid 驱动器块或不同的节点或不同的服务器上。

于 2020-10-02T15:45:28.167 回答