mixi engineer blog

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

プラグインで独自ストレージを作ろう

mixi

OpenSocialとかC++0xとか世の中の流れが早すぎて、いろいろと勉強しなきゃなと焦りつつも、ついついピクミン2にはまってしまうmikioです。今回はTokyo Tyrant（TT）を使ってユーザ独自のストレージシステムを簡単に構築する方法について説明します。

ttplugin

プラグインとは

オブジェクト指向プログラミングに慣れた人にとっては、インターフェイスと実装を分離することによってプログラムの拡張性や保守性を向上させる技法（データ抽象）は常識ですよね。その考えをさらに進めると、インターフェイスのみをプログラムに記述しておいて、具体的な実装は実行時に割り当てるという、いわゆるプラグイン（plug-in）という技法に至ります。プラグインでカスタマイズできる能力をプラガブル（pluggable）などと言ったりもします。

例えばTokyo Cabinet（TC）では、レコードの挿入、削除、参照といった操作を抽象データベースAPIという共通のインターフェイスにまとめて、それを介してハッシュ表データベースやB+木データベースの実装を呼び出すことで、拡張性と保守性を向上させています。TTはTCの抽象データベースを用いているので、TTのコードにいっさい手を加える加えることなく、TCの新機能をTT経由で利用できるわけです。この時点では単なるデータ抽象にすぎないのですが、今回はさらに進んで、UNIXのダイナミックリンク機構を用いてプラグインを実現してみました。

余談ですが、memcachedの次のバージョン（1.4系）では、弊社のt.maesaka氏が主導して開発を進めているプラガブルストレージ機構が組み込まれる見込みです。今回ご紹介するTTの機能はそれとほぼ同じコンセプトで作られています。

まずは作ってみよう

TCとTTのそれぞれ最新版をインストールしてください。そして、プラグインとして以下のコードを用意します。これは「get」コマンドのみをサポートしていて、キーのデータをそのままエコーバックする機能を持ちます。こんなんではストレージとは言えませんが、インターフェイスさえ合っていれば何をやってもいいのです。 

#include <tcadb.h>

/* openのダミー実装 */
bool myopen(void *opq, const char *name){
  return true;
}

/* closeのダミー実装 */
bool myclose(void *opq){
  return true;
}

/* getの置き換え */
void *myget(void *opq, const void *kbuf, int ksiz, int *sp){
  *sp = ksiz;                    /* 戻り値のサイズを指定 */
  return tcmemdup(kbuf, ksiz);   /* キーをコピーして返す */
}

/* ライブラリを初期化して、実装をオーバーライドする */
bool initialize(ADBSKEL *skel){
  skel->open = myopen;
  skel->close = myclose;
  skel->get = myget;
  return true;
}

このファイルを「ttskelecho.c」という名前で保存したならば、以下のコマンドでダイナミックリンクライブラリ（共有オブジェクト）である「ttshelecho.so」をビルドできます（Macでは「-shared」の代わりに「-bundle -undefined suppress」を指定してください）。 

gcc -shared -o ttskelecho.so ttskelecho.c

そして、作ったライブラリをロードしつつ、サーバを起動します。 

$ ttserver -skel ./ttskelecho.so

別の端末を開いて、置き換えた「get」コマンドを実行してみましょう。 

$ tcrmgr get localhost hello

「hello」とエコーバックされたなら成功です。簡単ですよね。「get」以外でも全てのメソッドがオーバーライドできるので、いろいろ遊んでみてください。TTはmemcached互換プロトコルやHTTP互換プロトコルもサポートしていますので、TTを使うだけで独自のキャッシュサーバやHTTPサーバを簡単に実装できるというわけです。

スケルトンデータベース

ここからは、TTがどうやってプラグインを実現しているか、内部のカラクリを説明します。実は、プラグインストレージは、TTよりも下のTCの層でサポートされています。TCの抽象データベースに「スケルトン」と名付けた機構を挿入することでプラグインを実現しているのです。

