こんにちは!プラットフォーム開発チームに所属してます、よういちろうです。7月に行われるOpenSocial Hackathonについてお知らせいたします。

株式会社ミクシィエヌ・ティ・ティ レゾナント株式会社の共同主催にて、OpenSocial Hackathonを7月17日に開催いたします。

gooホームはOpenSocial対応された環境を既に一般公開しており、gooホームガジェットが広く利用されています。また、mixi Platformについてもオープンβ版の公開により幅広い開発者の方々に利用していただいております。

今回のOpenSocial Hackathonでは、mixiアプリ開発またはgooホームガジェット開発に興味をお持ちの方々を対象に、実際にmixi Platformもしくはgooホーム Sandboxを利用して、多くのユーザにリーチするアプリケーションの開発を体験して頂けます。OpenSocialアプリケーション開発の中心はJavaScriptコードの記述となりますので、例えばAjaxによる開発経験をお持ちの方であれば、すぐに開発を始めることが可能です。Hackathonでは、いくつかのチームに分かれ、短時間でアプリケーションの開発を行います。

皆さまの開発をサポートするために、Google API ExpertもHackathonに参加し、皆さまの質問にお答えいたします。

mixiアプリ/gooホームガジェットの開発経験を得る貴重な機会をぜひご活用ください。

[参加方法] 以下のURLよりお申し込みください。 ※先着順となります。
https://mixi.jp/entry_hackathon.pl

========================================
主催: 株式会社ミクシィ、エヌ・ティ・ティ レゾナント株式会社
日時: 2009年7月17日(金) 10:00~18:00 (開場:09:30)
場所: 株式会社グーグル
人数: 30名
参加条件: OpenSocialアプリケーションの開発経験のある方
ノートパソコンの持参が可能な方

※参加者の方々は7月14日に事前ミーティングも行いますので、ご参加ください。
日時: 2009年7月14日(火) 19:00~21:00 (開場:18:30)
場所: 株式会社グーグル
内容: Hackathonでのチーム分け等の手続き、アイデアの意見交換
お問合せ: フォーム<http://mixi.jp/entry_platform.pl>よりお問合わせください
========================================

<注意事項>

  • Hackathonではチームでアプリケーションを作成し、コーディング終了後にアプリケーションをプレゼンしていただきます。その際、コードなどがチームのメンバーや他の応募者に開示されますことを予めご了承ください。
  • 作成したアプリケーションはmixiやgooホームなどのサイトにてご紹介させていただく場合があります。
  • 当日はチーム内での情報共有のためのツールとして、Google Docsを使用します。その際、他の応募者にお名前とメールアドレスが他の応募者に開示されることを予めご了承ください。
  • 当日はソースコードの共有のためのツールとして、Google Project Hostingをご利用いただけます。その際、Subversionを使用することになるため、何らかのSubversionクライアントを予めご用意ください。

梅雨。部屋干しした洗濯物による異臭騒ぎに苦しむmikioです。今回は、Tokyo Cabinetのテーブルデータベースで超お手軽に全文検索をする方法について説明します。

tcindexvariants

使い方

テーブルデータベースについてまずおさらいしておきましょう。PerlやRubyのハッシュのようにコラム名とその値を関連づけた構造を、主キーを識別子として保存するデータベースです。例えばRubyからデータを保存するに以下のように行います。データベースであることをほとんど意識させないというのが素敵ポイントです。APIはCでもPerlでもRubyでもほとんど同じなので、言語にかかわらず同じようにレコードを操作できます。

require 'tokyocabinet'
include TokyoCabinet

# データベースを開く
tdb = TDB::new
tdb.open("casket", TDB::OWRITER | TDB::OCREAT)

# レコードを入れる
tdb.put("12", { "name" => "mikio", "lang" => "c,c++,perl,ruby,java,lua",
                "birth" => 19780211, "intro" => "趣味はサーフィンです。" })
tdb.put("34", { "name" => "jonathan", "lang" => "c,c++,perl" })
tdb.put("56", { "name" => "joseph", "lang" => "c++,perl,ruby,php" })
tdb.put("789", { "name" => "jotaro", "lang" => "ruby,python,java" })

# データベースを閉じる
tdb.close

一般的なリレーショナルデータベースと違ってスキーマがなく、レコード毎のデータ構造が同じである必要はありません。上記のように、mikioだけ生年月日と本名を入れるみたいなことが普通にできます。さて、上記のDBにいろんな条件で検索をしてみましょう。

require 'tokyocabinet'
include TokyoCabinet

# データベースを開く
tdb = TDB::new
tdb.open("casket", TDB::OREADER)

# nameが「jo」で始まる人を探す (普通の文字列検索)
qry = TDBQRY::new(tdb)
qry.addcond("name", TDBQRY::QCSTRBW, "jo")
p qry.search

# C++とRubyが使える人を探す (タグ検索)
qry = TDBQRY::new(tdb)
qry.addcond("lang", TDBQRY::QCSTRAND, "c++,ruby")
p qry.search

# 自己紹介に「サーフィン」を含む人を探す (全文検索)
qry = TDBQRY::new(tdb)
qry.addcond("intro", TDBQRY::QCFTSPH, "サーフィン")
p qry.search

# データベースを閉じる
tdb.close

このように、任意のコラムを対象にして様々な演算子で条件を設定することができます。テーブルDBにさえ入れておけば、いわゆるタグ検索(”c++”と”ruby”を含む)や全文検索(部分文字列として”サーフィン”を含む)などの高度な検索条件でレコードを取り出すことができます。100万レコードくらいの規模であれば、専用の全文検索エンジンを使わなくても、おそらくTCだけでそこそこ実用的な情報検索システムや文書管理システムを構築することができるでしょう。もちろんTokyo Tyrant経由でも利用できるので、Solr(Lucene)っぽい位置づけで使えるとも言えるでしょう。

本当に3行で全文検索機能を追加できる

この仕組みを使って、前回とりあげた100行チャットのデモサイトにも検索機能が加えられました。データベースと検索エンジンが統合されているので、特に工夫しなくてもリアルタイム検索になっているのが自慢です。それでいて、加えたのは以下のたった3行です。

...
// 検索クエリをパラメータから受け取る
const char *search = tcstrskipspc(tcmapget4(params, "search", ""));
...
// 検索クエリがあれば、チャットログの表示条件にそれを加える
if(*search != '\0') tctdbqryaddcond(qry, "t", TDBQCFTSEX, search);
...
// ページ遷移でクエリを引き継ぐためにテンプレート変数に渡す
tcmapprintf(vars, "search", "%s", search);
...

