百万级别排名

Question

我正在为一个能够处理数百万玩家的在线游戏设计服务器。现在，这个游戏需要排行榜功能，并希望能够显示一位玩家当前的排名以及可能与该玩家排名相近的其他玩家的位置，以及该玩家好友的位置。

我以前用MySQL做过类似的东西，我知道这在技术上是可行的，但我认为既然这是许多在线游戏常见的实践，必定存在专门用于此目的的现成库或数据库？

有人能告诉我哪种数据库最适合这些类型的查询，可能还有任何已经完成大量工作的现成库吗？具有API访问权限的第三方服务也可以。

希望能得到一些好的建议，谢谢！

编辑：

为了澄清，我需要一个能够容纳数百万条记录的数据库（迄今为止MySQL很好），并且我可以轻松地获取排名结果。例如，如果我从"排行榜"表中获取特定行，我需要知道该行的排名。无论数据库的大小如何，此查询的响应时间必须在500毫秒以下。

或者，如果可以更新表格以包含当前的排名信息，并且此更新查询不锁定整个表格，并且更新查询在30秒内运行，这样也可以。

有什么关于要使用哪种数据库/机制或第三方服务的想法将不胜感激！

- Naatan

---

你能发布一下你的架构图和你当前的评分系统是如何工作的吗？谢谢。 - Jon Black

请问您预计最大的同时在线玩家数量是多少？ - Jon Black

嗨f00，模式是无关紧要的，它是为了实现最终目的而服务的-即在500毫秒内获得数百万条记录之间的特定排名。至于并发用户，这将随着条目数量的增加而相应扩展，100万条目将相当于（非常粗略的估计）约10,000个并发用户。 - Naatan

所以，如果我将（game_id、round_id、player_id）设置为复合主键，您不介意吧。我猜想，在游戏的生命周期中可能会有多个回合，但是嘿，既然它无关紧要（哈哈），那就没有关系了。 - Jon Black

嘿，f00。不确定你所指的“round”是什么意思，我猜测你在谈论某种级别机制？无论如何，这并不重要，唯一重要的是id_game、id_user和score这三个字段。 - Naatan

Answer 1

一次磁盘寻址大约需要15ms，也许使用服务器级别的磁盘可以稍微缩短时间。小于500ms的响应时间限制您只能进行约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中按照score的顺序维护了(score，player_id)这对数据。由于InnoDB索引中的数据存储在B树中，行指针（数据指针）是主键值，因此定义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 的排名查询在我的笔记本电脑上需要精确的500ms：

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)

你来打电话。

- Isotopp

---

感谢您的精彩回复lsotopp！您的数字似乎与我的相当吻合。我已经多次进行了优化，但似乎没有任何绕过它的方法。我将基本上使用您建议的方法，但如果得分低于某个数字，则会回退到“估计”排名，显然不是理想的选择，但如果您的排名是＃5000，那么即使有点偏差也无所谓。无论如何，非常感谢您详尽的回复！真的非常有帮助！ - Naatan

不用谢。这篇文章是我与两位 MySQL AB 同事 Kai Voigt（现在是 Cloudera）和 Jan Kneschke（现在是 Oracle）共同探讨的一个主题的变化。请参见 http://mysqldump.azundris.com/archives/32-The-Quota-Query-and-Running-Sums-by-Jan-and-Kai.html 获取原始文章。 - Isotopp

有点令人困惑：您在表名和列名中都使用了“score”，因此在（相对复杂的）查询中很难区分两者。 - aberaud

当你有5000万行数据并查询最后一个分数为零的玩家时，子查询是否与查询前1000名玩家一样快？ - Daniel

不需要手动指定范围，是否可以使用当前玩家排名来指定范围，例如玩家排名-2和玩家排名+2？ - Kumar KS

Answer 2

我知道这是一个老问题，但我喜欢研究这样的问题。考虑到数据-查询速度所需的比率，可以使用一些非传统技巧，这需要更多的编码工作，但确实可以大大提高查询性能。

评分桶

首先，我们应该使用桶来跟踪分数。我们希望桶列表（多么好的名字！）足够小，可以轻松地保存在内存中，并且足够大，以便桶不会经常受到影响（相对而言）。这为我们提供了更大的并发性，以避免锁定问题。

您需要根据负载来判断如何分割这些桶，但我认为您希望专注于尽可能多的桶，这些桶可以轻松地适合内存并快速添加。

为了适应这一点，我的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

结束语

使用不同数量的桶进行基准测试，每次加倍或减半。您可以快速编写一个桶加倍/减半脚本来进行负载测试。更多的桶意味着扫描用户分数索引的次数更少，在更新分数时锁定/事务争用也更少。更多的桶会消耗更多的内存。为了选择一个起始数字，使用10,000个桶。理想情况下，您的桶将覆盖整个分数范围，并且每个桶中计算的用户数量大致相同。如果您的得分分布图遵循某种曲线，请使您的桶分布遵循该曲线。

这个理论有点类似于跳表的两层结构。

- Jeff Ferland

---

我喜欢这种方法。 - Sorter

