論文
DBSJ Letters Vol.6, No.1――――――――――――――――――――――――――――――――――――

大規模 Web アーカイブのための更新クローラの設計と実装
Design and Implementation of an
Incremental Crawler for Large Scale WebArchives

田村 孝之♥

喜連川 優♦

Takayuki TAMURA Masaru KITSUREGAWA

筆者らは刻々と変化する Web 情報からの社会知の抽出を目指し，日本語 Web ページを中心とする大規模 Web アーカイブの構築を行っている．本プロジェクトは Web の大域的構造や時間変化の分析を主眼としており，Web アーカイブの網羅性と時間分解能に対する要求が高い．これらの要求に応えるため，取得した Web ページのリンクから新規 URLを発見して収集範囲を拡大しつつ，既知 Web ページに対してはその更新頻度を推定して適応的に再アクセスを行う更新クローラの設計と実装を行った．
For exploiting social knowledge from continuously
changing Web information, we are building a large scale
Web archive mainly containing Japanese Web pages. The
project is unique in that its major concern is structuraland temporal analyses of the Web. As a result, its
demands for both comprehensiveness and temporal
resolution are quite high. To fulfill the requirements, wehave designed and implemented an incremental crawler
which explores into the frontier of new URLs discoveredfrom fetched Web pages while revisiting known URLs
adaptively to their estimated change frequency.

1. はじめに筆者らは刻々と変化する膨大なWeb情報を実社会の鏡像と見做し，その大域的な構造や時間変化の分析に基づく社会知の抽出に取り組んでいる[1]．Web分析の基盤となるのは日本のWeb情報を網羅的に収集・蓄積した大規模なWebアーカイブである．
Webの大域的構造と時間変化の分析を主眼とするWebアーカイブに要求される網羅性と時間分解能の両立を図るには ， Web ペ ー ジ を 1 回 ず つ 収 集 す る 一 括 ク ロ ー ラ (batchcrawler)ではなく，連続的に動作しWebページ毎に独立したタイミングで再アクセスを行う更新クローラ(incrementalcrawler)が不可欠である．更新クローラは過去のクローリン
グ履歴をデータベース化し，Webページ毎の更新頻度に適応したスケジューリングを行うことで，低更新頻度Webページのアクセスに割かれていたリソースを高更新頻度Webページのアクセスに振り向け，最短1日程度の高い時間分解能を♥

正会員 三菱電機（株）情報技術総合研究所
ttamura@acm.org♦
正会員 東京大学生産技術研究所
kitsure@tkl.iis.u-tokyo.ac.jp

1

得ることを可能にする．
多くの国々でWeb上のデジタル文書の保全を目的とする
Webアーカイビングプロジェクトが組織されているが，これらのプロジェクトにおいては網羅性よりもコンテンツの再現性（スクリプトやプラグインの動作まで含む）が重視される傾向にある[2, 3]．また，米国のInternet Archiveは古くから網羅的な収集に取り組んでいるが，1～2ヶ月毎に外部から提供されるデータが主体となっている[4]．Internet Archive
独自のオープンソースクローラの開発も進められているが，更新クローリングを実現するには至っていない[5, 6]．
また，大量のWebページを扱うことの困難さを回避するために，WebサイトやWebページ群を単位として更新の有無を推定する手法も提案されている[7]．これらの手法では1ヶ月あるいは1週間などの比較的長い間隔で一部のWebページをサンプリングし，更新が検出された場合に残りのWebページを一括してクロールするという戦略を用いる．しかし，更新されていないWebページの収集コスト（false positive）や更新されたWebページの収集漏れ（false negative）の問題が本質的に伴うため，大規模なWebページ集合を高い時間分解能で収集するのは難しい．
一方，Webページの更新頻度に適応してアクセススケジューリングを行っても，与えられたリソースの下ではその実施が不可能な場合もある．従来，クローラの動作を制約するリソースとしては，クローラ側のマシンやネットワークが想定されてきたが，相手Webサーバに及ぼすアクセス負荷を考慮することも長期的にクローリングを継続する上では重要である．本稿で述べる更新クローラは，Webページの更新頻度に基づく再アクセススケジューリングを行うと共に，その結果をWebサーバ毎に集約することでWebサーバの負荷状態を把握し，Webサーバに対するアクセス間隔の制御を実現する．

