FreyaSX開発メモ(5) -- 18 July, 2004, Yutaka Sato

FreyaSXの使い方 (プロキシのキャッシュ検索)

(梅雨も明けて連休の中日なんですが、暑いので定常状態です) 2004年7月7日はお日柄も良くなかったのですが(赤口)、FreyaSX もだいぶ落ち着いて 来たような気がしたので、七夕だし、その時点の版をとりあえず FreyaSX-0.95 として固定しました。ところがその後、これにDeleGateのキャッシュデータを 食わせたところ、色んな問題が見つかり、修正して 0.96 としました(16日/先負)。 ところが、固定前にちょこっといじったのが災いしてバグが入り、実質一行だけ 修正した版を0.96.1 としました(17日/赤口)(ftp://ftp.delegate.org/pub/freyasx/)

これまではもっぱらDeleGateメーリングリストの検索という特定用途に、FreyaSX を使って来たのですが、今回キャッシュに含まれる種々雑多なデータでテスト しながら修正しましたので、一般の使用にかなり耐えるものになった(かな?)と 思います。この際に、プロキシサーバDeleGateの キャッシュを検索する最近アクセスしたものの順に表示 する、という利用例を用いて、FreyaSX の使い方を 説明してみたいと思います。

FreyaSXの使い方概要

具体例の前に、Freya (SX) の使い方の概要を示しますと、以下のような手順に なります。

1) は通常、find コマンドを使用して作成します。ファイル名を一行に一つづつ 列挙したテキストファイルを作ります。

2) のために、FreyaSX では any2fdif というコマンドを作りました。 ここでは、1)でリストされた各文書に対して、3)で索引ファイルを生成する ために用いられる元データ(.fdif)と、4)で検索結果を表示する際に用いる 要約情報(.dsc)が作られます。検索対象の元データはテキストの形式や 文字コードが様々ですが、それらをXML風の共通形式、共通の文字コード(EUC) のテキストに変換したものが .fdif です。 .dsc は、各文書の日付、著者、題目や要約等を固定長のレコードとして格納 するファイルです。 オリジナルFreyaではこのために、元データの形式に応じてhtml2fdif, mail2fdif, text2fdif という3種類のPerlスクリプトが用意されていますが、Perlで実行 すると実行性能に難があり、インストール時にデフォルトでは無いモジュール が必要だったりしました。それで、FreyaSX では C で any2fdif を書いた わけですが、生成するデータは互換ですので、オリジナルFreyaの *2fdif を 使うこともできます。(オリジナルFreyaで作成した.fdifや.dscを使えます)

3) を行うのが findex というコマンドです。findex は 2) で作成した .fdif ファイルから索引ファイル (.idx, .lex, .map) を作ります。 findex に対して FreyaSXでは性能向上のためにに幾つかの変更を行いました が、今のところ機能面・仕様上の変更はありません。

4) を行うのが fsearch というコマンド、あるいは fsearch.cgi というCGI プログラムです。これらは、3) で作成した索引ファイルを用いて検索を行い、 ヒットした文書の識別番号のリストを作ります。そして識別番号に対応する 文書の情報を、3) で作成した.dscから取り出して、表示用のテキストを生成 します。オリジナルFreyaでは、検索語との適合度によるソートの一本槍で したが、FreyaSXでは、文書の日付等でもソートできるように拡張しました。 その後0.96では、ファイルのアクセス日付やらアクセス頻度やら、任意の数値 を元にソートできるような仕組みを実験的に拡張しています。

2)〜4)を通して、オリジナルFreyaでは索引ファイル(群)を何処に作り、また 何処で探すかは、ファイル名が示す通りのところになっています。つまり、 索引名だけを示した場合にはカレントディレクトリにあることになります。 これはこれでさわやかな仕様なのですが、何処で作業を行うかによらず、索引 ファイルは所定の場所に置きたい、という場合に、ちょっと不便です。 (まあちょっとしたスクリプトでも書いて、所定の場所を参照するよう引数を 加工すれば良いとも言えますが) この際なので、利用者によって、FreyaSXの置き場所が「FSXHOME」という 環境変数で示されれば、そこを索引ファイルやらライブラリファイルやらの デフォルトの置き場所として認識するようにしました。(この変更が0.96の リリース直前だったのでバグを入れてしまい、0.96.1で直したのでした)

まずはインストール

