这是Happy Elements株式会社卡卡利亚工作室2016年圣诞降临日历的第19篇文章。

总览

在我所属的团队应用中，我们使用Redis的Sorted Sets来实现用户排名。关于Redis的基本解释请参考另一篇文章，本文将介绍使用脚本功能（EVAL命令）进行实现的方法。

从已排序集合中随机获取成员

请考虑以下情景（设定是虚构的）。

百万名用户各自都有自己的分数，并且根据此实时排名。分数会根据用户之间的对战而变化。例如，如果战胜比自己分数高的用户，则自己的分数会大幅增加，而战胜比自己分数低的用户，则增加较少。选择对战对手时，希望选择与自己分数相当的用户，并且希望从以自己为中心的一定分数范围内随机选择候选人，以避免每次都与同一对手对战。1

由于使用Redis的有序集合来实现排行榜，希望也能用它来进行对手匹配。然而，有序集合中没有像Sets中的SRANDMEMBER一样的命令来随机获取元素，所以需要自己实现这个功能。

实验的设置

使用 redis-rb 来连接 Redis 的客户端。将随机得分分配给一百万个用户，并将其添加到 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

我們將對以下兩種實驗進行各自10次測量，然後比較它們的平均值。
– 一次性抽取一萬人
– 分批次抽取五人，共分為兩千次抽取

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进行实施时，以下两个缺点可以被提出。当用户数量和网络服务器数量较多时，这两个问题都变得棘手。

• 各 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来实现大部分功能，但是使用Lua来编写与Redis的交互部分，并将其作为参数传递给EVAL命令。这样一来，我们可以一次完成与服务器的交互，并减少通信的开销。同时，在执行EVAL命令时，其他命令不会打断，因此服务器的状态不会在脚本执行期间意外改变。

快慢对比

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 的实现只需要一次操作，因此与情况2相比有很大的差距。
情况2更接近实际应用，但仍存在明显差距。

总结

我们对使用Ruby进行的Sorted Sets的随机成员获取方法进行了比较，并与使用EVAL和Lua的实现进行了对比。考虑到在其他用途中也可能通过使用EVAL命令来实现加速，建议您考虑一下这个方法。

此外，虽然本次没有提及，但还有一个叫做 EVALSHA 的命令。它除了具有 EVAL 命令的功能外，还可以通过不每次将脚本发送到服务器来节省通信数据量。对于较大的脚本可能会更加有效。