这就是冗余的样子
冗余码*广泛应用于计算机系统中，以提高数据存储的可靠性。 在 Yandex 中，它们被用于许多项目中。 例如，在我们的内部对象存储中使用冗余代码而不是复制可以节省数百万美元，而不会牺牲可靠性。 但尽管冗余码被广泛使用，但对冗余码如何工作的清晰描述却非常罕见。 那些想要了解的人大约面临以下情况（来自 ):
我叫 Vadim，在 Yandex 开发内部对象存储 MDS。 在本文中，我将用简单的语言描述冗余码（Reed-Solomon 和 LRC 码）的理论基础。 我将告诉您它是如何工作的，无需复杂的数学和罕见的术语。 最后我将给出在 Yandex 中使用冗余代码的示例。
我不会详细考虑许多数学细节，但我将为那些想要更深入研究的人提供链接。 我还要指出，一些数学定义可能并不严格，因为本文不是为数学家准备的，而是为想要了解问题本质的工程师准备的。
* 在英语文献中，冗余码通常称为擦除码。
1.冗余码的本质
所有冗余代码的本质都极其简单：存储（或传输）数据，以便在发生错误（磁盘故障、数据传输错误等）时数据不会丢失。
在大多数冗余码中，数据被分为n个数据块，其中m块冗余码被计算，总共有n+m个块。 冗余码的构造方式使得仅使用 n + m 块的一部分即可恢复 n 块数据。 接下来，我们将仅考虑块冗余码，即将数据分为块的代码。
要恢复所有 n 个数据块，您需要至少有 n + m 个块，因为您无法仅通过 n-1 个块来获得 n 个块（在这种情况下，您必须“凭空取出 1 个块”）空气”）。 n + m 块的 n 个随机块是否足以恢复所有数据？ 这取决于冗余码的类型，例如，Reed-Solomon 码允许您使用任意 n 个块恢复所有数据，但 LRC 冗余码并不总是如此。
数据存储
在数据存储系统中，通常，每个数据块和冗余代码块都被写入单独的磁盘。 那么，如果任意一个磁盘发生故障，仍然可以恢复并读取原始数据。 即使多个磁盘同时发生故障，也可以恢复数据。
数据传输
冗余码可用于在不可靠的网络上可靠地传输数据。 传输的数据被分成块，并为它们计算冗余码。 数据块和冗余代码块都通过网络传输。 如果任意块（最多一定数量的块）出现错误，数据仍然可以通过网络传输而不会出现错误。 例如，里德-所罗门码用于通过光通信线路和卫星通信传输数据。
* 还有一些数据不被分成块的冗余码，例如汉明码和CRC码，广泛用于以太网中的数据传输。 这些是用于纠错编码的代码，它们旨在检测错误，而不是纠正错误（汉明码还允许部分纠正错误）。
2.里德-所罗门码
Reed-Solomon 码是使用最广泛的冗余码之一，发明于 1960 世纪 1980 年代，并于 XNUMX 世纪 XNUMX 年代首次广泛用于光盘的大规模生产。
理解里德所罗门码有两个关键问题：1）如何创建冗余码块； 2）如何利用冗余码块恢复数据。 让我们来寻找它们的答案吧。
为了简单起见，我们将进一步假设 n=6 和 m=4。 其他方案依次类推。
如何创建冗余代码块
每个冗余码块都独立于其他块进行计数。 所有n个数据块用于对每个块进行计数。 下图中，X1-X6 为数据块，P1-P4 为冗余代码块。
所有数据块的大小必须相同，并且可以使用零位进行对齐。 生成的冗余代码块的大小将与数据块的大小相同。 所有数据块都分为字（例如，16 位）。 假设我们将数据块分成 k 个字。 那么所有的冗余码块也将被分为k个字。
为了计算每个冗余块的第i个字，将使用所有数据块的第i个字。 它们将根据以下公式计算：
这里的值x是数据块的字，p是冗余代码块的字，所有的alpha、beta、gamma和delta都是专门选择的数字，对于所有i都是相同的。 必须马上说的是，所有这些值都不是普通的数字，而是伽罗瓦域的元素；运算+、-、*、/不是我们大家熟悉的运算，而是对伽罗瓦域的元素引入的特殊运算场地。
为什么需要伽罗瓦域？
看起来一切都很简单：我们将数据分成块，将块分成单词，使用数据块的单词我们计算冗余代码块的单词 - 我们得到冗余代码块。 一般来说，它是这样工作的，但问题在于细节：
- 如上所述，字长是固定的，在我们的示例中为 16 位。 上述 Reed-Solomon 码的公式是这样的：当使用普通整数时，计算 p 的结果可能无法使用有效大小的字来表示。
- 恢复数据时，上述公式将被视为必须求解才能恢复数据的方程组。 在求解过程中，可能需要将整数相除，从而导致无法在计算机内存中准确表示实数。
这些问题阻碍了里德-所罗门码使用整数。 该问题的解决方案是原始的，可以描述如下：让我们想出可以使用所需长度（例如16位）的字来表示的特殊数字，以及对其执行所有操作的结果（加法） 、减法、乘法、除法）也将使用所需长度的字呈现在计算机存储器中。
这种“特殊”数字已经被数学界研究了很长时间；它们被称为域。 字段是一组元素，并为其定义了加法、减法、乘法和除法运算。
Galois* 域是对于该域的任意两个元素的每个运算（+、-、*、/）都有唯一结果的域。 伽罗瓦域可以构造为 2 的幂：2、4、8、16 等（实际上是任何素数 p 的幂，但实际上我们只对 2 的幂感兴趣）。 例如，对于 16 位字，这是一个包含 65 个元素的字段，对于每一对，您都可以找到任何运算（+、-、*、/）的结果。 上述方程中的 x、p、alpha、beta、gamma、delta 的值将被视为伽罗瓦域的元素进行计算。
因此，我们有了一个方程组，可以通过编写适当的计算机程序来构造冗余码块。 使用相同的方程组，您可以执行数据恢复。
* 这不是严格的定义，而是描述。
如何恢复数据
当 n + m 块中的某些块丢失时，需要进行恢复。 这些可以是数据块和冗余代码块。 数据块和/或冗余代码块的缺失将意味着上面的等式中相应的x和/或p变量是未知的。
Reed-Solomon码的方程可以看作是一个方程组，其中所有的alpha、beta、gamma、delta值都是常数，所有可用块对应的x和p都是已知变量，其余的x和p未知。
例如，假设数据块1、2、3和冗余码块2不可用，则对于第i组字，将有以下方程组（未知数用红色标记）：
我们有一个包含 4 个未知数的 4 个方程组，这意味着我们可以求解它并恢复数据！
从这个方程组可以得出关于 Reed-Solomon 码数据恢复的许多结论（n 个数据块，m 个冗余码块）：
- 如果丢失任何 m 个或更少的块，则可以恢复数据。 如果 m+1 或更多块丢失，则数据无法恢复：不可能求解具有 m + 1 个未知数的 m 个方程组。
- 即使要恢复一个数据块，也需要使用剩余块中的任意 n 个，并且可以使用任意冗余码。
我还需要知道什么？
在上面的描述中，我避免了一些需要深入研究数学才能考虑的重要问题。 特别是，我不会对以下内容发表任何言论：
- Reed-Solomon 码的方程组对于任意未知数组合（不超过 m 个未知数）必须有一个（唯一）解。 根据这个要求，选择alpha、beta、gamma、delta的值。
- 方程组必须能够自动构建（取决于哪些模块不可用）并求解。
- 我们需要构建一个伽罗瓦域：对于给定的字长，能够找到任意两个元素的任意运算（+、-、*、/）的结果。
本文末尾引用了有关这些重要问题的文献。
n 和 m 的选择
实际中如何选择n和m？ 实际上，在数据存储系统中，冗余码用于节省空间，因此m总是选择小于n。 它们的具体值取决于许多因素，包括：
- 数据存储的可靠性。 m越大，磁盘故障中能够幸存的次数就越多，即可靠性越高。
- 冗余存储。 m/n 比率越高，存储冗余度越高，系统成本也越高。
- 请求处理时间。 n + m 之和越大，请求的响应时间就越长。 由于读取数据（在恢复期间）需要读取存储在n个不同磁盘上的n个块，因此读取时间将由最慢的磁盘决定。
此外，将数据存储在多个 DC 中对 n 和 m 的选择施加了额外的限制：如果关闭 1 个 DC，则数据必须仍然可供读取。 例如，在3个DC中存储数据时，必须满足以下条件：m >= n/2，否则可能会出现1个DC关闭时数据无法读取的情况。
3.LRC——本地重建码
要使用 Reed-Solomon 码恢复数据，您必须使用 n 个任意数据块。 对于分布式数据存储系统来说，这是一个非常显着的缺点，因为要在一个损坏的磁盘上恢复数据，您将不得不从大多数其他磁盘上读取数据，从而对磁盘和网络造成大量额外负载。
最常见的错误是由于一个磁盘故障或过载而导致一组数据无法访问。 在这种（最常见的）情况下，是否可以以某种方式减少数据恢复的额外负载？ 事实证明你可以：有专门用于此目的的 LRC 冗余码。
LRC（本地重建代码）是 Microsoft 发明的用于 Windows Azure 存储的冗余代码。 LRC的思想尽可能简单：将所有数据块分为两个（或多个）组，并分别读取每个组的部分冗余码块。 然后，一些冗余码块将使用所有数据块进行计数（在LRC中，它们被称为全局冗余码），而另一些则使用两组数据块中的一组（它们被称为局部冗余码）。
LRC由三个数字表示：nrl，其中n是数据块的数量，r是全局冗余码块的数量，l是局部冗余码块的数量。 要在一个数据块不可用时读取数据，您只需要读取 n/l 块 - 这比 Reed-Solomon 码少 l 倍。
例如，考虑 LRC 6-2-2 方案。 X1–X6 — 6 个数据块，P1、P2 — 2 个全局冗余块，P3、P4 — 2 个本地冗余块。
使用所有数据块对冗余代码块P1、P2进行计数。 冗余代码块P3 - 使用数据块X1-X3，冗余代码块P4 - 使用数据块X4-X6。
其余的在 LRC 中通过类比 Reed-Solomon 码来完成。 计算冗余代码块的字数的方程为：
要选择数字 alpha、beta、gamma、delta，必须满足许多条件才能保证数据恢复（即求解方程组）的可能性。 您可以阅读有关它们的更多信息 .
同样在实践中，XOR运算用于计算局部冗余码P3、P4。
LRC 方程组得出许多结论：
- 要恢复任何 1 个数据块，读取 n/l 块（在我们的示例中为 n/2）就足够了。
- 如果r+l块不可用，并且所有块都包含在一组中，则数据无法恢复。 用一个例子很容易解释这一点。 让块 X1-X3 和 P3 不可用：这些是来自同一组的 r + l 个块，在我们的例子中是 4 个。 那么我们就有了一个由 3 个方程组成的系统，其中有 4 个无法求解的未知数。
- 在r+l块不可用的所有其他情况下（当每组中至少有一个块可用时），LRC中的数据可以被恢复。
因此，LRC 在单个错误后恢复数据方面优于 Reed-Solomon 码。 在Reed-Solomon码中，要恢复2块数据，就需要使用n个块，而在LRC中，要恢复4块数据，使用n/l块（在我们的示例中为n/2）就足够了。 另一方面，LRC 在最大允许错误数方面不如 Reed-Solomon 码。 在上面的例子中，Reed-Solomon码可以恢复任意4个错误的数据，而对于LRC来说，当数据无法恢复时，有XNUMX种XNUMX个错误的组合。
更重要的是取决于具体情况，但通常LRC提供的超额负载节省超过了可靠性稍差的存储。
4.其他冗余代码
除了Reed-Solomon码和LRC码之外，还有许多其他冗余码。 不同的冗余码使用不同的数学。 以下是一些其他冗余代码：
- 使用 XOR 运算符的冗余代码。 对n个数据块进行异或运算，得到1块冗余码，即n+1方案（n个数据块，1个冗余码）。 用于 ，其中数据块和冗余代码被循环写入阵列的所有磁盘。
- 基于异或运算的奇偶算法。 允许构建2块冗余码，即n+2方案。
- 基于XOR运算的STAR算法。 允许您构建3块冗余代码，即n+3方案。
- Pyramide 代码是 Microsoft 的另一种冗余代码。
5. 在 Yandex 中使用
许多 Yandex 基础设施项目使用冗余代码来实现可靠的数据存储。 这里有些例子：
- MDS 内部对象存储，我在文章开头写过。
- — Yandex 的 MapReduce 系统。
- (Yandex DataBase) - newSQL 分布式数据库。
MDS 使用LRC 冗余码、8-2-2 方案。 具有冗余代码的数据被写入12个不同DC中不同服务器的3个不同磁盘中：每个DC中4台服务器。 阅读有关此内容的更多信息 .
YT 使用最先实现的 Reed-Solomon 码（方案 6-3）和 LRC 冗余码（方案 12-2-2），其中 LRC 是首选存储方法。
YDB 使用基于偶数和奇数的冗余码（图 4-2）。 关于YDB中的冗余代码已经 .
由于系统的不同要求而采用不同的冗余码方案。 例如，在MDS中，使用LRC存储的数据被同时放置在3个DC中。 对我们来说重要的是，如果任何一个 DC 发生故障，数据仍然可供读取，因此这些块必须分布在各个 DC 上，以便如果任何 DC 不可用，则不可访问的块的数量不超过允许的数量。 在1-8-2方案中，可以在每个DC中放置2个块，那么当任何一个DC关闭时，这4个块将不可用，并且可以读取数据。 无论我们选择哪种方案放置在4个DC中，在任何情况下都应该有(r + l) / n >= 3，即存储冗余至少为0,5%。
在YT中，情况有所不同：每个YT集群完全位于1个DC中（不同的集群位于不同的DC中），因此没有这样的限制。 12-2-2方案提供33%的冗余，即存储数据更便宜，而且它还可以承受最多4个同时的磁盘中断，就像MDS方案一样。
在数据存储和处理系统中使用冗余代码还有很多特性：数据恢复的细微差别、恢复对查询执行时间的影响、数据记录的特性等。我将分别讨论这些和其他特性如果主题有趣的话，在实践中使用冗余代码。
6. 链接
- 关于里德-所罗门码和伽罗瓦域的一系列文章：
他们用通俗易懂的语言更深入地研究数学。 - 微软关于LRC的文章：
第 2 节简要解释了理论，然后讨论了 LRC 的实践经验。 - 偶奇方案：
- 明星计划：
- 金字塔代码：
- MDS 中的冗余代码：
- YT 中的冗余代码：
- YDB中的冗余代码：
来源： habr.com