続・最速IPアドレスマッチ研修会B!

前置き

CasualTrackの第一日目、kazeburoさんの「最速IPアドレスマッチ研修会」を読んで触発され、より最速な高みを目指し、作成したモジュール「Net::IP::Match::Trie」を紹介します。

本題

正確にいうと、「作った」のではなく、mod_cidr_lookupというApacheモジュールを「ポーティング」しました。

Net::IP::Match::* 系のCPANモジュールには、様々なデータ構造、探索方法の実装があるのですが、今回のお題の「Net::IP::Match::Trie」は、その名に冠しているようにTrie(トライ木)というデータ構造を採用しています。

Trieについての解説は、

などを参照していただくとして、ここでは、他の Net::IP::Match::* 系の実装と比べて、Net::IP::Match::Trieがどのような特徴を持っているか書いてみたいと思います。

まずはベンチマーク

kazeburoさんの記事のベンチマークスクリプトをベースにして、ベンチマークをとってみました。(ベンチマークスクリプトは、 http://github.com/hirose31/p5-net-ip-match-trie/blob/master/samples/benchmark/benchmark.pl にあります)

ベンチマークスクリプトの変更点は以下の通りです。

  • Net::IP::Match::Trieを追加
  • Net::IP::Match::XS2を追加
  • 検査の母データとなるCIDRを155個に増量

Net::IP::Match::Trie は XS 版と Pure Perl 版があるので、それぞれでベンチマークをとりました。結果はこうなりました:

$ ./samples/benchmark/benchmark.pl
155
Net::IP::Match::Trie::XS
            (warning: too few iterations for a reliable count)
              Rate     cidr  regexp patricia       xs      bin      xs2     trie
cidr       44643/s       --    -67%     -71%     -77%     -92%     -93%     -97%
regexp    134529/s     201%      --     -11%     -31%     -77%     -78%     -90%
patricia  151515/s     239%     13%       --     -22%     -74%     -76%     -88%
xs        194805/s     336%     45%      29%       --     -66%     -69%     -85%
bin       576923/s    1192%    329%     281%     196%       --      -8%     -56%
xs2       625000/s    1300%    365%     312%     221%       8%       --     -52%
trie     1304348/s    2822%    870%     761%     570%     126%     109%       --

$ env NIMT_PP=1 ./samples/benchmark/benchmark.pl
155
Net::IP::Match::Trie::PP
             Rate     cidr   regexp patricia       xs     trie      bin      xs2
cidr      40323/s       --     -69%     -74%     -80%     -82%     -93%     -93%
regexp   128205/s     218%       --     -16%     -36%     -42%     -79%     -79%
patricia 152284/s     278%      19%       --     -24%     -31%     -75%     -75%
xs       201342/s     399%      57%      32%       --      -9%     -66%     -66%
trie     220588/s     447%      72%      45%      10%       --     -63%     -63%
bin      600000/s    1388%     368%     294%     198%     172%       --      -0%
xs2      600000/s    1388%     368%     294%     198%     172%       0%       --

XS版はダントツで最速、Pure Perl版もPure Perlな実装の間では最速という結果がでました。

入力CIDR数と、セットアップとマッチ処理時間の関係

さて、「最速」というのはわかったのですが、Net::IP::Match::Trieがどのような「特徴」をもっているかというのはこれだけではわかりません。ですので、もうひとつ、ベンチマークスクリプトを走らせてみたいと思います。

ベンチマークには、Net::IP::Match::Regexp に含まれる speedtest.pl を改変したものを使いました。(スクリプトは、 http://github.com/hirose31/p5-net-ip-match-trie/blob/master/samples/benchmark/speedtest.pl にあります)

結果はこうなりました。("Networks:"は、探索母データとなるCIDRの数です)

$ ./samples/benchmark/speedtest.pl
Initialization time of test: 0.032882

Networks: 1, IPs: 10000
Test name              | Setup time | Run time | Total time | Errors
-----------------------+------------+----------+------------+--------
simple                 |    0.000   |  0.058   |    0.058   | n/a
Net::IP::Match::XS     |    0.000   |  0.015   |    0.016   | 0
Net::IP::Match::Regexp |    0.001   |  0.072   |    0.072   | 0
Net::IP::Match::Trie   |    0.000   |  0.022   |    0.022   | 0

Networks: 10, IPs: 10000
Test name              | Setup time | Run time | Total time | Errors
-----------------------+------------+----------+------------+--------
simple                 |    0.000   |  0.085   |    0.085   | n/a
Net::IP::Match::XS     |    0.000   |  0.022   |    0.022   | 0
Net::IP::Match::Regexp |    0.001   |  0.091   |    0.093   | 0
Net::IP::Match::Trie   |    0.000   |  0.023   |    0.023   | 0

Networks: 100, IPs: 10000
Test name              | Setup time | Run time | Total time | Errors
-----------------------+------------+----------+------------+--------
simple                 |    0.000   |  0.371   |    0.371   | n/a
Net::IP::Match::XS     |    0.000   |  0.084   |    0.084   | 0
Net::IP::Match::Regexp |    0.010   |  0.098   |    0.107   | 0
Net::IP::Match::Trie   |    0.001   |  0.022   |    0.024   | 0

Networks: 1000, IPs: 10000
Test name              | Setup time | Run time | Total time | Errors
-----------------------+------------+----------+------------+--------
simple                 |    0.002   |  2.784   |    2.786   | n/a
Net::IP::Match::XS     |    0.001   |  0.647   |    0.648   | 0
Net::IP::Match::Regexp |    0.090   |  0.103   |    0.193   | 0
Net::IP::Match::Trie   |    0.064   |  0.023   |    0.087   | 4

この結果から読み取れることはこんなところでしょうか:

  • Net::IP::Match::XS
    • API的に、セットアップ処理がなくマッチ処理のみの実装になっている
    • マッチ処理はそれほど高速ではない
  • Net::IP::Match::Regexp
    • 入力CIDR数の増加によりセットアップ時間が線形に増加するので、少ないうちはいいが多くなると注意
    • マッチ処理に要する時間も徐々に増加した
  • Net::IP::Match::Trie
    • 入力CIDR数の増加によりセットアップ時間も増加する
    • 一方、Trieの特長により、マッチ処理時間はまったく変わらない (CIDR数が増加しても一定)

ちなみに、最後の結果で Net::IP::Match::Trie の Errors の項が非ゼロですが、これは、Net::IP::Match::Trie はマッチするCIDRが複数ある場合には、ネットワークアドレスが一番長い(=ネットマスクが一番短い)ものを返す実装になっているのに対し、ほかのものはそういう実装になっていないからです。

たとえば、

$matcher->add("big"   => [qw(10.0.0.0/8)]);
$matcher->add("small" => [qw(10.6.25.0/24)]);
say $matcher->match_ip("10.6.25.1");

の結果は、最初に add した "big" ではなく、より限定的(ネットワークアドレスが長い=ネットマスクが短い)なCIDRである "small" になります。

まとめ

  • Net::IP::Match::Trieは、
    • 一度だけ、かならずセットアップ処理が必要です
    • マッチ処理は最速です (少なくとも今回比較した中では)
    • また、Trieの特長により、探索母データのCIDRの数がとっても多くなっても、常に一定の速度で結果を返せます
    • 一回のマッチ処理で、ラベル付けしたいずれかのCIDRにマッチするかどうかがチェックできます
      • 例: 「このIPアドレスは、どの携帯電話キャリア(DoCoMo、au、Softbank、willcom)のものか？」というのが、Net::IP::Match::XSやNet::IP::Match::Regexpではキャリアの数の分だけマッチ処理が必要ですが、Net::IP::Match::Trieなら一発でわかります。
  • よって、Net::IP::Match::Trie は、このような用途に向いています:
    • そのライフサイクルの中で、初期セットアップの回数より、マッチ処理の回数の回数が圧倒的に多い
    • CIDRの変化が頻繁にはない
      • 例: daemon的な比較的長寿のサーバプロセスとか
  • 最後に。Advent Calendarのおかげで、Net::IP::Match::Trie というモジュールを作るきっかけを得ることができました！ ありがとうございました！ Happy SUSHI!!!

というわけで今日はここまでです。明日は lestrrat さんです。

Mon, 14 Dec 2009 11:23:01 GMT  |  Index