mixi engineer blog

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

逆襲のLua

mixi

こんにちは。開発部最後の良心、mikioです。今回はLua処理系の並列化とそこでのKyoto Cabinetの利用法についてご紹介します。

サーバサイドスクリプティングといえばLua

Kyoto CabinetのLuaバインディングは後回しにしてKyoto Tyrant的なサーバの設計を進めていたのですが、やはりそのサーバにもスクリプティング機能を持たせたくなりました。つまり、サーバがデフォルトで提供する機能群だけでなく、ユーザがスクリプト言語で記述した任意の機能を追加して利用できるようにするということです。

Tokyo TyrantではLua拡張と呼ばれる機能を用いてそれを実現しています。サーバの起動時にLuaのスクリプトを記述したファイルを読み込ませて、そこで定義した関数をリモートから呼び出せるようにしています。そこで実行されるLuaの処理系にはTTが管理するデータベースを操作するためのオブジェクトが予め定義されているので、それを介して任意のデータ処理を行うことができます。

Kyoto Tyrant（仮称）の設計はまだまだ固まっていませんが、おそらくLuaを組み込むことになるでしょう。TTでは独自のDB接続用モジュールを書いていましたが、そのモジュールの構造はTCのLuaバインディングと酷似するものでした（というかほとんどコピペで作りました）。二重管理が嫌いな私としては、KTではKCのLuaバインディングそのものを呼び出す形でスクリプティング機能を実現したいと思います。

なぜLuaなのかという点については以前の記事でも述べましたが、言語仕様が小さくて覚えやすく、処理系も高速で軽量でリエントラントだからです。

Luaバインディング

先日、KCのLuaバインディングをリリースしました。TCのそれよりもさらに使いやすくなっています。KCのJava、Python、Ruby、Perlの各バインディングと同様に、言語共通のIDLに準拠するインターフェイスを備えるとともに、Lua言語に合わせたスタイルで操作できるようにもしています。具体的なAPIやサンプルについてはAPI文書をご覧ください。

Luaならではのインターフェイスと言えばクロージャとメタテーブルと汎用for文でしょうか。 

require("kyotocabinet") -- KCのモジュールをロードする
kyotocabinet.import()   -- kyotocabinet.*をグローバル名前空間に取り込む

-- データベースを操作するためのコールバック関数
function dbproc(db)

   -- メタテーブルによってテーブルインターフェイスで書き込み
   db["foo"] = "hop"
   db["bar"] = "step"
   db[3] = "jump"

   -- クロージャによるトランザクションでレコードを更新
   function tranproc()
      db["foo"] = 2.71828
      return true
   end
   db:transaction(tranproc)

   -- Visitorパターン風にレコードを更新
   function mulproc(key, value)
      return tonumber(value) * 2
   end
   db:accept("foo", mulproc)

   -- 汎用for文でレコードを横断取得
   for key, value in db:pairs() do
      print(key .. ":" .. value)
   end

   -- Visitorパターン風に全レコードを更新
   function upproc(key, value)
      return string.upper(value)
   end
   db:iterate(upproc)

   -- 外部カーソルでレコードを横断取得
   function curproc(cur)
      cur:jump()
      function printproc(key, value)
         print(key .. ":" .. value)
         return Visitor.NOP
      end
      while cur:accept(printproc) do
         cur:step()
      end
   end
   db:cursor_process(curproc)

end

-- 上記関数をデータベースに適用
-- （openやcloseが不要なところがナイス）
DB:process(dbproc, "casket.kch")

Luaの実力

裏の仕組みは違えども、上記と同じような使い方はPythonやRubyやPerlでもできるので、Luaの利点として挙げるようなものではありません。というかミニマリズムに基づくLua言語の記述力は他の言語に比べると貧弱なのは否めず、言語としては個人的にはあんまり好きではありません。特に配列の添（ry

言語の機能やライブラリの拡充度からいくと他者に大きく水をあけられてはいますが、処理系の効率の良さがその欠点を補って余りあるというのがLuaの存在意義でしょう。特筆すべきはネイティブスレッドとの親和性が高いことです。