表示部分が既にあるならば、その絞り込み条件を入力として受けて1行、それをクエリオブジェクトに渡して1行、結果画面に反映させるために出力に渡して1行、合計3行です。これは極端な例ですが、ストレージ層が検索機能を備えているならば、検索システムを構築する際の実装工程は刺身にタンポポを乗せるような簡単な仕事になります。浮いた分の工数を要求分析や設計やテストに注力できたらハッピーですよね。

転置インデックス

タグ検索も全文検索も、TCのテーブルデータベースで従来からサポートされていました。何が新しいのかというと、それらの検索操作を高速化するために、2種類の転置インデックスを使うことができるようになったことです。タグ検索を高速化する「トークン転置インデックス」と、全文検索を高速化する「q-gram転置インデックス」です。

タグ検索について考えてみます。コラムの値を空白またはコンマで区切ったトークンの集合とみなして、指定したトークンが存在するレコードを探す操作です。例えば、「ruby,python,java」という文字列があった場合、「ruby」と「python」と「java」が照合条件になります。タグ検索は広い意味では全文検索の一種とも言えるのですが、切り出したトークンを単位としてでないと検索できないことが特徴です。例えば、「python」の「thon」といったトークン内の部分文字列や、「by,py」といったトークンをまたがった部分文字列は照合条件にすることができません。

タグ検索を高速化するには、レコードの値そのものを検索キーとしたインデックスを作るわけにはいきません。そうでなく、レコードから切り出した各々のトークンを検索キーとして、それを含むレコードの主キーのリストを値としたインデックスを作る必要があります。このように、検索対象のレコードを分解して検索キーを作り出して、それに付随させてレコードを特定するための位置情報のリスト(posting listともいいます)を記録したインデックスのことを転置インデックスといいます。通常の文字列型および数値型のインデックスとの比較はこの記事の冒頭のイラストを見ていただけるとわかりやすいと思います。

全文検索について考えてみます。ここではタグ検索と対比して、アプリケーションレベルのトークンを無視して、全ての部分文字列でも検索対象にした検索操作を全文検索と呼ぶことにします。英文を検索する場合は空白などの記号でトークンを区切ればタグ検索の使用感と全文検索の使用感をほぼ同じにすることができるのですが、日本語だとMeCabなどの優れた形態素解析器をもってしても期待通りにトークンを切り出せるとは限らない(そもそも期待される切り出し方が一通りでないことも多い)ので、タグ検索と全文検索の仕組みは別個に実装しておく必要があります。

全文検索を高速化するには、任意の部分文字列を検索キーとして、それを含むレコードの主キーのリストを値としたインデックスを作る必要があります。とはいえ、任意の部分文字列の組み合わせ数はレコードの文字数の2乗という膨大な数になってしまうので、一定の文字数で区切って検索キーを作り出すことにします。このような方式をq-gram(文字N-gram)インデックスと呼びます。詳しい特性は以前の記事で述べましたので興味のある方はご確認ください。

転置インデックスの威力

転置インデックスの威力を見るために、インデックスを張った場合と張らない場合で検索性能がどう変わるかを見てみましょう。まずは、以下のコマンドで、100万レコードを登録したテスト用のデータベースを作ります。

$ tcttest write casket 1000000

どんなレコードが入っているか確かめるべく、5件だけ表示してみます。

$ tctmgr list -m 10 -pv casket
1    str    1    num    1    type    18   flag   4,6,9,12  text    4,6,9,12
2    str    2    num    1    type    8    flag   1,2       text    1,2
3    str    3    num    1    type    15
4    str    4    num    2    type    28
5    str    5    num    3    type    3    flag   2,4,7     text    2,4,7

この状態では転置インデックスは張っていません。flagコラムにトークンとして「19」を含むものを探してみましょう。”-ph” オプションでヒント情報を出力しています。

$ tctmgr search -pv -ph casket flag STRAND 19
449   str  449   num  114   type  10   flag  5,10,15,19   text  5,10,15,19
1246  str  1246  num  1182  type  16   flag  5,9,14,19    text  5,9,14,19
1542  str  1542  num  973   type  14   flag  4,9,14,19    text  4,9,14,19
1941  str  1941  num  323   type  22   flag  5,9,14,19    text  5,9,14,19
2007  str  2007  num  1425  type  32   flag  4,9,14,19    text  4,9,14,19
...
        :::: scanning the whole table
        :::: result set size: 1292
        :::: leaving the natural order
        :::: number of records: 1292
        :::: elapsed time: 1.24810

ヒントの「scanning the whole table」は全表操作であることを示します。それにともない、転置インデックスを張らない状態だと、検索に1.25秒もかかっています(文字列型インデックスを張ったとしてもSTRANDとSTRORには効かないので性能は変わりません)。そこで、flagコラムにトークン転置インデックスを張ります。

tctmgr setindex -it token casket flag

この規模なら1秒くらいでインデックスが張り終わると思います。”-it token” はインデックスの型がトークン転置インデックスであることを示しています。なお、q-gram型にしたい場合は “-it qgram” とします。では、転置インデックスのある状態で検索してみます。

$ tctmgr search -pv -ph casket flag STRAND 19
449   str  449   num  114   type  10   flag  5,10,15,19   text  5,10,15,19
1246  str  1246  num  1182  type  16   flag  5,9,14,19    text  5,9,14,19
1542  str  1542  num  973   type  14   flag  4,9,14,19    text  4,9,14,19
1941  str  1941  num  323   type  22   flag  5,9,14,19    text  5,9,14,19
2007  str  2007  num  1425  type  32   flag  4,9,14,19    text  4,9,14,19
...
        :::: using an index: "flag" inverted (STRAND)
        :::: result set size: 1292
        :::: leaving the natural order
        :::: number of records: 1292
        :::: elapsed time: 0.00169

出力されるレコードは変わっていませんが、ヒントの「using an index: “flag” inverted (STRAND)」は転置インデックスが使われたことを示しています。そして今度は検索が0.0016秒で済んでいることがわかります。圧倒的に高速ですよね。

転置インデックスも他の型のインデックスと同じく、レコードを入れる前に張ってもレコードを入れてから張ってもかまいません。インデックスがある状態でレコードを入れるとインデックスも自動的に更新されます。スキーマなんてあまり考えずにとりあえず何でもデータベースに突っ込んでおいて、運用してみて高速化したくなった演算にだけインデックスを張るというお気楽な開発スタイルがとれるのが強みではないでしょうか(業務システムでそれやったらしばかれるでしょうが)。

全文検索用の演算子

