遅めの夏休みで那須塩原に行ってきたmikioです。牧場でアルパカに触ってきたのですが、めちゃかわいかったです。さて今回は、Tokyo Tyrant（TT）にスクリプト言語Luaの処理系を組み込んで使う方法について解説します。

つか、Luaって何？

Lua（公式サイトによると「るーあ（LOO-ah）」と発音）という言語の名前は聞いたことがあっても、数あるマイナー言語のひとつと思って特に気にかけていない人も多いと思います。私もそうでした。しかし、今では、C言語使いの第2言語・第3言語として使うにはとても有望な言語だと思っています。

Luaに関する日本語の情報はまだ多くはないのですが、以下のサイトを順に読むとだいたいの雰囲気が掴めると思います。

• Lua で組んでみる
• Lua 5.1 リファレンスマニュアル

Luaは言語仕様が小さいので、とても習得しやすいです。上記のリファレンスマニュアルだけ読めばプログラミングに必要な情報はほとんど把握できるくらいです。事実、私もそれだけの知識でこの記事を書けるくらいはLuaを使いこなせるようになっています。

Luaによるプログラミングでは、Perlでいうところのハッシュや配列としての機能を兼ね備える「テーブル」という機構を使いこなすのが要点となります。Luaは手続き型言語ですが、テーブルのメンバに関数を持たせることでオブジェクト指向言語っぽく使うこともできます。

私が新しい言語を覚える時によくやるのが、DBM風のインターフェイスを実装することです。こんな感じになります。下記プログラムを test.lua というファイルに保存したら、lua test.lua コマンドで実行できます。

DBM = {}            -- クラス風に見せるためのオブジェクト
function DBM.new()  -- 上記オブジェクト内にコンストラクタを定義
   -- オブジェクトを作ってインスタンスフィールドを定義
   local obj = {
      data = {},   -- 実際のレコードを入れるテーブル
      iter = nil,  -- イテレータ用のインデックス
      num = 0,     -- レコード数のカウンタ
   }
   -- レコードを格納する関数（上書きモード）の定義
   function obj.put(self, key, value)
      if self.data[key] == nil then
         self.num = self.num + 1
      end
      self.data[key] = value
      return true
   end
   -- レコードを格納する関数（既存保持モード）の定義
   function obj.putkeep(self, key, value)
      if self.data[key] ~= nil then
         return false
      end
      self.num = self.num + 1
      self.data[key] = value
      return true
   end
   -- レコードを削除する関数の定義
   function obj.out(self, key)
      if self.data[key] == nil then
         return false
      end
      self.num = self.num - 1
      self.data[key] = nil
      return true
   end
   -- レコードの値を参照する関数の定義
   function obj.get(self, key)
      return self.data[key]
   end
   -- イテレータを初期化する関数の定義
   function obj.iterinit(self)
      self.iter = nil
   end
   -- イテレータから次のレコードのキーを取り出す関数の定義
   function obj.iternext(self)
      self.iter = next(self.data, self.iter)
      return self.iter
   end
   -- レコード数を取得する関数の定義
   function obj.rnum(self)
      return self.num
   end
   -- 作ったオブジェクトを返す
   return obj
end

-- クラス風オブジェクトのコンストラクタを呼び出してオブジェクトを作る
db = DBM.new()

-- レコードを格納する
db:put("one", "first")
db:put("two", "second")
db:put("three", "third")
db:putkeep("three", "fail")

-- レコードを検索する
print("one: " .. db:get("one"))

-- レコードを消す
db:out("one")

-- イテレータをしばく
db:iterinit()
while true do
   local key = db:iternext()
   if key == nil then
      break
   end
   print(key .. ": " .. db:get(key))
end

コンストラクタ（new）のあたりが少しわかりにくいかもしれませんが、function myfunc(arg){ … } という書き方は myfunc = function(arg){ … } と書くのと同義であるという仕様を考えると理解できます。DBMというオブジェクトのメンバnewとして関数を持たせて、その関数の中でdbというオブジェクトを作って、そのメンバとして各種の関数を持たせているということです。

後半の、オブジェクトを利用するところも面白いですね。メンバーを参照する「.」演算子の代わりに「:」演算子を使うことで、呼び出した関数のレシーバを暗黙の第一引数に指定してくれるところがニクい演出です（Perlのblessみたいなノリ）。

Luaを組み込む

DBMがよく「組み込み用データベース」などと称されるように、Luaもよく「組み込み用スクリプト言語」などと称されます。ここでいう「組み込み」とは、PC以外の小型ハードウェアに組み込むという意味ではなく、アプリケーションのプロセス内に処理系を組み込むという意味です。LuaはC言語用のAPIが美しく整備されているので、アプリケーションに組み込む作業がとても容易なのです。

余談ですが、TTに最初に組み込もうとしたのはRubyの処理系でした。同じくC言語用のAPIがきちんと整備されており、ユーザ人口やライブラリの充実度で優れているからです。しかし、動き出すところまで作って気づいたのは、現状の処理系（ruby-1.8.x）では、OSネイティブのスレッド機構（POSIX thread）を使うプロセスでRubyのAPIを呼び出すと、GCが走ったところで落ちてしまうことでした。今のところRubyは組み込み用途には向いていないようですが、今後の新しい処理系でこの問題が解決されれば、Ruby on Tyrantも公開しようと思います。

一方で、Luaの処理系はネイティブスレッドと併用して使うことができます。グローバル変数や静的変数を一切使っていないのでLuaのAPIの関数群はリエントラントです。ただし、Lua自体はANSI Cのみで実装されており、したがってネイティブスレッドに起因するレースコンディションの回避手段を自身では備えないので、ネイティブスレッドの排他制御はアプリケーション側の責任で行う必要があります。TTではワーカスレッド毎に別々のLuaの処理系のインスタンスを持たせることで、レースコンディションを解決しています。

上記で処理系のインスタンスと言っているものは、CのAPIでは lua_State という構造体で表現されます。Luaに対するすべての操作は lua_State へのポインタを介して行います。ということで、CのAPIによるHello Worldです（ビルドは、gcc -I/usr/include/lua5.1 luatest.c -o luatest -llua5.1 とかやってください）。

