全文検索エンジンを利用した ファイルシステムの名前空間拡張 電気通信大学 大学院 情報システム学研究科 多田研究室 滝田 裕 ・ 多田 好克 発表の流れ 研究の動機 関連研究 設計 実装 評価 今後の課題・まとめ 研究の動機 近年のストレージ事情 ディスク容量とファイル数の増大 この10年のディスク容量の増加率は60～70%/年 MicrosoftのWinFS関連文章では70%/年 Impress AKIBA PC Hotline!によると60%/年 発売週 1998/05/30 2005/06/18 型番 IBM DTTA-351680 Hitachi HDS725050 容量 16.8GBytes 500GBytes 価格 99,800 35,580 ファイル数も35年前は約10,000個→現在はその数十～数百倍 ファイルの名前管理 ディレクトリによる階層化 木構造をもつ UNIXでは35年前から変わらない すでにファイルを管理できなくなっている ファイルの検索 内容からファイルを特定 find + grep その場ですぐ検索できる 低速で検索結果が利用しにくい 全文検索エンジン 高速、高機能 インデックスの準備、要ブラウザ より使いやすい検索が必要 検索とファイルシステムの統合 ファイル名を使ったファイル検 索 ディレクトリ名が検索キーワード 動的にディレクトリ生成 全文検索エンジンで検索 検索結果はシンボリックリンクで 表現 既存の木構造の名前空間と 検索による仮想的な名前空間 を共存 書き込み時の検索インデック ス自動更新 関連研究 Semantic file system ディレクトリ名による検索 NFSサーバとして実装 検索したい属性とキーワードを 別ディレクトリで指定 (A-Vペア) A-Vペアは動的に生成される仮 想ディレクトリ 既存のファイルツリーの一部と してマウント Crawlerによるインデックス 更新 HAC (Hierarchy and Content) Semantic directoryによる検索 属性に検索クエリーを持つ特殊なディレクトリを利用 ディレクトリ自体は既存のディレクトリとして存在 ファイルの追加、削除で検索インデックスの変更可能 DLLで実装され、使用前にプリロード WinFS Microsoftの次世代Windows 用ファイルシステム バックエンドにSQLサーバを 使用 SQLサーバで属性を管理 SQLベースの検索 既存の木構造ディレクトリと 独立 設計 ファイルの内容に基づく名前空間 ディレクトリで検索キーワードを指定 プレフィックスで検索キーワードディレクトリを判別 “.../:keyword=word/...” :keyword= word プレフィックス 検索キーワード 検索キーワードディレクトリは動的に生成 アクセスするまで存在しない 書き込み権限がないディレクトリでも生成可能 プレフィックスの種類 プレフィックス :keyword= 検索 完全一致 value :prefix= 前方一致 value* :inside= 中間一致 *value* :suffix= 後方一致 *value :regex= 正規表現 /value/ :subject= フィールド指定 +subject:value :from= フィールド指定 +from:value :message-id= フィールド指定 +message-id:value Namazu検索式 複数キーワード検索 検索キーワードディレクトリの連接はAND検索 “.../:keyword=A/:keyword=B/” A and B 逆ポーランド記法により複雑な検索式を表現 演算子ディレクトリ:and, :or, :notの導入 “.../:keyword=A/:keyword=B/:and/” “.../:keyword=A/:keyword=B/:or/” “.../:keyword=A/:keyword=B/:not/” Namazuの演算子notは二項演算子 A and B A or B A not B 検索結果の表現 検索結果はシンボリックリンクで表現 シンボリックリンクの命名法 “nnn:filename” nnn filename 検索適合順位 元のファイル名 検索適合順位を入れることで名前の衝突を回避 ファイルの絞り込みと結果の制限 ファイルパスによる絞り込み アクセス権限による絞り込み 検索キーワードディレクトリの前にある通常のディレク トリを検索範囲の限定に使用 検索しているユーザがアクセスできないファイルは検 索結果から除く 検索結果の制限 検索結果のうち上位50件のみ表示 以降は:whence=, :max=, :allを用いて表示 実装 システム構成 NetBSD 1.6.2上で実装、全文検索エンジンとしてNamazuを利用 search filesystem ディレクトリ名を使った検索機能を提供 indexing filesystem 書き込みに伴い、ボリュームごとに用意した検索インデックスを更新 search filesystem マウント時にデーモンプロセス生成 検索プログラムの起動を担当 検索キーワードディレクトリへのアクセスをフック(vノードスタック) デーモンプロセスとの通信はソケットを利用 ディレクトリエントリの生成&既存ディレクトリとの合成 search filesystemのファイル操作処理 既存ファイルへのアクセスは下層fsへ 検索キーワードディレクトリのアクセスのみ処理 lookup プレフィックスの検出、vノード生成 readdir 検索プログラムの起動、検索結果の合成 readlink取得済みの検索結果を出力 getattr 適当なファイル情報を出力 仮想ディレクトリの扱い 親ディレクトリへのエントリ追加 親ディレクトリをキー、仮想ディレクトリ名を値とした ハッシュ表(仮想ディレクトリエントリ)を使ってエントリ 合成 ディレクトリの所有権を無視 仮想ディレクトリは勝手に消滅 vノードが再利用される際に仮想ディレクトリエントリを 消去 rmdirによる手動消去も可能 indexing filesystem マウント時にデーモンプロセス生成 mknmzによる検索インデックスの更新 差分更新可能な修正版mknmzを使用 書き込みフック(vノードスタック) 検索インデックスは各ボリュームのrootに配置 評価・考察 評価について ソースコード量、オーバーヘッド、検索時間で評 価 評価環境 Pentium4 1.7GHz, 512MB memory, 20GB HDD NetBSD 1.6.2, Namazu 2.0.14 対象 /usrに含まれるファイル(187,397個)の内10,579個 ソースコード量 ファイルシステム search indexing overlay overlay+layerfs portal portal+genfs カーネル デーモン 3959 1365 2478 791 599 2517 1186 1915 2928 1915 portal+genfsと変わらない程度のソースコード量 機能削減分、デーモンは縮小 ファイルシステム化オーバーヘッド ディレクトリ /usr/shar/man/man7 /usr/shar/man/man1 /usr/shar/man/man9 /usr/shar/man/man3 N 31 483 694 1900 ufs 0.28 1.15 1.48 3.01 +index 0.29 1.21 1.55 3.47 +search 0.32 1.69 1.98 5.15 通常ディレクトリの参照で比較 エントリ数にほぼ比例する形でオーバーヘッド増大 indexing fs+search fsの場合、エントリ数1,900で参照 時間はufsの1.7倍 検索時間 ディレクトリ /usr/:keyword=purple /usr/:keyword=bold /usr/:keyword=track /usr/:keyword=root /usr/:keyword=list N 6 102 336 980 検索 0.84 3.00 8.26 22.43 参照 1.26 4.30 12.02 43.27 3053 68.68 222.75 Namazu検索にかかる時間は件数に比例 件数が少ない場合、参照時間は検索時間の1.5倍程度 :all参照時間はおよそ件数の二乗に比例 表示件数制限により性能改善 :all 1.27 5.06 20.71 203.92 16604.00 今後の課題 複数のファイル名を持つファイルの内容更新 多言語対応 現状では最後にアクセスした名前しかわからない Namazuを日本語用として設定 ユーザのlocale情報取得で対処可能? より高度な検索への対応 全文検索以外の検索にも利用可能? まとめ ファイル内容に基づく名前空間を提案した NetBSD+Namazuで実装 既存ディレクトリと共存 search fs: 検索機能の提供 indexing fs: 検索インデックスの更新 既存アプリケーションに検索機能を提供 考察 類似機能であるデスクトップ検索と比較 デスクトップ検索(googleデスクトップなど) 完全にユーザ空間で動いている 対応アプリケーションしか利用できない 本システム すべてのアプリケーションで利用可能 検索時間の隠蔽ができない アプリ側のファイルオープンをマルチスレッド化 件数の二乗に比例する理由 vノードの管理 portal fsのコードを流用してハッシュで管理 ハッシュのキーは下層fsのvノードポインタの値 search fsの作る仮想ディレクトリは下層fsがない 実は単方向リストで仮想ディレクトリの管理を行っていた 仮想ディレクトリアクセス時にvノードの存在確認が行わ れる 初めてアクセスした場合、リストを全て検索 参照にかかる時間は (仮想ディレクトリの数)×(リストの長さ) ≒(件数)^2
© Copyright 2024 ExpyDoc