2. アクセススケジューリングアルゴリズム
2.1 Poisson 過程に基づく Web ページ更新間隔推定
更新クローラにおいては，Webページ毎に独立に再アクセスのタイミングを決定することにより，一括クローリングでは実現できない大規模かつ高頻度の収集を可能にする．あるページを再度アクセスするタイミングはそのページが次に更新された直後であることが望ましい．従って効率的な再アクセススケジューリングの実現には，Webページの更新タイミングを正確に見積もることが重要となる．
Choら[8]はWebページの更新が一定の更新頻度λ（更新間隔の逆数）を持つPoisson過程に従うと仮定し，あるWebページを一定期間毎にアクセスした際の更新検出結果からλを推定する方法について包括的に議論している．しかし，大規模Webアーカイブ構築においては大量のWebページを扱うため，一定期間のアクセスを高頻度に繰り返して更新間隔を推定するのは現実的でなく，推定した更新間隔を直ちにアクセス間隔に反映させて不必要なアクセスを生じさせないようにしなければならない．
ここでChoら[8]と同様に不規則アクセスによる更新検出を表す変数を導入する．すなわち，あるページに対してn回アクセスした際にm回(m < n)の更新を検出したものとし，第i番目の更新を検出した際のアクセス間隔を t ci ，更新が検出されなかったアクセス間隔の第j番目のものを tuj とする（図1参照）．

日本データベース学会 Letters Vol.6, No.1

論文
DBSJ Letters Vol.6, No.1――――――――――――――――――――――――――――――――――――
back off により次のアクセス間隔を決定する．また，T = 0となる初回アクセス後には，2 回目のアクセスまでの間隔をある範囲の一様乱数を生成して決定する．

2.2 Web サーバアクセス間隔の制御
図 1 不規則アクセス間隔によるページ更新検出
Fig.1 Page change detection with irregular accessintervals
Poisson過程では tci の期間に1回以上の更新が起こる確率は 1 − exp(−λt ci ) ， tuj の期間に更新が起こらない確率はexp(−λtuj ) であるから，実際にある更新パターンが観測される確率はそれぞれの確率の積となり，最尤法によりλが満たすべき条件は以下の式(1)で与えられる．
mn−mt∑ exp(λcit ) − 1 = ∑ tuj
i =1ci(1)j =1Cho ら[8]は不規則アクセスに基づく更新間隔推定方法として式(1)の直接解法を挙げるに留まっているが，この式は過去のアクセス間隔の履歴を全て含んでおり，Web ページ毎に保持すべき状態量が膨大になってしまう．また，保持する履歴の範囲を有限ウィンドウ内に限定したとしても，式(1)からλの値を求める計算は単純ではない．そこで式(1)を近似し，より単純な推定方法を導いた．
まず，各 tci が全て等しい場合，すなわち tci = tc (1 ≤ i ≤ m) の場合は式(1)を解くことができ，λの推定値の逆数は式(2)で与えられる．
mt + UT(2)
λˆ−1 = t c / log c= t c / log(0 < U < T )UU
ただし，U は更新が検出されなかったアクセス間隔の総和，すなわち ∑ tuj を表し，mtc + U は全アクセス間隔の総和に等しいので T とした．
全ての tci が等しくない場合については，式(2)の t c を {t ci }の代表値 t c で置き換えた式(3)によりλの逆数を近似する．

T(3)λˆ−1 ≈ tc / log(0 < U < T )Ut c としては例えば tci の最小値 tc min や平均値 tc avg などを用いることができる．ただし，最小値，平均値とも極端な tci 値の影響を受け易いため，最小値と平均値の幾何平均を用いている．指数移動平均により有限の履歴を用いるようにしても良いだろう．また，比 U/T は Web ページの安定度を表すと考えられ，この値が大きいほど λˆ−1 を大きくする効果がある．
式(3)においては個々のアクセス間隔の履歴は不要であり，初回アクセスからの経過時間 T，更新が検出されなかったア
クセス間隔を累積した U，更新を検出したアクセス間隔の最小値 tc min や平均値 tc avg (=(T - U)/m)から次回アクセスのタイミングを決定することが可能になる．このように Web ページ毎に保持する状態変数を大幅に削減したことにより，大規模な Web ページ集合に対して再アクセススケジューリングを適用することが可能となった．
なお，式(3)には特異点があり， λˆ−1 を求められない場合がある．すなわち，全く更新が検出されない場合(U = T)や全てのアクセスで更新が検出される場合(U = 0)である．これ
らの場合には直前のアクセス間隔を定数倍する exponential