トークン転置インデックスを張ると、今までインデックスが効かなかったSTRAND演算子とSTROR演算子が高速化されます。じゃあ全文検索用のq-gram転置インデックスを張るとSTRINC演算子(文字列の部分一致)が高速化されるのかと思うところですが、そうではありません。最新版からは全文検索用の以下の演算子が追加されていて、それらを高速化する効果があります。

  • FTSPH : フレーズ検索の全文検索を行う
  • FTSAND : コンマ区切り(または空白区切り)の文字列を用いてAND検索の全文検索を行う
  • FTSOR : コンマ区切り(または空白区切り)の文字列を用いてOR検索の全文検索を行う
  • FTSEX : 複合検索式の全文検索を行う

STRINCとは別に演算子を設けた理由の第一は、全文検索用の演算で文字列の正規化をしたいということです。すなわち、全角英数字と半角英数字を同一視したり、全角片仮名と半角片仮名を同一視したり、ウムラウトなどのアクセントマークの有無を同一視したりといった正規化です。STRINC演算子はあくまでそのままのバイト表現の中間一致を調べるべきで、現行の仕様は変えたくなかったので、正規化をした文字列の中間一致を調べるには別の演算子を設けるのが最善でしょう。

ということでSTRINC演算子の正規化版とも言えるFTSPH演算子をまず作りました。ただ、それだけだと全文検索でよく使うAND検索をうまく扱うことができません。FTSPH演算子で「unix linux」と入れると、「unix linux」が現れるレコードを探すのであって、「unix」と「linux」がそれぞれ任意の位置に現れるレコードを探すわけではありません。FTSAND演算子はそのために追加しました。さらに、AND検索があったらOR検索もあるだろうということで、FTSOR演算子も追加しました。

AND検索、OR検索と来たら、NOT検索とかそれらの複合条件も指定したくなるのが人情というものです。例えば、「リュウ」か「ryu」を含んで、かつ「ケン」か「ken」を含んで、かつ「魔弾戦記リュウケンドー」は含まないといった条件で検索をしたくなるわけです。その際にはFTSEX演算子による複合検索式として「リュウ || ryu && ケン || ken !! 魔弾戦記リュウケンドー」などと指定します。「&&」はAND検索、「||」はOR検索、「!!」はNOT検索を意味します。結合の優先度は「||」が上位で「&&」と「!!」はその下です。同一優先度の場合は左結合で評価されます。空白を照合条件に含めてフレーズ検索をするために、「”"」でくくることもできます。これで全文検索のユースケースの99%以上はカバーできているのではないかと思います。

まとめ

Tokyo Cabinetのテーブルデータベースは、各種スクリプト言語のハッシュと同じような簡潔なインターフェイスを備え、それでいて強力な機能群によって実用的なアプリケーションを容易に構築することを可能にしてきました。それにさらに2種類の転置インデックスと全文検索用の演算子が加わり、専用の全文検索システムがなくても、データベースに入れるだけで一般的な情報検索や文書管理に必要な検索操作のほとんどを充足させることができるようになりました。とっても簡単で便利なのでぜひ試してみていただきたいところです。

タグ検索と全文検索といえば、Tokyo Dystopiaが同じような機能を既に実現しています。TCにタグ検索と全文検索がサポートされたからもうTDは不要なのかと思われるかもしれませんが、そうではありません。転置インデックスのライブラリとしてはTDの方がはるかに効率的かつスケールする設計になっていて、また業務に必要なカスタマイズを容易にするためにシンプルな実装になっています。一方でTCの転置インデックスは、パフォーマンスやスケーラビリティではTDに劣りますが、ものすごく簡単に導入できることが特徴です。既にテーブルDBでデータの管理をしているならば、setindexホゲホゲという文を書くだけで1分以内に検索機能を強化することができるのです。

実装の詳細についてもうちょっと書こうかなとも思ったけれど、「内部がどうなってるかなんて別に興味ない」とか「ソースとか張られても読み飛ばすだけだし」とか言われることが多いので割愛しました。10わっふる以上を検知したら次回以降に書くかもしれませんが…。

逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。

クラスタリングとは

クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。

例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。

クラスタリング

様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下のページが詳しいため、そちらをご参照下さい。

軽量データクラスタリングツールbayon

シンプルなデータクラスタリングツールとして、bayonというツールを作成しました。名前は、筆者が好きなアンコール・ワット遺跡のバイヨン寺院から拝借したもので、特にクラスタリングには関係ありません。

bayonはシンプルな構成で、かつ大規模なデータでも実用的なスピードで実行できるようにすることを目標に作成しています。手元の環境でいくつかのデータセットを用意して簡単に実行時間を測ってみたところ、以下の結果が得られました。50万件のデータでも12分程度で完了できており、用途にもよるとは思いますが、実用に耐えるだけの速度は得られていると思います。

データ数 クラスタ数 実行時間(秒)
1000 10 0.17
50000 1000 36
500000 10000 720

bayonはクラスタリング手法として、後述するRepeated Bisection法を採用しているのですが、これは他のクラスタリングツールCLUTOで使用されている手法です。CLUTOは高速かつ精度もよいクラスタリングツールで、GUIでの利用や様々なオプションなどを利用することができる非常に便利なツールです。じゃあそもそもCLUTOを使えばいいのでは?となりそうですが、CLUTOは商用で利用する場合は事前許可が必要となり、使用の際はライセンスに注意しなければなりません。その点bayonはライセンスにGPL2を採用しているため、商用のサービスでの利用も問題ありません。

また手元の環境で試した限りでは、クラスタリングの実行速度はCLUTOよりもbayonの方が上回っています。ただCLUTOは精度向上のためにさらに複雑なことをしているので、単純な比較はできないのですが、さくっと傾向を確認したい場合等にはbayonも一つの選択肢として考慮していただければ幸いです。

実行方法

実際にbayonでクラスタリングを行う際は、まず入力として以下のようなタブ区切りのテキストファイルを用意してください。1行に1つのドキュメントの情報を表し、行の先頭にドキュメントのID、それ以降はそのドキュメントの特徴を表すキーとポイントをペアで記入します。

% cat input.tsv
阿佐田  J-POP      10 	J-R&B     6   ロック   4
小島    ジャズ      8 	レゲエ    9
古川    クラシック  4 	ワールド  4
田村    ジャズ      9 	メタル    2   レゲエ   6
青柳    J-POP       4 	ロック    3   HIPHOP   3
三輪    クラシック  8   ロック    1

例えば上記の例では、1ユーザの情報を1つのドキュメントと考え、ユーザが聞く音楽のジャンルによってそのユーザの特徴を表しています。「阿佐田」「小島」「古川」が各ユーザのID(名前)で、「阿佐田」の特徴を表すキーとして「J-POP」「J-R&B」「ロック」が挙げられています。

