mixi engineer blog

＊＊＊ 引っ越しました。最新の情報はこちら → https://medium.com/mixi-developers ＊＊＊ ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

DBMによるデータベースサーバ

mixi

DSのスターフォックスというゲームにはまりまくりのmikioです。最近社内外で「俺ストレージサーバ」を作るのが流行っているようなので私も参戦してみました。今回はDBMのネットワーク層をほぼスクラッチで作った話をします。

Tokyo Tyrant

Tokyo Tyrant（以下TT）はTokyo Cabinet（以下TC）をラップしてネットワーク越しに操作できるようにするツールです。キャビネット（内閣）を傀儡にするタイラント（僭主）ということで名付けました。ダウンロードはこちら。

TCは高性能なDBMで、マルチスレッドモデルで高い並列性を実現していますが、逆にマルチプロセスモデルだとファイルロックがかかるので並列性が低くなってしまいます。つまり、書き込みモードでデータベースにアクセスしているプロセスがいると、その間は他のプロセスがデータベースに接続しようとするとブロックされることになります。また、DBMはローカルファイルシステムにあるデータベースファイルに接続するものなので、高速である反面、リモートホストからデータベースを直接操作することができないという制限もあります。

そこでTTの登場です。内部にTCを抱えたネットワークサーバと、それにアクセスするためのライブラリをパッケージにしたものです。サーバとクライアントは独自のバイナリプロトコルで通信します。それによって、同一または複数のマシンで動作する複数のプロセスがデータベースを同時に操作できるようになります。サーバ内ではマルチスレッドで複数のセッションを同時実行するので、クライアントが特に気にしなくても並列性を確保できます。処理ごとにデータベースを開いたり閉じたりしないからキャッシュが有効活用されるのも利点ですね。

tt_dbm.png

サーバ側でTCを扱う際には、TCの「抽象データベースAPI」を用います。これはTCMDB（オンメモリハッシュデータベース）とTCHDB（ファイルハッシュデータベース）とTCBDB（ファイルB+木データベース）を同一のオブジェクト（TCADB）として扱えるようにしたものです。実際にどの型のデータベースが作られるかは、データベースをオープンする際に名前で決めることができます。「*」ならTCMDBが開かれ、「hoge.tch」などのように接尾辞「.tch」がつけばTCHDBが開かれ、「hoge.tcb」などのように接尾辞「.tcb」がつけばTCBDBが開かれます。チューニングパラメータをつけたい場合は「hoge.tch#bnum=1000000#fpow=12」などとします。ともかく、細かいことは気にせず以下のコマンドでファイルハッシュデータベースのサーバを立ててみてください。ポート番号は1978番になります。

ttserver '/tmp/casket.tch#bnum=1000000'

クライアント側ではTTが提供する「リモートデータベースAPI」を用います。これは上述の抽象データベースAPIとほぼ同じシグネチャを持つもので、TCRDB型のオブジェクトに対して各種の操作を行います。まずはリモートデータベースAPIを使ったテストコマンドを動かしてみてください。1000000個のレコードの書き込みを行って、それから個々のレコードを検索してみます。

tcrtest write localhost 1000000
tcrtest read localhost

私の環境だとwriteもreadも1000000回で1分（60マイクロ秒/クエリ）くらいの性能になるようです。プロセス内で非同期モードでTCHDBを動かした場合（tchtest write -as casket 1000000 2000000）の1.41秒（1410ナノ秒/クエリ）くらいに比べるとずいぶん遅いですが、幸いにして各回をストップウォッチで計れないくらいにはなっています。サーバやリモートデータベースAPIの詳細についてはTTの仕様書をご覧ください。

memcached互換プロトコル

TTの独自プロトコルはシンプルで高効率な設計になっていますが、いちいちC言語やC++言語でアプリケーションを書かなきゃならないのは面倒です。わざわざスクリプト言語バインディングのモジュールを作るのも手間ですよね。

そこで、memcachedのプロトコルでTTのサーバにアクセスできるようにしてみました。memcachedは複数のサーバのメモリ空間を仮想的な単一のハッシュテーブルとして利用するためのソフトウェアです。memcachedのプロトコルを喋るライブラリは主要な言語のほとんどで整備されているので、クライアントのポータビリティはHTTP並に高いと言えるでしょう。しかもクライアントライブラリの実装によってはConsistent Hashing等の賢いアルゴリズムも選択できるので、分散ストレージとしても使えるようになります。その上で、TTはメモリでなくファイルにデータを記録するので、サーバを再起動してもデータは失われないようになったわけです。