2

Webページ再アクセススケジューリングにより，各ページをアクセスするタイミングが決定されるが，実際のクローリングにおいてはWebページは独立な実体ではないことに注意が必要である．すなわち，WebページはURLをキーとするWebサーバへの問合せの結果として得られるものであり，Webサーバに対するアクセスタイミングも考慮に入れなければならない．
一般にクローリングにおいては同一Webサーバから同時に複数のWebページを取得することはマナー違反とされる．
また，Webサーバへのアクセスを逐次に行ったとしても，連続するアクセスの間隔が短いとWebサーバが高負荷となるので好ましくない．どの程度のアクセス間隔なら許容されるかは明確には規定されておらず，Webサーバ管理者の心証に依る所も大きい．少数Webサイトを対象とする選択的アーカ
イビングでは事前にWebサーバ管理者に了解を得ることもできるが[3]，大規模Webアーカイブ構築においては実施不可能であり，明示的な拒否（管理者からの連絡やrobots.txtなどのRobot Exclusion Standardに従った設定）がない限り収集を行うopt-outポリシーを採用せざるを得ない．従って，Webサーバへの負荷を最小限に止める配慮は極めて重要である．
ここで，Webサーバiに属する全てのWebページの集合を{Pij } とし，Pij の再アクセス間隔を Tij ,十分長い期間τにおける Pij のアクセス回数を N ij とする．Webサーバiへのアクセスを時間 I i 毎に逐次的に行うという制約の下で各ページの取得が可能となるには，
I i ∑ N ij ≤ τ(4)jが成り立つ必要がある． N ij ≈ τ / Tij （小数部分を無視）により，式(4)から以下が得られる．
−1⎛1 ⎞= ⎜ ∑ ⎟ ≡ Li −1Ii ≤(5)⎜∑ j N ij ⎝ j Tij ⎟⎠Li はWebサーバiに属するページのアクセス頻度の総和とτなっており，Webサーバの負荷を表す指標と考えられる．負荷指標の逆数である右辺全体は，Webページ再アクセススケジューリングに従ったアクセスを実現するWebサーバアクセス間隔の理論的な上限である．Webサーバの負荷指標が大きくなるに従って，より短い間隔でWebサーバにアクセスする必要が生じるが，Li −1 がマナー上許容できない値となった
場合，Webサーバiは過負荷状態となり，Webページ再アクセススケジューリングに従ったアクセスが実施不可能となる．
このように，Webページ再アクセススケジューリングの結果をWebサーバ毎にまとめて負荷指標という単純な値で表すことにより，必要十分なWebサーバアクセス間隔を設定したり，過負荷状態の検出に利用することが可能になる．
なお，Webサーバ負荷指標は要素であるWebページの追加・削除（収集対象からの除外）や再アクセス間隔の変更に
対し，インクリメンタルな更新が可能である．すなわち，現

日本データベース学会 Letters Vol.6, No.1

論文
DBSJ Letters Vol.6, No.1――――――――――――――――――――――――――――――――――――
在の負荷指標の値と更新前後のWebページの再アクセス間隔の値だけに基づいて（全Webページに関する値をスキャンすることなく）新たな負荷指標を設定することができる．

3. 更新クローラの実装
前節で述べたWebページおよびWebサーバに対するアクセススケジューリングを実現する更新クローラをPCクラス
タ上で実装した．図2は単一ノード上のプロセス構成およびデータフローである．以下，各プロセスの機能を述べる．の曖昧さ（エスケープシーケンスなどによる）の解決と共に，サーバ別名DBを参照したサーバ名の正規化を施される．
url splitter: リンクデータファイルをURLのサーバ名部分にハッシュ関数を適用することにより，担当するクローラノード毎のファイルに分割する．分割後のファイルを各担当ノードに送付する．なお，クローラノード間の通信はこの部分でのみ発生し，残りのほとんどの処理は各ノードが独立して動作する．
requester: 各ノードのurl splitterから転送されたリンクデータファイルの断片を読み込み，workerに対して新規URL アクセス要求を送る．
link extractor，リンクデータファイル，url splitter，およびrequesterを含むループは新規URL発見のための機構であり，一括クローラにも見られるものである．一方，schedsplitter,長期キュー，およびrefresherからなるループはURL再アクセスに固有の機構である．更新クローラでは，これら2つのループが同時に動作することにより既知ページの更新と新規ページの出現の双方に対応することが可能となっている．

