## 定義 データを k 個のデータシャードと m 個のパリティシャードに分割し、任意の k 個のシャードがあればデータを復元できるようにする前方誤り訂正技法。k-of-(k+m) 符号とも表現される。ストレージシステムでは冗長性の確保に広く使われ、レプリケーション(n 個の完全コピー)に比べてストレージオーバーヘッドを大幅に削減できる。(Source: 一般的な定義; [[@2023__ATC__On-demand Container Loading in AWS Lambda]]) ## キャッシュシステムでの応用 通常イレイジャーコーディングはストレージの耐障害性確保に使われるが、AWS Lambda の L2 キャッシュでは**テールレイテンシ削減**のために使っている点が特徴的である([[@2023__ATC__On-demand Container Loading in AWS Lambda]])。 **Lambda の 4-of-5 スキーム**: - キャッシュミス時: ワーカーがオリジン(S3)からチャンクを取得後、5 本のイレイジャー符号化ストライプを 5 ノードに分散アップロード - キャッシュヒット時: 5 ノード全てにリクエストを送り、最初に届いた 4 ストライプで即座に再構成(残り 1 つの遅延・障害は無視) - ストレージオーバーヘッド: 25%(5/4 = 1.25x) - リクエスト数増加: 25%(5 リクエスト / 4 必要なストライプ) **EC-Cache との類似**: EC-Cache (OSDI 2016, Rashmi et al.) は同様の発想をクラスタキャッシュに適用した先行研究。 **レプリケーションとの対比**: | 手法 | テールレイテンシ | ストレージコスト | ヒット率低下(ノード障害時) | |------|----------------|----------------|--------------------------| | レプリケーション(n=2) | 良好 | 2x | あり(該当ノードのデータ) | | 4-of-5 イレイジャーコーディング | 良好 | 1.25x | なし(k+1 ノードが稼働していれば復元可能) | **定常作業(Constant Work)との関係**: 再試行(retry)に依存するテールレイテンシ対策はメタ安定障害モードを誘発する。イレイジャーコーディングは成功時と失敗時で同じ量の作業(5 ノードへのリクエスト)を行うため、この問題を回避する。[[メタ安定障害]]参照。 ## 横断的知見 - イレイジャーコーディングをキャッシュシステムのテールレイテンシ削減に使うのは EC-Cache (OSDI'16) と Lambda が代表例。ストレージ(S3・HDFS 等)での耐障害性確保とは目的が異なる点が興味深い。(Source: [[@2023__ATC__On-demand Container Loading in AWS Lambda]]) - 1000 チャンクを取得する起動では、キャッシュの 99.9 パーセンタイルレイテンシを 63% の確率で経験する。このことから、単一ノードの高速化だけでなくシステムレベルのテール管理が重要になる。(Source: [[@2023__ATC__On-demand Container Loading in AWS Lambda]]) ## 未解決の問い - k-of-(k+m) のパラメータ選択(k と m の比率)はどのように最適化するか？Lambda は 4-of-5 を選んでいるが、異なる障害モデルや負荷パターンで最適値は変わるか？ - イレイジャーコーディングのパリティ計算コスト(Lambda では AVX/NEON で 10x 高速化が必要だった)は他のシステムでも課題になるか？ ## 関連 - [[@2023__ATC__On-demand Container Loading in AWS Lambda]] — L2 キャッシュでの 4-of-5 実装の詳細 - [[コンテナ起動高速化]] — テールレイテンシが問題になる文脈 - [[メタ安定障害]] — 再試行に依存しないための定常作業原則 ## 出典 - Rashmi et al. "EC-Cache: Load-Balanced, Low-Latency Cluster Caching with Online Erasure Coding." OSDI 2016. - Brooker et al. "On-demand Container Loading in AWS Lambda." USENIX ATC 2023.