Redisでスコアを複数設定できるランキングを作ってみた

ランキングを作っているとスコアを複数設定したいことがよくあると思います。例えば「得点が同じだったら早くその得点を出した人優先」とか「勝ち点が同じだったら得失点差が大きい方優先」とかのように、最初の基準で順位を決められなかった場合の第二基準が欲しいみたいな場合です。

ランキングを作るのにはRedisのSorted Setを使うのが便利ですが、残念ながらSorted Setはひとつしかスコアを設定できません。少し前にどうやったら実装できるかと社内チャットで話題に上ったので、試しにRedis::LeaderBoardMulti(仮名)という名前で書いてみました。

shogo82148/p5-Redis-LeaderBoardMulti

使い方

メソッドの名前はRedis::LeaderBoardにあわせてありますが、スコアが複数指定できるようになった関係でちょっと変わってます。

use Redis;
use Redis::LeaderBoard;
my $redis = Redis->new;
my $lb = Redis::LeaderBoardMulti->new(
    redis => $redis,
    key   => 'leader_board:1',
    order => ['asc', 'desc'], # asc/desc, desc as default
);
$lb->set_score('one' => 100, time); # 第二基準は時間=得点が同じだったら早くその得点を出した人優先
$lb->set_score('two' =>  50, time);
my ($rank, $score, $time) = $lb->get_rank_with_score('one');

set_scoreの第二引数以降はすべてスコアとして扱われます。(そのためRedis::LeaderBoardと互換性はない) 上の例では「得点が同じだったら早くその得点を出した人優先」になってます。

制限事項

実装の都合により、以下のような制限があります。

スコアはすべて64bit符号付き整数です
- Redis::LeaderBoardのスコアは倍精度浮動小数点型なので小数も扱えるが、Redis::LeaderBoardMultiは整数だけ
Redis 2.8.9以降のみで動きます

実装の仕組み

Sorted Setの同じスコアを持つメンバーは辞書順にソートされます(zaddの同じスコアを持つ要素の項を参照)。例えば以下の様にメンバー「a」「b」「c」を追加すると、必ず「abc」の順番になることが保証されています。

127.0.0.1:6379> ZADD ranking 0 "a" 0 "b" 0 "c"
(integer) 3
127.0.0.1:6379> ZRANK ranking "b"
(integer) 1

これを利用して、メンバーの先頭にスコアをエンコードして付けておきます。もちろんエンコードしたあとでもスコアの大小関係が保たれている必要があります。以下はエンコード方式にビッグエンディアンの16bit整数を使った例です。 Redis 2.8.9から辞書順比較に特化したコマンド(LEXがつくやつ)が追加されているので、ランクを求める処理は以下のように書くことができます。

127.0.0.1:6379> ZADD ranking 0 "\x00\x02b"    (bをスコア2で追加)
(integer) 1
127.0.0.1:6379> ZADD ranking 0 "\x00\x01a"    (aをスコア1で追加)
(integer) 1
127.0.0.1:6379> ZLEXCOUNT ranking - "(\x00\x02"    (スコア2未満の個数=bのランク)
(integer) 1

さすがに16bit符号なし整数だと範囲が狭いので、実際の実装は以下のようになっています。

エンコードはビッグエンディアンの64bit符号付き整数
負数も扱えるように下駄を履かせる
- 1と-1を単純にエンコードすると-1の方が大きくなってしまう
- 0x8000000000000000を足して符号なし整数の範囲で比較できるように補正

アトミック性について

この方法だとSorted Setだけでは現在のスコアを取得できないので、スコアだけ別管理にする必要があります。スコアの更新とランキングの更新があるので、片方だけ更新される状況がないようにアトミック性に注意する必要があります。更新途中の間違った結果を返すだけならすぐに復旧するのでまだマシですが、途中でネットワーク障害が起こって不整合なデータが残ってしまうと面倒です。

アトミック性を確保するためのパターンをいくつか実装してみました。 use_scriptとuse_hashで制御が可能です。

トランザクションを使った方法

Redisにはトランザクションの仕組みがあるのでこれを使った方法です。 use_script=>0が指定されるとこの方法で更新を行います。

127.0.0.1:6379> WATCH ranking:a   (他のクライアントが更新を行っていないか監視)
OK
127.0.0.1:6379> GET ranking:a   (ranking:aに入っている現在のスコアを取得)
"\x00\x01"
127.0.0.1:6379> MULTI
OK
127.0.0.1:6379> ZREM ranking "\x00\x01a"
QUEUED
127.0.0.1:6379> ZADD ranking 0 "\x00\x03a"
QUEUED
127.0.0.1:6379> SET ranking:a "\x00\x03"
QUEUED
127.0.0.1:6379> EXEC   (スコアの更新とランキングの更新をアトミックに行う)
1) (integer) 1
2) (integer) 1
3) OK

Redisのトランザクションは楽観的ロックなので、他のクライアントがスコアを更新していると失敗する場合があります。失敗した場合はリトライが必要です。 (この機構、いろいろと注意点があって毎回実装するのはつらすぎるので、別モジュールとして分離したいけど、いい名前とインターフェース募集中)

use_hash=>1が指定されていると、スコアの記録にHashを使います。「Hashの特定のキーの更新をWATCHする」という命令はないため、ランキング全体をWATCHで監視します。 (use_hash=>0の場合、そのメンバのスコアだけ監視する)

Luaスクリプトを使った方法

RedisはLuaスクリプトを実行する機能があります。 Luaスクリプト実行中は他の命令の実行をブロックするので、アトミック性が確保されます。

local s=redis.call('GET', 'ranking:a')
if s then
  redis.call('ZREM', 'ranking', s..'a')
end
redis.call('ZADD', 'ranking', 0, '\x00\x03a')
redis.call('SET', 'ranking:a', '\x00\x03')

Luaスクリプトを実行するにはEVALとEVALSHAの二種類のコマンドがあります。 EVALSHAは転送量を抑えられて便利ですが、事前にSCRIPT LOADで使うスクリプトを登録しておく必要があります。 (ココらへんも別モジュールに分離したいけど、いい名前とインターフェース募集中) use_evalshaオプションでどちらを使うか制御可能です。

ちなみにEVALで実行したスクリプトも永遠にキャッシュされるらしいです。上の例はわかりやすいようにキー名や値を直接埋め込んでいますが、同じことをしようとLuaスクリプトの動的生成なんてすると死にます。スクリプト内でKEYSやARGVを使うとEVAL時にパラメータを渡せるようになるので、これを活用しましょう。

諦める

Redis::LeaderBoardの実装を見て気がついたんですが、 get_rankの実装は「スコアの取得」「スコアに対応するランクの取得」がアトミックでないため、以下の条件を満たすと実際のランクより1大きい結果を返します。

同じメンバーのスコア更新とランク取得が同時に行われる
ランクが上がるようにスコアが更新される

確かに厳密性は欠けますがたかだか1結果が変わるだけですし、そもそも更新と取得が同時に行われないようにモジュールを使う側が排他制御するべきですね。こういうケースでは諦めるというのも一つの手かなと思いました。もちろんデータの整合性が壊れる場合は頑張ってアトミック性を確保するべきでしょう。

まとめ

Redisでランキングをつくる際に、スコアを複数設定する方法を紹介しました
アトミック性を確保する方法を紹介しました
- トランザクションを使った方法
- Luaスクリプトを使った方法
- 諦める

もうちょっとドキュメントを整備したらCPANにあげてみますかね。トランザクション管理・Luaスクリプト管理も分離したい(いい名前を思いついたら)。「こんな名前がいい！」「こんなインターフェースがいい！」等あればコメントください。