Задача о рейтинге игрока

Как часто игрокам надо все это обновлять? Если раз в 10 минут и только тем, кто онлайн, то никакого хайлоада тут нет. Делаешь индексы на таблицу и все летает SELECT * FROM ... ORDER BY ... LIMIT 5. Даже если join по друзьям сделаешь.

Да и вообще, зря ты такое называешь хайлоадом.

SELECT * FROM ... ORDER BY ... LIMIT 5

Ну это понятно, для top 5 лучших, я и написал, что это тривиально, а как определить, что сам игрок Вася Пупкин стоит на 840693 месте, а его друзья Коля и Петя на 45938 и 396028 местах соответственно?

Ну, у тебя есть табличка friends, там 2 поля: user_id, friend_id.

SELECT id, position FROM 
  (SELECT id, score, row_number() AS "position" FROM users ORDER BY score ASC) AS "source" 
  LEFT JOIN friends WHERE ( friends.user_id = source.id ) 
WHERE friends.user_id = <me> ORDER BY source.score LIMIT 5;

Типа того

Ну это на лету, но что-то типа такого будет довольно шустро.

(SELECT id, score, row_number() AS «position» FROM users ORDER BY score ASC)

перенумеровать всех игроков на лету — это быстро?

Тебе всё равно придётся расчитывать позицию всех игроков в системе, даже тех кто в оффлайне.

Поэтому делаешь одну глобальную таблицу со всеми игроками и дальше из неё выдираешь всё что нужно. Причём всё это отлично влезает в память.

Тебе всё равно придётся расчитывать позицию всех игроков в системе, даже тех кто в оффлайне.

Естественно

Поэтому делаешь одну глобальную таблицу со всеми игроками и дальше из неё выдираешь всё что нужно. Причём всё это отлично влезает в память.

То есть, тут лучше самописное решение, которое будет хранить в памяти?

Я тут ещё подумал, что при изменении очков рейтинг достаточно пересчитывать только у тех игроков, которые по очкам попадают в диапазон изменения. А это должно значительно облегчить расчёты.

небольшой дополнительный вопрос от меня. Условие - рейтинг считается как сложная функция от разных параметров других игроков. Например, количество выигранных боёв в отношении к среднему значению по серверу, еще что-то. Мы эту лажу просто обновляли не чаще, чем раз в сутки. Просто считали что можно в оракле, остальное - скриптом (ибо в самом PHP что-то считать и хранить неприятно). А как делают реальные(с) пацаны(тм)?

Я чуток ошибся, там еще окно указать надо

SELECT id, position FROM 
  (SELECT id, score, row_number() OVER (ORDER BY score DESC) AS "position" FROM users) AS "source" 
  LEFT JOIN friends WHERE ( friends.user_id = source.id ) 
WHERE friends.user_id = <me> ORDER BY source.score LIMIT 5;

Это очень быстро. Я у себя на боевой базе попробовал по табличке с 600000 записей с выводить top-5 по дате. Выполняется всего десятки миллисекунд

Это при том, что база развернута на моей не очень быстрой рабочей машине, а не на нормальной серверной тачке.

тут лучше самописное решение, которое будет хранить в памяти?

Я не очень понимаю о чём ты, но тут подойдёт любое решение, отсортировать миллион-другой записей это не проблема. Я на питоне вот такое сделал для 10млн записей:

from random import randint
import string
rndstr = lambda: ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(16))

# тут тупило 15-20 секунд на ноуте, но это оптимизируется
data = [(randint(1,10000), rndstr()) for _ in range(1000000)]

# меньше 2 секунд
data.sort()

Всё вместе 200метров RSS. В общем, на нормальном сервере нету никаких проблем обновлять эту таблицу хоть несколько раз в минуту.

по табличке с 600000 записей с выводить top-5 по дате. Выполняется всего десятки миллисекунд

очень интересно, спасибо большое

как делают реальные(с) пацаны(тм)?

