Redisのsortedsetで得点をランキング出来るのはわかった。で、自己最高得点でランキングする一番いい方法を頼む

ソート済みセット型 — redis 2.0.3 documentation

Redisのsorted set型を使うと、キーとなる文字列(member)と数値データ(score)のペアをソート済みの状態で保存できて、「scoreの上位100位までのランキングを行いたい」ようなシチュエーションで大変重宝します。

で、単純にscoreのランキング情報を得る場合は良いのですが、例えば「memberが過去に登録したscoreのうち、最も高いscoreのみを用いてランキングを行いたい」といった場合にどういう戦略を取るのが有効なのかなと言う点についてゆるく検証していと思います。

詳細

検証に使ったJavaソースはこちら。
Redis perftest to get max score. · GitHub

redisクライアントとしてjedisを使用。
github.com

使用するデータ

memberとしてUUID文字列を使用し、UUIDから生成したDouble型のhash値をscoreとします。

  private Map<String, Double> initData(int size) {
    Map<String, Double> data = new HashMap<String, Double>();
    System.out.println("------------ Generated value - score pair. ------------");
    for (int i = 0; i < size; i ++) {
      UUID uuid = UUID.randomUUID();
      System.out.println(uuid + ", " + Math.abs(Double.valueOf(uuid.getMostSignificantBits())));
      data.put(uuid.toString(), Math.abs(Double.valueOf(uuid.getMostSignificantBits())));
    }
    System.out.println("------------------------");
    return data;
  }

件数は10万件ぐらい。

戦略1: 過去のscoreを取得して最新scoreより大きいかどうかを比較し、大きければsorted setへ保存

Javaで書くとこんな感じ。
scoreの値を1, 2, 3...10倍することで、一つのmemberに複数のscoreを紐付けています（超適当だけど）。

  private void zscoreThenZadd(String key, int loop) {
    del(key);
    long start = System.currentTimeMillis();
    for (String value : data.keySet()) {
      for (int i = 1; i <= loop; i++) {
        try (Jedis jedis = this.pool.getResource()){
          Double currentScore = data.get(value) * i;
          Double oldScore = jedis.zscore(key, value);
          if (oldScore == null || currentScore.compareTo(oldScore) > 0) {
            jedis.zadd(key, currentScore, value);
          }
        }
      }
    }
    long total = System.currentTimeMillis() - start;
    System.out.println(key + ":" + total);
  }

毎回Redisからzscoreで古いscoreを取ってきて新しいscoreと比較。新しいscoreのほうが大きい場合は改めてzaddでmemberとscoreのペアをsorted setへ入れる。
補足すると、RedisではTransactionも使えますが、同じTransaction内でzscoreの値を取れるのはTransactionの完了時になります。SQLでいうselect for updateのように、zscoreの結果を取得してその結果をもとにzaddするかどうかを分岐するという処理は出来ません。あやうげ。

戦略2: Luaスクリプトを使い、Redis側で過去scoreの比較と保存を行う

javaで書くとこんな感じ。

  private final String scriptTemplate = 
    "local new_score = tonumber(KEYS[1])\n" +
    "local data = KEYS[2]\n" +
    "local bulk_old_score = redis.call('zscore', '%s', data)\n" +
    "local old_score = -1\n" +
    "if bulk_old_score then old_score = tonumber(bulk_old_score) end\n" +
    "if old_score < new_score then\n" +
    "  return redis.call('zadd', '%s', new_score, data)\n" +
    "else\n" +
    "  return nil\n" +
    "end";
  
  private void zscoreThenZaddInScript(String key, int loop) {
    del(key);
    String sha = null;
    try (Jedis jedis = this.pool.getResource()){
      String script = String.format(scriptTemplate, key, key);
      sha = jedis.scriptLoad(script);  
    }

    long start = System.currentTimeMillis();
    for (String value : data.keySet()) {
      for (int i = 1; i <= loop; i++) {
        try (Jedis jedis = this.pool.getResource()){
          Double currentScore = data.get(value) * i;
          String[] args = {currentScore.toString(), value};
          jedis.evalsha(sha, args.length, args);
        }
      }
    }
    long total = System.currentTimeMillis() - start;
    System.out.println(key + ":" + total);
  }

