検索エンジンを作る

第20回 転置インデックスの実装(その2)

この記事を読むのに必要な時間:およそ 3 分

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

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

ハードディスクはレコードのようなディスクと呼ばれる円盤が回転する構造になっており,円盤上の磁気情報を読み書きするためにレコードのアームのように磁気ヘッドが動く構造になっています。レコードは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の磨き込みを行いたいと考えています。作業内容がトピックとしてご紹介できるものになるかは未確定ですが,次回連載は,磨き込み後を予定しています(請うご期待⁠⁠。

著者プロフィール

工藤智行(くどうともゆき)

有限会社サイパック取締役社長。システム構築・管理のコンサルティング,ローカライゼーション,文書処理や障害者向けソフトウェアを中心とするプログラミングを長年手がける。 近著『UNIXプログラミングの道具箱』『システム管理現場の鉄則FreeBSD編』等

URLhttp://www.cypac.co.jp/

著書