30分で論文流し読みシリーズ4「CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data」

CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data

  • 実際の所要時間 1時間半
  • 課題
    • オブジェクトストレージにおいて、どのストレージデバイスにどのようにデータをを配置するかには様々な方法がある
    • 既存のものは巨大なメタデータ(およびそれを置くメタデータサーバ)が必要だったりストレージデバイスの故障や追加/削除によって大量のデータの移動が必要だったりと一長一短
    • RUSHという計算によってオブジェクトの配置場所を決めるいいかんじのアルゴリズムがあるが、あんまり効率がよくない
  • 解決方法概要
    • CRUSHと言うアルゴリズムを開発した
      • データを各ストレージデバイス疑似ランダムに配置できる
      • レプリカやイレージャコーディングも可能
      • ストレージデバイスの故障や追加/削除によるデータの再配置が少なくて済む
      • デバイスごとにweightも変えられる。たとえば大容量のストレージデバイスのweightを上げて小容量のものはweightを下げる、など
      • トポロジーを意識したデータ配置ができる。この構成のことをcrush mapと呼ぶ
      • crush mapに対して、あるオブジェクトのレプリカを同じノードに置かないとかいうルールが作れる。これをplacement ruleと呼ぶ
  • 解決方法詳細
    • 論文の中のAlgorithm 1、figure 1~4あたりを見てね!
    • 細かいところではinternal nodeに相当するbucketの種類が複数ある(uniform buckets, list buckets, tree buckets, straw buckets)
    • それぞれオブジェクトをストレージデバイスにmapする速度、デバイス追加/削除時の処理の効率が違う(table 2参照)
  • 効果
    • 様々な性能をbucketの種類ごとに、場合によってはそれに加えてRUSHのものと比較してある(figure 5~8)

感想 - Ceph(データ配置にCRUSHを使っている)の内部を知るには読んどかないとまずい - 魔法のようである。うまくやるものだ - RUSHの論文も読んでおかないとうまく解釈できないと思う

Cephとの比較 - Cephにおいては、いまではbucketは上記4つとはまた違うstraw2というのがデフォルトで使われている。もはや他のものをあえて使う必要はないだろう - placement ruleはCephにおいてはcrush ruleと呼ばれることが多い - オブジェクトは直接ストレージデバイス(正確にはOSD)にマップされるのではなく、Placement Groupというものにマップされる。同じplacement groupに属する全オブジェクトは、placement groupに対応するOSDにレプリカを配置する。たぶん組み合わせ数が死ぬほど増えるのを防ぐためにこうなってる