ただし、memcachedと完全互換を実現するのは難しかったので、互換性は部分的です。TTがサポートしているコマンドはset、add、replace、get（gets）、delete、incr、decr、stats、flush_all、version、quitだけです（つまりappendとprependは未実装）。また、set等でのexpireやcas uniqueの機能も実装されていません。

TTをmemcachedと同様のキャッシュサーバとして使うこともできます。ttserver '*#capsiz=100000000' として起動すれば最大100MBのキャッシュサーバになります。expireを実装していないのに古いキャッシュを自動削除するにはどうするんだという話になりますが、TCADB（TCMDB）には入れた順序が古いものから自動削除する機能が備わっています。キャッシュサーバとしての性能は本家memcachedとほぼ同等になっていると思います。

いちおうPerlクライアントのサンプルを挙げておきます。

use Cache::Memcached;

my $memd = Cache::Memcached->new();
$memd->set_servers(["localhost:1978"]);

$memd->set("tako", "ika");

my $val = $memd->get("tako");
printf("%s\\n", $val);

$memd->delete("tako");

HTTP互換プロトコル

memcached互換プロトコルがそれっぽく動いたので、調子に乗ってHTTPもサポートしちゃいました。キーは（URLエンコードした）URLで表現し、値はエンティティボディに生データを指定します。それらをPUTで格納してGETで取得してDELETEで消すというだけなのですが、なんとなくRESTっぽい気に浸れる逸品です。正直、あまり存在意義はないですけど。 いちおうPerlクライアントのサンプルを挙げておきます。

use LWP::UserAgent;

my $ua = LWP::UserAgent->new(keep_alive => 1);
my $baseurl = 'http://localhost:1978/';

my $req = HTTP::Request->new(PUT => $baseurl . "tako", [], "ika");
my $res = $ua->request($req);

$req = HTTP::Request->new(GET => $baseurl . "tako");
$res = $ua->request($req);
printf("%s\\n", $res->content());

$req = HTTP::Request->new(DELETE => $baseurl . "tako");
$res = $ua->request($req);

ちなみにPOSTはどうしたものかと思うわけですが、とりあえずはmemcachedのaddに対応させています。つまり、PUTだと既存のレコードを上書き（tcadbput）してしまうので、POSTは既存のレコードを上書きしない（tcadbputkeep）ようにしています。

クライアント数に対するスケーラビリティ

TCPのハンドシェイクのオーバーヘッドを極小化するために、TTの独自プロトコルでは単一のコネクションを再利用して複数回の操作が行えるようになっています。「キープアライブ」と言えばHTTP/1.1でおなじみですし、もちろんmemcachedでもそれを採用しています。

多数のクライアントから共有されるストレージとして使う場合、クライアントとサーバ間ではたとえデータベース操作をしていなくてもTCPのソケットが繋ぎっぱなしになることがあります。例えばmixiのような何万人が同時アクセスするかわからないような環境では、ストレージサーバにも同時に何万コネクションが張られるかわかりません（実際にはWebサーバの数とMaxClientsの値の積が上限ですが）。

tt_server.png

そのような膨大なコネクション数をさばくにあたっては、古式ゆかしいselectシステムコールでI/Oを多重化するアプローチは通用しません。そこで、epollとかkqueueとかいうモダンな接続監視機能が各種プラットフォームで提供されています（epollの記事参照）。TTではepollを採用していて、クライアントが数万になっても耐えられるようにしています（試してないのであくまで理論的にはですが）。その副作用でサーバはLinux上でしか動かなくなってしまっているのですが、適当にエミュレーション層を書くなりlibeventを使うなりして他のプラットフォームにも対応していく所存です（気が向けば）。

コネクション数の問題は解決したとして、次にセッション（つまり一連のリクエストとレスポンス）をどう並列化するかが問題となります。典型的な「ボス/ワーカ」モデルでリクエスト毎にスレッドを起こしてデタッチする方法がまず思い浮かびますが、それだと一時的にアクセスが集中した場合にスレッド数が増えすぎて困ったことになります。そこで、TTでは「スレッドプール」モデルを採用しています。すなわち、予め決まった数のワーカスレッドを起こしておいて、彼らにタスクキューを監視させます。ボススレッドはepollキューを監視しておいて、返されたファイルディスクリプタをepollキューからタスクキューに移動させます。タスクキュー内にファイルディスクリプタを見つけたワーカスレッドは、取り出したファイルディスクリプタを介したセッションを実行し、終わったらファイルディスクリプタをepollキューに戻します。

tt_queue.png

