読者です 読者をやめる 読者になる 読者になる

アルパカDiary Pro

はてなブログProではありません

Redisのビットコマンドを用いた高速集計

Redis

Redisは様々な型をもっているので
単純な集計(increment)は結構柔軟にできたりします。


ですが、後から条件付きでクロス集計したい時があると思います。
Redisにはビット演算するコマンドがあるので
それを使っていろいろな集計をしてみました。

ビット関連コマンドリファレンス

GETBIT/SETBIT

Redis 2.2.0以降が必要。
ビットのオフセットに対してフラグを取得/設定します。

GETBIT key offset
SETBIT key offset value(1/0)
BITCOUNT

Redis 2.6.0以降が必要。
キーに対するビットカウントを取得します。

BITCOUNT key [start] [end] 
BITOP

Redis 2.6.0以降が必要。
複数のキーに対してビット操作を行うことが出来ます。
集計にはこの操作を使います。

BITOP operation(AND/OR/XOR) destkey key [key ...]
BITOP operation(NOT) destkey
BITPOS

Redis 2.8.7以降が必要。今回は利用しません。

BITPOS key bit [start] [end] 
簡易Example
127.0.0.1:6379> SETBIT keyA 1 1
(integer) 0
127.0.0.1:6379> SETBIT keyA 2 1
(integer) 0
127.0.0.1:6379> SETBIT keyA 3 1
(integer) 0
127.0.0.1:6379> SETBIT keyB 1 1
(integer) 0

127.0.0.1:6379> BITCOUNT keyA
(integer) 3  # keyA のカウント
127.0.0.1:6379> BITCOUNT keyB
(integer) 1  # keyB のカウント

127.0.0.1:6379> BITOP AND keyAandB keyA keyB
(integer) 1
127.0.0.1:6379> BITCOUNT keyAandB
(integer) 1  # keyAandB のカウント

127.0.0.1:6379> BITOP OR keyAorB keyA keyB
(integer) 1
127.0.0.1:6379> BITCOUNT keyAorB
(integer) 3  # keyAorB のカウント

127.0.0.1:6379> BITOP XOR keyAxorB keyA keyB
(integer) 1
127.0.0.1:6379> BITCOUNT keyAxorB
(integer) 2  # keyAorB のカウント

ユースケース1:日別集計

ここから具体的なシナリオを考えてみます。
2014/4/1-2014/4/3 に訪れたユーザ数をいくつかの軸で集計してみます。
キーを日別に分けておいて、後でBITOPで演算して集計します。
ビットのoffsetにはユニークユーザID(Integer)を指定します。

登録スクリプト:キーを「2014/4/1〜2014/4/3」に分け、1000ユーザを適当に登録
use strict;
use warnings;
use Redis;
use 5.10.0;

my $redis = Redis->new;

my @date = qw/
    visit:2014-04-01
    visit:2014-04-02
    visit:2014-04-03
/;


sub choice { $_[int(rand(scalar(@_)))] }

sub clear {
    $redis->del($_) for (@date);
}

sub setbit_all {
    for my $uid (1..1000) {
        $redis->multi();
        # 適当な確率でvisitする
        {
            # 4/1: 9割の確率でvisitさせる
            if(rand() < 0.9) {
                $redis->setbit($date[0], $uid, 1, sub {});
            }
            # 4/2: 5割の確率でvisitさせる
            if(rand() < 0.5) {
                $redis->setbit($date[1], $uid, 1, sub {});
            }
            # 4/3: 3割の確率でvisitさせる
            if(rand() < 0.3) {
                $redis->setbit($date[2], $uid, 1, sub {});
            }
        }
        $redis->exec();
    }
}

clear();
setbit_all();
集計スクリプト:日付でユーザ集計

A: では日別の結果をORで演算し、3日間全体のユニークユーザ数を集計しています。
B: では4/1と4/3をANDで演算し、2日間どちらも訪れたユニークユーザ数を集計しています。

use strict;
use warnings;
use Redis;
use 5.10.0;

my $redis = Redis->new;

# 集計する日付
my @date = qw/
    visit:2014-04-01
    visit:2014-04-02
    visit:2014-04-03
/;


sub p {
    my ($key) = @_;
    printf ("%s %d\n", $key, $redis->bitcount($key));
}

