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