冗長性は次のようになります

冗長コード* は、データ ストレージの信頼性を高めるためにコンピュータ システムで広く使用されています。 Yandex では、多くのプロジェクトで使用されています。 たとえば、内部オブジェクト ストレージでレプリケーションの代わりに冗長コードを使用すると、信頼性を犠牲にすることなく数百万ドルを節約できます。 しかし、広く使用されているにもかかわらず、冗長コードがどのように機能するかについての明確な説明は非常にまれです。 理解したい人は、およそ次のような問題に直面します（ ウィキペディア):

私の名前は Vadim です。Yandex で内部オブジェクト ストレージ MDS を開発しています。 この記事では、冗長符号（リードソロモン符号とLRC符号）の理論的基礎を簡単に説明します。 複雑な数学や珍しい用語を使わずに、それがどのように機能するかを説明します。 最後に、Yandex での冗長コードの使用例を示します。

多くの数学的詳細については詳しく検討しませんが、より深く知りたい人のためにリンクを提供します。 また、この記事は数学者を対象としたものではなく、問題の本質を理解したいエンジニアを対象としているため、一部の数学的定義は厳密ではない可能性があることにも注意してください。

* 英語の文献では、冗長コードはイレイジャー コードと呼ばれることがよくあります。

1. 冗長コードの本質

すべての冗長コードの本質は非常に単純です。エラー (ディスク障害、データ転送エラーなど) が発生したときにデータが失われないように、データを保存 (または送信) するものです。

ほとんどの* 冗長コードでは、データは n データ ブロックに分割され、そのうち m ブロックの冗長コードがカウントされ、合計で n + m ブロックになります。 冗長コードは、n + m ブロックの一部のみを使用して n ブロックのデータを復元できるように構築されます。 次に、ブロック冗長コード、つまりデータがブロックに分割されているコードのみを考えます。

データの n ブロックすべてを回復するには、n + m ブロックのうち少なくとも n 個が必要です。n-1 ブロックだけでは n ブロックを取得できないためです (この場合、「薄いブロックから 1 ブロックを取得する必要があります)」空気"）。 すべてのデータを復元するには、n + m ブロックの n 個のランダム ブロックで十分ですか? これは冗長コードのタイプによって異なります。たとえば、リードソロモン コードでは任意の n ブロックを使用してすべてのデータを復元できますが、LRC 冗長コードでは常にそうとは限りません。

データ保存

データ ストレージ システムでは、原則として、データ ブロックと冗長コード ブロックのそれぞれが別のディスクに書き込まれます。 これにより、任意のディスクに障害が発生した場合でも、元のデータを復元して読み取ることができます。 複数のディスクが同時に故障した場合でもデータを復旧できます。

データ転送

冗長コードを使用すると、信頼性の低いネットワーク上でデータを確実に送信できます。 送信されたデータはブロックに分割され、ブロックごとに冗長符号が計算されます。 データ ブロックと冗長コード ブロックは両方ともネットワーク経由で送信されます。 任意のブロック (特定のブロック数まで) でエラーが発生した場合でも、データはエラーなくネットワーク上に送信できます。 たとえば、リードソロモン符号は、光通信回線や衛星通信でデータを送信するために使用されます。

※イーサネットネットワークのデータ伝送に広く使われているハミング符号やCRC符号など、データをブロックに分割しない冗長符号もあります。 これらは誤り訂正符号化のための符号であり、誤りを訂正するのではなく検出するように設計されています（ハミング符号では誤りの部分的な訂正も可能です）。

2. リードソロモン符号

リードソロモン符号は、最も広く使用されている冗長符号の 1960 つで、1980 年代に発明され、XNUMX 年代にコンパクト ディスクの大量生産に初めて広く使用されました。

リードソロモン符号を理解するには、1 つの重要な質問があります。2) 冗長符号のブロックを作成する方法。 XNUMX) 冗長コードブロックを使用してデータを回復する方法。 それらに対する答えを見つけてみましょう。
簡単にするために、さらに n=6 および m=4 と仮定します。 他のスキームも同様に検討されます。

