高速データ復旧。 LRCはどのように役立ちますか？

現代の世界では、データ量の指数関数的な増加が観察されています。 ストレージベンダーは、膨大な量の情報に関連する一連のタスクに直面しています。 その中には、ユーザーデータの損失からの保護と、サーバーまたはディスクに障害が発生した場合の最速のデータ回復があります。



この記事では、迅速な再構築のタスクを検討します。 データ保護の最適なソリューションはレプリケーションと思われますが、このシナリオのオーバーヘッドは100％以上です。 このようなボリュームを常に割り当てることはできません。 したがって、冗長性と回復率の間で妥協点を探さなければなりません。



より少ないオーバーヘッドを提供するよく知られたアプローチは、 ローカルパリティ（LRC） コードと再生成コードです。 これらのソリューションは、分散システムとローカルディスクアレイの両方で機能します。



この記事では、ディスクアレイにLRCコードを使用する機能を検討し、故障したディスクのデータリカバリを高速化するシナリオを提案します。



LRCと再生成コードの両方で同時にパフォーマンスをテストしましたが、次の記事のいずれかで後者について詳しく説明します。

データの可用性

RAIDテクノロジー （Redundant Array of Independent Disks）は、データストレージシステムで使用され、高速データアクセスとフォールトトレランスを提供します。 ノイズに強いコーディングを使用して、ディスクへのデータの読み書きプロセスとフォールトトレランスのプロセスを並列化することにより、高速が実現されます。



時間の経過とともに、ストレージシステムのボリュームと信頼性に対する要件は増加しています。 これにより、新しいRAIDレベル（RAID-1 ... 6、RAID-50、RAID-60、RAID-5Eなど）が出現し、MDS（最大距離分離可能-最大のコードなど）の異なるクラスのノイズ耐性コードが使用されました。コード距離）および非MDS。



特定のエンコード方法を使用したデータの配置が、障害が発生したディスクの回復速度にどのように影響し、その結果、ディスクアレイデータの可用性に影響するかを検討します。



可用性とは、要求に応じてシステムが利用できる可能性です。 特に、コーディングにより高可用性が実現されます。 システムのディスク領域の一部は、ユーザーデータ用ではなく、チェックサムの保存用に割り当てられます。 システムドライブに障害が発生した場合、これらのチェックサムを使用して失われたデータを回復できるため、データの可用性が確保されます。 原則として、可用性は次の式で計算されます。

$$

$$可用性= \ frac {MTTF} {MTTF + MTTR}$$

MTTF-平均故障時間 （MTBF）、 MTTR-平均修理時間 （平均復旧時間）。 特定のシステムコンポーネント（この場合はディスクまたはクラスターノード）を復​​元するのに必要な時間が短いほど、データの可用性は高くなります。



コンポーネントの回復速度は以下に依存します。

• 復元されたデータの記録速度;
• 読み取り速度;
• 復元に必要な読み取りデータ量。
• デコードアルゴリズムのパフォーマンス。

データストレージを整理し、チェックサムを計算するためのオプションには、それぞれ長所と短所があります。 たとえば、リードソロモンコード（RSコード）は高いフォールトトレランスを提供します。 RSコードは、最大コード距離（MDS）のコードであり、チェックサムを保存するための余分なスペースに関して最適であるように見えます。 RSコードの欠点は、コーディングの点で非常に複雑であり、障害を回復するために多くの読み取り値を必要とすることです。



他の可能な解決策の中には、修正された回転RSコードまたはWEAVERコード（XORコードの一種）があります。 後者はコーディングの点ではかなり単純であり、障害から回復するための読み取り値はほとんど必要ありません。 ただし、このエンコード方式では、チェックサムにMDSコードよりもはるかに多くのストレージを割り当てる必要があります。



上記の問題に対する適切な解決策は、LRC（Local Reconstruction Codes）の出現です。 Windows AzureストレージのErasure Codingは、これらのコードの詳細な説明を提供します。これは、本質的に、RSコードから非MDSへの変換です。 同じ論文は、LRCを他のコードと比較し、LRCの利点を示しています。 この記事では、LRCストライプブロックの場所が回復速度にどのように影響するかを見ていきます。

