mixi engineer blog

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

京都収納棚紅玉束縛： Rubyで簡単、DBプログラミング

mixi

静かに暮らしたいmikioです。今回は、新進気鋭のDBMであるKyoto CabinetのRubyバインディングを駆使してお手軽にデータベースプログラミングを行う方法について述べます。

Kyoto Cabinetのおさらい

Kyoto Cabinet（KC）は、Tokyo Cabinet（TC）に比べて、最適化された性能よりも保守性を重視したDBMの実装です。オブジェクト指向プログラミングの技法を用いて、少ないコード記述量で容易に機能追加できるように設計しています。また、実装としては、空間効率の向上と並列処理性能の向上を重視しています。以下のプレゼン資料も参考になると思います。

TCでもハッシュ表やB+木などのデータ構造を動的に切り替えて同じインターフェイスで操作するための「抽象データベース」という機構がありましたが、KCでは同じことを「多相データベース（polymorphic database）」という名前の機構として提供しています。なぜ「抽象データベース」という名前を止めたかと言うと、KCでは各種のデータ構造のDBクラスの基底クラスとして純粋仮想関数のみを持つ抽象クラスを導出していて、そちらを抽象データベースと呼びたいからです。多相データベースは、敢えてデザインパターンの用語で言えば、抽象データベースの実装クラスを実行時にデータベース名によって切り替えてインスタンス化するファクトリメソッドを内包したストラテジ的な具象クラスです。

使い方はTCの抽象データベースAPIとほぼ同じで、DBオブジェクトをインスタンス化しておいてから、openメソッドでデータベースを開いた時の名前で実際に開かれるデータベースの構造が決定されます。C++では以下のようなコードになります。 

PolyDB db;
db.open("casket.kch", PolyDB::OWRITER | PolyDB::OCREATE);
...
db.close();

上記では、データベース名が「.kch」という拡張子を持つので、ファイルハッシュデータベースが開かれます。もし拡張子が「.kct」なら、ファイルツリーデータベースが開かれます。open、close、set、getなどなどの全てのメソッドはどのデータ構造でも同じインターフェイスで操作できるので、いちいち全てのAPI文書に目を通す必要はありません。抽象データベース（FileDB）のAPIだけ知っていればよいのです。なお、拡張子をつけたくないという人は、「casket#type=kch」などとすれば、「casket」というファイル名のままでハッシュDBを作ることができます。

多相データベースで利用できる具象データベースの一覧を以下に示します。

プロトタイプハッシュDB
ファイル名：「-」そのもの
機能：STLのunordered_map（ハッシュ表）を使ったオンメモリのDB
レコード参照の時間計算量：O(1)
ロックモデル：DB全体のリードライトロック
プロトタイプツリーDB
ファイル名：「+」そのもの
機能：STLのmap（赤黒木）を使ったオンメモリのDB
レコード参照の時間計算量：O(log N)
ロックモデル：DB全体のリードライトロック
キャッシュDB
ファイル名：「*」そのもの
機能：二重リンクリストでLRU消去機能を実装したオンメモリのDB
レコード参照の時間計算量：O(1)
ロックモデル：レコード単位の通常ロック
ファイルハッシュDB
ファイル名：拡張子が「.kch」
機能：ハッシュ表と二分探索木を使ったファイル上のDB
レコード参照の時間計算量：O(1)
ロックモデル：レコード単位のリードライトロック
ファイルツリーDB
ファイル名：拡張子が「.kct」
機能：B+木とLRUページキャッシュを使ったファイル上のDB
レコード参照の時間計算量：O(log N)
ロックモデル：ページ単位のリードライトロック

伝統的なDBMに相当する機能を持つのはファイルハッシュDBであり、これがKCにおいて最も重要な実装になります。TCのファイルハッシュDBでもレコード単位のロックを実現していましたが、新規レコードを挿入する際にDB全体をロックする区間がありました。KCではそれも無くしてほぼ完全なレコード単位ロックになっています。また、PthreadのロックでなくCPUのcas命令を使った自作のロックを使うことでロック自体の性能も向上させています。