#include "lua.h"
#include "lualib.h"
#include "lauxlib.h"

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

  /* Luaのインスタンスを生成する */
  lua_State *lua = luaL_newstate();

  /* 標準ライブラリを読み込む */
  luaL_openlibs(lua);

  /* 文字列のLuaプログラムをチャンクとしてスタックに載せる */
  luaL_loadstring(lua, "print('hello world')");

  /* スタック上のチャンクを実行する */
  lua_pcall(lua, 0, 0, 0);

  /* Luaのインスタンスを削除する */
  lua_close(lua);

  return 0;
}

激烈に簡単ですよね！ 唐突に「チャンク」とか「スタック」とかいう用語が出てきて何だかむかつくという以外は、とてもわかりやすい構成になっていると思います。Luaの世界では全ての値はLuaスタックという入れ物に入れられることになっていて、Luaスタックから外された値はガベージコレクタによって消去されてしまいます。ただし、Luaスタックの値を、名前をつけた変数や、その変数がテーブルである場合はそのフィールドに、退避することもできます（つまり変数に値を代入するということ）。

さて、チャンクというのは、実行される文の塊のことで、関数と同じように扱うことができます。関数を実行する際には、関数をLuaスタックのトップに載せ、その上に関数に渡す引数を載せた状態で、lua_pcallというAPIを呼びます。つまり、print(’hello world’) というLuaのチャンクを読み込むのは、printという変数に代入されている関数をLuaスタックに載せてから、その上に ‘hello world’ という文字列を載せるという操作とほぼ同義です。実際にやってみましょう。

#include "lua.h"
#include "lualib.h"
#include "lauxlib.h"

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

  /* Luaのインスタンスを作る */
  lua_State *lua = luaL_newstate();

  /* 標準ライブラリを読み込む */
  luaL_openlibs(lua);

  /* グローバル変数 "print" の中身をスタックに載せる */
  lua_getglobal(lua, "print");

  /* 文字列 "hello world" をスタックに載せる */
  lua_pushstring(lua, "hello world");

  /* 引数1個の関数を呼び出す */
  lua_pcall(lua, 1, 0, 0);

  /* Luaのインスタンスを解放する */
  lua_close(lua);

  return 0;
}

激烈に簡単ですよね！ もはやCだけでLuaの処理系を操作できるようになっています。とにかく何をするにもLuaスタックに載せてから、Luaスタック上のレコードの数や番号を指定してその処理のためのAPIを呼び出すというスタイルを覚えてください。APIの詳しいことはリファレンスマニュアルに書いてあります。

Tokyo TyrantとLua

さて、いよいよ本題です。なぜTTにスクリプト言語を組み込んだのかと言えば、自分で使いたくなったりユーザの皆さんからの要望をいただいたりした機能の各々を提供する度に、TTの実装とプロトコルを拡張するのが面倒だからです。サーバ側にLuaで記述した任意の関数を登録できるようにして、クライアント側から関数名を指定して呼び出せるようにすれば、TT自身の実装を拡張する必要はなくなります。また、「キーと値を引数として渡して、実行結果を返す」というインターフェイスはどのデータベース操作にも共通しているので、「メソッド名のstringと、キーのstringと、値のstringを送信すると、その名前のメソッドにキーと値を渡して実行し、戻り値のstringが返信される」というプロトコルだけ用意しておけば、プロトコルを都度定義する必要もなくなります。

実際に使ってみましょう。まずはインストールです。Tokyo Cabint 1.3.10以降と、Lua 5.1以降を予めインストールした上で、Tokyo Tyrant 1.1.2以降をインストールします。TTのソースパッケージを展開したディレクトリの中で、以下の作業を行ってください（もし–enable-luaを指定しないとLuaが組み込まれないので注意）。

./configure --enable-lua
make
su
make install

次に、Luaスクリプトを作ります。myfunc.lua というファイルに以下のプログラムを記述してください。単にキーと値をコロンで区切った文字列を返す関数です。

function echo(key, value)
   return key .. ":" .. value
end

Luaスクリプトを読み込ませてデータベースサーバを起動します。

ttserver -ext myfunc.lua

別の端末を開いて、先ほど定義した「echo」関数を呼んでみます。キーとして「foo」、値として「bar」を渡します。

tcrmgr ext localhost echo foo bar

「foo:bar」が表示されたら成功です。激烈に簡単ですよね！ では次は、こんなスクリプトを読み込ませて起動してみてください。キーに対応した値を10進数値として加算する関数です。

function incr(key, value)
   value = tonumber(value)
   if not value then
      return nil
   end
   local old = tonumber(_get(key))
   if old then
      value = value + old
   end
   if not _put(key, value) then
      return nil
   end
   return value
end

ソースコードを見ればどんな処理をするのかだいたい検討つきますよね。実際に呼び出して使ってみましょう。

$ ./tcrmgr ext localhost incr foo 1
1
$ ./tcrmgr ext localhost incr foo 2
3
$ ./tcrmgr ext localhost incr foo 3
6
$ ./tcrmgr ext localhost incr foo 4
10

TTによるビルトイン関数

上述のサンプルでは、「データベースから古い値を取り出して、付与の値と加算して、結果の値をデータベースに格納するとともに、それを返す」という処理を行っています。データベースの操作は、「_」で始まるビルトイン関数によって行います。ビルトイン関数としては以下のものが提供されています。引数keyやvalueには文字列でも数値でも指定できます。

• _put(key, value) : レコードを格納する（上書き）
• _putkeep(key, value) : レコードを格納する（既存値保持）
• _putcat(key, value) : レコードを格納する（既存値連結）
• _out(key) : レコードを削除する
• _get(key) : レコードの値を取得する
• _vsiz(key) : レコードの値のサイズを取得する
• _iterinit() : イテレータを初期化する
• _iternext() : イテレータから次のレコードのキーを取り出す
• _vanish() : 全レコードを削除する
• _rnum() : レコード数を取得する
• _size() : データベースのサイズを取得する

