Loading article…
符号理論において、消去符号は、ビットエラーではなくビット消去を仮定した前方誤り訂正（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)と呼ばれることもあります。消去符号により、これらのホストのいずれかが停止しても操作を継続できます。[ 4 ] [ 6 ]
ブロックレベルのRAIDシステムと比較して、オブジェクトストレージ消去符号化には、より耐障害性を高めるいくつかの重要な違いがあります。[ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]
最適消去符号は、 n個の符号語シンボルのうち任意のk個があれば元のメッセージを復元できるという性質を持つ（すなわち、受信効率が最適である）。最適消去符号は、最大距離分離符号（MDS符号）である。
パリティチェックは、 n = k + 1の特殊なケースです。k個の値のセットから チェックサムが計算され、k個のソース値に追加されます。
k + 1 個の値の集合チェックサムに関して一貫性があります。これらの値のいずれかが、が消去された場合でも、残りの変数を合計することで簡単に復元できます。
k = 2 の単純なケースでは 、2 つの元のシンボル間の線上の異なる点をサンプリングすることによって冗長シンボルを作成できます。これは、err-mail と呼ばれる簡単な例で示されています。
アリスはerr-mailを使ってボブに自分の電話番号（555629）を送りたい。err-mailは電子メールとほぼ同じように機能するが、
アリスはボブに自分が送ったメッセージを確認するよう求める代わりに、次のような計画を立てた。
ボブは、 f ( k )の形式がここで、aとbは電話番号の2つの部分です。ボブが「D=777」と「E=851」を受け取ったとします。
ボブは、受信した値（f（4）とf （5））からaとbの値を計算することで、アリスの電話番号を復元できます。ボブはこの手順を任意の2つのエラーメールを使用して実行できるため、この例の消去コードの成功率は40%です。
アリスの電話番号は6文字なので、1つのエラーメールにすべてエンコードすることはできません。エラーメールの最大長は5文字だからです。もしアリスが電話番号を分割して送信し、ボブに各分割分の受信確認を依頼した場合、少なくとも4つのメッセージを送信する必要があります（アリスからの2つのメッセージと、ボブからの2つの確認メッセージ）。したがって、この例で使用されている5つのメッセージを必要とする消去符号は、非常に効率的です。
この例は少し不自然です。あらゆるデータセットで機能する真に汎用的な消去符号には、与えられたf ( i )以外のものが必要になります。
上記の線形構成は、多項式補間へと一般化できる。さらに、点の計算は有限体上で行われる。
まず、位数が少なくともnである有限体F を選択しますが、通常は 2 のべき乗です。送信者はデータシンボルに 0 からk − 1 までの番号を付けて送信します。次に、データシンボル i と等しくなるような (ラグランジュ) 多項式 p ( x ) を k の位数で作成します。そして、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個のデータブロックのセットが、( k + r )個のチャンクにエンコードされます。チャンクの全体セットがストライプを構成します。このコーディングは、( k + r )個のチャンクのうち少なくともk個が利用可能であれば、データ全体を復旧できるように行われます。つまり、( k , r )RSエンコードストレージは、最大r個の障害に耐えることができます。 （これは、 n = k + rとする標準的な RS( n , k ) 表記とは異なります。）
例: Facebook のHDFS (現在は Apache Hadoop の一部) で使用されているRS(10, 4) コードでは、10 MB のユーザーデータが 10 個の 1MB ブロックに分割されます。次に、冗長性を提供するために 4 つの追加の 1 MB パリティ ブロックが作成されます。これにより、最大 4 つの同時障害に耐えることができます。ここでのストレージ オーバーヘッドは 14/10 = 1.4 ×です。[ 16 ]
完全複製システムの場合、10MBのユーザーデータは、最大4つの同時障害に耐えられるように4回複製する必要があります。この場合のストレージオーバーヘッドは50/10 = 5.0倍になります。
これは、完全複製と比較してイレイジャーコーディングストレージのストレージオーバーヘッドが低いことを示しており、今日のストレージシステムにおいてイレイジャーコーディングストレージが魅力的な理由となっている。
Hitchhikerスキームは、RS コーディングと組み合わせることで、データ ブロックの再構築に必要な計算量とデータ転送量を削減できます。また、HDFS コーデックとしても実装されていますが、使用するにはポリシーを手動で定義する必要があります。[ 12 ]
当初、消去符号は「コールド」（めったにアクセスされない）データを効率的に保存するコストを削減するために使用されていましたが、より単純な冗長化方式（ミラーリング）と比較して、「ホット」（より頻繁にアクセスされる）データを提供するパフォーマンスを向上させるためにも使用できます。[ 12 ]
消去コードによってパフォーマンスが向上する典型的な例は、RAID 5です。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 ]
以下に、各種コードの実装例をいくつか示します。