次に重要なのがファイルツリーDBで、速度はファイルハッシュDBに劣りますがキーの順序が保証される実装です。TCにおけるファイルツリーDBの実装ではロックモデルがDB全体のリードライトロックでしたが、KCではページ単位になっているところが飛躍的な進化といえるでしょう。また、ページキャッシュはTCでは単一のLRUリストでしたが、KCではInnoDBなどを真似して2段式（中間挿入＆格上げ方式）のLRUリストを採用することにより、実際のユースケースでのヒット率を向上させています。

キャッシュDBは文字通りキャッシュとして利用するための実装で、並列性と省メモリ性能に特長があります。プロトタイプハッシュDBとプロトタイプツリーDBは主に比較テストのためにのみ存在する機能ですが、ツリーの方は順序の保持が重要なオンメモリDBとして利用する価値があるかもしれません。プロトタイプDBは純粋なテンプレートとして実装されているので、std::mapに互換する実装であれば何でもスレッドセーフなDBオブジェクトとしてラッピングできるという利点もあります。

Rubyバインディング

KCのRubyバインディングは、上述の多相データベースAPIをRubyから操作できるようにしたものです。つまりKCの全ての機能をRubyから利用することができるということです。C++もRubyもクラスベースのオブジェクト指向言語として共通した機能を持っている言語ですので、KCのAPIも両者でだいたい同じ感じになっています。各種言語においけるAPIの指針はIDL（kyotocabinet.idl）で定義しているので、もし別の言語でのバインディングを書いてくれる方がいらっしゃれば参考にしていただきたいところです。ちなみに、C言語のプログラムからKCを使いたい人のために、多相データベースを extern "C" な関数でラップしたCバインディングもコアパッケージに同梱されています。

本題のRubyバインディングに話を戻します。自分で言うのもなんですが、すごく...使いやすいです。最も基本的なサンプルプログラムは以下のようになります。 

require 'kyotocabinet'
include KyotoCabinet

# データベースオブジェクトを作成する
db = DB::new

# データベースを開く
unless db.open('casket.kch', DB::OWRITER | DB::OCREATE)
  printf("open error: %s\n", db.error)
end

# レコードを格納する
unless db.set('foo', 'hop') and
    db.set('bar', 'step') and
    db.set('baz', 'jump')
  printf("set error: %s\n", db.error)
end

# レコードを参照する
value = db.get('foo')
if value
  printf("%s\n", value)
else
  printf("get error: %s\n", db.error)
end

# 全てのレコードを横断的に参照する
class Traverser < Visitor
  def visit_full(key, value)
    printf("%s:%s\n", key, value)
    return NOP
  end
end
db.iterate(Traverser::new, false)

# データベースを閉じる
unless db.close
  printf("close error: %s\n", db.error)
end

上記ではIDLに合わせたインターフェイスしか使っていないので、C++やCや今後現れるだろうその他の言語と同じノリで記述することができます。統一されてわかりやすい反面、Rubyの良さが生かしきれていないとも言えるでしょう。ご安心ください。RubyっぽいAPIも用意してあります。

基本操作の簡略化

データベースを開いたら閉じるというのは極めて重要なことですが、閉じ忘れるというバグは実にありがちなものです。C++ではDBオブジェクトをスタックに貼り付けることでRAIIによる保証を得ることができます。closeしていないオブジェクトが破棄されると暗黙的にcloseされるようになっており、スコープから抜けた時点でオブジェクト破棄されることは言語が保証してくれるということです。Rubyにおいては、DBオブジェクトを作ってファイルを開いてから、最後に閉じるという操作の間に任意のユーザ定義操作を挟むという構造をイテレータで表現することでRAIIっぽくしてみます。 

# DBを開いて、何かして、閉じる
err = DB::process('casket.kch') { |db|
  db['nagisa'] = 'kagikakko'
  p db['nagisa']
}
# エラーがあれば表示する
if err
  p err
end