スクリプト内でzscoreとzaddを行う処理。スクリプト内の処理はatomicなので、戦略1にあったトランザクション問題も解決。ただし、スクリプト処理を行う分だけRedisの負荷が増えます。

戦略3: scoreとmemberのペアをsetとして保存しておき、アプリ側で大小比較後に最も大きいscoreをsorted setとして保存する

  private static final String KV_SPLITTER = "::";
  private void saddAllPreProcessedData(String preProcessedStoreKey, int loop) {
    del(preProcessedStoreKey);
    long start = System.currentTimeMillis();
    for (String value : data.keySet()) {
      for (int i = 1; i <= loop; i++) {
        try (Jedis jedis = this.pool.getResource()){
          String score = String.valueOf(data.get(value) * i);
          jedis.sadd(preProcessedStoreKey, value + KV_SPLITTER + score);
        }
      }
    }
    long total = System.currentTimeMillis() - start;
    System.out.println(preProcessedStoreKey + ":" + total);
  }

  private void smembersAllPreProcessedDataThenAggregateAndZadd(String preProcessedStoreKey, String key) {
    del(key);
    try (Jedis jedis = this.pool.getResource()){
      long start = System.currentTimeMillis();
      Set<String> preProcessed = jedis.smembers(preProcessedStoreKey);
      jedis.del(preProcessedStoreKey);
      Map<String, Double> map = new HashMap<String, Double>();
      for (String kv : preProcessed) {
        String[] kvAry = kv.split(KV_SPLITTER);
        String value = kvAry[0];
        Double score = Double.valueOf(kvAry[1]);
        if (map.putIfAbsent(value, score) != null) {
          map.computeIfPresent(value, (val, oldScore) -> {
            return oldScore < score? score: oldScore;
          });
        }
      }
      jedis.zadd(key,map);
      long total = System.currentTimeMillis() - start;
      System.out.println(key + ":" + total);
    }    
  }

最初にmember - valueペアの文字列表現を全てRedisへsetとして保存しておいて、改めてRedisから呼び出してscoreの大小比較とzaddでの保存を行います。実環境だとまあ、別々のスレッドでrpush+blpopで非同期に処理してくようなパターン。Redis側のメモリも食うし転送量も多いしであまりパフォーマンスは良くないんだろうなと予想してました。

(12/04追加) 戦略4: スコアを別々のキーに保存しておいて、zuniscoreで集計

  private void zunionstore(String key, int loop) {
    del(key + "::*");

    long start = System.currentTimeMillis();
    for (String value : data.keySet()) {
      for (int i = 1; i <= loop; i++) {
        try (Jedis jedis = this.pool.getResource()){
          Double currentScore = data.get(value) * i;
          jedis.zadd(key + "::" + value, currentScore, value);
        }
      }
    }
    
    try (Jedis jedis = this.pool.getResource()) {
      Set<String> keys = jedis.keys(key  + "::*");
      double[] weights = new double[keys.size()];
      Arrays.fill(weights, 1d);
      ZParams params = new ZParams();
      params.weightsByDouble(weights);
      params.aggregate(Aggregate.MAX);
      jedis.zunionstore(key, params, keys.toArray(new String[keys.size()]));
      del(key + "::*");
    }
    
    long total = System.currentTimeMillis() - start;
    System.out.println(key + ":" + total);
  }

最初にmember - valueペアの文字列表現をキー名としてzscoreとして保存したあとで、改めてzuniscoreで最大値を集計するパターン。戦略3と同じく、これも別スレッドで非同期に実行する想定。

