大規模なデータをそれなりに効率良く計数できる Algorithm::LossyCount を書いた

要旨

Algorithm::LossyCount というモジュールを書きました。これを使うとそこそこメモリ効率良く大規模なデータの計数ができます。アクセスランキング集計とかに使えるんじゃないでしょうか。

• Github
• MetaCPAN

動機

例えばブログホスティングサービスで HTTP サーバのアクセスログを集計して人気のあるブログ記事ランキングを出したいとします。
Perl でデータの出現頻度を計数するのはハッシュを使うのが鉄板なので、適当に書くとだいたいこんな感じのコードになると思います:

#!/usr/bin/env perl

use v5.18;

my %access_counts;
while (<>) {
    chomp;
    my $access_log = parse_access_log($_);
    next if is_article_request($access_log);
    ++$access_counts{$access_log->{requested_article}};
}

my @popular_articles = (
  sort { $b->[1] <=> $a->[1] }
  map { [ $_ => $access_counts{$_} ] } keys %access_counts
)[0 .. 49];

say "Rank\tURL\tFreq.";
for my $i (0 .. $#popular_articles) {
  say join "\t", $i + 1, @{ $popular_articles[$i] };
}

sub is_article_request { ... }

sub parse_access_log { ... }

シンプルですね。
しかしブログの記事数はサービス全体で数千万から数億のオーダになります。一定期間に全記事にアクセスがあるわけではないにしろ、逐次計数していくとハッシュのキーが数千万件になってメモリが貧弱なマシンだと残念なことになります。
ところで Web ページのアクセス傾向に関しては Zipf の法則1が当てはまることが知られています。要するにアクセス数でソートしたグラフはロングテールで、超人気記事がごく少数あり、急激に坂を下ってほとんどアクセスのない記事がズラーッと並ぶグラフになります。 つまり計数ハッシュの中には低頻度で同順位のデータが大量に存在していることになります。集計したところで下位の順位なんか誰も見ないので無駄です。
こういうロングテールな大規模なデータが対象で、低頻度データの計数結果が多少不正確でも構わないような場合にメモリ効率良く計数するための近似アルゴリズムが Lossy-Counting2 です。 このアルゴリズムは入力が一定数追加される毎に低頻度データの計数結果を捨てていきます。高頻度データの計数結果はパラメータによりますが確率的にまず捨てられないので上位の結果は信頼でき、下位の低頻度データはナンヤカヤ・ウヤムヤにされます。

使い方

上記の例でハッシュを使っている箇所を Algorithm::LossyCount に置き換えるだけ。

#!/usr/bin/env perl

use v5.18;
use Algorithm::LossyCount;

my $counter = Algorithm::LossyCount->new(max_error_ratio => 0.005);
while (<>) {
    chomp;
    my $access_log = parse_access_log($_);
    next if is_article_request($access_log);
    $counter->add_sample($access_log->{requested_article});
}

my $access_counts = $counter->frequencies;
my @popular_articles = (
  sort { $b->[1] <=> $a->[1] }
  map { [ $_ => $access_counts{$_} ] } keys %$access_counts
)[0 .. 49];

say "Rank\tURL\tFreq.";
for my $i (0 .. $#popular_articles) {
  say join "\t", $i + 1, @{ $popular_articles[$i] };
}

add_sample メソッドにデータを渡すと対応するカウンタに1加算したことになります。frequencies メソッドで計数の結果がハッシュリファレンスとして返ります。 詳細は例によって perldoc 参照。

感想

状態を持ったオブジェクトは面倒くさかったです (小並感)。
Algorithm::LossyCount 0.02 で依存関係に Smart::Args が入っていますが消し忘れです。他に変更が無ければ来週にでも 0.03 をリリースします。

---

1. ジップの法則 - Wikipedia ↩
2. Manku, Gurmeet Singh, and Rajeev Motwani. "Approximate frequency counts over data streams." Proceedings of the 28th international conference on Very Large Data Bases. VLDB Endowment, 2002. ↩