分散コンピューティング環境上の Webリンク収集システムの実装 林研究室 ０５００１１ 伊藤 正敬
目次 研究の背景と動機 システム構成の概要 システム全体の処理フロー システムの評価実験 結果のまとめと考察
研究の背景と動機 システム構成の概要 システム全体の処理フロー システムの評価実験 結果のまとめと考察
WWWについて いかに有用な情報を探せるか？ WWWの特徴 Webページ検索の問題点と現状 大規模 ：１０億ページ以上 大規模 ：１０億ページ以上 変化が速い ：更新・削除などが頻繁 多様性 ：個人の日記から映像メディアまで存在 構造的 ：HTML記述やハイパーリンクによって構成 Webページ検索の問題点と現状 キーワード検索のみでは限界？ ハイパーリンク構造に注目したサービスが多くなってきた Google、Lycos、Yahoo！、Excite、BIGLOBEなど いかに有用な情報を探せるか？
システムの構築方法や問題点までは公開されていない Ｗｅｂページの収集方法 WWWソフトウェアロボット 開始点となるURLからリンクを辿り、Webページを収集 分散コンピューティング 時間のかかる処理を複数マシンで並列実行 情報収集システムの事例はあるが、 システムの構築方法や問題点までは公開されていない 構築方法や技術的な課題を明らかにしたい
研究の目的と方法 研究の目的 仕様、機能の定義 構成する諸技術 全体の処理フロー パフォーマンスの評価実験 Webリンク収集システムの構築 構築方法や技術的な問題点を明らかにする 仕様、機能の定義 構成する諸技術 全体の処理フロー パフォーマンスの評価実験 そこで、研究の目的として、 Webリンク収集システムの構築を行い、 今回の構築の試みからわかった構築方法や技術的な問題点を明らかにする そこで、具体的な方法として、 システムの仕様、機能を定め、 その仕様に基づいたシステムを構成する諸技術を決定し、 システム全体の処理の流れを定め、 構築したシステムのパフォーマンスを評価するために実験を行いました
研究の背景と動機 システム構成の概要 システム全体の処理フロー システムの評価実験 結果のまとめと考察
システムの仕様と機能 開発言語 分散システム データベース Webリンクの収集 分散環境の構築 リンクデータの処理 Webページを解析 並列処理可能 分散環境の構築 複数台PCによる負荷分散 リンクデータの処理 膨大なデータを格納できる 検索やデータの更新などが容易 メモリ管理の考慮 排他制御が必要 開発言語 分散システム データベース
開発言語の選択 分散システム に対応 HTML 処理が容易 並列処理 可能 メモリ管理 が容易 データベース 接続が容易 Java言語
分散システム技術 分散システム：RPC、Java RMI、CORBA、HORB 他技術との比較 比較した上での Ｊａｖａ用分散オブジェクト技術ＨＯＲＢを用いた 他技術との比較 比較した上での ＨＯＲＢのメリット RPC 関数の使い方などが容易 Ｊａｖａ ＲＭＩ 実行処理速度が2倍 非同期メソッドをサポート ＣＯＲＢＡ ＩＤＬ記述不要 非同期メソッドの記述が容易 ＣＯＲＢＡ ＩＩＯＰをサポート
データベースの選択 Javaとの接続が容易 排他制御が可能 容量制限が大きい PostgreSQL7.1.3
システム全体の処理フロー 研究の背景と動機 システム構成の概要 システム全体の処理フロー システムの評価実験 結果のまとめと考察
システムの全体像 Master PC DB Slave PC タスクURL数 と深さだけ収集 Web リンク 収集 HORBによる ハイパーリンク Slave PC Web リンク 収集 タスクURL数 と深さだけ収集 HORBによる 分散環境構築 DB リンクデータの格納 Master PC Slaveのタスク管理
並列処理の必要性 Slave PC １ Slave PC ２ 同時にデータが 送られてくるかも しれない Master PC DB
非同期メソッドとマルチスレッド 処理を同時並行的に進める 複数人で仕事を行う Slave タスク Master タスク Slave タスク
非同期メソッドとマルチスレッド Slave Master Hisyo Slave それぞれが 別スレッド 非同期 メソッド Slave
システムの評価実験 研究の背景と動機 システム構成の概要 システム全体の処理フロー システムの評価実験 結果のまとめと考察
実験の方法 実験１：時間量とSlave PC台数の変化 実験２：初期値設定の変化（60分間で計測） Slave PCの｛２、５、１０｝台 30分、60分、90分 タスクURL数３、リンクの深さ４ 実験２：初期値設定の変化（60分間で計測） タスクURL数の変化｛１、３、５｝ リンク収集の深さ｛２、４、６｝ 実験は各3回ずつ行った 「解析Webページ数」と「獲得リンク数」の平均値で評価 初期URLデータは日本の大学Web TOP Page100個 解析するドメイン対象をJPドメインに限定した
全実験データの結果 1ページあたり約１２リンク 約５％の割合でエラーページに遭遇 実験時間 ：63時間 解析ページ数 ：２０５１７７ページ 実験時間 ：63時間 解析ページ数 ：２０５１７７ページ 獲得リンク数 ：2494075 エラーページの接続回数：９７６７回 1ページあたり約１２リンク 約５％の割合でエラーページに遭遇
実験１：時間量の変化 解析したWebページ数 解析ページ数 時間量
実験１：時間量の変化（1台あたり） 台数が多い場合ほど 解析ページ数が減少している 2台 5台 10台
実験２：タスクURL数の変化（1台あたり） 10台 ２台 解析ページ数 どの台数でも 解析ページ数が上昇 5台 タスクURL数
実験２：深さの変化（1台あたり） 10台 解析ページ数 ５台、10台の場合、 解析ページが増加 2台 5台 深さ
実験２：タスクURL数の変化（1台あたり） 10台 解析ページ数 5台 ２台 ネットワークトラフィック の影響が考えられる タスクURL数
結果のまとめと考察 研究の背景と動機 システム構成の概要 システム全体の処理フロー システムの評価実験 結果のまとめと考察
結果のまとめと考察 台数が多い程、1台あたりの解析ページ数は 時間とともに減少する 重複チェックにかかる処理時間が大きくなる タスクURL数、深さを大きく設定すると 1台あたりの解析ページ数が増加する 広く、深い範囲を収集するため、解析ページが増加 但し、時間がたてば異なるSlaveが同時期に 同一領域を解析する可能性がある 収集時間帯によるネットワークトラフィックの影響
パフォーマンス低下の要因 同じURLを解析 しているかもしれない Slave Master Hisyo Slave Slave
システムの問題点 重複したURLチェックに要するオーバーヘッド WWWロボットの収集範囲の指針 データベースのリンクデータ処理 エラーページの回避 収集時間帯の考慮
よりよいシステムにするために 分散処理方式の変更 データベースの処理速度の向上 Master Master Slave Slave データベースの分散化 高速アルゴリズムの適用 Master Master Slave Slave Slave Master Master Slave
おわり
Webページ ハイパーリンク タスク URL数：３ 深さ：３ 深さ １ 深さ ２ 深さ ３
本システムの問題点 無反応サーバへの接続問題 サーバが生きてて、８０番ポートは空いているが、 http daemonが（少なくとも８０番ポートでは）動いていない。 CSSへの非対応 使っているAPIではスタイルシートには非対応
但し、ＭａｓｔｅｒＰＣはメモリを198Ｍに、ＤＢはＨＤＤを４０Ｇに増設 使用ＰＣについて Ｗｅｂページを解析してＵＲＬを収集する「ＳｌａｖｅＰＣ」 ＳｌａｖｅＰＣのタスク管理などを行う「ＭａｓｔｅｒＰＣ」 ＵＲＬデータを格納しておく「データベースサーバ」 ＯＳは全てＶｉｎｅＬｉｎｕｘ２．１．５を使用 マシン名 ＨＩＴＡＣＨＩ ＦＬＯＲＡ３７０ ＣＰＵ Ｐｅｎｔｉｕｍ２－４００ＭＨｚ メモリ １２８Ｍ ＬＡＮ １０ＢＡＳＥ－Ｔ ＨＤＤ ６Ｇ 但し、ＭａｓｔｅｒＰＣはメモリを198Ｍに、ＤＢはＨＤＤを４０Ｇに増設
ＤＢ サーバ ＭａｓｔｅｒＰＣ ＳｌａｖｅＰＣ
Documentクラスによってドキュメント化 ＨＴＭＬの解析方法 HTML Documentクラスによってドキュメント化 ドキュメントを要素ツリー構造化 構造化した要素一つ一つのタグチェック HTML.Tag.FRAME HTML.Tag.A SRC タグの属性値を取得 HREF URL取得
マルチスレッドについて Master Slave 役割 スレッド 各スレッドの仕事内容 Mainメソッド runメソッド タスクURL先の DBからタスクURLの取得 Slaveへのタスク割り当て Slave監視 runメソッド SlaveからのURLデータの受取り URLデータをチェック URLデータをDBへ格納 Slave タスクURL先の Webページ解析 割り当てられたURL先のWebページ を順に解析していく 指定の深さまでWebページを解析する HTTP URL確認 Webページの解析前に，URL先に接続してWebページが正常かを確認する