TCの抽象データベースは従来からいくつかの具象データベースオブジェクトの操作をswitch文で切り替えて呼び出すという実装になっています。例えばデータベースサイズを返すtcadbsizeメソッドは以下のような実装になっています（なお、switch文による分岐がdisられるかもしれないので念のため補足しますが、case文が多くなってもラベルが離散的でなければいわゆるテーブルジャンプを使った最適化がコンパイル時に施されるので、実行時のオーバーヘッドはそれほど大きくなりません）。 

uint64_t tcadbsize(TCADB *adb){
  uint64_t rv = 0;
  switch(adb->omode){
  case ADBOMDB: rv = tcmdbmsiz(adb->mdb); break;
  case ADBONDB: rv = tcndbmsiz(adb->ndb); break;
  case ADBOHDB: rv = tchdbfsiz(adb->hdb); break;
  case ADBOBDB: rv = tcbdbfsiz(adb->bdb); break;
  case ADBOFDB: rv = tcfdbfsiz(adb->fdb); break;
  case ADBOTDB: rv = tctdbfsiz(adb->tdb); break;
  }
  return rv;
}

しかし、上記だと、TCのコードに気軽に手を加えられる私にとっては新しい具象データベースをどんどん追加できて楽ではあるのですが、逆に言えば、TCに手を加えないと拡張できないのでユーザの皆さんは困ってしまいます。そこで、関数ポインタを使って任意の実行コードに制御を移せるようにしてみました。 

typedef struct {            // スケルトンデータベースの構造体
  void *opq;                // レシーバへのポインタ
  ...
  uint64_t (*size)(void *); // sizeメソッドの関数ポインタ
  ...
} ADBSKEL;

typedef struct {            // 抽象データベースの構造体
  int omode;                // 動作モード
  ...
  ADBSKEL *skel;            // スケルトンへのポインタ
  ...
} TCADB;

uint64_t tcadbsize(TCADB *adb){
  uint64_t rv = 0;
  switch(adb->omode){
  case ADBOMDB: rv = tcmdbmsiz(adb->mdb); break;
  case ADBONDB: rv = tcndbmsiz(adb->ndb); break;
  case ADBOHDB: rv = tchdbfsiz(adb->hdb); break;
  case ADBOBDB: rv = tcbdbfsiz(adb->bdb); break;
  case ADBOFDB: rv = tcfdbfsiz(adb->fdb); break;
  case ADBOTDB: rv = tctdbfsiz(adb->tdb); break;
  case ADBOSKEL: rv = adb->skel->size(adb->skel->opq); break;
  }
  return rv;
}

ADBSKELという構造体型のメンバ変数に抽象データベースの各種メソッドと互換する型の関数ポインタを持たせ、任意の関数を参照できるようにします。この構造体をスケルトンデータベースと呼ぶことにしましょう。そして、実行時にスケルトンモードの場合（adb->omodeがADBOSKELの場合）には、スケルトンデータベースが参照する関数に制御を移すのです。タネを明かして見れば簡単な仕組みですよね。C++言語などのオブジェクトシステムも単純化すればこのようなディスパッチテーブルを用いて実現されているようです。個人的には「オブジェクト指向xxx」とか言われるとものすごく高尚な感じがしてびびっちゃいますが、「関数ポインタによるディスパッチテーブルを階層化した奴」だと思うと何とか使いこなせる気がしてくる今日この頃です。

さて、TCの層の抽象データベースAPIに加わったスケルトンデータベース機構の完全な定義は以下のようになります。 

typedef struct {
  void *opq;
  void (*del)(void *);
  bool (*open)(void *, const char *);
  bool (*close)(void *);
  bool (*put)(void *, const void *, int, const void *, int);
  bool (*putkeep)(void *, const void *, int, const void *, int);
  bool (*putcat)(void *, const void *, int, const void *, int);
  bool (*out)(void *, const void *, int);
  void *(*get)(void *, const void *, int, int *);
  int (*vsiz)(void *, const void *, int);
  bool (*iterinit)(void *);
  void *(*iternext)(void *, int *);
  TCLIST *(*fwmkeys)(void *, const void *, int, int);
  int (*addint)(void *, const void *, int, int);
  double (*adddouble)(void *, const void *, int, double);
  bool (*sync)(void *);
  bool (*optimize)(void *, const char *);
  bool (*vanish)(void *);
  bool (*copy)(void *, const char *);
  bool (*tranbegin)(void *);
  bool (*trancommit)(void *);
  bool (*tranabort)(void *);
  const char *(*path)(void *);
  uint64_t (*rnum)(void *);
  uint64_t (*size)(void *);
  TCLIST *(*misc)(void *, const char *, const TCLIST *);
  bool (*putproc)(void *, const void *, int, const void *, int, TCPDPROC, void *);
  bool (*foreach)(void *, TCITER, void *);
} ADBSKEL;