それで、まずはインストールですが、FreyaSX のインストールの手順は、 "INSTALL-ja" に記した通りです。 (ftp://ftp.delegate.org/pub/freyasx/INSTALL-ja) 基本的には、伸長・展開して make する、ということだけです。 取り寄せる必要があるのは FreyaSX と DeleGate の配布ファイル、あとは C++ を含んだふつうの Unix 環境があればOKです。

説明上、ホームディレクトリ直下で作成してそのまま使うように書いていますが、 実際にはどこで作成してどこに移動しても構いません。 インストールした FreyaSX のルートディレクトリがどこにあるのかを、 $HOME/freyasx という(シンボリック)リンクで指し示して置くと、利用時に 環境変数 FSXHOME の定義をしなくても良いというメリットがありますが、 大したメリットでも無いですかね。(FSXHOME環境変数を導入する前には このシンボリックリンクが有用でしたが)

FreyaSX で独自に開発された any2fdif は、DeleGateの機能の一部を利用して 実装されていて、その結合度は今後さらに高くなる(標準のDeleGateの一部に なるかも)と思いますので、DeleGateをベースに make するようになっています。 any2fdif では、元の文書が Unicode だった場合に、それを JISコードに変換 するためのテーブルを必要としますので、これもインストールします。 このテーブルとしては、昔から Unicodeコンソーシアムが配布しているもの (JIS0208.TXT)を使っているのですが、これが再配布禁止なので、インストール 時にダウンロードするようにしていて、その部分がちょっとウザイです。 確か最近は再配布可のテーブルもあったように思いますので、いずれそっちを 使うように作り変えて、FreyaSXと一緒に配布したほうが良いかも知れません。

利用の前準備

「FSXHOME」という環境変数で、インストールされた FreyaSX のありかを指し 示します。あわせて、PATH 環境変数に、FreyaSXの各コマンドの在処である $FSXHOME/binを含めて下さい。

索引の作成と検索

ということで準備が整いまして、本題のDeleGateのキャッシュの索引化です。 以下ではDeleGateのキャッシュディレクトリ名を /path/of/cahce/ とします。 (実際には例えば /var/sppol/delegate/cache/ とか、色々です) そこには、HTTPサーバからの応答データが http というディレクトリの下に 蓄えられているはずです。これを「cache」という索引名で検索できるように することにします。その手順は以下のようになります。

1) の find で、索引に取り込むべきファイルのリストを作成します。 さすがにフラットファイルだけをリストするように (-type f)していますが、ファイル名(拡張子など)によるフィルタリングはして いません。ファイル名でフィルタする機能は次段のany2fdifに組み込まれています。 (そもそもHTTP経由でアクセスされるデータの場合、URLからはデータ型は判別 できず、HTTP 応答の Content-Typeで判別しなければなりません。"/" で終る URL とか ".cgi" で終るものとかが典型的ですが、厳密に言えば ".gif" と あってもHTTPかも知れません)

2) の any2fdif で、cache という名前の索引 (-b cache) の作成を開始します。 これにより、索引ファイル群が $FSXHOME/bank/cache/ の下に、cache.{fdif,dsc} 等として作られます。 -f clist で、1) で作られたリストファイルを指定しています。 このリストは /path/of/cache/http/www... というようなファイル名の並びですが、 これを元の URL にする場合には先頭の /path/of/cahce/ の部分は不要ですので、-s /path/of/cache/ として削除します。 (元のURLは現在のところ、検索結果の表示と、結果HTML中へのアンカーの埋め 込みにだけ用いられます) (読み込んだファイルがHTTP応答のキャッシュであるかどうかは自動判別して いるので、そのように判別したら -s /path/of/cache/ を暗黙で行うように しても良いかもしれません) (DeleGateのキャッシュファイル名は基本的にURLそのままですが、幾つかの 特殊文字は %XX にエスケープしていますので、any2fdif ではその対処も 行います)

3) の findex による索引作成では、-b cache という指定に従い、cache という 名前の索引の 検索用ファイル群が作成されます。具体的には、$FSXHOME/bank/cache/cache.fdif を入力して、$FSXHOME/bank/cache/cache.{idx,lex,map} を出力します。

4) の検索では、cache という名前の索引、つまり $FSXHOME/bank/cache から、 "delegate" という語を含む文書を検索しています。 検索のキーとして "http" を指定すると、索引化されている全ての文書が ヒットします。 ここではオプション名がオリジナルFreya のまま -i になっていますが、FreyaSX 的に解釈されているものなので、これも -b にしたほうが良いですね。次の版ではそうしようかと思います。ただ、 fsearch のつもりで間違って findex と打っちゃったりすると、索引ファイル 作り直しになっちゃったりするので。。。実際には fsearch はテスト用くらい にしか使わないと思いますので、このママで良いかも。