newやopenやcloseがコードから消失しています。DB::processメソッドを呼び出すと、DBオブジェクトを準備した上で、引数のブロックのパラメータに与えて実行します。ブロックが終了したら、正常終了でも例外などの大域脱出でも、必ずDBは閉じられます。ついでに、組み込みのHashクラスと同じように "=" メソッドでレコードを格納して "" メソッドでレコードを参照していることにもお気づきいただいたと思います。その他にもHashクラスと互換のメソッドを実装していますので、それを使っている既存のコードにKCを適用するのはとても簡単です。

横断操作の簡略化

集合（＝データベース）に格納されている要素（＝レコード）をひとつひとつ参照すると言えば、DB#eachメソッドです。KCでももちろん対応しています。全レコードの内容を表示するには以下のようにします。 

db.each { |key, value|
  printf("%s:%s\n", key, value)
}

さらに便利なことに、KCでは、イテレータでレコードの値を更新することもできてしまいます。DB#iterateメソッドを用います。全レコードの値の小文字を大文字に置き換えるには以下のようにします。 

db.iterate { |key, value|
  value.upcase
}

たったこれだけです。DB#iterateはブロックの戻り値を新しい値とみなしてデータベースに更新をかけてくれます。よって、値に対する任意の加工をブロック内で定義することができます。なお、更新したくない場合にはVisitor::NOPという値を返し、そのレコードを消したい場合にはVisitor::REMOVEを返します。

ちょっと複雑になりますが、カーソル（外部イテレータ）も使えます。全レコードの内容を表示するには以下のようにします。 

cur = db.cursor
cur.jump
while cur.accept { |key, value|
    printf("%s:%s\n", key, value)
    Visitor::NOP
  }
  cur.step
end

カーソルでもブロックの戻り値を新しい値とみなして更新をかけることになっているので、レコードの値に対する任意の加工を行うことができます。NOPとREMOVEについても同じです。なお、内部イテレータとカーソルの使い分けですが、内部イテレータは一連のイテレーション操作をアトミックに行いたい時に使い、カーソルはアトミックでなくてもいいから複数のイテレーション操作を並行して走らせたい時に使うということになります。

Visitor風インターフェイスの詳細

既に横断検索のところで話題に出てしまっていますが、ユーザが定義したブロックを呼び出してレコードの値の参照や更新を任意に行わせるという操作ができるというところがKCのセールスポイントです。元来はVisiotorというインターフェイスを実装したオブジェクトをDB#acceptメソッドに渡すという以下のようなAPIになっています。DB#iterateやCursor#acceptも同様です。 

class Visitor
  NOP = 0
  REMOVE = 1
  def visit_full(key, value) end
  def visit_empty(key) end
end

class Cursor
  def accept(visitor = nil, writable = true, step = false) end
end

class DB
  def accept(key, visitor = nil, writable = true) end
  def iterate(visitor = nil, writable = true) end
end

各メソッドで、visitorがnilの場合にはブロックパラメータが呼び出されます。ブロックにはレコードのキーと値が渡されます（該当のレコードが無い場合には値はnilになる）。writableはDBの内側のコードでリードライトロックの判断に用いられるもので、コールバックによって更新が発生しうる場合には真、更新が絶対に発生しない場合には偽にします。stepはカーソルを自動的に進めたい場合に真にします。なお、C++ではvisitorとして渡すオブジェクトはVisitorクラスを継承している必要がありますが、Rubyではduck typingに基づくので継承関係は必要ありません。通常パラメータとして与える場合にはvisit_fullやvisit_emptyを備えるオブジェクトを、ブロックパラメータとして与える場合にはkeyとvalueを受け取るブロックを指定すればOKです。

暗黙の型変換

KCではレコードのキーと値は単なるバイナリ（C/C++ではcharの配列）であり、RubyではそれをStringクラスとして表現しています。ただ、キーや値に指定するデータを全て明示的にStringクラスのオブジェクトに変換しているとかなり面倒なので、多くのクラスを暗黙的に変換してくれます。以下のコードはいずれもそれっぽく動作します。trueは "true"、falseは "false"、nilは空文字列に変換されます、 

db["tako"] = "ika"                   # String
db[:kyoto] = :cabinet                # Symbol
db[12] = 34                          # Fixnum
db[12345678901234] = 98765432109876  # Bignum
db[12.34] = 56.78                    # Float
db[true] = false                     # TrueClass/FalseClass
db[nil] = nil                        # NilClass

