Groonga: パトリシアトライのキーをデフラグ

Groongaの開発をがんばっている阿部です。

最近はパトリシアトライのキーをデフラグする機能を実装したのでその機能について紹介します。

（わかりやすさを優先するため説明を割愛している部分や厳密には正確ではない説明も含まれますがご了承ください。）

前提: パトリシアトライのキーの追加と削除

課題があったのでデフラグ機能を実装したわけですが、その課題を理解するため「パトリシアトライのキーの追加と削除」について説明します。

key-1、key-2、key-3 という5バイトの文字列がキーとして3つ登録されてある状態を例に使います。（例ではサイズの計算をわかりやすくするためにすべてのキーのサイズを5バイトにしていますが、実際はいろいろなサイズのキーです。）

境目がわかりやすいように | で区切り、キーの保存領域を次のように図示して説明します。

キーの保存領域を図示:

|key-1|key-2|key-3|

追加

キーを保存するための領域にキーを追加していきます。

追加前（計15バイト使用）:

|key-1|key-2|key-3|

key-4を追加（計20バイト使用）:

|key-1|key-2|key-3|key-4|

追加する場合は末尾に追加していくだけなのでシンプルです。

削除

削除の場合は該当の領域からデータだけ削除するイメージです。結果としてすき間のあるデータになります。

削除前（計20バイト使用）:

|key-1|key-2|key-3|key-4|

key-2を削除（計20バイト使用）:

|key-1|.....|key-3|key-4|

..... の部分は key-2 を削除してできたすき間です。注目すべきは 削除しても使用領域が減らない ことです。

削除後に追加

また、すき間の部分は再利用されることなく、ずっとすき間のままです。

追加前（計20バイト使用）:

|key-1|.....|key-3|key-4|

key-5を追加（計25バイト使用）:

|key-1|.....|key-3|key-4|key-5|

..... のすき間は使われることなく、末尾に key-5 が追加されます。

課題

上述の説明でだいたい課題はおわかりかと思いますが改めて説明します。

パトリシアトライの最大総キーサイズは4GiBです。上限の4GiBを超えるとデータの追加ができなくなります。

データを削除しても使用領域が減らないため、レコード数は多くないはずなのに最大総キーサイズを超えてしまうことがあります。例えば、追加と削除を繰り返すことですき間が大量に発生している場合に起こりえます。残っているレコードの総キーサイズだけを見ればデータが追加できるはずなのに、すき間が使っている使用領域が原因で最大総キーサイズを超えてしまい、データの追加ができなくなります。

このようにすき間が原因でデータの追加ができなくなることが課題でした。

対応方針

ということで、すき間をどうにかすればデータを追加できるようになります。

今回はユーザに明示的にデフラグを実行してもらう方針にしました。デフラグを実行することですき間を詰めて使用領域を減らします。

デフラグ前（計25バイト使用）:

|key-1|.....|key-3|key-4|key-5|

デフラグ後（計20バイト使用）:

|key-1|key-3|key-4|key-5|

これによりすき間がなくなり使用領域が減るのでデータが追加できるようになります。

対応方針: 補足

デフラグ以外では追加のときにすき間があったらそこを再利用する方法もあります。

追加前（計25バイト使用）:

|key-1|.....|key-3|key-4|key-5|

key-6を追加（.....のすき間を再利用）（計25バイト使用）:

|key-1|key-6|key-3|key-4|key-5|

この例のようにすき間と追加するキーのサイズが同じであればぴったり収まりますが、すき間と追加するキーのサイズが一致するとは限りません。

などなど、追加時にすき間を再利用する方法は複雑になりすぎる懸念などがあり、今回はデフラグですき間を一括削除する方針にしました。

デフラグする方針を決めるやりとりは「Groonga開発者に聞け！（グルカイ！）第84回」に残っているので、合わせてご視聴ください。

実装概要

対応方針が決まればあとは実装するだけなので、実装しました。詳細な説明は長くなるのと複雑になるので、概要の紹介にとどめます。

|key-1|.....|key-3|key-4|key-5|

↑を例にすると key-1 と key-3 の間にすき間があるので、key-3 以降をすき間のサイズ分スライドしてすき間を詰めるイメージです。これを繰り返すことですべてのすき間が詰められ、キーの保存領域が増えます。

使い方

Groongaの defrag コマンドでデフラグできます。

Groongaコマンド例:

defrag TABLE_NAME

デフラグを実行するときは、万が一のDB破損に備えバックアップを作成の上、DBへアクセスを停止して実行してください。

デフラグの手順

Linuxでの手順です。 DB_PATH は対象のDBファイルのパスに、TABLE_NAME は対象のテーブル名に置き換えてください。

デフラグの準備: 対象のテーブルから不要なキーの削除
- 削除しておかないと defrag で領域が増えないため
DBへのアクセスを停止
groonga DB_PATH select TABLE_NAME --output_keys _id,_key --limit -1 --output_pretty yes > before_keys.json を実行
- defrag の成否確認に利用する
groonga DB_PATH io_flush を実行
- バックアップの前にメモリー上のすべての変更を明示的にディスクに書き出す必要があるため
DBファイル全体をコピーしてバックアップ
- スパースファイル¹が含まれるので、tar の --sparse を利用してバックアップ
- コマンド例: tar --sparse -czf backup.tar.gz DB_PATH
  - 適宜 -C と組み合わせて tar --sparse -czf backup.tar.gz -C BASE_DIR DB_DIR のように実行するとよい
groonga DB_PATH defrag TABLE_NAME
- デフラグ中はDBへのアクセスがない状態で実行する
groonga DB_PATH select TABLE_NAME --output_keys _id,_key --limit -1 --output_pretty yes > after_keys.json を実行
- defrag の成否確認に利用する
diff before_keys.json after_keys.json で defrag の成否を確認
- ヘッダ部分以外で差分がなければ defrag に成功したので運用再開
  - ヘッダ部分のコマンド開始時間などで差分が出ますが、_idと_keyに差分がなければOK
- ヘッダ部分以外で差分があれば defrag に失敗したので復旧

万が一破損してしまった場合の復旧方法

復旧Aと復旧Bの2つの復旧方法を紹介します。いずれかの方法で復旧できれば他の復旧方法の実行は必要ありません。

復旧A（基本的にはこの手順で復旧できるはずです、おすすめ）
- バックアップしたDBファイル全体から対象のテーブルに対応するファイルのみコピーして復旧する
- 対象のテーブルに対応するファイルはGroongaコマンド: object_list で確認できる
  - jq コマンドと組み合わせると groonga DB_PATH object_list | jq '.[1].TABLE_NAME.path' で確認できる
- 復旧の成否は上述の手順の6と7で確認する
復旧B
- バックアップしたDBファイル全体をコピーして復旧する
- 復旧の成否は上述の手順の6と7で確認する

まとめ

パトリシアトライのキーをデフラグする機能を実装したので紹介しました。これでパトリシアトライのキーの領域を効率的に利用できるようになります。

具体的なデフラグの手順なども紹介したので、キーの上限問題で困っている場合はぜひお試しください。

Groongaの利用でお困りのことがありましたら、お問い合わせよりご連絡ください。

空の領域が含まれるファイルを効率的に保存する仕組みです。詳しくは参考ページをご覧ください。参考1: スパースファイル - ArchWiki。参考2: スパースファイル - Win32 apps。 ↩

ククログ