前回は、FINDSPOTの転置インデックスの構造について説明しました、今回はこの構造に至った経緯などについて解説します。

ブロックの拡張問題

前回、転置インデックスのブロックは次のような構造になっていることを説明しました。

このブロックには、ブロックサイズがいっぱいになるまで（空きレコートが存在する間）は、データを詰め込むことができますが、ブロックが溢れてしまって、これ以上データが格納できない場合にどうするかという課題があります。

転置インデックスの作成当初は対象とする文書数が少ないので、転置インデックスに登録するデータ量は少ないのですが、だんだん登録する文書数が増えていくと、転置インデックスに登録しなければならないデータ量も大きくなっていきます。必然的に、特定のN-gramに関する転置インデックスのレコードが溢れることになり、この時にどのように対処すべきかという問題が発生するのです。

FINDSPOTの初期の実装

FINDSPOTの初期の実装では、ブロックが溢れたら、続きのデータを格納するために新たに別のブロックを作成する方式を採っていました。この時、続きのデータ用のブロック位置に関する情報は、ブロックの第2番目のレコードに格納していました。

最初に作成するブロックは16レコード分です。この時、ブロックサイズ、見だし語、次のブロック位置のために3レコードを消費するので、都合13レコード分がデータ用に利用できます。このブロックには13個分のデータを書き込めますが、次に14個目のデータを同じN-gramに関して書き込む必要が生じたら、新たなブロックを作成して、14個目のデータを書き込むという寸法です。新たなブロックの転置インデックス内の位置は、元のブロックの第2レコードに書き込むことで、検索の際には、このチェーンを辿って次のブロックを参照できます。

また、ブロックのサイズに関しては、最初は16レコード分のブロックサイズ（128バイト）とし、続きのデータ用のブロックは5個ごとにサイズを倍に拡張するというアルゴリズムを使用していました。次の表は、このブロック拡張によって、トータルで何個のデータが格納できるかを示したものです。

この表によると、1000個のデータを格納するには19個のブロック、1万個のデータを格納するには35個のブロック、10万個のデータを格納するには53個のブロックが必要になることがわかります（表中色のついた箇所⁠）⁠。

このブロック数を拡張する方法は、使用されていない空きレコードが少ない（最大でも最後に作成したブロックの空きレコード分）ことや、データを追記する際の処理が軽くて済むというメリットがあります。実際に使用してみたところ、転置インデックスの作成スピードは十分でしたが、検索性能に関してはもうひとつ満足のいくものではありませんでした。

ハードディスクのスピード

実はブロック数を拡張する方法の検索性能が思わしくない大きな理由は、記憶媒体がハードディスクである点です。ハードディスクには物理的な特徴があり、これがディスクの読み書きの性能を大きく左右します。

ハードディスクはレコードのようなディスクと呼ばれる円盤が回転する構造になっており、円盤上の磁気情報を読み書きするためにレコードのアームのように磁気ヘッドが動く構造になっています。レコードは1本の溝が蚊取り線香のように渦状になっていますが、ハードディスクは年輪のように磁気情報が輪を描いている点が異なります。この磁気情報の輪のことをトラックと呼びます。

ハードディスクの読み書きスピードは、磁気ヘッドが目的のトラックに移動するまで位置決めの時間、ディスクの回転待ち時間と、実際のデータを読み書きする時間の3つが主たる要素です。

位置決め時間（シークタイム）

ハードディスクの磁気ヘッドはアームの先に取り付けられています。この磁気ヘッドが目的のトラックに移動してからでないと、トラック上の情報を読み書きできません。磁気ヘッドの移動に要する時間が、位置決め時間になります。位置決め時間はハードディスクによってさまざまですが、近年のドライブならば8～12ミリ秒位が一般的です。サーバ用の高速なものになると4ミリ秒程度のドライブも存在します。

回転待ち時間

ハードディスクの回転スピードは一般のPC用だと7200～5400rpm、サーバ用では10000～7200rpm位になります。サーバ用の特別に速いものでは15000rpmという回転スピードのものがあります。車のタコメータでもおなじみのrpmという単位はRevolutions Par Minuteの意味で、1分間あたりのディスクの回転数を表します。

