Ceph で使われている CRUSH アルゴリズムの論文を読んだのでメモ

この記事は Ceph でオブジェクトの配置先を決定するのに使われている CRUSH アルゴリズムの論文を読んで内容を自分向けにまとめたものです。

CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data

翻訳ではないので私の解釈が入ったり削ったりした部分があるのでご注意ください。

Introduction

CRUSH はオブジェクトの識別子を、それが保存されているデバイスにマッピングするアルゴリズムである。

ここでオブジェクトはオブジェクトグループであったり、デバイスはデバイスのリスト (オブジェクトがレプリケーションされている場合) だったりする。

従来のようなファイルごと、ディレクトリごとにマッピングを持つような手法とは違い、CRUSH はストレージクラスターの階層を表現した地図と、その中でのオブジェクトの配置ルールだけを使ってマッピングを行うのでコンパクトである。

このアプローチは 2 つの点で有効である:

1. クライアントはそれぞれ独立に、オブジェクトの配置位置を導出できる (つまり Read/Write でボトルネックが生じにくい)
2. デバイスが追加されたり削除されたりした時しかメタデータ (地図のこと) が変化しない (つまりほぼ静的である)

Related Work

CRUSH は従来研究と比べて以下の点が進歩している:

• オブジェクト配置の偏りを減らすための再配置や、デバイスの重み付けが考慮されている
• オブジェクトの配置場所を決定するのに、コンパクトなクラスター地図と決定性のマッピング関数だけを使う。これは特にデータの書き込みの時に効果的で、特定の中央サーバーを介さずに、クライアントが独自にオブジェクトの配置場所を導出できる (別に読み込みの時も同様に効果的な気が？)
• 基となった RUSH アルゴリズムで課題だった信頼性とレプリケーションを改善し、パフォーマンスと柔軟性が向上している

The CRUSH algorithm

オブジェクトが配置されているデバイスは cluster map, placement rules, x (オブジェクトの識別子) だけから計算可能である。

cluster map は device と bucket で構成され、bucket を内部ノード、device を葉ノードとする木構造である。device はプロパティとして weight を持ち、bucket の weight は子ノードの weight の総和である。

この木構造はストレージクラスターの物理的な構成を反映させることを意図している。例えば HDD の一つ一つを device とし、それらを収めるサーバーをの親 bucket とし、さらにそれらのサーバーを収めるラック、それらが並ぶデータセンターのフロアの列、そしてフロア全体、といった具合に bucket でまとめていく。物理的、ネットワーク的に近いディスク同士は同時に故障する確率が高い (電源故障やネットワーク障害によって) ので、オブジェクトのレプリカを木構造的に遠くに配置することで耐障害性を高められる。

placement rules は cluster map の木構造をルートからリーフまでどのように辿るかを記述するルールのリストである。辿った先のリーフ (リーフは必ず device) がオブジェクトの配置先となるデバイスである。

placement rules は次の 3 つの関数で記述される。

x = 'オブジェクトの識別子'
trees = []  # 現在処理中の cluster map のサブツリー
devices = []  # オブジェクトの配置先となる device の一覧 (レプリカの数だけ device が選ばれる)


def take(cluster_map, trees=trees):
    """探索のルートとなるツリーをセットする
    """
    trees.clear()
    trees.append(cluster_map)


def select(num_replicas, node_label, trees=trees, x=x):
    """ツリーを辿り、node_label を持つノードを num_replicas 個選択する

       num_replicas: 選択するノードの個数
       node_label: 選択するノードのラベル (row, rack, cabinet, device 等)
    """
    subtrees = []
    for bucket in trees:
        for i in range(num_replicas):
            while True:
                # 論文ではここでデバイス故障時の対応もしていたが省略

                # 後述する決定性のアルゴリズムに従って子ノードを選択する
                child = bucket.select_child(i, x)

                if child.label != node_label:
                    bucket = child
                    continue
                else:
                    subtrees.append(child)
                    break
    trees.clear()
    trees.extend(subtrees)


def emit(trees=trees, devices=devices):
    """リーフの一覧を配置先としてセットする
    """
    devices.extend(trees)

この 3 つの関数を使い、placement rules を記述する例を示す。

今、例えば cluster map が次のようであるとする。ただし bucket(label, id), device(label, id) という書式である。

