grn_dat - 参照ロックフリーなダブル配列
注意: トライやダブル配列に関する知識があっても何のことやらサッパリ分からないかもしれません．
written by Susumu Yata.
はじめに
grn_dat は，キーと ID の関連付けに用いるモジュール grn_pat, grn_hash の新しい仲間です．Common prefix search と Predictive search をサポートしつつ，高速な参照を実現します．その代わり，メモリ消費が大きいという欠点があります．特性を簡単にまとめると以下のようになります．
| モジュール名 | データ構造 | 検索機能 | 時間効率 | 空間効率 |
|---|---|---|---|---|
| grn_pat | パトリシアトライ | ◎ | △ | ◎ |
| grn_hash | ハッシュ表 | △ | ◎ | ○ |
| grn_dat | ダブル配列 | ○ | ○ | △ |
grn_dat の役割は，grn_pat, grn_hash の隙間を埋めることです．Common prefix search や Predictive search が必要だけど，grn_pat では十分な速度が確保できないという悩みを解決します．また，grn_pat, grn_hash で課題となっていた「ID を変更せずにキーのみを差し替える機能」を持っているので，groonga の使い勝手を向上させるという面でも活躍します．
もちろん，groonga の特徴である参照ロックフリーを実現しているため，更新をおこなってしているときでも，別のプロセス・スレッドでは問題なく参照できます．
データ構造
grn_dat の基本的なデータ構造はダブル配列です．ただし，単純な実装ではキーと ID の相互参照およびに参照ロックフリーを実現できないため，いくつかの拡張を施しています．
キーと ID の相互参照に関する拡張では，キーを入力して ID を求めるだけでなく，ID を入力してキーを取得するという使い方も想定しているので，本来のダブル配列ではキーの後半部分のみを残すのに対し，grn_dat ではキー全体を残すようにしました．結果として，最小接頭辞（Minimal prefix）トライ，キーを詰め込むためのプール，ID からキーの格納位置を求めるための配列という構成になっています．キーを入力したときは，まずトライを探索し，葉からキーのプールへのリンクをたどることになります．一方，ID を入力したときは，ID からキーの格納位置を求めて，キーのプールを参照することになります．
参照ロックフリーについては，ノードの再利用を禁止するとともに，CHECK の内容を親のノード番号からラベルに変更しました．また，これらの変更によって生じる問題を解決するため，ノードをブロック単位で管理するようにしただけでなく，従来とは少し異なる管理方法を採用しました．さらに，削除・更新における問題を解決するため，葉に ID を持たせるのではなく，葉にはキーの格納位置を持たせ，キーのプールに ID を格納するようにしました．詳細は後述します．
参照ロックフリー
groonga の魅力的な特徴の一つが参照ロックフリーです．更新しているから参照できない，あるいは参照しているから更新できないということがなく，応答性・即時性の高いシステムを実現できます．groonga のモジュールである grn_dat は，もちろん参照ロックフリーです．
ノードの再利用
残念ながら，本来のダブル配列は参照ロックフリーなデータ構造ではありません．更新によってノードの配置が変化したり，破棄された領域が再利用されたりと忙しいため，更新と並行して参照をおこなうと，どこに行き着くのか想像もつきません．たとえば，参照において，あるノードにたどり着いたとき，そのノードが更新によって破棄，再利用されると，まるで別のパスをたどってきたかのように見えてしまいます．この問題は，存在しないはずのキーが見つかったり（False positive），逆に存在するはずのキーが見つからなかったり（False negative）という誤りにつながります．
そこで，ノードの再利用はしないという方針が生まれます．具体的には，ノードの移動に際して，新しいノードを配置するだけで，古いノードはそのままにしておくという手法です．移動したノードの数に比例して無駄な領域が増えるという欠点はあるものの，上述の参照誤りは防ぐことができます．空間効率の悪化については，あらかじめ確保しておいた領域を使い切った時点で，領域の拡張と併せて無駄なノードの除去もおこなうことにより改善できます．
親子関係の表現
次に重要な問題は，本来のダブル配列ではノードの移動をアトミックに実現できないことです．例として，あるノード S が親ノード P と子ノード C を持つ状態から，ノード S をノード S' に移動するとき，つまり親子関係はそのままにノード番号が S から S' に変更するときを考えてみます．移動前の状態では，ノード P, S, C の親子関係は以下のように表現されています．
BASE[P] ⊕ LABEL[S] = S; // ⊕ は排他的論理和（XOR）の意味で用いています．
CHECK[C] = S;
次に，ノード S の移動後は以下のようになります．LABEL[S] はノード S のラベルであり，LABEL[S'] とは等しくなります．
BASE[P] ⊕ LABEL[S'] = S';
CHECK[C] = S';
すなわち，BASE[P] と CHECK[C] の書き換えによって親子関係が引き継がれることになります．
問題が顕在化するのは，CHECK[C] が更新されていない状況でノード S' に到達したときと，CHECK[C] が更新されている状況でノード S に到達したときです．前者は BASE[P] を先に更新したとき，後者は CHECK[C] を先に更新したときに発生する可能性があります．そして，ノード P の子ノード（ノード S とその兄弟ノード）と孫ノード（ノード S の子・甥・姪ノード）がたくさんあるときは，整合性の取れない状態が長く続くため，問題が顕在化しやすくなります．
この問題を解決する方法は，CHECK に格納する内容を親のノード番号からラベルに変更し，ノード P, S, C の親子関係を以下のように表現することです．
BASE[P] ⊕ LABEL[S] = S; // 従来と同じです．
CHECK[C] = LABEL[C]; // S から LABEL[C] になりました．
ノード S の移動後は以下のようになります．
BASE[P] ⊕ LABEL[S'] = S'; // 従来と同じです．
CHECK[C] = LABEL[C]; // S' から LABEL[C] になりました．
つまり，BASE[P] は従来と同様に書き換えますが，CHECK[C] は書き換えなくてもよくなります．BASE[P] の書き換えのみであれば，アトミックな操作になるため，整合性の取れないタイミングをなくすことが可能です．
未使用領域の管理
ノードの再利用を禁止し，CHECK の内容をラベルに変更して，さらにフラグの設定と値の更新などをまとめてアトミックな操作にすれば，参照ロックフリーなダブル配列は実現できます．しかし，衝突が起きたときに兄弟ノードが少ない方を選んで移動するという経験則が適用できなくなるため，従来のダブル配列と比べて移動すべきノードが多くなり，移動先の選定にかかる時間がとても長くなるという問題があります．主因はノードの再利用を禁止したことですが，CHECK の内容をラベルに変更するだけでも，衝突が起きたノードの親が分からなくなるので同様の問題にたどり着きます．
移動するノードの数が多くなるような状況では，未使用領域をブロック単位で管理し，無駄な探索を減らす手法が有効です．具体的には，兄弟ノードが同じブロックに配置されるようにブロックのサイズを設定し，各ブロックに未使用領域の大きさを持たせたり，ブロック内部の未使用領域を連結リストで管理したり，未使用領域の割合によってブロックを別々に管理したりします．ブロック単位で探索をスキップできるので，未使用領域を一つずつ確認するより効率的になります．
注目すべきことは，隙間なく詰め込むと次の更新でノードを移動する以外の手段がなくなることです．意外なことに，各ブロックに隙間なく詰め込むより，隙間が残るようにパラメータを選択した方が時間効率・空間効率ともに良い性能を示します．
キーの差し替え
grn_pat, grn_hash に対して grn_dat の特徴的なところは，ID を変更せずにキーのみを差し替える機能を持っていることです．実装については，新しいキーを登録して古いキーを無効にするだけです．ただし，すぐに ID を再利用するため，トライの葉に ID を持たせる構成では，古いキーを参照しようとして到達した葉から新しいキーにアクセスしてしまう可能性があります．そして，クエリとキーの後半部分のみで照合していると，存在しないはずのキーが見つかるという問題につながります．
キーの差し替えによって生じる問題の単純な解決方法は，クエリとキーの前半部分も照合の対象に含めることです．しかし，トライの利点である Common prefix search や Predictive search の効率が大幅に悪化してしまいます．
そこで，grn_dat では，葉にキーの格納位置を持たせ，キーのプールに ID を格納するようにしています．これにより，キーの差し替えによって別のキーにアクセスしてしまう問題は解決されます．また，ID からキーの格納位置に変換する必要がなくなるため，参照の時間効率は少しだけ向上します．
ラベルによる連結
トライの代表的な機能の一つが Predictive search です．しかし，長子と次の兄弟へのポインタを各ノードが持つようなトライと比べると，ダブル配列は Predictive search を苦手とします．理由は，ラベルの種類数を m とするとき，子ノードの列挙にかかる時間計算量が O (m) になるからです．長子と次の兄弟へのポインタを各ノードが持っていれば，時間計算量は子ノードの数によって抑えられます．トライの根から Predictive search を実行するとき，葉では子ノードを列挙しなくてもよいという例外を無視して考えると，すべてのノードにおいて子ノードを列挙することになるため，ダブル配列の時間計算量は m 倍ということになります．
そこで，grn_dat では，長子と次の兄弟へのポインタに代わる存在として，長子と次の兄弟のラベルを各ノードに持たせるようにしています．たとえば，ノード S について，長子のラベルを FIRST_CHILD[S]，次の兄弟のラベルを NEXT_SIBLING[S] とすると，長子ノード X と次の兄弟ノード Y は以下のように求められます．
X = BASE[S] ⊕ FIRST_CHILD[S]; // ⊕ は排他的論理和（XOR）の意味で用いています．
Y = S ⊕ LABEL[S] ⊕ NEXT_SIBLING[S];
ポインタやノード番号を持たせるよりはラベルの方がコンパクトで済み，効率的な Predictive search を実現できるようになります．また，CHECK をラベルに変更したことで余った領域の使い道としての意味もあります．
領域の拡張
ノードの再利用を禁止している grn_dat では，徐々に拡張していくという方式を採用すると，古い情報が蓄積して空間効率がとても悪くなってしまいます．そこで，領域が不足すると一気に拡張するという方式を採用しました．具体的には，新しく大きな領域を確保して，必要な情報のみを移行するようにしています．また，プールに格納されているキーを辞書順に整列することで，Common prefix search や Predictive search の効率化を図っています．
おわりに
すぐに終わると思って書き始めたドキュメントなのですが，途中で力尽きるくらい長いものになってしまいました．しかも，ダブル配列の実装をしたことのない人にとっては意味不明な内容になっています．「はじめに」を書いていたときは，そんなつもりはなかったのですが…．そもそも，本格的なテストの前に API の仕様をきっちりドキュメントにしておこうという動機だったはずなのに，何がどうなって実装方法のドキュメントになったのでしょうか．謎です．
