mixi engineer blog

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

PerlとRubyで省メモリなハッシュを使おう

mixi

サボっていた早朝ジョギング＠駒沢公園を再開して2週間たち、やっと抜かれる数より抜く数の方が増えてきたmikioです。今回は、PerlやRubyのハッシュの代用としてTokyo Cabinetを使うことでメモリ使用量を激減させられることを説明します。

hashperfgraph

抽象データベースAPI

Tokyo Cabinetには抽象データベースという機構があり、先日、そのPerlとRubyのバインディングをリリースしました。それを使うと、各種言語のハッシュとほぼ同じような共通したインターフェイスで、以下のデータ構造を利用することができます。

  • オンメモリハッシュ：各種言語に標準のハッシュと同じく、メモリ上でkey/valueの関係を表現する。
  • オンメモリツリー：メモリ上の二分探索木としてkey/valueの関係を表現する。
  • ファイルハッシュ：いわゆるDBMとして、ファイル上でkey/valueの関係を表現する。
  • ファイルツリー：ファイル上にB+木としてkey/valueの関係を表現する。

各種言語のハッシュとほぼ同じように使えるということころがポイントで、ハッシュオブジェクトを作る部分だけを書き換えれば、既存のコードをほぼそのままTokyo Cabinet対応にできるのです。

例えばPerlの場合はこんな感じです。ハッシュにタイするところ以外のコードは全く同じですよね。

# 標準のハッシュ
my %hash;
$hash{"foo"} = "bar";                 # レコードを格納
printf("%s\n", $hash{"foo"});         # レコードを参照

# TCのオンメモリハッシュ
my %tcdb;
tie(%tcdb, "TokyoCabinet::ADB", "*"); # TCのオンメモリハッシュに連結
$tcdb{"foo"} = "bar";                 # レコードを格納
printf("%s\n", $tcdb{"foo"});         # レコードを参照

そしてRubyの場合はこんな感じです。クラス名とopenするところ以外のコードは全く同じですよね。

# 標準のハッシュ
hash = Hash.new
hash["foo"] = "bar"                   # レコードを格納
printf("%s\n", hash["foo"])           # レコードを参照

# TCのオンメモリハッシュ
tcdb = TokyoCabinet::ADB::new
tcdb.open("*")                        # TCのオンメモリハッシュに連結
tcdb["foo"] = "bar"                   # レコードを格納
printf("%s\n", tcdb["foo"])           # レコードを参照

性能評価

さて、そうするとメモリ使用量をどれだけ減らせるのかということです。100万件のレコードを格納した場合のメモリ使用量と処理時間を測ってみましょう。Perl（5.8.8）でテストコードを動かしたところ、以下の改善が確認できました。標準のハッシュに比べて、メモリ使用量がTCのオンメモリハッシュだと約61%、TCのオンメモリツリーだと約37%になることがわかります。処理時間に関しては157%ほどになっていますが、まあ許容範囲ですよね。ファイルハッシュやファイルツリーだとさらに省メモリになりますが、もちろん処理時間はその分遅くなります。

  メモリ使用量 処理時間
Perl標準のハッシュ 162.402 MB 1.657 sec.
TC:オンメモリハッシュ 99.289 MB 2.602 sec.
TC:オンメモリツリー 61.105 MB 2.393 sec.
TC:ファイルハッシュ 4.156 MB 6.945 sec.
TC:ファイルツリー 6.812 MB 3.163 sec.

Ruby（1.8.6）でテストコードを動かしたところ、以下の改善が確認できました。標準のハッシュに比べて、メモリ使用量がTCのオンメモリハッシュだと約34%、TCのオンメモリツリーだと約18%になることがわかります。処理時間に関しても27%以下になっていて、大変お得です。ファイルハッシュやファイルツリーだとさらに省メモリになり、かつ処理時間も標準ハッシュと同じくらいになっています。

  メモリ使用量 処理時間
