消去コード

符号理論において、消失訂正符号とは、ビット誤りではなくビット消失を仮定した前方誤り訂正（FEC）符号であり、 k個のシンボルからなるメッセージを、 n個のシンボルからなるより長いメッセージ（コードワード）に変換し、 n個のシンボルのサブセットから元のメッセージを復元できるようにするものである。分数r  =  k / nは符号化率と呼ばれる。分数k'/k （k'は復元に必要なシンボル数を表す）は受信効率と呼ばれる。復元アルゴリズムでは、n個のシンボルのうちどのシンボルが失われたかが既知であると想定される。

歴史

消失訂正符号化は1960年にアーヴィング・リードとギュスターヴ・ソロモンによって発明されました。 ^{[ 1 ]}

消失訂正符号化方式には様々な種類があります。最も一般的な消失訂正符号は 、リード・ソロモン符号、 低密度パリティ検査符号（LDPC符号）、 ターボ符号です。^{[ 1 ]}

2023年現在、現代のデータストレージシステムは、3つのアプローチのいずれかを使用して、データ損失なしで少数のディスクの完全な障害に耐えるように設計できます。^{[ 2 ] [ 3 ] [ 4 ]}

• レプリケーション
• レイド
• 消失訂正符号

技術的にはRAIDは一種の消去符号と見なすことができますが、^{[ 5 ]} 「RAID」は通常、単一のホストコンピュータ（単一障害点）に接続されたアレイを指します。一方、「消去符号化」は通常、複数のホストを指します。^{[ 3 ]} RAIS（ Redundant Array of Inexpensive Servers ） と呼ばれることもあります。消去符号により、これらのホストのいずれかが停止しても、処理を継続することができます。^{[ 4 ] [ 6 ]}

ブロックレベルのRAIDシステムと比較して、オブジェクトストレージ消去符号化には、より回復力のあるいくつかの重要な違いがあります。^{[ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]}

最適な消去コード

最適な消失訂正符号は、 n個の符号語シンボルのうち任意のk個で元のメッセージを復元できるという特性を持つ（つまり、最適な受信効率を持つ）。最適な消失訂正符号は、最大距離分離符号（MDS符号）である。

パリティチェック

パリティ チェックは、 n  =  k + 1の特殊なケースです。k個の値 のセットからチェックサムが計算され、k個のソース値に追加されます。 ${\displaystyle \{v_{i}\}_{1\leq i\leq k}}$

${\displaystyle v_{k+1}=-\sum _{i=1}^{k}v_{i}.}$

k  + 1 個の値の集合は、チェックサムに関して整合しています。これらの値のうちの1つが消去された場合でも、残りの変数を合計することで簡単に復元できます。 ${\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}$ ${\displaystyle v_{e}}$

${\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}$

RAID 5は、XORを使用したパリティチェック消去コードの広く使用されているアプリケーションです。^{[ 1 ]}

多項式オーバーサンプリング

例: Err-mail ( k  = 2)

k = 2 という単純なケースでは 、2つの元のシンボル間の線に沿って異なる点をサンプリングすることで冗長シンボルを作成できます。これは、err-mail と呼ばれる単純な例で示されています。

アリスは自分の電話番号（555629）をerr-mailを使ってボブに送りたい。err-mailは電子メールと同じように動作するが、

1. 郵便物の約半分が紛失します。
2. 5 文字を超えるメッセージは無効です。
3. 非常に高価です（航空便と同様）。

送信したメッセージを確認するようボブに求める代わりに、アリスは次の方式を考案します。

1. 彼女は自分の電話番号をa = 555、b = 629の 2 つの部分に分割し、2 つのメッセージ「A=555」と「B=629」をボブに送信します。
2. 彼女は、かつ となるような線形関数（この場合は）を構築します。${\displaystyle f(i)=a+(ba)(i-1)}$ ${\displaystyle f(i)=555+74(i-1)}$ ${\displaystyle f(1)=555}$ ${\displaystyle f(2)=629}$

