## 定義 データを 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]]) - **イレイジャーコーディングの目的は「テールレイテンシ削減」(Lambda・EC-Cache)と「ストレージオーバーヘッドを抑えた耐久性向上」(Dropbox)の2系統に分かれ、どちらも本質は同じ「k-of-(k+m) の冗長性を待ち行列の柔軟性に変換する」という設計原理に帰着する**: [[@2021__OReillyJapan__SREの探求 - Chapter 17 データ耐久性のエンジニアリング]] は、フルレプリケーション(n個の完全コピー)に比べてストレージオーバーヘッドを大幅に削減しながら高い耐久性を実現する手法としてイレイジャーコーディングを位置づけ、Dropbox がエクサバイト規模のデータに対し、複数地域に分散しつつ日常的なディスク障害からのリカバリに必要な地域横断ネットワーク帯域幅を最小化する変種を使っていると述べる。これは Lambda の 4-of-5 スキームが「5ノードのうち最初に届いた4つで再構成し、残り1つの遅延を無視する」ことでテールレイテンシを削減するのと表面上の目的は異なるが、いずれも「n個のうちk個あれば復元できる」という同じ冗長性の数理を、Lambda はレイテンシの分散(待たなくてよい選択肢を増やす)に、Dropbox は耐久性とネットワークコストの最適化(リカバリに必要な帯域を絞る)に転用している点で共通する。(Source: [[@2021__OReillyJapan__SREの探求 - Chapter 17 データ耐久性のエンジニアリング]] §17.1.2, [[@2023__ATC__On-demand Container Loading in AWS Lambda]]) ## 未解決の問い - k-of-(k+m) のパラメータ選択(k と m の比率)はどのように最適化するか？Lambda は 4-of-5 を選んでいるが、異なる障害モデルや負荷パターンで最適値は変わるか？ - イレイジャーコーディングのパリティ計算コスト(Lambda では AVX/NEON で 10x 高速化が必要だった)は他のシステムでも課題になるか？ - Dropbox が採用する「地域横断のリカバリ帯域幅を最小化する変種」の具体的な符号化方式(パラメータ n, m の値、地域内/地域間での符号化の使い分け)は [[@2021__OReillyJapan__SREの探求 - Chapter 17 データ耐久性のエンジニアリング]] には明記されておらず、Lambda の 4-of-5 のような単純な k-of-(k+m) 構成とどう異なるかは未確認。 ## 関連 - [[@2023__ATC__On-demand Container Loading in AWS Lambda]] — L2 キャッシュでの 4-of-5 実装の詳細 - [[@2021__OReillyJapan__SREの探求 - Chapter 17 データ耐久性のエンジニアリング]] — エクサバイト規模ストレージにおける耐久性・帯域幅最適化目的での利用(§17.1.2) - [[コンテナ起動高速化]] — テールレイテンシが問題になる文脈 - [[メタ安定障害]] — 再試行に依存しないための定常作業原則 - [[データ耐久性]] — レプリケーションに代わる耐久性実現手法としての位置づけ ## 出典 - 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. - [[@2021__OReillyJapan__SREの探求 - Chapter 17 データ耐久性のエンジニアリング]] §17.1.2