bool tcadbsetskel(TCADB *adb, ADBSKEL *skel);

アプリケーションは、ADBSKEL構造体の各メンバを設定してから、tcadbsetskelにそのポインタを渡すと、データベースの各操作をオーバーライドできるというわけです。各メソッドの第1引数（レシーバ）として渡されるポインタにはopqメンバで指定したものがそのまま渡されます。

思考実験のために、抽象データベースの中でさらに抽象データベースを呼び出すスケルトンの実装を考えてみましょう。以下のようなコードになります。もちろん動作もちゃんとしますよ（使う意味は全くないけれど）。 

ADBSKEL skel;
memset(skel, 0, sizeof(skel));
skel.opq = tcadbnew();
skel.del = (void (*)(void *))tcadbdel;
skel.open = (bool (*)(void *, const char *))tcadbopen;
skel.close = (bool (*)(void *))tcadbclose;
skel.put = (bool (*)(void *, const void *, int, const void *, int))tcadbput;
skel.putkeep = (bool (*)(void *, const void *, int, const void *, int))tcadbputkeep;
skel.putcat = (bool (*)(void *, const void *, int, const void *, int))tcadbputcat;
skel.out = (bool (*)(void *, const void *, int))tcadbout;
skel.get = (void *(*)(void *, const void *, int, int *))tcadbget;
skel.vsiz = (int (*)(void *, const void *, int))tcadbvsiz;
skel.iterinit = (bool (*)(void *))tcadbiterinit;
skel.iternext = (void *(*)(void *, int *))tcadbiternext;
skel.fwmkeys = (TCLIST *(*)(void *, const void *, int, int))tcadbfwmkeys;
skel.addint = (int (*)(void *, const void *, int, int))tcadbaddint;
skel.adddouble = (double (*)(void *, const void *, int, double))tcadbadddouble;
skel.sync = (bool (*)(void *))tcadbsync;
skel.optimize = (bool (*)(void *, const char *))tcadboptimize;
skel.vanish = (bool (*)(void *))tcadbvanish;
skel.copy = (bool (*)(void *, const char *))tcadbcopy;
skel.tranbegin = (bool (*)(void *))tcadbtranbegin;
skel.trancommit = (bool (*)(void *))tcadbtrancommit;
skel.tranabort = (bool (*)(void *))tcadbtranabort;
skel.path = (const char *(*)(void *))tcadbpath;
skel.rnum = (uint64_t (*)(void *))tcadbrnum;
skel.size = (uint64_t (*)(void *))tcadbsize;
skel.misc = (TCLIST *(*)(void *, const char *, const TCLIST *))tcadbmisc;
skel.putproc =
  (bool (*)(void *, const void *, int, const void *, int, TCPDPROC, void *))tcadbputproc;
skel.foreach = (bool (*)(void *, TCITER, void *))tcadbforeach;
tcadbsetskel(adb, &skel);

関数ポインタをキャストする必要があるのは、レシーバの型が(TCADB*)と(void*)で差があるからです（ポインタ同士の互換性は言語仕様で保証されています）。ここでは抽象データベースの全てのメソッドをオーバーライドしていますが、自分に必要ないメソッドは実装しなくても大丈夫です。最初にmemsetしたことで全てのメンバにあらかじめNULLを代入しているのと同じ効果があり、呼び出そうとする関数がNULLの場合は単にエラーを返す仕様だからです。

ダイナミックリンク