worker: クローラの本体であり，Webサーバと通信してWebページのダウンロードを行う．また，requesterプロセスおよびrefresherプロセスからダウンロード対象のURLを受け取って処理する．requesterが要求するのは新規URL候補であり，URL状態DBに既に存在する場合は棄却する．
URL状態DBに存在しなかった場合は新たにエントリを追加し，URLを短期キューに投入する．refresherからは常に既知URLを受け取り，短期キューへの投入を行う．
短期キューはWebサーバ毎に独立したプライオリティキ
ューと見做すことができ，Webサーバアクセススケジューリングに従ったURLの取り出しを可能にする．短期キューには1日以内に取得可能なURLのみを格納し，それを超えるURLは長期キューに書き出して3日後に再度受け付けるようにしている．
workerはWebページをダウンロードしてそのコンテンツをファイルに格納すると，Webサーバの応答コード（304：
Not Modified）やコンテンツ（ハッシュ値）の変化に基づいて更新判定を行う．その結果をWebページ再アクセススケジューリングに適用し，再アクセス時期の決定を行うと共に，URL状態DBに含まれる状態変数（2.節の T,U,および tc など）やコンテンツハッシュ値を更新する．さらに，URLを短期キュ ー か ら 取 り 除い て 長 期 キ ュ ー に 移 動 す る （ schedsplitterに渡す）．
sched splitter: workerが出力する再アクセスURLをアクセス日付順にソートし，長期キューを構成する1日毎のファイルのうち，対応する日付のファイル末尾に追加する．
refresher: 一定時間毎に動作し，長期キューから再アクセス期限を過ぎたファイルを読み込んで，workerにURL再アクセス要求を発行する．
link extractor: workerが出力した新規コンテンツの内，リンクを含むHTMLデータを解析してリンク先URLを抽出し，ルールに従って選別や優先度設定を行った上でリンクデータファイルに出力する．リンク先URLは相対パス指定や表記

3

4. 大規模クローリング実験
ここでは更新クローラの動作結果から得られた知見について述べる．クローリング開始に当たってはこれまで数ヶ月～1 年置きに実施してきた一括クローリングの数年分の履歴を活用し，URL 状態 DB の初期値に反映した．その後，改良を加えながら延べ約 1 年に亘り更新クローラを動作させた．
図 3 は，実験終了時点での Web ページ再アクセス間隔の頻度分布である．ただし，1 回しかアクセスしていない Webページは除いている．一週間以内に再アクセスするページが非常に多くなっている．一方，長期間更新がないと予測されるページも多い．再アクセス間隔の上限を 400 日とし，これを超えるページについては 300～400 日の間の一様乱数で代替したため，この区間のページ数が目立って多くなっている．
これらのページは再度更新される見込みは極めて少ないと思われるが，Web サーバやドメインの廃止によりアクセスできなくなる可能性はあるため，強制的にアクセスするようにしている．
1e+08

1e+07
Page frequency

Fig.2

図 2 更新クローラの構成
Architecture of incremental crawler

1e+06

100000

10000
050

100

150
200250
Revisit interval [days]

300350400

図3

Web ページ再アクセス間隔の頻度分布

Fig.3

Histogram of web page revisit intervals

図 4 は同一再アクセス間隔を持つ Web ページについてページ更新検出率の平均および標準偏差をプロットしたものである．ページ更新検出率はページアクセス回数に対する一

日本データベース学会 Letters Vol.6, No.1

