コミュニティブラウザ

By skimura on 1 月 31, 2008 in algorithm, mixi, search.

はじめまして。mixi開発部のskimuraです。
１月２８日にリリースした「コミュニティブラウザ」について書きたいと思います。

■ コミュニティブラウザとは

存在するコミュニティが増加するほど、目的のコミュニティを捜し出すのは困難になると考えられます。mixiに存在するコミュニティは日々増加しており、今現在では180万以上ものコミュニティが存在します。そこで、興味があるコミュニティを探す手助けをするためのツールを作成したいと考え、本サービスを作成しました。コミュニティブラウザは各コミュニティ対して、関連性が高いコミュニティをおすすめするサービスです。それぞれのコミュニティに参加している各ユーザが参加しているコミュニティの傾向をもとに計算しています。

■ コミュニティブラウザの使い方

実際のサービスはこちらです。

  1. コミュニティブラウザにアクセスすると自分の所属しているコミュニティの一覧が表示されます
  2. オススメコミュニティが見たいコミュニティをクリックします
  3. クリックしたコミュニティに対して、関連性の高いオススメコミュニティが表示されます
  4. ★の数はオススメの度合いを示しています(10段階)

オススメコミュニティは最大２０個まで表示されます。

■ キーワード検索との違い

キーワード検索のメリットとデメリット

コミュニティの場合、キーワードベースの検索では見つけるのが困難なものがあります。例えば、システムエンジニアであるユーザがシステムエンジニアにとって有用なコミュニティを探したい、と考えたとします。そこでmixiの「コミュニティ検索」で“システムエンジニア”を検索キーワードとして検索すると、“システムエンジニア”というキーワードを含むコミュニティが検索結果として大量に得られます。キーワード検索の特徴は、検索キーワードを含む検索結果を大量に得られるのと引き換えに、次の問題が存在します。

関係の無い結果も得られる

高速に膨大な検索結果を得られるのは、検索エンジンの良いところです。しかし、キーワード検索の場合、膨大な結果を得られますが、その中にはたまたまそのキーワードが使用されているだけで、そのキーワードとほとんど関係が無いものも一緒に得られます。したがって検索者はその膨大な検索結果から求めているコミュニティを探さなければならない、というコストが発生します。

キーワードの表記の揺れなどがあると検索結果として得られない

“システムエンジニア”に関するコミュニティの場合、“システムエンジニア”を“SE”や単に“エンジニア”と省略して表記している可能性があります。これは記述者としては“システムエンジニア”と同じ意味でこの言葉を使用していたとしても、検索エンジンにとっては両者の単語は別のものであると判断します。他には言い換えの問題があります。例えば“Mr.children”を“ミスチル”と表現しても両者は、同じバンドグループを意味しています。しかし、Mr.childrenに関する有用なコミュニティが存在しても、そのコミュニティで“Mr.children”を“ミスチル”とだけ表記してしまっていたら、“Mr.children”を検索キーワードとして検索したユーザには表示されません。

レコメンド型の検索

キーワード検索と方法はまったく別物なのですが、コミュニティブラウザではこれらの問題を軽減した形でコミュニティを探すことができます。コミュニティブラウザでは、個々のコミュニティに対して関連性が高いコミュニティが表示されるため、その関係性をたどっていき、目的としていたコミュニティにたどり着くことができます。たとえば“システムエンジニア”の例で、既にシステムエンジニアのコミュニティには所属しているが、さらにプログラム関係やデーターベースに関する特化されたコミュニティを探したいと考えたとき、その分野に詳しい人であれば、“システムエンジニア”に関するキーワードをすぐに思い浮かぶかもしれませんが、一般的には簡単には思い浮かびません。

そこで、「システムエンジニアの部屋」というコミュニティを対象にコミュニティブラウザを利用してみると以下のような結果が得られます。

se.png

「システムエンジニアの部屋」コミュニティには、「Java、C言語、PHP、Perl, Visual Basic」といったシステムエンジニアにとって必要なスキルに関するコミュニティや「ネットワークエンジニア、迷えるSEの卵たち」など直接的に関係するコミュニティなどが結果として得られます。そもそも「システムエンジニアの部屋」というコミュニティを探すのには、キーワード検索をしなくてはなりません。しかし、よりニッチでコアなコミュニティを求める場合には、これまでの説明をしたようにレコメンド型の形式の方が見付かりやすい場合が多くあります。

