Groongaのパトリシアトライについてちょっとわかってきたつもりの阿部です。

ちょっと前に意気揚々とパトリシアトライのキーをデフラグする機能を追加したことを紹介したのですが、その機能にバグがありました。かなしい。

本記事ではどのようなバグがあってどのように修正したのかを紹介します。

バグの説明をするためにパトリシアトライのレコード削除やレコードの再利用について知っておく必要があるので、はじめにその辺の説明をします。

（前の記事の続編な内容なので、前回の記事を読んでから本記事を読んでもらえるとうれしいです。）

前提知識: パトリシアトライのレコード削除やレコードの再利用について

前の記事でわかりやすさ重視のため「削除されたキーの保存領域は再利用されない」と説明していましたが、実は再利用される場合があります。 （今回もこのあとの説明でわかりやすさを優先するため割愛している部分や厳密には正確ではない説明も含まれますがご了承ください。）

パトリシアトライでレコードを削除すると完全に削除するのではなく、「再利用BOX」のような場所に置かれます。 「再利用BOX」にデータは残るものの削除されたレコードではあるので、検索してもヒットはしません。

「再利用BOX」のデータは片っ端から再利用されるわけではなく、特定の条件のときのみ再利用されます。 それは追加するキーの長さと「再利用BOX」にあるキーの長さが同じときです。

また、再利用するときには 削除前に確保していた保存領域を再利用して上書きをします。

テキストだけだとわかりにくいので、前回と同様の図を使って具体例で説明をします。

このあとの具体例で使うデータや図について

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

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

キーの保存領域を図示:

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

再利用BOX: なし

削除

再利用するためにはデータを削除しないといけないので、まずは key-2 を削除するときを考えます。

削除前:

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

再利用BOX: なし

key-2を削除:

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

再利用BOX: key-2の保存領域の場所

..... の部分は key-2 を削除してできたすき間です。 このとき「再利用BOX」には「key-2の保存領域の場所」が保存されています。

追加（再利用あり）

key-2 の削除後に key-4 を追加するするときを考えます。 「再利用BOX」にデータがあり、追加するキーと「再利用BOX」にあるキーの長さが同じなので、key-2 の保存領域（..... の部分）が再利用されます。

追加前:

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

再利用BOX: key-2の保存領域の場所

再利用して追加後:

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

再利用BOX: なし

key-2 の保存領域が再利用され、key-4 が保存されました。また key-2 は再利用されたので「再利用BOX」も空になります。

バグの説明

以上の再利用の挙動を踏まえバグを説明します。 端的にいうと デフラグ時に「再利用BOX」をクリアしなかったから です。

具体例で説明するのがわかりやすいので、具体例で説明します。

先程の key-2 を削除したあとのデータを例に使います。

key-2を削除:

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

再利用BOX: key-2の保存領域の場所

この状態でデフラグをします。すると次のようになります。

デフラグ実行後:

|key-1|key-3|

再利用BOX: key-2の保存領域の場所

削除済の ..... の部分が詰められました。ただ「再利用BOX」をクリアしていないので「再利用BOX」には "key-2の保存領域の場所" が残っています。

ここで考えてほしいのは "key-2の保存領域の場所" がどこを指しているかです。 答えはデフラグ前に ..... があった場所なので、デフラグ後の key-3 がある場所を指しています。

この状態で key-4 を追加するとどうなるでしょうか？

「再利用BOX」にデータがあり、キーの長さも同じなので再利用が起こります。 そしてその再利用する場所は key-3 の場所なので key-4 を追加すると次のような状態になります。

key-4 追加後:

|key-1|key-4|

再利用BOX: なし

ということで、key-3 が上書きされて key-4 になりました。明らかにキーのデータがおかしなことになっています。

このように想定外の再利用が起こりキーが壊れる、というのが今回のバグです。

修正

デフラグ後も「再利用BOX」にデータが残っていて不正な再利用が生じたことが原因なので、デフラグ時に「再利用BOX」をクリアするようにしました。

バグ修正前のデフラグ後:

|key-1|key-3|

再利用BOX: key-2の保存領域の場所

バグ修正後のデフラグ後:

|key-1|key-3|

再利用BOX: なし

「再利用BOX」をクリアしたことで不正な再利用が発生しなくなりました。

参考: バグ修正後のデフラグ後に key-4 を追加すると以下の状態になります。

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

再利用BOX: なし

まとめ

便利機能を追加したつもりがバグがあったので修正した話でした。

本記事では再利用についてのみ触れましたが、パトリシアトライのレコード削除にはいろいろややこしい処理があります。 今回のバグ調査・修正でそのあたりに理解も深まったので、別記事として紹介するので乞うご期待！

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

おまけ: 再利用の条件について補足

再利用の条件に "追加するキーと「再利用BOX」にあるキーの長さが同じ" があります。 なぜこの条件が必要かを補足説明します。

これまでの説明で想像できていると思いますが、この条件がある理由はキーの長さが同じでないとデータの保存領域が無駄になったり、データが壊れたりするからです。

追加前:

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

再利用BOX: key-2の保存領域の場所

キーの長さが短いk-5を、key-2 の保存場所を再利用して追加:

|key-1|k-5..|key-3|

再利用BOX: なし

再利用データの key-2 は長さ5、追加したいキー k-5 は長さ3、なので .. の長さ2が余ります。これは無駄です。

キーの長さが長いkey-66を、key-2 の保存場所を再利用して追加:

|key-1|key-6|6ey-3|

再利用BOX: なし

再利用データの key-2 は長さ5、追加したいキー key-66 は長さ6、なのではみ出ます。 はみ出たことで key-3 が 6ey-3 になってしまいデータが壊れてしまいます。

ということで、"キーの長さが同じ" が条件になっています。