使ってみようTokyo Cabinet

2010/01/28 22:21
mikio

この記事は、Software Design2010年2月号の特集「ほんとうに知りたいあなたのためのkey-valueストア講座」に寄稿した記事の校正前の版です。

----

本稿では、巷で話題の軽量データベースライブラリTokyo Cabinetの概要と使い方について説明します。

----

DBMとは

PerlやRubyやPHPなどのスクリプト言語が世の中に多数存在しますが、どの言語にも必ず連想配列もしくはハッシュと呼ばれる機構があります。これは、キーと値という二つのオブジェクトを関連付けて記憶しておき、キーに一致する値を効率的に取得するための機構です。プログラマの皆さんは日々当たり前のように使っている機能ですよね。

スクリプト言語組み込みの連想配列はメインメモリ上にデータを記録するので、プロセスが終了したらデータが消えてしまいますし、メインメモリの容量以上のデータが扱えないという問題があります。それを解決するのがDBM(DataBase Manager)です。DBMは連想配列をファイル上で実現したものですので、プロセスが終了してもデータは残りますし、ディスク容量の許す限りの大規模なデータを格納することができます。

オリジナルのDBMはUNIXの生みの親であるKen Thompson氏が開発したもので、以下のようなC言語のインターフェイスを備えています。

typedef struct { char *dptr; int dsize; } datum;  // データ用構造体
int dbminit (char *name);                         // データベースを開く
int store (datum key, datum content);             // 任意のレコードを保存
datum fetch (datum key);                          // 任意のレコードを取得
datum delete (datum key);                         // 任意のレコードを削除
datum firstkey ();                                // 最初のキーを取得
datum nextkey (datum key);                        // 次のキーを取得
int dbmclose ();                                  // データベースを閉じる

最近話題に取り上げられることが多いkey-valueストレージですが、その原型は30年も前に世に登場していました。多数のレコードを入れるとファイルサイズが極端に大きくなってしまうとか、プロセス内で同時にひとつしかデータベースを開けないとかいう制限はありましたが、こんな単純なインターフェイスでもデータベース管理機能として実用されていたのです。そして、NDBM、GDBM、SDBM、TDB、QDBM、BerkeleyDB、CDBなど、数多くの製品がDBMを模倣して登場しています。Tokyo Cabinet(以後TCと呼びます)もそういったDBMフォロワーのひとつです。

Tokyo Cabinetの特徴

TCは「DBMのモダンな実装」という製品コンセプトに基づいて開発されました。モダンであるとは、市場に流通するハードウェアの進化によるデータの大規模化や並列処理能力の向上に合わせた機能や性能を提供しているということです。具体的には、以下の点が挙げられます。

  • 空間効率が高い
    • レコード毎のヘッダが小さく、ファイルサイズも小さくなる
  • 時間効率が高い
    • アルゴリズムの単純化やメモリの有効活用により、高速に動作する
  • 並列性が高い
    • ひとつのデータベースにマルチスレッドで並列的に操作を行える
  • 64ビット対応
    • 理論上、最大8エクサバイト(約9京バイト)までのデータベースが扱える

C言語のインターフェイスだけでなく、各種スクリプト言語から利用するためのバインディングも多く開発されているので、Perl、Ruby、Java、Lua、Python、PHP、Erlang、Haskell、Goなどなど、ほぼ全ての言語のプログラマの方に気軽に使っていただけると思います。

DBM系の実装全般に言えることですが、データベースサーバとネットワーク通信でデータの授受を行うのではなく、アプリケーションプロセス内にライブラリとして組み込んで直接的にデータベースファイルを操作するので、TCは極めて高速に動作します(図1参照)。ファイル入出力がOSのキャッシュに乗っている状態だと、レコードの挿入は1秒に250万回、レコードの取得は1秒に300万回も行うことができます。リレーショナルデータベースしか使ったことのない方がTCを初めて触ったなら、文字通り桁違いの早さに驚かれるかもしれません。

図1:データベースサーバとDBMの対比

簡単な使い方

