追記型オブジェクトストレージ「Kastor」（pre-alpha）

Facebookで写真配信のために使われているストレージシステム「Haystack」に関する情報が公開されました。（Needle in a haystack: efficient storage of billions of photos）

Facebookは最初はNFSを使っていたようです。しかし写真の1枚1枚をファイルとして保存していたため、ディレクトリエントリなどのinodeメタデータの総量がキャッシュに収まらないサイズになってしまい、一つの写真を保存したり取り出したりするのにHDDのシークが複数回発生していたのがボトルネックになっていたそうです。


（もしかしたら「NetAppは高すぎた」のがもっと重要だったかも知れません：Facebook、独自の写真配信ネットワーク、Haystackを完成―収益性の改善に寄与か？）

シークの問題を軽減するために、profile用などの小さな写真はキャッシュしたり、NFSのfile handleをキャッシュするキャッシュする階層を挟んだりもしたようです。


…などなどの問題を踏まえて、Haystackはできる限りHDDを1回シークするだけで写真を保存したり取り出したりできるように設計されています。

と、詳しい設計については本家の情報を読んでいただくとして、私もHaystackに似た追記型のオブジェクトストレージ Kastor を実装してみたので紹介します。


※2009-06-27 追記：ソースコードをgithubに置いてみました：http://github.com/frsyuki/kastor/tree/master

概要

Kastorは写真などの少し大きめのデータで、一度保存したらほとんど更新も削除もしないデータを大量に扱うのに適したkey-valueストレージです。HTTP の GET と PUT を使って読み書きができます。

なお品質はα版以前で、使い物にはならないので注意してください ^^;)　レプリケーションやcompactionなどの超重要な機能も実装されていません。
主に現在開発中のクラスタアプリケーションを書くためのフレームワーク（ccf; Cluster Communication Framework）の使い勝手を評価するために開発しました。

Kastorのアーキテクチャ

Kastorは実際にデータを保存していくベクタストレージと、ベクタストレージの中のどこにデータが保存されているかを示すインデックスの2つでストレージを構成します。
インデックスはできるだけ小さくし、すべてメモリに載るようにします。



データを保存するときは、まずベクタストレージにデータ本体を「追記」し、その書き込んだオフセットとサイズをインデックスに書き込みます。
読み込むときはインデックスを参照してオフセットとサイズを取得します。
削除はできません ^^;)


I/O戦略にはWavyアーキテクチャを採用しています。

Kastorの特徴

Kastorの実装はできるだけコピーをしないようになっている点と、ロック･フリーで並列性が高い点が特徴です。

Kastorのストレージには次の4つのAPIがあります：

block* balloc(size);       // sizeバイトの領域をベクタストレージの末尾に確保する
void bfree(block*);        // そのblock*はもう使わない宣言
void update(key, block*);  // インデックスを更新してkeyに対応するブロックをblock*にする
block* search(key);        // keyに対応するblock*を得る

blockにはオフセットとサイズ（とファイルディスクリプタ）が入っています。


データを書き込む手順は次のようになります：

  1. ベクタストレージの末尾にデータを領域を確保する（balloc）
  2. 確保した領域をmmap(2)する
  3. mmapした領域に向かってクライアントからデータを受け取る
  4. インデックスを書き換える（update）

balloc()の操作はほとんどの場合「ここまで使用済みだよ」という変数を（アトミックに）増やすだけなので、瞬時に終わります。
こうして確保した領域に、クライアントから受け取ったデータを直接書き込んでいきます。これでブロックができあがったので、最後にupdate()操作でインデックスを書き換えて、keyが指す先を（アトミックに）張り替えるというわけです。


一方、データを読み込む手順はこうなります：

  1. 要求されたkeyに対応するブロックを得る（search）
  2. クライアントにsendfile(2)する

search()の操作はインデックスからkeyを探し出すだけで、実際にデータを読み込んだりはしません（事実blockにバッファは入っていません）
クライアントにデータを送るときはsendfile(2)システムコールを使って、カーネル空間から直接ソケットにデータを送信します。


普通にread(2)してwrite(2)する方法と比べると↓このような違いがあります。



mmap(2)やsendfile(2)を使う方法は、read(2)してwrite(2)する方法よりもコピーの回数が減っていることが分かります。
ベンチマークテストしていないので全然ダメなのですが、たぶんおそらく速いハズです ^^;)

まとめ

というわけで Facebook の Haystack に似た追記型のオブジェクトストレージを実装してみました。ソースコードはここからダウンロードできます。
compactionやレプリケーションなどの重要な機能が欠けていますが、今後実装する予定はあまりなくて^^; 「こんなアーキテクチャどうですか」という提案です。
大きめのデータを扱いたいけどNFSはイケてない…という局面はよくあるかなーと思いますがどうでしょうか。