SDSで冗長コードを使用すると、Yandexはデータを安価で信頼性の高い方法で保存できます。

Yandexは、他の大規模なインターネット企業と同様に、大量のデータを保存します。 さまざまなサービス、マイニングサイトからのこのユーザーデータ、天気を計算するための中間データ、およびデータベースのバックアップコピー。 ストレージコスト（$ / GB）は、システムの重要な指標の1つです。 この記事では、ストレージのコストを大幅に削減できる方法の1つについて説明します。

ご存知のとおり、2015年にはドルが大幅に増加しました。 より正確には、2014年の終わりに成長し始めましたが、2015年には既に新しい鉄を注文しました。 Yandexはルーブルでお金を稼いでいるので、料金とともに鉄のコストも増加しています。 これにより、現在のクラスターにより多くのデータを配置できるようにする方法について再度考えました。 もちろん、これは定期的に行いますが、今回は特にモチベーションが高くなりました。

クラスター内の各サーバーは、プロセッサ、RAM、ハードドライブ、およびネットワークのリソースを提供します。 ここでのネットワークは、単なるネットワークカードよりも複雑な概念です。 これは、データセンター内のインフラストラクチャ全体であり、異なるデータセンターとトラフィック交換ポイント間の接続です。 クラスターでは、信頼性を確保するためにレプリケーションが使用され、クラスターの合計サイズは、ハードドライブの合計容量によってのみ決定されました。 残りのリソースをスペースの増加と交換する方法を見つける必要がありました。 ところで、投稿後も個人的に議論したい質問がある場合は、 会議に参加してください。

RAMは交換が困難です。 ディスクシェルフを使用しており、ディスク容量に対するRAMの量の差は3桁を超えています。 単一のマシン内でのアクセスを高速化するために使用できますが、これは別の記事の話です。

プロセッサは、明らかにアーカイブを介して交換します。 ただし、いくつかの落とし穴に注意する必要があります。 まず、圧縮率はアーカイバと保存されたデータの組み合わせに大きく依存します。つまり、データの代表的なサンプルを取得して、どれだけ保存するかを見積もる必要があります。 第二に、アーカイバはほとんどどこからでもデータを読み取る機能を提供する必要があります。そうしないと、HTTPのRangeヘッダーを忘れる必要があります（これにより、大きなファイルをダウンロードできなくなったあまり良くないインターネットでクライアントを怒らせます）。 第三に、圧縮と解凍の速度、および関連するCPU消費が重要です。 データを非常に効率的に圧縮するアーカイバを使用できますが、クラスター内のプロセッサの数では、現在の書き込み速度を確保するには不十分です。 展開すると、リクエストの遅延が発生します。 少し前、FacebookはZstdアーカイバを公式にリリースしました。試してみることをお勧めします。 非常に高速で、データを適切に圧縮します。

すべてのリソースの中で、ネットワークはそのままであり、それによって私たちは創造性の大きな範囲を持っています。 ネットワークをストレージ容量に交換する方法については、さらに説明します。

Yandexには、ストレージシステムに関するかなり厳しい要件があります。 1つのデータセンター全体が失われた場合でも、運用を継続する必要があります。 この条件により、適用できるテクノロジーにかなり強い制限が課せられますが、その代わりに、データセンター自体の信頼性よりも高い信頼性が得られます。 ストレージシステムの開発者である私たちにとって、これは、DCが抜け落ちたときの冗長係数が1より大きくなければならないことを意味します。

一般に、アクセシビリティゾーンについて話す方が正しいです。 私たちの場合、これはデータセンター全体ですが、別のマシン、ラック、ホール、または大陸である場合もあります。 つまり、4つのアクセシビリティゾーンがあり、それらの間でデータを均等に分散している場合、冗長性の程度は各ゾーンで1（3）、0。（3）より小さくすることはできません。 したがって、アベイラビリティゾーンはN個あり、それらのデータを何らかの方法で分解する必要があります。

レプリカ