RAIDでLRCを使用する際の問題

次に、LRCのイデオロギーについて簡単に説明し、新たな問題と可能な解決策を検討します。 1つのストリップを形成するディスクに格納されたブロックのシーケンスを検討してください。 将来的には、特に指定がない限り、ストライプは異なるディスクに配置され、共通のチェックサムによって結合されたブロックのセットとして理解されます。



このストリップのデータが、たとえば2つのチェックサムを持つRAID-6で行われるようにRSコードでエンコードされている場合、コード情報にはストリップの2つのブロックが含まれます。 図 上の1は、2ブロックを含む19ブロックのストリップです。 $$$S_1$ そして $$$S_2$ -チェックサム。 たとえば、ブロック番号2を含むディスクに障害が発生した場合、このブロックを復元するには、各ストライプから17ブロックを読み取る必要があります（16は失敗せず、1つのチェックサム）。



この場合、ローカル再構成コードでは、ストライプをいくつかのローカルグループに分割する必要があり、各グループに対してローカルチェックサムが計算されます。 すべてのデータブロックについて、グローバルチェックサムも計算されます。 図 図1に示すように、ブロックがサイズ5の3つのローカルグループに分割される例を考えます。各ブロックについて、ローカルチェックサムが計算されます $$$S_1、S_2、S_3$ 、および1つのグローバルチェックサムG





図 1. RAID6およびLRCストライプ表現の例



ローカルチェックサムは、依存するXORデータブロックとして計算されます。 複数のグローバルチェックサムがあり、RSコードのチェックサムとして計算されます。 この場合、ブロック番号2を復元するには、6ブロックを読み取る必要があります。 これは前のケースに比べて3倍少なくなりますが、チェックサムを保存するためにより多くのストレージが必要です。 同じグループの2つのディスクに障害が発生した場合、3つのローカルチェックサムをすべて追加（XOR）すると、LRCは簡単にクラシックRSに変換されることに注意してください。



LRCを使用すると、1つのドライブを復元するために必要な読み取り回数の問題を完全に解決できます。 それでも、すべてのストリップが同じ方法でディスクまたはクラスターノードに配置され、それらのブロックのシーケンスが変更されない場合、ローカルグループの任意のブロックのデータを変更すると、このグループのローカルチェックサムとストライプのグローバルチェックサムが常に再カウントされることがわかります。 したがって、チェックサムのあるコンポーネントは高負荷と摩耗の影響を受けます。 したがって、このようなアレイのパフォーマンスは低下します。 従来、RAIDにおけるこのような問題は、ディスク上のストリップの周期的なシフトによって解決されていました。図を参照してください。 2。



そのため、データリカバリ中、ストレージシステムの1つのコンポーネントへの書き込み速度によってリカバリ速度が制限されることはありません。RAID5EおよびRAID-6Eで行われるように、いわゆるストライプ（E）を各ストライプに追加できます。 したがって、各ストリップで復元されたデータは、その空のブロックに書き込まれるため、別のディスクに書き込まれます。 ストリップ内の空のブロックの存在はオプションです。 今後の議論では、完全を期すために、このようなブロックを持つストライプを検討します。





図 2.シフトのあるストライプブロックの位置



したがって、循環シフトと空のブロックの存在を使用する場合、ディスク上のストリップの配置は、図3のような形式になります。 2。



LRCを使用すると、ストライプを配置できるディスクの数にもわずかな制限が課せられます。 したがって、ローカルグループの数が等しい場合 $$$k$ 、1つのローカルグループのサイズは $$$l$ 、グローバルチェックサムの数は $$$g$ 空のブロックがある場合、ストライプの合計サイズは等しくなります $$$kl + g + 1$ 。 ディスクの数がストライプの長さと異なる場合、2つのオプションが可能です。