このようにコミュニティブラウザは検索のあり方の実験も兼ねて開発したサービスでもあります。

■ コミュニティブラウザの仕組み

コミュニティブラウザは次の仮説を前提に実装したものです。

あるコミュニティAに所属しているユーザ達が重複して参加しているコミュニティはコミュニティAに関連性が高い

mixi_blog_picture.png

図で示したように、Community Aに参加しているそれぞれのユーザが参加しているコミュニティをカウントすると、Community Cに最も多く参加していることがわかります。

基本的には、コミュニティブラウザはこの着想をもとに実装されています。だいたいのコミュニティに対してはこの実装のみでそれなりに関連性があるコミュニティを獲得できます。しかし、これだけの実装では次の問題が発生します。

オススメコミュニティのほとんどが参加数が多いコミュニティになってしまう

実際に図のようにコミュニティをカウントしていくと、たいていはあまり関係のないコミュニティが上位になってしまいます。そうするとどのコミュニティにも、単に参加数が多いコミュニティがオススメされてしまいます。そこで、なるべく関連性が高いコミュニティを得られるようにいくつかのパラメータを設定しています。つまり、コミュニティブラウザで示されている星印のポイントは、そのコミュニティに参加しているユーザが重複して入っている確率といくつかのパラメータから作成されています。

■ コミュニティブラウザの楽しみ方

最後にコミュニティブラウザの楽しみ方の例を示したいと思います。基本的には楽しみ方は自由で、興味にしたがってどんどん興味があるコミュニティをたどっていけば良いのですが、その中でもいくつかおもしろいオススメコミュニティが得られたものを紹介したいと思います。

地域コミュニティについて

地域といっても、地名や駅名など様々なものが存在するのですが、基本的にその地域特有のオススメコミュニティが得られます。例えば、株式会社ミクシィが所在している「原宿」コミュニティに対するオススメコミュニティは以下のようになっています。
harazyuku.png

上位は「表参道、神宮前、代官山、青山」と傾向が似た街のコミュニティが示されます。おそらく原宿に良く行く、もしくは好きな人は、これらの街にもよく行かれるのかもしれません。個人的にはおしゃれな街関連なのではないかなどと、予想をしたりしているのですが根拠になる分析はまだしていません。

似ている街以外にも原宿らしい「古着屋、カフェ」に関するコミュニティも得られています。その街の属性を表すコミュニティが得られました。これは、「六本木」や「恵比寿」と比べるとまた、全然違う傾向が表れておもしろいですね。

文学コミュニティについて

私は最近、ミステリー系作家である森博嗣さんの小説を好んで読んでいるのですが、そろそろ森さんの作品をすべて読み終えようとしています。そこで、森さんの小説に傾向が似ている作家を探すため、コミュニティブラウザを用いて、森さんのコミュニティのオススメコミュニティを見てみることにしました。オススメ結果を見ると、「京極夏彦さん、西尾維新さん、綾辻行人さん、宮部みゆきさん」といったミステリー系の作家のコミュニティを得ることができました。このように似ている作家を得るとき以外にも、似ている音楽、料理屋などを探すときにも、コミュニティブラウザの機能を応用することが可能であることが示唆されています。

mori.png

Bookmarklet of Community browser

コミュニティブラウザに簡単にアクセスするためのbookmarkletを作成しました。
以下のbookmarkletをブラウザのお気に入り追加して利用してください。

