这是一篇关于纠删码（Erasure Coding）的技术文章，涵盖了纠删码的基本概念、在分布式系统中的应用、使用基础、不那么基础的使用情况以及实现纠删码等方面的内容：

• Erasure Coding Basics（纠删码基础）：

  • 配置纠删码围绕公式(k + m = n)，其中(k)是数据分割的块数，(m)是生成的奇偶校验块数，(n)是生成的总块数。纠删码常以(k+m)元组表示，不同文献中变量名可能不一致。
  • 提供了一个小计算器来展示不同(k)和(m)设置的效果，纠删码对存储提供商有吸引力，能以最小的存储开销提供容错能力，如 Backblaze B2 运行(17+3)，OVH Cloud 使用(8+4)，Scaleway 使用(6+3)。
  • 纠删码主要的权衡是减少存储空间，但增加了读取数据的请求，适合不常访问的数据存储系统。它是一类算法的统称，一般可使用 Reed-Solomon 码实现，也有针对特定子集的更高效算法，如 RAID 系列。MDS 纠删码具有特定的多数派性质，其他纠删码有不同的权衡。

• Applications in Distributed Systems（在分布式系统中的应用）：

  • Space and Tail Latency Improvements（空间和尾部延迟改进）：在具有固定副本集的系统中，可减少存储成本和增加数据耐久性，如将 blob/object 存储或 NFS 存储的副本从 3 个改为(15)个（(10+5)纠删码），可减少一半的数据存储量和提高容错能力。在缓存系统中使用(k+m)纠删码可改善存储空间和尾部延迟，但会增加 IOPS/QPS 或 CPU 消耗。
  • Quorum Systems（仲裁系统）：在 quorum 系统中，纠删码在读取方面匹配良好，但在写入方面只有特定情况下（如(N)个副本且期望容错(f)时，使用((N - 2f)+f)的纠删码）才有节省。RS-Paxos 和 HRaft 探讨了纠删码在 Paxos 和共识协议中的应用及相关问题。

• Usage Basics（使用基础）：

  • 计算纠删码有成熟的Jerasure和Intel Intelligent Storage Acceleration Library，可使用pyeclib从 Python 中访问纠删码实现，并应用于 HRaft 的自适应纠删码方案，通过示例展示了不同副本数量下的编码和效率情况。

• Usage Not So Basics（不那么基础的使用情况）：

  • Decoding Cost Variability（解码成本可变性）：解码性能随需要恢复的数据块数量而变化，从三个数据块解码(3+2)代码计算简单，而从两个数据块和一个奇偶校验块解码则涉及线性方程组求解，计算量增加。有论文比较了不同纠删码实现及其在不同块大小和数据块数量下的性能。
  • Library Differences（库差异）：Liberasurecode 抽象了常见的纠删码实现库，但实现并不等价，它添加了必要的元数据且不可禁用或修改。Jerasure 和 ISA-L 是常见的纠删码库，Jerasure 对输出进行置换，ISA-L 不进行置换，可读取编码数据的子集或超集。除 Jerasure 和 ISA-L 外，还有tahoe-lafs/zfec等其他实现，可根据具体情况选择更优化的库。

• Implementing Erasure Codes（实现纠删码）：

  • 可将纠删码视为将 1 个文件转换为(n)个块的魔法函数，无需理解其数学原理即可使用。构造(n)个块涉及一般的线性代数，包括 Galois 域，可参考相关资料。
  • 主要有两个维度需要研究：一是实现确切的 MDS 编码和解码算法，二是如何最有效地实现该算法。对于不同的奇偶校验块数量(m)，有不同的算法，一般多数 MDS 码通过矩阵乘法实现，编码是矩阵乘法，解码是求解线性方程组。Gaussian 消元是最简单但最慢的解码方法，有更高效的方法如使用 Fast Fourier Transforms。
  • 实现纠删码的效率有不同层次，包括用 C 实现并依赖编译器自动矢量化、使用向量库或编译器内在函数、手写向量化实现以及针对特定(k+m)配置进行优化等，可参考"Fast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration Techniques"。
• References（参考资料）：提供了References as BibTeX以及建议从James S. Plank’s publications开始深入研究。