5.6. Pyramid イレイジャーコード

Pyramid イレイジャーコードは、データのアクセスとリカバリーを向上させるために、元のイレイジャーコードアルゴリズムに基づいて、非常に改善されたアルゴリズムになりました。これは単に、任意の (n, k) に対して Reed-Solomon のような既存の MDS (Maximum Curve Separable) コードを判別するだけです。ここで、k はデータチャンクの元の数で、n はコーディングプロセス後のデータチャンクの合計数です。Pyramid コードは標準の MDS コードをベースとしているため、エンコーディング/デコードアプローチと同じです。pyramid コーディングされたデータプールには、同じ書き込みオーバーヘッドがあり、通常のイレッジャーコードプールなどの任意の障害などのリカバリーが可能です。pyramid コードの利点は、通常のイレイジャーコードと比べると、オーバーヘッドを大幅に削減することです。

(11、8) イレイジャーコードプールの例を考えて、pyramid コードアプローチをこれに適用します。イレッチャーコード (11, 8) の元号を、(12, 8) の Pyramid コードプールに変換します。イレイジャーコード化されたプールには 8 個のデータチャンク、11 - 8 = 3 の冗長チャンクがあります。Pyramid コードは、8 データチャンクを 2 つのサイズグループ (例: P1 = {a1, a2, a3, a4} および P2 = {a5, a6, a7, a8}. に分割します。イレイジャーコードから冗長なチャンクが 2 つ変更されない (b2 と b3) の 2 つを維持します。これら 2 つのチャンクは、すべての 8 データチャンクに対応するため、グローバルな冗長チャンクと呼ばれます。次に、グループ P1 に対して新たな冗長チャンクが計算されます。これはグループ (またはローカル) の冗長チャンク b1,1 として示されます。この計算は、P2 にあるすべてのデータチャンクを 0 に設定する場合を除き、元のイレイジャーコードで b1 の計算用として行われます。同様に、グループ冗長チャンク b1,2 は P2 用に計算されます。グループ冗長チャンクは、対応するグループのデータチャンクにのみ影響し、他のグループには影響を及ぼしません。グループ冗長チャンクは、イレイジャーコード内の元の冗長チャンクのプロジェクト地点として解釈できます。つまり、b1,1 + b1,2 = b1 です。したがって、この方法では、1 つのデータチャンクが失敗した場合は、通常のイレイジャーコードプール用に 8 ではなく、4 の読み取りオーバーヘッドを使用して復旧できます。たとえば、P1 の a3 に障害が発生し、a1 がスクラビングの代表的な OSD である場合は P2 からの読み取りではなく、a1、a2、a4、および b1,1 を使用して a3 を回復できます。すべてのチャンクを読み取ることは、同じグループに複数のチャンクが欠落している場合にのみ必要になります。

この Pyramid コードには、元のイレイジャーコードと同じ書き込みのオーバーヘッドがあります。データチャンクが更新されるたびに、Pyramid コードには 3 つの冗長チャンク (b2、b3、そして b1,1 または b1,2 のいずれか) を更新する必要がありますが、イレイジャーコードが 3 つの冗長なチャンク (b1、b2、および b3) を更新します。また、通常のイレイジャーコードと同じ 3 つの元号を回復することもできます。上述の利点は、1 つの冗長チャンクを使用するコストがかかるため、オーバーヘッドが少なくなります。したがって、Pyramid コードは、アクセス効率に対するストレージ領域をトレードオフします。

以下の図は、構築された pyramid コードを示しています。