RADOS の概略 (RADOS と CRUSH と Placement Group の関係)

作成日:2012.02.10
更新日:2012.10.27

このページでは Ceph や RBD を使う上で分かり辛い RADOSCRUSHPlacement Group の概念を掘り下げて説明する。

以下は関連ページ。


更新履歴
(2012.02.10) 作成。
(2012.10.27) Mapping Algorithm を追加。


目次

1. RADOS

RADOS (Reliable Autonomic Distributed Object Storage) はレプリケーション機能を備えた分散オブジェクトストレージである。 オブジェクトストレージはオブジェクトを単位としてデータをやり取りするストレージシステムである。 これが分散オブジェクトストレージを構成するので、多数のノードとディスクを束ねて全体で一つのストレージのように振舞う。 Amazon S3 を思い浮かべるとよい。

OSD の実体は、Linux ホストマシン上で動く OSD デーモンプロセスである。 OSD デーモンは動作しているマシンの指定のサブディレクトリ以下または指定のブロックデバイスにファイルを格納してゆく。 ブロックデバイスを指定した場合、デフォルトではそのブロックデバイスを btrfs でフォーマットして使用する。 ホスト(マシン)と OSD の関係は、構成方法によって変わる。

  1. ホストマシンに複数台の HDD を載せて、それぞれの HDD を別々の OSD として扱う。この場合、1台のホスト上に複数の OSD デーモンプロセスが動作することになる。
  2. ホストマシンに複数台の HDD を載せて全体をハード RAID や LVM で一まとめにみせる。概念的には 1 OSD となる。

実際は OSD はジャーナル機構を持ち、SSD などの高速なフラッシュデバイスをジャーナルに割り当てることが推奨されている。 1. のように HDD 1 台とジャーナル用の SSD 1 台をペアにしてそれをホストマシン内に複数組つくるか、2. のように複数台の HDD を束ねてジャーナル用の SSD 1台と組み合わせて OSD を作るかは思案が分かれる。

RADOS を使ってみる

Ceph をインストールした状態であれば、RADOS として使用することができるので使ってみる。 Ceph のモニタ(mon)が動いているマシンで以下のように操作してみよう。

まず RADOS 内に既に存在しているプールは lspools コマンドで表示される。 最初から datametadatarbd のプールが存在している。 詳細は後で述べるが datametadata は ceph ファイルシステムのために、rbd は RBD ブロックデバイスのために使用される。

# rados lspools
data
metadata
rbd

自分用に mypool というプールを作ってみる。

# rados mkpool mypool

適当な大きさのファイルをオブジェクトとして突っ込んでみる。

# rados -p mypool put ceph-0.41.tar.gz.obj  /home/nminoru/ceph-0.41.tar.gz
successfully created pool mypool

ls コマンドを使うと格納状況を確認できる。

# rados -p mypool ls
ceph-0.41.tar.gz.obj

RADOS のファイルはどこに格納されたのか?

オブジェクトは RADOS 支配下の OSD に格納される。 OSD の実体は「Ceph に関する覚え書き」で設定したように ceph.conf 設定ファイルに記述された /data/osd0/ のような指定ディレクトリ以下である。

このディレクトリを探すと先ほど PUTした ceph-0.41.tar.gz.obj の実体が見つかる。

/data/osd0/current/3.5_head/ceph-0.41.tar.gz.obj__head_D4271CB5

少し説明すると、

複数の OSD を使っている場合、レプリケーションができる。 デフォルトのレプリカ数は 2 なので、OSD が 2 台しかなければ /data/osd1/current/3.5_head/ceph-0.41.tar.gz.obj__head_D4271CB5 に同じファイルが入っているはずである。

3. Replication

RADOS はレプリケーションをとる。 レプリケーションには複数のコピー(レプリカと呼ぶ)が対等の関係を持つ Multi-Master Replication と呼ばれる方式や、レプリカ間に優先順位があり基本的に第一コピーが重要となる Primary-Copy Replication という方式がある。

RADOS のレプリケーション方式は Primary-Copy Replication である。