データベース操作ではありませんが、数値とバイナリ文字列を相互変換するためのビルトイン関数も提供されています。_packは引数がテーブル（配列）である場合はその要素を対象として処理を行い、引数が数値である場合はそのものを対象とします。引数自体を複数指定して配列を表現してもOKです。

• _pack(format, array, …) : フォーマットに基づいて数値リストをバイナリ文字列に変換
• _unpack(format, binstr) : フォーマットに基づいてバイナリ文字列を数値リストに復元

フォーマットには以下の変換文字が利用できます。PerlやRubyやPythonのpack/unpackとはちょっと違うので注意してください。

• c : 符号付き8ビット値
• C : 符号なし8ビット値
• s : 符号付き16ビット値
• S : 符号なし16ビット値
• i : 符号付き32ビット値
• I : 符号なし32ビット値
• l : 符号付き64ビット値
• L : 符号なし64ビット値
• n : 符号なしネットワークバイトオーダ16ビット値
• N : 符号なしネットワークバイトオーダ32ビット値
• M : 符号なしネットワークバイトオーダ64ビット値
• w : 非負整数のBERエンコード

Perl等と同じように変換文字の後ろに繰り返し回数やワイルドカードを指定することは可能です。例えば、変数arrayの配列に入っている数値を、1個の符号なし8ビット数値を先頭につけ、その後ろに4個の符号付きネットワークバイトオーダ32ビット数値をつけ、その後ろに残り全部の数値をBERエンコードでつなげたい場合は、binstr = _pack(”CN4w*”, array) とします。もちろん、それを復元するには、array = _unpack(”CN4w*”, binstr) とすればよいのです。データベースに入れるデータは文字列（バイナリでもOK）に直列化する必要があるのですが、「1234」などのASCII文字列で表すよりも、変域に合わせたバイナリ表現で表した方が空間効率がよくなります。ということで、真面目なユースケースにおいては、_pack/_unpack を使いこなすのはかなり重要です（Luaの標準ライブラリにはpack/unpackがないから自分で作るハメになってしまった）。

Luaの処理系のインスタンスをネイティブスレッド毎に持っている関係で、Luaのグローバル変数を動的に生成した場合、セッション毎にそのグローバル変数があったりなかったりする事態となってしまいます。つまりLuaのグローバル変数はロード時に定義して定数としてしか利用できないということです。となると、セッション間で共有すべきデータはデータベースに格納するのが基本となるわけですが、抜け道として、セッション間のちょっとしたデータ共有のためのスタッシュという機構を用意しています。スタッシュはTCのオンメモリデータベースとして実装されています。

• _stashput(key, value) : スタッシュにレコードを格納する
• _stashout(key) : スタッシュのレコードを削除する
• _stashget(key) : スタッシュのレコードの値を取得する

「_begin」および「_end」というユーザ定義関数がある場合、PerlのBEGINブロックやENDブロックのように、サーバの起動時や終了時に引数なしでそれらの関数が呼ばれます。Luaの処理系のインスタンス数（＝ネイティブスレッド数）がいくつであっても「_begin」と「_end」は1回しか呼ばれないのがポイントです。これらはスタッシュの初期化処理や終了処理に便利です。

ところで、サンプルプログラムで定義した「incr」関数の処理において、「_get」と「_put」の間に他のスレッドが同じレコードの操作をしてしまったら値の整合性がとれなくなって困ります。つまり「incr」関数はレコードロックで保護して実行する必要があります。レコードロックで保護しつつLua関数を呼ぶには、以下のようにします。

tcrmgr ext -xlr localhost incr foo bar

なお、「-xlr」の代わりに「-xlg」とするとグローバルなロックをかけることもできます。レコードロックもグローバルロックもアドバイザリロックにすぎないことに注意してください。つまり全てのクライアントが該当のロックをかけて関数を呼び出すということが整合性の前提となります。

この解説ではクライアントとしてtcrmgrコマンドを使っていますが、もちろんTTのAPI（リモートデータベースAPI）でも同様の操作はできます。PerlやRubyやJavaのクライアントライブラリも気が向いたら作っていく所存です。

High and Low

突然ですが、High and Lowという古典的なゲームをご存知でしょうか。次に出される数値が今の数値より大きいか小さいかを当てるゲームです。それをTTとLuaで実装してみましょう。以下のようなフローを考えます。

• 「start」という関数で、ユーザ名と所持金を登録するとともに、今の値を返す。キーはユーザ名、値は所持金。
• 「high」または「low」という関数で、大小と掛金を表明するとともに、結果と今の値を返す。キーは名前、値は掛金。掛金が0以下になるか、セッションが5ラウンド過ぎたらゲームオーバー。
• 「over」という関数で、セッションを破棄する。キーはユーザ名、値は無視。

セッションはユーザ名をキーとして管理し、キーに「:r」を接尾させたレコードでラウンド数を、キーに「:n」を接尾させたレコードで今の値を、キーに「:m」を接尾させたレコードで所持金を記録します。ここまで決まれば、あとは実装するだけです。

NUMRANGE = 100
MAXROUND = 5
math.randomseed(os.time())

function start(key, value)
   value = tonumber(value)
   if not value or value <= 0 then
      return "error: invalid value"
   end
   if not _putkeep(key .. ":r", 1) then
      return "error: already started"
   end
   local num = math.random(NUMRANGE)
   _put(key .. ":m", value)
   _put(key .. ":n", num)
   return "Welcome, " .. key .. ".\\n" ..
      "The current number is " .. num .. ".\\n" ..
      "Your money is " .. value .. ".\\n" ..
      "Round 1 Bet!\\n"
end

function high(key, value)
   return do_bet(key, value, true)
end

function low(key, value)
   return do_bet(key, value, false)
end

function over(key, value)
   if _vsiz(key .. ":r") < 0 then
      return "error: not started"
   end
   _out(key .. ":r")
   _out(key .. ":m")
   _out(key .. ":n")
   return "Good Bye!"
end

