Sorted Set

スコアランキングはむつかしい。

数万人がリアルタイムにランキングを見に来るサービスで、RDBMSのORDER BYは使えない。上位100人はLIMITで取れるが、厄介なのは「自分の順位」だ。全体の中で自分が何位かを出すには全件ソートが要る。こういうときのベストプラクティスは、RedisのSorted Setを使うことだ。スコアと一緒にメンバーを突っ込めば、スコア順で保持してくれる。自分の順位もO(log N)で取れる。

同点の扱いは定番の課題だ。同じスコアだとメンバー名の辞書順で並ぶ。同点なのに順位が違う。スコアの小数点以下にUNIXタイムを仕込んで、先に到達したほうが上位になるようにする。力技だが動く。逆に、同点を同じ順位としてまとめたい場合はSorted Setだけでは対応できない。別途集計が要る。

RedisとMemcachedはよく比較されるが、特性がかなり違う。Redisはシングルスレッドだ。マルチコアを活かすにはシャーディングが要る。メモリもバックアップ時にforkするため、実質的に半分しか使えない。データ構造は豊富で、文字列だけでなくハッシュ、リスト、セット、Sorted Setがある。永続化もできる。KVSというよりデータストアそのものだ。

Memcachedはマルチスレッドで、純粋なKVSに徹している。slab allocatorでメモリを管理する。固定サイズのチャンクに分けて、近いサイズのデータを同じスラブに入れる。スラブのサイズ分布がデータと合っていないと、特定のスラブだけ溢れて他はスカスカになる。メモリは余っているのにevictionが走る。とはいえMemcachedの設計はシンプルで、その分速い。昔はスラブのウォームアップなんてこともやっていたが、もう誰もやっていないだろうか。

AWSにElastiCacheとしてRedisとMemcachedの両方のマネージドサービスがあるのは、用途が違うからだ。セッションストアや単純なキャッシュならMemcachedで十分だし、マルチスレッドで効率がいい。データ構造や永続化が要るならRedis。この性能特性の違いを説明できる若手は少なくなってきた。