利用方法
  1. コミュニティブラウザのbookmarkletをブラウザのお気に入りに追加する
  2. mixiのコミュニティページ(http://mixi.jp/view_community.pl?id=xxxx)を表示している状態で設置したbookmarkletをクリックする
  3. 表示しているコミュニティに対してのコミュニティブラウザのページに遷移する

■ まとめ

コミュニティブラウザの使い方、簡単な仕組みについて説明しました。コミュニティブラウザを使うと、それぞれのコミュニティに対する関連コミュニティを取得できます。しかし、これまでの説明にもあったように、基本的にはコミュニティブラウザは各コミュニティに参加しているユーザの傾向を計算しているため、参加人数が少ないコミュニティや、逆にとても多いコミュニティでは関連するコミュニティを抽出するのが困難となります。パラメータ調整により、参加数が多いコミュニティに関しては、関連があるものが抽出できるようになりましたが、参加メンバーが少ないコミュニティに関してはまだまだいい結果が得られないため今後の課題にしたいと思っています。

今後もコミュニティブラウザのオススメコミュニティの抽出アルゴリズムに関しては検討していきたいと思います。
また、本機能を応用したサービスも展開していけたら、と思います。

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

By mikio on 1 月 26, 2008 in 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にもちゃんとした用途がありますけどね）。

memcachedのストレージ層をmodularにしてみた

By tmaesaka on 1 月 24, 2008 in mixi.

前回に続いてまたmemcachedの話をしたいと思います。今回は改造編です。

ハッシュデータベースサーバなどの実装でmemcachedライクなものを書くのも良いですが、以前からmemcached自体のストレージをmodularにできたら面白いかも？と思っていたので実験的にmemcachedを改造してみました（memcached-1.2.4がベース）。

とりあえず名前はmemcached modularの略でmmcmodと名づけて、mikioさんのTokyo Cabinetをストレージとして使うモジュール（厳密にいうと共有ライブラリ）を書きました。ソースコードは後日CodeReposの方に上げますがとりあえずこの記事で公開します。ちなみに新しいプロダクトを作る気はなくて、最終的にpatchを作ることが目的です。

で、話を続けると今回の改造を簡単にビジュアライズするとこんな感じです：

memcached modular

図のmmcstorageは外部ライブラリとリンクしてサーバ内でストレージエンジンの様に使用される更なるラッパーです。

ソースコード

mmcmod：

TokyoCabinetのハッシュデータベースモジュール：

ビルドは通常通りアーカイブの展開後にディレクトリに入って：

./configure
make
make install

で行います。

mmctchdbをビルドするには予めTokyo Cabinetのインストールが必要で、mmcmodをビルドするにはmemcachedと同じく予めlibeventのインストールが必要です。

mmcmodの使い方

“-e /path/to/library” でモジュールを指定します。モジュールを指定しなかった場合は通常のmemcachedとして起動します。

“-o filename”で出力データベースファイルの名前を指定できます、指定しなかった場合はmmcmod.dbというデータベースファイルが作成されます。

例えばmmctchdbがデフォルトのパスにインストールされていたら：

mmcmod -e /usr/local/lib/mmctchdb.so -o mystorage.db

mystorage.dbという名前のTokyo Cabinetのハッシュデータベースがストレージとして使われます。ただし、デーモンとしてmmcmodを起動する場合は必ず絶対パスで許可のある場所にファイルを作るよう指定してください。

使ってみた結果

上記の方法でmmcmodを起動して前回の記事で書いたmemstormで以下の様に：

memstorm -s tokyo -n 10000 -k 32 -l 64

実行してみたところ：

----
Num of Records      : 10000
Non-Blocking IO     : 0
TCP No-Delay        : 0

Successful   [SET]  : 10000
Failed       [SET]  : 0
Total Time   [SET]  : 2.39497s
Average Time [SET]  : 0.00024s

Successful   [GET]  : 10000
Failed       [GET]  : 0
Total Time   [GET]  : 2.50545s
Average Time [GET]  : 0.00025s
----

という結果が返ってきました。

ここで気になるのが本当の本当にTokyo Cabinetにデータが保存されているのか？という事ですよね。という事でTokyo Cabinetのユーティリティツールでデータベースファイルを見てみたところレコードは挿入されています：

[]$ tchmgr inform mystorage.db

path: mystorage.db
database type: hash
additional flags:
bucket number: 16381
alignment: 16
free block pool: 1024
options:
record number: 10000
file size: 1989952

他にも動作確認を行いたかったのでCache::Memcached::Fastのmake testを実行させてみたところ、とりあえずテストは通過する事ができました。

ちなみにmemcachedとして(ライブラリを指定しないで起動）だと：

----
Num of Records      : 10000
Non-Blocking IO     : 0
TCP No-Delay        : 0

Successful   [SET]  : 10000
Failed       [SET]  : 0
Total Time   [SET]  : 2.38709s
Average Time [SET]  : 0.00024s

Successful   [GET]  : 10000
Failed       [GET]  : 0
Total Time   [GET]  : 2.51502s
Average Time [GET]  : 0.00025s
----

という結果になりました。

ここで面白いのがメモリ上で済む程度のデータ量でしかテストを実行していないとはいえ、Tokyo Cabinetのハッシュデータベースではmemcachedのメモリストレージと同等、もしくはより高速なパフォーマンスの可能性が見られるという事です。この驚異的なパフォーマンスに驚かずにはいれませんね。

Modularだと何が嬉しいか

まず第一にメモリという限られたリソースに捕らわれずに高速に大量のデータを扱う事が可能です。しかもストレージがデータベースであればデータを永続的に保持することが可能です。ちなみにmodularではないですが既存のプロダクトでWikimediaが作ったTugela CacheというBerkeley DBをストレージとして使うものがあります。

運用上のメリットを述べるとmemcachedを既に使っているシステムはクライエントサイドを大改造しなくても比較的楽にバックエンドの交換が可能な事です。しかも色々な言語で書かれた素敵なクライエントライブラリが既に世の中に存在しているのでこれらを取り込めるメリットもあります。

もう一つボーナス的な事は保存先が特定のものに特化しないという事です。ライブラリの実装は基本仕様さえ守れば自由なので、典型的な”memcachedに入ってなかったらRDBMSからデータを取る”という処理を全て抽象できます。又、ストレージがハッシュデータベースでなくてもストレージとして使用する事ができます。例えばAmazon S3のようなサービスに送る事だってやろうと思えば可能です。

注意書き

mmcmodはまだ実験段階でUDPとマルチスレッドモードに対応していない事と、今のところ以下のオペレーションしか対応していません：

  • ADD
  • REPLACE
  • SET
  • GET
  • INCR
  • DECR
  • DELETE

追々append,prepend,flush,statsを対応する予定です。

まとめ

今回は実験的に開発したmmcmodというmemcachedのストレージ層をmodularにしたキャッシュ兼ストレージサーバを紹介しました。私のような未熟者が書いた拡張なのでまだまだ完成には程遠いですが個人的に面白いと感じるプログラムなので継続して開発しようと思います。

libmemcachedで快速キャッシュ生活

By tmaesaka on 1 月 10, 2008 in mixi.

みんな大好きなmemcached。今日はBrian AkerのC言語用クライエントライブラリについて書きたいと思います。日本語の情報がとても少なく、ドキュメンテーションも英語だけという事で興味はあるけど手をつけていないという方のお役に立てれたらなと思います。

本題の前に why libmemcached?

既にlibmemcacheが存在するのに何故、libmemcached？かと言うと理由の一つは最近libmemcacheの開発が止まったからです。本家ではそれが理由でlibmemcacheではなくlibmemcachedを推奨してますね。又、効率的なメモリ使用、Consistent Hashing、様々なハッシュアルゴリズム、新しいオペレータに対応している等という宣伝文句があります。apr_memcacheというライブラリも存在しますが自分は使った事がないためノーコメント。

ただ、推奨されているという理由だけでは大して嬉しくないのは私だけではないはず。ということで私が現在知っているメリットを述べさせて頂きます。

使うと嬉しい理由

嬉しい理由の一つはlibmemcachedを使う事によってmemcachedを分散させたシステムを高速化できるという事です。例えば従来の方法通りに<key, value>をクライエント任せで登録するのではなく、libmemcachedではmemcached_set_by_key(3)という関数を使う事によってデータを<master_key, key, value>という形式でSETできます。

で、master_keyが何かというとクライエントアプリケーションがmaster_keyとkeyをひもづける事でデータを散らばらせず、特定のサーバに保存するためのkeyです（つまり関連データをクラスタ内で一箇所に集中させられる）。このメカニズムがあるというまでもなくmgetが段違いに速くなると仮定できます。なぜなら無駄に複数のサーバに接続してデータ回収を行うネットワークコストが抑られるから。

分散環境でもう一つ嬉しい点を述べるとconsistent hashingを用いる事によって、ノードのサービスイン・サービスアウトの際に必ず生じるデータのズレが限りなく小さくなるという点ですが、この件に関して書き始めると読者の眠気を誘う記事になってしまうので、これは後日書きたいと思います。

本当に？

喉から手が出るほどmemcached_(set|get)_by_key(3)の性能テストを行いたいのですが、やはり行うにはサーバを10台くらい用意したいので、後日結果を公開したいと思います。

実際に宣伝通りに素晴らしいソフトウェアかを語るには少なくとも自分で手を動かさないといけないのでlibmemcachedを使ってみました。それでもってサンプルアプリを作ったので、興味のある方は目を通して頂けたら光栄です（記事の最後の方）。

libmemcachedを使ってみよう

使い方は人それぞれですが、ここでは単純にデータのSETとGETの方法の一つを紹介します。基本的に使用するパーツは：

  • memcached_st （サーバとのやりとりに使用する構造体）
  • memcached_server_st （サーバ情報やそのbufferを持つ構造体）
  • memcached_return （ほぼ全ての関数が返す返り値）

と以下の関数：

  • memcached_create(3)
  • memcached_servers_parse(3)
  • memcached_server_push(3)
  • memcached_set(3)
  • memcached_get(3)
  • memcached_server_list_free(3)
  • memcached_free(3)

だけです。includeするヘッダーは “memcached.h” だけ。

まず最初に必要なパーツの定義：

struct memcached_st *mymmc;
struct memcached_server_st *myservers;
memcached_return rc;
char *key = "yome";
char *val = "hiiragi_kagami";
char *hostname;

何をするにも必要なmemcached_stを作る：

mymmc = memcached_create(NULL);

予め作ってあるmemcached_stをアサインする事も可能。その構造体へのポインタをmemcached_createに渡すだけで良い。次にサーバ接続への仕込みをします。ドキュメントには「接続する」と書いていますがソースを読んだらここでは接続は発生しないようだから「仕込み」とあえて言います。

サーバ接続の準備・仕込み：

myservers = memcached_servers_parse((char*)hostname);
rc = memcached_server_push(mymmc, myservers);
assert(rc == MEMCACHED_SUCCESS);

上記のコードは一つのサーバでも複数のサーバでも関係なく動作します。

他にも色々と接続手段がありますので気になる方はlibmemcachedのインストール後、 “man 3 memcached_server_add” に目を通してみてください。実際に接続が行われるのは”lib/memcached_do.c”の中のmemcached_do関数の模様 （もっと正確には”lib/memcached_connect.c”のmemcached_connectを使って）。

次にお好みで色々なサーバの設定が可能です。これはmemcached_behavior_set(3)で行います。例えば使うハッシュアルゴリズムを以下から選べます：

  • MEMCACHED_HASH_DEFAULT
  • MEMCACHED_HASH_MD5
  • MEMCACHED_HASH_CRC
  • MEMCACHED_HASH_FNV1_64
  • MEMCACHED_HASH_FNV1A_64
  • MEMCACHED_HASH_FNV1_32
  • MEMCACHED_HASH_FNV1A_32
  • MEMCACHED_HASH_KETAMA

他に何が設定できるかなどはlibmemcachedのインストール後に “man 3 memcached_behavior_set” で読む事ができます。

で、次にデータのSET：

/* key = "yome", val = "hiiragi_kagami" */
rc = memcached_set(mymmc, key, strlen(key), val, strlen(val),
                   (time_t)0, (uint16_t)0);

if(rc != MEMCACHED_SUCCESS) {
  fprintf(stderr, "failed to SET\\n");
}

KeyでGET：

char *ret; /* 返ってきたデータへのポインタ */
size_t val_len;
ret = memcached_get(mymmc, key, klen, &val_len, (uint16_t)0, &rc);

if(rc != MEMCACHED_SUCCESS) {
  fprintf(stderr, "failed to GET\\n");
}

free(ret); /* 使い終わったらfree(3)しよう */

Multi Getしたい場合はmemcached_mgetとmemcached_fetchを使って行います。詳しくは “man 3 memcached_mget” に記載されています。

使い終わったmyserversとmymmcはきちんと開放：

memcached_server_list_free(myservers);
memcached_free(memc);

とまあ見ての通り使い方は簡素です。

簡単なプログラムを書いてみた

正直な話、私は何かデモを書かないとライブラリ等を理解できない不器用なプログラマです。だからlibmemcached-0.12の感触をつかむために簡単なmemcached単体・クラスタのパフォーマンスをテストするツールを書いてみました。

memstorm-0.6.8.tar.gz
追記： libmemcached-0.13でエラーが生じる件は原因を判明しパッチを送りましたので、memstormのお試しにはlibmemcached-0.12をお使いください。

ビルド＆インストールはアーカイブを展開した後にディレクトリに入って：

./configure
make
make install

で行います（インストールまでする必要はないかも）。あ、それと当然ながら最初にlibmemcachedをシステムにインストールしていないとビルドできません。

memstormを使ってみよう

使い方は超簡単、例えばtokyoとkyotoというサーバにそれぞれmemcachedをデフォルトポートに立ち上げていると仮定しましょう。

memstorm -s kyoto,tokyo -n 10000 -k 64 -l 10240

上記を実行したらmemstormはkyotoとtokyoに10000回、10240バイトのデータを64バイトのKeyでSETしてレコードを同じ回数だけGETします。つまり合計100MB近いテストデータを使ったテストです。

デフォルトポートを使っていない場合、例えばkyotoはデフォルトポートだけれどtokyoでは11311をlistenしている場合は以下のようにmemstormを実行します：

memstorm -s kyoto,tokyo:11311 -n 10000 -k 64 - 10240

普段はあまり意味がないけど複数のサーバと通信しているかを確認するために同一サーバでmemcached 1.2.4のインスタンスを二つ立ち上げた環境ではこんな結果でした：

memstormの実行：

memstorm -s tokyo:11211,tokyo:11311 -n 10000 -k 64 -l 10240

結果：

Num of Records      : 10000
Non-Blocking IO     : 0
TCP No-Delay        : 0

Successful   [SET]  : 10000
Failed       [SET]  : 0
Total Time   [SET]  : 13.61078s
Average Time [SET]  : 0.00136s

Successful   [GET]  : 10000
Failed       [GET]  : 0
Total Time   [GET]  : 12.63989s
Average Time [GET]  : 0.00126s

非同期モードで同じテストを実行した結果、バグった？と思わされるほどSETの性能が飛躍的に向上したのが解ります：

memstormの実行：

memstorm -s tokyo:11211,tokyo:11311 -n 10000 -k 64 -l 10240 -b

結果：

Num of Records      : 10000
Non-Blocking IO     : 1
TCP No-Delay        : 0

Successful   [SET]  : 10000
Failed       [SET]  : 0
Total Time   [SET]  : 1.56849s
Average Time [SET]  : 0.00016s

Successful   [GET]  : 10000
Failed       [GET]  : 0
Total Time   [GET]  : 22.10626s
Average Time [GET]  : 0.00221s

SETは確かに早くなっていますが引き換えに私の環境ではGETが遅くなっている模様。ただし遅いと言ってもAverage Timeを見ると爆速でデータの出し入れが行われているのが解ります。

普通に１インスタンス（同期モード）だけ立ち上がっていても2インスタンス（同期モード）とパフォーマンスは変わらないっぽい：

memstormの実行：

memstorm -s tokyo:11211 -n 10000 -k 64 -l 10240

結果：

Num of Records      : 10000
Non-Blocking IO     : 0
TCP No-Delay        : 0

Successful   [SET]  : 10000
Failed       [SET]  : 0
Total Time   [SET]  : 13.62225s
Average Time [SET]  : 0.00136s

Successful   [GET]  : 10000
Failed       [GET]  : 0
Total Time   [GET]  : 12.14061s
Average Time [GET]  : 0.00121s

では非同期通信だとどうなるのでしょう？

memstorm -s tokyo -n 10000 -k 64 -l 10240 -b

結果：

Num of Records      : 10000
Non-Blocking IO     : 1
TCP No-Delay        : 0

Successful   [SET]  : 10000
Failed       [SET]  : 0
Total Time   [SET]  : 1.53818s
Average Time [SET]  : 0.00015s

Successful   [GET]  : 10000
Failed       [GET]  : 0
Total Time   [GET]  : 22.08139s
Average Time [GET]  : 0.00221s

なるほど、先ほどと同様にSETは早くなってGETが遅くなっていますね。ただ、このテストだけではあまり有力な判断材料にはならないためConcurrency（並列）テストも出来るように書こうかなと考えたのですが、これから紹介するmemslapはそれが既に出来るので今回はノータッチ。

memslap

memslapとはlibmemcachedと一緒に配布されている負荷テスト・ベンチマークツールです。生みの親が同じである事からmysqlslapの兄弟です。これを使って何が嬉しいかというと並列してサーバに負荷をかけられる事です（mysqlslapはエンジンを変えたりもっと色々できます）。

で、memslapを使うとmemcachedを普段から使っている人の疑問である：

  • thread有効オプションでコンパイルしたら実際に嬉しいのか？
  • やっぱロックのコストで何も変わらない、もしくは性能が劣化するのか？

などの判断材料になります。ただしkey/valueのサイズを自由に変えたり、テスト進捗が見えないのが個人的に不便だと感じました（これ、実はmemstormを書いた理由でもあります）。

ちなみに作者がいうにはmemslapは未完成との事です。実際にlibmemcached-0.12のmemslapは自分の環境だとなぜかreadが失敗しまくるんですよね。といってもこれはmemslapより私側の否であるかもしれないのでODFの日に調査してみようと思います。PerlのWrapperはDBIでお馴染みのTim Bunce氏が開発中。

まとめ

今回はlibmemcachedを紹介し利用例とテストツールを書いてみました。memcachedは弊社ではかなりの台数のサーバで使い込んでいるのでこれから面白い発見などがあればブログに書いていきたいと思います。

またお会いしましょう！

おすすめマイミクシィ／コミュニティ

By mikiokato on 1 月 7, 2008 in algorithm, mixi, odf.

はじめまして。mixi開発部・運用グループでアプリケーションの運用を担当しているmikiokatoといいます。週に一日興味があることについて研究や開発ができるOneDayFree の制度を使って開発し、12月25日にリリースしたインディーズ機能「おすすめ マイミクシィ／コミュニティ」について書いてみたいと思います。

おすすめ マイミクシィ／コミュニティとは

マイミクシィやコミュニティのリンクを分析して、マイミクシィになる可能性の高い人や興味がありそうなコミュニティをおすすめします。膨大な情報の中から検索などでユーザーにいろいろと探してもらうよりも、データを分析して興味がありそうなものをシステムからおすすめする試みです。

実際の画面はこちらです。

人によって精度は差があるので、結果がいい場合もよくない場合もありますが、マイミクシィやコミュニティの発見につながればと思います。では、どういった仕組みでおすすめしているかを説明していきます。

おすすめ マイミクシィ／コミュニティの仕組み

おすすめマイミクシィ

親しい人から招待を受けてミクシィに参加し、よく知っている人からマイミクシィになっていく場合が多いため、一般にマイミクシィの数が少ないほど、親しい関係だと考えられます。
マイミクシィの数によってポイントを加算して集計することで、おすすめマイミクシィの候補を決定しています。

つまり、下の図のように、マイミクシィBさんのマイミクシィの数が10人だったとすると、マイミクシィのマイミクシィDさん、Eさんのポイントにそれぞれ1/10が加算されます。基本的には、それをマイミクシィの数だけ集計してランキングをつけているというわけです。例では、Dさんよりポイントの高いEさんの方が親しいだろうと予測されます。

recommend

おすすめコミュニティ

おすすめマイミクシィと同様に、親しいユーザーを分析し、そのマイミクシィが参加しているコミュニティをおすすめします。
また、マイミクシィがよく参加しているコミュニティや、参加者の多いコミュニティもあわせておすすめしています。

こちらはおすすめマイミクシィの計算方法に加えて、マイミクシィがよく参加しているコミュニティという要素も取り入れていて、適度な割合になるように両方の要素のポイントを合計しています。

このように、分析に使っているデータはマイミクシィのリンクとコミュニティに参加しているかどうかのリンク情報だけで、プロフィールなどの文章的な情報は全く使っていませんが、文章的な解析をしなくてもある程度の精度を出すことができています。こういったリンク情報の解析の研究は、リンクマイニングと呼ばれる研究分野となっています。

システム的な仕組み

解析の考え方は上記のとおりですが、こういった単純なアルゴリズムでも、マイミクシィの多いユーザーの場合は、処理時間がかかったり、システムに負荷がかかってしまいます。ですので、バッチ処理で定期的に結果のみデータベースに格納するようにしています。

mixi はユーザ数が1000万人以上いるので、単純に直列的なバッチ処理を考えると、1人あたりの処理に0.5秒かかったとしても・・・

1000万人×0.5秒=500万秒=約58日

と、これくらいの日数がかかる計算になります。

実際には、おすすめマイミクシィ／コミュニティの場合はID別に並列処理が可能なので、複数のプロセスで処理したり、同じ内容のデータベースを複数用意したりして、72時間程度で初回の解析を完了することができました。その後はアクセスの有無やマイミクシィの数の変動等を基準にして再度解析することでデータを更新しています。

まとめ

新しくマイミクシィになったり、コミュニティに参加したという声も聞かれる一方、こういったような問題もあります。

  • マイミクシィじゃなくなったユーザーや退会したコミュニティが表示される
  • 興味がないマイミクシィやコミュニティが表示される
  • アクセスブロックしているユーザーが表示される

    • 今後は機能追加やアルゴリズムの改善などでこういった問題を対処していきたいと思います。