次にこの入力ファイルを使って、クラスタリングを実行します。以下ではクラスタ数を3に指定して実行しています。

% bayon -n 3 input.tsv > output.tsv

クラスタリング結果は、以下のようなタブ区切りのテキストになります。1行が1つのクラスタを表し、行の先頭がクラスタのID、それ以降はそのクラスタに所属するドキュメントのIDのリストです。

% cat output.tsv
1       小島    田村
2       阿佐田  青柳
3       古川    三輪

それぞれ、ジャズ好き、J-POP・ロック好き、クラシック好きのクラスタに分割できていることが分かります。

より詳しく知りたい方は、チュートリアルを用意してありますので、そちらをご参照下さい。

クラスタリング手法

bayonでは、Repeated Bisectionと呼ばれるクラスタリング手法を採用しています。Repeated BisectionはクラスタリングツールCLUTOで使用されているクラスタリング手法で、データ集合を繰り返し2分割することでクラスタリングを実行します。K-means法などと比較して、高速に実行でき、また精度も良好なようです。

Repeated Bisectionではまずすべてのデータを1つのクラスタに格納し、その後は以下の1-4の処理を実行して、繰り返してクラスタを2分割してクラスタリングを行います。

  1. 分割するクラスタを1つ選択する(一番クラスタ内のまとまりが悪いものを選択)
  2. クラスタ中からランダムに2つ要素を選択し、それぞれが格納したクラスタを2つ作成する
  3. 元のクラスタ中の全ての要素に対し、2で選んだ要素との類似度を求め、類似度が高い方のクラスタに要素を追加する
  4. 2クラスタ間で要素の移動を行い、分割結果の洗練を行う(移動できる要素がなくなるまで続ける)

repeated bisection

ここで、2-4のプロセスだけに注目してみると、これはクラスタの中心を2つとしてK-means法を実行しているのと同じことをしています。つまりRepeated BisectionはK-meansを繰り返し実行しているだけなのです。

プロセス1でまとまりの悪いクラスタを選択するとき、プロセス4で要素を移動してクラスタの洗練を行うときは、クラスタのまとまり具合を評価する必要があります。このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほどクラスタの中心に凝集しているようになり、クラスタ中のデータが似た者同士の集まりである、と考えるわけです。ただし、クラスタ中の各要素と中心との類似度をまじめに全て比較するのは計算量も高くなってしまいます。実際には、この値はクラスタ中のベクトルをすべて足した複合ベクトルの長さと同値になり、そのため計算量も少なく評価値を求めることができます。評価値についてはCLUTOの論文に詳しく書かれているため、そちらをご参照下さい。

また、既存のクラスタリング手法には、確率・統計な枠組みを使用したより精度が高いと思われる手法が存在します。今回はシンプルさと実用的なスピードを主な目的としたためそれらは採用しませんでしたが、今後は他の手法も組み込み、実行時に自由に切り替えられるようにできればと考えています。

まとめ

軽量クラスタリングツールbayonのご紹介をさせていただきました。 bayonは容易に使用することができ、また実用に耐えられるだけのスピードを備えています。精度・機能面や、汚いソースコードなどまだまだ改善の余地がたくさんありますが、データの特徴をサッと調べたいときなどには皆様のお役に立てるかもしれません。もしご興味がある方がいらっしゃいましたら、ぜひご利用下さい!

例の冷却ファンを修理してもらいに秋葉原に行ったのですが、最近の同人ゲームのクオリティはすごいなあと感心していたら、その二階はもっととんでもないことになってて、ひとつ大人になってしまったmikioです。今回は、Tokyo Cabinetのテンプレート直列化機能を駆使して、たった100行のCプログラムでWebチャットシステムを実装してみます。

chatscreen

古式ゆかしいWebチャットシステム

10年くらい前にCGIスクリプトでチャットシステムを作るのが流行していたのを覚えている方も多いと思います。チャットログは現在のようにデータベースサーバに転送して格納するのではなく、ローカルファイルシステム上のファイルにCSVやTSVなどのフォーマットで格納したり、同じくローカルのDBMファイルに格納するのが主流でした。2ちゃんねるの「datファイル」もそのようなデータファイルの一種と言えるでしょう。

その頃から、CGIスクリプトと言えば、Perlなどのスクリプト言語を用いて実装するのがあたりまえでした。動作環境でコンパイル等の作業をする必要がなく、文字列処理の便利なライブラリが揃っていて、Cに比べれば高水準かつ直感的な記法で処理を記述できるからです。

今回は、そのようなCGIスクリプトによるチャットシステムを、敢えてC言語で実装してみます。しかも、Tokyo Cabinet(TC)の機能のみを用いて他のライブラリに一切依存せずにプログラミングを行います。そして、それがたった100行で記述できることを示すことによって、TCがCプログラマの友達であることをあらためてアピールしたいと思います。

まずはデモサイトにアクセスしてみてください。このシステムが今回の成果物です。ユーザの皆さんの最新の発言が時系列に並んで表示されています。ページ下端にある入力フォームにユーザ名と本文を入れて「post」ボタンを押すと、新しい発言を投稿することができます。

実際のソースコードは、C言語によるロジック実装がこちらで、テンプレートによるデザイン実装がこちらです。ロジック部分は100行以下(95行)に収まっています。

テンプレート直列化機能

このチャットシステムはWebインターフェイスなのでもちろんHTMLを出力するのですが、処理の論理的な流れを記述するプログラミング言語の中にHTMLという表現用の別言語を埋め込むと、二つの言語を同時に扱うことになって非常に厄介です。なので、ある程度以上の複雑さを持ったアプリケーションを実装する際には、テンプレートと呼ばれるファイルにHTMLを分離して保守性を高める努力をするのが普通です。テンプレート内の置換表現にプログラム側で生成したデータを流し込むことで最終的に出力されるHTMLを生成するのです。ここで言う「直列化(serialization)」とは、テンプレートや別個の変数として別次元に存在している複数のデータを、連続する一つの文字列(文字の連続した配列)として真っ直ぐに並べるということを意味しています。

企業などで組織的にWebアプリケーションを開発する場合、テンプレートはWebデザイナとかマークアップエンジニアとか呼ばれる人たちがHTMLやCSSやJavaScriptなどのノウハウを駆使して記述し、プログラム側はプログラマとかアプリケーションエンジニアとか呼ばれる人たちがPerlやRubyやPHPや各種データベースのノウハウを駆使して記述するのが一般的です。いわゆる「デザイン(プレゼンテーション)とロジックの分離」というやつです。mixiでも、HTML::Template::Proというライブラリの上に構築した独自のフレームワークを使って開発効率と保守性を向上させています。