冗長コードブロックを作成する方法

冗長コードの各ブロックは、他のブロックとは独立してカウントされます。 n 個のデータ ブロックすべてが各ブロックのカウントに使用されます。 以下の図では、X1 ～ X6 はデータ ブロック、P1 ～ P4 は冗長コード ブロックです。

すべてのデータ ブロックは同じサイズである必要があり、位置合わせにはゼロ ビットを使用できます。 結果として得られる冗長コード ブロックはデータ ブロックと同じサイズになります。 すべてのデータ ブロックはワード (たとえば 16 ビット) に分割されます。 データ ブロックを k 個のワードに分割するとします。 次に、冗長コードのすべてのブロックも k ワードに分割されます。

各冗長ブロックの i 番目のワードをカウントするには、すべてのデータ ブロックの i 番目のワードが使用されます。 これらは次の式に従って計算されます。

ここで、値 x はデータ ブロックのワード、p は冗長コード ブロックのワード、すべてのアルファ、ベータ、ガンマ、デルタは、すべての i で同じである特別に選択された数値です。 これらの値はすべて通常の数値ではなく、ガロア体の要素であることをすぐに言わなければなりません。演算 +、-、*、/ は、私たち全員に馴染みのある演算ではなく、ガロア体の要素に導入された特別な演算です。分野。

なぜガロア体が必要なのでしょうか?

すべてが単純であるように思えます。データをブロックに分割し、ブロックをワードに分割し、データ ブロックのワードを使用して冗長コード ブロックのワードをカウントします。冗長コード ブロックが得られます。 一般的にはこのように動作しますが、悪魔は細部に宿ります。

1. 上で述べたように、ワード サイズは固定されており、この例では 16 ビットです。 リードソロモン コードの上記の式は、通常の整数を使用すると、有効なサイズのワードを使用して p を計算した結果を表現できない可能性があります。
2. データを回復する場合、上記の式は、データを回復するために解く必要がある連立方程式として考慮されます。 解決プロセス中に、整数を互いに除算する必要がある場合があり、その結果、コンピューターのメモリ内で正確に表現できない実数が生成されます。

これらの問題により、リードソロモン符号に整数を使用できなくなります。 この問題の解決策はオリジナルであり、次のように説明できます。必要な長さのワード (たとえば、16 ビット) を使用して表現できる特別な数値を考え出し、それに対してすべての演算 (加算) を実行した結果を考え出します。 、減算、乗算、除算など）も、必要な長さの単語を使用してコンピュータのメモリに表示されます。

このような「特別な」数値は数学で長い間研究されており、体と呼ばれます。 フィールドは、加算、減算、乗算、除算の演算が定義された要素のセットです。

ガロア* フィールドは、フィールドの任意の 2 つの要素に対する各演算 (+、-、​​、/) の固有の結果が存在するフィールドです。 ガロア体は、2、4、8、16 などの 2 のべき乗の数値に対して構築できます (実際には任意の素数 p のべき乗ですが、実際には 16 のべき乗のみに注目します)。 たとえば、65 ビット ワードの場合、これは 536 個の要素を含むフィールドであり、各ペアについて任意の演算 (+、-、​​、/) の結果を見つけることができます。 上記の方程式の x、p、アルファ、ベータ、ガンマ、デルタの値は、計算のガロア体の要素とみなされます。

したがって、適切なコンピュータ プログラムを作成することで、冗長コードのブロックを構築できる方程式系が得られます。 同じ方程式系を使用して、データ回復を実行できます。

※これは厳密な定義ではなく、説明です。

データを回復する方法

n + m 個のブロックの一部が欠落している場合は、復元が必要です。 これらは、データ ブロックと冗長コード ブロックの両方にすることができます。 データ ブロックや冗長コード ブロックが存在しないということは、対応する x 変数や p 変数が上記の方程式で不明であることを意味します。

