かれ4

かれこれ4個目のブログ

クローラを生まれ変わらせるにあたっての思考

crawler scraping キャベツはどうした お料理行進曲

Advent Calendar 2015の13日目の記事です。

今うちで動いているCrawlerは数年前に作られたもので、
仕組みとしてはAzureのService Fabricの上でAWSのLambdaを動かしているのと似たアーキテクチャになっている。

そろそろ生まれ変わりの頃かなと思う。

生まれ変わるにあたって、これからのアーキテクチャをどうしようかと悩むわけだけど、
そんな時には過去に遡っていくと次時代へのヒントが転がっていることがよくある。
特に、過去に敗北した素晴らしいアーキテクチャが今の技術であれば一般時にも実現可能になっていたりする。

昔話

昔々世界にはInktomiという会社と
AltaVistaという会社があった。
Inktomiという会社はソフトウェア開発会社で、2002年に米Yahoo!に買収されている。
AltaVistaは検索エンジンの会社だったが、2003年にOverture社が買収し、
2003年にOverture社を米Yahoo!に買収している。

詳しい歴史等はWikipediaを見てもらえば良いとして、この２社はざっくり言うとどちらもクローラを持ち、
検索サイトとして、もしくは検索エンジンのAPI提供として一時代を築いた２つの企業。

この二つの企業では、crawlingとindexingについて大きく違う思想を持ってやっていた。

AltraVistaはDEC Alphaの高性能差をアピールするために生まれたという経緯があり、
1台で完結するように作られたCrawlerが動いていた。
それに対し、Inktomiは完全に分散された環境でスケールする事を意図して作られている。

この2つの会社の事を心に止めておきながら、本題に入っていきたい。

原子的なCrawler

Crawlerについて順を追って、どのようにしていくべきなのかを考えてみる。

その過程でCrawlingとScrapingを分けて考えていかないと行けない。
Crawlingに関して言えば、初期ロボット型検索サイトを作りたいのであればScrapingはせずに、
シンプルに正規表現なんかでタグをはずし、
テキスト部分だけで転置インデックスを作って行くだけでも大規模でなければ実現できる。

それに対してScrapingをする必要があるのは、インデックスを作りたいのではなく、
構造化されたデータとして使いたい場合。

とはいえ、とりあえずCrawlingの話からしよう。
Crawlingと言っても、シンプルな方法からまるで人間がアクセスしているかのような動きをするとか
様々なレイヤーがある。

HTTPでファイルを取得する。

まずシンプルにHTTPでリクエストを送りファイルを保存する事を考えてみる。

  +-------------+    +-----------+
  | HTTP Client | -> | HTML File |
  +-------------+    +-----------+

このようにCrawlerがHTTPRequestを送り、シンプルにHTML、もしくはJsonなどをファイルに保存する方法。
ただ、これでは、CrawlerではなくただのHTTPClientでしかない。

これを実現するためにはwgetというコマンドがある。

再帰的に取得する。

次に再帰的に取得する場合を考えてみる。

  +-------------+    +-----------+    +------------+
  | HTTP Client | -> | HTML File | -> | html parse |
  +-------------+    +-----------+    +------------+
       ^                                v
       +---------------------------------
  1. HTTP ClientがHTMLファイルをダウンロード
  2. そのHTMLをパース
  3. Aタグの文字列を絶対パス(URL)に変換
  4. URLをHTTP Clientが

というループを繰り返すことになる。

そして、これを実現するためにはwgetというコマンドがあり、

  • rというオプションをつけることで可能。

不要なアクセスをなくす。

次に考える事は、どこをたどるかという事。
不要なところにアクセスして、ファイルを取得しても仕方がないので、必要なところだけに絞って次のアクセスをする。

  +-------------+    +-----------+    +------------+
  | HTTP Client | -> | HTML File | -> | html parse |
  +-------------+    +-----------+    +------------+
       ^              +--------+                   v
       +------------- | Filter | -------------------
                      +--------+

HTMLをパースして、Aタグを抜き出すところまではさっきと同じだけれども、その後、HTTP Clientに行く前に
Filterを介すことにする。
そうすることで、不要なアクセスをなくし、効率的にクローリングすることが可能になる。


そして、これを実現するためには、wgetというコマンドがあり、これだけのフィルタオプションがある。