さて、スケルトンに関数ポインタの集合を与えることで抽象データベースの振る舞いを完全にオーバーライドできることがわかったところで、実際に呼び出される関数の実装をどうやってTCやTTのパッケージの外に追い出すかが次の課題となります。最初に思いつくのは、TCやTTのビルド時に./configureでユーザ指定のファイルを組み込む「スタティックリンク」戦略ですが、それだと機能を拡張する度に毎回TCやTTをインストールしなおさなければいけなくなります。そうでなく、実行時に任意のライブラリをリンクさせる「ダイナミックリンク」戦略をここでは採用しましょう。

UNIX系のプラットフォームでは、ダイナミックリンクはdlopenファミリと呼ばれる関数群で実現されています。dlopenでファイル名を指定してライブラリを開いてハンドルを得て、dlsymでハンドルと関数名を指定してそのライブラリ内の関数実装を指す関数ポインタを得て、使い終わったらdlcloseでハンドルを破棄するというわけです。例えば「hoge.so」というライブラリで定義されている、char*を引数にして戻り値のない「myfunc」という関数を呼び出したい場合には、以下のようにします。 

void *lib = dlopen("hoge.so", RTLD_LAZY);
void (*myfunc)(char *) = dlsym(lib, "myfunc");
myfunc("hello");
dlclose(lib);

簡単ですね。あとはTTのサーバ（ttserver）の起動時にスケルトンを定義するコードを含んだライブラリを指定できるようにすればOKです。TTの仕様では、ライブラリ内に「initialize」という名前の関数が定義されていて、それはADBSKEL構造体へのポインタを受け取って、その各メンバに任意の値を設定してから、実行の成否をboolで返すということを要求しています。すなわち以下のシグネチャです。 

bool initialize(ADBSKEL *skel);

openとcloseは必ずオーバーライドしてください（前述したようなダミーでOKです）。さらに、opqに設定したオブジェクトを抽象データベースの解放時に始末したい場合は、del（デストラクタ）をオーバーライドするとよいでしょう。仕上げに「gcc -shared ...」でコンパイルして「ttserver -skel ...」で組み込むだけです。簡単ですよね。なお、「-skel」の引数に渡す名前に「/」が含まれない場合には、dlopenによってライブラリサーチパスから自動的にライブラリを探してくれますので、例えば「/usr/lib」の下にライブラリをおいておけば、「ttserver -skel hoge.so」とするだけでロードすることができます。ライブラリサーチパスの指定はldconfigコマンドや環境変数LD_LIBRARY_PATHで行うことができます（Macではちょっと違うみたいですが、私はよく知りません）。

スケルトンデータベースはTCの層の機能ですが、dlopen経由でスケルトンを設定する機能はTTの層でのみサポートされます。なぜなら、TCを直接使っているということはADBSKEL構造体に直接触れる状態にあるということと同義なので、わざわざダイナミックリンクしないでも実装を切り替えられるはずだからです。また、いくつかの処理系でdlopenが実装されていないことが想定されるために、TCをdlopenに依存させることは避けたかったという理由もあります。

ディレクトリデータベース

もう少し実践的な例も見てみましょう。少数のでかいデータをネットワーク経由で管理したい場合は、各レコードをTCなどのDBMに格納するのではなく、ファイルシステム上の単一のファイルとして扱った方が効率的な場合もあります。そうすると各種のファイルシステム管理ツールと連携できるという利点もあるでしょう。ということで、特定のディレクトリの中に、URLエンコードしたキーを名前とするファイルを作ってその中に値を記録するという、「ディレクトリデータベース」を実装してみます。ここでは、del, open, close, put, out, get のみをオーバーライドします。openの引数にはディレクトリ名を指定する仕様です。 

#include <tcutil.h>
#include <tcadb.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

typedef struct {
  char *name;
} TCDDB;

/* キーからファイルパスを作るユーティリティ */
static char *makepath(TCDDB *ddb, const void *kbuf, int ksiz){
  char *uenc = tcurlencode(kbuf, ksiz);
  char *path = tcsprintf("%s/%s", ddb->name, uenc);
  tcfree(uenc);
  return path;
}

/* コンストラクタの実装 */
static TCDDB *tcddbnew(void){
  TCDDB *ddb = tcmalloc(sizeof(*ddb));
  ddb->name = NULL;
  return ddb;
}

/* デストラクタの実装 */
static void tcddbdel(TCDDB *ddb){
  tcfree(ddb);
}