1. さまざまなサイズのローカルグループを作成します。 この場合、ストライプデータが変更されると、一部のローカルチェックサムがより頻繁に更新され、記録が遅くなる可能性があります。
   
   
   
   
2. すべてのディスクに各ストライプを配置しないでください。1つのストライプが終了する場所で、すぐに2番目のストライプを開始してください。図を参照してください。 3.このアプローチにより、すべてのローカルグループを同じサイズにすることができ、ストリップの場所に応じて循環シフトが自動的に導入されます。 ストライプの長さがディスクの数と一致する場合、RAID-6の場合と同様に、各ストライプに対して循環シフトが実行されます。

図 3. 1つの故障したドライブを回復するために必要なブロック



図 3単一ディスク障害の場合が考慮されます- $$$D_7$ 。 ピンクは、復元するために読み取る必要があるすべてのブロックを示します。





図 4.故障したディスクを復元するために各ディスクから読み取られたブロック数



合計105ブロックの読み取りが必要でした。 LRCの代わりにRAID-6が使用された場合、340の読み取りブロックが必要になります。 このブロックの配置が最適かどうかを理解するために、各ディスクから読み取られたブロックの数を計算します。図を参照してください。 4。



障害が発生したディスクの近くにあるディスクは、他のディスクに比べてはるかに負荷が大きいことに気付くかもしれません。 したがって、障害が発生した場合のデータ回復中に、ボトルネックになるのはこれらの最も負荷の高いディスクです。 ただし、LRCストリップブロックの場所は、最初のローカルグループブロックが最初に移動し、次に2番目、3番目の順に移動する場合、厳密な制限ではありません。 したがって、私たちのタスクは、障害が発生した場合にすべてのディスクの負荷が最小かつ均一になるブロックの場所を特定することです。

大容量ディスク用のランダム化アルゴリズム

RAID-6の同様の問題を解決するさまざまな方法は別として、LRCの場合に考えられるシナリオを検討してください。

1. LRCストリップごとに、古典的なブロックの配置を採用します（図1と同様）。 選択したストライプの番号を、乱数ジェネレーターの初期値（シード）として使用します。 すべてのストリップに対して、同じ乱数ジェネレーターが使用されますが、シードが異なります。
2. 開始された乱数ジェネレータとブロックの初期配置を使用して、現在のストリップのブロックのランダム配置を取得します。 このケースでは、Fisher – Yatesシャッフルアルゴリズムが適用されました。
3. ストリップごとにこの手順を実行します。

このアプローチでは、各ストライプにランダムな構造があり、その構造はその数によって一意に決まります。 この問題では乱数ジェネレーターの暗号強度は必要ないため、かなり単純で迅速なバージョンを使用できます。 したがって、障害が発生した場合の各ディスクの平均負荷の数学的予想を推定することができます。



次の表記法を紹介します。 $$$V$ -アレイ内の各ディスクのボリューム、 $$$s$ -1つのストライプブロックのサイズ、 $$$N$ -1つのストライプの長さ、 $$$n$ -ディスクの数、 $$$l$ -ローカルグループのサイズ。 $$$k$ -ローカルグループの数、 $$$g$ -グローバルチェックサムの数。 次に、各ディスクの平均負荷の数学的期待値は次のように計算されます。

$$

$$M（D_i）= \ frac {Vk（l-1）（l + g）} {s（n-1）}$$

このような評価を行い、ディスクからブロックを読み取る速度を知ることで、1つの障害が発生したディスクの復旧時間のおおよその見積もりを行うことができます。

性能試験

パフォーマンステストのために、さまざまなレイアウトの22台のディスクからRAIDを作成しました。 RAIDデバイスは、特定のアルゴリズムに従ってデータブロックのアドレス指定を変更するデバイスマッパーの変更を使用して作成されました。



データはRAIDに書き込まれ、その後の回復のためにチェックサムが計算されました。 故障したディスクが選択されました。 データリカバリは、対応する空のブロックまたはホットスペアディスクで実行されました。



次のスキームを比較しました。