リードソロモン コードの方程式は、すべてのアルファ、ベータ、ガンマ、デルタ値が定数、利用可能なブロックに対応するすべての x と p が既知の変数、残りの x と p が含まれる方程式系として見ることができます。は不明です。

たとえば、データ ブロック 1、2、3 と冗長コード ブロック 2 が利用できないとすると、i 番目の単語グループについては次の方程式系になります (未知のものは赤色でマークされます)。

4 つの未知数を含む 4 つの方程式系があり、これを解いてデータを復元できることを意味します。

この方程式系から、リードソロモン コード (n データ ブロック、m 冗長コード ブロック) のデータ回復に関して多くの結論が得られます。

• m 個以下のブロックが失われた場合、データを復元できます。 m+1 以上のブロックが失われた場合、データは復元できません。m + 1 個の未知数を含む m 方程式系を解くことは不可能です。
• データ ブロックを XNUMX つでも回復するには、残りのブロックのうち任意の n 個を使用する必要があり、任意の冗長コードを使用できます。

何を知る必要がありますか？

上記の説明では、数学をさらに深く掘り下げて検討する必要がある多くの重要な問題を避けています。 特に以下の点については何も言いません。

• リードソロモン符号の方程式系は、未知数 (m 個以下) の任意の組み合わせに対する (一意の) 解を持たなければなりません。 この要件に基づいて、アルファ、ベータ、ガンマ、デルタの値が選択されます。
• 方程式系は、(使用できないブロックに応じて) 自動的に構築され、解決できなければなりません。
• ガロア体を構築する必要があります。指定されたワード サイズで、任意の XNUMX つの要素に対する任意の演算 (+、-、​​、/) の結果を見つけることができます。

記事の最後には、これらの重要な問題に関する文献への言及があります。

nとmの選択

実際に n と m を選択するにはどうすればよいですか? 実際には、データ ストレージ システムでは、スペースを節約するために冗長コードが使用されるため、m は常に n より小さい値が選択されます。 それらの具体的な値は、次のような多くの要因によって異なります。

• データストレージの信頼性。 mが大きいほど、ディスク障害に耐えられる回数が多くなり、信頼性が高くなります。
• 冗長ストレージ。 m/n 比が高くなるほど、ストレージの冗長性が高くなり、システムの価格も高くなります。
• リクエストの処理時間。 n + m の合計が大きいほど、リクエストに対する応答時間は長くなります。 データの読み取り (リカバリ中) には、n 個の異なるディスクに保存されている n 個のブロックを読み取る必要があるため、読み取り時間は最も遅いディスクによって決まります。

さらに、複数の DC にデータを保存すると、n と m の選択に追加の制限が課せられます。1 つの DC がオフになっても、データは引き続き読み取り可能でなければなりません。 たとえば、3 つの DC にデータを保存する場合、m >= n/2 という条件を満たす必要があります。そうでないと、1 つの DC がオフになったときにデータを読み取れなくなる可能性があります。

3. LRC - 地域復興コード

リードソロモン符号を使用してデータを回復するには、任意の n 個のデータ ブロックを使用する必要があります。 これは、分散データ ストレージ システムにとって非常に重大な欠点です。XNUMX つの壊れたディスクにデータを復元するには、他のほとんどのディスクからデータを読み取る必要があり、ディスクとネットワークに大きな追加の負荷がかかるからです。

最も一般的なエラーは、XNUMX つのディスクの障害または過負荷により XNUMX つのデータ ブロックにアクセスできなくなることです。 この（最も一般的な）ケースで、データ回復のための過剰な負荷を何らかの形で減らすことは可能でしょうか? この目的専用の LRC 冗長コードがあることがわかりました。