このような特徴があるため、RADOS のレプリケーションは全てのレプリカが対等ではなく、プライマリーとセカンダリー(secondary)以降に大きな非対称性がある。 またセカンダリー以降も優先番号が付いているので、多重度が 3 以上の場合にはサードリー、フォースリーのように順位が付く。

オブジェクト毎にレプリカの配置位置は違うので大量のオブジェクトが RADOS に格納される場合にはプライマリーレプリカは全ての OSD に分散して配置される(ただし分散の単位は4.で述べるplacment groupの点に注意)。 そのためプライマリーレプリカを担当した OSD の負荷も分散される。

RADOS クラスタ内の特定の OSD がダウンした後に、RADOS があるオブジェクトにアクセスしたとする。

3. CRUSH

RADOS は大規模分散環境を目的として設計された。 よって OSD を数千台並べてペタスケールの容量を実現することを想定している。

RADOS は CRUSH(Controlled Replication Under Scalable Hashing) と呼ぶアルゴリズムでこれを解決している。 CRUSH は階層化された consistent hash であり、同時にクラスタのネットワークトポロジーやディスクの性質によりユーザがルールセット(rule set)を設定することで目的に応じた構成を可能にしている。

CRUSH が consistent hash かどうかは判断が難しいような気がする。 5. Mapping Algorithm を読んで考えてほしい。

例えば 1 つのデータセンターの中にラックの列(raw)があり、ラック(rack)には複数台のホスト(host)が格納され、ホストには複数台の HDD が格納されていたとする。 HDD装置(device) 1台 1台が OSD だとすると、root - raw - rack - host - device という階層が見える。 この時、「3重のレプリケーションをとりたいけどラック列を跨いだ位置にレプリカを作るのはネットワーク負荷がかかるので避けたい。 逆に同じホスト内の HDD (device) に同一オブジェクトのレプリカができたら、ホストマシンが死んだときにまずいので避けたい」というような要求が出てくる。

これを実現するために以下のようなルールを決める。

  1. まず列(raw)を1つだけ選択する。
  2. 取り出した列(raw)の中から3つのホスト(host)を選択する。この場合、別々のホスト(host)が選択できれば同一ラック(rack)に居ても居なくてもよい。
  3. ホスト(host)の中から1つだけHDD装置(device)を選択する。

RADOS は新しいオブジェクトの配置位置をルールセットに従って CRUSH アルゴリズムを動かして決める(実際はオブジェクト単位ではなく Placement Group 単位に決める)。 その結果、同一の列(raw)内にある別々のホスト(host)に3つのレプリカがとられるはずである。

このルールセットは CRUSH マップに記載するが、この記述は手動である。 ユーザーが良く考えて決める必要がある。 RADOS が最適化されるかどうかは CRUSH マップの構成方法にかかっていると言ってよい。

バケット(Bucket)

実機の Ceph システムの階層化された構造を CRUSH マップとして示すために バケット(Bucket) と呼ぶデータ構造が導入されている。

Bucket は入り口を1つ出口を複数持つデータ構造である。 出口の部分をアイテム(Item)と呼ぶ。 Bucket は item によって別の bucket または最終ゴールである OSD (なぜか CRUSH マップでは device と呼ばれる) につなげる。

Bucket

CRUSH マップの書き方は「Ceph の CRUSH マップの書き方」を参考のこと。

Bucket の種類

CRUSH マップは運用中に変更することができるが、Item の追加・削除に伴い リウェイト(reweight) が必要になる。 この時、酷い場合には大量のオブジェクト移動が、うまくいけば最小のオブジェクトの移動が発生する。

これを防ぐために CRUSH は bucket 毎にハッシュアルゴリズムを uniformlisttreestraw の 4 つから選択できるようになっている。 説明を端よると uniform は constant hash で straw は consistent hash である。

Bucket の種類によって以下のような特性の違いがあるようだ。

 UniformListTreeStraw
オブジェクト割り付けコストO(1)O(n)O(log n)O(n)
ノード追加pooroptimalgoodoptimal
ノード削除poorpoorgoodoptimal

ところで ceph のデフォルトは straw である。 オブジェクトの割り当てが遅いのは、次に述べる placement group の機構で概ね解決している。 そのため基本的には straw だけを使っていればよい。