論文
DBSJ Letters Vol.6, No.1――――――――――――――――――――――――――――――――――――意バージョン取得数の比であり，1 に近い程無駄なアクセスがないことを示すが，逆にページ更新を取りこぼすリスクも増す．グラフでは再アクセス間隔の増加と共にページ更新検出率が徐々に減少している．再アクセス間隔が大きい領域ではさらにアクセス間隔を増加させてアクセス回数を減らす必要がある．また，再アクセス間隔が小さい領域ではページ更新検出率が 1 に近付いている．これらについては再アクセ
ス間隔をさらに短縮し，バージョンの取りこぼしがないことを確認する必要がある．
Change detection rate (#uniq.-versions / #visits)

1

Mean
Mean +/- StdDev

0.8

0.6

0.4

0.2

0050100150200250Revisit interval [days]

300350400

図4Web ページ再アクセス間隔に対する更新検出率

Fig.4

Change detection ratio vs. Web page revisitintervals

図 5 は Web サーバ負荷指標（Web サーバに属するページの再アクセス間隔の逆数の総和）の逆数として与えられるWeb サーバアクセス間隔理論値の分布を示したものである．
1e+07

Cumulative frequency(Cumulative) server frequency

1e+06

100000

10000

1000

100
Every minute

HourlyDaily

WeeklyMonthly

Yearly10110100

1000

10000 100000 1e+06

1e+07

1e+08

1/load-factor (Theoretical server access interval) [sec.]

図5Fig.5

Web サーバアクセス間隔理論値の分布

Distribution of theoretical web server accessintervals

図 5 によると非常に緩やかなアクセスで十分なサーバが多いことが分かる．1 分以内にアクセスする必要があるのは全体の 1%に満たない．しかしながら，数秒毎にアクセスする必要があるサーバも 100 程度存在している．これらのサーバに対しては，理論値通りのアクセスを行うとマナー違反と見做されてしまう可能性が高い．しかしながら，単純にアクセス間隔の下限値を適用すると，収集対象 Web ページや再アクセス間隔が制御不能になってしまう．そのため，これらの過負荷サーバに対しては，Web ページ再アクセス間隔の修正や一部 URL の除外などの対処が必要になる．Web サーバ
負荷指標を維持することで，過負荷状態を検知するだけでな

4

く，過負荷状態の解消を定量的に実施することも可能になる．

5. まとめ
本稿では，Web 分析の基盤となる大規模 Web アーカイブの構築を目的とした更新クローラについて述べた．更新クローラは収集した Web ページから新たなリンク先 URL を発見して収集対象に加えると共に，過去の更新傾向に基づいて各Web ページの再アクセスをスケジューリングすることで高い網羅性と時間分解能の両立を図る．また，Web サーバに及ぼす負荷を考慮し，アクセスマナーの制約下で Web ページ再アクセススケジューリングが実施可能かどうかを判定する指標を導入した．
実際に数百万 Web サーバを対象とする大規模クローリングを行い，そこから得られた Web サーバの特性を評価した
結果，一部の Web サーバが過負荷状態となっており，理想的なスケジューリングが実施できない条件下にあることが分かった．これらの Web サーバに対しては，Web ページ再アクセススケジューリングを修正し，次善の状態を求めるようにして行くことが不可欠である．今後は各種スケジューリ
ングアルゴリズムの詳細な評価と共に，過負荷状態の解消手法について検討し，更新クローラへの統合を進めて行きたい．

[謝辞]
本研究の一部は文部科学省リーディングプロジェクト
e-Society 基盤ソフトウェアの総合開発「先進的なストレー
ジ技術および Web 解析技術」による．

[文献][1] 豊田, 喜連川：“日本におけるウェブコミュニティの発展過程”, 日本データベース学会 Letters, 2, 1, pp. 35-38(2003).
[2] International Internet Preservation Consortium:“netp-reserve.org”. http://netpreserve.org/.
[3] 国立国会図書館：“インターネット資源選択的蓄積実験事業(WARP)”. http://warp.ndl.go.jp/.
[4] Internet Archive: “About IA”.
http://www.archive.org/ about/about.php.
[5] K. Sigurosson: “Incremental crawling with heritrix”,Proc. of IWAW (2005).
[6] K. Sigurosson: “Managing duplicates across sequentialcrawls”, Proc. of IWAW (2006).
[7] J. Cho and A. Ntoulas: “Effective change detection
using sampling.”, Proc. of VLDB, pp. 514-525 (2002).
[8] J. Cho and H. Garcia-Molina: “Estimating frequency ofChange”, ACM TOIT, 3, 3, pp. 256-290 (2003).

田村 孝之

Takayuki TAMURA

三菱電機株式会社情報技術総合研究所専任および東京大学生産技術研究所協力研究員．1996 東京大学大学院工学系研
究科博士課程修了，博士(工学)．並列データベース，Web マイニングに関する研究に従事．情報処理学会，電子情報通信学会各会員．日本データベース学会正会員．

喜連川 優

Masaru KITSUREGAWA

東京大学生産技術研究所戦略情報融合国際研究センター長，教授．1983 東京大学大学院工学系研究科博士課程了．工博．
データベース工学，並列処理，Web マイニングに関する研究に従事．情報処理学会フェロー，電子情報通信学会フェロー，
SNIA-Japan 顧問．日本データベース学会理事．

日本データベース学会 Letters Vol.6, No.1