LRC (ローカル再構築コード) は、Windows Azure ストレージで使用するために Microsoft によって発明された冗長コードです。 LRC の考え方は可能な限りシンプルです。すべてのデータ ブロックを XNUMX つ (またはそれ以上) のグループに分割し、各グループの冗長コード ブロックの一部を個別に読み取ります。 次に、一部の冗長コード ブロックはすべてのデータ ブロック (LRC ではグローバル冗長コードと呼ばれます) を使用してカウントされ、一部の冗長コード ブロックは XNUMX つのデータ ブロック グループの XNUMX つを使用してカウントされます (ローカル冗長コードと呼ばれます)。

LRC は XNUMX つの数字、nrl で表されます。n はデータ ブロックの数、r はグローバル冗長コード ブロックの数、l はローカル冗長コード ブロックの数です。 XNUMX つのデータ ブロックが利用できない場合にデータを読み取るには、n/l ブロッ​​クのみを読み取る必要があります。これはリードソロモン コードの XNUMX 分の XNUMX です。

たとえば、LRC 6-2-2 スキームを考えてみましょう。 X1 ～ X6 — 6 データ ブロック、P1、P2 — 2 つのグローバル冗長ブロック、P3、P4 — 2 つのローカル冗長ブロック。

冗長コードブロック P1、P2 はすべてのデータブロックを使用してカウントされます。 冗長コード ブロック P3 - データ ブロック X1 ～ X3 を使用し、冗長コード ブロック P4 - データ ブロック X4 ～ X6 を使用します。

残りはリードソロモン符号と同様に LRC で行われます。 冗長コード ブロックのワードを数える方程式は次のようになります。

数値アルファ、ベータ、ガンマ、デルタを選択するには、データ回復の可能性を保証する (つまり、方程式系を解く) ための多くの条件が満たされなければなりません。 それらについて詳しくは、 статье.
また、実際には、ローカル冗長コード P3、P4 を計算するために XOR 演算が使用されます。

LRC の方程式系からは、次のような多くの結論が得られます。

• 任意の 1 データ ブロックを回復するには、n/l ブロッ​​ク (この例では n/2) を読み取るだけで十分です。
• r + l ブロッ​​クが使用できず、すべてのブロックが 1 つのグループに含まれている場合、データは復元できません。 これを例で説明すると簡単です。 ブロック X3 ～ X3 と P4 を利用できないものとします。これらは同じグループの r + l ブロッ​​クであり、この場合は 3 です。 すると、解けない 4 つの未知数を含む XNUMX つの方程式からなる系ができます。
• r + l ブロッ​​クが利用できない他のすべての場合 (各グループから少なくとも XNUMX つのブロックが利用可能な場合)、LRC 内のデータは復元できます。

したがって、LRC は単一エラー後のデータ回復においてリードソロモン符号よりも優れています。 リードソロモン符号では、データの 2 ブロックを回復するためにも n ブロックを使用する必要がありますが、LRC では、データの 4 ブロックを回復するには、n/l ブロッ​​ク (この例では n/2) を使用するだけで十分です。 一方、LRC は許容される最大誤り数の点でリードソロモン符号に劣ります。 上記の例では、リードソロモン符号は任意の 4 つのエラーに対してデータを回復できますが、LRC の場合、データが回復できない場合には XNUMX つのエラーの組み合わせが XNUMX つあります。

何がより重要かは特定の状況によって異なりますが、多くの場合、LRC によって提供される過剰な負荷の節約は、信頼性が若干劣るストレージよりも重要です。

4. その他の冗長コード

リードソロモン コードと LRC コード以外にも、他にも多くの冗長コードがあります。 冗長コードが異なれば、使用する数学も異なります。 その他の冗長コードは次のとおりです。

• XOR 演算子を使用した冗長コード。 ｎ個のデータブロックに対してＸＯＲ演算を行い、１ブロックの冗長コード、すなわちｎ＋１方式（ｎデータブロック、１冗長コード）を得る。 で使われる RAID 5、データのブロックと冗長コードがアレイのすべてのディスクに周期的に書き込まれます。
• XOR 演算に基づく偶数-奇数アルゴリズム。 2 ブロックの冗長コード、つまり n+2 スキームを構築できます。
• XOR 演算に基づく STAR アルゴリズム。 3 ブロックの冗長コード、つまり n+3 スキームを構築できます。
• ピラミッド コードは、Microsoft のもう XNUMX つの冗長コードです。