こうすると、常に決まった数のワーカスレッドが並列動作するので、個々のセッションの性能が安定します。リクエスト数が多すぎる場合には一時的にタスクキューが溜りますが、それでもサーバがハングするようなことはありません。ワーカスレッドの数はCPUのコア数より少し多いくらいにしておくとよいでしょう。TTの実装では、「TCP接続を受け付けて、epollキューとタスクキューをよろしく管理して、接続イベントに応じてコールバック関数を起動する」という部分をライブラリ化することで保守性を向上させています（それlibeventでいいじゃんorz）。

中二病的主張

memcached互換プロトコルにおいてstatsコマンドの実装でやや困惑しました。プロトコルの仕様書には以下のような定義があり、すなわちCPU使用時間は秒とマイクロ秒を「コロン」区切りで表現すべきとされています。

In the type column below, "32u" means a 32-bit unsigned integer, "64u"
means a 64-bit unsigner integer. '32u:32u' means two 32-but unsigned
integers separated by a colon.
...
rusage_user       32u:32u  Accumulated user time for this process 
                           (seconds:microseconds)
rusage_system     32u:32u  Accumulated system time for this process 
                           (seconds:microseconds)

しかし、本家memcachedの実装は以下のようになっており、すなわち秒と6桁固定のマイクロ秒を「ピリオド」で連結して小数表現としてみなせるようになっています。

sprintf(pos, "STAT rusage_user %ld.%06ldrn",
        usage.ru_utime.tv_sec, usage.ru_utime.tv_usec);

仕様（de jure）と実装（de fact）が矛盾している場合にどうすべきかといった哲学的課題をつきつけられて私のごとき小物はただただ怯えるばかりですが、とりあえず今回は実装の方にしたがっておきました。今となっては実装の方を「正」とみなして仕様の方を改訂して欲しいところです。

勢いでさらにヤブヘビな発言を続けますが、クライアント側であるCPANのCache::Memcachedモジュール（バージョン1.24）におけるstatsの実装も少し変です。statsメソッドを実行すると必ず「Argument "0.9.1" isn't numeric in addition (+) at /usr/lib/perl5/site_perl/5.8.8/Cache/Memcached.pm line 873.」とかいう警告が出るのです。複数のサーバの統計情報を積算する実装になっているのですが、その際にバージョン番号も積算しているようです。「1.0.8」と「1.2.4」を足すと「2.2.12」になるべきなのかどうかはわかりませんが、ともかく「+=」で足すのはよろしくないのかなと思いました（互換性検査につかうならば小さい方のバージョン番号を出すのが合理的なんですかねぇ）。

memcachedには何かの頻度を数えるためにincrコマンドとdecrコマンドがあるわけですが、該当のキーが存在しない場合には何もしてくれない仕様なのがちょっと不便かなと。incr("hoge", 1) としたら "hoge" が存在しない場合には増分を初期値として設定してくれた方が嬉しいケースがほとんどだと思います。add("hoge", 0); incr("hoge", 1); と毎回やらにゃならんのは精神衛生上よくないというか、盗んだバイクで走り出したい気分になります。ていうかincrに負数を指定すればdecrは不要なのかなと思ったけど、decrは0以下を0にするリミッタがついているあたりが新しいのかと思ったけど、でもincrで初期値と変域を指定できるようにした方が実用的なんじゃないかと思ったけど、それはエゴだよ。ていうかそもそもキーに空白文字を入れられないっつーのは(ry

と、何だかんだ言いつつも、memcachedプロトコルに乗っかっているのは、それが有用だからに他なりません。Webアプリケーション等のシステムでキャッシュ的なデータを扱うのに必要十分な仕様になっていますし、実装もよく練られていますし、何より世界中で動作実績があり人々を幸せにしているところが素晴らしいですね。

まとめ

Tokyo Cabinetをネットワーク越しに操作できるようにしたTokyo Tyrantの機能と実装について説明しました。TTはDBMをTCP/IP越しに操作できるようにしただけなので、「リモートストレージ」ではありますが、「分散ストレージ」を直接実現するものではありません。memcachedクライアントを利用することで複数のサーバにデータを分散させることは可能ですが、ノード数が増えると故障率も上がるので、信頼できるストレージとして使うためには冗長化やレプリケーションが必要となるでしょう。今後はそのあたりを強化していきたいと思っています（暇があれば）。

TTの他にも素敵なプロダクトが先行して存在します。弊社トールマエサカ氏のmmcmodも面白い試みですし、GREEの藤本さんが作っておられるFlaredも熱いです。TCを使ったPHPのデータベースサーバとしてrskyさんのTCHDBServerというのもあります。みんなで似たようなもの作ってどうするんだという意見も聞こえてきそうですが、まあ趣味なんでいいじゃないですか（いちおうTTにもちゃんとした用途がありますけどね）。