豪鬼メモ

MT車練習中

TkrzwのGo言語インターフェイスをリリース

並列処理性能を重視したデータベースライブラリTkrzwだが、ついにGo言語をサポートした。並列処理が簡単に書けるGo言語と並列に読み書きできるDBMの親和性は高い。ここでは、各言語の性能比較をした上で、Goでの簡単な使い方について説明する。
f:id:fridaynight:20210724153934p:plain


各言語で、1000万個のレコードの格納（Set）と検索（Get）のスループットを計測してみよう。キーと値はそれぞれ8バイトのユニークな文字列である。データ構造にはハッシュデータベースを用い、ハッシュバケットの数はレコード数の2倍とする。どの言語でも標準ライブラリのスレッド機能を使っている。Goでは当然ゴルーチンを起動している。マシンは私のノートPC（Core i7 8550U 1.8Ghz）である。単位はQPS（クエリ毎秒）である。

1スレッド Set 1スレッド Get 4スレッド Set 4スレッド Get
C++ 1,328,341 1,615,792 2,243,716 3,678,283
C 1,288,903 1,493,747 2,200,075 3,444,403
Go 641,006 772,380 1,330,526 1,724,950
Java 376,495 376,495 892,625 1,019,015
Python 766,904 799,475 232,128 236,093
Ruby 674,557 586,534 187,629 182,665

まず、C++の結果に着目しよう。古めのノートPCでも1スレッドで100万QPS以上で読み書きでき、並列化するとそれなりに性能向上することがわかる。200万QPSのSetや300万QPSのGetができれば、ほとんどのユースケースでボトルネックになることはないだろう。そして、その非常に薄いラッパーに過ぎないCインターフェイスでも、ほぼ同じ性能が出ている。少なくとも毎回のクエリでmallocを1回多く呼んでいるはずなので、もう少し遅くなると思っていたが、実際に測定するとそうでもないらしい。

Goの結果を見てみよう。さすがにCやC++には劣るが、その半分くらいのスループットが出るというのは驚きだ。そしてスレッド数を上げるとちゃんとスケールしてくれる。GoインターフェイスはCインターフェイスの薄いラッパーなのだが、Goの文字列をGoのバイトスライスを介してCのバイト配列と相互変換するという実装になっている。このあたりはもう少し最適化する余地がありそうだが、まあここまでちゃんとした性能が出ていれば充分かとも思う。スレッド数に応じてスケールするってところが重要なのだ。

JavaもGoと似たような傾向なのだが、全体的な数値がGoの半分になっている。Javaのネイティブ関数呼び出し（JNI）のオーバヘッドがGoのネイティブ関数呼び出し（cgo）のそれよりも大きいということだろう。スレッド数に応じてスケールするのは良いところだ。

PythonとRubyはグローバルインタープリタロック（GIL）のある処理系なので、呼び出す処理が一定以上高速な場合には、スレッドを使ってもスループットが上がらない。むしろスレッド切り替えのオーバーヘッドで遅くなることが多い。今回のケースがまさにそれだ。シングルスレッドではJavaを凌駕してGoと同等の性能が出ているが、マルチスレッドにすると性能がガタ落ちしてしまう。GetとSetの性能がほとんど同じことから、ネイティブ側での処理は性能に影響しないと判断できる。つまり、Python/Rubyの処理系側のオーバーヘッドが律速していることが伺える。TkrzwではGIL外でネイティブ関数を呼ぶconcurrentモードを設定でき、この実験結果はconcurrentモードのものだ。しかし、ネイティブ関数が十分早い場合、GIL外で実行しGIL内で実行しても全体のスループットはあまり変わらない。


評判に違わず、Goは実行性能が良く並列処理にも強い言語であるということが確かめられた。さて、GoでTkrzwを使うとどんな感じになるのか、サンプルコードで見ていただきたい。

package main

import (
    "fmt"
    // これを書くだけで勝手にTkrzwが使えるようになる
    // パッケージは tkrzw という名前で取り込まれる
    "github.com/estraier/tkrzw-go"
)

