Cephがスケールできる理由、単一障害点を排除する仕組み、負荷を減らす実装：Ceph/RADOS入門（4）（3/4 ページ）

Ceph／RADOS が採用しているCRUSH、Paxosといった、分散したデータから正しく応答するための仕組みを支えるアルゴリズムの概要を学びながら、挙動を見ていきます。

[佐藤友昭，VA Linux Systemsジャパン]

CRUSHアルゴリズム（3）「バケットリスト」「ルールリスト」とマッピング

　PG番号とOSDのマッピングはCRUSHマップを用いて行われます。CRUSHマップはバケット（buckets）とルールのリストで構成されます。バケットはルールから参照され、ルールはルール番号でプールの属性として設定されます。

　ここでは「Ceph Storage Clusterの構築」においてceph-deployで構築した環境の、デフォルトで生成されたCRUSHマップから、バケットリストとルールリストの部分を示します。

　CRUSHマップの参照方法はCeph Documentsの「CRUSH Maps」のページなどを参照してください。

バケットリストの例(抜粋)：2台のホストにそれぞれOSDが1個の構成の場合

#rules
rule data{
    ruleset 0
    type replicated
    min_size 1
    max_size 10
    step take default
    step chooseleaf firstn 0 type host
    step emit
}
rule metadata{
    ruleset 1
    type replicated
    min_size 1
    max_size 10
    step take default
    step chooseleaf firstn 0 type host
    step emit
}
rule rdb{
    ruleset 2
    type replicated
    min_size 1
    max_size 10
    step take default
    step chooseleaf firstn 0 type host
    step emit
}

デフォルトのルールリスト（一部抜粋）

「バケット」の階層構造を使ってスケールする仕組み、冗長化の仕掛け

　1つのバケットは1つの入り口と複数の出口を持ち、各出口をアイテム（item）と呼びます。アイテムはアイテム番号で特定します。複数のバケットで階層構造を作ります。

　上の図の例では、一番上がホストのバケットになり、中間のアイテムはホストごとのOSDのバケットになり、一番下のアイテムが個々のOSDになります。Ceph/RADOSでは、PG番号をアイテム番号にマップしながらバケットの階層構造を下っていくことでOSDを特定します。

　この例ではOSDのバケット（head-01、head-02）とホストのバケット（default）の2階層だけですが、システムの規模が大きくなるにつれ、サーバーラックのバケット、ラック列のバケット、マシンルームのバケット、データセンターのバケット、……という具合に、システム管理者がCRUSHマップを編集して、階層の数を増やしていくことができます。

　具体的なCRUSHマップの編集方法はここでは言及しませんので、Ceph Documentsの「CRUSH Maps」のページなどを参照してください。

　あるオブジェクトとそのレプリカを格納するOSDアイテムは、冗長性を保つために異なるバケットから選択します。こうすることで、故障ドメイン（ハードウェア故障の影響範囲。例えばある電源系列やネットワークスイッチなどがダウンした場合の影響範囲）を考慮してバケットの階層構造を定義でき、データの安全性を高めることができます。

選択できるバケットの種類と使い分け方

　バケットを定義する際には、バケットタイプを以下から選択できます。

• Uniformバケット
• Listバケット
• Tree バケット
• Straw バケット

　Sage Weil氏の論文「CEPH: RELIABLE, SCALABLE, AND HIGH-PERFORMANCE DISTRIBUTED STORAGE」*では、バケットが固定的である環境ではUniformバケットの使用が、バケットが伸長する一方の環境ではListバケットの使用が、アイテム削除があってその際のリバランスの影響が深刻な環境ではStrawバケットの使用がそれぞれ向いており、Treeバケットは総合的な折衷（all around compromise）と紹介されています。

　デフォルトで生成されたCRUSHマップではStrawバケットが選択されています。Strawバケットでは、「ストローくじ（drawing straws）」のように**、Jenkinsハッシュ関数の引数に、PG番号、アイテム番号、レプリカ番号（0、1、2、…、N）を与えた結果が最大となるようなアイテム番号を選択します。Nはオブジェクト冗長度です。

* Sage Weil「CEPH: RELIABLE, SCALABLE, AND HIGH-PERFORMANCE DISTRIBUTED STORAGE」(Dec, 2007)。（リンクはPDF）

ストローくじ（出典：HowWiki「How to Draw Straw」）

**ストローくじ　複数本のストローの一端を隠して一人ずつ引いていき、短いストローを引いた人が「当たり」となるくじのこと。CRUSHのStrawバケットの場合は長さに相当する値はばらばらですが、最も長いものを「当たり」とします。アイテム数によって長さに相当する値は増減しますが、一番長いものが変わらなければ、オブジェクトを移動する必要がない点がメリットとなります。

　OSDノードにOSDを追加したり、OSDノードを追加することを「アイテム（item）の追加」といいます。逆にOSDやOSDノードを削除することを「アイテムの削除」といいます。

　ここで、アイテムが追加・削除された結果、ハッシュアルゴリズムで選択されるアイテム番号が変化する場合と変化しない場合があります。選択されるアイテム番号が変化するオブジェクトは旧アイテムから新アイテムに移動させる必要があります。これを「リバランス」といいます。

　Strawバケットでは、Jenkinsハッシュ関数の結果が変化しても一番大きなアイテムが変化しなければリバランスが発生しません。このことから、単純なハッシュアルゴリズムで作成したバケット（Uniformバケット）に比べてリバランスが少なくて済むメリットがあります。

アイテム追加前後でのリバランスの様子。出典：http://ceph.com/docs/master/architecture/（抜粋）