function do_bet(key, value, ishigh)
   value = tonumber(value)
   if not value or value <= 0 then
      return "error: invalid value"
   end
   local round = tonumber(_get(key .. ":r"))
   if not round then
      return "error: not started"
   end
   local money = tonumber(_get(key .. ":m"))
   if round > MAXROUND or money < 1 then
      return "error: already finished"
   end
   if value > money then
      value = money
   end
   local num = tonumber(_get(key .. ":n"))
   local newnum = math.random(NUMRANGE)
   local cmp = "even"
   local res = "lost"
   if newnum > num then
      cmp = "high"
      if ishigh then
         res = "won"
      end
   elseif newnum < num then
      cmp = "low"
      if not ishigh then
         res = "won"
      end
   end
   round = round + 1
   if res == "won" then
      money = money + value
   else
      money = money - value
   end
   _put(key .. ":r", round)
   _put(key .. ":m", money)
   _put(key .. ":n", newnum)
   local call = "Round " .. round .. " Bet!\\n"
   if round > MAXROUND or money < 1 then
      call = "Game Over!\n"
   end
   return "The currnet number is " .. newnum .. ".\\n" ..
      newnum .. ":" .. num .. " (" .. cmp .. ") ... You " .. res .. "!\\n" ..
      "Your money is " .. money .. ".\\n" ..
      call
end

エラー処理なども織り込んでいるのでちょっと長いソースになりましたが、フローは単純なので追いやすいと思います。また余談ですが、Luaのソースを書いていると、JavaScriptとRubyを混ぜたような感じがしてきます。C、C++、Perl、Ruby、Java、JavaScriptあたりに慣れた人ならばとっつきやすいですよね。個人的には、EmacsのLuaモードの標準インデントが3なのに萌えました。それでは、実際に遊んでみましょう。

$ tcrmgr ext -xlr localhost start mikio 10000
Welcome, mikio.
The current number is 30.
Your money is 10000.
Round 1 Bet!

$ tcrmgr ext -xlr localhost high mikio 5000
The currnet number is 54.
54:30 (high) ... You won!
Your money is 15000.
Round 2 Bet!

$ tcrmgr ext -xlr localhost low mikio 3000
The currnet number is 9.
9:54 (low) ... You won!
Your money is 18000.
Round 3 Bet!

$ tcrmgr ext -xlr localhost high mikio 15000
The currnet number is 65.
65:9 (high) ... You won!
Your money is 33000.
Round 4 Bet!

$ tcrmgr ext -xlr localhost low mikio 10000
The currnet number is 75.
75:65 (high) ... You lost!
Your money is 23000.
Round 5 Bet!

$ tcrmgr ext -xlr localhost low mikio 10000
The currnet number is 65.
65:75 (low) ... You won!
Your money is 33000.
Game Over!

$ tcrmgr ext localhost over mikio
Good Bye!

ちゃんと動きましたよね？ 冗談のようなプログラムですが、ロバストでスケーラブルな作りになっています（本当に真面目にやるなら、start関数で秘密のセッションキーを生成して返すべきですが）。いずれも処理能力に定評のあるTokyo TyrantとTokyo CabinetとLuaで構成されたシステムですから、おそらく10万人が同時にプレーしても大丈夫でしょう。

足あとデータベース

もうちょっと実用的な例も考えてみました。mixiの足あとデータベースです。単純なIDのリストを記録するだけならTTのputrttコマンドを用いるだけで実現できるのですが、mixiの足あとデータベースはもうちょっと小賢しい仕様なので、サーバ側でLuaが使いたくなります。その仕様とは、「同じユーザが同じ日に何度も訪問してきた場合、その日の最終の訪問時刻のみを記録し、それ以前の時刻のレコードは消去する」というものです。このようなad hocな要求をいちいちサーバの実装とプロトコルに反映していたら私の身が持ちません。そこでLuaの登場なのです。以下のようなフローを考えます。

• 「add」という関数で、被訪問ユーザと訪問ユーザのIDを指定して、足あとを記録する。キーは被訪問ユーザのID、値は訪問ユーザのID。
• 「list」という関数で、被訪問ユーザのIDを指定して、足あとのリストをTSV形式で取得する。キーは被訪問ユーザのID、値は最大取得件数。

足あとは、ユーザIDとタイムスタンプのペアを各々int型で表現し、それを最大60個分連結したバイナリデータとして保存します。引数や戻り値には10進数の文字列を使うが、保存はバイナリデータで行うことによって、効率性と保守性を両立させる作戦です。ここまで決まれば、あとは実装するだけです。

MAXPRINT = 60

