CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data を読んだ
CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Dataを読んだ時のメモ。
どんなもの?
- 擬似ランダムデータ分散アルゴリズム
先行研究とくらべて何がすごい?
- 先行研究
- CRUSH
技術や手法の肝は?
- ClusterMap
Collisions, Failure, and Overload
Bucket Types
どうやって有効と検証した?
- storage deviceを追加・削除した後のデータの再配置の効率性 - 1が最適な状態 - 総合的にみるとstraw bucketのパフォーマンスが良い
- アイテムを追加した後のデータの再配置の効率性
- 1が最適な状態
- strawとlist headのパフォーマンスが良い
- listのtailは悪い
- treeはbucket sizeの対数値によって変化する
- 階層サイズの計算時間の違い - CRUSHは対数的にスケールする
- レプリカを個々のCRUSH bucketとbucketサイズにマッピングするLow-level speed
- uniformは一定の時間
- treeは対数的な時間
- listとstrawは線形の時間
議論はある?
- 一般的にはdevice failedは一時的なものなので、階層構造に残しているが、本当に故障していたりするとパフォーマンスが劣化する
次に読むべき論文は?
Evaluation of distributed recovery in large-scale storage systems.