Redis の Sorted Sets でランダムにメンバーを取得する

17516 ワード
Redis Ruby Ruby テキストリンク

Happy Elements 株式会社 カカリアスタジオ Advent Calendar 2016 19日目の記事です。

概要

自分の所属チームのアプリではユーザーランキングの実装に Redis の Sorted Sets を使用しています。Redis についての基本的な解説は別の記事に譲り、この記事ではそのスクリプティング機能（EVAL コマンド）を使った実装について紹介します。

Sorted Sets でランダムにメンバーを取得する

以下のような状況を考えます。（架空の設定です）

100万人のユーザーがそれぞれ自分のスコアを持っており、それによってリアルタイムにランキングされています。スコアはユーザー同士のバトルによって変化します。例えば自分より大きなスコアのユーザーに勝利すれば自分のスコアが大きく加算され、小さなユーザーに勝利すれば小さく加算されます。対戦相手の選択には自分と同程度のスコアをもったユーザーを選択するのが望ましく、また、毎回同じ相手とならないように、自分を中心とした一定のスコアの範囲からランダムに候補を選択したいとします。1

Redis の Sorted Sets によってランキングを実装しているため、対戦相手のマッチングにもそれを利用したいです。しかし、Sorted Sets には要素をランダムに取り出すコマンド（ Sets における SRANDMEMBER みたいなやつ）が無いため、自分で実装する必要があります。

実験のセットアップ

Redis に接続するクライアントには redis-rb を使用します。100万人のユーザーにランダムなスコアを持たせて Sorted Sets に追加し、Ruby による実装、EVAL コマンドと Lua による実装 をそれぞれ行い、性能を比較します。実装するのは以下のメソッドです。あるスコアと、それを中心としたスコアの範囲を指定することで、そこにいる対戦相手の候補をランダムに選択します。

# redis: Redisクライアント
# target_score: 対戦相手を探しているユーザーのスコア
# score_range: target_score を中心とするスコアの範囲
# count: 対戦相手の候補として取り出すユーザー数
def get_random_members(redis, target_score, score_range, count)
end

実験内容は以下の2通りをそれぞれ10回計測し、その平均値を比べてみます。
・1万人を1度に取り出す場合
・5人ずつ2000回に分けて取り出す場合

Redis サーバーはローカルではなく AWS の ElastiCache を使用しました。（後で触れますが EVAL コマンドによる通信のオーバーヘッドの減少を確認したかったためです。）クライアントは EC2 インスタンス上でスクリプトを実行しました。以下がスクリプトの全体像です。

require "redis"
require 'benchmark'
require 'uri'

KEY = "myzset"

# Sorted Sets に100万人のユーザーを追加する
def setup(redis)
  unless redis.exists(KEY)
    lua_script = <<-EOS
      for id = 0, 1000000 - 1, 1 do
        local member = 'user_' .. id
        local score = math.random(10000)
        redis.call('zadd', KEYS[1], score, member)
      end
    EOS
    redis.eval(lua_script, [KEY], [])
  end
end

# 指定した回数の平均を計測する
def benchmark(measure_count, title)
  Benchmark.benchmark(Benchmark::CAPTION, 5, Benchmark::FORMAT, title) do |x|
    tms = []
    measure_count.times do |i|
      tms << x.report(i.to_s) { yield }
    end
    [tms.inject(:+) / measure_count]
  end
end

def get_random_members(redis, target_score, score_range, count)
  # ここを実装する
end

uri = URI.parse("redis://your-elasticache-endpoint.amazonaws.com:6379")
redis = Redis.new(host: uri.host, port: uri.port)
# redis = Redis.new(host: "127.0.0.1", port: 6379, :db => 0)

setup(redis)

target_score = 5000
score_range = 100
measure_count = 10

benchmark(measure_count, "ケース1") { get_random_members(redis, target_score, score_range, 10000) }
benchmark(measure_count, "ケース2") { 2000.times { get_random_members(redis, target_score, score_range, 5) }}

環境

  • ElastiCache Redis 3.2.4, cache.r3.large
  • EC2 t2.micro
  • Ruby 2.2.1
  • redis-rb 3.3.x

Ruby による実装

ZRANGEBYSCORE と ZREVRANGEBYSCORE によって対象範囲のスコアにおける最初のユーザーと最後のユーザーを取り出しています。また、ZRANK によってそれらのユーザーのランクを取得し、最後に、指定した人数のユーザーをランダムに取り出しています。2