Luaはコルーチン（協調スレッド）と呼ばれる並行プログラミングのための機構を備えていますが、これは各スレッドが自分で実行権を手放すことによって「並行」処理を実現するための機構であり、「並列」処理つまり複数のCPUコアを同時に使って演算をする機構ではないので、ここでは言及しません。並列処理を行ってサービスのスループットを向上させるためにはあくまでネイティブスレッドを使う必要があります。

Lua処理系のAPIはいかなるグローバル変数も静的変数も使っておらず、完全にリエントラントです。その点はJavaも同じですが、Lua処理系のインスタンスはメモリ使用量も少ないし起動にかかるオーバーヘッドも小さいので、スレッド毎にLua処理系のインスタンスを割り当てるのにうってつけなのです。

サーバサイドスクリプティングでLuaを用いる場合、サーバのスレッドプールに存在するスレッドの上でLua処理系のインスタンスが動くことになります。その際に各スレッドに別個のLua処理系のインスタンスを割り当てると、Lua処理系に関してスレッド間のレースコンディションが起こり得ないので、排他制御に伴うオーバーヘッドを一切被ることなく、目的の処理を実行することができます。というより、Lua処理系はネイティブスレッドに対する排他制御機能を自身では全く持たないので、この方法がLuaによる唯一の並列化手法であると言えます。

しかし、Lua処理系のインスタンスをスレッド毎に割り当てると、スレッド間でデータを共有することができなくなるという欠点が生じます。ひとつのデータベースを複数のスレッドで同時に扱えないと意味がないので、それだと困ってしまいます。

そこで、KCのLuaバインディングでは、複数のLua処理系で同一のデータベースオブジェクトを共有する仕組みを提供することにしました。スレッド間で共有したいデータはすべてKCのデータベースに入れれば目的を達成できます。KC自体も並列性が高いのでそのようなデータ操作も並列に行うことができます。オンメモリDBを使えばファイルIOのオーバーヘッドを気にする必要はありませんし、逆にメモリに収まらないような規模のデータもファイルDBに収めることで共有と永続化ができます。また、オンメモリツリーDB（赤黒木）やファイルツリーDB（B+木）を使えば順序を管理できるので、リストやプライオリティキューとみなしてタスク管理に使うこともできます。

DBオブジェクトの共有

比較のために、まずは単一のLuaインスタンスのみでDBを作る方法について見てみます。 

db = DB:new()
db:open("casket.kch", DB.OWRITER + DB.OCREATE)
db:set("japan", "tokyo")
db:set("england", "london")
db:set("germany", "berlin")
db:close()

DB:newメソッドを呼び出すと、その内部でC++のDBポインタが作られ、それをLuaから操作するためにLuaオブジェクト（Luaテーブル）としてラップしたものを返します。ここではそれをdbという変数で受けて、以降の操作ではそれを介してデータベースファイルを開いたりレコードを書き込んだりデータベースを閉じたりしています。

次に、複数のLuaインスタンスで単一のDBを共有する方法について見てみましょう。C++でネイティブスレッドを立てて、その各スレッドでLuaインスタンスを作って使うわけです。Lua層でなくC++層でDBポインタを作り、それを使いまわすのです。 

// DBを作る
kyotocabinet::DB db;
db.open("casket.kch", DB.OWRITER | DB.OCREATE)

// スレッドクラス
class ThreadImpl : pubic kyotocabinet::Thread {
pubic:
  // コンストラクタでDBポインタを受け取る
  ThreadImpl(DB* db) : db_(db) {}
  // スレッドの処理内容
  void run() {
    // Luaインスタンスを作る
    lua_State* lua = luaL_newstate();
    // Luaの標準ライブラリを開く
    luaL_openlibs(lua);
    // DBポインタをLuaの軽量ユーザデータとしてラップ
    lua_pushlightuserdata(lua, db_);
    // 上記をグローバル変数としてエクスポート
    lua_setglobal(lua, "_db");
    // Luaスクリプトをロードする
    luaL_loadfile(lua, "myscript.lua");
    // 上記スクリプトを実行する
    lua_call(lua, 0, 0);
    // スレッドプールのワーカーとして働き、ジョブがあれば処理する
    while (alive) {
      Job job = get_job();                 // ジョブを取り出す
      lua_getglobal(lua, "do_job");        // Lua関数を取得
      lua_pushstring(lua, job.message());  // ジョブの内容を引数に指定
      lua_call(lua, 1, 0);                 // 上記関数を呼び出す
    }
    // Luaインスタンスを破棄する
    lua_close(lua);
  }
private:
  DB* db_;
};