障害対応とトランザクション

開いたデータベースを閉じないでプロセスが終了すると、データベースが壊れたり書いたはずのレコードが消失したりするリスクがあります。RAII的な手法を使えばcloseを呼び忘れるというバグは無くすことができますが、シグナルでプロセスが殺されたり電源断でマシンごと落ちたりすればやはり閉じ損ねが生じることになります。TCではそのような事態においては「データベースが壊れた」というエラーを提示してユーザに明示的な修復を求めることにしていました。たとえ全てのレコードが生存していたとしても、正常に終了しなかった場合は破壊とみなして明示的対応を求めるということです。一貫性が失われているかもしれない状態で通常運用を続けるのはよろしくないという判断で敢えてそうしています。

しかし、自分でマシンを落としておきながらヒステリックな反応をする人が結構多いようなので、KCのデフォルトではデータベースが壊れた場合にも勝手にベストエフォートで修復して通常運用を続けるようにポリシーを変更しました。open/closeの呼び出しで上げ下げされるフラグをDB内で管理し、起動時に前回のcloseが検出されない場合には、fsckのようにDB全体をスキャンして整合性を回復させます。このような動作が望ましくない場合には、openメソッドのmodeパラメータに DB::ONOREPAIR を加えてください。

というか、「そもそも壊れるなよ」と言いたい人もいるかと思います。closeで更新操作のdurabilityを確定させるのではなく、setやremoveなどの呼び出し毎にdurabilityを確定させたい場合には、自動トランザクション機能を使ってください。これは、各々の更新操作の前に更新内容のログをとるWAL（write ahead logging）という手法でdurabilityを保証するものです。ただし、WALを書くためのオーバーヘッドによって性能が半減することは避けられません。自動トランザクションを有効にするにはopenメソッドのmodeパラメータに DB::OAUTOTRAN を加えてください。さらに、ファイルシステムが不整合を起こした場合に備えて DB::OAUTOSYNC を加えることもできます。これはDBファイルやWALファイルの更新の度にfsyncシステムコールでディスクとの同期をとるものです。むちゃくちゃ遅くなりますが、単一マシンでのdurabilityを最大化させたければこの機能を利用してください（単一マシンでのdurabilityにそこまで重きを置くかはよく考えてほしいところですが）。

自動トランザクションは毎回の更新操作で暗黙的にコミットされるトランザクション機能ですが、任意の操作群をまとめてコミットしたり、ロールバックさせたりしたいこともあるかと思います。その場合は明示的にトランザクションを実行することもできます。begin_transactionでトランザクションを開始して、end_transactionで終了します。end_transactionの引数が真の場合、トランザクションの更新内容がコミットされて確定します。偽の場合、トランザクションの更新内容は破棄されて、トランザクション開始前の状態にロールバックされます。KCではトランザクションを実行できるのは同時に1スレッドだけですので、isolationレベルはSerializable相当ということになります。 

db.begin_transaction
db["tako"] = "ika"
db["uni"] = "ikura"
db.end_transaction(true)

開始したトランザクションは必ず終了させたいわけですから、例によってイテレータでそれを保証した方がいいですよね。もちろんサポートしてますよ。transactionメソッドに与えたブロックの実行前にトランザクションを開始し、ブロックの戻り値が真の場合はトランザクションはコミットされ、偽の場合は破棄されます。 

db.transaction {
  db["tako"] = "ika"
  db["uni"] = "ikura"
  true
}

例外は不採用

Rubyにおいては、モジュール内で起きたエラーを例外として報告してそれを呼び出し側で補足してエラー処理を行うというスタイルが一般的ですが、KCではエラーは例外ではなく戻り値で報告するようにしています。TCと同じく、IDLに基づいて言語間で統一的なインターフェイスを提供したいというのがその理由の第一です。CやLuaやPerlなど例外機構のない言語でも同じように利用できるようにしたいし、C++で例外安全でないライブラリとも共存させたいということです。

