了解一下：纠删码（Erasure Code）

Question

半年前撸了一遍海草，这两天跟踪一下，海草半年间做了一些什么升级，看到了 Erasure Code 部分，然后就顺便了解一下纠删码了。

存储变化：

纠删码介绍，来自 EC纠删码原理

Erasure Code（EC），即纠删码，是一种前向错误纠正技术（Forward Error Correction，FEC，说明见后附录），主要应用在网络传输中避免包的丢失， 存储系统利用它来提高 存储 可靠性。相比多副本复制而言， 纠删码能够以更小的数据冗余度获得更高数据可靠性， 但编码方式较复杂，需要大量计算 。纠删码只能容忍数据丢失，无法容忍数据篡改，纠删码正是得名与此。 

一图示意原理

存储效率对比

EC Scheme

EC Scheme	#Data Nodes	#Parity Nodes	#Nodes Needed	#Failures Recoverable	#Nodes to Read to Recover Data
3+2	3, 2	3	2	5	2
4+2	4, 2	4	2	6	2
5+2	5, 2	5	2	7	2
6+3	6, 3	6	3	9	3
10+ where x is a value from 1 to 9	N.A	10	x	10+x	x

----------------------------

总数据块 = 原始数据块 + 校验块

n = k + m

允许故障：任意m个块，包括原始数据块 和 校验块

从k个原始数据块中计算出m个校验块。

将这k+m个数据块分别存放在k+m个硬盘上，就能容忍任意m个硬盘故障。

当出现硬盘故障时，只要任意选取k个幸存数据块就能计算得到所有的原始数据块。

同理，如果将k+m个数据块分散在不同的存储节点上，就能容忍m个节点故障。

n = k + m

k值影响数据恢复代价。k值越小，数据分散度越小，故障影响面越大，重建代价也就越大；k值越大，多路数据拷贝增加的网络和磁盘负载越大，重建代价也越大。
m值影响可靠性与存储成本。取值大，故障容忍度高；m 取值小，数据冗余低。在两者之间权衡。
k 取值 有时候也和数据块对齐，k/m 按照磁盘故障率来选择。

Reed-Solomon（RS）码

Hadoop 3.0 纠删码技术分析（Erasure Coding）

纠删码技术（Erasure coding）简称EC，是一种编码容错技术。最早用于通信行业，数据传输中的数据恢复。它通过对数据进行分块，然后计算出校验数据，使得各个部分的数据产生关联性。当一部分数据块丢失时，可以通过剩余的数据块和校验块计算出丢失的数据块。

里德-所罗门码 Reed-Solomon（RS）码是存储系统较为常用的一种纠删码，它有两个参数k和m，记为RS(k，m)。如下图所示，k个数据块组成一个向量被乘上一个生成矩阵（Generator Matrix）GT从而得到一个码字（codeword）向量，该向量由k个数据块和m个校验块构成。如果一个数据块丢失，可以用(GT)-1乘以码字向量来恢复出丢失的数据块。RS(k，m)最多可容忍m个块（包括数据块和校验块）丢失。

比如：我们有 7、8、9 三个原始数据，通过矩阵乘法，计算出来两个校验数据 50、122。这时原始数据加上校验数据，一共五个数据：7、8、9、50、122，可以任意丢两个，然后通过算法进行恢复。

条形布局（Striping Layout）

条（stripe）是由若干个相同大小的单元（cell）构成的序列。文件数据被依次写入条的各个单元中，当一个条写满之后再写入下一个条，一个条的不同单元位于不同的数据块中。这种分布方式称为条形布局。

优点：

1. 客户端缓存数据较少
2. 无论文件大小都适用

缺点：

1. 会影响一些位置敏感任务的性能，因为原先在一个节点上的块被分散到了多个不同的节点上
2. 和多副本存储策略转换比较麻烦

什么是纠删编码方案

https://docs.netapp.com/sgws-113/index.jsp?topic=%2Fcom.netapp.doc.sg-admin%2FGUID-9A6EEF24-E976-4FEA-86BB-9BBB321F27C6.html

可以根据计划使用的存储池中的存储节点和站点数量选择可用的纠删编码方案。纠删编码方案可控制为每个对象创建的数据片段的数量以及奇偶校验片段的数量。

StorageGRID 系统使用 Reed-Solomon 纠删编码算法。该算法会将对象分段为 k 数据片段，并计算 m 奇偶校验片段。k + m = n 片段分布在 n 存储节点之间，以提供数据保护。对象最多可承受 m 丢失或损坏的片段。 k 检索或修复对象需要片段。

在配置擦除编码配置文件时，请确认存储池仅包含一个或三个或更多站点。请勿使用默认存储池，所有存储节点或包含默认站点的存储池所有站点。

注： 如果存储池包含两个站点，则无法配置擦除编码配置文件。