• RAID-6-2つのチェックサムを持つクラシックRAID-6。 ホットスペアディスク上のデータリカバリ。
• RAID-6E-ストリップの端に空のブロックがあるRAID6。 対応するストライプの空のブロックのデータ復旧。
• クラシックLRC + E-ローカルグループが順番に進み、チェックサムで終わるLRCスキーム（図3を参照）。 空のブロックへの回復。
• LRC rand-各LRCストリップを生成するために、その番号が乱数ジェネレーターのカーネルとして使用され、空のブロックでデータが回復されます。

テストでは、次の特性を持つ22個のディスクが使用されました。

• メーカー：IBM
• 部品番号：ST973452SS-IBM
• 容量：73GB
• インターフェース：SAS
• 速度：15K RPM
• サイズフォームファクター：2.5IN

パフォーマンスをテストする場合、ストライプブロックのサイズが大きな役割を果たします。 データ回復中のディスクからの読み取りは、アドレスを増やして（連続して）実行されますが、ランダムレイアウトでのクラスター解除により、一部のブロックがスキップされます。 これは、小さなブロックで作業する場合、磁気ディスクヘッドの位置決めが非常に頻繁に実行され、パフォーマンスに悪影響を及ぼすことを意味します。



データ回復速度の特定の値は、ハードドライブのモデル、メーカー、RPMなどに依存する可能性があるため、相対的な用語で結果を示しました。 図5は、従来のRAID-6と比較した、考慮された回路（空のブロックを持つRAID6、クラシックLRC、LRCランド）のパフォーマンスの向上を示しています。





図 5.さまざまな配置アルゴリズムの相対的なパフォーマンス



ホットスペアディスクにデータを復旧する場合、復旧率は、ホットスペアを使用するすべてのスキームのディスクへの書き込み速度によって制限されていました。 ランダム化されたLRCスキームは、最適でないスキームおよびRAID-6と比較して、回復速度がかなり高くなることに気付くかもしれません。





図 6.さまざまなアルゴリズムの冗長性

おわりに

ブロックの場所に可能なオプションを提供し、さまざまなスキームをテストしたところ、回復速度が顕著に向上しました。 LRCコードの高いスケーラビリティにより、このアプローチは、ローカルグループの数を増やすことで、多数のディスクからアレイを構築するときにも使用できます。 グローバルチェックサムの数を増やすことで、信頼性を向上させることができます。



LRCの堅牢なコーディングにより、レプリケーションよりもストレージの冗長性を大幅に削減できます。 リードソロモンコード以外のコーディングスキームは、LRCのコンテキストで実際に検討されることがほとんどです。 Xorbas — HDFSでのLRCの実装—は、RSエンコーディングよりも冗長性を14％向上させる必要がありました。 回復率は25〜45％増加しました。 ネットワークを介した読み取りと転送の回数も大幅に削減されました。 最適なLRCのさらなる研究については、「ローカルで最適に回復可能な最適なコードのファミリー」（Itzhak Tamo、Alexander Barg）を参照することをお勧めします。



使用されるソース：

• Hafner、JL、WEAVERコード：ストレージシステム向けの高度なフォールトトレラントな消去コード、FAST-2005：ファイルおよびストレージテクノロジーに関する第4回Usenix会議
• カーン、O。、バーンズ、R。、プランク、JS、ピアース、W。、ファン、C。およびストレージ技術
• Huang、C.、Simitci、H.、Xu、Y.、Ogus、A.、Calder、B.、Gopalan、P.、Li、J.、Yekhanin、S.、Erasure Coding in Windows Azure Storage、USENIX Annual Technicalコンファレンス
• M. Sathiamoorthy、M。Asteris、D。Papailiopoulos、AG Dimakis、R。Vadali、S。Chen、およびD. Borthakur。 XORing Elephants：Big Dataの新しい消去コード。 VLDB基金のプロシーディングス、ボリューム6、325〜336ページ。 VLDB寄付、2013年。
• イザク・タモ、アレクサンダー・バーグ。 局所的に回復可能な最適なコードのファミリー。 arXivプレプリントarXiv：1311.3284、2013年。