Bucket の種類に関しては惨たらしい用語の混乱が見受けられる。 CRUSH の論文 によると bucket には 2 系統の type が存在しているのだ。
一つは item の選択方法をしめす type (uniform/list/tree/straw) で、これは CRUSH マップ中では alg と呼ばれている。
もう一つは CRUSH 中の階層を示すために bucket に与えられる type (root/raw/rack/host) である。これは CRUSH マップ中で type と呼ばれている。
alg は RADOS にビルトインされた type で、typedevice 以外は勝手に CRUSH マップ中で勝手に命名してもよいルールセット記述用の type である。
type と kind とか言い分ければいいのにと切に思う。

Bucket が実際にどのようにオブジェクトを割り付けるかはマッピングアルゴリズム(Mapping Algorithm)によるが、これは5. Mapping Algorithmを参照。

OSD の過負荷(overload)と残空き容量

CRUSH は OSD の容量を考慮せずに OSD リストの選択を行う。 これを防ぐには容量に応じて bucket 定義内の item の重み付け(weight)を設定する。 weight の設定方法は「Ceph の CRUSH マップの書き方」を参考のこと。

オブジェクトの分散の仕方によっては特定の OSD の空き容量がなくなってしまうことがある。 この場合、RADOS は空き容量のある OSD にオブジェクトを移動するような処理をしない。 そのため RADOS 全体では空き容量が残っているのに、特定の OSD の空き容量がないためにオブジェクトへの PUT が失敗することがある。 RADOS をベースにした分散ファイルシステムである ceph の場合、ENOSPC エラー(No space)として顕在化する。

ただし ceph や RBD は 4MB 単位でデータを分割して別々のオブジェクトとする wide striping を行っているため、OSD 間にオブジェクトが極端に片寄らないことは期待できる。

特定の OSD が過負荷になった場合の処理に関しては、CRUSH の論文によると OSD リストの再選択が行われて負荷の分散が行われるような記述がある。 ただし実際に ceph を動作させている分には、この機能が働いているようにはみえない。

4. Placement Group

本来 n 台の OSD からレプリケーション多重度 m の設定で配置位置を決める場合、その組み合わせは nCm となる(C は Combination)。 ただし RADOS のレプリカ間には優先順位が付くので、実際の組み合わせは nPm となる(P は Permutation)。 例えば 100 台の OSD から多重度 3 を考えると 100P3 = 100×99×98 = 970,200 通りとなる。

OSD の追加・削除・停止時には OSD リストを変更しオブジェクトを OSD 間で移動(reweight)する必要があるが、あまり組み合わせが多いとやっかいだ。 RADOS としては格納するオブジェクトが各 OSD に分散して配置されればよく、可能な全ての組み合わせがとれる必要はない。 そこで RADOS はレプリカ配置がとりえる OSD リストをあらかじめ制限し、これを Placement Group(PG) と呼んでいる。

PG はプール毎に別々に存在する。 プールが作成される時に OSD 数の 100 倍程度の値が自動的に設定される。 各 PG は自身の番号を元に CRUSH アルゴリズムを適用して、レプリカ配置位置となる OSD リストにマッピングされる。 PG 数は運用中、運用中に変えることはできるが、基本的には変えない。

Placement Group を確認する

PG の内容を調べるには以下のようにコマンド入力すればよい。 9 台の OSD に多重度 2 のレプリカを実行した結果である。

