Groongaには可変長データを削除・更新しつづけるとデータベースのサイズが大きくなり続けてしまうという問題があります。次回のリリースではこの問題が解消される見込みで、現在、ユーザーにテストをお願いしています。（詳細は[groonga-dev,02173] データベース肥大化に悩むみなさんへテストのお願いを参照。）

ここでは、Groongaがどうやって可変長データを管理していて、どのようにして肥大化を抑えるようにしたかを説明します。

前提

Groongaは新しい鮮度のよい情報をすぐに検索できることを重視しています。そのため、データ更新時も検索性能を落とさないことを重視した設計になっています。具体的には参照ロックフリーという性質を実現しています。

参照ロックフリーとはデータを更新している最中でもデータを読み込める性質のことです。この性質のおかげでデータ更新中でもデータを参照できるため、検索処理がブロックしません。そのため、検索性能を落とさずに済みます。

参照ロックフリーを実現するための基本的な考えは次の通りです。

• インプレースでの値の変更はアトミックに実行できる操作のみ。
  • 例えば、32bit整数の変更はアトミックな操作。
• アトミックに変更できない値は別の場所に新しい値を用意して、そこを指す位置だけをアトミックに変更する。
  • 位置は32bit整数などアトミックに変更できる値にする。

32bit整数の値は前者の考えを使います。

文字列は後者の考えを使います。

文字列を含む可変長データはアトミックに変更できない値なので後者の方法で参照ロックフリーを実現しています。

データの更新方法の概要を説明したので、次はデータの管理方法を説明します。

データの格納方法

Groongaはデータのサイズで可変長データの格納方法を変えています。

• 小さなサイズのデータは固定長の領域の中に格納。
  • データによっては使われない領域ができる。
• 大きなサイズのデータは前のデータの次の場所に連続して格納。
  • 隙間なくデータを詰める。

小さなサイズのデータの格納方法を図示するとこうなります。

大きなサイズのデータの格納方法を図示するとこうなります。

データベースの肥大化の要因は大きなサイズのデータの格納方法にあります。

単に追加するだけの場合は大きなサイズのデータの格納方法の方が空間効率がよく、順番にデータにアクセスする場合は速いです。しかし、データの削除・更新を実行するとそのメリットが崩れていきます。

大きなサイズのデータの更新

Groongaは参照ロックフリーを実現するために、可変長データを更新するときはインプレースで書き換えません。新しい値を用意してそこへの参照を書き換え、古いデータには削除マークをつけます。

図示するとこうなります。

削除する場合は単に削除マークをつけるだけなので更新の特別な場合と考えることができます。よって、ここでは更新操作についてのみ説明します。

更新操作をするたびに削除マークがついた未使用の領域が増えます。未使用の領域が増えると空間効率が悪くなり、順番にデータにアクセする速度も遅くなります。データが連続していないからです。フラグメンテーションが起きている状態です。

削除マークをつけた領域を使わないのはもったいないので、しばらくすると再利用します。しかし、再利用する条件がシビアです。そのため、再利用はなかなか進みません。これが、データベースが肥大化する原因です。

大きなサイズのデータを格納する領域は一定のサイズごとに塊になっています。具体的には4MiBごとの塊になっています。たとえば、合計12MiBのデータを利用する場合は、きっちり隙間なく詰められたとすると3つの塊が必要だということです。

削除マークがついた領域を削除する条件はこの4MiBの塊全部の領域に削除マークがついた場合です。1つでも使っている領域が残っていればその塊の中の削除マークつきの領域は再利用されません。すべて削除マークがついてようやく再利用対象になります。

図示するとこうなります。

つまり、1つでもずっと更新されないレコードがあると再利用されないということです。

データベースの肥大化を抑える方法

それでは、どうやってこの「大きなサイズのデータを更新しつづけるとデータベースが肥大化していく」問題を解決したかを説明します。

「小さなサイズ」と扱う範囲を広げました。

後述しますが、小さなサイズのデータの格納方法は比較的再利用されやすい方法になっています。そこで、よく使われるサイズのデータを小さなサイズのデータと扱うようにしました。

具体的には、これまでは128バイト未満のデータを小さなサイズのデータと扱っていたものを64KiB未満のデータを小さなサイズのデータと扱うようにしました。Groongaでは一番小さな文字列型のサイズが4KiBなので、そのサイズをカバーしています。また、多くのテキストデータは64KiB未満になることが多いため、多くのデータが小さなサイズのデータ扱いとなります。

小さなサイズのデータの格納方法は大きなサイズのデータの格納方法に比べて空間効率がよくないので追加のみのユースケースではこれまでよりもデータベースサイズが大きくなります。

Groongaは新しい情報を提供することに価値をおいているので、更新するユースケースでのメリットが非常に大きいと考えて、次のリリースからこの肥大化を抑える方法を有効にする予定です。

小さなサイズのデータの更新

それでは、小さいサイズのデータの更新方法を説明して終わりにします。

小さいサイズのデータも、新しい値を作ってからその参照を書き換えて古い値に削除マークをつける、という更新方法は同じです。そのため、それについての説明は省略します¹。削除マークがついた領域の再利用条件についてだけ説明します。

小さいサイズのデータも4MiBごとの塊の中にデータを格納しているのは同じです。塊の中で10個以上削除マークがついた領域ができると削除マークがついた領域を再利用します。大きなサイズのデータよりもだいぶ緩い条件です。

図示するとこうなります。

レコードが10件更新されるだけで再利用条件を満たすので、再利用頻度がだいぶあがります。再利用が増えるのでデータベースの肥大化を抑制できるというわけです。

まとめ

• Groongaには可変長データを更新しつづけるとデータベースが肥大化するという問題があった。
• 次回のリリースからその問題が解消する。
• 64KiB未満のデータを再利用しやすい格納方法に変更することで解消。
• 解消方法をテストしてくれる人を募集している。
  • 詳細：[groonga-dev,02173] データベース肥大化に悩むみなさんへテストのお願い

1. データのサイズごとに固定長の領域のサイズを変えて隙間をできるだけ小さくしようとしているということは説明したほうがよいのですが、省略します。 ↩