データベースの動的デフラグ

ノートPCの冷却ファンがうるさいのを対処しようとしてWebで調べたら、そのファンの設計者が﹁静音性へのこだわり﹂を語ったページにたどり着いて複雑な心境のmikioです。今回は、Tokyo Cabinet︵TC︶の最新バージョンで実装された動的デフラグ機能について長々と説明します。

断片化とデフラグ

任意のサイズのデータを管理する記憶装置においては、利用可能領域の断片化︵fragmentation︶の問題が常につきまといます。ファイルシステム上で任意のサイズのファイルを管理する際にも、データベースファイル内で任意のサイズのレコードを管理する際にも、C言語のmalloc/free関数群でメモリの管理をする際にも、様々なレイヤで断片化が起きうるのです。なぜなら、データを削除もしくは移動した際の空き領域を再利用するにあたって、その領域と同じサイズのデータが常に入ってくるとは限らないからです。特にデータのサイズが変わるような更新操作を頻繁に行う場合や、サイズがまちまちのデータの追加や削除を頻繁に行う場合には、断片化の問題が顕著になります。断片化が進むと占有領域がどんどん肥大化してしまい、性能が悪化したり、それ以上データが入れられなくなったりといった不都合が起こることになります。


断片化を解消するには、使用している領域を連続した場所に詰めて再配置するとともに、空き領域も連続させて再配置して再利用可能にすることが必要です。そのような操作を﹁デフラグ︵defragmentation︶﹂と呼びます。Windowsのコントロールパネルなどからファイルシステムのデフラグをかけた経験のある方も多いと思います。メモリ管理のレイヤでは﹁コンパクション﹂と呼ばれる機能として実装されています。TCでも従来からデフラグ機能を最適化という名目で実装しています。


なお、TCには従来から﹁フリーブロックプール﹂という機構があります。空き領域のリストを管理して、新たにレコードの領域を割り当てる際に、空き領域の中で要求サイズ以上の最小の領域を再利用することで断片化の影響を最小化するものです。割り当てた領域と空き領域の差分︵余り領域︶が一定サイズ以上であればさらに空き領域としてリストに還元するといった工夫もしています。しかし、そこまでしても、固定長でなく任意のサイズの領域を割り当てようとする時点で、余り領域が各所に発生するのは避けられず、断片化は起きてしまうのです。

静的デフラグと動的デフラグ

一般的に言って、ファイルシステムやデータベースの文脈でいうところの﹁デフラグ﹂ないし﹁最適化﹂という操作は、その操作をしている間にその記憶領域全体が掌握されて、他の操作ができなくなることが多いです。このような静的かつ大域的なデフラグ操作をここでは﹁静的デフラグ﹂と呼ぶことにします。それに対して、記憶領域全体を掌握することなく、他の操作と並行に行われるような局所的なデフラグ操作を﹁動的デフラグ﹂と呼ぶことにします。TCのoptimize系メソッドは静的デフラグですし、MySQLなどのRDBMSで使われるoptimize文も静的デフラグです。一方でZFSやBtrfsなどの新しめのファイルシステムでは動的デフラグを実装しているようです。

静的デフラグの実装は比較的単純で、他スレッドの更新操作をブロックしてしまえばレースコンディションにまつわる複雑な問題に悩まされずに済むので、結果的に効率的な処理を実現することが容易になります。しかし、デフラグをかけている数秒から数分の間に更新操作ができないというのは、24時間365日稼働のWebサービスのバックエンドに適用するには辛いものがあります。RDBMSの場合、デュアルマスタのレプリケーション構成でアクティブマスタを切り替えながら最適化をかけるといったワークアラウンドもありますが、できればそういう面倒は避けたいものです。一方で、動的デフラグであれば、アベイラビリティの問題を特に意識することなく、ストレージのサイズとパフォーマンスを一定に保つことができます。

ということで、TCに動的デフラグを実装してTokyo Tyrant︵TT︶から利用可能にすることで、24*365対応が必要な皆様のハートにアピールしてしまおうという魂胆です。実装が複雑になりがちですが、それだけの価値があるでしょう。

動的デフラグの実装

レコードの使用領域と空き領域が混在している状態が断片化であるわけですから、それを解消するには、使用領域は使用領域だけで集めて連続した位置に詰めて配置し、空き領域は空き領域で集めて連結して一つの領域にしてフリーブロックプールに入れるという操作を行えばよいことになります。

TCでは、ハッシュデータベース内部に動的デフラグ用のイテレータを備えています。データベースを開いた際にはイテレータはデータベースの先頭に配置され、動的デフラグの遂行が指示される度に、イテレータの位置の領域を読み込みます。読み込んだ領域がレコードであればイテレータを次の領域まで進めます。読み込んだ領域がフリーブロックであれば、次のレコードを読むまでフリーブロックを読み飛ばし、そのレコードをイテレータの位置に移動させて、イテレータをその直後まで進めます。レコードが元々あった領域は空き領域になり、かつ既存のフリーブロックと隣接しているので、連続したフリーブロックを連結した領域とみなし、それをフリーブロックプールに登録します。