# ceph pg dump
...snip...
pg_stat objects mip     degr    unf     kb      bytes   log     disklog state   v       reported        up      acting  last_scrub
2.1p3   0       0       0       0       0       0       0       active+clean    0'0     3'8     [3,4]   [3,4]   0'0     2012-02-06 20:24:55.717844
2.0p2   0       0       0       0       0       0       0       active+clean    0'0     3'8     [2,8]   [2,8]   0'0     2012-02-06 20:22:32.704238
1.0p1   0       0       0       0       0       0       0       active+clean    0'0     3'8     [1,5]   [1,5]   0'0     2012-02-06 20:18:51.683999
1.1p0   0       0       0       0       0       0       0       active+clean    0'0     3'8     [0,8]   [0,8]   0'0     2012-02-06 20:21:39.698837
0.0p0   0       0       0       0       0       0       0       active+clean    0'0     3'8     [0,9]   [0,9]   0'0     2012-02-06 20:14:21.656730
0.1p1   0       0       0       0       0       0       0       active+clean    0'0     3'8     [1,5]   [1,5]   0'0     2012-02-06 20:12:01.643749
2.0p3   0       0       0       0       0       0       0       active+clean    0'0     3'8     [3,8]   [3,8]   0'0     2012-02-06 20:24:52.717523
2.1p2   0       0       0       0       0       0       0       active+clean    0'0     3'8     [2,4]   [2,4]   0'0     2012-02-06 20:22:34.704490
1.1p1   0       0       0       0       0       0       0       active+clean    0'0     3'8     [1,8]   [1,8]   0'0     2012-02-06 20:18:52.684132
1.0p0   0       0       0       0       0       0       0       active+clean    0'0     3'8     [0,5]   [0,5]   0'0     2012-02-06 20:21:17.696717
0.1p0   0       0       0       0       0       0       0       active+clean    0'0     3'8     [0,5]   [0,5]   0'0     2012-02-06 20:14:22.656889
...

各行が PG をあらわし、最初の pg_stat のカラムの (pool番号).(PG番号) が PG のラベルとなる。 0.* は ceph ファイルシステムの「データ」用、1.* は ceph ファイルシステムの「メタデータ」用、2.* は RBD 用の PG となる。

各行の右側にある [x,y] が PG がマップされた OSD のリストである。 最初に表示された 2.1p3[3,4] とありプライマリレプリカは osd3 に、セカンダリーレプリカは osd4 に配置されたことが分かる。 多重度 2 なので [x,y] だが、多重度上がると [x,y,z] のように増えてゆく。

PG の OSD リストは CRUSH によってある程度ランダムに決まるので、同一のプールに属する異なる PG が同じ OSD リストにマップされることはある。 極端な例を出すと OSD が 2 台で、多重度が 2 なら [0,1][1,0] しか組み合わせがないが、OSD が 2 台なら PG が 200 程度できるので、PG は [0,1][1,0] の 2 パターンをランダムに繰り返すことになる。 逆に OSD の数が増えると、とりえる OSD リストの数が増えて、PG の中に [1, 2, 3] がない! と言った風になる。

オブジェクトを Placement Group に割り当てる

オブジェクトが RADOS に格納される時に、オブジェクト名をハッシュ関数にかけてハッシュ値を求める。 これがオブジェクトIDとなる。 このオブジェクトIDを単純に PG 数で割って剰余をとる。 剰余値が PG の番号となり、その PG の OSD リストがオブジェクトの配置位置になる。

PGの選択

Ceph ファイルシステムの場合は少し違い、ファイルは 4MB 単位のブロックがオブジェクトになる。 これには i-node 番号とブロック番号(ブロックのファイル内でのオフセットをブロック長(4MB)で割った値)を元にオブジェクトIDを作っている。 オブジェクト ID が Placement Group に割り当てられるのは変わらない。

RADOS がオブジェクトの検索する際に、CRUSH アルゴリズムを使って PG 番号から OSD リストを毎回計算しているか、それとも PG 毎の OSD リストをあらかじめ記憶しおいてそれを使っているのかは不明。 RADOS がオブジェクトの検索する際には、CRUSH アルゴリズムを使って PG 番号から OSD リストを計算するが、その結果をキャッシュしているようだ。

5. Mapping Algorithm

すでに説明したように CRUSH はオブジェクトごとではなく PG ごとに OSD への割り当てを決める。 そのため各 bucket は与えられた PG 番号(PG_ID) を、bucket の下に出ているどの item にマッピングするかが問題になる。

CRUSH のマッピングは概念的には crush_bucket_choose(crush_bucket, pg_id, r) という関数であらわされる。 この関数の戻り値が item 番号として返ってくる。

同一の PG 番号に対して複数のレプリケーションを用意する場合には入力 r を使う。 レプリケーションの多重度に応じて r を 0、1、2、… と変えていけば、pg_id が同じでも違う item 番号が出てくる。 ただ r が違っても同じ item 番号が返ってくることがあるので、その場合は多重度分の item がそろうまで r++ していくしかない。