1. 彼女は値f（3）、f（4）、f（5）を計算し、3つの冗長メッセージ「C = 703」、「D = 777」、「E = 851」を送信します。

ボブは、 f ( k )の形式が であることを知っています。ここで、aとbは電話番号の2つの部分です。ここで、ボブが「D=777」と「E=851」を受け取ったとします。 ${\displaystyle f(i)=a+(ba)(i-1)}$

ボブは、受け取った値（f (4)とf (5)）からaとbの値を計算することで、アリスの電話番号を復元できます。ボブは任意の2つのerrメールを使ってこの手順を実行できるため、この例の消失訂正符号の消失率は40%です。

アリスは電話番号を1通のerr-mailで暗号化することはできないことに注意してください。なぜなら、err-mailは6文字で構成されており、1通のerr-mailメッセージの最大文字数は5文字だからです。もしアリスが電話番号を分割して送信し、ボブにそれぞれの受信確認を求めるとしたら、少なくとも4通のメッセージ（アリスから2通、ボブから2通）を送信することになります。したがって、この例の5通のメッセージで済む消失訂正符号は非常に経済的です。

この例は少し不自然です。あらゆるデータセットに適用できる真に汎用的な消失訂正符号を実現するには、与えられたf ( i ) 以外の何かが必要になります。

一般的なケース

上記の線形構築は多項式補間に一般化できます。さらに、点は有限体上で計算されます。

まず、少なくともn次、通常は 2 のべき乗の位数を持つ有限体F を選択します。送信者はデータシンボルに 0 からk  − 1 までの番号を付けて送信します。次に、p ( i ) がデータシンボルiと等しくなるように、位数kの（ラグランジュ）多項式p ( x )を構築します。次に、 p ( k )、...、p ( n − 1 )を送信します 。受信側は、k個のシンボルを正常に受信した場合、多項式補間を使用して失われたパケットを回復することもできます。 Fの位数が 2 ^b未満（b はシンボル内のビット数）の場合、複数の多項式を使用できます。

送信者は、シンボルkからn  − 1 を「オンザフライ」で構築できます。つまり、シンボルの送信間でワークロードを均等に分散します。 受信側が計算を「オンザフライ」で実行したい場合は、シンボルi < kが正常に受信された場合はq ( i ) = p ( i )となり、シンボル i < k が受信されなかった場合は q ( i ) = 0 となるような新しい 多項式 qを構築できます。ここで、 r ( i ) = p ( i ) − q ( i ) とします。まず、シンボルi < kが正常に受信され た場合はr ( i ) = 0 であることがわかります。次に、シンボル i ≥ k が正常に受信された場合は、 r ( i ) =  p  ( i ) − q (  i )を計算 できます。したがって、 rを構築し、それを評価して失われたパケットを見つけるのに十分なデータ ポイントがあります。したがって、送信者と受信者の両方に必要な操作はO ( n ( n  −  k )) 回であり、オンザフライで操作するために必要なスペースは O ( n  −  k ) 回のみです。

現実世界での実装

このプロセスはリード・ソロモン符号によって実装され、符号語はヴァンダーモンド行列を使用して有限体上に構築されます。

最も実用的な消失訂正符号は体系的な符号であり、元のk個のシンボルのそれぞれが、エンコードされていないコピーとしてn個のメッセージシンボルの1つとして見つかる可能性がある。 ^{[ 12 ]} （秘密分散を サポートする消失訂正符号では体系的な符号は使用されない）。

ほぼ最適な消去コード

準最適な消失訂正符号では、メッセージを復元するために (1 + ε) k個のシンボルが必要です（ただし、ε>0）。ε を小さくするとCPU時間が長くなります。準最適な消失訂正符号は、訂正能力と計算量とのトレードオフです。実用的なアルゴリズムでは、線形時間計算量でエンコードとデコードが可能です。

