ikemonn's blog

技術ネタをちょこちょこと

CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data を読んだ

CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Dataを読んだ時のメモ。

どんなもの?

  • 擬似ランダムデータ分散アルゴリズム
    • データの名前に対して偏りが無いようにデータノードを割り当てる
    • central allocatorがいなくても新しいデータの保存先を計算できるアルゴリズム
    • マッピングの計算はO(log n)で終わり、何千台ものデバイスがあっても数ミリ秒で計算できる

先行研究とくらべて何がすごい?

  • 先行研究
  • CRUSH
    • リソースに余裕がある部分に動的にデータを分散していく
    • ストレージデバイスの追加・削除時には効率的にデータを再配置する
    • データの位置を擬似ランダムマッピング関数で計算することで、データの保存位置に関するメタデータの必要性を減らした

技術や手法の肝は?

  • ClusterMap
    • データノードのリストのこと
    • bucketとdeviceで構成される
      • 双方、数値IDと重みを持っている
    • bucket
      • 木構造のnode
      • 任意の数のdeviceとbucketで構成される
    • device
    • 階層構造になっており、root -> row -> cabinet -> diskのように構成されている

f:id:ikemonn:20170710233357p:plain

  • Collisions, Failure, and Overload

    • バイスが高負荷だったり、障害があったりすると、階層構造に残したままフラグが立てられる
      • 高負荷だったり障害は一時的なものが多く、不要なデータの移動を避けるため
      • placementアルゴリズムによって、再分散される
  • Bucket Types

    • 下記の4つがあり、データ移動の際にそれぞれ異なった選択アルゴリズムが適用される
      • uniform bucket
        • 従来のhashアルゴリズムと同じで、全ての要素に重みが与えられる
      • list bucket
        • 要素がlinkリストのような構造をしており、要素に任意の重みをつけられる
      • tree bucket
        • 素数が少ない時は効率的に処理ができるlinkリストのような構造
      • straw bucket
        • ハッシュ関数を横ではなく縦に適用するようなイメージ
        • 重みが最大になるアイテムに、より多くのアイテムがひも付きやすくなる
          • deviceの追加・削除時のデータの移動を効率化する

f:id:ikemonn:20170710233310p:plain

どうやって有効と検証した?

f:id:ikemonn:20170710233433p:plain - storage deviceを追加・削除した後のデータの再配置の効率性 - 1が最適な状態 - 総合的にみるとstraw bucketのパフォーマンスが良い

f:id:ikemonn:20170710233447p:plain

  • アイテムを追加した後のデータの再配置の効率性
    • 1が最適な状態
    • strawとlist headのパフォーマンスが良い
    • listのtailは悪い
    • treeはbucket sizeの対数値によって変化する

f:id:ikemonn:20170710233516p:plain - 階層サイズの計算時間の違い - CRUSHは対数的にスケールする

f:id:ikemonn:20170710233530p:plain

  • レプリカを個々のCRUSH bucketとbucketサイズにマッピングするLow-level speed
    • uniformは一定の時間
    • treeは対数的な時間
    • listとstrawは線形の時間

議論はある?

  • 一般的にはdevice failedは一時的なものなので、階層構造に残しているが、本当に故障していたりするとパフォーマンスが劣化する

次に読むべき論文は?

Evaluation of distributed recovery in large-scale storage systems.