再帰ダウンロード時のフィルタ:
  -A,  --accept=LIST               ダウンロードする拡張子をコンマ区切りで指定する
  -R,  --reject=LIST               ダウンロードしない拡張子をコンマ区切りで指定する
       --accept-regex=REGEX        許容する URL の正規表現を指定する
       --reject-regex=REGEX        拒否する URL の正規表現を指定する
       --regex-type=TYPE           正規表現のタイプ (posix|pcre)
  -D,  --domains=LIST              ダウンロードするドメインをコンマ区切りで指定する
       --exclude-domains=LIST      ダウンロードしないドメインをコンマ区切りで指定する
       --follow-ftp                HTML 文書中の FTP リンクも取得対象にする
       --follow-tags=LIST          取得対象にするタグ名をコンマ区切りで指定する
       --ignore-tags=LIST          取得対象にしないタグ名をコンマ区切りで指定する
  -H,  --span-hosts                再帰中に別のホストもダウンロード対象にする
  -L,  --relative                  相対リンクだけ取得対象にする
  -I,  --include-directories=LIST  取得対象にするディレクトリを指定する
  --trust-server-names             ファイル名としてリダイレクト先のURLの最後の部分を使う
  -X,  --exclude-directories=LIST  取得対象にしないディレクトリを指定する
  -np, --no-parent                 親ディレクトリを取得対象にしない

スクレイピングする

ここまでで、HTMLファイルを再起的に収集することは出来た。

次は取得したHTMLから必要部分を抽出しくことで、やっとクローリングに意味が出てくる。
このHTMLから必要部分を抽出していくことが、スクレイピングなわけだけど、どのように実施していくのが効率的なのだろうか？

これは大きく2つの方法が考えられる。

後になってやっぱり、この項目も抽出したいなんて感じになった場合はCrawlingしたタイミングでのHTMLが必要になる。
もう一度クローリングし直すでも良いかもしれないが、時系列データを収集したい場合なんかはそれではいけない。
その分ストレージ容量を大量に消費するというのがトレードオフになり、それぞれのメリットとデメリットとして存在する。
ここは用途に併せて作るべきと言いたいところだけれども、ストレージをクラウドに任せる事によって
なんとかなるかもしれない。

そして後は抽出後のデータをどこに格納するかという事を考えないと行けない。
今回はCrawlerとScrapingの事を考えないと行けないので、データをどこに保存するのかは
おいておく。

Crawlerをスケールさせる事を考える

次にスケールする場合について考えてみる。
とりあえずオンメモリでやる場合は、メモリ上にしかHTMLが保持されていないので、マシンやプロセスをまたぐことは出来ないと思ったほうがよい。
RDMAなんかでやってやれない事はないが、そんな事を考えるほうがめんどくさい。
というわけでスケールの単位としては以下の図のようになる。

+-- PROCESS -----------------------------------+ +------+
|  +-------------+    +------+    +----------+ | |+----+|
|  | HTTP Client | -> | HTML | -> | Scraping | |-|| DB ||
|  +-------------+    +------+    +----------+ | |+----+|
+----------------------------------------------+ +------+

このような感じでPROCESSを増やすなり、マシンを増やすなりすれば良いので、
コンテナなんかとの相性が良さそうだ。

しかし、ここで考えないと行けないのが、HTTP Client部とScraping部を非同期にするか同期にするか。
一つのProcessがHTTPでの通信とScapingの両方をやる場合、どちらの速度も同じ場合のみ、
非同期でも問題はない。
しかし、HTTPの通信速度は安定するものではないし、HTMLのボリュームによってはScrapingの速度も安定しない。
並列、非同期にするメリットがなく、直列の同期処理にするのが良い。


次に、HTMLを一度ファイルに書き出す方法の場合はどうだろうか。
ここでの前提としては、ファイルはローカルのストレージではなく、クラウド上のObjectStorageに保存するものとする。
この場合のスケールは下の図のようになる。

+---------------+  +--------+  +-------------+
|+-------------+|  |+------+|  |+----------+ |
|| HTTP Client ||->|| HTML ||->|| Scraping | |
|+-------------+|  |+------+|  |+----------+ |
+---------------+  +--------+  +-------------+

HTTP ClientとScraping部が完全に切り離されている。
これによって、HTTP ClientとScrapingのProcessを分離することが可能になっている。
HTMLのファイルを取得するためのIOコストがあるが、HTTP ClientのHTTP通信のコストよりも
低いコストである確率は高い。(ScrapingのプロセスがObjectStrageと同一クラウドに存在する場合。)


しかし、この場合再帰的なCrawlingをする時にScrapingが終わるまで、次のページの取得が始まらない。
それではあまりスケーリングのメリットが享受出来ない可能性が高い。

なので、この構造から少し改良をして、再帰的なクローリングを効率的に行うようにする。
リンクをたどるためにHTMLのParserをHttp Client内部に持ち、Crawlingだけを先に進めていき
Scrapingを非同期に動かすという方法。 下の図のようになる。

+---------------+  +--------+  +-------------+
|+-------------+|  |+------+|  |+----------+ |
|| HTTP Client ||->|| HTML ||->|| Scraping | |
|+-------------+|  |+------+|  |+----------+ |
|    ^    V     |  +--------+  +-------------+
|+-------------+| 
|| HTML Parser ||
|+-------------+|
+---------------+