CGIからの検索は以下のように手動でテストすることができます。

実際にHTTPサーバ経由で検索するには、

のようにします。5a) はWebサーバの種別によって別途設定が必要かも知れません。

処理時間と改善案

ちなみに、私が個人的に使っているDeleGateのキャッシュには、昨年の夏の終り に立ち上げてから約一年間のキャッシュデータが残っていまして、ファイル数と しては49,500個ほどあります。そのうち、現状の any2fdif が取り込むテキスト ファイル(HTMLまたはプレイン)は5,850個ほどで、全体の 11% ほどです。大半 は(おそらくインラインの)画像ファイルで、GIFが56%、JPGが16%、swfが5%、と いった具合です。SWF(フラッシュ)にもわずかにテキストが含まれていて、 DeleGate でも MOUNT の対象にしているので、いずれ索引に取り込むかも知れま せん(となると索引対象がイッキに約5割増しになるかも:p)。PDF は私のキャッ シュ中では全体の0.2%ほどでした(これらの統計は any2fdif の実行の最後に 出力されます)。

索引の作成1)〜3)にかかったそれぞれの時間は以下のような感じです。(time コマンドで測定、iMac: MacOS X 10.3.4 + 1GHz Power PC G4 + 512MBメモリ + 内蔵80GBディスク、つまりイマドキのごく普通かそれ以下の環境を使用)

(気がつくと iTunes で音楽聞きながら測ってたので、いつもより数パーセント 実行の実時間が長くなっているようですが、まあいずれにしろ目安としては こんな感じです)

大雑把に言って、10分間(600秒)に6,000件の処理ですので、一秒あたり10件程度 の処理ということになります。これはメモ(2)で標榜した一秒あたり100件の処理 から大幅に後退しています。メモ(2)の時点での対象は基本的にDeleGateの メーリングリストというもので、形式的に等質でファイルアクセス的にもなめらか な感じだったのに対して、今回の対象がキャッシュのような乱雑なデータである (語彙も多く、ディレクトリも複雑)ことが主な要因と思います。

前処理である1)と2)の部分はディスクアクセスの待ち時間が大半なので、 パイプラインにしたら多少は待ち時間が減るかと、find | any2fdif -f - の ように結んでみますと、

という具合で、たまたま多少は改善するみたいですが、まわりの状況によっては 悪化することもあると思います。いずれにしても、ゼロから作る場合の性能を 劇的に向上するのは難しいと思われるので、変更分だけの更新をする方向で 改善するのが実際的な解決法ではないか思います。例えば実際に、一旦2)で 作成した索引化されたファイルのリスト(後述の.sum)に従って、そのファイルの 日付だけを収集するのに要する時間は15秒程度なので、6000/15 = 400 という ことになり、更新されたファイルの索引だけを作り直す、あるいは作り足す ようにした場合、100件/秒という目標みたいなもの?は達成できそうです (なんか 違う気もしますが)。

プロキシサーバのキャッシュの場合、新しいファイルの追加や既存のファイルの 更新をプロキシが認識していますので、何が追加されたり変更されたりしたかを、 プロキシ自身が記録するようにすれば良さそうです。 あるいはアクセスログファイルを使ってそれを検出するということも、イケそう です。いやしかし、アクセスログはローテートされてしまうのが普通だし、 元データの更新日付のような情報も普通含まれないので、やはり別途専用の ファイルを作ったほうがすっきりしそうです。 (DeleGate ではキャッシュの容量制限とか、メタ情報の交換のために、そのような ものを作ろうと考えたこともあるのですが、実際の必要性があまりなくて 実現しませんでした)

なお、any2fdif では、最初全てのファイルを、ファイル名によらず実際に読ん でみて、Content-Type: text なら処理するということをやっていましたが、 これだと時間がかかったので、結局URL中の拡張子とおぼしき部分 (例えば末尾 が .gif とか)から、明らかにテキストではなさそうと思われるものは除外する ことにしました。-a というオプションで、ファイル名によるスクリーニングを やめることができますので、これをつけて測定してみますと