func main() {
    // データベースオブジェクトを作って、データベースファイルを開く
    dbm := tkrzw.NewDBM()
    dbm.Open("casket.tkh", true, "truncate=true,num_buckets=100")

    // レコードをいくつか格納する
    // キーと値にはバイト列でも文字列でも指定できる
    dbm.Set("first", "hop", true)
    dbm.Set("second", "step", true)
    dbm.Set("third", "jump", true)

    // 値を検索して文字列として取得する
    fmt.Println(dbm.GetStrSimple("first", "*"))
    fmt.Println(dbm.GetStrSimple("second", "*"))
    fmt.Println(dbm.GetStrSimple("third", "*"))

    //  レコードを一つずつ取り出すチャンネルを使って全レコードを表示
    for record := range dbm.EachStr() {
      fmt.Println(record.Key, record.Value)
    }

    // データベースを閉じる
    dbm.Close()
}

最近のGo処理系は、インポートディレクティブにGitHubのリポジトリを書くだけで勝手にgo getが走ってインストールしてくれる親切設計になっている（Tkrzw本体が予めインストールしてある必要がある）。インポートしたら、あとはtkrzw.NewDBMでデータベースオブジェクトを作って、Openメソッドでファイルと接続すればよい。そうしたら、文字列のマップとほとんど同じような使い方ができる。

GetとSetとRemoveだけを使っている限りは単純なAPIとも言えるが、Tkrzwの機能はかなり豊富だ。Openメソッドに与えるパラメータを変えれば、ハッシュ表のデータベースとB+木のデータベースとスキップリストのデータベースなどを切り替えることができる。Searchメソッドを使えば、範囲検索や正規表現検索や類似検索なども一撃でできる。CompareExchangeメソッドやCompareExchangeMultiメソッドを使えば、アトミックなトランザクションも実現できる。ダイレクトI/OをサポートしたフラットファイルのAPIもある。詳細についてはこちらのAPI文書をご覧いただきたい。Tkrzw自体については、「はじめてのDBM」スライドをご覧いただきたい。

もう少し真面目な例として、CompareExchangeMultiメソッドを使ったロングトランザクションを行うコードも見てみよう。アリスとボブが銀行口座を持っているとして、アリスからボブに500円を送金する。それには、アリスのレコードの値から500を引き、ボブのレコードの値に500を足すという操作をアトミックに行う必要がある。アプリケーション側でロックの管理をせずにそれを実現させるのがCompareExchangeという手法である。CAS = Compare-and-Swapとも言う。

package main

import (
  "fmt"
  "github.com/estraier/tkrzw-go"
)