さらに、例外になるエラーとそうでないエラーの区別を仕様書にイチイチ書かなきゃならないの煩雑で嫌だというのが第二の理由です。DB#getが返すrecord not foundエラーを例外にすべきか、であればDB#openが返すfile not foundエラーやpermission deniedエラーはどうなのか、DB#casやDB#incrementのconflictエラーはどうなのか、といったあたりの議論とそれに基づく仕様変更が面倒なので、一貫して全て例外でないということにしました。

メモリ使用量対決

TCの抽象データベースでも好評でしたが、言語組み込みのHashクラスの代替として省メモリな連想配列としてDBMを使うというのも一興です。そこで、言語組み込みのHashクラスとKCの各種データベースとで時間性能とメモリ使用量を測ってみました。「00000000」から「00999999」までの100万レコードの格納にかかった時間とメモリ使用量を比べてみます。

経過時間 メモリ使用量 ファイルサイズ
組み込みHash 7.018 秒 177.41 MB -
プロトタイプハッシュDB 3.442 秒 135.12 MB -
プロトタイプツリーDB 6.802 秒 157.55 MB -
キャッシュDB 2.648 秒 74.05 MB -
ファイルハッシュDB 3.418 秒 41.77 MB 36.52 MB
ファイルツリーDB 3.250 秒 61.06 MB 19.00 MB

ということで、省メモリな連想配列が欲しければ、まずKCのキャッシュDBを使ってみてください。速度もメモリ使用量もお得です。それより少し遅くてもいいからもっとメモリ使用量を減らしたい場合には、データの特性に応じてファイルハッシュDBやファイルツリーDBを使ってみてもよいでしょう。

チューニングパラメータ

openメソッドに渡す名前でデータ構造を選択できることは既に述べましたが、名前の後に「#」で区切ってチューニングパラメータを指定することもできます。各データ構造でサポートされるパラメータを以下に示します。

プロトタイプハッシュDB、プロトタイプツリーDB
なし
キャッシュDB
bnum, capcount, capsize
ファイルハッシュDB
apow, fpow, opts, bnum, msiz, dfunit, erstrm, ervbs
ファイルツリーDB
apow, fpow, opts, bnum, msiz, dfunit, erstrm, ervbs, psiz, rcomp, pccap

それぞれのパラメータの意味を以下に示します。サイズを指定する際には「10m」のように接尾辞で単位を指定することもできます。

  • bnum : ハッシュ表のバケット数。デフォルトは100万くらい。格納するレコードの総数の2倍くらいがオススメ。
  • capcount : 格納するレコード数の上限。溢れたはLRUなものから削除される。デフォルトは制限なし。
  • capsize : 格納するレコードサイズの合計の上限。溢れた分はLRUなものから削除される。デフォルトは制限なし。
  • apow : レコードのアラインメント。2の冪で指定。デフォルトは3（ハッシュ）か8（ツリー）。
  • fpow : フリーブロックプールのサイズ。2の冪で指定。デフォルトは10。
  • opts : "s"（small）、"l"（linear）、"c"（compress）を含めた文字列。デフォルトはなし。
  • msiz : mmapする領域のサイズ。デフォルトは64MB。
  • dfunit : 動的デフラグの単位。デフォルトはなし。動的デフラグをしたい場合は8くらいがオススメ。
  • erstrm : エラーレポートの出力先。"stdout" か "stderr"。デフォルトはなし。
  • ervbs : エラーレポートの冗長フラグ。"true" か "false"。デフォルトは偽。
  • psiz : B+木のページサイズ。デフォルトは8192バイト。4096でもOK。
  • rcomp : B+木の比較関数。"lex"（lexical）か "dec"（decimal）。デフォルトはlexical。
  • pccap : ページキャッシュのサイズの合計の上限。デフォルトは64MB。

大抵の値はデフォルトのままでOKですが、bnumだけは設定した方がよいでしょう。また、巨大なデータベースを扱う場合、メモリに余裕があるならmsizやpccapを増やすと性能が劇的に改善します。1億レコードを格納する10GBのファイルハッシュデータベースを作るなら、"casket.kch#bnum=200000000#msiz=16g" などとすればよいでしょう。

Rubyスレッド対応