となりました。つまり スクリーニングしないで全部中身を確認すると処理時間 が2倍以上かかります。実際にオープンしてみるファイルの数は10倍近くになる わけですが、ヘッダ部分を読むだけですので、所要時間の増加としてはその程度 ということですね。 一方、テキストではなさそうだとスクリーニングで無視されたファイルで、実際 にはテキストだったというのはありませんでした。

また、findex はほぼ CPU バウンドになっています。DeleGateのメーリング リストに対して利用した経験から、経験的に(^^)元データが日本語コードの場合、 ASCIIだけの場合に較べて処理速度がぐっと低下することがわかっているので、 そのあたりには結構性能の改善の余地があるのではないかと勘ぐっています。

FreyaSXの置き場所について

最初しばらくオリジナルのFreyaを使ってみてふつふつ感じたのは次のようなことです。

2) については、FreyaSX で増分索引機能 (index+N.*) を導入したため、より 深刻:pになりました。さらに今後、索引の更新や外部情報によるソートなどを 導入する際にファイルが増えていくはずです。そんなわけで、 ということにしました。具体的には、オリジナルFreyaでは、あるindexを作成 したり検索したりする際に必要なファイルは以下のようでした。 このうち icot.dic (辞書) にだけはデフォルトの場所というのがあって、 コンパイル時に指定することになっていました。 DeleGateではこれらに加えて、拡張されたファイルを含め、以下のようなディレ クトリ構成の下に、実行時に使用するファイルが集められていると想定することに しました。 実際には、0.95 では、これらのファイルのデフォルトのの置場を、$HOME/freyasx とすることにしていたのですが、0.96 で FSXHOME という環境変数で指定できる ようにし、そのデフォルト値を FSXHOME=${HOME}/freyasx と考えることにしました。

fsearch.cgi からの検索では、FSXHOME環境変数を設定しなくても済むように (fsearch.cgiにひと皮かぶせずに済むように)、自分の実行位置(実行ファイルが 存在する位置)から相対的に索引ファイルを探すようになっています。例えば、
.../cgi-bin/fsearch/fserach.cgi
というCGIプログラムは、
.../cgi-bin/fsearch/
というディレクトリで実行していると想定されます。ここから "index" を検索 する場合には、一つ上のディレクトリの下に索引置場の "bank" があるものとして、
.../cgi-bin/fsearch/../bank/index/index.* つまり、
.../bank/index/index.*
というファイルを探します。従って、FreyaSX が上記のように構成されていれば、 例えば Web サーバのデータのディレクトリ ($WWW とします)から、
$WWW/cgi-bin/fsearch -> $FSXHOME/cgi-bin
というシンボリックリンクを張り、/cgi-bin/fsearch/fsearch.cgi という URLパスでこのCGIプログラムにアクセスすれば良いことになります。 (dict/icot.dic は etc/icot.dic で良いかも知れません。fsearch.cgi は、 自分のパス名から相対的に使用ファイルを探せるようにすべきかも。 any2fdif は JIS0208.TXT を探すためにそのようなことをやっているので、 これを FreyaSX 全般に適用すべきかも)

今後当面の検討課題について

DeleGate自体にもキャッシュのエクスパイア用に find のサブセットのような 関数があるので、いずれこれを any2fdif で使って、リストを作るフェーズと それを処理するフェーズを一体にできるようにすることも考えられます。これ だとディレクトリを2回なめることがなくなるという利点はあります。ただ、 一旦作成したリストについて、以降の処理を繰り返し行うという使い方もある ので、いずれにしても、予め作られたリストから索引を作成する機能は必要と 思います。リストと索引作成をパイプラインにする効果も多少はあるようですし。

any2fdif まわりでは、まだ仕様が固まっていませんが、いくつかの拡張機能 を試作しています。 キャッシュを検索する場合、ファイルのアクセス日付が変わってしまうと困る ことがあります。特にDeleGateではファイルのアクセス日付をそのまま、 キャッシュへの最終アクセス時刻として用い、エクスパイアの判断に用いて いるからです。それで any2fdif では、ファイルを読み出した後に、アクセス 日付を、読み出し前の値に復元するようにしてみました。もっとも、このような 使い方がなにか問題を起こす(ctimeが更新されますし)可能性がなくもありません。 そもそも tar なんかでバックアップするために読み出したらアクセス日付が 変わっちゃうわけですし、これは諦めたほうがよいのかも? と思ったら、きょうびのtarには --atime-preserve なんていうオプションが あって、これと同じ働きをするようです。マニュアルには「これによって ctimeが更新されることに注意!」とあります。まあそういうことですね。 どっちを保持したいかというと、少なくともキャッシュの場合にはatimeに一票。 (しかし最終的にはファイルシステムに依存しないで、アクセス時刻を管理 するようにプロキシを作るのがまっとうな道のようだとは思いますが)

