用MySQL实现排行榜

问题的引出

开发产品时（特别是在游戏中）时常会出现诸如“实时计算用户积分并且显示排名”的需求。 针对这类需求，往往会有多种多样的实现方式，接下来谈谈机种常见的解决方式。

问题的一般分类及对策

这些东西一般需求方是不会提出来的。 如果自己不主动挖掘，往往会在第一时间就错过最好的解决方案。

个人认为数据的变动特点是影响这类问题解决方案最重要的要素。
其分类和解决思路如下：

• 读写都少 这种情况其实没有讨论的必要。
• 写多读少（或者读写分开在不同时段的情况） 这种情况通常比较少见。因为很难想象一个排行榜做出来居然读请求比写请求少。 一个可能的情况是，读写请求分的比较开，或者可以通过某种手段将两类请求错开。 针对这种情况，一个比较自然的考虑就是——“线下计算，线上查询”。 这种做法的好处显而易见，如果在一个时间段内读请求少的可以忽略而基本上是写请求的话。 那么显然应该将计算资源投入在分数和排名的计算而不是为读取做优化上。 等到更新结束开放读取时，缓存和索引基本已经就绪，即使是大量的数据也可以在短时间内响应。 典型的例子就是搜索引擎，但是这个并不是本文主要的讨论范围。
• 读多写少 这种情况应该比较常见。（毕竟一个积分榜就应该长成这个样子） 这种情况的特点是更新和读取掺杂在一起。 而且更新操作会直接改变读取操作的结果因此不能视而不见。 对于这类情况，只能线上实时更新和读取。 所以必须采取方法进行优化。
• 读写都多 上一种状况的升级版，说实话比较少见。 个人更推荐在设计阶段想办法把这种问题转化成前面两类问题，这样可以省不少麻烦。 当然解决的办法有是有，只不过优先考虑成本更低的更容易解决的方式总是好的。

排行榜类问题的基本特征

• 以纯数字排序为主
• 数据量较大，一般是百万量级以上
• 因为涉及到线上查询，所以对响应时间的要求较高。(应该维持在<1s的量级)
• 大多不会为了解决这个问题投入很多的资源（因此这里只讨论在DB里实现排行榜的方法）

1. 统一积分排名模式

类似于Game Center的模式。 每一个玩家有一个积分的属性。 在这个属性上建索引，计算得到玩家排名。

SELECT	count(*) + 1 AS rank
  FROM	user_ranking
  WHERE	pt > ?

如果用户数量在10万量级以内，那么这个方法应该是毫无压力。 但是很显然的，这个查询的响应时间会随着用户量的增长急剧增长。

针对这种情况，一个很简单的优化方法是使用覆盖索引。 注意mysql explain之后是否出现了”using index”。 对于百万数据量级的查询，使用覆盖索引可以将响应时间控制在平均300ms左右。 但是对于排名比较靠后，分数比较少的查询而言，最开始的几次查询效率会接近于全表count，响应时间超过1s，实际上不是很理想。 时间代价上虽然说不上很理想，但是配合缓存和对于精度的模糊处理仍然可以应对大部分此类需求。

• 查询效率: O(n)

• 更新效率: O(1)

• 优点
  • 简单、容易实现
• 缺点
  • 不适用于数据较多的情况
  • 查询效率低、响应时间较慢

2. 分段积分排名模式

针对第一种积分榜最常采用的优化方法就是分段排名。 顾名思义就是将用户划分为数段，在段内对用户进行排名。 在需要的情况下组合成各段的总排名。

SELECT	count(*) + 1 AS rank
  FROM	user_ranking
  WHERE pt >= 1000
	AND	pt <  2000
	AND pt > ?

这样做的好处是极大的缩减了需要count的记录条数，缩短响应时间。 坏处是需要额外维护一张表，记录每个区段各有多少用户。 如果用户的跨区间变动比较频繁的话维护的开销会比较大。

并且区间的划分也是一个需要考虑的问题。 一般而言，根据80/20原则，分数比较低的区段需要多划分以平衡每个区段的用户量，比如：

>10000pt 每10000pt一段
>1000pt  每1000pt一段
>100pt   每100pt一段
<=100pt  独立一段

当然，实际的分段策略要根据用户的分布而定，需要逐步调整。

可以用MySQL的Partition功能对于这种方法稍作改进，但是无法在时间上取得更好的效果。 在200~300ms的量级，使用partition是可以一定程度改善最坏情况，但是没有办法让查询变得更快。

• 查询效率: O(n/m) + O(m) + C (可以看到，m的最佳取值是n^(1/2))

• 更新效率: C * O(1)

• 优点
  • 查询响应时间较快，但没有数量级上的改善
  • 可以进一步提升能够支持的数据量
• 缺点
  • 有额外的分区表维护成本
  • 处理逻辑稍复杂
  • 分段逻辑需要在实际环境下进行调整

3. 交换排名模式

交换排名模式仅适用于排名由强弱关系而非具体分数决定的场合。 用户的强弱由用户间的胜败关系决定。 排名低的用户可以向排名高的用户挑战，如果胜则交换排名。

• 查询效率: O(1)

• 更新效率: O(1)

• 优点
  • 单表可以支持的数据量最大
  • 查询响应时间最快
  • 最大限度的减小了排行榜的维护代价
• 缺点
  • 如果更新操作频繁则会产生同步问题
  • 适用范围有限

4. 混合排名模式

可以理解为前两种的混合体。 动态的将用户分为若干动态组，用户在小组之间的迁移只能够通过交换实现。 小组之内用户的位次由积分决定。例如:

user_id win_num pt
12345	4 		350
12346	4 		353
02345	3 		153
02344	3 		253
00344	1 		53

上边的这个例子中，胜利场数即为分组的基准。 3胜组的用户只可以向4胜组用户挑战，胜则交换所在小组。 这样在查询的时候首先根据胜利场数对用户进行划分， 然后在对各组之内的用户计算其组内排名。

• 查询效率: O(1) + O(n/M) (M » m)

• 更新效率: 组间 C * O(1); 组内 O(1)

• 优点
  • 可以支持的数据量较大
  • 查询响应时间比较快
  • 与分段积分模式相比，维护成本较小
• 缺点
  • 需要有多参数辅助排名，参数的区分度（基数）需要斟酌
  • 排名比较靠后的位置会有用户聚集现象，需要另行优化

同样是混合排名方法，我们可以将上边的做法反过来。 在组内用胜败关系决定位次，用积分决定分到哪个组。

• 查询效率: C * O(1)

• 更新效率: 组间 C * O(1); 组内 O(1)

• 优点
  • 可以支持的数据量最大
  • 查询响应时间非常快
  • 每个组不限制数量，查询无负担
  • 不需要多参数辅助排名
• 缺点
  • 需要设定以及调整分组条件，有额外的维护成本

总结

• 如果以积分为基准的做排行榜，则一定需要count才能决定位次，复杂度是O(n)
  • 需要考虑限制count数据集的大小
  • 需要考虑缓存之前count过的结果
  • 需要考虑提供不那么精确的结果
  • 需要考虑实现层面的优化（覆盖索引等等）
• 以胜败关系为基准的排行榜，复杂度是O(1)，但是适用范围有限