30分で論文流し読みシリーズ5「Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data Distribution」

Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data Distribution

↓の参考として挙げられているもの satoru-takeuchi.hatenablog.com

• 実際の所要時間: 1時間半
• 課題
  • 分散ストレージにおいてオブジェクトの配置情報を中央集権型でなくするには、かつては実際のデータ配置前にすべての配置位置を決めて、その後のディスク増減コストは大量のデータ移動が必要な高コストなものだった
• 解決方法概要
  • RUSHというアルゴリズムセットを開発した*1
  • RUSHはディスクの追加削除も低コストでできる
• 解決方法詳細
  • ストレージクラスタはサブクラスタ単位に分かれる。ディスク追加において、一回に追加するディスク群をサブクラスタと呼ぶ。クラスタ全体はサブクラスタの集まりの木構造となる
  • サブクラスタ内のディスクが故障すると同じサブクラスタ内の他のディスクにデータが再配置される(figure7を参照)
  • レプリケーションによる冗長化をサポートする
  • レプリケーションする場合は、あるオブジェクトのレプリカがそれぞれ別のディスクに配置されることを保証する
  • Rush{P,R,T}という三つのアルゴリズムが存在する。それぞれの違いはtable2に書いている
  • 各ディスクにweightも付けられる
• 効果
  • 図5~8あたりを参照
• 感想
  • CRUSHの論文にRUSHには問題があるようなことが書かれていたが、たしかにこれだけだとけっこうつらそう。以下理由
    • あるオブジェクトのレプリカを同じラックに配置するようなtopology awareな配置ができない
    • ちょこちょこストレージを足していくとサブクラスタの数が増えて色々な処理が低速化しそう

*1:正確にはRushPは以前の論文に既に書かれている