動的デフラグ用イテレータがファイルの末尾まで到達した場合、直前のレコードの末尾をファイルの終端とみなしてtruncateしてファイルサイズを縮めるとともに、イテレータをファイルの先頭まで戻します。末尾まで到達しなかった場合でも連結されたフリーブロックがフリーブロックプールに戻されて再利用されるので、以降の更新操作で肥大化が起きる確率をどんどん下げていくことができます。

なお、B+木データベースやテーブルデータベースはハッシュデータベースの上に実装されているので、ハッシュデータベースの機能追加の恩恵は自動的にB+木データベースやテーブルデータベースにも波及します。固定長データベースはそもそも断片化が起きないのでデフラグという概念もありません。

使い方

まず、TCおよびTTの最新版をインストールしてください。それで、TCの各種データベースオブジェクトを開く部分のコードに、以下のような自動デフラグの設定を追加してください。ハッシュデータベースでもB+木データベースでもテーブルデータベースでも使い方はほぼ同じです。

TCHDB *hdb = tchdbnew();
tchdbsetdfunit(hdb, 8);  // 必ずopenの前に呼ぶ
tchdbopen(hdb, "casket", HDBOWRITER | HDBOCREAT);

上記でtchdbsetdfunit関数に与えている引数﹁8﹂は、断片化を8回検出したら、それに相当する領域を回収するくらいの動的デフラグ操作を暗黙的に行うという意味です。動的デフラグといえども、その操作を行っている間は該当する領域をロックせざるを得ないので、その処理の粒度を指定することは比較的重要です。﹁1﹂などとして粒度を小さくすれば並行性は上がりますが、一度に処理できる領域が限られるので時間効率と空間効率は下がります。逆に﹁128﹂などとして粒度を大きくすれば、一度に処理できる領域が増えて時間効率と空間効率を上げられますが、その間に他の操作がブロックされる確率も上昇します。私の経験では、ハッシュデータベースでは8くらい、B+木データベースでは2くらい、テーブルデータベースでは4くらいにすると丁度良いような気がしています。なお、デフォルトでは自動デフラグ機能は無効化されています。

抽象データベースでは以下のようにopenの際にパラメータを指定します。抽象データベースから使えるということはTTからも起動時に指定するだけで使えるということですね。楽ちんです。

TCADB *adb = tcadbnew();
tcadbopen(adb, "casket.tch#dfunit=8");

断片化を検出する度にデフラグを少しずつ進めるというのは多くのユースケースで妥当な選択なのですが、高負荷なWebサービスのバックエンドに用いる場合は事情が異なります。例えばmixiの場合、午後11時から日付変わって午前1時までのいわゆるピークタイムの負荷は、それ以外の時間帯の負荷に比べると3倍もしくはそれ以上になります。ピークタイムの負荷がバックエンドに対する要求スループットを決定するので、ピークタイムには余計な処理をしたくないというのが本音です。デフラグなんてのは負荷の比較的低い時間帯にちょこちょこやれば十分でしょう。ということで、任意のタイミングで明示的に動的デフラグ操作を進められるようにもしています。

tchdbdefrag(hdb, 8);

暇な時間帯であれば、更新操作を行った後に上記の関数を呼ぶというのもよいし、別スレッドを立てて継続的に上記の関数を呼ぶというのでもよいでしょう。例によって﹁8﹂は、8個分の空き領域を回収するという意味です。ここで﹁0﹂を指定すると、データベース全体を動的にデフラグします。全体にやったら静的デフラグじゃないかと言われそうですが、微妙に違います。排他制御のロックをかけたり外したりを繰り返しながら休み休みで処理を進めるので、見掛け上、他のスレッドがブロックされないのです。

性能

動的デフラグの性能を見るための恣意的なテストプログラムを実行してみました。アラインメントやフリーブロックプールが効かないようにチューニングした上で、できるだけたくさん断片化が起きるように、まちまちのサイズのレコードを追加したり削除したりを1000万回繰り返すものです。以下のような結果になりました。

	DBサイズ	経過時間
デフォルト	270.58 MB	54.853 秒
dfunit=8	74.797 MB	43.242 秒

データベースのサイズを30%以下に抑えつつも、処理時間が79%に短縮されています。空間効率が上がった分だけ、時間効率も下がるという素晴らしい結果になっています。また、上記のデータベースに静的デフラグをかけると65.33MBになりました。

処理内容は複雑化しているのに時間効率が上がるというのはちょっと不思議な感じがしますね。動的デフラグの処理の中では、I/Oをするにしても同一もしくは隣接ブロックの読み書きをするケースがほとんどなので、ファイルシステムのキャッシュが効きやすく、性能劣化の原因になりにくいと考えられます。その上で、データベースが小さくなった分だけファイルI/Oが効率化されたり各種のレイヤでキャッシュが効きやすくなるのが全体の処理速度を高速化した原因となっていると考えられます。