function add(key, value)
   key = tonumber(key)
   value = tonumber(value)
   if not key or not value or key == value then
      return nil
   end
   local ksel = _pack("i", key)
   local time = os.time()
   local date = os.date("*t", time)
   date.hour = 0
   date.min = 0
   date.sec = 0
   local mintime = os.time(date)
   local vsel
   local ary = _unpack("i*", _get(ksel))
   local anum = 1
   if ary and #ary > 0 then
      local nary = {}
      local nidx = 1
      local nidxmax = MAXPRINT * 2 - 1
      for i = 1, #ary, 2 do
         if ary[i] ~= value or ary[i+1] < mintime then
            nary[nidx] = ary[i]
            nary[nidx+1] = ary[i+1]
            nidx = nidx + 2
         end
      end
      vsel = _pack("i*", nary, value, time)
      anum = (#nary / 2) + 1
      if anum > MAXPRINT then
         vsel = string.sub(vsel, MAXPRINT * -8)
         anum = MAXPRINT
      end
   else
      vsel = _pack("ii", value, time)
   end
   if not _put(ksel, vsel) then
      return nil
   end
   return anum
end

function list(key, value)
   key = tonumber(key)
   value = tonumber(value)
   if not key then
      return nil
   end
   if not value or value < 1 then
      value = MAXPRINT
   end
   local result = ""
   local ksel = _pack("i", key)
   local ary = _unpack("i*", _get(ksel))
   if ary and #ary > 0 then
      for i = #ary - 1, 0, -2 do
         if value < 1 then
            break
         end
         result = result .. ary[i] .. "\\t" .. ary[i+1] .. "\\n"
         value = value - 1
      end
   end
   return result
end

バイナリデータとの相互変換にビルトイン関数 _pack/_unpack が活躍します。最大60個の制御のためにstring.subで前方を切り捨てているのもちょっとした工夫ですね。それでは、実際に動かしてみましょう。今回もレコードロックが必要なので「-xlr」をつけて呼び出しています。

$ ./tcrmgr ext -xlr localhost add 1 123
1
$ ./tcrmgr ext -xlr localhost add 1 456
2
$ ./tcrmgr ext -xlr localhost add 1 789
3
$ ./tcrmgr ext -xlr localhost add 2 987
1
$ ./tcrmgr ext -xlr localhost add 2 654
2
$ ./tcrmgr ext -xlr localhost add 2 987
2
$ ./tcrmgr ext -xlr localhost list 1
789     1222150402
456     1222150398
123     1222150392

$ ./tcrmgr ext -xlr localhost list 2
987     1222150419
654     1222150416

このプログラムは冗談でなくかなり実用を意識して作っています。ベンチマークテストを動かしたところ、20000QPS以上の性能は出るようなので、おそらくmixiの本番で運用しても耐えるでしょう（必然性がないのでやらないけど）。TTの起動時にレプリケーションの設定をしている場合、ビルトイン関数「_put」や「_out」などによる更新ももちろん更新ログとして伝播するので、マスタにaddしてスレーブからlistするという使い方もできます。

まとめ

スクリプト言語Luaについて簡単に説明し、それをTTに組み込んで使ってみました。Luaは実用に耐える機能と性能と拡張性を備えた言語なので、ビジネスシーンでもこれからメジャーになってくる予感がします。データベースサーバでスクリプト言語を動かすなんて効率が悪いと考える人も多いかもしれませんが、CPUの並列処理性能がどんどん進化しつつあるこのご時勢では、DBM等のI/O部分（通常ここがボトルネック）のレイテンシに比べれば、スクリプト言語によるレイテンシなんてのは無いみたいなもんです。並列性が高ければたとえパフォーマンスが芳しくなくてもスループットは出ます。しかもLuaのパフォーマンスはスクリプト言語の中ではかなり好成績です（ベンチマーク）。よって、もっとLuaを使いたおしましょう。

Luaを組み込む前のTTは単なるハッシュデータベースのネットワークインターフェイスだったのですが、Luaのおかげで今やアプリケーションコンテナっぽく使うこともできるようになったわけです。mixiのようなWebサイトのバックエンドとしても、例で紹介した足あとデータベースの他に、キューサービスやキャッシュサービスなどとして実用になると思っています。実際にTTとLuaを使ったソリューションができたらまたここで紹介します。

追伸1：Tokyo (Cabinet|Tyrant|Dystopia)のコミュニティをmixi上ではじめました。現状唯一のサポートの場なので、興味のある方はご参加ください。

追伸2：Linuxでしか動かなかったTokyo Tyrantですが、epollのエミュレーション層をkqueueを使って書いたので、FreeBSDとMac OS Xでも動くようになっています（多分）。該当のプラットフォームの方はぜひ使ってみてください。

はじめまして。開発部アプリケーション開発グループの向田（むかいだ）です。今回は、mixiの中では珍しいmixi有料サービスについて紹介したいと思います。堅い内容かもしれませんが、最後までお付き合いいただければと思います。また、今回の内容はPC版の有料サービスに限定させていただきますのでご了承ください。

■はじめに

mixi有料サービスと言っても、以前よりmixiプレミアムは存在していました。しかし、当時はお支払い用に登録していただいた決済情報が、mixiプレミアムのサービスだけでしか利用できず、今後有料サービスを追加したい、様々なサービスを提供したいという思いのさまたげになっていました。そこで、下記コンセプトを元に課金処理部分を再構築し、2008年4月1日より新たにスタートしました。

◇コンセプト

• クライアントサービスとの疎結合
• セキュリティリスクの軽減
• 利便性の向上

1. クライアントサービスとの疎結合

これまではmixiプレミアムだけで利用可能だった課金処理部分を課金システムとして独立させました。具体的には下記の通りです。

• 決済情報登録：サービスに関係無く、お支払い用の決済情報を登録できるようにしました。
• 決済：決済完了時には内部APIを通じクライアントサービス側へ必要な処理が施されるようにしました。
• 状態確認：通常のmixiとの連携では、内部APIを用いてサービスの契約状態を判定するようにしました。

図：アーキテクチャ 

2.セキュリティリスクの軽減

堅牢な構成のネットワークに専用サーバを設置することも当然ですが、システムとしては一層の強化を図るべく、情報保持という視点に立ち見直しを行いました。具体的には、弊社と決済代行会社との間で、専用の外部APIを通じ情報の登録、照会を行うようにすることにしました。この対応により弊社ではクレジットカード情報を保持する必要がなくなり、セキュリティリスクが軽減されました。

3.利便性の向上

こちらがmixi有料サービスのトップ画面となります。これまでには無かった「ご利用サービス一覧」で契約中のサービス一覧が、左メニュー「ご利用履歴照会」よりこれまでの利用履歴が閲覧可能となりました。

図：一覧や履歴の画面

■課金パターンと有料サービス

弊社の課金パターンとしては、現在２つあります。
一度の登録で毎月継続して課金を行う「月額課金」というパターンと商品を購入する度に課金を行う「都度課金」というパターンです。それぞれで利用可能なサービスは下記の通りとなります。

◇月額課金
月額課金で利用可能なサービスとして代表的なものは、これまでも提供されていた「mixiプレミアム」です。さらに7月から「ミュージックプラス」という有料サービスが追加されました。

◇都度課金
都度課金で利用可能なサービスは、「ギフトソング」です。こちらも7月より有料サービスとして追加されました。

mixi内にも徐々に有料サービスが増えているのがご理解いただけるかと思います。ラジオのように音楽が聴けるミュージックプラスや、聴いている音楽、好きな音楽をマイミクへ贈ることができるギフトソングサービスなど、他サービスへ課金処理を提供するという目的を果たすことができていると思います。

■外部脆弱性診断

課金サイトである為、画面遷移の制限なども組み込んでいますが、セキュリティリスクが高いということで、外部専門会社に脆弱性の診断をしていただきました。今後の課題を指摘いただくなど、専門家によるテストや監査が有用なことがわかりました。また、技術的にも非常に興味深く勉強になりました。以降の開発に役立てたいと思っています。

■内部統制

最近は定着しつつある内部統制。弊社も例外ではありません。内部統制については、wikipediaより抜粋致しますが、簡単には下記の通りとなります。

・会社自らが業務の適正を確保するための体制を構築していくシステムを指す。
・広義には、会社の存在の目的を果たすために経営者が整備するものである。
・狭義には法律行為や財務報告における不正や誤りを防止するために経営者が主体となって整備するものである。
・具体的には、組織形態や社内規定の整備、業務のマニュアル化や社員教育システムの運用、また規律を守りつつ目標を達成させるための環境整備、そして財務報告や経理の不正防止策があげられる。

実は、開発へ着手した当初、弊社内では内部統制についてそれほど重要視されていませんでした。というよりも、その準備段階にあったようでして、本格的な適用はありませんでした。現在は、課金に関連するシステムが内部統制の対象となり、仕様の整理から開発変更管理までのフローやルールを構築しています。具体的には以下の通りです。

• 社内規定の見直しや細則の整備
• システム変更管理に必要な業務フローの制定とドキュメントの整備
• ログ完全性保障のために専用のログサーバを設置

他にもありますが、これまでのやり方を大きく変えることなく、いかに溶け込むような体制が作れるかを意識しています。苦労する部分でもありますが、効率を悪くしては意味がありません。会社規模が大きくなるとこういった取り組み、仕組み作りがとても大切になってきます。

■合弁会社設立

先日、弊社と「三菱商事株式会社様」との間で「決済システム及びサービスを提供する合弁会社設立」を合意致しましたのでお知らせ致します。
以下、引用となります。

　「株式会社ネクスパス」においては、1,500万人を超えるソーシャル・ネットワーキング サービス(SNS)『mixi』のユーザーに対して、利便性の高い決済システムを提供いたします。また、将来的には、決済システム及びサービスを他のウェブサービス事業者にも提供することで利用拡大を図ってまいります。
三菱商事が有する金融ノウハウやリアルな世界での小売・流通企業との取引先ネットワークと、日本最大のSNSである『mixi』が有するインターネットにおけるコミュニケーションサービスの運営ノウハウを組み合わせることにより、これまでに無いユーザー視点のサービスを立ち上げ、益々伸張するウェブサービスの発展をリードすべく取り組んでまいります。

あまり多くを語れませんが、というよりも知らないだけですが、新たな有料サービスが始まりそうですね。

■まとめ

今回、課金処理部分を分離し提供することで、新しいmixi有料サービスの追加を実現することができました。また、同様にユーザー利便性の向上も多少なりとも図ってまいりました。

目新しい工夫や技術はありませんが、mixi有料サービスの実情については、ご理解いただけたのではないでしょうか。特に今回は、脆弱性診断や内部統制への取り組みを実施し、mixiとしてより安全なシステムの提供を心掛けているという「知られざる裏側」を紹介させていただきました。

今後は、合弁会社設立でもわかるかと思いますが、これまで以上の決済システム、サービス提供を目指してまいりますので、少しでも注目いただければと思います。

朝のジョギング生活を絶賛継続中ですが、あまり体重が減らなくてショボンヌなmikioです。さて今回は、Tokyo Dystopiaを使った検索機能「かんたん友人検索」の設計と実装についてお話しします。

全体の戦略

Tokyo Dystopia（TD）は単なる全文検索用のインデックス管理ツールです。多数の文字列の中から特定のパターンを含んだ文字列を特定する処理を高速化することはできますが、逆に言えばそれしかできないのです。住所を市区町村単位で限定して結果を絞り込むとか、ログイン時間が近い順に並び替えるとかの高機能は備えていません。Hyper Estraierにはそういったアプリケーション寄りの機能を持たせていましたが、逆にコードベースが肥大化して保守や最適化がしにくくなってしまいました。その反省を踏まえて、今回は、「全文検索による対象の絞り込み」だけはTDにやらせて、その他の機能は全て専用に書き下ろすことにしました。

かんたん友人検索のシステムを構成する機能を大別すると、プロセス管理、ネットワークインターフェイス、全文検索、属性による絞り込み、適合度によるソート、クエリの分散と結果のマージなどがあります。この記事では、まずは全ての機能で中核的な役割を果たすTokyo Cabinet（TC）に行った改良について説明し、次に各種のインデックスの構造と構築方法について触れて、さらに検索処理の具体的な手順を示し、最後にアーキテクチャ全体と個々の実装を概観します。

■ 機能構成

TCの性能を大幅にアップ

TDはTCをストレージに用いる検索システムですが、そのTCの性能を向上させることでTDの性能も向上させました。従来（1.2系列）までのTCは、reader/writerロックで排他制御を行っていました。すなわち参照（read）は共有ロックを用いて参照スレッド同士は同時に処理を行わせ、一方で更新（write）は排他ロックを用いて他のスレッドをブロックして独占的に処理を行わせるというモデルです。1.3.1では参照も更新も共有ロックを用いるようになり、openやcloseなどのメタな操作以外は全て同時に行えるようにしました。

ところが、ベンチマークテストをしてみると、ユーザランドでのロックをあらかた取り払っても、スループットが以前とあまり変わらないことがわかりました。Web等でいろいろ調べたところ、ファイルの読み書きに用いているpreadやpwriteの並列処理性能が（少なくともLinuxにおいては）あまり高くないのではないかという説が浮上しました。そこで、同記事に倣ってmmapを使うようにしたところ、単一スレッドによるパフォーマンスも複数スレッドのスループットも劇的に改善しました。100万レコードの読み書きの性能（単位は秒）を以下に示すとおり、今やTCの性能はCDBに匹敵するところまで来ています。

■ 旧バージョンとの比較

■ DBMファミリーとの比較

TCの数え上げモード

検索やデータマイニングのシステムを実装する際には、様々な事象の頻度を高速に数え上げる必要に迫られることが多くあります。例えば、各ユーザのログイン頻度を数えたり、各ページの被閲覧数を数えたり、各単語の出現頻度を数えたりする処理です。そこでは、事象の識別子（ユーザIDや日記IDや単語の文字列）をキーとして、それに該当する出現回数を値としたハッシュデータベースを作り、キーを指定して値を増加させる操作が繰り返されます。この操作を効率化するために、TCの各種データベースに、以下のようなメソッドを追加しました（もちろんCのAPIでは関数として提供されます）。すなわち、キーに対応づけたint型またはdouble型の数値をアトミックに加算し、戻り値として加算後の値を返します。

int DB::add_int(string key, int num);
double DB::add_double(string key, double num);

上記のメソッド群がない場合、getして値を取り出してからそれを加算した結果の値をputをすることになるのですが、その方法だと2回演算が必要であるのみならず、アトミック性を確保するためにアプリケーション側でロックをかけなければならないので、大変効率が悪くなってしまいます。地味な機能ではありますが、こういう改善が後でジワッと効いてくるのです。なお、Tokyo Tyrant（TT）のバイナリプロトコルでも数え上げができるようになったので、同じような悩みのある方はぜひチェックしてみてください。

全文検索用転置インデックス

検索を高速に行うには、その過程で参照するデータを効率的に取得できるように予めインデックスを作っておく必要があります。ユーザの名前や自己紹介文を対象とした全文検索を行うので、mixi本体のデータベースに問い合わせて、全ユーザのデータを取得し、それをTDのユーティリティで転置インデックスに変換します。mixi本体はMySQLのデータベースなので、PerlのプログラムでDBIを使って接続して、結果はTSV形式のファイルとしてインデクシング用のマシンに保存します。あとはTDの付属のコマンドにそれを流し込むだけです。現状では転置インデックスの更新は24時間に1回のペースで行っています。転置インデックスの構造については以前の記事を参照してください。

属性データベース

かんたんユーザ検索では「性別」「年齢」「現住所」「出身地」による絞り込みを行うことができますが、それらはいずれもカーディナリティ（ばらつき）が低い属性なので、インデックスによって絞り込みを高速化することは現実的ではありません。「年齢」はカーディナリティが比較的高いと思われるかもしれませんが、「18歳から90歳まで」のような条件を入力される可能性もあるので、やはりインデックスは期待どおりに機能しないのです。

となると、候補の全件に対して逐次的に属性の照合を行うしかありません。それを高速化するために、全属性データをメモリに載せて、ユーザIDを添字にした固定長領域の配列として参照できるようにしました。実装は簡単で、インデックス作成時に全ユーザの属性を格納した構造体配列をそのまま直列化してファイルに書き込み、検索時にはそれをmmapして参照するようにしています。TCに固定長データベースというAPIセットがありますが、それとほぼ同じ発想です。

■ 固定長配列のイメージ

スコアデータベース

かんたん友人検索の最大の特徴である適合度順の算出処理においては、現住所や最終ログイン時刻やマイミクシィの数などをスコア情報として利用します。これらの情報は検索されるユーザごとに一定で、検索操作を行うユーザによって変わるわけではないので、静的なスコア情報と考えられます。後述するマイミクシィグラフを使った動的なスコア情報と好対照です。現住所などはMySQLのデータベースから取得し、TTによる最終ログイン時刻データベースから取得します。これらの取得はインデックスを作成する前後に行うのが原則ですが、最終ログインデータベースは結構な負荷がかかっているので、負荷がピークになる時間帯（22時〜26時くらい）は避けるように制御しています。

マイミクシィグラフ非正規化データベース

適合度順の精度をさらに高めるために、マイミクシィ関係のグラフ構造を3ホップまで追跡して、操作しているユーザと各ユーザとの関係の強さを反映させています。そのためには、「誰と誰がマイミクか」を調べる処理をものすごい回数、しかもオンデマンドで実行することになります。ところで、mixi本体においてマイミクシィ関係のデータベースはMySQLで管理されています。リレーショナルデータベースのテーブルとして、ユーザIDのペアを二重化して保持しています。例えば3番と5番がマイミクシィである場合、[3:5]というレコードと、[5:3] というレコードを記録し、左の列にインデックスを張って高速に参照できるようにしています。

しかし、もしMySQLにマイミク関係を3ホップまで問い合わせるとなると1回の検索で10000回くらいMySQLにクエリを投げることになってしまうので、インデックスを張っているとはいえ、現実的な時間で応答することはできません。そこで、ユーザIDをキーにしてそのユーザのマイミクシィのIDの配列を関連付けた構造に非正規化し、それをTCのハッシュデータベースに格納するようにしました。マイミクシィ関係はそんなに激しく更新されるわけではないので、MySQLからTCへのデータの流し込みは週に1回くらいの頻度で行います。こうしておくと、TCのハッシュデータベースならば1秒に200万クエリくらい検索処理を行えるので、10000クエリくらいならオンデマンドで参照されても屁の河童なのです。

■ 非正規化のイメージ

検索処理の手順

転置インデックスと属性データベースがあれば、検索処理の実装は簡単です。ここでは処理の主体をアプリケーション層と検索サーバに分けて考えます。

1. アプリケーションは、ユーザがブラウザ経由で入力した検索条件を検索サーバ群へのクエリとして組み立てて送信する。
2. 検索サーバ群は、全文検索用のキーワードをTDに渡し、転置インデックスから条件に該当する候補のIDセットを受け取る。
3. 検索サーバ群は、IDセットの各々のIDに対して属性データベースを参照し、属性条件に該当しないものを削る。
4. 検索サーバ群は、IDセットの各々のIDに対してスコアデータベースを参照して静的スコアを算出する。
5. 検索サーバ群は、マイミクシィグラフ非正規化データベースを用いて操作ユーザのIDを中心としたグラフ分析による動的スコアの算出を行う。
6. 検索サーバ群は、静的スコアと動的スコアをマージした結果の降順でIDセットを並び替える。
7. 検索サーバ群は、IDセットを直列化してアプリケーションに返信する。

アーキテクチャ

上記の手順を複数のマシンで分散して処理できるように、システム全体のアーキテクチャを考えなければなりません。なぜ分散が必要なのかといえば、データ量が多い（しかも増大し続ける）ので1台だとパフォーマンスが追いつかないという理由と、QPSが高いのでピーク時にスループットが追いつかないという理由からです。要するに負荷が半端ないからということです。

パフォーマンスやスループットを向上させるには、各種の演算の対象データを減らすことが必要です。といっても、処理しなければならないデータの総量は決まっているので、対象データを適当な単位で分割して複数のマシンに分配したものを同時に処理させることになります。今回は、全文検索用転置インデックスと属性データベースとスコアデータベースを分散して処理させることにしました。つまり、全文検索と属性絞り込みと静的スコアリングは分散処理で行います。それらの処理を行うサーバをサーチャと呼ぶことにします。また、分散処理の結果のマージと動的スコアリングは単一のサーバで行います。これをマージャと呼ぶことにします。

■ アーキテクチャ

サーチャの実装

サーチャのマシンは10数台です。現状ではそこまで分散させる必要はないのですが、ユーザ数が増大していくことを考えて多めに見積もっています。全文検索はTDのIndexed Database API（文字N-gram API）で行い、属性による絞り込みと静的スコアリングはmmapしたファイルやTCのデータベースを直接参照して行います。クエリ毎にファイル群のopen/closeを行うと効率が悪いので、ファイル群との接続を維持したネットワークサーバのデーモンとして実装します。プロトコルにはHTTPを用います。ネットワーク層の部分はTT（libtokyotyrantのttutil.h）を再利用することで、epollやマルチスレッド等を用いた効率的な実装になっています。

マージャの実装

マージャのマシンは2台です。1台でもよかったのですが、フェイルオーバーのためにもう1台用意しています。マージャは、アプリケーションからクエリを受け取って、マルチスレッドでサーチャ群にクエリを分配し、結果が返されるまでの間にマイミクシィグラフの分析を行い、最後に結果をマージしてアプリケーションに返します。マージャはFastCGIプログラムとして実装し、アプリケーションともサーチャともHTTPで通信します。最初はPerlでお気楽に書きたかったのですが、スレッドが安心して使えないのでCで書かざるを得ませんでした。

マイミクシィグラフの分析は、動的に行います。すなわち、予め結果を計算して保存した結果を使うのではなく、クエリが来た時に計算するということです。設計当初は予め計算することを考えたのですが、1500万ユーザの分のデータを保持するとなるとデータベースが巨大になりすぎて、ファイルアクセスによるレイテンシが致命的になりかねないので、それよりもCPUに頑張らせた方が得だと考え直しました。

一般的に、検索機能を利用する際には1回だけ検索して終わりというのではなく、平均3回くらいは連続して検索を行うようです。グラフ分析を動的に行うといっても、連続されて投げられるクエリの分は分析結果を再利用した方が得なので、グラフ分析の結果はTTのオンメモリDBにキャッシュしています。

分析の具体的な手順は以下のようになります。

1. 自分（操作しているユーザ）のIDを、スコア100を与えて、プール（TCのオンメモリメモリデータベース）に加える。（0ホップ目）
2. プールの各々（今は自分のみ）のマイミクシィを取得し、「そいつのスコア / 取得したマイミク数 + α」をスコアとして与えて、プールに加える。（1ホップ目）
3. プールの各々のユーザのマイミクシィを取得し、「そいつのスコア / 取得したマイミク数 + α」をスコアとして与えて、プールに加える。（2ホップ目）
4. プールの各々をスコアの降順でソートし、上位1000人だけ残して他は捨てる。
5. プールの各々のユーザのマイミクシィを取得し、「そいつのスコア / 取得したマイミク数 + α」をスコアとして与えて、プールに加える。（3ホップ目）
6. プールの各々をスコアの降順でソートし、上位3000人だけ残して他は捨てる。

プールに加えていくところでは、そのIDが既にプールにある場合は、スコアを加算します。この処理で、前述したTCの数え上げモードが活躍します（そのために数え上げモードを作りました）。手順2の時点で、「自分」と「マイミクシィ」と「マイミクシィのマイミクシィ」が、自分からの経路の太さに応じたスコアの数直線に並べられていることになります。単なるホップ数を数えているわけではなく、マイミクシィ数が多い人よりもマイミクシィ数が少ない人と繋がっている方が経路が太いとみなすモデルです。裂けるチーズを裂いていく感じと言えばわかりやすいかもしれません。ここで重要なのは、2ホップ目の処理では2ホップ目同士や1ホップ目にもスコアを再分配しているということです。こうすることで、同じ1ホップ目の中でも序列をつけることができ、手順3や手順5によって計算量を減らす際に重要な経路を切ってしまうリスクが軽減されます。

アプリケーションの実装

アプリケーション層は通常のmixiのアプリケーション群と同居させています。マージャとHTTPで通信するためにLWPを用います。ユーザから検索条件が渡されると、ユーザIDや現住所等のプロフィール情報を補完して、マージャにクエリを投げます。マージャから結果が返されたら、その各々についてニックネームや紹介文などの表示情報をmixiデータベースから取得して、HTMLとして出力します。こうして「かんたん友人検索」の簡単でない処理は完了します。

■ ユーザインターフェイス

まとめ

かんたん友人検索の仕組みについて説明しました。全文検索機能をベースとしていながらも、周辺の機能群をいかに効率化するかに注力していることが意外だったかもしれません。正直、全文検索のエンジンがTDである必然性はなく、LuceneやHyper EstraierやSennaやを代用しても目的は達成できたと思います。ぶっちゃけ、キーワードの絞り込みに使うだけなら検索エンジンなんて何でもよかったのです。最も大変な課題は、属性による絞り込みとソートです。それらは候補の各々を対象とした演算になるので、少しでも賢いことをやろうとすると途端に計算量が跳ね上がってしまうのです。この問題をなんとか乗り切るためには、ドメインに特化した簡便法によって計算量をギリギリまで削減する手法を考案したり、DBMのような効率的なストレージを開発したり、並列化や分散処理を行ってスループットを稼いだりといった工夫を重ねるしかありません。かんたん友人検索もまだまだ改善の余地がありますが、今回の開発で得た知見をもとに、また新たなサービスを構築し改良していけたらと思っています。