func main() {
  // データベースを開く
  // OrDieメソッドは、ステータスが成功でない場合にパニックを起こす
  // 実際のシステムでは適当なエラー伝搬処理を書くこと
  dbm := tkrzw.NewDBM()
  dbm.Open("casket.tkt", true, "truncate=true,num_buckets=100").OrDie()

  // deferを使ってデータベースを確実に閉じる。
  // エラーチェックをする場合にはfuncでラップするとよい。
  defer func() { dbm.Close().OrDie() }()

  // ボブとアリスの銀行口座を作る。
  // キーや値に数値を指定しても勝手に変換してくれる。
  dbm.Set("Bob", 1000, false).OrDie()
  dbm.Set("Alice", 3000, false).OrDie()

  // 送金トランザクションをアトミックに行う関数
  transfer := func(src_key string, dest_key string, amount int64) *tkrzw.Status {
    // 古いレコードの値を調べる。
    old_src_value := tkrzw.ToInt(dbm.GetStrSimple(src_key, "0"))
    old_dest_value := tkrzw.ToInt(dbm.GetStrSimple(dest_key, "0"))

    // レコードの新しい値を計算する。
    new_src_value := old_src_value - amount
    new_dest_value := old_dest_value + amount
    if new_src_value < 0 {
      return tkrzw.NewStatus(tkrzw.StatusApplicationError, "insufficient value")
    }

    // 事前条件と事後条件を設定する。それぞれはキーと値のペアのスライス。
    old_records := []tkrzw.KeyValueStrPair{
      {src_key, tkrzw.ToString(old_src_value)},
      {dest_key, tkrzw.ToString(old_dest_value)},
    }
    new_records := []tkrzw.KeyValueStrPair{
      {src_key, tkrzw.ToString(new_src_value)},
      {dest_key, tkrzw.ToString(new_dest_value)},
    }

    // 事前条件に合う場合に、事後条件に移行する。
    // 他のスレッドによる変更で事前条件に合わなくなった場合、安全に失敗する。
    return dbm.CompareExchangeMultiStr(old_records, new_records)
  }

  // 成功するまで送金トランザクションを試みる。
  var status *tkrzw.Status
  for num_tries := 0; num_tries < 100; num_tries++ {
    status = transfer("Alice", "Bob", 500)
    // 事前条件に合わなかった場合はStatusInfeasibleErrorになる。
    // そうでない場合は成功か致命的エラーなので、いずれにせよループから抜ける。
    if !status.Equals(tkrzw.StatusInfeasibleError) {
      break
    }
  }
  status.OrDie()

  // 各々のレコードを取り出すためのイテレータを作る。
  //  全てのイテレータはDestructで破棄すること。
  iter := dbm.MakeIterator()
  defer iter.Destruct()
  // 最初のレコードにイテレータを飛ばす。
  iter.First()
  for {
    // 現在のレコードを取得して表示。
    key, value, status := iter.GetStr()
    if !status.IsOK() {
      break
    }
    fmt.Println(key, value)
    // イテレータを次のレコードに進める。
    iter.Next()
  }
}

イテレータを使う場合、使い終わったイテレータをDestructで破棄するのを忘れないで欲しい。また、開いたデータベースはCloseで閉じるのを忘れないで欲しい。deferを活用するとよい。

CompareExchangeMultiはバイト列としてレコードのキーと値をを扱い、CompareExchangeMultiStrはそのラッパーで、文字列でレコードのキーと値を扱う。CompareExchangeMultiは「そのレコードが存在しない」という条件を値がnilのレコードとして表現する。CompareExchangeMultiStrでは、stringはnilにできないので、空文字列の値が非存在を意味する。非存在が扱えるし、複数レコードのアトミック処理ができるので、CompareExchangeMultiは万能の更新操作だと言える。理論的には、GetとCompareExchangeMultiだけがあれば、他のメソッドは一切なくても、どんなに複雑なトランザクションも実現できる。事前条件を空リストにすればSetMultiやRemoveMultiの代用としても使える。

特殊なユースケースだとは思うが、SetAndGetとかRemoveAndGetとかいうメソッドが役に立つ場合もあるだろう。レコードに新しい値を設定したり削除したりしつつ、その更新操作の前のレコードの値を取り出せるのだ。本来2回に分けてやらねばならないような操作を1回でできるという性能上の利点があるとともに、アトミックにそれが行われるというのが重要だ。並列処理（というか並行処理）の文脈では、原子性（atomicity）は最重要概念であると言っても過言ではない。Go言語によって並列処理が身近になってくれたおかげで、Tkrzwの設計の基本理念である並列処理への最適化がやっと日の目を見るかもしれないと期待している。


まとめ。データベースライブラリTkrzwがGoから使えるようになった。並列処理に強いこの二つの組み合わせはなかなか面白いんじゃないかと思っている。正直なことを言うと、Goはもっと遅いと思っていたので、今まで手を付けていなかった。並列実行でここまでしっかりとした性能が出るなら、C/C++じゃないと駄目だと思っていた様々な仕事がGoで出来そうだ。そんな中で高速なデータストレージが欲しくなった時にはTkrzwのことを思い出してくれると幸いだ。