さて、全てをCで書く宿命を背負っている私としては、各種スクリプト言語に便利なテンプレート直列化ライブラリがあるのにC言語にそれがないのが気に入らないわけです。Cだって立派にWebアプリケーションを書けることを世に示さねばなりません。Tokyo Cabinetにはスクリプト言語のstringやlistやhashに相当するデータ構造が既に実装されているわけですから、あとはそれを直列化してテンプレート内に埋め込む関数を実装すればテンプレート直列化ライブラリが完成するはずです。テンプレートの出力はXMLやHTML以外にもCSVやTSVやYAMLやJSONにすることができますので、ミドルウェア的な使い方も簡単にできてウマーな感じです。

使い方

テンプレートの構文の設計は基本的にはTemplate TookitというPerlのライブラリをパクっています。テンプレートに書いた文字列はそのまま出力に反映され、「[%」と「%]」に挟まれた部分だけは「ディレクティブ」と呼ばれる特殊な構文になります。最も単純なサンプルを以下に示します。

<html>
<body>
<h1>[% greeting %]</h1>
</body>
</html>

上記のファイルが「sample.tmpl」という名前で保存されていたとすると、以下のプログラムでそれを利用した出力を生成することができます。

#include <tcutil.h>
#include <stdio.h>

int main(int argc, char **argv){

  // テンプレートオブジェクトを作る
  TCTMPL *tmpl = tctmplnew();

  // テンプレート文字列をファイルからロードする
  tctmplload2(tmpl, "sample.tmpl");

  // テンプレートに渡す変数のハッシュを作る
  TCMAP *vars = tcmapnew();

  // 「greeting」というテンプレート変数に文字列を入れる
  tcmapput2(vars, "greeting", "Hello, World");

  // テンプレートを直列化する
  char *str = tctmpldump(tmpl, vars);

  // 直列化した文字列を出力する
  printf("%s", str);

  // 確保したリソースを開放する
  tcfree(str);
  tcmapdel(vars);
  tctmpldel(tmpl);

  return 0;
}

なんだか長ったらしいですね。生成された文字列よりもプログラムの方が長いんじゃ意味ねーだろと言われそうですが、実際のテンプレートはもっともっと長いので、それらをプログラムに埋め込むよりはかなり見通しがよくなっています。また、プログラマでなくてもテンプレートをいじれるので、保守性も向上していると言えるでしょう。

テンプレートの構文

テンプレートに渡す変数をテンプレート変数と呼びますが、ディレクティブに変数名を書くとそのテンプレート変数の値に置換されて直列化が行われます。また、以下のように変数の値にエンコード(エスケープ)を施したりデフォルト値を指定する機能もあります。ENCとDEFは同時に使うこともできます。エンコード方式は「XML」(XMLやHTMLのメタ文字を実体参照にエスケープ)と「URL」(URLのメタ文字をパーセントエンコードにエスケープ)があります。

  • [% varname ENC encoding %]
  • [% varname DEF "strings" %]

その他にも、以下の制御構文をディレクティブとして表現することができます。これらの制御構文はネストして使うことができます。

  • [% IF varname %] … [% END %]
  • [% IF varname EQ "strings" %] … [% END %]
  • [% IF varname RX "strings" %] … [% END %]
  • [% FOREACH varname tmpname %] … [% END %]

IFディレクティブは条件分岐で、条件が成立した場合にのみENDディレクティブまでのブロックを評価し、そうでなければ無視します。間にELSEディレクティブを書くと、条件が偽の場合にのみ評価されるブロックを記述できます。EQ演算子とRX演算子を指定すると、文字列の完全一致や正規表現の一致を条件とすることができます。

FOREACHディレクティブは、リストのテンプレート変数を受け取り、その個々の要素を一時変数に代入しつつ、要素の個数だけ、ENDディレクティブまでのブロックを繰り返して評価します。FOREACHの一時変数はそのブロックのローカル変数になるので、そのブロックの内部でのみ参照でき、外部への副作用はありません。

テンプレート変数にはハッシュを指定することもできます。その場合、ハッシュの要素を参照するには、「.」演算子を用います。例えば、「foo.bar」はfooという変数のbarという要素を参照します。「foo.bar.baz」などと連鎖させて指定することもできます。