ここでもう一度 CRUSH マップの中の bucket の書き方 を見てもらう。

# buckets
rack unknownrack {
	id -1		# do not change unnecessarily
	# weight 11.000
	alg straw
	hash 0	# rjenkins1
	item host1 weight 4.000
	item host2 weight 4.000
	item osd.0 weight 1.000
	item osd.1 weight 1.000
	item osd.2 weight 1.000
}

この bucket は下図のようになる。

Bucket

実際のマッピングアルゴリズムはBucket の種類によって異なるので、順に紹介してゆく。 しかし先に結論を言っておくと straw bucket は素晴らしく、これ以外を選択する理由はない。

ハッシュ関数

CRUSH を理解する上で重要なのは、CRUSH が多入力ハッシュ関数を使っている点である。

Jenkins のハッシュ関数と呼ばれるマルチバイトのキーをハッシュ化するアルゴリズムがあり、引数が 2 個以上のハッシュ関数を簡単に作れる。

CRUSH は bucket の hash の項が 0 なら Jenkins のハッシュ関数を使う。 というか hash が 0 以外のハッシュアルゴリズムは用意されていない。

#define crush_hash_seed 1315423911

#define crush_hashmix(a, b, c) do {			\
		a = a-b;  a = a-c;  a = a^(c >> 13);	\
		b = b-c;  b = b-a;  b = b^(a << 8);	\
		c = c-a;  c = c-b;  c = c^(b >> 13);	\
		a = a-b;  a = a-c;  a = a^(c >> 12);	\
		b = b-c;  b = b-a;  b = b^(a << 16);	\
		c = c-a;  c = c-b;  c = c^(b >> 5);	\
		a = a-b;  a = a-c;  a = a^(c >> 3);	\
		b = b-c;  b = b-a;  b = b^(a << 10);	\
		c = c-a;  c = c-b;  c = c^(b >> 15);	\
	} while (0)

static uint32_t crush_hash32_rjenkins1_3(uint32_t a, uint32_t b, uint32_t c)
{
	uint32_t hash = crush_hash_seed ^ a ^ b ^ c;
	uint32_t x = 231232;
	uint32_t y = 1232;
	crush_hashmix(a, b, hash);
	crush_hashmix(c, x, hash);
	crush_hashmix(y, a, hash);
	crush_hashmix(b, x, hash);
	crush_hashmix(y, c, hash);
	return hash;
}

static uint32_t crush_hash32_rjenkins1_4(uint32_t a, uint32_t b, uint32_t c, uint32_t d)
{
	uint32_t hash = crush_hash_seed ^ a ^ b ^ c ^ d;
	uint32_t x = 231232;
	uint32_t y = 1232;
	crush_hashmix(a, b, hash);
	crush_hashmix(c, d, hash);
	crush_hashmix(a, x, hash);
	crush_hashmix(y, b, hash);
	crush_hashmix(c, x, hash);
	crush_hashmix(y, d, hash);
	return hash;
}

ストローバケット(Straw Bucket)

Straw bucketdrawing straws のロジックでマッピングする item を選択する。 Drawing straws は「複数の藁を表に出ている部分が等しくなるように手で隠し持って、順番に引かせて一番長いのを引いた人が勝ち」というイメージのアルゴリズムである。 この場合、bucket の下についている item が藁を引く人で、長さの違う藁はハッシュ値となる。

Straw bucket は接続されている全ての item に対して、pg_id と r と item 番号を使ってハッシュ値を計算する。 だから straw bucket の下に 100 個 item があれば、100 個ハッシュ値ができることになる。 この 100 個のうち最大の値の item が選択される。

Straw bucket で使うハッシュ関数は 3 引数の Jenkins ハッシュ関数を使う。 crush_hash32_rjenkins1_3(pg_id, item_id, r) を計算し、最後の下位 16 ビットだけを取り出す(上位 16 ビットは捨てる)。 下位 16 ビットだけを使うのは、後でハッシュ値に重みを掛ける際に 32 ビットに収めるためだと思われる。