/* openメソッドの実装 */
static bool tcddbopen(TCDDB *ddb, const char *name){
  struct stat sbuf;
  if(stat(name, &sbuf) == 0){
    if(!S_ISDIR(sbuf.st_mode)) return false;
  } else {
    if(mkdir(name, 0755) != 0) return false;
  }
  ddb->name = tcstrdup(name);
  return true;
}

/* closeメソッドの実装 */
static bool tcddbclose(TCDDB *ddb){
  tcfree(ddb->name);
  return true;
}

/* putメソッドの実装 */
static bool tcddbput(TCDDB *ddb, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
  bool err = false;
  char *path = makepath(ddb, kbuf, ksiz);
  if(!tcwritefile(path, vbuf, vsiz)) err = true;
  tcfree(path);
  return !err;
}

/* outメソッドの実装 */
static bool tcddbout(TCDDB *ddb, const void *kbuf, int ksiz){
  bool err = false;
  char *path = makepath(ddb, kbuf, ksiz);
  if(unlink(path) != 0) err = true;
  tcfree(path);
  return !err;
}

/* getメソッドの実装 */
static void *tcddbget(TCDDB *ddb, const void *kbuf, int ksiz, int *sp){
  void *vbuf;
  char *path = makepath(ddb, kbuf, ksiz);
  vbuf = tcreadfile(path, -1, sp);
  tcfree(path);
  return vbuf;
}

/* ライブラリを初期化して、実装をオーバーライドする */
bool initialize(ADBSKEL *skel){
  skel->opq = tcddbnew();
  skel->del = (void (*)(void *))tcddbdel;
  skel->open = (bool (*)(void *, const char *))tcddbopen;
  skel->close = (bool (*)(void *))tcddbclose;
  skel->put = (bool (*)(void *, const void *, int, const void *, int))tcddbput;
  skel->out = (bool (*)(void *, const void *, int))tcddbout;
  skel->get = (void *(*)(void *, const void *, int, int *))tcddbget;
  return true;
}

鬼のように簡単ですね。TTはHTTPも喋るので、簡易的な更新機能付きWebサーバとして使えるのは魅力でしょう。ただし、念のため補足しますと、このデータベースの検索性能はファイルシステムのディレクトリ機構に完全に依存しているため、ファイルシステムの種類にもよりますが、レコード数が多くなるとすぐに性能が劣化してしまいます（そりゃもうストップウォッチで計れるほどに）。くれぐれも「少数のでかいデータをネットワーク経由で管理したい場合」にのみ使ってください。

ブラックホールデータベース

今度は、MySQLの "blackhole" ストレージエンジンに相当する機能を作ってみましょう。これは文字通り何もしないスケルトンで、必ずレプリケーションのマスタとして使います。ブラックホールであるマスタは何もせずに更新ログの記録だけ行い、その更新ログを受け取ったスレーブ側で実際のデータベースへの記録を行います。このスケルトンは内部状態を持たず、かつ更新系のみをサポートするので、open, close, put, out, misc のみをオーバーライドします。 

#include <tcadb.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>

static bool myopen(void *opq, const char *name){
  return true;
}

static bool myclose(void *opq){
  return true;
}

static bool myput(void *opq, const void *kbuf, int ksiz, const void *vbuf, int vsiz){
  return true;
}

static bool myout(void *opq, const void *kbuf, int ksiz){
  return true;
}

static TCLIST *mymisc(void *opq, const char *name, const TCLIST *args){
  return tclistnew2(1);
}

bool initialize(ADBSKEL *skel){
  skel->open = myopen;
  skel->close = myclose;
  skel->put = myput;
  skel->out = myout;
  skel->misc = mymisc;
  return true;
}

ブラックホールエンジンは、マスタにメッセージキューのような役割をさせることで、比較的重い処理を非同期的に行ったり、スレーブを副数台並べて水平分散を行ったりすることが簡単にできるのです。目からウロコですね。こんなバカっぽい仕組みですが、同期性を少し犠牲にするだけでスケーラビリティをものすごく高めることができるので、非常に大規模なデータセットを扱う際には重宝します。また、地理的に離れている拠点間でデータを同期させたい場合にも活用できるでしょう。