明らかに、最も簡単な方法は完全なレプリカを作成することです。 ほとんどの場合、2つまたは3つのレプリカが作成され、長年にわたってこのパターンに従って生きてきました。 欠点は明らかです。1ギガバイトのデータを保存するには、2ギガバイト（または3ギガバイト）のハードディスク領域を使用する必要があります。 しかし、利点があります。各レプリカには本格的なファイルが含まれており、読みやすく、同時に完全に1台のマシン上、1台のハードディスク上にあります。 ディスクが失われた場合のデータの回復も非常に簡単です-ネットワーク経由で通常のコピーを使用します。

ユーザーコンテンツ、Yandex.Musicデータ、さまざまなアバター、およびその他の類似データのストレージについては、MDSサービス（メディアストレージ）を担当しています。 Elliptics、Eblob、およびHTTPプロキシに基づいています。 Ellipticsはネットワークルーティングを提供し、Eblobはデータをディスクに保存するために必要です。プロキシはユーザートラフィックを終了するために必要です。 このクラスターはすべて、Mastermindと呼ばれるシステムによって制御されます。 ストレージでは、以前にEllipticsで試した大きなDHTリングの概念から離れ、スペース全体を916ギガバイトの小さな破片に分割しました。 私たちはそれらを「ドロップ」と呼びます（英語から。カップル）。 番号916は、複数のドロップレプリカを1台のハードドライブに配置する必要があるために選択されました（ディスクメーカーは、マーケティングを好み、ボリュームを10進テラバイト単位で検討します）。 Mastermindは、1つのドロップのレプリカが常に異なるDCに配置されることを保証し、データ回復手順、最適化を開始し、一般にシステム管理者の作業を自動化します。

一貫性を回復するために、すべてのキーを実行し、存在しないレプリカに不足しているキーを追加する特別な手順があります。 この手順はそれほど高速ではありませんが、レプリカ間のライブキーの数に不一致がある場合にのみ開始します。 サイドプラス-ハードドライブに負荷がかかります。たとえデータが冷たくて、ユーザーが来なくてもです。 その結果、データを回復しようとしている時点ではなく、別のレプリカがすでに停止していることを発見したため、ディスクは事前に停止し始めます。 穏やかに変更します。その後、回復が自動的に開始され、ユーザーデータは安全で健全なままです。

冗長コード

類推すると、同様のデータ複製方法はRAID 1であり、シンプルで信頼性が高く、スペース消費の面であまり効率的ではありません。 しかし、RAID 5またはRAID 6に似たものを作成する必要があります。繰り返しますが、単純なものから複雑なものへと進みます。3つのアクセスゾーンを取得します。 3番目は、ブロック間のバイトXORの結果です。 エラーを検出するために、各ブロックについて、ブロックサイズと比較して無視できるチェックサムを考慮します。 データ回復は基本です。a^ b = cの場合、b = a ^ cです。 このアプローチでの冗長率は1.5です。 ブロックが失われた場合は、さらに別のアクセシビリティゾーンから他の2つを読み取る必要があります。 1つのディスクを失うことなく回復できます。これは、3つのレプリカの場合よりもはるかに悪く、2つのレプリカと同等です。 これは、文字列「Hello、habrahabr」のXOR結果の計算方法です（以下の数字は、バイトの10進表現です）。

ここでストライプの概念を紹介する価値があります。 ストリップはN個の連続したブロックであり、最初のストリップの先頭はデータストリームの先頭と一致します。Nは選択したコーディングスキームに依存し、RAID 1の場合はN = 2です。 冗長コードを効果的に使用するには、すべてのファイルを1つの連続したバイトストリームに結合し、すでにストリップに分割する必要があります。 次に、各ファイルが開始するスタイルとサイズ、およびそのサイズでマークアップを保存する必要があります。 データストリームの長さがストライプのサイズの倍数でない場合、残りの部分はゼロで埋める必要があります。 概略的には、これは次のように表すことができます。

ストライプサイズを選択するときは、次の考慮事項を使用できます。

• ブロックサイズが大きいほど、1つのブロックに収まるファイルが多くなり、同時に2つのアクセスゾーンからの読み取り値が少なくなります。
• ブロックサイズが大きいほど、ブロックが一時的に使用できなくなったり損失したりする場合に、ネットワーク上でより多くのデータをドラッグする必要があります。