ファウンテン符号（レートレス消失訂正符号とも呼ばれる）は、準最適消失訂正符号の注目すべき例である。kシンボルのメッセージを実質的に無限の符号化形式に変換することができる。つまり、任意の数の冗長シンボルを生成し、それらすべてを誤り訂正に使用できる。受信機は、 k個よりわずかに多い符号化 シンボルを受信した時点で復号を開始できる。

再生成コードは、既存のエンコードされたフラグメントから失われたエンコードされたフラグメントを再構築（修復とも呼ばれる）する問題に対処する。この問題は、エンコードされた冗長性を維持するための通信が問題となる分散ストレージシステムで発生する。^{[ 12 ]}

ストレージシステムにおける消失訂正符号化の応用

消失訂正符号化は現在、信頼性の高いデータストレージの標準的な手法となっている。^{[ 13 ] [ 14 ] [ 15 ]} 特に、リード・ソロモン消失訂正符号化のさまざまな実装は、Apache Hadoop、 Linuxに組み込まれているRAID-6、Microsoft Azure、Facebookのコールドストレージ、Backblaze Vaultsで使用されている。^{[ 15 ] [ 12 ]}

ストレージシステムの障害からの復旧には、従来はレプリケーションが用いられていました。しかし、レプリケーションは無駄なバイト数という点で大きなオーバーヘッドをもたらします。そのため、データセンターなどで使用されるような大規模ストレージシステムでは、消失訂正符号化ストレージがますます多く採用されています。ストレージシステムで使用される最も一般的な消失訂正符号化は、リード・ソロモン（RS）符号です。これは、パリティブロックと呼ばれる既知のデータ片から欠損データを再生するために用いられる高度な数学式です。( k ,  r )RS符号では、「チャンク」と呼ばれるデータブロックの集合が( k  +  r )個のチャンクに符号化されます。チャンクの集合全体でストライプが構成されます。この符号化は、 ( k  +  r )個のチャンクのうち少なくともk個が利用可能であれば、データ全体を復旧できるように設計されています。つまり、( k ,  mr')RS符号化ストレージは最大m個の障害に耐えることができます。 (これは、 n  =  k  +  rの標準 RS( n ,  k ) 表記とは異なります。)

RS(10,4)

例： FacebookのHDFS（現在はApache Hadoopの一部）で使用されているRS(10, 4)コードでは、10MBのユーザーデータが1MBのブロック10個に分割されます。さらに、冗長性を確保するために、1MBのパリティブロックが4つ追加されます。これにより、最大4つの同時障害を許容できます。ここでのストレージオーバーヘッドは14/10 = 1.4倍です。^{[ 16 ]}

完全複製システムの場合、最大4つの同時障害に耐えるためには、10MBのユーザーデータを4回複製する必要があります。この場合のストレージオーバーヘッドは50/10 = 5倍になります。

これにより、完全なレプリケーションと比較して、消去コード化ストレージのストレージ オーバーヘッドが低いことがわかり、それが今日のストレージ システムの魅力となっています。

ヒッチハイカー方式はRSコーディングと組み合わせることで、データブロックの再構築に必要な計算量とデータ転送量を削減できます。HDFSコーデックとしても実装されていますが、使用するにはポリシーを手動で定義する必要があります。^{[ 12 ]}

ホットデータ

当初、消失訂正符号は「コールド」（めったにアクセスされない）データを効率的に保存するコストを削減するために使用されていましたが、消失訂正符号は、より単純な冗長化方式（ミラーリング）と比較して、「ホット」（より頻繁にアクセスされる）データを提供する際のパフォーマンスを向上させるためにも使用できます。^{[ 12 ]}

消去コーディングによるパフォーマンス向上の典型的な例はRAID 5で、 RAID 1と比べて必要なハード ドライブの数が少なくても、同じ単一ドライブ障害保護を提供します。 余分なハード ドライブは、より多くのデータを保存するために使用でき、 RAID 5 の向上した読み取り/書き込み速度の乗数を利用できます。 これは、処理能力が十分であれば、 RAID 6 (二重冗長性: 1 つのパリティと 1 つの消去コーディング) にも当てはまります。^{[ 1 ]}一般化 RAID は、任意の数の冗長ドライブで動作できます。 一般化 RAID には 2 つの表記法があります: RAID7。x はx 台の冗長ドライブを備えたシステムを指し、 x台のドライブが故障しても回復が可能です。^{[ 17 ]}また、RAID N+M は N 台の通常データ ドライブと M 台の冗長ドライブを備え、M 台のドライブのうちどれかが故障してもすべてのデータを回復できます。^{[ 1 ]}

より高度な例としては、EC-Cache（クラスタキャッシュ）、つまり複数のノードに分散されたキャッシュがあります。このようなシステムでは、あるノードがより頻繁にアクセスされるアイテムをホストしている場合、負荷の不均衡が生じる可能性があります。この問題に対処する一般的な方法は、選択的レプリケーション（つまり、より頻繁にアクセスされるオブジェクトに対してより多くのレプリカを作成する）です。しかし、この方法は利用可能なメモリ量に制限されます。すべてのオブジェクトをk個の分割とr個の冗長ユニットに個別に分割することで、メモリの無駄を最小限に抑えながら、完全な負荷分散を実現できます。^{[ 12 ]}

例

以下に、さまざまなコードの実装例をいくつか示します。

ほぼ最適な消去コード

• 竜巻コード
• 低密度パリティ検査符号

近似最適ファウンテン（レートレス消失）符号

• 噴水コード
• オンラインコード
• LTコード
• ラプターコード
• ネットワークコード
• 三角形のコード

最適な消去コード

• XORパリティ。消去可能なシンボルを1つ追加します。RAID4 、RAID5で使用されます。
• リード・ソロモン符号。消失訂正モードで使用すると最適であり、k個のシンボルを追加した場合にk個の消失を許容する。誤り訂正モードで使用する場合も最適であり、フロア( k /2)個の誤りを許容する。
  • Parchiveファイル形式 1.0、2.0、および (オープン) 3.0 は RS を使用します。3.0 は他の線形コードもサポートします。
  • RAID6ではさまざまな最適な消去コードが使用されますが、RS が一般的な選択肢です。
  • Tahoe-LAFSには、Classic RS の実装であるzfecが含まれています。
• 消失耐性体系的符号は、同じシンボルサイズでリードソロモンよりも多くの冗長パケットを可能にするMDS符号である。2ビットのRS(4,2)または3ビットのRS(9,2)を参照。
• 再生コード^{[ 18 ] [ 19 ]}
• その他の最大距離分離可能なコード

参照

• 前方誤り訂正コード。
• 秘密共有（元の秘密が暗号化され、復号クォーラムに達するまで隠蔽される点で異なる）
• スペルアルファベット
• バイナリ消去チャネル

参考文献

1. 「RAID vs. Erasure Coding. What's the Difference? | Blog | Xinnor」。最速かつ最も信頼性の高いソフトウェアRAID | Xinnor。2023年9月3日。 2024年9月18日閲覧。
2. 「Ceph.io — Ceph における Erasure Coding」 . ceph.io. 2014年4月7日. 2024年9月18日閲覧。
3. Lee, Brandon (2023年12月26日). 「RAID vs Erasure Coding vs Replication」 . BDRSuite . 2024年9月18日閲覧。
4. O'Reilly, Jim. 「RAID vs. Erasure Coding」 . www.networkcomputing.com . 2024年9月18日閲覧。
5. Dimitri Pertin、Alexandre van Kempen、Benoît Parrein、Nicolas Normand。「RAID-6消去コードの比較」。情報通信技術に関する第3回中仏ワークショップ、SIFWICT 2015、2015年6月、フランス、ナント。ffhal-01162047f
6. 「IBM Spectrum Scale Erasure Code Editionのフォールトトレランスについて」 www.ibm.com 2024年9月18日閲覧。
7. 「オブジェクトストレージのイレイジャーコーディングとブロックストレージRAID」 . MinIOブログ. 2021年7月27日. 2024年9月18日閲覧。
8. 「データ保護方法としての消去符号化とRAID | Computer Weekly」 ComputerWeekly.com . 2024年9月18日閲覧。
9. Kruth, Peter (2023年10月4日). 「Erasure Code: RAIDのあるべき姿 – Huawei BLOG」 . 2023年10月4日時点のオリジナルよりアーカイブ。2024年9月18日閲覧。
10. 「Erasure Coding 101」 . MinIO Blog . 2022年4月25日. 2024年9月18日閲覧。
11. Bhaskaran, Dinesh Kumar (2018年7月6日). 「なぜ消失訂正符号がデータ回復力の未来なのか」 . 2020年8月7日時点のオリジナルよりアーカイブ。
12. Rashmi Vinayak. 「ビッグデータシステムのための消失訂正符号化：理論と実践」 . 2016. p. 2: セクション「概要」。p. 9: セクション「体系的コード」。p. 12: セクション「コードの再生成」。
13. 「消失訂正符号化—実践と原則」 2016年。
14. Matt Sarrel. 「Erasure Coding 101」 2022年。
15. ブライアン・ビーチ. 「Backblazeがリード・ソロモン消失訂正符号化のソースコードをオープンソース化」 . 2015年.
16. Xia, Mingyuan; Saxena, Mohit; Blaum, Mario; Pease, David A. (2015). HDFSにおける2つの消失訂正符号の物語. FAST '15. pp.  213– 226. ISBN 978-1-931971-20-1。
17. Leventhal, Adam (2009年12月). 「トリプルパリティRAIDとその先：ハードドライブの容量がスループットを上回り続ける中、新たなレベルのRAIDの時代が到来」. ACM Queue . 7 (11): 30– 39. doi : 10.1145/1661785.1670144 .
18. Dimakis, Alexandros G.; Godfrey, P. Brighten; Wu, Yunnan; Wainwright, Martin J.; Ramchandran, Kannan (2010年9月). 「分散ストレージシステムのためのネットワークコーディング」. IEEE Transactions on Information Theory . 56 (9): 4539– 4551. arXiv : cs/0702015 . Bibcode : 2010ITIT...56.4539D . CiteSeerX 10.1.1.117.6892 . doi : 10.1109/TIT.2010.2054295 . S2CID 260559901 .  
19. “home [分散ストレージ向けErasure Coding Wiki]” . 2017年7月31日. 2017年7月31日時点のオリジナルよりアーカイブ。 2023年8月20日閲覧。

外部リンク

• Jerasure は、SIMD 最適化を使用してリード・ソロモンおよびコーシー消去コード技術を実装したフリー ソフトウェア ライブラリです。
• ルイージ・リッツォ著「コンピュータ通信におけるソフトウェアFEC」では、最適な消失訂正符号について解説しています。
• Feclibは、バンド行列を用いるLuigi Rizzoの研究成果をほぼ最適な形で拡張したものです。バンド幅や有限体のサイズなど、多くのパラメータを設定できます。また、現代のCPUの大きなレジスタサイズをうまく活用しています。ただし、前述のほぼ最適なコードとの比較は不明です。
• コードの再生成と消去コードの再構築に関する、分散ストレージ向けコーディング wiki 。
• ECIP（Erasure Code Internet Protocol） は1996年に開発され、インターネット上で初めてFEC（Forward Error Correction）を採用したプロトコルです。商用利用は初めて、スリランカのアーサー・C・クラーク卿のライブ映像をインディアナ州のUIUCにストリーミング配信するために行われました。