まず現状を説明すると、KCのRubyバインディングは、Ruby 1.8系ではスレッドセーフではありませんが、Ruby 1.9系ではスレッドセーフです。ここで言うスレッドセーフとは、Rubyレベルのスレッドに対してのことです。KCはネイティブスレッド（POSIXスレッド）に対してはネイティブのロック機構やTLS（スレッド局所記憶）を用いてDBオブジェクトの排他制御を行うことによってスレッドセーフを達成しています。しかし、1.8系におけるRubyスレッドは単一のネイティブスレッド上でユーザ層のコンテキストを切り替えて動作する仕組みであり、ネイティブのスレッド関連機能が働かないために、必ずしもRubyスレッドセーフにはならないのです。このあたりの問題は最近発覚して調査やテストをしているところで、おそらく私の理解が甘いところが多いので、識者のご意見を賜りたく存じます。

1.9系はRubyスレッドとネイティブスレッドが1対1で対応するっぽいので、ネイティブのロックやTLSが期待通りに動作すると思われます。しかし、KCではDB#acceptメソッドなどでRubyコードをコールバックする関係で、KCのクリティカルセクションの中でRubyのGVL（Global Vm Lock。一般にはGIL）が開放されて別スレッドが同じクリティカルセクションに突入しようとしてデッドロックする問題があります。よって、現状では全てのAPIをRubyのMutexクラスによるクリティカルセクションで保護してデッドロックを防いでいます。この問題に関しては、Thread#criticalに相当する機能でDB#acceptなどを保護することで対応できると思っていますが、1.9ではThread#criticalが廃止されているのでそれに相当する機能が使えるか否かを調査しているところです。

上記が解決するかDB#accept等を廃止するかした場合、1.9系では、ネイティブのスレッド関連機能に任せてスレッドセーフを達成できるため、ネイティブコードを実行している最中にはGVLを外すことができると思われます。1.9系においてもGVLによってRubyコードの並列性はないわけですが、ボトルネックになることが多いIO関連機能の処理をGVL外で実行することによってプログラム全体のスループットを上げることが期待できます。DBMはIO関連機能の典型なのでこの手法がまさにうってつけだと思っています。thread.cのrb_thread_blocking_regionが使えるかどうか検討しています。

で、とりあえずRubyのMutexでKCのDBオブジェクトを保護している現状では1.8系でもスレッドセーフだと言えるんじゃないかと思ったのですが、それは早計でした。KCのエラーコードはネイティブのTLSで管理しているのですが、1.8系ではそれをRubyのTLSにコピーする必要があるようです。1.8系と1.9系で実装をかき分けたり、効率が悪い方に合わせて効率が良い方にオーバーヘッドを強いるのはちょっと心苦しいこともあり、現状では1.8系のスレッドセーフ性は放置ということになっています。現状でTLSのコピーをして1.8対応したとしても上述の1.9向けの最適化をする足かせになってしまうので、1.8系スレッド対応の優先度は低いというのが正直な気持ちです。

まとめ

Kyoto CabinetのRubyバインディングの使い方と内部事情について簡単に説明しました。まだまだインターフェイスや実装に改良の余地があるとは思っていますが、実用できるレベルにはなってきたと思っています。実際に自分で使ってみた限りではかなり快適で性能も悪くないので、皆様にもぜひお試しいただければ幸いです。今後は1.9向けの最適化を手探りでも進めていこうと思っています。

蛇足ですが、「あんたのところPerlの会社じゃないの？」というツッコミに対するレスを予め示しておきます。もちろんPerlバインディングも作る予定なのですが、バインディングシリーズの最初に取り組むのは回避したということです。PerlのXSを書くのは興味深い仕事ではあるのですが、ルールが多くて神経をすり減らす面もあり、設計と実装を同時に進めると両方が疎かになってしまうと判断しました。そして、私のスキルセットにあるスクリプト言語（Perl、Java、Ruby、Lua）の中で最もバインディングを作りやすいRubyにまずは取り組んだというわけです。先にRubyでインターフェイスの設計とC++側の実装を整えておけば、その他の言語でも比較的楽に作業を進めることができるでしょう。急がば回れ。急いては事を仕損ずる。