変り種として、以下の設定ディレクティブもあります。設定ディレクティブで定義した変数はグローバルスコープでテンプレートの他の場所から参照することができます。さらに、関数 `tctmplconf’ によってプログラム側から参照することができます。

  • [% CONF varname "strings" %]

設定ディレクティブはアプリケーションのちょっとした設定項目をテンプレートに含めて楽をするための仕組みです。設定項目がそれほど多くない場合には設定ファイルをわざわざ分離するのもウザいので、テンプレートファイルと一括してしまおうということです。

典型的な例

典型的なWebアプリケーションでは、表示すべきレコードの集合をクエリによって特定し、該当するレコード群をデータベースから取り出し、それを直列化して表示するという処理を主体とします。通常、レコードは複数のコラムを持った構造体であり、それはハッシュとして表現することができます。したがって、テンプレートの典型的な仕事は、ハッシュのリストを直列化するということになります。

例によって社員名簿を考えてみましょう。各社員のレコードは社員番号と名前と性別と入社日と所属部署のコラムを持ちます。社員のリストがstaffsというテンプレート変数に入っているなら、以下のようなテンプレートで直列化することになるでしょう。

<table>
<tr>
<td>ID</td>
<td>名前</td>
<td>性別</td>
<td>入社日</td>
<td>所属部署</td>
</tr>
[% FOREACH staffs s \%]
<tr>
<td>[% s.id ENC XML %]</td>
<td>[% s.name ENC XML %]</td>
<td>[% s.sex ENC XML %]</td>
<td>[% s.hdate ENC XML %]</td>
<td>[% s.div ENC XML %]</td>
</tr>
[% END \%]
</table>

「staffs」の各要素が「s」という一時変数に代入されます。あとは、ハッシュである「s」の各要素を直列化するブロックを書けば、社員名簿全体を直列化することができることになります。各要素にはHTMLのメタ文字が含まれる可能性があるため、クロスサイトスクリプティングを防止するためにXMLエンコードを指定して直列化することが非常に重要です。なお、ディレクティブの末尾に「\」がついていますが、これは直後の改行を抑制する効果があります。HTMLは改行を無視するのでどうでもいい話ではありますが、ディレクティブを見やすくするために入れた改行が出力に反映されるのはちょっとダサいのでこの機能があります。

テンプレートオブジェクトにテンプレート変数の集合を与えるためにはハッシュがインターフェイスとして使われます。そして、そのハッシュにリストを与えるには、関数 `tcmapputlist’ を用います。さらにそのリストに社員レコードのハッシュを与えるには、関数 `tclistpushmap’ を用います。それらの関数はオブジェクトへのポインタをコンテナに格納します。注意すべきなのは、ポインタを関連付けているだけで、オブジェクトのコピーを行っているわけではないので、オブジェクトの寿命管理はあくまでアプリケーション側で行わなければならないということです。つまり、テンプレート変数を使い終えるまでは、そこに登録したオブジェクトは生存させておかねばならず、そしてテンプレート変数を使い終えた後に自分で破棄することが肝要です。

TCTMPL *tmpl = tctmplnew();
tctmplload(tmpl, ...);
TCMAP *vars = tcmapnew();
TCLIST *staffs = tclistnew();
...
// 社員レコードを設定する
TCMAP *staff = tcmapnew();
tcmapput2(staff, "id", "1");
tcmapput2(staff, "name", "空条承太郎");
tcmapput2(staff, "sex", "male");
tcmapput2(staff, "hdate", "20050321");
tcmapput2(staff, "div", "brd,dev");
...
// 社員リストに社員レコードを加える
tclistpushmap(staffs, staff);
// テンプレート変数に社員リストを設定する
tcmapputlist(vars, "staff", staffs);
...
char *str = tctmpldump(tmpl, vars);
...
tclistdel(staffs);
tcmapdel(vars);
tctmpldel(tmpl);

余談ですが、TCのオブジェクトシステムで定義される拡張可能文字列(TCXSTR)、配列リスト(TCLIST)、ハッシュマップ(TCMAP)、ツリーマップ(TCTREE)における各オブジェクトは、自身の型が何であるかを知る術を持っていません。したがって、汎用コンテナであるリストやハッシュに各オブジェクトへのポインタをvoid*型にアップキャストして格納した場合、元の型が何であったかは忘れられてしまうのです。そうすると、テンプレート側で変数varsのハッシュからテンプレート変数を取り出そうとした際に型の判断がつかずに困ったことになります。例えばテンプレートでFOREACHのパラメータに指定した変数がリスト以外のオブジェクトを参照していた場合には、実際にそれがリストなのか確認する術がないと、Segmentation Faultを引き起こす可能性があります。この問題に対処するために、オブジェクトのポインタをコンテナに入れる際には、必ず tclistpushlist、tclistpushmap、tcmapputlist、tcmapputmapのいずれかを用いることにしています。それらの関数は型情報とポインタを直列化したデータをコンテナのレコードとして格納するので、取り出す際に元の型が何なのかを知ることができるのです。それによって、ハッシュを文字列として評価した場合には “[map]” という文字列を出力して用法の誤りを検出できるようになり、また文字列をハッシュとして評価した場合には単に無視するようになっています。

チャットのテンプレート

ここまで材料が揃えば、実装に関して技術的な問題点はなさそうです。あとは設計さえまともであれば良いアプリケーションが作れるでしょう。ということで、チャットシステムの要件を整理します。

  • データベースに入っているチャットログを時系列に閲覧できる。
    • ログの各行は、投稿時間、発言者名、発言内容からなる。
    • 一般的なIRCクライアントのような表示にする。すなわち、1ページに最大16件のログを表示し、それらは最新のものを下端にし、順次古いものをその上に表示する。
    • 前ページと次ページのリンクによるページネーションで全てのログを閲覧できる。
    • 発言者名はわかりやすいように色分けする。
  • 発言者名と発言内容をテキストフィールドで入力して新規発言を投稿できる。
    • 発言時刻は現在時刻とする。
    • 投稿内容はデータベースに即座に記録され、チャットログに反映される。
    • 発言者名や発言内容の長さ制限は適当に設ける。

次に、Webデザイナの気持ちになって、テンプレートを書きましょう。変数を置換する変数ディレクティブ、条件分岐のIFディレクティブ、繰り返しのFOREACHディレクティブをまぜまぜしたHTMLを書くのです。実際のテンプレートのbody要素の部分だけ以下に抜粋します。

<body>
<div class="page">
[% IF prev %]<a href="[%url%]?page=[%prev%]">[PREV]</a>[% ELSE %]<span class="void">[PREV]</span>[% END %]
[% IF next %]<a href="[%url%]?page=[%next%]">[NEXT]</a>[% ELSE %]<span class="void">[NEXT]</span>[% END %]
</div>
<h1><a href="[%url%]">[%title ENC XML%]</a></h1>
[% FOREACH msgs msg \%]
<div class="msg">[%msg ENC XML%]</div>
[% END \%]
<hr />
<div class="chatlogs">
[% FOREACH logs log \%]
<div class="chatlog" id="log-[%log.pk%]">
<span class="d">[%log.d ENC XML%]</span>
<span class="a [%log.c%]">[%log.a ENC XML%]</span>
<span class="t">[%log.t ENC XML%]</span>
</div>
[% END \%]
</div>
<hr />
<form method="post" action="[%url%]">
<div class="writeform">
<input type="text" name="author" value="[%author ENC XML%]" size="16" title="author" tabindex="1" accesskey="1" />
<input type="text" name="text" value="" size="64" title="text" tabindex="2" accesskey="2" />
<input type="submit" value="post" title="post" tabindex="3" accesskey="3" />
</div>
</form>
<hr />
</body>

意外に短いですね。細かい装飾は全てCSSに任せることにして、XHTMLとして論理的に整理された構造であることのみを目指します。実際、このテンプレートはXHTML 1.0として完全に適格です。

チャットのロジック

最後にロジック層のプログラミングを行います(テンプレートを後回しにしたり同時に手がけたりする開発体制も一般的ですが)。まずはmain関数を以下に抜粋します。

int main(int argc, char **argv){

  // テンプレートオブジェクトを作る
  TCTMPL *tmpl = tctmplnew();

  // ファイルからテンプレートをロードする
  tctmplload2(tmpl, "tctchat.tmpl");

  // メモリプールオブジェクトを作る
  TCMPOOL *mpool = tcmpoolnew();

  // 実際の処理を行う
  proc(tmpl, mpool);

  // 確保したリソースを開放する
  tcmpooldel(mpool);
  tctmpldel(tmpl);

  return 0;
}

今回のテンプレートの話とはちょっとずれますが、main関数ではほとんど何もしないというのがCGIスクリプト開発におけるオススメのスタイルです。おそらく実用アプリケーションでは、生CGIではなくFastCGIを使うことになるので、その書き換えを簡単にできるようにしておくと幸せになれます。FastCGIではリソースの初期化とセッション毎のイベントループを明確に分ける必要があるので、前者をmain関数、後者をproc関数に予め分けておくと保守性が向上するのです。自分で書いたネットワークサーバに組み込む場合にもこの戦略は恩恵をもたらすでしょう。

上記の例で唐突に現れた「メモリプール」とは何でしょうか。テンプレートを使ったプログラミングでは、生存範囲の異なるオブジェクトを多数扱うことになるので、C++言語(STL)におけるスマートポインタのような仕組みが欲しくなることがあります。そのため、TCではメモリプールという機構を提供し、全てのオブジェクトの生存期間をそれと関連づけて管理するスタイルを推奨しています。FastCGI化やサーバ化の際には、イベントループ内にtcmpoolnewとprocとtcmpooldelを入れることで、各イベント毎に利用されて破棄されるリソースを一括して管理することができます。

proc関数の実装に進みましょう。処理の流れを大枠で言うと以下のようになります。

  • 入力を解析してパラメータを取り出す。
  • データベースを開き、更新クエリがあれば更新を行う。,
  • データベースに参照クエリを投げ、チャットログを読み出す。
  • チャットログをテンプレート変数に設定する。
  • テンプレートを直列化して文字列を取り出し、それを出力する。

細かい説明はソースコードのコメントとして行います。なお、頻出するtcmpoolxxxxxはメモリプールに関連付けてオブジェクトを作成する関数です。

static void proc(TCTMPL *tmpl, TCMPOOL *mpool){

  // 入力パラメータを格納するハッシュを作る
  TCMAP *params = tcmpoolmapnew(mpool);

  // HTTPのGETメソッドかPOSTメソッドかに応じて入力データを読み込む
  char *query = getenv("QUERY_STRING");
  const char *rp = getenv("CONTENT_LENGTH");
  if(rp){
    int clen = tclmin(tcatoi(rp), 1024 * 1024);
    query = tcmpoolmalloc(mpool, clen + 1);
    fread(query, 1, clen, stdin);
    query[clen] = '\0';
  }

  // www-form-urlencoded形式を個々の入力パラメータに分解
  if(query) tcwwwformdecode(query, params);

  // 必要なパラメータを取り出す
  const char *author = tcmapget4(params, "author", "");
  const char *text = tcmapget4(params, "text", "");
  int page = tcatoi(tcmapget4(params, "page", "1"));

  // テンプレートの設定からデータベースのパスを取り出す。
  const char *dbpath = tctmplconf(tmpl, "dbpath");
  if(!dbpath) dbpath = "casket.tct";

  // エラーメッセージ用リストを作る
  TCLIST *msgs = tcmpoollistnew(mpool);

  // データベースオブジェクトを作成する
  TCTDB *tdb = tctdbnew();
  // 専用のメモリプール内生成関数がないので、デストラクタをメモリプールに登録。
  tcmpoolpush(mpool, tdb, (void (*)(void *))tctdbdel);

  // POSTメソッドで、更新パラメータがある場合には更新を行う
  rp = getenv("REQUEST_METHOD");
  if(rp && !strcmp(rp, "POST") && *author != '\0' && *text != '\0'){

    // ライタとしてテーブルデータベースを開く
    if(!tctdbopen(tdb, dbpath, TDBOWRITER | TDBOCREAT))
      tclistprintf(msgs, "The database could not be opened (%s).", tctdberrmsg(tctdbecode(tdb)));
    tctdbsetindex(tdb, "", TDBITDECIMAL | TDBITKEEP);

    // 主キーとその他の属性を設定
    char pkbuf[64];
    int pksiz = sprintf(pkbuf, "%.0f", tctime() * 1000);
    TCMAP *cols = tcmpoolmapnew(mpool);
    tcmapput2(cols, "a", author);
    tcmapput2(cols, "t", text);

    // トランザクション内で更新を行う
    tctdbtranbegin(tdb);
    if(!tctdbputkeep(tdb, pkbuf, pksiz, cols)) tclistprintf(msgs, "The message is ignored.");
    tctdbtrancommit(tdb);

  } else {

    // 更新がない場合、リーダとしてテーブルデータベースを開く
    if(!tctdbopen(tdb, dbpath, TDBOREADER))
      tclistprintf(msgs, "The database could not be opened (%s).", tctdberrmsg(tctdbecode(tdb)));

  }

  // チャットログ用リストを作る
  TCLIST *logs = tcmpoollistnew(mpool);

  // データベースに投げるクエリを生成し、検索を行う
  TDBQRY *qry = tctdbqrynew(tdb);
  tcmpoolpush(mpool, qry, (void (*)(void *))tctdbqrydel);
  tctdbqrysetorder(qry, "", TDBQONUMDESC);
  tctdbqrysetlimit(qry, 16, page > 0 ? (page - 1) * 16 : 0);
  TCLIST *res = tctdbqrysearch(qry);
  tcmpoolpushlist(mpool, res);

  // 検索結果のオブジェクトを逆順にチャットログ用リストに格納する
  int rnum = tclistnum(res);
  for(int i = rnum - 1; i >= 0; i--){
    int pksiz;
    const char *pkbuf = tclistval(res, i, &pksiz);
    TCMAP *cols = tctdbget(tdb, pkbuf, pksiz);
    if(cols){
      tcmpoolpushmap(mpool, cols);
      tcmapprintf(cols, "pk", "%s", pkbuf);
      char date[64];
      tcdatestrwww(tcatoi(pkbuf) / 1000, INT_MAX, date);
      tcmapput2(cols, "d", date);
      const char *astr = tcmapget4(cols, "a", "");
      tcmapprintf(cols, "c", "c%02u", tcgetcrc(astr, strlen(astr)) % 12 + 1);
      tclistpushmap(logs, cols);
    }
  }

  // テンプレート変数に各種オブジェクトを登録する
  TCMAP *vars = tcmpoolmapnew(mpool);
  if(tclistnum(msgs) > 0) tcmapputlist(vars, "msgs", msgs);
  if(tclistnum(logs) > 0) tcmapputlist(vars, "logs", logs);
  tcmapprintf(vars, "author", "%s", author);
  if(page > 1) tcmapprintf(vars, "prev", "%d", page - 1);
  if(tctdbrnum(tdb) > page * 16) tcmapprintf(vars, "next", "%d", page + 1);

  // テンプレートを直列化して出力する
  char *str = tctmpldump(tmpl, vars);
  printf("Content-Type: text/html; charset=UTF-8\r\n");
  printf("\r\n");
  fwrite(str, 1, strlen(str), stdout);
  tcfree(str);
}

処理内容が多い割には簡潔に記述できていますよね。C言語でありながらC++やJavaに近いプログラミングスタイルになっているように思います。チャットプログラムの機能性としては上記だけではイマイチですが、100行だとこんなもんでしょう。二重投稿やクロスポストを防止する機能もあと10行ほどで書けるでしょうし、テンプレートを分ければRSS出力も可能です。TCのデータベースを開く代わりにTTのリモートデータベースを開けば、1万qps級のアクセスに耐えるチャットサーバとしても利用できるでしょう。テンプレート側にJavaScriptを仕掛ければXMLHttpRequestで自動更新する仕組みも作れるでしょう。

xxxxput2とかxxxxprintfとかいろいろな関数が出てきましたが、それらの多くはTCの隠しAPIとして定義されています。全てのAPIの完全な仕様はヘッダファイル `tcutil.h’ に書いてあるので、エキスパートなあなたはそちらを参照してください。C言語でWebアプリを作ろうと思ったときにあなたが欲しいと思った機能のほとんどは既に実装されていると思います。私が欲しいと思った機能のすべてをそこで実装していますので。

