高速データ復旧。 コードを再生成するためのバタフライスキーム

データ回復に関する前の記事で説明したコードの場合、回復操作中に必要なディスクの数を最小限に抑えるタスクが策定されました。 [2]では、データストレージの問題へのネットワークコーディングの適用が議論されました。これは、近年、研究者の注目を集めています。 この記事では、データ回復に必要なディスク数の最適化については考慮せず、これから生じるネットワークトラフィックの最小化について検討します。



ストレージシステムがn個のノードで構成されているとします。 フィールドGF（q）のB文字で構成されるファイルを考えます。これは、 GF（q）上のnα文字でエンコードされ、ノード間で分散されるため、各ノードはα文字を格納します。 コードは、 k個のノードからの情報からデータを完全に復元できるように構築されています。 さらに、1つのノードからデータを回復するには、 d個のノード[1,2]からβ≤αの情報を取得するだけで十分です。図を参照してください。 1.値γ=dβは、修復帯域幅と呼ばれます。



[2]では、データサイズBが上に制限されていることが示されました。

$$

$$B \ le \ sum_ {i = 0} ^ {k-1} min \ {α、（d-i）β\}$$

図1.コードの再生成



（ B、k、d ）の固定値の場合、この境界を満たす多くのペア（α、β）があり、これらのパラメーターに関して、2つの極端なポイントで妥協を得ることができます。 storage "、またはMSR 、Minimum Storage Regeneration）および範囲γ=dβの最小化（このポイントは、"最小範囲での回復 "またはMBR 、Minimum Bandwidth Regeneration）と呼ばれます。 指定された境界を満たすコードは、再生コードと呼ばれます。 対応する境界の例を図に示します。 2 [2]。





図 2.コードを再生成するためのMSR-MBR曲線



近年、MSRとMBRのポイントでのコードの構築、および境界の中間ポイントにあるコードの構築にかなりの注意が払われました[3,6,7]。 [8-15]には、再生成コードのさまざまな構造も記載されています。 これらのコードの主な欠点は、スケーラビリティが低いことです。



さまざまな再生成コードの1つである「butterfly」[4]（このコードは体系的で、ランダム読み取りなどのクエリにとって非常に重要です）を最適化して、1つのディスクを迅速に回復し、この設計のスケーラビリティを向上させました。

バタフライコーディングスキーム

のシーケンスを考えます $$$2 ^ {n-1}$ ストライプ。nはデータディスクの数です。 このストライプセットのデータは、XORコードを使用してエンコードされます。 最初のチェックサム（ h ）は、すべてのデータディスク上の同じLBAを持つブロックで計算されます。 $$$（h_i = \ sum_ja_j、i）$ 。 2つ目は、図3に示されているバタフライ図に従っています。





図 3.バタフライコーディングスキーム



たとえば、チェックサム計算 $$$b_3$ xorブロックとして実装 $$$a_ {3.0}、a_ {2.1}、a_ {0.2}、a_ {4.3}$ 。 さらに、ブロックの色も重要です。これは次のように定義されます。iのバイナリ表現のj番目のビットが（ j-1 ）番目のビットと一致する場合、ブロックは $$$a_ {j、i}$ 緑になります。 ゼロコンポーネントの場合、偶数ブロックはすべて緑色になります。



結果のセットに緑色のブロックが含まれる場合、それらのそれぞれに対して、その右側のブロックをセットに含める必要があります。 つまり、ブロックが $$$a_ {j、i}$ メインセットから-緑、ブロックもセットに含まれています $$$a_ {j-1、i}$ 。 この方法でセットに含まれるブロックの場合、色は問題ではなくなります。 したがって、次の計算式 $$$b_3$ このようになります：

$$

$$b_3 = a_ {3,0} + a_ {2,1} + a_ {0,2} + a_ {0,1} + a_ {4,3}$$

まさにそのようなコーディング方法の選択は、[4]で実証されています。 これにより、同時に故障した2つのコンポーネントの復元が保証されます。



このエンコード方式を使用すると、読み取りデータでコンポーネントを回復するために必要なものは少なくなります。 すなわち、回復のために $$$2 ^ {n-1}$ 故障したストレージシステムコンポーネントのブロックを読み取る必要があります $$$（n + 1）⋅2^ {n-2}$ ブロック-制限では、RAID-6と比較して読み取り回数が2回減少します。



ただし、チェックサムを含むノードに障害が発生した場合、リカバリのためにすべてのデータを読み取る必要があり、この場合、ゲインはありません。 この問題は、RAID-6のシフトと同様のシフト、またはローカル再構成コードを使用したアプローチですでに使用したランダム化の助けを借りて解決できます 。 各セットに $$$2 ^ {n-1}$ ストリップはランダムな順列を行い、チェックサムによるコンポーネント障害のケースを処理するために必要な読み取り値は、すべての障害モードに均等に分散されます。