この条件で PG 番号の 0〜9 に関してハッシュ値を計算したの下の表になる。 ここではプライマリーレプリカだけを計算しているつもりなので r には 0 を指定する。

  pg_id=0 pg_id=1 pg_id=2 pg_id=3 pg_id=4 pg_id=5 pg_id=6 pg_id=7 pg_id=8 pg_id=9
item=0 62386 28542 44565 60963 21810 37274 1173 21461 47 3222
item=1 28691 10905 54092 37545 32692 22271 8163 49672 32505 4972
item=2 32439 19538 17678 33041 31391 24439 32687 43965 63252 45574
item=3 43321 48894 33574 38061 29187 62656 30270 28102 40183 4646

Straw bucket に 3 台の OSD がぶら下がっている場合、item 番号は 0、1、2 となる。 この時、各 PG 番号(列)で一番大きいハッシュ値を赤字で示してみた。 この PG 番号ではこの赤字の出た行がマッピングされたことになる。 つまり PG 番号 0、1、3、5 は item 0 に、PG 番号 2、4、7 は item 1 に、PG 番号 6、8、9 は item 2 にマッピングされる。

もしこの bucket に 4 台目の OSD が加わり、item 3 が増えると表の最下段の1行が加わったことになる。 このうち青字で示した PG 番号 1、5 は、古い item 0 〜 2 のハッシュ値よりも大きい。 そのためマッピングが変わり、PG 番号 1、5 の PG に含まれていたオブジェクトが、item 3 へリマップされる。

これが RADOS のリバランスになる。 新しい OSD を追加した場合、全体容量が均等になるように古い OSD から新しい OSD へオブジェクトが移動されるが、この例では PG 番号 1 と 5 に入っていたオブジェクトが移動するのである。 また OSD が削除する場合も、残った OSD の中で一番長い藁を持つ OSD へ移動する。これもオブジェクトの移動量が最小となる。

また item には重み(item_weight)を指定できる。 藁の比較は (crush_hash32_rjenkins1_3(pg_id, items[i], r) & 0xFFFF) * item_weights[i] のように重みをつけるので、ある item にオブジェクトが集まりやすくすることや、逆に避けることも可能だ。

もし item の重みを変更した場合もオブジェクトの移動が発生するが、これも必要最小限であることが類推できる。

また straw bucket は items[] の並びをかえてもほとんど影響がない(最大値のハッシュ値が複数あった場合は items[] の並びが若い方が優先される)。 ハッシュ値を item 番号から決めているので、CRUSH マップ中の item の並びを変え items[] = {0, 1, 2} から items[] = {1, 2, 0} へ変更してもマッピングはほとんど変わらない。

Straw bucket は優れたアルゴリズムだが、bucket 内の全ての item に対してハッシュを計算を必要があるのが重い。 単一の straw bucket に下に OSD(ディスク) を数百〜数千ぶら下げると crush_bucket_choose の呼び出しコストが上がる。

リストバケット(List Bucket)

List bucket は重み(weight)が重要である。 各 item は重み(item_weight)のパラメータを持っている。 確率的には item は (その item の item_weight) / (全 item の items_weights の合計) だけ PG がマッピングされる。

List bucket は CRUSH マップの構成時に item_weithg を累積した sum_weights を作っておく。 下の表は例である。 例では item=2 以外の item_weight は 1.0 で、item=2 だけ他と変えて 0.5 とする。

  item=0 item=1 item=2 item=3
item_weight 1.0 1.0 0.5 1.0
sum_weights 1.0 2.0 2.5 3.5

List bucket に PG 番号をマッピングする場合、以下のような処理を行う。

まず list bucket 内の最後の item から Jenkins ハッシュ関数を使い crush_hash32_rjenkins1_3(pg_id, item_id, r) を計算する(実際は下位 16 ビットだけ使う)。 これに sum_weights[last] を掛けたものが、item_weights[last] よりも小さければ、この item が採用される。

以降、最後の item からひとずつ前に戻っていき、ハッシュ値に sum_weights[i] を掛けたものが item_weights[i] よりも小さくなる item を探して行く。 最後に item 1 がダメなら、無条件で item 0 が採用される。

擬似コードを書くと以下のようになる。 ハッシュ関数は 0 以上 1 未満の小数を返す疑似乱数として使われているのが見て取れる。

