HTTPリクエスト並列化のボトルネック

今日(昨日?)は、HTTPリクエストを並列化して大量のURLからのデータ取得を高速化する、というようなことを試していた。

並列化

初めは単純に、個々のHTTPリクエスト(URL)を別々のスレッドで処理すれば、(イメージ的には)総処理時間もO(1)*1に近いものになるのではないかと考えていた。

その考えを反映して書かれたのが以下のコード:
参照: tiny-http[置き場]*2

(require :tiny-http) ; 0.1.7

;; 引数のurlリストに対して、並列的にHTTPリクエストを行う関数
(defun parallel-http-request (urls)
  (let ((threads (loop FOR url IN urls COLLECT
                   (sb-thread:make-thread   ; スレッド作成
                     (lambda ()
                       (tiny-http:request url))))))  ; 作成されたスレッドの中でHTTPリクエストを行う
    ;; (mapcar #'sb-thread:join-thread threads)の方が短い: 2009/12/16
    (loop FOR thd IN threads COLLECT
      (sb-thread:join-thread thd))))

;; 引数のurlリストに対して、逐次的にHTTPリクエストを行う関数
;; ※ 上との比較用
(defun http-request (urls)
  (loop FOR url IN urls COLLECT
    (tiny-http:request url)))

これの実行結果は次のようになった:

;; URLリストを準備  ※sbclのサイトを使わせてもらう
(defvar *urls* (loop repeat 10 collect "http://www.sbcl.org/"))

;;; 計時
;; まず逐次的な方
> (time (progn (http-request *urls*) 'done))
Evaluation took:
  3.818 seconds of real time   ; 約4秒
  0.004000 seconds of total run time (0.004000 user, 0.000000 system)
  0.10% CPU
  1,200 forms interpreted
  12,112,676,377 processor cycles
  933,080 bytes consed
--> DONE

;; 次に並列的な方
> (time (progn (parallel-http-request *urls*) 'done))
Evaluation took:
  5.390 seconds of real time   ; 約5.5秒: 逐次的なものより遅い?
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  0.00% CPU
  17,098,359,103 processor cycles
  945,232 bytes consed
--> DONE

見ての通り、HTTPリクエストを並列化している関数の方が、総処理時間が長くなってしまっている。
実際の処理時間は、その時のネットワークの調子などによって結構大きく前後するが、いずれにせよ当初期待していたように、並列化すればその分だけ速くなる、ということはなかった。

ボトルネック

最初の試みの上のような結果になったが、並列化しても少しも速くならないというのはいくらなんでもおかしいので、その原因を調べてみた。
結果、どうやらホスト名の名前解決がボトルネックになっているらしいことが判明した。
試しに、上の例のリクエストで投げているURLのホスト名部分をIPアドレスに置換して、同様の処理を実行してみる。

;; 'www.sbcl.org'のIPアドレスは'216.34.181.97' ※ hostsファイルを書き換える方法でも良い
(defvar *ip-urls* (loop repeat 10 collect "http://216.34.181.97/"))

;;; 計時
;; 逐次
> (time (progn (http-request *ip-urls*) 'done))
Evaluation took:
  4.617 seconds of real time   ; 約4.5秒
  0.004000 seconds of total run time (0.004000 user, 0.000000 system)
  0.05% CPU
  1,200 forms interpreted
  27,337,039,972 processor cycles
  934,832 bytes consed
--> DONE

;; 並列
> (time (progn (parallel-http-request *ip-urls*) 'done))
Evaluation took:
  0.406 seconds of real time   ; 約0.5秒: 速くなっている
  0.004000 seconds of total run time (0.004000 user, 0.000000 system)
  0.99% CPU
  1,285,470,726 processor cycles
  372,952 bytes consed
--> DONE

名前解決が不要なら、処理時間はほぼ期待通りに速くなっている。

理由は良く分からないが、sbclの名前解決関数(sb-bsd-sockets:get-host-by-name)*3は、(ホスト名を渡した場合)マルチスレッド環境で呼び出されるとブロッキング時間が長くなるらしい。※ ただし、各URLのホスト名が異なる場合には、マルチスレッドだからといって極端に遅くなることはなさそう
最初の例の場合は、全体の半分位のスレッドに対してはきびきび応答するのだが、残りのスレッドに対する応答は悪く、最長ではこの関数だけで5秒くらい掛かったりもしていた。

結論

とりあえず現時点での(暫定的な)結論:

  • HTTPリクエストを並列化すれば、総処理時間は短くなる
  • ただし、各リクエストのURLのホスト名に重複が多い場合は、名前解決のレスポンスが(何故か)遅くなるので、(例えばキャッシュを用いるなどして)名前解決処理が行われる回数を抑える工夫をプログラム側で行う必要がある
  • sbcl(linux+x86+sb-bsd-sockets+sb-threadの組み合わせ)以外でも同様の結果となるかどうかは未確認

*1:1は、シングルスレッドで処理した場合に、一つのHTTPリクエストが要する時間

*2:ほとんど使わないので確かではないが、drakmaでも大丈夫なはず

*3:sb-bsd-sockets:get-host-by-nameは、内部的にはPOSIXのgethostbyname及びgetaddrinfo関数を使用しているようなので、同じようにこれらの関数を利用している他の言語やcommon lisp実装でも、同様のことは当てはまるかもしれない。ただし、sbcl以外で検証はしていないので不明。