包含三个或更多的存储池的纠删编码方案 站点

下表列出 StorageGRID ，适用于包含三个或更多站点的存储池。它指定每个方案的建议站点和存储节点数。支持的纠删编码方案旨在提供站点丢失保护。一个站点可能会丢失，但对象仍可访问。

纠删编码方案（k + m）	已部署站点的最小数量	每个站点的建议存储节点数	建议的存储节点总数	站点丢失保护？
4+2	3	3 星	9	是
6+2	4	3 星	12	是
8+2	5	3 星	15	是
6+3.	3	4	12	是
9+3.	4	4	16	是
2+1	3	3 星	9	是
4+1	5	3 星	15	是
6+1	7	3 星	21	是

每个站点至少需要三个存储节点。

在确定要使用的纠删编码方案时，应根据修复所需的网络流量要求（更多的片段等于更多的网络流量）平衡容错（通过具有更多的奇偶校验分段来实现）。例如，在选择 4+2 方案和 6+3 方案时，如果需要额外的奇偶校验和容错功能，请选择 6+3 方案。如果在节点修复期间网络资源受到限制，从而减少了网络使用量，请选择 4+2 方案。

注： 如果您不确定要使用的方案，请选择 4+2 或 6+3 ，或者联系支持部门。通常，除非 m您的应用程序不需要较高的容错能力，否则应避免使用 +1 方案。

单站点存储池的纠删编码方案

纠删编码非常适合需要高效数据保护的单站点部署，只需一个纠删编码副本，而不是多个复制副本。仅包含一个站点的存储池支持上表中列出的所有纠删编码方案，前提是该站点包含足够数量的存储节点。例如， 2+1 纠删编码方案要求存储池包含三个或更多存储节点，而 6+3 方案则要求存储池至少包含九个存储节点。

纠删编码的优势，劣势和要求

在决定是使用复制还是纠删编码来保护对象数据不会丢失之前，您应了解纠删编码的优点，缺点和要求。

纠删编码的优势

与复制相比，纠删编码可提高可靠性，可用性和存储效率。

1. 可靠性：可靠性是根据容错能力来衡量的，即可以在不丢失数据的情况下持续发生的并发故障的数量。通过复制，多个相同的副本会存储在不同的节点上以及不同的站点上。通过纠删编码，对象会编码为数据和奇偶校验片段，并分布在多个节点和站点上。这种分散方式可同时提供站点和节点故障保护。与复制相比，纠删编码可提高可靠性，而存储成本相当。
2. 可用性：可用性可以定义为在存储节点出现故障或无法访问时检索对象的功能。与复制相比，纠删编码可以以相当的存储成本提高可用性。
3. 存储效率：对于相似级别的可用性和可靠性，通过纠删编码保护的对象比通过复制保护的相同对象占用的磁盘空间更少。例如，复制到两个站点的 10 MB 对象会占用 20 MB 的磁盘空间（两个副本），而采用 6+3 纠删编码方案在三个站点之间进行纠删编码的对象只会占用 15 MB 的磁盘空间。

注： 擦除编码对象的磁盘空间计算为对象大小加上存储开销。存储开销百分比是奇偶校验片段数除以数据片段数。

纠删编码的缺点

与复制相比，纠删编码具有以下缺点：

1. 需要增加存储节点和站点的数量。例如，如果您使用的纠删编码方案为 6+3 ，则必须在三个不同的站点上至少有三个存储节点。相比之下，如果只复制对象数据，则每个副本只需要一个存储节点。
2. 在分布在不同地理位置的站点之间使用纠删编码时，检索延迟会增加。与在本地复制并提供的对象（客户端连接的同一站点）相比，通过 WAN 连接检索经过纠删编码并分布在远程站点上的对象的对象片段所需时间更长。
3. 在地理位置分散的站点之间使用纠删编码时，检索和修复的 WAN 网络流量使用率较高，尤其是频繁检索的对象或通过 WAN 网络连接进行对象修复。
4. 当您在站点间使用纠删编码时，最大对象吞吐量会随着站点间网络延迟的增加而急剧下降。这一减少是由于 TCP 网络吞吐量相应减少 StorageGRID ，从而影响 StorageGRID 系统存储和检索对象片段的速度。
5. 提高计算资源的利用率。

纠删编码要求

纠删编码最适合以下要求：

1. 大于 1 MB 的对象。
   注意： 由于管理与纠删编码副本关联的片段数量会产生开销，因此请勿对小于 200 KB 的对象使用纠删编码。
2. 长期或冷存储，用于存储不经常检索的内容。
3. 高数据可用性和可靠性。
4. 防止发生完整的站点和节点故障。
5. 存储效率。
6. 需要高效数据保护的单站点部署，只需一个纠删编码副本，而不是多个复制副本。
7. 站点间延迟小于 100 毫秒的多站点部署。