CephのCRUSHはストレージを検索するのではなく計算で見つけた

大規模な分散ファイルシステムは伝統的に、各ブロックやオブジェクトがどこに存在するかを示すメタデータを必要としていた。ペタバイト規模では、そうした割り当てマップが調整、復旧、再バランスの問題となった。

Cephの答えはCRUSHだった。疑似ランダム配置関数である。クライアントとストレージノードは、中央のテーブルに問い合わせる代わりに、オブジェクト名とクラスタマップからオブジェクトの位置を計算できた。

OSDI論文は、Cephが毎秒25万回以上のメタデータ操作をサポートしたと報告し、CRUSHの論文は、中央ディレクトリを避けつつ数万から数十万のストレージデバイスを対象とするアルゴリズムとして位置づけられた。

配置を関数に変えた

決定的な配置関数により、すべての参加者が独立して同じオブジェクトを見つけられる。

重みと故障ドメインのルールは、ラックやデバイスサイズといった現実世界の制約を保持する。

小さなトポロジ変更では、移動が必要なデータだけが移動するため、拡張や故障による影響が小さくなる。

割り当てリストをなくすことで、メタデータサーバの役割はすべてのバイトのアドレスではなく、名前空間へと縮小する。

極端な規模では、調整を最適化するよりも調整を削除する方が重要になり得る。共有された決定的な関数が、共有された可変ディレクトリを置き換えられる。

CRUSHはCephを代表するアイデアの一つとなり、このプロジェクトを持続的なオープンソースストレージシステムにする一助となった。その美しさはアーキテクチャにある。ペタバイト規模で最良のディレクトリとは、ディレクトリが存在しないことだった。