Хз. Я бы хранил в базе в отдельной таблице или redis каком-нить. Главное атомарно обновлять данные. Если не ошибаюсь, mysql такое умеет, остальные БД должны тоже: http://dev.mysql.com/doc/refman/5.0/en/rename-table.html

Обновлять можете хоть по крону :). Главное не допустите того чтобы новый скрипт не стал отрабатывать пока старый не завершиться. Тут гугл в помощь.

Короче, всё зависит от того что у вас ещё есть. Если уже стоит мускул/postgres то юзайте его. Если redis/mongo... юзайте их. Это непринципиально.

в самом PHP что-то считать и хранить неприятно

Хранить согласен. А вот считать.. Я не знаю что у вас там, но при наличии ORM не вижу никаких проблем. Но, возможно, я ошибаюсь. Что мешает выгрузить данные по игрокам из базы и загрузить обратно? Да, гонять туда-сюда не комильфо, но... 1млн записей раз в минуту это не так уж и много данных по сравнению с остальной нагрузкой на базу.

Я бы всё же сохранил результат в памяти где-нить (in-memory table чтобы зря не дёргать диски и логи транзакций там) для всех игроков и потом уже тягал данные оттуда. Потому что при паре тыщ игроков онлайн эти десятки миллисекунд могут превратиться в ощутимую нагрузку, не?

Для ранка заводишь отдельный столбец и при любом изменении входных данных (поменялся у кого-то скор, ник, появилась/удалилась запись пользователя) запускаешь джобу пересчета путем отправки сообщения джобе. Только сообщения троттлить нужно, что бы ограничить количество общетов, например не чаще, чем раз в 10 секунд.

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

Если и этого мало, выносишь индекс во внешний сервис, который строит кеш в памяти.

Да, на хайлоаде эти десятки миллимекнунд может быть дохрена. Например если запрос прямо отжирает 20 миллесекунд CPU (а не сети), то 50 запросов в секунду уже отожрут одно ядро.

Блин, указанная ТС задача не относится к хайлоад. Такие данные у клиентов обычно обновляются раз в дофига минут.

Такие данные у клиентов обычно обновляются раз в дофига минут.

Если взять за основу очки опыта, то в некоторых играх у каждого игрока они могут меняться в течение минуты несколько раз. Кроме того, такая ситуация: игрок докачивается до 10000 очков, смотрит рейтинг, а он (поскольку не обновился), показывает, что у него всего 9 тысяч с копейками. Естественно, что некоторые начнут жаловаться и возмущаться.

Разумеется, если результаты рассчитываются непосредственно при запросе, то проблемы валидности кэша нет. Но тогда нагрузка начинает зависеть от количества запросов рейтинга. А сколько их будет в секунду при онлайне 10000, зависит скорее от самой игры и желания гейм-дизайнеров и маркетологов.

не спорь с экспертом! ты в тасках и джобах нифига не разбираешься, иди домой троттлить и тюнить!

Если хочешь прям риалтайм, то делай последний вариант - сервис, который слушает апдейты и строит в памяти специализированнй кеш.

Тут разница - личные очки игрока и Топ всех игроков. Первый показывается в онлайне, второй обычно - нет.

Если нужен и второй в онлайне, тогда, действительно, надо делать какой-то кеш (пофиг какой, можно тупо хранить хешмапе какой-нибудь), но тогда будешь жертвовать памятью: надо кешировать Топ-5 глобальный + N игроков * Топ-5 друзей.

Если реальный highload, а те пара тысяч апдейтов, то _любой_ SQL тут как пятая нога.

Для highload делайте сервис на плюсах, либо рекомендую http://tarantool.org/ - все необходимое уже есть и разработчики свои/рядом.

Смотри исходники Лора, и как там скор и его отображение реализовано.

Смотри исходники Лора, и как там скор и его отображение реализовано.

а тут у нас разве есть топ рейтинга?