クローラープロジェクト進捗報告

クローラープロジェクト進捗報告
高橋俊行
今日の報告
 高速化
 Export API
Crawler, Spider, WWW robot
(a) Fetch a page
(b) Parse it to extract all linked URLs
(c) For all the URLs not seen before,
repeat (a)-(c)
[Broder03]
Web World
The web is very large.
 Google indexed over 3billion pages.
 The web has doubled every 9-12 months
The web pages are changing rapidly.
 Any change
About 40% of all web pages change weekly.
 Change by a third or more
About 7% of all web pages change weekly
Goal
To obtain a reasonably fresh and
complete snapshot of the web, a
search engine must crawl at least 100
million pages per day.
 Step (a) must be executed 1,000
times/sec.
 Membership test in step (c) must be
done well over ten thousand times/sec.
Issues
Parallel and distributed
Tolerance to failures
Scalability
Politeness
 Robot exclusion protocol
 No DoS nor DDoS
Zao project
空いている計算機資源を有効活用
世界中に分散→World Wide Web Crawler
分散Indexing, Link Analysis
とりあえず、、、
Cluster を使用したcrawling
 NEC Express5800 16台
 Compaq DL360 16台
1000pages/sec をめざす
 ４台のDEC DS20で270pages/sec
 16台のDEC DS20で500pages/secの報告あり
Kototoi.org(133.11.36.x)
www.kototoi.org
計算ノード
 Sun Blade 1000 * 16 (SPARC)
 Compaq DL360 * 16 (Dual PIII 800MHz)
 NEC Express 5800 * 16 (PIII 1.4GHz)
データサーバー
 IBM xSeries (8 Xeon 1.6GHz) 3TB Disk
 20TB RAID
東大幹線に直接光接続
Zao crawler version 1
http://www.abc.com/def.html をcrawl
User-agent: *
 www.abc.com → 133.11.36.2
Disallow: /cgi-bin
 www.abc.com/robots.txt の取得 Disallow: /images
 www.abc.com/def.html の取得
 /def.html のparse → あたらしいリンクの発見
同時に数千の Webサーバーにアクセス
ひとつのWebサーバーには1分おき
複数のクローラーが協調してcrawl
資源の追加削除が自由でスケーラブルな性能
Zaoクローラーの構造
Retriever
Scheduler
Extractor
Compressor
Downloader
Partition
Table
Eliminator
Forwarder
Document
DB（Silo)
URL
DB
Forward
URLs
Document flow
URL flow
to other crawlers
Partition Table
layout_table = [
(‘q0.*.*.*.o0’, ‘tsubame00.kototoi.org’),
(‘q1.*.*.*.o0’, ‘tsubame01.kototoi.org’),
(‘q2.*.*.*.o0’, ‘tsubame02.kototoi.org’),
(‘q3.*.*.*.o0’, ‘tsubame03.kototoi.org’),
(‘q0.*.*.*.o4’, ‘hibari00.kototoi.org’),
(‘q1.*.*.*.o4’, ‘hibari01.kototoi.org’),
(‘q2.*.*.*.o4’, ‘hibari02.kototoi.org’),
(‘q3.*.*.*.o4’, ‘hibari03.kototoi.org’),
]
fc403278
q3
o1
(‘q3.*.*.*.o1’,
‘tsubame07.kototoi.org’)
h0～h1
q0～q3
o0～o7
Half
Quarter
Octant
Retriever の構造
Ready
Queue
URL
Internet
Connection
Holdover
Queue
URL
Job
Idle
deny
holdover
ready
save
error
connect
URL &
Page
Retrieve
Queue
Idling
sending
saving
receive
send
timeout
receiving
Eliminator
Extracted URLを
 他のcrawlerに転送
 URLDBに照会して
→New URLを抽出
URLDB
非常に大きい、ボトルネックになりやすい
分割、統合が短い時間でできる必要有
照会～抽出の時間はきにしない
Eliminator
Extracted URLを
 他のcrawlerに転送
 URLDBに照会して
→New URLを抽出
URLDB
このときにキャッシュを使う！
[Cho02][Broder03]
非常に大きい、ボトルネックになりやすい
分割、統合が短い時間でできる必要有
照会～抽出の時間はきにしない
URL Cache
役割
 他のcrawlerに転送するURLを減らす
 URLDBへの照会を減らす
CLOCK または RANDOM がよい
キャッシュサイズは50000が適当
[Broder03]
CLOCK Cache
キャッシュサイズぶんのMark bit
 Hit したときは Mark bit を on にする