また、コードの再生成には1つの重大な欠点があることを理解する必要があります。ストリップ内のブロック数の厳密な制限です。 ディスクアレイの場合、これは重要ではありません。エンコードされたブロックのサイズが変わる可能性があるため、つまり、その数が変わる可能性があるためです。 ただし、ディスクの数を制限できるノードのクラスター構成では、スケーリングの問題を解決する必要があります。 考えられる解決策の1つは、ストライプを再生グループに分割することです。 これにより、グループの数だけ冗長性が向上しますが、コーディングセット自体は指数関数的に小さくなります。図を参照してください。 4。





図 4.エンコードされたセットストライプの指数関数的削減



最後に、再生コードを適用する際に考慮すべき最後のことは、故障したディスクからの情報が復元される領域です。 実際、ホットスペアディスクにリカバリする場合、リカバリ速度は書き込みディスクの速度によって制限され、読み取り回数を減らしても大きな利点は得られません。 したがって、ストリップに空のブロックを含める必要があります。

性能試験

パフォーマンステストのために、特定のレイアウトの22台のディスクからRAIDを作成しました。 RAIDデバイスは、特定のアルゴリズムに従ってデータブロックのアドレス指定を変更するデバイスマッパーの変更を使用して作成されました。 データはRAIDアレイに書き込まれ、その後のリカバリのためにチェックサムが計算されました。 故障したディスクが選択されました。 データリカバリは、対応する空のブロックまたはホットスペアディスクで実行されました。 次のスキームを比較しました。

• RAID-6-2つのチェックサムを備えたクラシックRAID-6、ホットスペアディスク上のデータ復旧。
• RAID-6E-ストリップの最後に空のブロックがあるRAID6、対応するストライプの空のブロックのデータ復旧。
• クラシックLRC + E-ローカルグループが連続してチェックサムで終了し、空のブロックに復元するLRCスキーム。
• LRC rand-各LRCストリップを生成するために、その番号が乱数ジェネレーターのカーネルとして使用され、空のブロックでデータが回復されます。
• Classic Regen -3つのグループの再生成コードを持つスキーム。
• Regen rand -3つのグループのコードの再生成とランダム化、空のブロックでのデータリカバリのスキーム。

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

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

パフォーマンスをテストするとき、ストライプブロックサイズは大きな影響を及ぼします。 復元する場合、ディスクからの読み取りはアドレスを増やして（順次）実行されますが、ランダムレイアウトでのクラスター解除により、一部のブロックがスキップされます。 これは、ブロックのサイズが小さい場合、磁気ディスクヘッドの位置決めが非常に頻繁に行われ、これがパフォーマンスに悪影響を与えることを意味します。 データ回復速度の特定の値は、ハードドライブのモデル、メーカー、RPMに依存する可能性があるため、結果を相対的な用語で示しました。 図5は、従来のRAID-6と比較したスキーム（b）-（f）によって得られるパフォーマンスの向上を示しています。





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



ホットスペアディスクにデータを復元する際、ホットスペアを使用するすべての回路のディスクへの書き込み速度によって回復速度が制限されることがわかりました。 ランダム化されたLRCスキームと再生成コードの両方が、最適でないRAID-6と比較して回復速度のかなり高い増加をもたらすことに気付くかもしれません。 再生成コードは明らかに回復率につながるという事実にもかかわらず、エンコードされたセットのブロック数の制限と大きな冗長性：テストされた構成の空のブロックを考慮すると、冗長性は30％以上でした（図6）。





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

おわりに

Butterflyコードの再生成は、HDFS、Ceph [5]で正常にテストされています。



ローカルシステムで再生コードを使用するためのオプションを検討し、それらをスケーリングし、単一のドライブ障害状況を迅速に処理するためにそれらを使用する方法を考え出しました。



このソリューションのパフォーマンスが最高であることが判明したという事実（図5を参照）にもかかわらず、冗長性の要件（図6を参照）には高いコストがかかる可能性があるため、このアルゴリズムはどこにも適していません。 したがって、特定の場合に信頼性のために場所を犠牲にすることが可能かどうかを常に理解する必要があります。



提示されたソリューションは、分散型のクラウドストレージシステムに一般化できます。 そのようなシステムでは、ボトルネックはネットワークを介したデータの送信であり、提示されたアプローチによって最小限に抑えることができるため、利点はさらに明白になります。