プロクシデータベース

最後に、あるTTのサーバに来たリクエストを別のTTにリレーしてそのレスポンスを中継するだけの「プロクシデータベース」を実装してみましょう。これはTTのリモートデータベースAPIを使って、ものすごく簡単に作れます。openの引数にはサーバ名とポート番号をコロン区切りで指定する仕様です。 

#include <tcadb.h>
#include <tcrdb.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>

bool initialize(ADBSKEL *skel){
  skel->opq = tcrdbnew();
  skel->del = (void (*)(void *))tcrdbdel;
  skel->open = (bool (*)(void *, const char *))tcrdbopen2;
  skel->close = (bool (*)(void *))tcrdbclose;
  skel->put = (bool (*)(void *, const void *, int, const void *, int))tcrdbput;
  skel->putkeep = (bool (*)(void *, const void *, int, const void *, int))tcrdbputkeep;
  skel->putcat = (bool (*)(void *, const void *, int, const void *, int))tcrdbputcat;
  skel->out = (bool (*)(void *, const void *, int))tcrdbout;
  skel->get = (void *(*)(void *, const void *, int, int *))tcrdbget;
  skel->vsiz = (int (*)(void *, const void *, int))tcrdbvsiz;
  skel->iterinit = (bool (*)(void *))tcrdbiterinit;
  skel->iternext = (void *(*)(void *, int *))tcrdbiternext;
  skel->fwmkeys = (TCLIST *(*)(void *, const void *, int, int))tcrdbfwmkeys;
  skel->addint = (int (*)(void *, const void *, int, int))tcrdbaddint;
  skel->adddouble = (double (*)(void *, const void *, int, double))tcrdbadddouble;
  skel->sync = (bool (*)(void *))tcrdbsync;
  skel->optimize = (bool (*)(void *, const char *))tcrdboptimize;
  skel->vanish = (bool (*)(void *))tcrdbvanish;
  skel->copy = (bool (*)(void *, const char *))tcrdbcopy;
  skel->path = (const char *(*)(void *))tcrdbexpr;
  skel->rnum = (uint64_t (*)(void *))tcrdbrnum;
  skel->size = (uint64_t (*)(void *))tcrdbsize;
  return true;
}

たったこれだけです。我ながらよくできてます。まあ、ただ中継してもしょうがないので、実用的にはキーにハッシュ関数をかけて水平分散するとか、接続先の死活管理をしてフェイルオーバーするとかいった付加機能をつけることになるでしょう。あるいはhBaseやMySQLのゲートウェイとして実装しても面白いでしょう。

まとめ

Tokyo Tyrantのストレージ層をダイナミックリンクのプラグインで差し替えて、独自のストレージ層を構築する方法について説明しました。以前からLua拡張によってかなり柔軟なストレージシステムを構築できるTTではありますが、ストレージ層をCレベルでハックできるようになったおかげで、そこそこ経験のあるプログラマにとっては、無制限に何でもできてしまうようになりました。

epollなどによる効率的入出力やレプリケーションなどの実用的な管理機能はTTをコンテナとすることで「再利用」できます。ストレージのプログラマは、ネットワークやユーティリティのことは忘れて、ひたすらアルゴリズムとデータ構造を考えることができるのです。クライアントライブラリを書く必要がないってのも嬉しいですね。

この記事ではサンプルとしてディレクトリを使ったデータベースやプロクシとして動作するデータベースを紹介しましたが、既存のソフトウェアを利用すればいくらでも応用例を考えることができます。Oracle社のBerkeley DB、D.J.バーンスタイン氏のCDB、岡野原大輔氏のTxやBep、山田浩之氏のLux IO、Google社のsparsehashなどなど、ネットワーク越しに利用できたりレプリケーションができるようになったりすると嬉しいようなkey-valueストレージは世の中にいっぱいあります。Tokyo DystopiaをTokyo Tyrant経由で使いたいというご意見も国内海外を問わず結構いただいているのですが、このスケルトンデータベース機構を用いることで美しいインテグレーションができると思っています。

ということで、Cを経験済みの紳士淑女はぜひマイストレージ作りに挑戦してみてください。