ともあれ、ファイルのアクセス時刻が保持されることを前提にしまして、 FreyaSX-0.96 ではアクセス日付による検索結果のソートというのを実装して みました。any2fdif は、index.{fdif,dsc} を作る時に、同時に index{.sum,+atime.srt} というファイルを作ります。前者には、索引に 取り込まれた文書ファイルのCRC値やパス名がテキストファイル形式で記録され、 後者には各文書ファイルのアクセス日付が(4バイトの整数値として)書き込まれ ます。このアクセス日付のリストである index+atime.srt は findex -b index -u -f - というコマンドで、高速に更新することができます。 この更新は、index.sum に列挙されたパス名に従って行います。

このアクセス時刻の値をどのように使えるかですが、これは fsearch.cgi で検索を 行う際に

とパラメタを指定することで、検索結果を、最近アクセスされた順にソートするのに 使えます。一般に、index=xxx&sort=yyy と指定すると、xxx という索引の 検索結果を、index-yyy.srt というファイルに格納された値でソートできる、 というようにしています。 (ソートのキーの値を検索結果の中で参照できるようにするのも良いですね。 ${sort.atime} みたいな。 整数値として表示するか、日付として表示するか、などのフォーマットの 指定もあればモアベター)

ソートのキーとして使って面白そうなものとしては、まず、対象文書への アクセス数(Webサーバやプロキシで集計)、過去の検索ヒット数(FreyaSXで集計)、 投票による票数(投票のインターフェイスをfsearch.cgiに導入する)などです。 これらの値を集計したり更新する方法は他にも色々考えられますが、それらは 基本的にFreyaSXの外で実現できることで、それに基づいてソートするFreyaSX のメカニズムはこの簡単なもので足りるでしょう。ただ、4バイトの整数値に 限るのはどうかとも思うので、ソートのキーファイルの先頭に、値の型を示す タグくらいは入れる必要があるかも知れません。

Freya(SX)本体の検討課題としては、他の検索エンジンがやっているように 検索にヒットした文書の文脈をダイジェストとして表示することが望まれますが、 そのためには .fdif に相当するデータを検索時にも持っている必要があります (現在は検索時には.dscだけを使用していますが)。 ただしそれはベタテキストではなく、findexで抽出したlexiconの列などとして 圧縮したほうが良さそうです。それは現行の版の表示情報である .dsc の圧縮に ついても言えるので、findex で .dsc の圧縮版を作るというようにするのが 良いのではないかと思います。表示用のダイジェストをどのようなものに するかは、前処理の段階で選択できることも必要だと思いますから、.dsc の、 ちょっと長めの原型を .fdif の中に「<DIGEST>ダイジェスト</DIGEST>」みたい にして渡せば良いのではないかと思います。.fdifを作るところからfindexを 飛び越えてfsearchに直接渡っているデータがあるのは(実用的な実装としては よく理解できますが)ちょっと気になってもいたので、一石二鳥です。

findex や fsearch (の用いる .lex) については、この際 Unicodeベースに してしまうというのも、ある種壮快かも知れません。

あとは、検索エンジンといえばロボット、といことになりますが、技術的には DeleGate の中に Web を漁るためのロボットの部品はほとんど揃っているので、 とりあえず作ること自体は簡単です。ただ、悪さをしないように、慎重に 作らなければならないと思います。

おわりに

時節柄、土用って何?丑の日って何よ?という疑問をこの際解決しておこうと 思ってちょっとGoogleでチキチキしてみたら、永年(ずいぶん長かった)の 疑問が簡単に解けました。土用からついでに、陰陽五行、七曜、そして六曜 ・陰暦とずるずる来て、ああ今年の7月7日は赤口でイマイチだったかもと 思ったわけです。今度からはリリースの際にお日柄を気にしてみるかも:p それはそうと、やっぱ検索エンジンて便利ですね(コンテンツ次第で)。

今日18日は先勝だし朝から松井にはホームランを期待する。。。が第一打席は 惜しいレフトフライ。あれ、こっちでは18日午前だけど現地では17日の午後か...


Yutaka Sato