分散システムのための Erasure Coding 技術
(transactional.blog)- Erasure Coding は、データを断片とパリティに分け、完全複製より少ない保存容量で障害に耐えられるようにする、保存効率と耐障害性の折衷技法である
- 基本モデルは k+m=n で、k は復元に必要なデータ断片数、m はパリティ断片数であり許容可能な障害数、n は全断片数である
- オブジェクト・ブロブストレージでは 3 重の完全複製の代わりに 10+5 のような構成を使い、より多くのサーバーに小さな断片を配置して保存量を減らせる
- Quorum システムは単純な多数決だけでは保存削減に限界があり、HRaft のように利用可能なレプリカ数に応じて 3+2, 2+2, 1+2 に切り替えると、再エンコードや容量プロビジョニングの負担が生じる
- 実際の導入では、応答断片の組み合わせによる デコードコストの変動 と、Jerasure・ISA-L・liberasurecode のメタデータやアラインメント要件の違いを検証する必要がある
保存効率と障害許容の基本的なトレードオフ
- N 台のサーバーにファイルを保存する極端な方式は 2 つある
- すべてのサーバーに 完全なファイル複製 を置けば、N-1 台のサーバーが失われてもファイルは失われないが、保存コストは最大になる
- ファイルを N 個の同一サイズの断片に分けて各サーバーに 1 つずつ保存すれば、保存効率は最も良いが、読み取り時には N 個すべての断片が必要になる
- Erasure Coding は、この 2 つの極端の間で保存効率と障害許容を調整する
- 「ファイルを N 個の断片に分割し、M 個の断片が失われても復元できるようにしたい」という目標に合うコードを構成できる
- この目標を満たすのに必要な最小サイズの断片を提供する
- 最も単純な直感的な例は、3 台のサーバーのうち任意の 2 台だけを読んで完全なファイルを得るケースである
- ファイルを 2 つの断片 A、B に分ける
- 3 つ目の断片 C を A ⊕ B で作る
- A と B を読めばそのまま結合でき、A と C または B と C を読めば XOR で欠けた断片を復元できる
- すべての Erasure Code は、データ断片と パリティ断片 を分けることでこのパターンを一般化している
k+m=n モデルと保存オーバーヘッド
- Erasure Code の設定は k + m = n で表される
- k: データを分割する断片数であり、値を復元するには少なくとも k 個の断片を読む必要がある
- m: 生成するパリティ断片数であり、許容される読み取り失敗数または障害許容数である
- n: 生成される断片の総数である
- 生成される断片 1 つのサイズは元のファイルの 1/k である
- Erasure Code は通常
k+mタプルと呼ばれる- 文献によって変数名は一貫していない
x+yは x 個のデータ断片と y 個のパリティ断片を意味する
- ストレージ事業者にとって魅力的なのは、低い保存オーバーヘッドで障害許容を得られるためである
- Backblaze B2 は 17+3 を使い、1.18 倍の保存容量で 3 件の障害に耐える
- OVH Cloud は 8+4 コードで 1.5 倍の保存容量で 4 件の障害に耐える
- Scaleway は 6+3 コードで 1.5 倍の保存容量で 3 件の障害に耐える
- 主なコストは、保存容量の削減と読み取り要求数の増加の交換である
- 1 台のディスクからファイルサイズ分を読む代わりに、k+m 台のディスク に要求を送る
- 頻繁にはアクセスされないデータ向けのストレージシステムは、追加の IOPS 負担が相対的に小さく、保存削減効果が大きいため適している
アルゴリズムの範囲と MDS コード
- 「Erasure Coding」は、特定の 1 つのアルゴリズムではなく アルゴリズム群 である
- Reed-Solomon コードは一般に任意の k+m 構成の Erasure Code 実装に利用できる
- RAID とも対応関係がある
- RAID-0 は k+0 Erasure Coding
- RAID-1 は 1+m Erasure Coding
- RAID-4 と RAID-5 は少し異なる k+1 Erasure Coding
- RAID-6 は k+2 Erasure Coding
- この記事の範囲は MDS(Minimum Distance Separable) Erasure Code である
- MDS コードは、任意の m 個の断片損失に耐える quorum 類似の性質を提供する
- 他の Erasure Code 系では、ある組み合わせでは m より少ない断片で復元できても、別の組み合わせでは m より多くの断片が必要になることがある
- 想定される障害パターンが分かっているなら、よく起きる障害はより少ない断片で復元し、例外的な障害はより多い断片で復元する方式が有利な場合がある
- Azure Storage の Local Reconstruction Codes と SD Codes がこの方向の例として扱われる
オブジェクトストレージとキャッシュでの適用
- 最も直接的な適用先は、固定されたレプリカ集合を持つシステムで保存コストを減らし、耐久性を高めるケースである
- 例としてはブロブ・オブジェクトストレージや NFS ストレージがある
- メタデータサービスが、ファイルパスをそのファイルを保存しているサーバーにマッピングする
- 3 つのレプリカがそれぞれ完全なファイルを保存する代わりに、15 個のレプリカが 10+5 Erasure Coded ファイル断片を保存できる
- 総保存データ量は半分になる
- 障害許容は 2 倍以上に増える
- より一般的なパターンは、「X 台のサーバーにデータを保存する代わりに、X+m 個のレプリカに X+m Erasure Code で保存する」というものである
- Marc Brooker のキャッシュシステムの例は、このパターンをキャッシュに適用している
- 一貫ハッシュで k 台のキャッシュサーバーのうち 1 台を選ぶ代わりに、k+m 台のキャッシュサーバーに k+m Erasure Code を使う
- 最も遅い m 件の応答を待つ必要がない
- 保存容量と テールレイテンシ の両方を改善できる
- この削減には、IOPS/QPS または CPU 増加というコストが伴う
- システムの制約資源が保存容量であり、CPU に余裕があるという前提が必要である
- すでに CPU 限界に近いシステムでは、コスト削減のアイデアにならない場合がある
Quorum システムの限界と HRaft
- 5 個のレプリカで、読み取りと書き込みの両方に少なくとも 3 個が必要な単純多数 quorum は、読み取りの観点では 3+2 Erasure Code とよく合う
- 任意の 3 個のレプリカ結果で読み取りを完了できるためである
- 書き込みは任意の 3 個のレプリカが受け取れば完了できるため、固定 Erasure Code では 1+2 コードしか使えない
- 1+2 はファイル 3 個の完全複製と同じである
- 単純適用だけでは保存削減はない
- RS-Paxos は、Paxos に Erasure Code を適用する際、2 つの quorum の重なりが 1 レプリカより大きい場合にのみ利点があるとみなす
- たとえば 7 個のレプリカで、読み取り・書き込みともに少なくとも 5 個が必要なら、障害許容は 2 個で 3+2 コードを適用できる
- 一般に N 個のレプリカと望ましい障害許容 f があるとき、固定 Erasure Coding で可能な最善は (N-2f)+f である
- HRaft は、単純多数 quorum でも利用可能なレプリカ数に合わせてコーディングを調整する
- 5 個すべて利用可能なら 3+2
- 4 個利用可能なら 2+2
- 3 個利用可能なら 1+2
- 適応型方式には改善の余地がある一方で、運用上の制約も大きい
- 各書き込みは、現在利用可能なレプリカ数を楽観的に見積もる
- 1 つのレプリカが予期せず書き込みを承認しなければ、書き込みを再エンコードしてすべてのレプリカに再送しなければならない
- 2 回の障害後に 1+2 構成で動作するときでも、ディスク容量やスループット不足で可用性が失われないよう、完全な値を保存できるレプリカ構成をプロビジョニングする必要がある
- 障害がまれで素早く復旧するなら、HRaft の適応型エンコードは大きな改善をもたらす
ライブラリと使用例
- Erasure Coding 計算には、成熟した標準ライブラリである Jerasure がある
- 最新の Intel プロセッサでは、Intel の Intelligent Storage Acceleration Library が SIMD 最適化ライブラリであり、ベンチマーク上位に安定して位置している
- Python では、pyeclib を通じて Erasure Coding 実装にアクセスできる
- 例では
liberasurecode_rs_vandドライバを使う - 各断片には位置識別用メタデータが先頭に付く
- いくつかの追加バイトも存在する
- 例では
- HRaft の利用可能レプリカ数ごとの例の結果は以下の通りである
- 3+2、元データ 10000 バイト: 5 個の断片、断片あたり 3355 バイト、実際の総計 16775 バイト、効率 59.61%
- 2+2、元データ 10000 バイト: 4 個の断片、断片あたり 5021 バイト、実際の総計 20084 バイト、効率 49.79%
- 1+2、元データ 10000 バイト: 3 個の断片、断片あたり 10021 バイト、実際の総計 30063 バイト、効率 33.26%
- 1+2 Erasure Encoding は、データ全体の 3 重複製と同じであり、Erasure Encoding を適用していないのと同一である
デコードコストと実装ごとの差異
- デコード性能は、復元しなければならないデータ断片数によって変わる
- 3+2 コードを 3 個のデータ断片からデコードするのは、計算上ほぼ単純である
- データ断片 2 個とパリティ断片 1 個から同じファイルをデコードするには、Gaussian elimination で線形方程式系を解かなければならない
- 必要なパリティ断片数が増えるほど計算量は増加する
- Quorum システムで Erasure Code を使うと、どのレプリカが応答したかによって CPU コスト が変わる可能性がある
- liberasurecode は一般的な Erasure Coding 実装ライブラリを抽象化するが、実装同士が等価であることを意味しない
- 2 つのコードがどちらも 3+2 だからといって、同じ数学で構成されているとは限らない
- liberasurecode は線形代数処理だけでなく、デコーダ設定や利用に必要なメタデータも追加する
- このメタデータは無効化も変更もできない
- Jerasure や ISA-L を直接使えば、Erasure Coded データだけを扱える
- ただし API 上、各断片が N 番目のデータ断片かパリティ断片かも併せて渡す必要があるため、インデックスは何らかの形でメタデータとして保持しなければならない
- Jerasure と ISA-L はアラインメント要件でも違いがある
- Jerasure は期待される線形代数出力に対して順列を適用する
- Jerasure はエンコードしたものの部分集合や上位集合を未整列のまま読み取れない
- ISA-L は順列を適用しないため、未整列の部分集合や上位集合のデコードが可能である
- 他の実装も選択肢に含まれる
- tahoe-lafs/zfec
- catid/cm256
- catid/longhair
- catid/leopard
- ボトルネックになるなら、特定のユースケースにより最適化されたライブラリを探せるが、ISA-L は一般に十分優秀である
アルゴリズム選択と数学的構成
- Erasure Code は、1 つのファイルを n 個の断片に変換して再び復元する 魔法の関数 のように扱っても、実務上は問題ない
- n 個の断片構成は一般に Galois Field を用いる線形代数で成り立っている
- Erasure Code を実運用で使うのに、この数学を必ず理解する必要はない
- ほとんどの MDS コードは行列積で計算される
- 加算は XOR に置き換えられる
- 乗算は GF(256) 上でのより高コストな乗算に置き換えられる
- パリティ断片数が 1〜3 個の特殊ケースには、Reed-Solomon ではない XOR 専用アルゴリズムがある
- m=1: すべてのデータ断片の XOR からなる単一パリティ断片
- m=2: RAID-6 に相当し、Liberation codes、HDP codes、EVENODD、X-Codes などが挙げられる
- m=3: STAR coding で可能である
- 一般的なケースでは Reed-Solomon 系を使う
- Vandermonde 行列または Cauchy 行列の構成が使われる
- 目標は、上部 k×k が単位行列となって各データ断片が保持され、m 個の行を削除した後でも逆行列が存在することにある
- エンコードはこの行列を掛けることであり、デコードは失われた断片に対応する行を削除した後、線形方程式系を解くことである
- ISA-L が使う Gaussian elimination は最も単純だが最も遅いデコード方法である
- Cauchy 行列では改善が可能で、catid/cm256 がこれを使っている
- 現時点で最も高速な方法は、catid/leopard に実装されているもので、エンコードとデコードに Fast Fourier Transform を使うようである
実装を効率化する段階
- 任意の k+m 構成で動作する Erasure Code 実装を高速化する方法はいくつかの段階に分かれる
- 第 1 段階は、アルゴリズムを C で実装し、コンパイラの自動ベクトル化に依存する方式である
- 最も単純で移植性が高い
restrictの使用や-march=nativeのようなアーキテクチャ固有のコンパイルフラグ指定が重要になる
- 第 2 段階は、ベクトル化ライブラリやコンパイラインストリンシックでプラットフォームの詳細を抽象化する方式である
- google/highway
- xtensor-stack/xsimd
std::experimental::simd- GCC ベクタ拡張 builtins
- エンコードとデコードの核心は Galois Field の乗算と加算である
- 最適化ライブラリとして catid/gf256 と James Plank’s Fast Galois Field Arithmetic Library が挙げられる
- 第 3 段階は、中心となるエンコード・デコード関数を直接ベクトル化して書く方式である
- PARPAR プロジェクトの fast-gf-multiplication と xor_depends work が高速な GF(256) 演算を扱っている
- XOR 専用の GF 乗算がテーブルベース乗算より速いというコンセンサスがあると整理されている
- さらに進めて、特定の k+m 構成に合わせてコードを特化できる
- 特定の GF 多項式とエンコード行列に合う最適なコーディング行列と XOR スケジュールを探す
- 演算、メモリ、キャッシュ最適化を適用する
- 特定アーキテクチャ向けの最適な命令スケジュールをプログラムで探索する
- 関連実装と資料として、yuezato/xorslp_ec、Thesys-lab/tvm-ec、"Fast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration Techniques" が挙げられる
さらに深く見るための資料
- Erasure Coding の線形代数入門として、次のリンクが有用である
- 幅広く掘り下げるなら、James S. Plank’s publications から確認し始める方法が提案されている
1件のコメント
Hacker News のコメント
レートレス・ファウンテンコードが言及されていないのは意外だった。この手の話題が好きなら、Luby Transform Code は面白いはず: https://en.wikipedia.org/wiki/Luby_transform_code
この論文も、より詳しい概説としてよい: https://switzernet.com/people/emin-gabrielyan/060112-capilla...
LT コードは RFC6330 で規定されている線形時間 RaptorQ エンコーディングで、外部コードとして使われている: https://www.rfc-editor.org/rfc/rfc6330
次に、アルゴリズムは実際には 2 つの部分に分かれていて、2 つ目のリカバリブロック生成は線形だが、1 つ目は 1 ブロックにまとめるメッセージ数に対して三乗時間がかかる。ほぼ行列のガウス消去法に相当する
エンコードとデコードの一部はキャッシュできるが、RaptorQ の線形時間エンコードは実質的にマーケティング文句だと思う
以前、回転式ディスクではなくマルチパスネットワーキングに頼る、かわいらしい消失訂正コードのアルゴリズムを誰かが提案していた
たぶんネットワークコーディングと呼ばれていたと思う。複数の経路があるネットワークで、メインサーバからファイル全体を待つ代わりに、あるアップストリームからファイルの 2 つの部分、あるいは 2 つのファイルを混ぜた消失訂正コードを受け取り、より早くファイルを得るというアイデアだった
S3 や他のクラウドストレージシステムの裏側にも、こうした方式は多くある気がする。特にアクセス頻度の低いストレージ階層ではその可能性が高そう。ただし AWS や GCP の内部システムを実際に知っているわけではない
参考までに、Freenet は少なくとも FEC で符号化されたファイルを使っており、どの断片を受け取るかに柔軟性があり、単一の断片が消えてもファイル全体が壊れることを減らしている
消失訂正符号は非常に昔からあった。Usenet の PAR2 ファイルを覚えている？ https://en.wikipedia.org/wiki/Parchive
消失訂正符号に関心があるなら、より大きな多次元のケースも検討する価値がある。複数のディスクにまたがって符号化するだけでなく、ラック、部屋、データセンター、リージョンといった他の障害ドメインも一緒に考えるやり方だ
目標は共通部品の故障だけでなく、より大きなシステム障害やパーティションにも耐えること。よい入門記事: https://chameleoncloud.org/blog/2023/12/12/design-considerat...
大洋横断の光ケーブルが 1Tbps しかなければ、全データを移すのに6か月以上かかる可能性がある
プロジェクトで Wirehair を使ったことがある人がいるのか気になる: https://github.com/catid/wirehair
ほぼ10年構想してきた大容量ファイルアーカイブ／データ復旧プロジェクトの標準基盤にできるほど、十分に明確に定義されているのか知りたい。公式標準ではなくても、非公式標準のように使えるのかを知りたい
これまで見つけた大きなブロック向けの消失符号の中で、理想的またはほぼ理想的なアルゴリズム性能と API の両方を備えているのはこれだけ。だから RaptorQ のように細かなディテールがあちこちに漏れ出して残りのスタックの複雑さと硬直性を高めるのとは違い、自分の用途にはよいブラックボックスになる
ただし Wirehair は仕様ではなく、あるアイデアの実装であり、実験的な実装のようにも見える。安定しているようには見えるが、2つ目の実装を自分で書いてみるか、十分に広く使われてアルゴリズムの鋭い角が明らかになるまでは、信頼できる仕様や2つ目の実装へ容易に移せるのかが心配
ただし Qualcomm が RaptorQ の特許に抵触すると主張する可能性はある。概念的に関連しているためだ。そのうち最も早い特許はまもなく失効するか、すでに失効しているはずだが、最近のファイルラッパーは確認していない。Qualcomm は RaptorQ 特許を無線以外には適用しないという約束を一部していたが、それが準拠実装だけに当てはまるのかは覚えていない
Bitcoin プロトコル本体で使うには仕様化が必要なので、何が必要かを調べたことがある。自分や何人かの Bitcoin 開発者は整数論と誤り訂正符号にはかなり詳しいが、その作業はあまり気が進まなかった。Wirehair の構造にはかなり多くのアドホックな細部があり、われわれの性向からして改善しようとして落とし穴にはまりかねないからだ
Bitcoin 側でファウンテンコードを広く使おうという関心が再び出てくるかもしれないので、少し待てば誰かが仕様を書いてくれる可能性もある
正確な用途によっては https://github.com/catid/fecal も興味深いかもしれない。想定される消失数が非常に少ないなら、Wirehair より速い可能性がある
記事で言及されている Leopard はファウンテンコードではないが、ブロックサイズはかなり大きい。仕様化の面では利点があり、単に退屈な Reed-Solomon 符号を非常に高速に実装したものなので、仕様にはフィールドと生成子の選択だけを文書化すればよいかもしれない
その通り。これが Ceph の Erasure Code プールの背後にある中核技術: https://docs.ceph.com/en/latest/rados/operations/erasure-cod...
ただし代償がないわけではない。後から符号化パラメータである k, m を変更できないため、その値が長期にわたって適切であると確信するか、最初からやり直す必要がある
この非弾力性のため、高可用性・障害耐性のあるデータ保存では、依然としてレプリケーションが支配的な選択肢になっている
ただ
--forceを使い、壊れたファイルシステムを残すだけだたぶん「その場にいたら笑えるが、自分だったら嫌だ」という類の面白さでしかないけれど
N 個のうち M 個だけが利用可能な障害状況で作られた成果物は、N 個すべてが利用可能なときとは異なる形で符号化される、という理解でよいのか？ もしそうなら「N が復旧したら再エンコードが必要」を示すビットフラグがあるべきな気がする
そうでないと、N の集合で任意の損失が起きたときに、復元力があまり高くないファイルが残ることになる
すべての分散ストレージシステムには、ストライプを点検して整理し、危険な状態から脱出させる一種の司書が必要だ
Rabin の情報分散アルゴリズムも思い浮かぶ。ここにある論文で説明されている:
https://dl.acm.org/doi/10.1145/62044.62050
実際には読み取り専用、あるいは読み取りが非常に多いワークロードでしか実用的ではないのか？