分散システムのためのErasure Coding技術

[GN⁺]

Hacker Newsのコメント

• rateless fountain codes への言及がないのは意外

  • Luby Transform Code が興味深い
  • LT codes は RFC6330 の RaptorQ エンコーディングで使われている

• 過去に提案されたネットワークコーディングのアルゴリズムがある

  • 複数経路を通じてファイルをより速く受け取れる可能性がある

• Erasure coding は古くからある技術

  • Usenet の PAR2 ファイルを思い出すべき

• Erasure coding に興味があるなら、多次元的なケースを考えるべき

  • スピンドルだけでなく、ラック、部屋、データセンター、地域など、さまざまな障害ドメインにまたがるエンコーディングを考える必要がある

• Wirehair をプロジェクトで使ったことがある人がいるのか気になる

  • Wirehair は理想的なアルゴリズム性能と API を備えている
  • しかし Wirehair は仕様ではなく、アイデアの実装である
  • 安定してはいるが、信頼できる仕様へ変換できるのか不安

• Ceph の Erasure Code pool の中核技術

  • コーディングパラメータ (k, m) は後から更新できない
  • この非柔軟性のため、高可用性・耐障害性データ保存では依然としてレプリカが主な選択肢になっている

• M of N の事象の間に生成された成果物は、すべての N が利用可能な場合と異なる形でエンコードされるのか気になる

  • 「N が復旧したときに再エンコードが必要」であることを示すビットフラグが必要かもしれない

• Rabin の Information Dispersal Algorithm を思い出させる

  • 関連論文へのリンクあり

• 読み取り専用または読み取り集中型のワークロードにしか実用的でないのか気になる

• Ceph が分散ブロブストレージで採用しているレプリケーション戦略の1つ