对擦除编码的简要介绍

擦除编码是目前分布式存储系统中的一个非常热门的话题。它已经在 Ceph 的路线图中存在近一年了，Swift 团队最近也提出了讨论。双方都计划实现擦除编码功能，所以我认为提供一个关于擦除编码原理的概述可能很有趣。在开始之前，我想指出 我对此文不承担任何功劳。我只是阅读了 Hakim Weatherspoon 和 John D. Kubiatowicz 从加州大学伯克利分校计算机科学部撰写的精彩白皮书 “Erasure Coding vs. Replication: A Quantitative Comparison”。非常感谢他们。在阅读论文时，我发现他们对擦除编码的介绍对于像我这样的新手来说很容易理解 :).

一、介绍 ¶

擦除编码提供冗余，而无需严格复制的开销。擦除编码将一个对象划分为 m 个片段并将其重新编码为 n 个片段，其中 n > m。我们称 r = m/n < 1 为编码率。

速率 r 编码将存储成本提高 1/r 倍。擦除编码的关键特性是，原始对象可以从任何 m 个片段重建。例如，对一个块使用 r = 1/4 编码会将该块划分为 m = 16 个片段并将原始 m 个片段编码为 n = 64 个片段；将存储成本提高四倍。擦除编码是复制和 RAID 系统的超集。例如，为每个块创建四个副本的系统可以由一个 (m = 1, n = 4) 擦除编码来描述。RAID 级别 1、4 和 5 可以由一个 (m = 1, n = 2, (m = 4, n = 5) 和 (m = 4,n = 5) 擦除编码来描述，分别。

二、数据完整性 ¶

在恶意环境中进行擦除编码需要精确识别失败或损坏的片段。如果无法识别，则尝试重建块；即 (n, m) 组合。因此，系统需要检测何时片段已损坏并丢弃它。安全的验证哈希方案可以同时用于识别和验证每个片段。必然的是，任何 m 个经过正确验证的片段都可以用于重建块。这种方案可能会增加带宽和存储需求，但可以证明仍然比复制少得多。

很简单，不是吗？