今回のエンジニアブログを担当する原です。

このエントリでは、Sorted Setからランダムに要素を選択する方法をサンプルコードとともにご紹介します。

要約

Redisにはランダムな要素を集合(Set)から取得するためのsrandmemberというコマンドがありますが、
Sorted Setにはそのようなコマンドは用意されていません。

以下の手順でSorted SetからSetに要素を移動し、結果のSetに対してsrandmemberを実行することで、要件を満たします。

1. zrangebyscore と zrevrangebyscoreで限定したランクの範囲内からランダムでランクを選択
2. そのランクを中心値とする範囲n件数分をzrangeで取得し、結果をSetに格納

背景

ゲームやWebサービスに限らず「特定条件を満たす部分集合からランダムに要素を選択する」という要件はたまにありますが、集合の要素数が大量である場合にその処理がサービスのボトルネックになることもよく見受けられます。

多少のデータであればRDBのデータに対してもSQLクエリを工夫すれば何とかなりますが、RDBの実装では、この「ランダム」という要件を満たしつつパフォーマンスを担保するのは非常に難しい。

RDBのパフォーマンス向上において、計算量を一定に保つ・ディスクIOを減らす目的で「キャッシュを如何に効かせるか」という設計課題があり、統計情報や実行計画・クエリ結果のキャッシュを各RDB製品が実装しています。

結果、検索結果にランダム性を持たせようとしても結果が一定になる、SQLクエリで頑張って無理にランダム性を持たせようとしてフルスキャンが走ってレスポンスが遅くなる、などの悪影響を与えることがあります。

上記の要件を満たすためには、キャッシュが効かなくてもある程度のパフォーマンスが出るストレージを選択する必要があります。また、「ランダムな要素を集合から取得する」というコマンド（命令）がデフォルトで用意されているとなお良いでしょう。

これらの機能要件を満たすストレージとして、インメモリKVSのRedisが該当します。

Redisはキャッシュサーバとして利用されることもあるほど高速です。また、「集合からランダムな要素を選択する」コマンドであるsrandmemberは選択する要素数Nに対しての 計算量がO(N) であるため、集合の要素数がレスポンスタイムに影響を与えません。

しかし、Redisの集合(Set)は単なる値の集合であるため、「特定条件を満たす部分集合からランダムに要素を選択する」要件をそのまま適用できません。

そこで、順序付き集合（Sorted Set）で特定条件を満たすかを判定し、条件を満たした部分集合をSetに保存、そこからsrandmemberでランダムに要素を選択することにします。

以降で、そのサンプルコードとその解説をしていきます。

前提

• Redis 2.8.9
• Python 3.3.3

（Macで）homebrew + pyenv + virtualenv導入済みであれば以下のコマンドですぐに環境が整います。

$ brew install redis
$ pyenv install 3.3.3
$ pyenv virtualenv 3.3.3 redis_sample
$ pyenv local redis_sample
$ pip install redis

以下のコマンドで、ローカルでRedisのサーバーを起動しておきましょう。
（デフォルトでポート6379を利用します）
$ redis-server /usr/local/etc/redis.conf

サンプルコード

# -*- coding: utf-8 -*-  
import sys
import random
import redis

client = redis.Redis(host='127.0.0.1', port=6379, db=0)

# 特定条件付き要素を持つSorted setのキー名  
SRC_KEY = 'sources'

# 最終結果の上位集合(Set)のキー名  
DIST_KEY = 'distination'

def select_random_list(base_score, rank_range, score_range, count):
    """  
      base_score±score_rangeの範囲からランダムにランクを選択、  
      そのランクを中心値とする範囲±score_range件分の要素から、  
      count件分の要素をランダムに選択する。  
    """

    # 1  
    min_score = base_score - score_range
    max_score = base_score + score_range

    min_score_player = client.zrangebyscore(SRC_KEY, min_score, max_score, start=0, num=1)
    min_rank = client.zrank(SRC_KEY, min_score_player[0])

    max_score_player = client.zrevrangebyscore(SRC_KEY, max_score, min_score, start=0, num=1)
    max_rank = client.zrank(SRC_KEY, max_score_player[0])

    # 2  
    selected_rank = random.randint(min_rank, max_rank)
    id_list = client.zrange(SRC_KEY, selected_rank - rank_range, selected_rank + rank_range)

    # 3  
    client.delete(DIST_KEY)
    client.sadd(DIST_KEY, *id_list)

    # 4  
    return client.srandmember(DIST_KEY, number=count)

if __name__ == '__main__':

    base_score = 25
    rank_range = 20
    score_range = 5
    count = 5

    # 5  
    client.delete(SRC_KEY)
    with client.pipeline() as p:
        for player_id in range(0, 50000):
            level = random.randint(0, 100)
            p.zadd(SRC_KEY, player_id, level)
        p.execute()

    results = select_random_list(base_score, rank_range, score_range, count)
    print(results)

# 1

基準のスコアからscore_range分の最小スコアと最大スコアを「特定条件付き要素を持つSorted Set（以下、条件集合S）」から取得、それぞれのランク（Sorted Set内での順位）を取得します。

zrangebyscoreとzrevrangebyscoreの違いに注意してください。
Sorted Setではスコアの昇順にランクが振られます。最小スコアのランクにはzrangebyscoreによってランクの最小値を、最大スコアのランクにはzrevrangebyscoreによってランクの最大値を採用しています。

# 2

1で取得したランクの最小値と最大値の範囲内で、任意のランクをランダムに一つ選択します。

そして、条件集合Sから、そのランダムに選択したランクを中央値とした範囲の要素をzrangeで取得します。
この結果が、最終的にランダムで選択する結果集合の上位集合（以下、上位集合D）です。

# 3

上位集合DとなるSetをRedisに保存します。
一応解説しておくと、 *id_list はPythonにおけるリストの引数展開です。
そのまま渡してしまうと、リスト自体が一要素として保存されてりますので注意しましょう:)

# 4

上位集合Dから、ランダムで要素を選択します。
前述したとおり、count分だけの計算量で済みます。
このサンプルコードの関数では、関数呼び出しごとに条件集合Sから上位集合Dを求めていますが、
実際は条件集合Sから上位集合Dを求める処理と、上位集合Dからランダムに要素を取得する処理は分離すると思います。

# 5

サンプルデータを用いて、条件集合Sを生成しています。
実際のプロダクトでは、バッチ処理等で生成することが多いでしょう。¹

上記のソースをsample.pyで保存した場合、以下のコマンドで実行できます。

$ python sample.py

base_scoreなどを値を変更して結果の変化を確認すると、処理内容への理解がより深まると思います。

まとめ

「特定条件を満たす部分集合からランダムに要素を選択する」要件を、RedisのSorted Setを用いて満たす方法をご紹介しました。
Redisを始めとするKVSやNoSQLデータストアは、RDBでのデータモデリングとは全く別の設計手法が求められます。
最初のうちは取っ付きづらかったり、用途が分からないこともあったりするのですが、その特徴を理解・上手く活用することで、今までは力技で解決していた問題がよりエレガントに解けるようになるでしょう。

Redisに興味のある方には、「Redis入門 インメモリKVSによる高速データ管理」という本をオススメします。
入門的な内容に加え、問題解決の事例も多く記載されており、非常に参考になります。