したがって、これらのイベントの確率を考慮する必要があります。 最適なサイズは、ファイルサイズの中央値2倍であることが判明しました。 さらに、ファイルの配置を変更して、ブロックの境界が1つのブロックに収まらない大きなファイルに収まるようにすることをお勧めします。 これにより、ネットワークの負荷も軽減されます。 また、コードを簡素化するために、パリティブロックストレージ機能がアクセシビリティゾーンの1つに割り当てられています。

リードソロモンコード

しかし、より高い信頼性が必要な場合はどうでしょうか？ そうです-より強力な冗長コードを使用してください。 現在、最も一般的なコードの1つはリードソロモンコードです。 DVDの書き込み、デジタルTV（DVB-T）、QRコード、およびRAID 6で使用されます。ここでは、ガロア体の数学については説明しません。エンジニアリングアプローチを待っているだけです。 すべての計算に、jerasureライブラリを使用します。これは困難な運命を持っていますが、非常に迅速に機能し、必要なすべての機能を備えています。

注目に値する最初のこと：効果的な結果を得るには、フィールド2 ^ 8、2 ^ 16、2 ^ 32、つまり機械語で作業する必要があります。 さらに簡単にするために、2 ^ 8フィールドを使用してバイトを操作します。 この例をより具体的にするために、2つのパリティブロックを使用して、1.5の複製係数を達成してみましょう。 これを行うには、データをそれぞれ4ブロックのストリップに分割し、2つのパリティブロックを生成する必要があります。 各データブロックから最初のバイトを取得する場合、次元4のベクトルと同様に、パリティブロックの次元2のベクトルを構成できます。 次元4のベクトルから次元2のベクトルを取得するには、2x4コーディングマトリックスを乗算する必要があり、エンジニアリングの観点から見ると、ガロア体での作業の規則に従って乗算する必要があります。 必要なマトリックスは、Vandermondeマトリックスと呼ばれます。 選択されたフィールドの場合、このような行列は、通常の代数に線形結合がないことに似た特性を保証します。 データを復元する際にも、重要な役割を果たします。

「Hello、habrahabr」という1つのデータストライプを取得しましょう。 これは、それぞれ4バイトの4つのブロックに非常にうまく分割され、1つのバイトが1つのエンコードワードに対応します。

したがって、次の図が取得されます。

パリティブロックは、単語ごとに（この場合はバイトごとに）同様の方法で計算します。

画像をわずかに変更し、エンコード行列の上に単位行列を追加すると、初期データが出力ベクトルに表示されます。

ブロック番号2とブロック番号4を失ったとします。対応する行を行列と右ベクトルから消します：

次に、結果の正方行列を反転し、等式の両側に乗算します。

ソースデータを取得するには、エンコードの場合と同じ乗算操作を実行するだけでよいことがわかります。 1つのブロックのみが失われた場合、コーディングマトリックスから正方形にするために、パリティブロックに対応する行の1つを削除する必要があります。 最初の行は単位で構成され、特別な魔法を持っていることに注意してください。計算はすべての要素間のXORの計算と同等であり、他の行を数えるよりも数倍高速です。 したがって、この行をスローする価値はありません。

ローカル復旧コード

それは非常にシンプルで、はっきりしていると思います。 しかし、他に改善できることはありますか？ はい、Microsoft Azureの同僚は彼らの出版物で私たちに語っています。 このメソッドは、ローカル再構築コード（LRC）と呼ばれます。 すべてのデータブロックを複数のグループ（たとえば、2つのグループ）に分割する場合、グループ内でエラー修正をローカライズするようにパリティブロックをエンコードできます。 以前のレプリケーション係数1.5の場合、スキームは次のようになります。ストライプを4ブロックの2つのグループに分割します。各グループには、独自のローカルパリティブロックと2つのグローバルパリティブロックがあります。 このスキームにより、3つのエラー、および4つのエラーがある状況の約96％を修正できます。 残りの4％には、4つのデータブロックとローカルパリティブロックを含む4つのエラーすべてが1つのグループに該当する場合が含まれます。