Evict するエントリを選ぶとき
 Handler がMark bit の配列をスキャン
Mark bit がon だったらoff にする
Mark bit がoff だったらEvict
URL Cache のインプリ
 CLOCKのインプリ
RANDOMのインプリ
URLDB の構造
ハッシュ値
www.abc.com:80/def.html
fc403278
0
4
c
f
URLDB の特徴
URLの投入に必要な時間は短いが、そのURL
がLeafに到達するまでそれが「新しいURL」な
のかどうかわからない
少ないメモリでもok
物理的な拡張が容易
URLDB の問題とその解決
 投入したURLがなかなか判定されない
Push 機能の導入
Retriever からの input がなくなったときに
乱数を発生し、その乱数へむかってpush
経験から改良したところ
eth0: can’t fill rx buffer (force 0)
 同時にMEMORY ERROR
 大きなファイルを取ってくるときに発生
→大きなファイルは取ってこない
腐ったデータを読み込むと動かない
→try catch で回避
メモリリーク
ドキュメントの数
ドキュメントの大きさ
圧縮しながらDiskの読み書きは損
Zlibを使い、URLを2000000行読み書きした
 圧縮して書く
 解凍して読む
69.93秒
30.15秒
 圧縮せずに書く
 圧縮しなかったものを読む
48.11秒
17.47秒
NEC Express5800 PIII 1.4GHz Ultra160SCSI
htmlしかとってこない
.html 60.4%
15.1%
.htm
9.9%
/
2.4%
.jpg
.shtml 2.2%
none
1.8%
.asp
1.6%
.pdf
1.4%
I/O の高速化
 URLDBはローカルディスクにつくる
 SiloとURLDBは別のディスクにつくる
Stop words
 stop_words =
'(free|password|pussy|bitch|manko|a
dult|fuck|sex|erotic|panty|skirt|porn|
nude|naked|AppleGate|pink|girl|teen
|kitt|video|sumi\masen|xxx|kogal|chikan|sukebe|mov
ie|superloose|peep)'
この１年
32台 16台
I/Oの高速化
RANDOM
Cache の
インプリ
I/Oの高速化
Push のインプリ
URLDB非圧縮
この2週間
性能が右肩下がりなのはなぜ
 URLDBから生産されるURLが少ない
 <Base> タグを認識していないために発生す
るループ
http://abc.com/error/
404 – Page not found
<base href=http://abc.com/>
<a href=“hoge”> hoge </a>
<a href=“aho”> aho </a>
http://abc.com/error/hoge
http://abc.com/error/aho
Export API
 できるだけシンプル
 tokiでもtsubameでもxx研のデスクトップで
も同じAPIがつかえる
Kototoiネットワーク
toki
hibari00
tsubame00
sekirei00
5TB
home
hibari01
tsubame01
sekirei01
5TB
hibari02
tsubame02
sekirei02
5TB
hibari03
tsubame03
sekirei03
5TB
sekirei04
5TB
PIII 800MHz*2
hibari15
PIII 800MHz*2
tsubame15
PIII 1.4GHz
Xeon
Zao C API
 クライアント・サーバ方式
 ユーザアプリケーション＝クライアント
 Siloが読めるところでサーバを立てる
 Siloを読むためのCライブラリを用意




ZaoStream* open_stream(char*)
ZaoUrl* get_url(ZaoStream*)
void request_contents(ZaoUrl*)
ZaoPage* get_contents(ZaoStream*)
デモ
性能
 １秒間にget_urlを実行できる回数
 6万回弱
 １秒間に
get_url/request_contents/get_content
sを実行できる回数
 1600回弱
 1秒間に.jpドメインだけをget_contentsでき
る回数
 1600回弱
Future work
 APIの並列化問題
 APIの関数を並列に呼び出したらどうなる？
 複数のストリーム○
 シングルストリームマルチスレッド×
 複数のクライアントにどのように分散させるか
 現在はすべてのページをスキャン
 途中でとめて途中から再開したい
 グループで仕事をシェアしたい
References
 [Broder03] A. Z. Broder, M. Najork, and J. L.
Wiener. Efficient URL Caching for World Wide
Web Crawling. In Proceedings of the 12th
World Wide Web Conference, May 2003.
 [Cho02] J. Cho and H. Garcia-Molina.
Parallel crawlers. In Proceedings of the 11th
World Wide Web Conference, May 2002.
 [Najork01] M. Najork and A. Heydon. Highperformance web crawling. SRC Research
Report 173, Compaq Systems Research
Center, Palo Alto, CA, Sept. 2001.

Download Report