// スレッドを作る
ThreadImpl t1(&db);
ThreadImpl t2(&db);

// スレッドを開始する
t1.start();
t2.start();

// イベントループ
while (alive) {
  Event ev = get_event();   // イベントを取り出す
  set_job(ev.job());        // ジョブを登録する
}

// スレッドの停止を待って回収
t1.join();
t2.join();

// DBを閉じる
db.close();

上記ではKCのスレッドライブラリを使っているおかげで、Java風にスレッド処理を定義することができています。Threadクラスを継承してrunメソッドをオーバーライドして、そうしてできたオブジェクトのstartメソッドを呼ぶというやつです。もちろん、別のスレッドライブラリを使ってもいいですし、POSIXスレッドやWin32スレッドのAPIを直接叩いてもいいです。

要点は、メインスレッドでDBを作って、そのポインタを個々のワーカスレッドに与えるということです。上記ではLuaの「_db」というグローバル変数としてそのポインタをLua側に渡しています。Lua側ではDBポインタをDBオブジェクトにラップして使います。また、上記ではワーカスレッドがジョブキューのコンシューマとして働くことを想定しており、各ジョブに対応してLuaの「do_job」という関数を呼ぶようにしています。となると、Lua側のスクリプトは以下のような内容になるでしょう。 

-- 起動処理
db = DB:new(_db)

-- タスクを処理するために呼ばれる
function do_job(message)
  -- DBを使ってIDを採番して表示してみる
  local jobid = db:increment("jobid", 1)
  print(jobid, message)
end

Luaスクリプトはスレッドの起動時に読み込まれて実行されます。先頭で「_db」というグローバル変数からDBポインタを取り出して、DBクラスのコンストラクタに渡してDBオブジェクトを生成しています。そして、do_job関数を定義しておいて、その中でDBオブジェクトを操作しています。

実際の性能

Javaバインディング（Javaスレッド）とLuaバインディング（ネイティブスレッド）の性能比較をしてみました。KCのファイルハッシュデータベースに対して合計100万レコードの書き込みと読み込みをスレッド数を変えて行った場合にかかる時間を測定したものです。

Java Lua
1スレッド書き 6.903秒 2.073秒
1スレッド読み 6.649秒 2.026秒
2スレッド書き 4.372秒 1.455秒
2スレッド読み 3.711秒 1.105秒
4スレッド書き 2.880秒 1.154秒
4スレッド読み 2.287秒 0.818秒

JavaもLuaもスレッド数の増加に応じて所用時間が短くなって高速化していることがわかります。Luaは1スレッドのみでも4スレッドのJavaを凌駕する性能を持ち、そしてスレッド数を増やすとさらに高速化するということです。

Lua＋ネイティブスレッドの構成だと少なくともユーザランドでは一切の排他制御をしないので、理論的にはCPUコア数を上限とするスレッド数に対して線形にスケールするはずです。実際にはDB層やOS層で多少のブレーキがかかるので線形とまではいかないわけですが、スレッドを増やすことで並列化の恩恵が体感レベルで受けられるということが今回の実験で確かめられたと思います。

まとめ

Web業界で生活しているとLua使いに出会うことは非常に稀なのですが、サーバサイドでもLuaは実用になる技術なのです。かく言う私もマイナー言語と思って優先度を下げていましたが、マルチコア・メニーコア時代にはLuaのような軽量な処理系をスレッド毎に割り当てるという手法も面白いんじゃないかなと思う次第です。C/C++で書いた高効率なサーバ実装にアドオンでき、Javaより高性能なスクリプト言語として機能するLua。最適化された世界に少しの柔軟性を持たせるLua。Lua最強説。

そして、複数のLuaインスタンスを並列させることによってインスタンス間でデータが共有できなくなる問題をKCは見事に解決してくれます。夢が広がりんぐですね。クラウドのトレンドには全く乗ってないプリミティブなアプローチではありますが、コア数の増加に対してスケールするようにすれば単一ノードの性能もまだまだ上げられます。KCはKVSのバックエンドとしてのみでなく、いわばDomain Specific Databaseのような実装を支援するツールとして育てていきたいと考えています。