我的建议是，如果有太多用户拥有相同的分数，即使他们超过了阈值，您仍然无法将桶分开。这种情况通常发生在游戏不太受欢迎且许多玩家在10分钟内退出但留下初始分数（如100）的情况下。因此，最好使用得分和时间戳来构建桶。score_buckets应该有三列：score_ts_from，score_ts_to和count。 - Daniel

Answer 3

我最近阅读了一篇关于使用Redis解决这类问题的文章。您仍然可以将MySQL作为基本存储，但是您可以在Redis中缓存未排序的结果并实时更新排名。您可以在此处找到相关链接。该文章的最后三分之一讲述了键排序，就像您在排名列表中所拥有的那样。

- David Richards

---

谢谢David，不幸的是，这并不适用于我的排行榜，因为它可以容纳数百万条目。缓存那么多数据有点过分了。我可以通过SQL查询获取排名，但是随着表格变得越来越大，这些查询将运行更长时间。我需要一些能够随着更大的数据库而扩展的东西，而不会使查询执行时间增加太多。 - Naatan

@Naatan：我支持David的答案，NoSQL是处理它的好方法。它是“随着更大的数据库而扩展，而不会使查询执行时间增加太多的东西。”如果您有一个能够为数百万用户提供规模的数据库，那么为某些用户参数设置并行Redis服务器应该不成问题。 - w.k

@Naatan：你应该看一下那篇文章。讨论的是如何使用 Redis 处理百万级别的问题集，这正是你所描述的。也许一个思考方式是 MySQL 专为集合操作进行优化而 Redis 则专为快速缓存非常大的数据集进行优化。 - David Richards

谢谢David，我会在我的初始可用版本运行后尝试它，这个版本应该可以处理大约500万条记录，而我们在接下来的几个月内不会达到这个数量。 - Naatan

Answer 4

对数百万条数据进行排序听起来可能很费力，但实际上并不是这样。在我的电脑上（只是一台老旧的EeePC，配备了一个Atom CPU（我想是第一代），1.6GHz），对10^6个完全随机的条目进行排序只需要大约3秒钟。

而且使用好的排序算法，在最坏情况下排序的时间复杂度为O(n*log(n))，因此，无论你有10^9个或更多的条目，都不会真正影响到排序的速度。而且大部分时间，排名列表已经接近排序完成（从之前的排名中），导致运行时间更可能是O(n)。

所以，请停止担心！唯一真正的问题是，大多数DBMS不能直接访问第1000个条目。因此，像SELECT ... LIMIT 1000, 5这样的查询将至少查询1005个条目，并跳过前1000个。但解决方法很简单。只需将每行的rank作为冗余列存储，添加索引，并每15分钟（或每5分钟、30分钟、1小时或其他适合您应用程序的时间）计算一次。这样，所有按排名查询的查询都只是简单的二级索引查找（大约是O(log(N))），非常快速，每个查询只需要几毫秒（网络是瓶颈，而不是数据库）。

PS：您在另一个答案中评论说，您无法缓存排序后的条目，因为它们对于您的内存太大。假设您只缓存具有两个64位整数（32位也足够！）的（user_id，rank）元组，那么您需要少于8 MB的内存来存储10^6个条目。您确定没有足够的RAM吗？

因此，请不要试图优化明显不是瓶颈的东西（尚未）。

- tux21b

---

感谢您的回答tux21b！非常有启发性！不幸的是，按照您所说的每15、30或60分钟更新一次仍然会导致查询运行大约1分钟，以更新所有行的新排名，而随着数据库的增长，这些排名将不断增加。我可能不得不采取这种方法，但我强烈不希望在cron工作中运行如此沉重的查询。不过我会研究缓存结果的方法，这可能是一个好的解决方案。 - Naatan

将排名存储在它们自己的表中（用户ID、排名、排名索引）如何？每隔N分钟清空并重新加载。 - Philip Kelley

Answer 5

你可以在玩家表中冗余地存储每个玩家的排名，这样就不必执行任何连接操作。每次重新计算排行榜时，玩家表也应该被更新。

- Alp

---

我知道我可以，但是对于数百万条目来说，这个更新需要很长时间才能执行，除非您知道一个可以显著减少执行时间的数据库/更新机制？ - Naatan

你可以尝试使用触发器。 - Alp

触发器如何减少被触发的查询的执行时间？另外，我不能简单地更新添加/更新的行的排名，因为这个排名会抵消其后面所有行的排名。 - Naatan

Answer 6

我可以想到两种方法来解决这个问题：

第一种方法：分批更新：

• 将分数排序，获得排名
• 按照排名将玩家分成批次，例如玩家0-999，玩家1000-1999等
• 对于每个批次，在现有表中删除与新数据冲突的条目。这意味着删除当前批次中的玩家或当前排名范围内排名的现有条目。然后将该批次的排名数据加载到数据库中，并在0.1秒后跳转到下一个批次。

第二种方法：新表

• 创建（或截断）一个与您现有排名表类似的新表。
• 计算新排名并插入您的数据
• 交换表格（最好在锁定它们之后）。这应该不到一秒钟。

- Seun Osewa