まとめ

Tokyo Cabinetのオブジェクトシステムとテンプレートによる直列化機能を用いてチャットシステムを簡単に構築する方法について説明しました。データベースからレコードを取り出して、それらをハッシュやリストを組み合わせてテンプレート変数にまとめて、最後にテンプレートに流し込んで単一の文字列として直列化するのです。オブジェクトの寿命管理にまつわる面倒はメモリプールをうまく使って片付けています。この一連のテクニックがあれば、各種のスクリプト言語での実装に引けをとらないWebアプリケーションを書けるはずです。

わざわざチャットシステムを作るためにテンプレート直列化ライブラリを作るなんて馬鹿げてると思われるかもしれません。しかし、チャット以外でも便利なんです。データベースに接続して取得したレコードをテンプレートに流し込むという、典型的なWebアプリケーションのエッセンスが詰まった例としてチャットシステムを取り上げたにすぎません。私の業務はWebアプリケーションそのものを書くというよりも、Webアプリケーションのバックエンドとして動作する社内WebAPIみたいなものを作ったりメンテしたりするのが主なのですが、そこでC言語のテンプレート直列化機能が欲しいと感じたのです。バックエンドではたいていCかC++を使って、いわゆるLLは使わないことが多いのですが、フロントエンドとの通信層の保守性を拡張性を高めるためにテンプレートが使えると便利なのです。Protocol BuffersとかThriftとか使えやという声も聞こえて来そうですが、既存のアーキテクチャを踏襲したまま部分部分の改修を行えるというのは大きな利点なのです。

