Ceph, 特にCRUSHアルゴリズムについて - 超ウィザード級ハッカーのたのしみ

Cephに興味が出たので調べていまして、そのメモ代わりに……

どのサーバーが何のデータを持っているのか覚えておかなければならない問題

分散ストレージシステムで面倒な課題にデータの位置の管理があります。あるファイルがあったとして、そのデータを読みたい。その際何も手段がなければ、どのサーバーが欲しいデータを持っているか分かりません。最も単純な解決方法は、どのサーバーが何のデータを持っているか覚えておくサーバーを用意することです。データを持っているサーバーをデータノード、どのデータがどのデータノードにあるかを覚えているサーバーをメタデータノードとでも呼ぶことにします。メタデータノードを用意する方法では、データにアクセスしたいマシン（アクセスクライアントと呼びます）がデータを得るには以下のような操作を行う必要があります。

アクセスクライアントは、メタデータノードに欲しいデータがあるデータノードのホスト名を問い合わせる。
メタデータノードは、記録している情報からアクセスクライアントが指定したデータを持っているデータノードを探して、アクセスクライアントにそれを教える。
アクセスクライアントはメタデータノードに教えてもらったデータノードに、データのリスエストを行う。
データノードは、アクセスクライアントにリクエストされたデータを渡す。

世の中の分散ファイルシステムはもう少し洗練された形体になっていますが、何かしらの形でデータの場所を覚えておくという機能は必要となります。

Cephはデータの場所を覚えなくて良い

しかし、Cephはデータの場所を覚えておく機能がありません。アクセスクライアントは、データの場所を問い合わせることなく、どのデータがどこのサーバーにあるのか知ることができます。CRUSHアルゴリズムという仕組みに、データの名前を入力すると、データを持つデータノード*1のホスト名のリストが出力されます。

データの名前 x --(CRUSH)--> データを持つデータノードのホスト名のリスト R

ざっくりいうとハッシュ関数のようなものです。データの名前に対して、偏りがないようにデータノードを割り当てます。ランダムではないので、同じxに対しては同じホスト名が返されます。この処理はアクセスクライアントのローカルで行うことができるので、データの場所の問い合わせをしなくても良くなります。書き込む場合も同様でどのホストに書き込めばいいのかをアクセスクライアントは自分で判断することができます。

Cephはストレージを階層構造で管理する

データノードのリストと、いくつデータノードを選ぶかというのは予め与えておきます。ですので、正しくは入力はデータの名前だけでなく、データノードのリストとデータノードの数となります。CRUSHに与えるデータノードのリストとデータノードの数というのは、実際にはもう少し複雑です。データノードのリストはcluster mapと呼ばれます。データノードの数等のデータの配置の仕方はplacement ruleと呼ばれます。

cluster mapは木構造になっています。nodeをbucket, leafをdeviceと呼びます。deviceは記憶装置の最小単位、例えばディスクです。bucketには、複数のbucketやdeviceが含まれており、階層構造となっています。一番上の階層がrootだとして、その次がrow、その次がcabinetといった具合です。

placement roleはcluster mapからのdeviceの選び方を決定しています。

rootからrowを１つ選び、そのrowから3つcabinetを選び、それぞれのcabinetから１つずつ、計３つのdeviceを選ぶ
rootからrowの2つ選び、それぞれのrowから１つcabinetを選び、それぞれのcabinetから２つずつ、計4つのdeviceを選ぶ

等を指定できます。

Bucket Types

root, row, cabinet等のbucketには４種類あって、bucket内のアイテムを選ぶ場合の動作が異なっています。

uniform bucket
list bucket
tree bucket
straw bucket

が用意されています。

uniform　bucketはハッシュ値の剰余をもとに選択するという最も単純な方法を取ります。list bucketとtree bucketについては割愛します。

straw bucketというのが驚くべきアイデアで私は非常に関心しました。

straw bucketという名前はdrawing strawsというゲームに由来します。ディーラーが藁の束を長さが分からないように持っておいて、プレイヤーが１本づつ藁を引き、藁の長さが最も大きかったプレイヤーが勝ちというゲームです。

名前xのデータのr番目のレプリカが存在するアイテムiを選ぶ関数は

c(r, x) = max_i(w_i hash(x, r, i))

のようになっています。w_iはアイテムの重みでアイデムが格納できるデータの容量を示しています。アイテムそれぞれについてハッシュ値を計算し、最も値が大きいアイテムを選ぶという仕組みです。重みを掛けることで、重みの大きいアイテムが選ばれやすくなります。

アイテムが横に並んでいるイメージだと、uniform bucketのような単純な方法はハッシュ関数を横向きに使います。一方、straw bucketはハッシュ関数をアイテムごとに、いわば縦向きに使用します。発想の転換があって興味深いです。

このstraw bucketの仕組みの何がうれしいのかというと、アイテムを増やしたり減らしたりした場合に、もともとあるアイテムに割り当てられているデータの位置が最低限しか変わらないことです。

例えば、A・B・Cの３つのアイテムがあって、新たにDのアイテムがbucketに追加されたとしましょう。A・B・Cのそれぞれにもとからあるデータの1/4ずつが、Dに移動されるのが理想です。逆に、A・B・C・Dの４つのアイテムがあったとして、Dのアイテムをbucketから削除したとしましょう。もともとA・B・Cにあったデータは移動せずに、DにあったデータがA・B・Cに1/3ずつ移動されるのが理想です。

uniform bucketの場合は最低で、アイテムを追加・削除するとすべてのデータを移動させなければなりません。ハッシュ値の剰余から選んでいるのでアイテム数が変わると、すべてがずれていきます。

しかし、straw bucketは理想的な動作を実現しています。先ほどの例ですと、A・B・Cの藁の長さw_i hash(x, r, i)はDの追加・削除で変わることはありません。もともとAにデータが割り当てられていた状態：Aの藁が最も長い状態のときに、Dを追加してDの藁がAより長くなる確率は1/4です。Dを削除する場合も、もともとDにあったデータは、A・B・Cの中で最も長い藁を持っているアイテムに移動するだけです。もともとAにあったデータは、B・Cの藁がAより長くなったりしないので、そのままの位置にとどまります。

straw bucketに唯一欠点があるとすれば、bucket内の全アイテムについてハッシュ値を計算しなればならないので計算量がアイテム数のオーダーになってしまうことです。しかし、Cephではbucketは階層構造になっているので一つのbucket内のアイテム数が極端に大きくなったりはしないので、問題にはならなさそうです。

まとめ・感想

あまりまとまっていませんが、CephのキモであるCRUSHアルゴリズムの概要について書いてみました。調べて思ったことは、Cephを作った人はとんでもなく頭がいいということです。Cephには多くの驚くべきアイデアが詰まっているということが分かりました。こういう人と仕事したいです。

参考

*1:Cephではデータノードという用語は使われていません。Object Storage Device (ODS)と呼ばれています。