Как создать отсортированный набор с порядком field1 desc, field2 asc в Redis?

Я пытаюсь создать списки лидеров в Redis, чтобы получить X первые результаты и получить ранг пользователя Y.

Сортированные списки в Redis выглядят легко, за исключением одной проблемы - мне нужно, чтобы оценки были отсортированы не только по фактическому счету, но и по дате (чтобы тот, кто получил такой же результат ранее, был на первом месте). SQL-запрос будет:

select * from scores order by score desc, date asc

Запуск zrevrange на отсортированном наборе в Redis использует что-то вроде:

select * from scores order by score desc, key desc

Что поместило бы пользователей с лексикографически большими клавишами выше.

Одно из решений, которое я могу придумать, - это произвести некоторые манипуляции с полем оценки внутри отсортированного набора для получения объединенного числа, состоящего из оценки и отметки времени.

Например, для оценки 555 с отметкой времени 111222333 окончательный результат может быть примерно таким, как 555.111222333, что ставит новые оценки выше старых (не совсем то, что мне нужно, но можно было бы скорректировать дальше).

Это сработает, но только с небольшими числами, поскольку оценка в отсортированном наборе имеет только 16 значащих цифр, поэтому 10 из них будут потрачены на временную метку сразу, оставляя мало места для фактической оценки.

Есть идеи, как заставить отсортированный набор упорядочивать значения в правильном порядке? Я бы действительно хотел, чтобы конечный результат был отсортированным набором (чтобы легко получить рейтинг пользователя), даже если для создания такого набора требуются некоторые временные структуры и сортировки.


redis sortedset
person serg    schedule 11.05.2012    source источник

Ответы (4)


arrow_upward
1
arrow_downward

На самом деле все мои предыдущие ответы ужасны. Не обращайте внимания на все мои предыдущие ответы (хотя я собираюсь оставить их для других).

Вот как вы должны это делать на самом деле:

  • Сохранять только партитуры в zset
  • Отдельно храните список, когда игрок достигал этого результата.

Например:

score_key = <whatever unique key you want to use for this score>
redis('ZADD scores-sorted %s %s' %(score, score))
redis('RPUSH score-%s %s' %(score, score_key))

Затем, чтобы прочитать оценки:

top_score_keys = []
for score in redis('ZRANGE scores-sorted 0 10'):
    for score_key in redis('LRANGE score-%s 0 -1' %(score, )):
        top_score_keys.append(score_key)

Очевидно, вы захотите провести здесь некоторую оптимизацию (например, читать только фрагменты списка score-, а не читать его целиком).

Но это определенно способ сделать это.

Рейтинг пользователей будет прямым: для каждого пользователя отслеживайте его высокий балл:

redis('SET highscores-%s %s' %(user_id, user_high_score))

Затем определите их ранг, используя:

user_high_score = redis('GET highscores-%s' %(user_id, ))
score_rank = int(redis('ZSCORE scores-sorted %s' %(user_high_score, )))
score_rank += int(redis('LINDEX score-%s' %(user_high_score, )))
person David Wolever    schedule 13.05.2012
comment
Извините, я не понимаю, как это создает вторичный порядок по дате. Как получить 10 лучших результатов, заказанных score desc, date asc? Как получить рейтинг конкретного пользователя? - person serg; 16.05.2012
comment
См. Второй пример, в котором показано, как получить 10 лучших результатов, отсортированных по количеству очков (по ZRANGE) и по дате в порядке убывания (от LRANGE, потому что список упорядочен от самого старого к самому новому. О, подождите, но вы хотите от самого нового к самому старому - в этом случае измените RPUSH на LPUSH, и список будет упорядочен от самого нового к самому старому. - person David Wolever; 16.05.2012
comment
И посмотрите мою правку, которая показывает, как будет рассчитываться рейтинг пользователя. - person David Wolever; 16.05.2012
comment
Я добавил 1 вопрос stackoverflow.com/questions/ 12854149 / Думаю, это связано с этим постом. Но я не перестаю понимать ваш ответ. Это тоже работает со временем. - person PHP Connect; 12.10.2012

arrow_upward
0
arrow_downward

Это не совсем идеальное решение, но если вы создадите индивидуальную эпоху, которая будет ближе к текущему времени, вам понадобится меньше цифр для ее представления.

Например, если вы используете 1 января 2012 года для своей эпохи, вам (в настоящее время) потребуется только 8 цифр для представления метки времени.

Вот пример на рубине:

(Time.new(2012,01,01,0,0,0)-Time.now).to_i

Это даст вам примерно 3 года до того, как временная метка потребует 9 цифр, и в это время вы можете выполнить некоторое обслуживание, чтобы снова переместить настраиваемую эпоху вперед.

Однако я хотел бы услышать, есть ли у кого-нибудь идеи получше, поскольку у меня точно такая же проблема.

person Thomas Dippel    schedule 13.05.2012

arrow_upward
0
arrow_downward

(Примечание: этот ответ почти наверняка неоптимален; см. https://stackoverflow.com/a/10575370/71522)

Вместо использования метки времени в счете вы можете использовать глобальный счетчик. Например:

score_key = <whatever unique key you want to use for this score>
score_number = redis('INCR global-score-counter')
redis('ZADD sorted-scores %s.%s %s' %(score, score_number, score_key)

И чтобы отсортировать их в порядке убывания, выберите большое количество очков (скажем, 1<<24), используйте его в качестве начального значения global-score-counter, затем используйте DECR вместо INCR.

(это также применимо, если вы используете метку времени)

В качестве альтернативы, если вы действительно невероятно беспокоитесь о количестве игроков, вы можете использовать счетчик очков:

score_key = <whatever unique key you want to use for this score>
score_number = redis('HINCR score-counter %s' %(score, ))
redis('ZADD sorted-scores %s.%s %s' %(score, score_number, score_key))
person David Wolever    schedule 13.05.2012

arrow_upward
0
arrow_downward

(Примечание: этот ответ почти наверняка неоптимален; см. https://stackoverflow.com/a/10575370/71522)

Пара мыслей:

Например, используя оба вышеперечисленных (в потенциально ошибочном псевдокоде):

score_small = int(score / 1000)
time_small = int((time - 1336942269) / 60)
score_key = uuid()
redis('SET full-score-%s "%s %s"' %(score_key, score, time))
redis('ZADD sorted-scores %s.%s %s' %(score_small, time_small, score_key))

Затем загрузить их (примерно):

top_scores = []
for score_key in redis('ZRANGE sorted-scores 0 10'):
    score_str, time_str = redis('GET full-score-%s' %(score_key, )).split(" ")
    top_scores.append((int(score_str), int(time_str))
top_scores.sort()

Эту операцию можно даже полностью выполнить внутри Redis (избегайте накладных расходов сети, связанных с операциями O(n) GET), используя EVAL (хотя я недостаточно знаю Lua, чтобы с уверенностью представить пример реализации).

Наконец, если вы ожидаете действительно огромного диапазона оценок (например, вы ожидаете, что будет большое количество оценок ниже 10 000 и такое же большое количество оценок выше 1 000 000), то вы можете использовать два отсортированных набора: scores-below-100000 и scores-above-100000 .

person David Wolever    schedule 13.05.2012