あと、Tokyoシリーズの議論を行うためのCMSをこのテンプレート直列化ライブラリを使って作りはじめているので、近いうちにお披露目できたらと思います。

数日前にmemcached-1.4のリリース候補が出ましたので、今日はその最新版と、それを使ったメモリ節約の運用法を紹介します。厳密にいうと、ご紹介させていただくmemcachedのメモリ節約機能は1.3のbetaから存在し、過去にこちらで取り上げました

memcached-1.4.0-rc1

1.4 RCは基本的に1.3.* betaで発見・報告されたバグの修正やコードベースの改修が主な内容です。詳しいリリースノートはこちらになります。

ダウンロードはこちらです。

新しいバージョンのmemcachedはバイナリプロトコルの導入以外に地味に生まれ変わっています。例えばコードベースを時代の流れにあわせて、シングルスレッドサーバのビルドをとり除いたり、過去から問題視されていたグローバルロックたちの一つを排除し、SMPパフォーマンスを向上させたことなどです。また、このエントリーの本題であるmixiにとって嬉しい新機能も登場しましたので、それを次に紹介します。

CASを使わない人はメモリを節約しよう

memcachedにはCASをエミュレートした機能が存在し、CASの値を64ビット整数で表現しています。この値は今まではレコードを表現する構造体のメンバーとして記録されていました。現在はこのデータをダイナミックにメモリ上でアラインできるようになっています。したがって、CASを使わない設定 (-C オプション) でmemcachedを起動すると、1レコードに対して8バイトのデータを節約する事ができます。

1レコードにつき8バイトの節約と聞くと大した数字に聞こえないかもしれませんが、たったの1000万レコードでおよそ76MBのメモリ空間を節約する事ができます。この機能によるインパクトはウェブサービスの様に粒度の細かなキャッシュを多数つくるユースケースでは言うまでもなく大きいです。弊社でも検証してみたところ、嬉しい結果を得る事ができました。

余談ですが、この節約機能はもともと開発のロードマップには載っておらず、Wikipediaの中のパフォーマンス屋さんの要望で実現されました。

簡単な検証

私のブログで使った例と同じで恐縮ですが、まず10万個のKey/Valueをキャッシュする簡単なスクリプトを用意します。

#!/usr/bin/perl
 
use strict;
use warnings;
 
use Cache::Memcached;
use constant {
    NITEMS => 100000,
    KLEN   => 8,
    VLEN   => 16,
};
 
sub random_key {
    my @chars = ('a'..'z', 'A'..'Z', '0'..'9');
    my $buf = "";
 
    foreach (1..KLEN) {
        $buf .= $chars[rand @chars];
    }
    return $buf;
}
 
my $memc = Cache::Memcached->new ({
    servers => ['localhost:11211'],
    debug   => 0,
});
 
my $val = 'a' x VLEN;
 
for (1..NITEMS) {
    $memc->set(random_key, $val);
}

そしてこのスクリプトを新機能を適用していない以下のオプションで起動したmemcachedのプロセスに対して行います。

$ memcached -m 1024

そして以下がstatsコマンド(一部)の結果です。

...
STAT bytes 9000000
STAT curr_items 100000
STAT total_items 100000
STAT evictions 0
END

さて、次に新しいメモリ節約オプションを有効にしたサーバに同じスクリプトを走らせます。

memcached -m 1024 -C

そして結果です。

...
STAT bytes 8200000
STAT curr_items 100000
STAT total_items 100000
STAT evictions 0
END

ご覧のとおり、781KBのメモリを節約したことがわかります。これだけのメモリをさらにキャッシュにつかえるので、インフラのコストパフォーマンスが向上し、ウェブサービス屋さんにとって嬉しい機能であることがわかっていただけるかと思います。

まとめ

memcached-1.4.0-rc1と新しいオプションを紹介しました。メモリ節約オプションを有効にすると一つのキャッシュレコードに対して、8バイトのメモリ領域を節約することができ、塵も積もれば山となる論理で、結果的にインパクトのあるメモリ空間の節約になります。

このRCには開発者たちだけではなく、様々な人たちや組織のフィードバックがこめられているので、ぜひ試していただけたらなと思います。