def get_random_members(redis, target_score, score_range, count)
  members = []
  first_score = target_score - score_range / 2
  first_member = redis.zrangebyscore(KEY, first_score, "+inf", limit: [0, 1])
  first_rank = redis.zrank(KEY, first_member)
  last_score = target_score + score_range / 2
  last_member = redis.zrevrangebyscore(KEY, last_score, "-inf", limit: [0, 1])
  last_rank = redis.zrank(KEY, last_member)
  count.times do
    rank = first_rank + rand(last_rank - first_rank + 1)
    member = redis.zrange(KEY, rank, rank)
    members << member
  end
  return members
end

Ruby による実装の欠点として以下の2つが挙げられます。ユーザー数やウェブサーバー数が多い場合はどちらも悩ましい問題です。

  • 各 Redis コマンドを実行するたびにサーバーとのやりとりが発生するためオーバーヘッドが大きい
  • クライアントが複数存在する場合、スクリプトの途中でサーバーの状況が変化し得る

EVAL と Lua による実装

上記の欠点は EVAL コマンドによって解消できます。今回は以下のように実装してみました。 

def get_random_members(redis, target_score, score_range, count)
  rseed = Time.new.to_f
  lua_script = <<-EOS
    local key = KEYS[1]
    local target_score = ARGV[1]
    local score_range = ARGV[2]
    local count = ARGV[3]
    local members = {}
    local first_score = target_score - math.floor(score_range / 2)
    local first_member = redis.call('zrangebyscore', key, first_score, '+inf', 'limit', 0, 1)[1]
    local first_rank = redis.call('zrank', key, first_member)
    local last_score = target_score + math.floor(score_range / 2)
    local last_member = redis.call('zrevrangebyscore', key, last_score, '-inf', 'limit', 0, 1)[1]
    local last_rank = redis.call('zrank', key, last_member)
    math.randomseed(ARGV[4])
    for i = 0, count - 1, 1 do
      local rank = first_rank + math.random(last_rank - first_rank + 1)
      local member = redis.call('zrange', key, rank, rank)
      table.insert(members, member)
    end
    return members
  EOS
  return redis.eval(lua_script, [KEY], [target_score, score_range, count, rseed])
end

やっていることは Ruby による実装とほぼ同じですが、Redis とやりとりする部分を Lua で記述し、EVAL コマンドに引数として渡しています。これにより、サーバーとのやりとりを一度で済ませることができ、通信のオーバーヘッドを削減できます。また、EVAL コマンドの実行中は他のコマンドが割り込まないため、サーバーの状態がスクリプトの途中で予期せず変化することはありません。3

速度比較

  • Ruby による実装
            user     system      total        real
ケース1    0.675000   0.092000   0.767000 (  3.186102)
ケース2    0.547000   0.129000   0.676000 (  2.801824)
  • EVAL と Lua による実装
            user     system      total        real
ケース1    0.070000   0.000000   0.070000 (  0.116453)
ケース2    0.148000   0.000000   0.148000 (  0.428765)

上記のように、どちらのケースにおいても EVAL と Lua による実装の速さが上回っています。ケース1では、Ruby による実装だと指定した人数分だけ Redis とやりとりする必要があったのに対し、EVALによる実装では1度で済んでいるため、ケース2と比べて大きな差となっています。4
ケース2は実際の用途に近いものですが、それでもなお大きな差があります。

まとめ

Sorted Sets でランダムにメンバーを取得する方法について、Ruby による実装と EVAL と Lua による実装を比較しました。他の用途においても EVAL コマンドを使うことで高速化を図れるかもしれないので、一度検討してみてはいかがでしょうか。

なお、今回は取り上げませんでしたが EVALSHA というコマンドもあります。これは EVAL コマンドと同じ動作に加え、スクリプトを毎回サーバーに送らないことで通信のデータ量を節約できるというものです。スクリプトが大きなものになる場合には効果的かもしれません。

  1. 実際の運用ではより簡略したマッチング方法でもいいかもしれません。例えば、スコアでなくランクによって候補の範囲を決めたり、5人候補が必要なら ZRANGE によって1回のクエリーで5人取ってきても問題ないかもしれません。 ↩

  2. 本来は対象のスコア範囲におけるメンバー数や、取り出したメンバーの重複も考慮すべきですが実験結果に影響は無いので省略しています。実装方法はここを参考にしています。 ↩

  3. 原子性についてはここに記述があります。また、Redis では MULTI コマンドを用いてロールバックの無いトランザクションを実現できますが、ここの記述のように将来的には EVAL コマンドによるスクリプティングに統一される可能性があります。 ↩

  4. 実際の運用ではケース1のような使い方はすべきでないと考えられます。ここの記述のように、クライアントが複数存在する状況では１つのコマンドが処理されている間、他のクライアントによるコマンドは全てストップされているため、長時間のクエリーは避けるべきでしょう。 ↩

023-Pythonのforサイクル
Python入門のソフトウェア開発規範