Ruby標準のハッシュ 354.598 MB 9.254 sec.
TC:オンメモリハッシュ 122.590 MB 2.580 sec.
TC:オンメモリツリー 66.648 MB 2.369 sec.
TC:ファイルハッシュ 4.512 MB 7.271 sec.
TC:ファイルツリー 7.625 MB 3.211 sec.

ということで、ハッシュにデータをたくさん詰め込むようなシーンでは、TCのオンメモリハッシュかオンメモリツリーを使うと幸せになれると思います。文字列以外のクラスのオブジェクトを格納する場合にはデータをシリアライズしてから扱わないといけないという制限はありますが、シリアライズしたとしても大抵の場合メモリ効率は改善することでしょう。さらに、ハッシュが大きくなりすぎて実メモリに乗らなくなってスワップ起きまくりで激烈遅くなっちゃうようなシーンでは、ファイルハッシュやファイルツリーを使うと性能を改善することができます。もちろんプロセスが終了してもデータを永続化させる目的でもファイルハッシュやファイルツリーは活躍します。

カラクリ

なぜTCだとメモリ使用量を節約できるのかというと、データ構造の内部に現れるノードの領域として、メタデータとキーエンティティと値エンティティを連続した領域に押し込んでいるからです。一方でPerlでは、元のレコードのキーエンティティと値エンティティの元来のオブジェクト（スカラ）そのものをコピーして保持するとともに、それとは別途にメタデータを保持します。Rubyでは、キーエンティティと値エンティティのオブジェクトのリファレンスを持つことでガベージコレクタによる回収を抑制するとともに、それとは別途にメタデータを保持します。つまり、TCでは格納したオブジェクトの元来のあり方を忘れてしまう分、そしてメタデータとエンティティを連結して扱う分、メモリ使用量を削減できるのです。

処理時間に関しては、内部でオブジェクトの領域をmallocおよびmemcpyで複製する分、遅くなってしまいます。その辺の理屈はSTLとの比較の記事でも述べました。

オンメモリハッシュよりもオンメモリツリーの方がメモリ使用量が少ないのはなぜでしょう。TCのソースコードに答えが書いてあります。個々のレコードに相当するノードの構造体のサイズがツリーの方が小さいからです。

typedef struct _TCMAPREC {    /* type of structure for an element of a map */
  int ksiz;                   /* size of the region of the key */
  int vsiz;                   /* size of the region of the value */
  unsigned int hash;          /* second hash value */
  struct _TCMAPREC *left;     /* pointer to the left child */
  struct _TCMAPREC *right;    /* pointer to the right child */
  struct _TCMAPREC *prev;     /* pointer to the previous element */
  struct _TCMAPREC *next;     /* pointer to the next element */
} TCMAPREC;

typedef struct _TCTREEREC {   /* type of structure for an element of a tree */
  int ksiz;                   /* size of the region of the key */
  int vsiz;                   /* size of the region of the value */
  struct _TCTREEREC *left;    /* pointer to the left child */
  struct _TCTREEREC *right;   /* pointer to the right child */
} TCTREEREC;

オンメモリハッシュのハッシュバケットのオーバーヘッドも多少影響してますが、それよりは内部ノードのオーバーヘッドの方が支配的です。マップの方はLRU削除キャッシュとして利用するために格納順の双方向リンクリストを内包しているのでオーバーヘッドが大きくなっています。ツリーの方はスプレー木というちょびっと癖のあるアルゴリズムで実装されていて、他の平衡木のように最悪計算量を保証しない代わりに、アクセスパターンに偏りがある場合に高い性能を出すようになっています。汎用コンテナとしてスプレー木なんて普通は採用しないみたいですが、主に全文検索のインデクサのキャッシュとして順序木を利用したかったという事情でこうなっています。

まとめ

Tokyo CabinetのPerlバインディングとRubyバインディングでサポートされた抽象データベースAPIを使うと、標準のハッシュを使っているコードをほとんど変更せずに、メモリ使用量を激減させることができます。これマジで便利なので、ぜひ使ってみてください。Java版とLua版は...、気が向いたら作ります。