int bucket_list_choose(bucket, pg_id, r)
{
    int size = (bucket 内の item 数);

    for (int i = size - 1; i > 0; i--) {
        uint64_t w = crush_hash32_rjenkins1_3(pg_id, bucket->items[i], r);
        w &= 0xffff;
        w *= bucket->sum_weights[i];
        w = w >> 16;
        if (w < bucket->item_weights[i])
            return bucket->items[i];
        }
    }

    return bucket->items[0]; // 当てはまるものがない
}

sum_weights は自分以下の番号の item_weight の累積なので、i が大きくなるほど sum_weights[i] は大きくなる。 そのため i が大きい時はハッシュ値に sum_weights[i] をかけたものは item_weights[i] 未満にはなりにくい。 結局、ハッシュ関数が十分に均等なハッシュ値を返すなら、各 item には item_weight の重み通りの出現率になるはずである。

List bucket に新しい item を挿入するのは簡単である。 最後に 1 列足してやればよい。 新しく追加した item に古い item から PG 番号が移動することになる。 一番最後に追加した item が最初にハッシュ値比較を行い、一部の PG が新しい item へリマッピングされる。

  item_id=0 item_id=1 item_id=2 item_id=3 item=4
item_weights 1.0 1.0 0.5 1.0 1.0
sum_weights 1.0 2.0 2.5 3.5 4.5

一方、item の削除は意外な影響を与える。 途中の item が抜けると以降の sum_weights[] が変わるからだ。 たとえば item=1 が抜けると sum_weights[]赤字の部分が変わる。

  item_id=0 item_id=2 item_id=3 item_id=4
item_weights 1.0 0.5 1.0 1.0
sum_weights 1.0 1.5 2.5 3.5

item_id=1 が抜けた結果、item_id=1 に割り当てられた PG が別の item に移動するのは当然である。 しかし残った item 間で PG のマッピングの移動が起きると、それは無駄なオブジェクトの移動が発生するということである。 例えば item_id=4 の sum_weights[] は 4.5 だったのに、item_id=1 が取り除かれたことで 3.5 になった。 そのため、これまで item_id=0、2、3 にマップされた PG が item_id=4 にリマップされるという事態が発生する。

List bucket は重み(item_weight)を変えた場合も、同様に不要なオブジェクト移動が発生する可能性がある。 また straw bucket では items[] 中の item の並びはマッピングに影響しなかった。 しかし list bucket では items[] = {0, 1, 2}items[] = {1, 2, 0} では結果がかなり違う。

また bucket_list_choose は処理コストがバラバラである。 ループの 1 回目の繰り返しで決まることもあれば、最悪の場合は全 item 分のループを回すことになる。 これもデメリットであろう。

ツリーバケット(Tree Bucket)

Tree bucket は list bucket の弱点を改良して作られたのではないかと予想する。 List bucket は最後の item から最初の item へ順にハッシュ値を比較して行ったが、tree bucket は 2 分木を作って、根から初めて右・左を決めながら葉に向けて降りて行き最後にある item を選択する。

Tree bucket は item がすっぽり覆える 2 分木を作る。 つまり 2N-2 < (item 数) <= 2N-1 を探して N 段の 2 分木を構成する。 2 分木といっても、ノードをポインタで結んで作ったデータ構造にすると操作が大変である。 2 分木ヒープ のように、フラットな配列を木構造に見做すやり方を採用する。

そのやり方だが、まず item 数が 8 ならその倍の 16 の要素数の配列を用意する。

2分木

これを以下のように 2 分木に見立てる。 item は配列の奇数要素が担当する。 奇数は (奇数)*20 とかけるので、これを 0 段目とみなす。 次の 1 段目が (奇数)*21、2 段目が (奇数)*22、3 段目が (奇数)*23 と並べてゆく。 0 は使わない。

根から葉へ木構造を下りてゆくには左右の子ノードを求める必要がある。 これは自分の段数を計算して、その後に自分自身のノード番号に 2一つ下の段数 を引いた左の子ノードで、2一つ下の段数 を足したのが右の子ノードとなる。 たとえば最上段は最初の item 数である 8 となる。 これは 3 段目のノードで 1 * 23 なるので、8 の左の子ノードは 8 - 22 = 4 で、右の子ノードは8 + 22 = 12 になる。 同様に 12 の左の子ノードは 12 + 21 = 10 で右の子ノードは 12 + 21 = 14 となる。