5.Yandexでの使用

多くの Yandex インフラストラクチャ プロジェクトでは、信頼性の高いデータ ストレージのために冗長コードが使用されています。 ここではいくつかの例を示します。

• MDS 内部オブジェクト ストレージ。記事の冒頭で説明しました。
• YT — Yandex の MapReduce システム。
• YDB (Yandex Database) - 新しい SQL 分散データベース。

MDS は、LRC 冗長コード、8-2-2 方式を使用します。 冗長コードを持つデータは、12 つの異なる DC (各 DC に 3 つのサーバー) の異なるサーバーにある 4 の異なるディスクに書き込まれます。 これについて詳しくは、 статье.

YT は、最初に実装されたリードソロモン コード (スキーム 6-3) と LRC 冗長コード (スキーム 12-2-2) の両方を使用しており、LRC が優先されるストレージ方式です。

YDB は偶数-奇数ベースの冗長コードを使用します (図 4-2)。 YDBの冗長コードについてはすでに ハイロードで語った.

異なる冗長コード スキームが使用されるのは、システムの要件が異なるためです。 たとえば、MDS では、LRC を使用して保存されたデータは一度に 3 つの DC に配置されます。 いずれかの DC に障害が発生した場合でも、データが引き続き読み取り可能であることが重要です。そのため、いずれかの DC が利用できない場合でも、アクセスできないブロックの数が許容範囲内になるように、ブロックを DC 全体に分散する必要があります。 1-8-2 方式では、各 DC に 2 つのブロックを配置でき、いずれかの DC がオフになると 4 つのブロックが使用できなくなり、データを読み取ることができます。 4 つの DC に配置するときにどのようなスキームを選択するにしても、いずれの場合も (r + l) / n >= 3 でなければなりません。つまり、ストレージの冗長性は少なくとも 0,5% になります。

YT では状況が異なります。各 YT クラスタは完全に 1 つの DC 内に配置されている (異なる DC 内の異なるクラスタ) ため、そのような制限はありません。 12-2-2 スキームは 33% の冗長性を提供します。つまり、データの保存が安価であり、MDS スキームと同様に、最大 4 つの同時ディスク停止にも耐えることができます。

データ ストレージおよび処理システムでの冗長コードの使用には、データ リカバリの微妙な違い、クエリ実行時間に対するリカバリの影響、データ記録の機能など、さらに多くの機能があります。これらの機能とその他の機能については、個別に説明するつもりです。トピックに興味があれば、実際の冗長コードの使用について説明します。

6. リンク

1. リードソロモンコードとガロア体に関する一連の記事: https://habr.com/ru/company/yadro/blog/336286/
   https://habr.com/ru/company/yadro/blog/341506/
   彼らは親しみやすい言語で数学をより深く考察します。
2. LRC に関する Microsoft の記事: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/LRC12-cheng20webpage.pdf
   セクション 2 では理論を簡単に説明し、次に実際の LRC の経験について説明します。
3. 偶数-奇数スキーム: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
4. STARスキーム: https://www.usenix.org/legacy/event/fast05/tech/full_papers/huang/huang.pdf
5. ピラミッドコード: https://www.microsoft.com/en-us/research/publication/pyramid-codes-flexible-schemes-to-trade-space-for-access-efficiency-in-reliable-data-storage-systems/
6. MDS の冗長コード: https://habr.com/ru/company/yandex/blog/311806
7. YT の冗長コード: https://habr.com/ru/company/yandex/blog/311104/
8. YDB の冗長コード: https://www.youtube.com/watch?v=dCpfGJ35kK8

出所： habr.com