TCは、LinuxやFreeBSDやMac OS Xなど、UNIX系のOSで利用することができます。インストール方法は多くのオープンソース製品と同様に、ソースパッケージを展開してビルドコマンドを実行するだけでOKです。ソースパッケージは公式サイト(脚注:http://1978th.net/tokyocabinet/)から入手してください。

$ tar zxvf tokyocabinet-1.4.40.tar.gz     # パッケージの展開
$ cd tokyocabinet-1.4.40                  # 展開されたディレクトリに移動
$ ./configure                             # 設定スクリプトを実行
$ make                                    # コマンドとライブラリをビルド
$ sudo make install                       # インストール(rootとして実行)

TCのパッケージにはライブラリだけでなくコマンドラインのツールも同梱されているので、まずはそれを使って簡易的な辞書ユーティリティを実現してみましょう。入力データとして、以下のようなTSV形式(タブと改行区切って行列を表す)のファイルを準備してください。

panda      パンダ
eagle      タカ
lion       ライオン
tiger      トラ
monkey     サル
hipo       カバ

このファイルをanimal.tsvとして保存したならば、以下のコマンドで辞書データベースを構築することができます。dict.tchというファイルが作成されます。

$ tchmgr importtsv dict.tch animal.txt

この辞書データベースを使って単語を検索してみましょう。第1引数にサブコマンド名、第2引数にデータベース名、第3引数に検索キーを指定します。

$ tchmgr get dict.tch lion
ライオン

tchmgrコマンドには、getの他にも、レコードを作成するput、レコードを削除するout、キーの一覧を取得するlistなどのサブコマンドがあり、一通りのデータベース操作をコマンドラインで行うことができます。

実のところ、DBMでできる主な操作はたったこれだけです。こんな単純なものは実用にならないと思われるかもれませんね。しかし、世にある複雑な探索アルゴリズムの多くはDBMに見られるような単純な操作の組み合わせで実現されているので、高速なDBMを獲得することは様々なシステムを効率化する上で強力な武器になります。

スクリプト言語から使う

各種スクリプト言語からTCを使う場合、組み込みの連想配列とほとんど同じように使うことができます。例えばRubyの場合、以下のように使うことができます。

# 標準のハッシュ
hash = Hash::new             # ハッシュオブジェクトを生成
hash["foo"] = "bar"          # レコードを格納
printf("%s\n", hash["foo"])  # レコードを参照

# TCのオンメモリハッシュDB
require 'tokyocabinet'
db = TokyoCabinet::ADB::new  # データベースオブジェクトを生成
db.open("*")                 # TCのオンメモリハッシュDBに連結
db["foo"] = "bar"            # レコードを格納
printf("%s\n", db["foo"])    # レコードを参照
db.close                     # データベースを閉じる

上記ではTCの抽象データベースという機能を使っています。抽象データベースオブジェクトは、openメソッドで指定するデータベース名で様々な種類のデータベースを切り替えることができます。サポートされているデータベースは以下の6種類です。

<名前> <命名規約>
オンメモリのハッシュ表 "*" そのもの
オンメモリの二分探索木 "+" そのもの
ファイル上のハッシュ表 拡張子が ".tch"
ファイル上のB+木 拡張子が ".tcb"
ファイル上の固定長配列 拡張子が ".tcf"
ファイル上のコラムテーブル 拡張子が ".tct"

オンメモリのデータベースは機能特性が言語組み込みの連想配列と同じだから存在意義がないと思われるかもしれませんが、たいていの場合、言語組み込みの連想配列よりも省メモリかつ高速に動作する利点があります(脚注:参考:http://alpha.mixi.co.jp/blog/?p=791)。

ファイル上のデータベースはDBMの元来の用途であるデータの永続化のために利用できます。キーの完全一致のみでレコードを探せればよいのならハッシュ表データベースを使うとよいでしょう。キーの範囲検索や前方一致検索が必要な場合はB+木データベースを使うとよいでしょう。キーが連番の数値の場合は固定長配列データベースを使うと非常に効率的です。レコードの構造がキーと値のように単純でない場合にはテーブルデータベースを利用するとよいでしょう(コラム1参照)。

Tokyo Tyrant

高速で便利なTCですが、不便な点もあります。データベースの整合性を保証するために、ひとつのプロセスがデータベースを書き込みモードで開いている間は、別のプロセスがデータベースを開こうとするとブロックして待たされてしまうのです。TCはマルチスレッドのプログラミングモデルに最適化されていて、マルチプロセスでアクセスするのには向いていません。

とはいえ、Apacheなどのマルチプロセスモデルのサーバ上でプログラムを動かすような場合にはどうしてもマルチプロセスでデータベースを共有したくなります。そこで、Tokyo Tyrant(以下TTと呼びます)というサーバを開発しました。TCのデータベースを抱え込んだ単一のサーバプロセスに対して複数のクライアントがネットワーク経由で操作指示を出すことで並列処理を実現します。

TTはTCのRPCサービスとみなしてもよいでしょう。事実、TTのクライアントAPIははTCのAPIとほとんど同じなので、TC用に作ったアプリケーションをTT用に書き換えるのは非常に簡単です。その証拠に、Rubyのサンプルコードを見てください。クラス名とopenメソッドの引数が違う以外はまったく同じコードになっています。

require 'tokyotyrant'
db = TokyoTyrant::RDB::new   # データベースオブジェクトを生成
db.open("localhost", 1978)   # データベースサーバに連結
db["foo"] = "bar"            # レコードを格納
printf("%s\n", db["foo"])    # レコードを参照
db.close                     # データベースを閉じる

TTはmemcachedプロトコルもサポートしていますので、既にmemcachedを使っているシステムをTTに載せ替えるのは、アクセス先のサーバを変えるだけで済みます。筆者が勤務するmixiでもmemcachedプロトコルでTTを利用しています(コラム2参照)。

TTにはLuaというスクリプト言語を組み込むことができ、それによって任意のデータベース操作をサーバ側で行うことができます。key-valueストレージはSQLのような強力な操作言語を持たないのが一般的ですが、サーバ側にスクリプト言語を組み込むことで、SQLよりもさらに柔軟に処理を記述できます。透過的なキャッシュ機構(図2参照)として利用したり、MapReduceモデルの集計処理を実行したりもできます。

図2:透過的なキャッシュ機構

まとめ

TCはDBMのモダンな実装で、key-valueストレージの基礎となる連想配列をファイルシステム上で実現するものです。単純な機能しか提供しない分、一般的なリレーショナルデータベースとは桁違いの高速性を実現しています。TTはTCのRPCサービスとして利用することができ、特にWebサービスで利用する際に力を発揮することでしょう。

本稿で紹介したのはTCやTTの機能のごく一部に過ぎません。詳しい情報は公式サイトにある仕様書(脚注:http://1978th.net/tokyocabinet/spex-ja.html)に載せていますので、ぜひご一読ください。Tokyoシリーズには他にも検索エンジンTokyo Dystopiaやコンテンツ管理システムTokyo Promenadeがあり、それらも旺盛に開発を続けています。ご意見やご要望があれば作者にご連絡いただければと思います。

----

コラム1:テーブルデータベースの使い方

ハッシュ表やB+木などのデータベースはあくまでキーと値の関係を記録するkey-valueストレージの範疇に収まりますが、テーブルデータベースはそれらとは大きく異なります。レコードを識別するためにユニークなキー(主キー)を必要とするところは同じですが、値として任意の名前をつけたコラムを複数持つことができるのです。連想配列の値としてさらに連想配列を入れるようなイメージです。

シリアライズして文字列に変換すれば他のデータベースにも連想配列を格納することはできますし、実際テーブルデータベースはそのような実装になっています。テーブルデータベースの存在意義は、任意のコラムにインデックスを張れることです。主キーだけでなく、任意のコラムの値を条件として効率的にレコードを探索することができるのです。

例として社員名簿を考えてみましょう。社員番号を主キーとし、名前と部署名と役職をコラムとして各レコードに持たせます。Rubyでそのようなデータベースを作るには、以下のようなコードを書きます。

require 'tokyocabinet'
include TokyoCabinet
db = TDB::new
db.open("sample.tct", TDB::OWRITER | TDB::OCREAT)

db["12"] = { "name" => "John", "div" => "hr" }
db["18"] = { "name" => "Nancy", "div" => "sales" }
db["20"] = { "name" => "Bob", "post" => "ceo" }

db.close

上記で、平社員のJohnとNancyは部署名を持ちますが、CEOであるBobは部署名の代わりに役職を持っています。このように、スキーマを予め定義することなく、レコード毎に違ったデータ構造を持つことができるようなデータベースを、スキーマレスデータベースと呼ぶこともあります。CouchDBやMongoDBのような実装が有名ですが、TCやTTも同じような用途で使うことができます。

営業部に属する人の一覧が欲しい場合、以下ようにクエリを発行します。SQLのようなクエリ言語を使わなくても、簡単な演算子を組み合わせるだけで任意のレコード集合を取得できます。

qry = TDBQRY::new(db)
qry.addcond("div", TDBQRY::QCSTREQ, "sales")
p qry.search()
----

コラム2:mixiでのTC/TTの用途

月間ページビュー数が150億を越えるmixi.jpですが、その中で最も更新頻度が高いと思われるデータベースとして「最終ログイン時刻データベース」と呼ばれるものがあります。このデータベースには常時1万クライアント以上が接続していて、夜23時頃から25時頃までのピークタイムには秒間数万クエリが殺到することになります。リレーショナルデータベースでこのアクセスを捌こうとするとコストがかかりすぎることから、従来はmemcachedで分散させて最終ログイン時刻を管理していました。しかし、memcachedではデータ消失のリスクを常に抱えて運用することになるため、近頃TTに載せ替えました(脚注:参考:http://alpha.mixi.co.jp/blog/?p=166)。

しかも、今まで分散させて保持していたデータをたった1台のTTに集約させて保持しています。そうすることで複数レコードの一括取得を行う際のパフォーマンスを劇的に向上させることができるのです。150億PVを1台に集約させるって結構すごいことだなと我ながら思います。セッションデータのような小さいレコードを多数管理するようなユースケースでは分散でなく集中させることでコストを下げるという選択肢もあるということです。

TTはmemcachedと同じくサーバ側では分散処理の機能を一切持ちませんが、クライアントライブラリ側でアクセス対象のサーバを割り振ることで分散処理を行うことができます。データの冗長化は非同期レプリケーション機能で実現していて、上記のユースケースでもホットスタンバイのサーバに常に最新データを複製しながら運用しています。ただし、TTはサーバの台数を随時追加するスケールアウトのアプローチには向いていませんので、その場合は本特集で登場するFlareやkumofsなどの採用を検討してみてください。

mixiでは検索エンジンやレコメンドエンジンの内部でTCを直接使っています。検索エンジンが利用するインデックスは、検索語をキーとして、その語を含む文書のIDの配列を値とする連想配列なので、まさにDBMの出番なのです。友人の共通の友人を新たな友人候補として推薦するようなレコメンドシステムでは、ユーザIDをキーとして、その友人のユーザIDの配列を値とする連想配列を操作することになるので、またもDBMの登場となるのです。いずれのケースでもリレーショナルデータベースで論理的に同等のことはできるのですが、処理効率のためにスキーマの非正規化を行うような場合には、いっそのことkey-valueストレージの採用を検討してみるといいかもしれません。


ロック自作による高速化

2010/01/28 20:00
mikio

マルチスレッドのロック機構を自作してKyoto Cabinetを高速化したよという話。

背景

以前の記事にも書いたとおり、組み込みのrwlockはmutexに比べても遜色ない速度で動作して素敵なのだが、実はロック処理自体の並列性があんまり高くないんじゃないかなぁと思い始めてきた。というか、pthreadのロック機構は遅い(期待ほど速くない)んじゃないかなぁと感じる今日この頃。

特にspin lock(pthread_spinlock_t)とrwlock(pthread_rwlock_t)が遅い気がしている。プロファイルをとると、Kyoto Cabinetの実行時間の多くをロック回りの処理が占めているので、こいつらを自作のロックに置き換えて軽量化してみよう。pthreadのロックプリミティブはPOSIXの規程に基づいたいろんな機能を備えているが、自分で作れば自分のユースケースに必要な機能だけにできるから、より高速化できる余地はある。もちろん、偉い人が最適化して作っているものの再発明をするのは負けることが多いというのは覚悟した上で、ちゃんと実験をしながらだ。

ロック単体の性能

まずはspinlockをcasで置き換えた実装作った。4スレッドで100万回のロックとアンロックをさせた時間を測ったところ、以下の高速化が見られた。条件にもよるだろうが、3倍以上は早いということになる。

lock
組み込みspin lock 0.959
自作spin lock 0.283

つぎに、rwlockを変えて、spin lockで状態を保護してそれを待つモデルとしてspin rwlockというのを実装する。本来のrwlockは状態変数に類する機構使ってビジーウェイトを避けてCPU負荷を抑えるらしいのだが、このspin rwlockは文字通りスピンしながら待つ。4スレッドで100万回のロックとアンロックをさせた時間を測ったところ、以下の高速化が見られた。

writer lock reader lock
組み込みrwlock 5.533 2.273
自作rwlock 4.315 2.544

うぬぬ。あんまり早くなってない。上記では組み込みのspin lockを使っていたので、それをさらにcasで置き換えてみよう。その結果は以下。最終的には、ライタロックで5倍以上、リーダロックで3倍以上は高速化するということがわかった。

writer lock reader lock
組み込みrwlock 5.533 2.273
自作rwlock改 1.032 0.723

CacheDBの性能

kc::CacheDBは、通常のメソッド(レコード操作)とメタメソッド(DB全体に対する操作)の競合を防ぐrwlockと、個々のレコードの整合性を確保するmutexと、外部カーソルの整合性を確保するmutexを持っている。これをそれぞれ自作のspin rwlockとspin lockに置き換えてみる。4スレッド並列で合計400万件のset、get、removeを行った時間を測った結果は以下。

set get remove
改修前 3.726 3.813 3.729
改修後 2.566 2.463 2.087

全体的にスループットが1.5倍くらいになっている。素晴らしい。ついでに語っておくと、このCacheDBはTokyo CabinetのTCMDB(並列化したTCMAP)をC++で再実装したものである。STL(libstdc++)のunorderd_map<std::string,std::string>よりも2倍以上高速で、メモリ使用量も半分以下になっている。しかもスレッドセーフで、LRU削除機能もついている。かなり使えるので、ぜひ試してみてほしい。

HashDBの性能

kc::HashDBは、通常のメソッドとメタメソッドの競合を防ぐrwlockと、個々のレコードの整合性を確保するrwlockと、外部カーソルの整合性を確保するmutexを持っている。これをそれぞれ自作のspin rwlockとspin lockに置き換えてみる。4スレッド並列で合計400万件のset、get、removeを行った時間を測った結果は以下。

set get remove
改修前 4.298 3.548 3.549
改修後 3.386 1.811 2.100

setのスループットは1.2倍くらい、getのスループットは2倍くらいになることがわかった。これまた素晴らしい。ロックとかの主にCPU負荷に対する最適化の重要度はIOが絡んでいる場合は低そうなものだが、それでも2倍とかいう差が出るとは驚きだ。

なお、HashDBの下層にあるFileクラスでは内部状態の保護にmutexを使っているのだが、それをspin lockに置き換えるのは逆によろしくないことがわかった。クリティカルセクション内でftruncateを読んでいるのだが、それの終了待ちをspin lockでやってしまうのは非常に効率が悪いみたいだ。ブロックし得る処理をspin lockのクリティカルセクションでやってはいけないというセオリー通りの結果である。

まとめ

Pthread組み込みのロック機構を自作のものに置き換えてみたところ、ロック自体は5倍とか3倍とかの高速化が達成され、それをデータベースに組み込んでみたところ、従来より1.2倍とか2倍とかいう勢いで高速化された。今やKCのハッシュDBのスループットは書き込み118万QPS、読み込み220万QPSに達している。TCにはまだ負けているけれど、だいぶ近づいてきた感じがする。

余談。今回のロックの話もそうだけど、標準仕様はユースケースを非常に広く想定しているため、思い切った最適化ができない。だから、競争力のある製品を作ろうと思ったら、躊躇せずに標準実装の代替を再発明していかなければならない。コンテナを自分で書く奴は死ねみたいな発言をどっかのブログ見かけたことがあるが、業務領域が違うとはいえ、そういう言われ方をすると正直むかつくよなー。


ヒット率が低いDBMを効率的に管理する方法

2010/01/27 19:53
mikio

表題のことについてtwitterに書きなぐっていたら幾人かの方々からレスポンスをいただいたので、せっかくだから自分の考えをまとめてみる。

背景

レコードをファイルに保存しているデータベースがあったとして、個々のレコードを参照する度に毎回ファイル入出力を行うと効率が悪いから、オンメモリのキャッシュ機構を用いるのが普通である。その実装には以下のことが求められる。

  • よくアクセスされるレコードのキーと値の対応関係を連想配列に入れて、高速に参照できる
    • キャッシュにない場合、ファイルを探して、見つかればそのレコードの情報をキャッシュに載せる
  • あまりアクセスされないレコードの情報は、LRUなどの尺度で判定してキャッシュから追い出す
    • ダーティな(キャッシュ内で更新された)レコードはファイルに書き込む

上記の方法で大抵の場合はうまくいくが、弱点もある。キャッシュにもファイルにも存在しないレコードを探すことが多い場合、毎回ファイルを参照することになり、キャッシュがほとんど効かないことになる。存在しないという情報をキャッシュに載せることも考えられるが、それだけのためにメモリを大量に使うのはイマイチな感じだ。存在するか否かを判定するだけならばもっと効率的な方法がありそうなものだ。

で、存在しないレコードを探しまくるユースケースがあるのかということになるわけだが、ないことはない。典型的な例として、迷惑ユーザのデータベースが上げられる。大多数のユーザは迷惑ユーザではないが、個々のユーザが迷惑ユーザに該当するかどうかは逐一調べねばならない。一方で迷惑ユーザに対してはその迷惑行為の度合いをカウントしなければならない。迷惑ユーザ対策以外でも、エラーや不正入力などのレアケースをカウントして特別な処理をするようなユースケースは考えられるだろう。

ブルームフィルタ

ある要素が集合のメンバーであるかどうかのテストを高い空間効率で行うことができるデータ構造として、ハッシュ関数とビットマップを使ったブルームフィルタというのがあるらしい。それをキャッシュの前段に適用すれば、存在しないレコードを検索することがなくなるため、ファイル入出力の回数を激減させ、キャッシュのヒット率も上げることができるはずだ。ブルームフィルタは偽陽性(本当はメンバーでないのにメンバーだと判定する)が起こりうるが、その場合でもファイル入出力で実際のレコードを調べてしまうだけで、その時点で偽陽性であることがわかるので問題ない。そして偽陽性の発生率は非常に低く抑えることができるので性能上に対する影響は無視できる。

ブルームフィルタはの弱点は、レコードが削除された際にその旨をフィルタに反映させることができないことである。したがって、レコードの削除が続くと、それに伴って偽陽性の発生率が上昇していくので、適当なタイミングでフィルタの再構築を行う必要が出てくる。レコードの削除回数を数えたり偽陽性の発生件数を数えたりしてそのタイミングを測ることになるだろう。

分割

ブルームフィルタの再構築を行うということは、全てのキーを再登録するということなので、その処理を行っている間は全てのデータベース操作をブロックしなければならない(実際にはブロックさせずにブルームフィルタを外した状態で運用すればよいのだが)。これはダサい。よって、集合を細かい単位にわけて、再構築の範囲をできるだけ抑えたい。そのためには、レコードのキーのハッシュ値などで「キー空間」なるものに分類し、キャッシュとファイルとそれを表すブルームフィルタをキー空間毎に分けて管理することが望ましいような気がする。キー空間の分割数を増やせばブルームフィルタを再構築する際にブロックされる範囲を縮小できるし、メモリやディスクの参照範囲が局所化されるので処理が高速になるはずだ。

ここまでの議論を図示すると以下のようになる。もちろん、このような分割は全てライブラリの中で行い、アプリ側からは見えなくする。アプリ側からはあくまでフラットなキー空間のように見える。

image:1:1264589606-keyspaces.png

このモデルに基づいて様々な実装形態が考えられそうだ。key space毎に別サーバにしてproxyと通信するのでもよいし、proxyも含めて全て単一のプロセス空間の中で動かしてもいいし、key spaceとCacheまでがローカルでDBMの部分だけ別サーバになっていてもいい。

まとめ

LRU削除機能付きのオンメモリDBMクラス(kc::CacheDB)と典型的なファイル上のハッシュDBMクラス(kc::HashDB)は既にKCのパッケージに存在しているので、それらとブルームフィルタを組み合わせて、「高効率キャッシュ付きDBM」みたいなものを簡単に作っちゃおうかなと思ったが、ちょっと面倒そうだということがわかった。競争力のあるものを作ろうとしたら、ブルームフィルタとキャッシュ層とファイルDB層を一括してアトミックにゴニョゴニョするモジュールを作る必要があるので、ロックのオーバーヘッドを考えると既存のモジュールを使いまわすのは現実的ではない。よって、もしこれを作るなら一から作らないとダメだ。


京都収納棚:DBMの率直な壱実装

2010/01/13 11:36
mikio

この記事は、mixiエンジニアブログに私が書いた記事の転載です。

----

飲み屋に行くとかなりの確率で荷物を忘れて帰るmikioです。さて、今回はここ2ヶ月ほどで急ピッチで開発した軽量データベースライブラリ「Kyoto Cabinet」について紹介します。

開発の動機

以前から軽量データベースライブラリとしてご好評いただいているTokyo Cabinetですが、DBMとして必要十分な機能と性能を備えていてなかなか良いものだと自負しております。ただ、開発を進める中でいくつか不満な点があったのも事実です。端的に言えば、全てC言語で記述して、標準ライブラリ(とzlib/bzip2)以外の機能は全て自作しているので、最適化がしやすい反面、メンテナンスの難易度が高くなってしまっているというのが不満です。

そこで、多少性能が悪くなってもいいから、私自身としてお気楽に開発およびメンテナンスができて、移植性も高いような実装を作ってみようと思い立ったのが昨年10月頃。様々な検討を経てついにC++を採用し、STLを使って楽々にプログラミングしてみようということになりました。

特徴

KCの基本設計はTCのものを踏襲しているので、TCと同じく以下の点が優れています。

  • プロセス組み込みなので、ネットワーク通信等のオーバーヘッドがない。
  • 静的ハッシュの単純な構造なので高速で並列性も高い。
  • データベースファイルが小さく空間効率が高い。
  • オンメモリデータベースとファイルデータベースを使い分けられる。
  • トランザクションによってACID属性を確保。
  • 動的デフラグでデータベースの肥大化を抑止。
  • APIが単純で使いやすい。
  • 名前がかっこいい。

一方で、KCは実装上の工夫をさらに重ねて、TCに比べて以下の利点を獲得しています。

  • さらに空間効率が高い。
  • さらに並列性が高い。
  • 下層の抽象化による非POSIX環境への対応。
  • レコード操作の究極的な抽象化。
  • 実装上の細かい改善。

KCの性能はTCに比べてかなり低く、現状では半分以下です。しかし、ユーザランドでの並列性は高いはずなので、OSやハードウェアの並列性が上がれば、並列処理で使った場合の全体のスループットがTCに勝つ日も来るかもしれません。

空間効率が高い

いかなるデータベースにおいても、レコードを管理するためのデータを記憶しておく必要があり、TCやKCではレコードに前置するヘッダとしてそれを表現しています。データベースの空間効率を高めるにはこのヘッダをできるだけ小さくすることが重要です。

TCでは通常モードで14バイト、ラージモードで22バイトのヘッダ領域をレコード毎に必要としていました。通常モードとラージモードの違いはレコードのアドレッシングのために4バイトの領域を使うか8バイトの領域を使うかの違いです。4バイトだと2^32=4GBまでの値を表せ、それにデフォルトアラインメントの16バイトを掛けた64GBまでのデータベースを扱えることになります。8バイトだと2^63=8EBまでのデータベースを扱えます。

今日の一般的な計算機環境を考えると、4バイトアドレッシングは非力すぎる一方、8EBのストレージなんてものも存在していません。そこで、KCではモードを統一して、6バイトアドレッシングを採用しています。6バイトだと2^48=256TBまでの値が扱え、デフォルトアラインメントは8なので、2PBまでのデータベースを扱えることになります。1台のデータベースで扱えるサイズとしては当面はこれで十分でしょう。なお、アラインメントは32768まで上げることができるので、ライブラリとしての最大データベースサイズはTCと同じく8EBまでとなります。

アドレッシングの幅が4バイトから6バイトに上がった分だけ空間効率が悪化するので、それが最小限になるように努力もしています。レコードを識別するためのマジックナンバをサイズ管理用の領域に押し込んだり、後述の二分探索木をバランスさせるためのキーを動的に再計算することで記憶領域をとらないようにしたりして、16バイトまで抑えました。TCの通常モード14バイトに比べると多少増えていますが、ラージモードの22バイトに比べるとかなり減っています。

TCやKCでは静的ハッシュ法によるインデックス(バケット配列)を管理することでレコードの探索を高速化していますが、バケット配列の要素が足りない場合でも著しく遅くならないようにするために、ハッシュ値の衝突管理を二分探索木で行って計算量を抑制しています。とはいえ、単一のマシンでどれだけのレコードを管理できるかはあらかじめ予測できるはずなので、きちんとチューニングすれば二分探索木の機構は不要とも言えます。そこで、きちんとチューニングできる人達のために、「線形モード」も用意しました。二分探索でなく線形リストとして衝突管理を行うことで子供のアドレスの6バイトを節約するのです。つまり、線形モードを使えば、バケット配列のサイズに対してセンシティブな性能特性にはなるけれど、ヘッダのサイズを10バイトにまで減らせるのです。

さらに、KCは使うけどデータベースサイズが32GB以下だと確実に分かっている場合には4バイトのアドレッシングで十分なので、「スモールモード」も用意しました。線形モードとスモールモードを併用するとレコード毎のヘッダは8バイトで済みます。ここまでやればTCに対して優位性を示せるでしょう。

並列性が高い

TCやKCではPthread(POSIXスレッド)パッケージでマルチスレッドの排他制御を行っています。例えばデータベースファイルのサイズというメタデータを更新するためには、mutexでロックをかけて、更新を行って、ロックを解除するという手順を踏んでいます。この構造自体は仕方ないことですが、変数一つを更新するためにmutexのロック/アンロックのオーバーヘッドがかかるのは非効率なので、できればもっと軽量な方法を使いたいところです。

うまいことに、GCCのバージョン4からはi386のアトミック演算機能を呼べる拡張機能がサポートされているので、それを使うことにしました。もちろんIntel系以外のCPUを使った環境やGCC以外のコンパイラでビルドする場合にはそれだとうまくいかないので、その場合はspinlockで該当の変数を保護する代替実装を適用するようにしています。

それ以外にも、並列性に着目してコード全体を見直して、ロックフリーとはいかないまでも、クリティカルセクション内でブロックし得るシステムコールを一切呼ばないというところまでは来ています。

TCと同じく、「pread/pwriteというシステムコールは明示的な内部状態(ファイル位置)を持たないので並列性が高いと言われつつも実際には期待外れな問題」に対処するためにmmapを積極活用しています。KCでは全てのファイルI/Oをmmap経由でやろうとも思ったのですが、諸事情で断念して、結局mmapとpread/pwriteを併用する実装になっています。

非POSIX環境への対応

TCでは最適化のためにモジュール化の原則を崩しまくっていわばモノリシックな構造になっているので、POSIX依存のコードをそうでないOS用に書き換えるのが絶望的に難くなっています。とはいえ、TCは主にWebサービスのバックエンドとして利用することを想定しているので、LinuxやFreeBSDやSolarisで動けば十分だという割り切りの上で設計をしていたので、これは問題ではありませんでした。いわゆる組み込み系やWindows等のデスクトップ環境で動く必要はないということです。

一方、KCは組み込み系やWindowsでも動くようにする予定です。よって、多少オーバーヘッドがあろうとも、処理系依存部分は徹底的にモジュール化して、C++03標準で定義されていないシンボルはハッシュDB本体の実装には一切現れないようにしました。主にファイルI/Oを抽象化するFileクラスとスレッド管理を抽象化Threadクラスがそれを担っています。

Windows版はまだ開発に着手できていませんが、数ヶ月以内にはリリースしたいと思っています。構造を単純化したのでPure Java版も作れるだろうとかDBフォーマットをRFCにできたら格好いいとか妄想は膨らみますが、多分口だけで終わると思います。

レコード操作の抽象化

KCを設計する際に、「KVSとは何だろう」「DBMとは何だろう」とかいう哲学的な部分を考察しました。その結果、KVSとは以下のメソッドを宣言したインターフェイスであるという仮説が導き出されました。

  • set : キーと値の組を記憶し、後でgetできるようにする。
  • get : キーを指定して、そのキーを伴って直前に記憶された組の値を取得する。
  • remove : キーを指定して、そのキーを伴って直前に記憶された組の記憶から消す。
  • open : 直前にcloseした際の記憶を復元する。
  • close : setやremoveによって更新された論理構造を記憶装置に保存する。

KVSの「Key-Value」はset/get/removeを示し、「Store/Storage」はopen/closeを示す感じでしょうか。そして、DBMとは、上記KVSの実装形態の一つであり、実装として以下の条件を満たすものです。

  • ファイル記憶 : 記憶状態をファイルシステム上のファイルに保存する。
  • プロセス組み込み : ネットワーク通信を伴わず、関数呼び出しだけの低いオーバーヘッドでメソッドを呼び出せる。

これらはあくまでオレオレ定義にすぎませんが、KCはDBMであり、DBMはKVSなので、KCはKVSだと考えています。まあ、「分散しないものはKVSとは言えない」とか、「ACIDじゃないものはそもそもDBとは言えない」とかいうオレオレ定義をするのも自由なので、TCやKCを実際のところ何と呼ぶのかはユーザの皆様にお任せすることにします。

話を戻して、KVSインターフェイスの一実装であると認識されるKCですが、並列処理を想定した場合、キーと値の組に対する操作はset/get/removeだけでは済まないというのが課題になります。単一スレッドの直列処理の場合、レコードの状態をgetしてから、その内容やそれ以外の状況に応じてそのレコードをsetしたりremoveしたりすれば、キーと値の組に対するいかなる操作も実現することができます。一方で、並列処理の場合、getしてからset/removeするまでの間に別のスレッドがレコードの状態を変更してしまう可能性があるため、何らかの排他制御機能が必要となります。そのためには主に以下の二つの戦略があります。

  • lock/unlockメソッドの定義 : 該当のレコードをlockしてから、任意の操作を行って、最後にunlockするのをアプリケーションの責任で行う。
  • 各種の操作を全てライブラリ側で定義 : 上記の操作のひとつひとつをライブラリ側で実装する。

前者はライブラリ側の実装が簡素になるとともに、アプリ側で排他制御の有無や粒度を自由に設定できるという利点がある反面、実装が複雑になり、デッドロック等の酷いバグを生み出す原因になります。後者逆の特性で、アプリ側は不自由ながらも簡潔になる反面、ライブラリ側のメンテナンスは非常に大変になります。TCでは後者を採用して、putcatとかaddintとかaddbouleとか多数のメソッドを実装しまくるという苦労を味わっていますが、KCではその苦労を少しでも軽減したいものです。

ここでKVSの定義を再検討してみましょう。レコードに対するいかなる操作も、「特定のレコードの状態を調べて、それに応じて更新操作をしたりしなかったりする、という挙動をアトミックに行う」という風に抽象化できます。例えば、各種操作は以下のような言い換えが可能です。

  • set : レコードの状態を調べるが、その状態の如何に関わらず新しい値に書き換えて更新する。
  • get : レコードの状態を調べて、レコードがあれば値を返し、元の状態をそのまま残す。
  • remove : レコードの状態を調べて、レコードがあれば削除して、なければ何もしない。
  • increment : レコードの状態を調べて、レコードがあればそれを数値とみなして、なければ0とみなして、付与の値を足した値をもって、レコードの値を書き換える。
  • append : レコードの状態を調べて、レコードがあればその値に、なければ空文字列に、付与の値を後置した値をもって、レコードの値を書き換える。

例えて言うなら、キーに対応するレコードの空間にアプリケーションの実行者を案内して、その値の読み書きを自由にさせるという操作を、その空間に限定してアトミックに行わせるということです。すなわち、KVSの仕様としては、操作の具体的な内容ではなく、アトミック性を保証する範囲が重要であるということになります。その考えに基づいてKVSを定義すると、以下のようになります。

  • キーに対応する値の更新履歴を1世代以上記憶することができる。
    • openメソッドは記憶のある時点のスナップショットを復元する
    • closeメソッドは記憶のその時点のスナップショットを保存する
  • キーに対応するレコードの状態の取得と更新をアトミックに行える
    • 付与のキーに基づくレコードがある場合、そのレコードの値を渡してコールバック関数を呼ぶ
    • 付与のキーに基づくレコードがない場合、何も渡さずコールバック関数を呼ぶ
    • 上記のコールバック関数が値を返したなら、その値を元のキーに対応する値として記憶する

具体的なAPI

ここまでの議論で新たに認識したKVSインターフェイスをC++のAPIに落とし込んでみましょう。

class DB {
  // レコードの空間を訪問する操作主体のクラス
  class Visitor {
  public:
    // 訪問時、更新が必要ない(no operation)の場合に返す値
    static const char* const NOP;
    // 訪問時、そのレコードを削除したい場合に返す値
    static const char* const REMOVE;
    // 仮想デストラクタ
    virtual ~Visitor() {}
    // 既存のレコードを訪問した場合に呼ばれるコールバック関数
    virtual const char* visit_full(const char* kbuf, size_t ksiz,
                                   const char* vbuf, size_t vsiz, size_t* sp) = 0;
    // 存在しないレコードを訪問した場合に呼ばれるコールバック関数
    virtual const char* visit_empty(const char* kbuf, size_t ksiz, size_t* sp) = 0;
  };
  // 訪問者を受け入れる
  bool accept(const char* kbuf, size_t ksiz, Visitor* visitor, bool writable) = 0;
  // データベースを開く
  bool open(const std::string& path, int mode) = 0;
  // データベースを閉じる
  bool close();
};

上記はKyoto Cabinetの実際のインターフェイスです。アプリケーションは、openでデータベースオブジェクトを利用可能にした後、DB::Visitorを実装した任意のクラスを定義して、それをデータベースオブジェクトのacceptメソッドに渡して操作を行い、最後にデータベースオブジェクトを閉じます。データベースから「hoge」というキーに対応する値を検索して表示するアプリケーションは以下のようになります。

DB db;
db.open("casket", DB::OREADER);
class : public DB::Visitor {
  virtual const char* visit_full(const char* kbuf, size_t ksiz,
                                 const char* vbuf, size_t vsiz, size_t* sp) {
    cout << string(kbuf, ksiz) << " has " string(vbuf, vsiz) << endl;
    return NOP;
  }
  virtual const char* visit_empty(const char* kbuf, size_t ksiz) {
    cout << string(kbuf, ksiz) << " is empty" << endl;
    return NOP;
  }
} visitor;
db.accept("hoge", 4, &visitor, false);
db.close();

毎回Visitorを実装するのは面倒なので、KCの実際のDBクラスには典型的な操作であるset/get/remove/append/incrementをacceptを使って実装したものがビルトインとして組み込まれています。ただ、レコードの操作は必ずacceptを経由するようにしているので、ライブラリ内の実装はとても簡潔で保守しやすくなっています。

詳細についてはKCのチュートリアルAPI文書をご覧ください。

実装上の細かい改善

KCではハッシュ関数としてMurMur hashを採用しています。TCで採用していた各バイトを37倍して足すハッシュ関数だと、自然言語の単語のようなものをキーにする際にはとても効率がよいのですが、intなどのバイナリ表現をそのままキーにすると衝突率が高まるという弱点があります。TCでは主なユースケースのひとつとしては全文検索の転置インデックスを想定していたのでそれでもよかったのですが、KCではより汎用性を重視して、数値のバイナリでも偏りが出にくいという評判のあるMurMurを採用した次第です。MurMur hashと同じような特性を示すFNV hashも捨てがたいところで、自然言語の単語ではFNVの方がよさげでしたが、やはり数値バイナリでの安定性が上のような気がするMurMurを採用しました。とはいえ、ハッシュ関数はプラグインで入れ替えられるようにする予定です。

TCでは値の圧縮にgzipとbzip2を切り替えて使えるようにしていましたが、bzip2モードを使う人があまり多くない割に、libbz2-devパッケージをインストールしていなくてはまる人が多いので、bzip2は廃止しました。ただし、TCと同じく任意の圧縮関数をプラグインで入れ替えられるようにしているので、bzip2はもちろん、LZOやLZSSやLZMAを使うことも可能です。

特定のハッシュ関数や圧縮関数で作ったデータベースファイルは同じ関数のセットを組み込んだDBオブジェクトで開かないと不整合が起きるわけですが、チェックサム機構を備えることでそういった不整合を事前に検出できるようにもしています。

TCでは全レコードを横断的に参照するために内部イテレータ方式を採用していました。内部イテレータ方式は、データベースの内部にどこまで読んだかという情報を保持するので、アトミック性の確保が容易になり、実装も単純になる反面、同時に一つのイテレータしか使えないという弱点があります。KCでは内部イテレータと外部イテレータの両方をサポートしています。外部イテレータ方式は、どこまで読んだかという情報を保持するカーソルオブジェクトを生成してアプリケーション側で管理するものです。アトミックに全レコードを操作したい場合には内部イテレータを用いて、アトミック性はいらないから複数スレッドで並列にスキャンを行いたい場合には外部イテレータを使うとよいでしょう。

さらに、KCではイテレータによるレコードアクセスもacceptメソッドを経由して行うので、Visitorによる任意のアトミック処理ができ、そしてイテレーション中のレコードの書き換えも簡単に行うことができます。どうせならSTLのstd::map::iteretorと互換にしようともちらっと思いましたが、あまりに面倒なので挫折しました。

まとめ

Kyoto CabinetはTokyo Cabinetの後継の製品で、性能は悪化していますが、機能性と並列性と移植性と保守性は向上しています。まだまだアルファバージョンで、実用に耐える品質とは言い難い状態ですが、そこそこ使える状態まではもっていく所存です。

TCは不要なのかというのがFAQになりそうなのでここで答えておくと、そんなことはありません。おそらく、TCが使える環境ではTCを使い続けるのがよいでしょう。POSIX準拠でない環境(主にWindows)でDBMが欲しい場合にはKCが役立つと思います。そういう意味では、KCはTCの後継というより、QDBMを共通の親とするTCの兄弟と言った方が適切かもしれません。


KCのデータフォーマット再考

2009/12/28 03:37
mikio

2009年12月26日づけでKyoto Cabinetの初版をリリースした。経緯に関する詳しい話は後日まとめるとして、さっそく仕様変更をバンバンやっていく。なるべく初期に仕様変更は出し尽くしてしまいたいのだ。で、まずはDBファイルのフォーマットを変える。

新しいヘッダ部のフォーマット

仕様は変わるものであり、ミッションクリティカルな用途では後方互換性を確保できるということが製品価値につながる。すなわち、ファイルフォーマットを変更した新しいバージョンのライブラリを出したときに、そのライブラリで古いバージョンのファイルも読み書きできるとうれしい。何らかの事情で書き込み機能は諦めたとしても、読み込んで新しい形式に変換できることは重要だ。そのためには、ファイルの中にそのフォーマットのバージョン情報を含めないといけない。

また、KCではハッシュ関数やレコードの圧縮器をプラグインできるようにしているのだが、同一のファイルの読み書きをする時には常に同じプラグインのセットを使っていることを保証しなければいけない。しかしプラグインのコード自体をデータベースフォーマットに入れるわけにはいかないので、プラグインの出力が同一であることでもって同一性を判定する。そのためには、一定の入力をプラグインに読ませて、その出力を記録しておけばいい。ファイルを再度開いた際にも同じ計算をして、記録しておいたものと一致することを確かめるのだ。「__kyotocabinet__」という文字列に圧縮器をかけ、その出力をさらにハッシュ関数に通し、その値の下位1バイトを代表値とすればいい。

ついでに、予約領域を静的なものと動的なものに分けた。KCをstable宣言してからどうしてもメタデータを追加したいような場合には予約領域を使うわけだが、静的データ(DB作成時に決まって以後は変わらない)と動的データ(DBを更新する度に変わる可能性がある)を明確に区別してトランザクションの保護対象を削りたい。

ということで、ヘッダ部の新しいフォーマットは以下のようになった。全体で64バイトというところは変わっていないので性能への影響は皆無だと思う。

名前 オフセット 長さ 機能
マジックナンバ 0 4 KCのDBファイルであることの判別。「KC\n\0」
ライブラリバージョン 4 1 ライブラリのメジャーバージョン番号
ライブラリバージョン 5 1 ライブラリのマイナーバージョン番号
フォーマットバージョン 6 1 現状では1
チェックサム 7 1 文字列「__kyotocabinet__」のハッシュ値の下位1バイト
データベースタイプ 8 1 ハッシュ表(0x01)かその他(未定)か
アラインメント力 9 1 アラインメントに対する2の冪乗
フリーブロックプール力 10 1 フリーブロックプールの要素数に対する2の冪乗
オプション 11 1 スモール(1<<1)、リニア(1<<2)、圧縮(1<<3)の論理和
静的予約領域 12 4 静的データの未使用領域
バケット数 16 8 バケット配列の要素数
状態フラグ 24 1 開きっぱなし(1<<0)、致命的エラー(1<<1)の論理和
動的予約領域 25 7 動的データの未使用領域
レコード数 32 8 格納しているレコードの数
ファイルサイズ 40 8 データベースファイルのサイズ
不透明データ 48 16 不透明データのサイズに対する2の冪乗

レコード部のフォーマット

フォーマット以前と変わっていないけれど、後で参照するのでここにも書いておこう。オフセットのサイズは、デフォルトだと6バイトで、スモールモードだと4バイトである。また、リニアモードの場合は右チェーンの領域がない。よって、キーと値とパディングの実データを除いたヘッダ部分の最小サイズ(つまりレコード毎のフットプリント)は、デフォルトで16バイト、スモールモードで12バイト、リニアモードで10バイト、スモールリニアモードで8バイトとなる。

名前 オフセット 長さ 機能
マジックナンバ 0 2 データの識別とパディングのサイズ
左チェーン 2 6 左チェーン接続先のオフセットのアラインメント商
右チェーン 8 6 右チェーン接続先のオフセットのアラインメント商
キーサイズ 14 可変 キーのサイズ
値サイズ 可変 可変 値のサイズ
キー 可変 可変 キーのデータ
可変 可変 値のデータ
パディング 可変 可変 意味を持たないデータ。先頭バイトは整合性チェッカ(0xEE)

レコードの削除や移動などでフリーブロックとなった領域には、以下のフォーマットでデータが記録される。ブロックサイズがデフォルトとスモールモードで違うのはレコードの時と同じである。

名前 オフセット 長さ 機能
マジックナンバ 0 2 データの識別(0xDDを2つ)
ブロックサイズ 2 6 ブロックのサイズのアラインメント商
パディング 8 可変 意味を持たないデータ。先頭バイトは整合性チェッカ(0xEE)

パディングのサイズはアラインメントサイズ未満であることが保証され、アラインメントの最大値は2<<15==32768であるため、つまりパディングのサイズはINT16_MAX以下であることが保証されている。したがって、レコードの先頭バイトは0x7f以下であることが保証され、0x80以上である場合にはフリーブロックであるということになる。なお、フリーブロックを再利用してレコードを記録した場合にはパディングのサイズがINT16_MAXを越えてしまう恐れがあるので、その場合はパディングを最小のアラインメントで切って、残りをフリーブロックとしてフリーブロックプールに再登録する。

レコード部の開始オフセットは、バケット部の末尾以降の最初のアラインメントの開始位置に合わせられる。

フリーブロックプール部のフォーマット

ヘッダ部の直後から、フリーブロックプールのサイズに6を掛けた長さの領域がフリーブロックプール部である。DBを閉じる時に持っているフリーブロックプールをオフセットの昇順で整列してから、各要素のオフセット部分を前の要素のオフセットとの差分に変換する。さらに各要素のオフセットとサイズの双方をアラインメントで割る。その値を先頭から順にBERエンコードで直列化して連結していく。そして最後に0x00を番兵として置く。

各要素をオフセット6バイトとサイズ6バイトの12バイトずつで直接化してもよかったのだが、それよりは差分列に圧縮して保存した方が領域を節約できる。ただし、常に圧縮率が50%を達成できるとは限らない。その場合に溢れた分は切り捨てる。フリーブロックプールはオマケ機能にすぎず、プールから消えたフリーブロックは別のデフラグ機能で回収することを期待すればよい。

バケット部のフォーマット

フリーブロックプール部の直後から、バケット数に6を掛けた長さの領域がバケット部である。スモールモードの場合は6でなく4となる。各要素はチェーンの先頭レコードのオフセットをアラインメントで割った値か、チェーンが空なら0が記録される。

TCではバケット全体をmmapで確保することを強制していたが、KCではその制限はなくなった。設定(tune_map)によって任意のサイズを指定して内部的にmmapを使わせることができる。0にもできるし仮想メモリの限界までとることもできる。mmapを使うのかpread/pwriteを使うのかFileクラスで完全に隠蔽されているので、ハッシュDB層ではそれについて考える必要はない。ただ、抽象化の分だけオーバーヘッドはでかくなっている。

おまけ

KCは動的ハッシュ系の手法を利用していないので、ハッシュバケットの利用率が高くなると性能が悪化する。レコードの参照にかかる時間は、各ハッシュバケットに連なるチェーンの長さに比例するので、その期待値をハッシュ表全体の「負荷」として可視化できると嬉しい。

バケット配列全体をスキャンするとその使用数がわかり、レコード数をバケット使用数で割ると、各バケットに連なるレコードの平均値が求まる。リニアモードの場合はその値がそのまま負荷となる。デフォルトでは、最初のレコードは1本道で、それ以後が2分探索木なので、リニアモードの値に1を足してから2の対数をとった値が負荷となる。以上の計算をコマンド一発「kchashmgr inform -st foobar」でできるようにしてあるので便利だ。