2分木

段数を調べるには、ノード番号を二進数であらわす。 使用数字から 0 を除いており、奇数に 2 のべき乗を掛けているので、最下位ビットから 0 がいくつ続くかを数えると段数が分かる。

xxxx1000(奇数)×23
xxxxx100(奇数)×22
xxxxxx10(奇数)×21
xxxxxxx1(奇数)×20

これで 2 分木データの準備が整った。 後は item の重み(weight)を木構造の葉から根に向けて足してゆく。 逆に言うと各ノードはそれよりも下にある item の重みを合計してゆく。 これが node_weights[n] となる。 n は item 番号ではなく、2 分木のノード番号。

Tree bucket では、木構造の各ノードで (crush_hash32_rjenkins1_4(pg_id, n, r, bucket_id) * node_weights[n]) >> 32 を計算し、それを左の子ノードの node_weights[left_child] よりも小さければ左の子ノードを選択し、そうでなければ右の子ノードを選択する。 ハッシュ関数は 0 以上 1 未満の小数を返す疑似乱数として使われているのが見て取れる。 根のノードなら node_weights[8] は 11.0 である。 11.0 * dran48() < 5.0 のようなチョイスをしたことになる。

Straw bucket と list bucket はハッシュ関数の結果の下位 16 ビットだけを使っていたが、tree bucket では 32 ビット全体を使っている。 このあたりの設計意図はよく分からない。

この選択を根ノードから葉ノードにたどり着くまで繰り返す。 葉ノードは n が奇数番号のノードで、それぞれ葉ノードの担当する item へマッピングする。

Straw bucket と list bucket では 3 引数の Jenkins ハッシュ関数だったが、tree bucket では 4 引数である。 増えたのは bucket_id で、これは tree bucket 自体の item_id を使う。 Straw bucket と list bucket は bucket の下にぶら下がっている item の item 番号を使っていた。 これは CRUSH マップ中で一意性がある値である。 一方、tree bucket はノード番号を使うため、これは木構造の段数が同じだとほぼ同じハッシュ値を返すことになってしまう。 そこで tree bucket 自身の item 番号を加えている。

item の数が 2 のべき乗にならない場合は配列を左詰めで使う。 item がないノードは重み(weight) を 0 とする。 重みが 0 ならハッシュ値に node_weights[i] を掛けると 0 になって、その子ノードは選択されなくなる。

この方法で item を追加するには、2N になるまでは配列の右側のあまり部分を埋めてゆけばよい。 2N を越えた場合は、配列サイズを 2N+1 に拡張する。

逆に item を削除する場合は、items[] の該当部分に穴をあけることになる。 削除した item のノード(段数 0 の奇数ノード)から親ノードに向かって item_weigths[deleted_item] だけ node_weights[] を減少させてゆく。

このようなロジックのため、straw bucket や list bucket が item 追加に対して完全なリバランスを見せるのに対し、tree bucket の item 追加はほどほどに良いが完全ではない。 一方、list bucket はノードを削除した場合に不必要なリマッピングが発生するが、tree bucket はノード削除でもノード追加と同様にほどほどに良いが結果が得られる。

ユニフォームバケット(Uniform Bucket)

プライマリーレプリカ(r=0)のマッピングだけ大雑把に説明すると、以下のような擬似コードであらわせる。 ハッシュ値を bucket に繋がっている item 数で割って余りを使う。

int bucket_uniform_choose(bucket, pg_id, r)
{
    unsigned s;
    s = crush_hash32_rjenkins1_3(pg_id, item_id, bucket_id) % bucket->size;
    return bucket->items[s];
}

Uniform bucket はハッシュ関数に item 番号を渡さない唯一の bucket である。 Item の重みも選択に反映されない。

と見るべきところがないので、uniform bucket を使う局面はないだろう。

コメント

コメントを書き込む

TOP    掲示板    戻る
Written by NAKAMURA Minoru, Email: nminoru atmark nminoru dot jp, Twitter:@nminoru_jp