sub display {
    # 全部のbitcount
    p($_) for (@date);
    say '';

    # bitop
    # A: 3日間に訪れたユニークユーザ数合計
    $redis->bitop('OR', 'visit:total', @date);
    p('visit:total');
    say '';

    # B: 2014-04-01 / 2014-04-03 両方に訪れたユーザ数合計
    $redis->bitop('AND', 'visit:2day:total', 'visit:2014-04-01', 'visit:2014-04-03');
    p('visit:2day:total');
    say '';
}

display()

ユースケース2:クイズのユーザ集計

クイズを出題し、回答/正解したユーザ数などを集計します。
先程と同じく、ビットのoffsetにはユニークユーザID(Integer)を指定します。

登録スクリプト:キーを「クイズ+選択肢」に分け、1000ユーザを適当に登録

1ユーザに対して性別を登録し、さらに3つの問題をランダムで回答させています。

use strict;
use warnings;
use Redis;
use 5.10.0;

my $redis = Redis->new;

# 性別
my @genders = qw/man woman/;
# 質問に対する回答群
my @option1 = qw/
    answer:question1:optionA
    answer:question1:optionB
    answer:question1:optionC
/;
my @option2 = qw/
    answer:question2:optionD
    answer:question2:optionE
    answer:question2:optionF
/;
my @option3 = qw/
    answer:question3:optionG
    answer:question3:optionH
/;




sub choice { $_[int(rand(scalar(@_)))] }

sub clear {
    $redis->del($_) for (@genders, @option1, @option2, @option3);
}

sub setbit_all {
    for my $uid (1..1000) {
        $redis->multi();
        {
            # gender
            $redis->setbit(choice(@genders), $uid, 1, sub {});
            # 3つの問題にランダムで回答
            $redis->setbit(choice(@option1), $uid, 1, sub {});
            $redis->setbit(choice(@option2), $uid, 1, sub {});
            $redis->setbit(choice(@option3), $uid, 1, sub {});
        }
        $redis->exec();
    }
}

clear();
setbit_all();
集計スクリプト:正解したユーザの集計

各問題の正解を定義し、正解したユーザを集計します。
C: では全問正解したユーザを集計しています。
D: では男性の中で全問正解したユーザを集計しています。

use strict;
use warnings;
use Redis;
use Time::HiRes qw/gettimeofday tv_interval/;
use 5.10.0;

my $redis = Redis->new;

# 性別
my @genders = qw/man woman/;
# 質問に対する回答群
my @answers = qw/
    answer:question1:optionA
    answer:question1:optionB
    answer:question1:optionC
    answer:question2:optionD
    answer:question2:optionE
    answer:question2:optionF
    answer:question3:optionG
    answer:question3:optionH
/;

# 以下を正解とする
#   question1 > optionA
#   question2 > optionF
#   question3 > optionH
my @collect = qw/
    answer:question1:optionA
    answer:question2:optionF
    answer:question3:optionH
/;

sub p {
    my ($key) = @_;
    printf ("%s %d\n", $key, $redis->bitcount($key));
}

sub display {

    # 全部のbitcount
    p($_) for (@genders, @answers);
    say '';

    # bitop
    # C: 全問正解したユーザ
    $redis->bitop('AND', 'answer:all:correct', @collect);
    p('answer:all:correct');
    say '';

    # D: 男性の中で全問正解したユーザ
    $redis->bitop('AND', 'answer:man:all:correct', @collect, 'man');
    p('answer:man:all:correct');
    say '';
}

display()

性能評価

BITOPで集計した時の性能評価をしてみました。

環境
サーバ EC2
インスタンスタイプ c3.large
Redis 2.8.9
シナリオ:3000万人の集計

先ほどのユースケース2で「3000万人」登録し、BITOPで集計してみました。

結果ログ(Intervalを表示するように改修)
$ perl answer_summary.pl

------------------------------------
man count:14996246
woman count:15003754
answer:question1:optionA count:10003730
answer:question1:optionB count:10001089
answer:question1:optionC count:9995181
answer:question2:optionD count:9999537
answer:question2:optionE count:10002139
answer:question2:optionF count:9998324
answer:question3:optionG count:14998858
answer:question3:optionH count:15001142
------------------------------------

------------------------------------
answer:all:correct count:1667467
---- 0.006544(sec)

------------------------------------
answer:man:all:correct count:833621
---- 0.006825(sec)

BITOPの結果だけ見ると 6-7ms で終わっています。一瞬ですね。

まとめ

Redisのビットコマンドについて調査してみました。
単純なビット操作なので使い所は限られると思いますが、
Redisだけで高速な集計をしたい場合には有用ではないでしょうか。