こんなにいいことずくめならデフォルトで動的デフラグを有効化しろという声も聞こえてきそうですが、肥大化が問題になりにくいようなユースケースで動的デフラグ有効にしてもオーバーヘッドになるだけですし、前述の明示的なデフラグ操作を行いたい場合も多いでしょうから、デフォルトでは依然として無効にしています。

永続的だが時限的なキャッシュ、再び

以前に書いたテーブルデータベースの記事で述べた、期限付きのセッション情報を永続記憶装置上で保持するユースケースを再び考えてみます。TCのテーブルデータベースのコラムとして期限切れ時刻を持たせて、1秒毎に起動する削除関数で古いレコードを消していくというものです。実はこれは最も断片化を起こしやすいユースケースのひとつで、今回の動的デフラグ機能は、キャッシュの肥大化に対して静的なoptimizeをせずに対処するために用意したようなものです。

おさらいになりますが、テストしてみましょう。以下のLuaスクリプトを準備して、ttexpire.luaとして保存してください。

function expire()
   local args = {}
   local cdate = string.format("%d", _time())
   table.insert(args, "addcond\0x\0NUMLE\0" .. cdate)
   table.insert(args, "out")
   local res = _misc("search", args)
   if not res then
      _log("expiration was failed")
   end
   print("rnum=" .. _rnum() .. "  size=" .. _size())
end

まずは、動的デフラグを無効にした状態で、どれくらい肥大化が起きるかを確認しておきます。以下のようにしてサーバを立ち上げてください。

ttserver -ext ttexpire.lua -extpc expire 1 "casket.tct#idx=x:dec#bnum=2000000"

別の端末を開いて、以下のテストコマンドを実行します。これは、50%の確率でランダムなセッション情報を格納し、10%の確率でその削除を試み、40%の確率でセッションの読み出しを行うというクエリを1000万回発行するテストを行います。セッションは入れられた時刻から180秒後に期限切れになって自動削除されます。

tcrtest table -exp 180 localhost 10000000

私の環境では、上記の条件だとだいたい130万セッションくらいを保持した状態でデータベースが維持され、598秒でテストが完了しました。つまり130万セッション保持で16722QPSくらいの性能は出そうです。それはよいのですが、問題は、データベースのサイズが213MBにもなってしまったことです。この調子でサイズが肥大化していけば性能もだんだん劣化してくるので最適化をかけるわけですが、この状態で﹁tcrmgr optimize localhost﹂したところ、12.6秒かかってサイズは102MBになりました。このことから、このアクセスパターンではDBが約2倍に肥大化するということと、それを解消するための静的デフラグには約13秒間のブロッキング︵＝サービス停止︶が発生することがわかります。うーむ。それくらいなら無理からぬ運用体制とも言えますが、正直イマイチですね。

今度は、データベースを作り直して、動的デフラグを有効にしてサーバを起動します。

rm -rf casket*
ttserver -ext ttexpire.lua -extpc expire 1 "casket.tct#idx=x:dec#bnum=2000000#dfunit=8"

クライアント側は同じコマンドです。

tcrtest table -exp 180 localhost 10000000

今度は599秒かかり、サイズは133MBでした。つまり肥大化率を1.3倍に抑えて定常運用できるということです。このサイズは同じ処理をいくら続けても増えることはないので、最適化をかける必要はありません。これで安心してセッション情報を入れ続けることができます。

ピーク時のスループットを重視して、ピーク時以外に動的デフラグをかけたい場合には、以下のLuaスクリプトを30分間隔くらいで定期実行︵-extpc defrag 1800︶するとよいでしょう。動的デフラグなので実行中も他の操作をブロックしないというのがポイントです。

function defrag()
   local time = tonumber(os.date("%H%M"))
   if time >= 2230 or time <= 0130 then
      return nil
   end
   if not _misc("defrag") then
      _log("defragmentation was failed", 2)
   end
end

まとめ

Tokyo Cabinetで実装された動的デフラグ機能の設計と実装について説明し、その性能を確認しました。動的デフラグを有効にすると、サービスを止めてoptimizeすることなく、データベースの肥大化を抑制しながら運用を続けることができます。また、暗黙的な動的デフラグと明示的な動的デフラグを使い分けることで、実サービスのアクセスパターンを踏まえてスループットを追求することができます。そして、それらの工夫で﹁永続的だが時限的なキャッシュ﹂のアベイラビリティを向上させられることを示しました。地味な機能を長々と語りましたが、ここまで読んでくれたあなたはその価値をわかってくれますよね？

余談ですが、またもt.maesaka氏が主導して開発を進めているTCを使ったMySQLのストレージエンジン﹁BlitzDB﹂でも動的デフラグ機構は活用されるようです。optimizeしないで運用できるというだけでもMyISAMに対してちょっぴりアドバンテージがあるかなと思っている次第です。