もう一度「単純から複雑へ」のアプローチを適用して、エンコードマトリックス内の単位の行を次のように2つに分割しました。

1	1	1	1	0	0	0	0
0	0	0	0	1	1	1	1
1	55	39	73	84	181	225	217
1	172	70	235	143	34	200	101

残念ながら、今回のアプローチは失敗しました。 最初はすべて問題ありませんでしたが、理論的に回復可能なエラーのすべてのバリアントを組み合わせてソートするテストを作成したとき、マトリックスではそれらの一部を回復できないことがわかりました。 出版物の研究に飛び込む必要がありました。 答えは、セクション2.2.1のMicrosoftの同じ出版物で見つかりました。 マトリックスはもう少し巧妙に構成する必要があります-幸いなことに、消去によってこれを簡単に行うことができます。

for row in range(4): for column in range(8): k = 8 index = row * k + column is_first_half = column < k / 2 if row == 0: matrix[index] = 1 if is_first_half else 0 elif row == 1: matrix[index] = 0 if is_first_half else 1 elif row == 2: shift = 1 if is_first_half else 2 ** (k / 2) relative_column = column if is_first_half else (column - k / 2) matrix[index] = shift * (1 + relative_column) else: prev = array[index - k] matrix[index] = libjerasure.galois_single_multiply(prev, prev, 8)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このようなマトリックスを使用すると、テストは正常に合格します。

1	1	1	1	0	0	0	0
0	0	0	0	1	1	1	1
1	2	3	4	16	32	48	64
1	4	5	16	29日	116	105	205

そのため、グループを形成しました。 ただし、アベイラビリティゾーン全体が低下した場合でも、システムが動作し続ける必要があることを忘れてはなりません。 LRCを使用すると、次のようにゾーンにブロックを配置することでこれを実現できます。

ここで、どの行を消しても、各ローカリティグループには3つ以下のエラーしか存在しないことがわかります。これは、データを読み取ることができることを意味します。 1つのブロックが存在する1つのドライブのみが故障した場合、他のアベイラビリティゾーンから追加ブロックを1つだけ要求することにより、データを読み取ることができます。 ブロックサイズに関する考慮事項は、XORを使用したスキームとほぼ同じです。ただし、1つの例外があります。読み取りがアクセスゾーン間でのみ高すぎると仮定した場合、ブロックサイズは4分の1になります。 1つのゾーン内。

練習する

これで、冗長コードの計算のプログラミングは非常に簡単なタスクであり、この知識をプロジェクトに適用できることがわかりました。 この記事で検討したオプション：

• レプリカ-複数の冗長性を提供し、簡単に実装され（多くの場合-デフォルトオプション）、ブロックレベルとファイルレベルの両方で機能します。
• XOR、冗長性-1.5は、ブロックレベルとファイルレベルの両方で実装でき、3つの可用性ゾーンが必要です。
• リードソロモンコード-冗長性の程度を柔軟に選択できますが、1つのデータブロックを復元するには、1つのストライプに含まれるブロックをすべて読み取る必要があります。 ブロックレベルでのみ有効です。
• LRC-Reed-Solomonコードに似ていますが、単一の障害で、より少ないデータの読み取りを許可しますが、少数のケースでデータ回復を提供します。

MDSでは、LRC-8-2-2スキーム（8データブロック、2ローカルパリティブロック、2グローバルパリティブロック）を適用しました。 その結果、2つのレプリカがあり、2つのハードディスクに存在する1つのドロップが、12台のハードディスクに配置され始めました。 これにより読み取り手順が非常に複雑になり、ハードドライブを失った後の回復も困難になりました。 しかし、25％のディスクスペースの節約が得られ、すべての短所を上回りました。 ネットワークの負荷を軽減するために、レプリカを使用して通常のドロップでデータが記録されます。 それらが完全に一杯になり、読み取り値が小さくなるとき、つまりデータが「クールダウン」するときにのみ変換します。

10月15日にモスクワのオフィスで開催されたイベントで、このスキームの実施中に発生した問題について説明します。 さあ、それは面白いでしょう！