例えば定期テストの点数など、全てのmemberが同時に何かの評価を受けてscoreを保存するという要な場合であれば、「第一回定期テスト」「第二回定期テスト」のようなキーを作ってそこにmember-valueのペアを入れてからzuniscoreで集計すれば良いんですが.........
あるmemberがスコアを100回残す一方で、もう一方のmemberは10回しかスコアを残さないような想定だと、member - valueペアをキー名として保存しとくしかないのかなと。キー名が爆発的に増加するけれど。

(12/05追加) 戦略5: 更新時に毎回zunionstoreで集計

  private void zunionstore2(String key, int loop) {

    long start = System.currentTimeMillis();
    for (String value : data.keySet()) {
      for (int i = 1; i <= loop; i++) {
        try (Jedis jedis = this.pool.getResource()){
          Double currentScore = data.get(value) * i;
          String tempStoreKey = key + "::" + UUID.randomUUID().toString();
          jedis.zadd(tempStoreKey, currentScore, value);
          double[] weights = new double[2];
          Arrays.fill(weights, 1d);
          ZParams params = new ZParams();
          params.weightsByDouble(weights);
          params.aggregate(Aggregate.MAX);
          jedis.zunionstore(key, params, tempStoreKey, key);
          jedis.del(tempStoreKey);
        }
      }
    }
    long total = System.currentTimeMillis() - start;
    System.out.println(key + ":" + total);
  }

戦略4だとキー数が爆発する件について、お昼のおしごとで指摘された改善案。
値を追加するたびに一旦テンポラリキーへ値を入れ、zunionstoreで集計する。

結果

データ1万件

戦略	処理時間 (ms)
戦略1	7648
戦略2	4985
戦略3合計	3844
戦略3(未処理データの保存)	3504
戦略3(sortedsetデータの保存)	340
戦略4	4042
戦略5	362037
戦略5(Transactionあり)	362933

データ10万件

戦略	処理時間 (ms)
戦略1	77007
戦略2	51638
戦略3合計	34856
戦略3(未処理データの保存)	36049
戦略3(sortedsetデータの保存)	4069
戦略4	41087
戦略5	NA
戦略5(Transactionあり)	NA

戦略1と比べると戦略2の処理時間は7割程度。戦略3の処理時間は半分程度。

一応、Redis側に10万件のデータが保存され、またいくつかのmemberについて抜取調査をして最も高いscoreが保存されていることも確認済み。

これだけ見れば戦略3が圧勝に見えるけれど、今回の結果は同じマシン内でJavaアプリとRedisが同居していてネットワーク負荷がボトルネックとならない環境であることを考慮する必要があります。JavaアプリとRedisが別サーバー上で動いているような場合であれば、ネットワーク速度がボトルネックとなり、転送量が多い戦略3が不利になる可能性もあるでしょう。
また、戦略2は他の戦略と比べるとRedisサーバー側でのスクリプト処理が重いはずです。Redisが使用できるCPU能力が低い場合には、スクリプト処理がボトルネックとなる可能性もあります。

戦略4は戦略3とほぼ同じぐらいのパフォーマンス。データ転送量は抑えられるものの、想定に寄ってはキーがかなり増えるのが欠点と言えば欠点。ただし、定期テストや大会の結果を集計するような処理であればキーの増加は無い。

戦略5は他の戦略と比べると桁一つ遅い。ただし、トランザクションが使えるのでデータ量が少数の場合だと使い勝手は良さそう。

いやほんとは負荷状況とかちゃんとモニタリングする必要はあるんだろうけれど休み中にそんなことしたくないよね。かといって、会社にいるとこの手の測定ってやりにくいんだよなあ。

それにしても、RDBの常識的には10万件を全件取得するようなTable Scanが走りまくる処理なんて考えられないよなーと思っていたものの、かなり良い数字が出てたのでびっくりしました。RDBでの「当たり前」を一回投げ捨てないと、Redis（だけではなくNoSQL）を上手く使うのは難しいなあ。