これによって、HTTPClientとScrapingを完全に分離出来てはいるが、非常に無駄の多い事はすぐに分かると思う。
HTTP Client部とScraping部で、2回HTML Parserが動くことになるからだ。

ここで言うParserと言うのは、きちゃないHTMLを綺麗なHTMLにしてDomParserがすんなり読み込める形にすることをいう。
具体的には、HTMLの整形と文字コードの変換になる。

この無駄に対してのアプローチとしては、非常にシンプルに解決できる。
ParseされたHTMLを保存しておけばいい。

+---------------+
|+-------------+|
|| HTTP Client ||
|+-------------+|
|    ^    V     |  +---------------+  +-------------+
|+-------------+|  |+-------------+|  |+----------+ | 
|| HTML Parser ||->|| Parsed HTML ||->|| Scraping | |
|+-------------+|  |+-------------+|  |+----------+ |
+---------------+  +---------------+  +-------------+

ここで、さっきのwgetでやっていた、無駄なアクセスを減らす動きも加えていきたい。
ここまでの構成だと、HTMLをParseし、そのままHTTP Client部に渡しているので、
間にFilterを挟めば良いだろう。


これによって、無駄なアクセスも省略できるようになってきた。
ここまで来ると、今度はこのParserすら非同期化したくなってくる。

+---------------+
|+-------------+|
|| HTTP Client ||
|+-------------+|
+---^-------v---+
| Queue | Queue |
+---^-------v---+
|+--^---+   v   |
||Filter|   v   |
|+--^---+   v   |
+---^-------v---+  +---------------+  +-------------+
|+--^-------v--+|  |+-------------+|  |+----------+ | 
|| HTML Parser ||->|| Parsed HTML ||->|| Scraping | |
|+-------------+|  |+-------------+|  |+----------+ |
+---------------+  +---------------+  +-------------+

HTTP ClientとParserの間をQueueでつなぎ、Filterを通したものをQueueを通してHTTP Clientに戻す形にする。

ここまで来ると勘の良い人は気づいているかも知れないけれど、
Scraperの準備をする前に、Crawlingだけ開始することができる。

Parsed HTMLはObjectStorage上に保管されているので、定点観測的に使う場合にはすぐにでも
データを収集しておくことが可能だ。

そして、この構造にするともう一つメリットがある。
Scrapingをしている人なら、わかると思うけれど、XPATHで抜くにしろ正規表現で抜くにしろ
何度も試行錯誤をすることが多いと思う。
そのたびにサイトにHTMLを取得しにいっていないだろうか？

もしインメモリでやっていたら、確実にHTMLを何度も取得しにいっているだろう。
この構造になることで、一度HTMLを収集していれば、何度でも試行錯誤し放題になる。



StorageとScrapingの関係。

最後にStorageとScrapingについてもう少し深く掘り下げていきたい。
もし、Scrapingをストリーム処理のように、Crawlingしてきたそばからやっていきたい場合は
Storageに保存されたことにHookさせる事ができるサービスもあるので、随時Scrapingを開始することも可能だ。

Scrapingをストリーム処理する必要がない場合は更に自由度がます。
必要がなくてもストリーム処理しても良いし、蓄積されたParsedHTMLに対して一気にScrapingすることも可能になる。

その場合は、未処理のScraping量に併せてProcessの数を増減させて行けばよい。
Scrapingをしなくていい時は、ScrapingのProcessすべてを停止しておけば良いので、
クラウド上のコンピューティングリソースを使う場合コストメリットも出てくる。
StorageがHDFSなんかだったりしたら、Hadoopで一気にScrapingする事も可能になったりもしてくる。
例えば、 

SELECT `span.name`, `span.price` FROM `STORAGEPREFIX.div#listtable ul li `

なんて事も可能に

また、StorageにHTMLを保存し、Scrapingを分離することによってデータ活用のタイミングをずらす事もできるので、
インターネット上の統計的な分析には無駄なコンピューティングリソースを使う事なく、機をうかがう事も可能になる。
半年分の動向とか見たい時なんかには効率的だ。



まとめ

ここまで、クローリングについてどのようなアーキテクチャにしていくのが良いか考えていた事をうぁーと書いてみたけれど、結果どうしたかというと、Crawling部とScraping部を分けた。
それによって、データの使い回しがきくようになったことと、クローリングだけを先に始めることができる事によって、やりたいことを実現するにあたって、
情報の取り逃しを減らすことが可能になった。
Storageコストはかかるが、そこは圧縮するなりコールドストレージに落とすなり、最適化の方法が尽きたわけではない。
というわけで、結局Microserviceのような形に落ち着いた。

で、冒頭に出てきた2つの会社だけれども、特に意味はなく意味深な感じにしたかっただけでした。