7200rpmの回転数は1分間に7200回転という意味になり、1秒間に直すと120回に相当し、ヘルツで表記では120Hz（西日本の交流電源が60Hzなのでちょうど倍）となります。1回転に要する時間は8.33ミリ秒になります。

ハードディスク表面にある目的のデータのある場所は、ヘッドに対して回転しているのでいつでもすぐに読み書きできるわけではありません。読み書きのためにはヘッドのちょうど真下の位置に目的のデータのある場所がやってこなければなりません。平均すると、1回転に要する時間の半分でヘッドの真下にディスクの目的の位置がやってくることになるので、先の7200rpmのディスクの場合には平均回転待ち時間は4.16ミリ秒となります。

実際のデータを読み書きする時間

実際のディスクの読み書きの時間はデータ量が少なければ短く、データ量が多くなります。昔のドライブは1トラックあたりのセクタ数と、トラック数がハードディスクのスペックシートに公表されていて、実際の読み書きのおよその時間も計算できました。ところが、近年のドライブは外周のトラックはセクタが多く、内周のトラックはセクタが少ないゾーン記録方式になっている関係で、1トラックあたりのセクタ数と、トラック数が公表されなくなったことで、実際の読み書きのおよその時間は実測しないとわからなくなっています。

以上の3要素の内、時間の予測がつきやすい位置決めの時間、ディスクの回転待ち時間を元に、検索性能にどう関係しているかについて話しを進めます。位置決めの時間が8ミリ秒、ディスクの回転待ち時間4ミリ秒のドライブを使用すると合計で、12ミリ秒の時間が読み書きの直前に必要になることになります。

先ほどの、表3によると、1,000個のデータを格納するには19個のブロックが必要でしたが、1ブロックの読み出しの度に12ミリ秒かかるとすると、19個のブロックでは、228ミリ秒（0.228秒）かかることになります。1万個のデータの場合には35ブロックなので420ミリ秒（0.420秒⁠）⁠、10万個のデータでは53ブロックなので636ミリ秒（0.636秒）になります。つまり、複数個のブロックに分ける方式は、検索時にデータの読み出し前にかかる時間が大きく効いてしまうことになるのです。

現在のFINDSPOTの実装

特定のN-gramに関して、複数のブロックに分けて情報を保存するという方法は、検索時にデータの読み出し前にかかる時間が無視できないほど大きいということが初期実装での結論でした。そこで、複数のブロックに分けないで、常に1つのブロックでデータを記録するように、FINDSPOTの実装を大きく変更することにしました。

具体的には、ブロックに空きレコードが無くなり新たなデータを登録できなくなったら、追加のブロックを生成する代わりに、元ブロックの倍の大きさのブロックを作成します。そして、元ブロックに記録されているデータを、新しいブロックの前半部分にコピーし、残りの後半部分を新たな空きレコード領域として使用します。元ブロックは、中身を0クリアした後、次に同じサイズのブロックを生成する際に再利用します。

この1ブロック方式ならば、実データの読み出し前にかかる時間は常に1回分で、先の例ならば12ミリ秒程で済むことになります。実際の全文検索時の実行スピードが大幅に改善されたことは言うまでもありません。

一方で、ブロック内の空きレコードが無くなった時の処理は、ハードディスクの読み書きの回数やデータ量が初期の実装と比べると多くなっています。このため転置インデックス作成時間については悪化してしまいました。また、初期の実装と比べるとブロック中の空きレコードの割合が多いため転置インデックスのファイルサイズが大きくなったことも1つのデメリットと言えます。このデメリットと検索時間の大幅短縮のメリットを勘案して、メリットの方が重要であるとの観点から、現在は1ブロック方式を採用しています。

システムの導入時や、削除データが多くなった時には、転置インデックスの再作成を行うことがあります。このような場面では、転置インデックスの作成時間は非常に大きなファクターです。現在は、インデックス作成よりも検索時間を重視した実装になっていますが、転置インデックスの作成時間が次なる実装上のテーマだと考えています。

次回予告

今年の年末は集中して、FINDSPOTの磨き込みを行いたいと考えています。作業内容がトピックとしてご紹介できるものになるかは未確定ですが、次回連載は、磨き込み後を予定しています（請うご期待⁠）⁠。