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

Ответ 1

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

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

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

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

[email protected] [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. Мы имеем

[email protected] [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) внутренне. Мы можем доказать, что, посмотрев план запроса для поиска баллов:

[email protected] [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 мс на моем ноутбуке:

[email protected] [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)

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

[email protected] [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, а затем вы получите два сканирования и квадратичное время выполнения. Таким образом, этот план полностью разрушается.

Время для прохождения процедуры:

[email protected] [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 (read: процедурная) будет выполнять как план выполнения.

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

[email protected] [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)

[email protected] [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)

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

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

[email protected] [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) будут замедляться для игроков с плохой оценкой, но затем грубо нарушают ваши ограничения времени.

[email protected] [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)

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

[email protected] [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)

Ваш вызов.

Ответ 2

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

Скользящие ковши

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

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

Для этого моя таблица 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)

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

Вставка/обновление/Удаление пользователей и их оценка

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

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

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

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

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

Ответ 3

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

Ответ 4

Сортировка миллионов записей может показаться большой работой, но это явно не так. Сортировка 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 записей. Вы уверены, что для этого недостаточно памяти?

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

Ответ 5

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

Ответ 6

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

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

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

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

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