Рейтинг с миллионами записей

Поиск одного диска занимает около 15 мс, может быть, немного меньше с дисками серверного уровня. Время отклика менее 500 мс ограничивает вас примерно 30 произвольными обращениями к диску. Это немного.

На моем крошечном ноутбуке у меня есть база данных разработки с

root@localhost [kris]> select @@innodb_buffer_pool_size/1024/1024 as pool_mb;
+--------------+
| pool_mb      |
+--------------+
| 128.00000000 |
+--------------+
1 row in set (0.00 sec)

и медленный диск ноутбука. Я создал таблицу результатов с

root@localhost [kris]> show create table score\G
*************************** 1. row ***************************
       Table: score
Create Table: CREATE TABLE `score` (
  `player_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `score` int(11) NOT NULL,
  PRIMARY KEY (`player_id`),
  KEY `score` (`score`)
) ENGINE=InnoDB AUTO_INCREMENT=2490316 DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

со случайными целыми числами и последовательными значениями player_id. У нас есть

root@localhost [kris]> select count(*)/1000/1000 as mrows from score\G
*************************** 1. row ***************************
mrows: 2.09715200
1 row in set (0.39 sec)

База данных поддерживает пару (score, player_id) в порядке score в индексе score, поскольку данные в индексе InnoDB хранятся в BTREE, а указатель строки (указатель данных) является значением первичного ключа, так что определение KEY (score) оказывается KEY(score, player_id) внутренне . Мы можем доказать это, взглянув на план запроса для получения оценки:

root@localhost [kris]> explain select * from score where score = 17\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: score
         type: ref
possible_keys: score
          key: score
      key_len: 4
          ref: const
         rows: 29
        Extra: Using index
1 row in set (0.00 sec)

Как видите, key: score используется с Using index, а это означает, что доступ к данным не требуется.

Ранжирующий запрос для заданной константы player_id на моем ноутбуке занимает ровно 500 мс:

root@localhost [kris]>  select p.*, count(*) as rank 
    from score as p join score as s on p.score < s.score 
   where p.player_id = 479269\G
*************************** 1. row ***************************
player_id: 479269
    score: 99901
     rank: 2074
1 row in set (0.50 sec)

С большим объемом памяти и на более быстром компьютере это может быть быстрее, но это все еще сравнительно дорогая операция, потому что план отстой:

root@localhost [kris]> explain select p.*, count(*) as rank from score as p join score as s on p.score < s.score where p.player_id = 479269;
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref   | rows    | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
|  1 | SIMPLE      | p     | const | PRIMARY,score | PRIMARY | 4       | const |       1 |                          |
|  1 | SIMPLE      | s     | index | score         | score   | 4       | NULL  | 2097979 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
2 rows in set (0.00 sec)

Как видите, вторая таблица в плане — это сканирование индекса, поэтому запрос замедляется линейно с количеством игроков.

Если вам нужна полная таблица лидеров, вам нужно убрать предложение where, и тогда вы получите два сканирования и квадратичное время выполнения. Так что этот план полностью рушится.

Время перейти к процедуре здесь:

root@localhost [kris]> set @count = 0; 
    select *, @count := @count + 1 as rank from score where score >= 99901 order by score desc ;
...
|   2353218 | 99901 | 2075 |
|   2279992 | 99901 | 2076 |
|   2264334 | 99901 | 2077 |
|   2239927 | 99901 | 2078 |
|   2158161 | 99901 | 2079 |
|   2076159 | 99901 | 2080 |
|   2027538 | 99901 | 2081 |
|   1908971 | 99901 | 2082 |
|   1887127 | 99901 | 2083 |
|   1848119 | 99901 | 2084 |
|   1692727 | 99901 | 2085 |
|   1658223 | 99901 | 2086 |
|   1581427 | 99901 | 2087 |
|   1469315 | 99901 | 2088 |
|   1466122 | 99901 | 2089 |
|   1387171 | 99901 | 2090 |
|   1286378 | 99901 | 2091 |
|    666050 | 99901 | 2092 |
|    633419 | 99901 | 2093 |
|    479269 | 99901 | 2094 |
|    329168 | 99901 | 2095 |
|    299189 | 99901 | 2096 |
|    290436 | 99901 | 2097 |
...

Поскольку это процедурный план, он нестабилен:

• Вы не можете использовать LIMIT, потому что это приведет к смещению счетчика. Вместо этого вы должны загрузить все эти данные.
• Вы действительно не можете сортировать. Это предложение ORDER BY работает, потому что оно не сортирует, а использует индекс. Как только вы увидите using filesort, значения счетчика резко снизятся.

Однако это решение ближе всего к тому, что будет делать база данных NoSQL (читай: процедурная) в качестве плана выполнения.

Однако мы можем стабилизировать NoSQL внутри подзапроса, а затем вырезать интересующую нас часть:

root@localhost [kris]> set @count = 0; 
    select * from ( 
        select *, @count := @count + 1 as rank 
          from score 
         where score >= 99901 
      order by score desc 
    ) as t 
    where player_id = 479269;
Query OK, 0 rows affected (0.00 sec)
+-----------+-------+------+
| player_id | score | rank |
+-----------+-------+------+
|    479269 | 99901 | 2094 |
+-----------+-------+------+
1 row in set (0.00 sec)

root@localhost [kris]> set @count = 0; 
    select * from ( 
        select *, @count := @count + 1 as rank 
          from score 
         where score >= 99901 
      order by score desc 
    ) as t 
    where rank between 2090 and 2100;
Query OK, 0 rows affected (0.00 sec)
+-----------+-------+------+
| player_id | score | rank |
+-----------+-------+------+
|   1387171 | 99901 | 2090 |
|   1286378 | 99901 | 2091 |
|    666050 | 99901 | 2092 |
|    633419 | 99901 | 2093 |
|    479269 | 99901 | 2094 |
|    329168 | 99901 | 2095 |
|    299189 | 99901 | 2096 |
|    290436 | 99901 | 2097 |
+-----------+-------+------+
8 rows in set (0.01 sec)

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

Однако обратите внимание, как оба запроса удовлетворяют вашему временному ограничению. Вот план:

root@localhost [kris]> set @count = 0; explain select * from ( select *, @count := @count + 1 as rank from score where score >= 99901 order by score desc ) as t where rank between 2090 and 2100\G
Query OK, 0 rows affected (0.00 sec)

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: <derived2>
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 2097
        Extra: Using where
*************************** 2. row ***************************
           id: 2
  select_type: DERIVED
        table: score
         type: range
possible_keys: score
          key: score
      key_len: 4
          ref: NULL
         rows: 3750
        Extra: Using where; Using index
2 rows in set (0.00 sec)

Однако оба компонента запроса (внутренний запрос DERIVED и внешнее ограничение BETWEEN) будут работать медленнее для игроков с плохим рейтингом, а затем грубо нарушат ваши временные ограничения.

root@localhost [kris]> set @count = 0; select * from ( select *, @count := @count + 1 as rank from score where score >= 0 order by score desc ) as t;
...
2097152 rows in set (3.56 sec)

Время выполнения описательного подхода стабильно (зависит только от размера таблицы):

root@localhost [kris]> select p.*, count(*) as rank 
   from score as p join score as s on p.score < s.score 
   where p.player_id = 1134026;
+-----------+-------+---------+
| player_id | score | rank    |
+-----------+-------+---------+
|   1134026 |     0 | 2097135 |
+-----------+-------+---------+
1 row in set (0.53 sec)

Ваш звонок.

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

Подсчет очков

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

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

Чтобы учесть это, моя таблица score_buckets будет иметь следующую структуру:

minscore, maxscore, usercount; PK(minscore, maxscore)

Пользовательская таблица

Мы должны отслеживать наших пользователей, и, вероятно, это будет сделано с помощью:

userid, score, timestamp
#(etc., etc. that we don't care about for this part of the problem)

Чтобы эффективно перебрать это, чтобы получить счет по счету, нам нужен индекс для счета. Временная метка — это просто то, что я добавил в своем примере для разрешения конфликтов, чтобы у меня был окончательный порядок. Если он вам не нужен, выбросьте его — он использует пространство, и это повлияет на время запроса. На данный момент: index(счет, временная метка).

Добавление/обновление/удаление пользователей и их оценок

Добавьте триггеры в пользовательскую таблицу. При вставке:

update score_buckets sb
    set sb.usercount = sb.usercount + 1
    where sb.minscore <= NEW.score
    and sb.maxscore >= NEW.score

При обновлении

update score_buckets sb
    set sb.usercount = sb.usercount - 1
    where sb.minscore <= OLD.score
    and sb.maxscore >= OLD.score
update score_buckets sb
    set sb.usercount = sb.usercount + 1
    where sb.minscore <= NEW.score
    and sb.maxscore >= NEW.score

При удалении

update score_buckets sb
    set sb.usercount = sb.usercount - 1
    where sb.minscore <= OLD.score
    and sb.maxscore >= OLD.score

Определение ранга

$usersBefore = select sum(usercount)
    from score_buckets
    where maxscore < $userscore;
$countFrom = select max(maxscore)
    from score_buckets
    where maxscore < $userscore;
$rank = select count(*) from user
    where score > $countFrom
    and score <= $userscore
    and timestamp <= $userTimestamp

Заключительные примечания

Сравните с различным количеством сегментов, каждый раз удваивая или уменьшая их вдвое. Вы можете быстро написать сценарий удвоения / деления пополам ведра, чтобы вы могли провести нагрузочное тестирование. Чем больше сегментов, тем меньше сканирование индекса оценок пользователей и меньше конфликтов между блокировками и транзакциями при обновлении оценок. Чем больше сегментов, тем больше памяти. Чтобы выбрать число для начала, используйте 10 000 ведер. В идеале ваши сегменты будут охватывать весь диапазон оценок, и в каждом сегменте будет примерно одинаковое количество пользователей. Если ваш график распределения очков следует какой-то кривой, сделайте так, чтобы распределение корзины соответствовало этой кривой.

Теория этого рода связана с двухуровневым списком пропуска.

Недавно я прочитал статью о решении такой проблемы с помощью Redis. Вы по-прежнему можете использовать MySQL в качестве основного хранилища, но вы будете кэшировать несортированные результаты в Redis и обновлять рейтинг в режиме реального времени. Ссылку можно найти здесь. Последняя треть статьи посвящена сортировке по ключу, как в случае со списком ранжирования.

Сортировка миллионов записей может показаться большой работой, но это явно не так. Сортировка 10 ^ 6 совершенно случайных записей на моем компьютере занимает около 3 секунд (просто старый EeePC с процессором Atom (я думаю, первого поколения), 1,6 ГГц).

И с хорошим алгоритмом сортировки сортировка имеет O (n * log (n)) в худшем случае, поэтому не имеет большого значения, если у вас есть 10 ^ 9 или более записей. И большую часть времени ранговый список будет уже почти отсортирован (из предыдущего ранжирования), что приведет к времени выполнения, которое, скорее всего, будет O (n).

Итак, перестаньте беспокоиться об этом! Единственная реальная проблема заключается в том, что большинство СУБД не могут напрямую обращаться к 1000-й записи. Таким образом, такой запрос, как SELECT ... LIMIT 1000, 5, должен будет запросить не менее 1005 записей и пропустить первые 1000. Но решение здесь тоже простое. Просто сохраните rank как избыточный столбец каждой строки, добавьте к нему индекс и вычисляйте его каждые 15 минут (или каждые 5 минут, 30 минут, 1 час или что-то еще, что имеет смысл для вашего приложения). При этом все запросы по рангу представляют собой просто поиск по вторичному индексу (около O(log(N))), который чрезвычайно быстр и занимает всего несколько миллисекунд на запрос (узким местом здесь является сеть, а не база данных).

PS: Вы прокомментировали другой ответ, что вы не можете кэшировать отсортированные записи, потому что они слишком велики для вашей памяти. Если предположить, что вы просто кэшируете кортежи (user_id, rank) с двумя 64-битными целыми числами (32-битных тоже будет более чем достаточно!), вам потребуется менее 8 МБ памяти для хранения 10 ^ 6 записей. Вы уверены, что у вас недостаточно оперативной памяти для этого?

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

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

Я могу придумать два способа решения этой проблемы:

Первый подход: обновление партиями:

• Сортируйте баллы, получайте рейтинг
• Разделите игроков по рангу на группы, такие как игрок0-игрок999, игрок1000-игрок1999 и т. д.
• Для каждого пакета удалите записи в существующей таблице, которые конфликтуют с новыми данными. Это означает удаление существующих записей, принадлежащих игрокам в текущем пакете или тем, кто в настоящее время находится в диапазоне рангов, обновляемых в текущем пакете. Затем вы загружаете данные ранжирования для пакета в базу данных и переходите к следующему пакету, скажем, через 0,1 с.

Второй подход: новая таблица

• Создайте (или сократите) новую таблицу точно так же, как ваша существующая таблица ранжирования.
• вычислить новый рейтинг и вставить свои данные
• Поменяйте столы местами (предпочтительно заблокировав их). Это должно занять меньше секунды.