• bucket(ROOT, 'root')
  • bucket(ROW, 'row1')
    • 省略
  • bucket(ROW, 'row2')
    • bucket(CABINET, 'cabinet1')
      • device(DISK, 'disk1-1')
      • device(DISK, 'disk1-2')
      • device(DISK, 'disk1-3')
    • bucket(CABINET, 'cabinet2')
      • device(DISK, 'disk2-1')
      • device(DISK, 'disk2-2')
      • device(DISK, 'disk2-3')
    • bucket(CABINET, 'cabinet3')
      • device(DISK, 'disk3-1')
      • device(DISK, 'disk3-2')
      • device(DISK, 'disk3-3')
    • bucket(CABINET, 'cabinet4')
      • device(DISK, 'disk4-1')
      • device(DISK, 'disk4-2')
      • device(DISK, 'disk4-3')
  • bucket(row, 'row3')
    • 省略

この時、placement rules が次のようなものであるとき、

take(ROOT)
select(1, ROW)
select(3, CABINET)
select(1, DISK)
emit()

オブジェクトが配置されるデバイスは次のように決定される。

1. take(ROOT): ROOT を探索のスタート地点とする
2. select(1, ROW): ROOT 直下の ROW から一つを選ぶ。ここでは row2 が選ばれたとする
3. select(3, CABINET): row2 の子から CABINET を 3 つ選ぶ。ここでは cabinet1, cabinet3, cabinet4 が選ばれたとする
4. それぞれの cabinet の子から DISK を一つずつ選ぶ。ここでは disk1-1, disk3-2, disk4-3 が選ばれたとする
5. disk1-1, disk3-2, disk4-3 をオブジェクトの配置先とする。ここではレプリカ数は 3 となる

この他、論文ではディスクの追加／削除でレプリカの再配置がどれくらいの量起こるかが簡単に触れられていたが、ここでは割愛する。基本的には cluster map 内の総 weight のうち、追加／削除された device の weight 分、少なくとも再配置が必要になる。

また bucket には 4 つのタイプが定義されており、uniform bucket, list bucket, tree bucket, straw bucket がある。タイプごとに bucket.select_child(i, x) の計算量と、配下のデバイスの追加／削除時のレプリカの再配置効率が異なる。

	Uniform	List	Tree	Straw
計算量	O(1)	O(n)	O(log n)	O(n)
ディスク追加時の再配置の効率	悪い	非常に良い	良い	非常に良い
ディスク削除時の再配置の効率	悪い	悪い	良い	非常に良い

各 bucket のデータ構造と bucket.select_child(i, x) の計算方法が簡単に説明されていたが、これはより詳細な Ceph の実装のドキュメントを見た方がよいと判断したためここでは省略。

Evaluation

図表だけ斜め読みした。

• ディスクの追加／削除に伴うレプリカの再配置効率を、CRUSH, RUSH_p, RUSH_t について比較していた。CRUSH は追加、削除で安定して高効率な結果だった。
• uniform, list, tree, straw の 4 種の bucket について、子ノードの追加後のレプリカ再配置の効率を比較していた。straw が安定して好成績だった。
• cluster map の階層の深さの増加に伴う、計算量の増加を list, tree, straw, そして RUSH_t, RUSH_p について比較していた。RUSH_t と tree が好成績だった。
• bucket の子ノードの数の増加に伴う、計算量の増加を uniform, list, tree, straw について比較していた。理論通り、uniform は O(1)、tree は O(log n)、list, straw は O(n) なカーブを描いていた。

Future Work

• Ceph で使われている今の placement rule で十分に柔軟ではあるが、もっと柔軟に書けるシステムも存在はする
• なんらかの統計モデルを使って MTTDL (Mean Time To Data Loss) を評価する
• マッピングにはハッシュ関数が使われていて、この性能はオブジェクトへのアクセススピードやレプリカの均等な分散にも影響するので、よりよいハッシュ関数がないか調査する

おわりに

おそらく紙面の都合で、論文だけでは詳細がつかめない部分があったので他のドキュメントも続けて読んでいきたい。

• CRUSH Maps — Ceph Documentation には特にマッピングのより詳細が説明されているので読む
• Apache Hadoop 3.3.0 – HDFS Architecture は同じ分散オブジェクトストレージとして Ceph とアーキテクチャの比較をしながら読む