海量用户的积分排序问题算法的分析

Question

表(user_score)的结构可以如下设计：

Algorithm 1

Thinking

通过使用一个简单的SQL语句查询出积分大于该用户积分的用户数量：

SELECT 1+ COUNT(t2.uid) AS rank FROM user_score t1, user_score t2 WHERE t1.uid = @uid AND t2.score > t1.score; 

Algorithm 2 均匀分区设计

Thinking

1. 用户排名是一个全局性的统计指标，而非用户的私有属性，缓存在这里并不适用。

2. 具体的进行问题分析：真实的用户积分变化是有一定规律的，通常用户积分都不会暴增暴减。一般用户都是在低分区，即用户积分的分布总体来说是有区段的。同时，高分区用户的细微变化对低分段用户排名影响不大。

3. 考虑按积分区段进行统计方法，引入分区积分表 score_range .

对用户积分的更新要相应地更新该表的区间值。在 score_range 的辅助下，查询积分为s的用户的排名，通过累加高积分区间的 count 值，再计算用户在本区间内的排名即可获得结果。

该方法貌似通过区间聚合减少了查询计算量。不过有问题是：如果查询用户在本区间内的排名呢？

SELECT 1+COUNT(t2.uid) AS rank FROM user_score t1, user_score t2 WHERE t1.uid = @uid AND t2.score > t1.score AND t2.score < @to_score; 

如果对 score 字段建立索引，我们期望该SQL语句将通过索引大大减少扫描的 user_score 表的行数。

不过根据二八定律，对于大量低分区用户进行区间内排名查询的性能不及对少数高分区用户进行查询。对于一般用户来讲，并没有实质性的性能提升。

Algorithm 3 树形分区设计

Thinking

再次考虑，是否可以按照二八定律，把 score_range 表设计为非均匀区间，把低分区划分密集一点。Eg:开始设置10分一个区间，然后区间逐渐变成100分，1000分……

不过该方法随机性较大，同时系统的积分分布会随着使用而逐渐变化。我们希望找到一种分区方法，既可以适应积分非均匀性，又可以适应系统积分分布的变化。这就是树形分区。

我们把[0, 1m)作为一级区间，再二分为两个2级区间[0, 500k), [500k, 1m)，以此类推，最终获得21级区间[0,1), ... , [999999,1m)。

每次用户积分有变化所需要更新的区间数量和积分变化量有关系，积分变化越小更新的区间层次越低。每次需要更新的区间数量是用户积分变量的 log n 级别。

在该积分表的辅助下查询积分为s的用户排名，实际上市在一个区间树上由上至下明确s所在位置的过程。s积分的排名即是排在他前面的区间的 count 的累加。

本算法的更新和查询都设计若干个操作，但如果为区间 from_score 和 to_score 建立索引，这些操作都是基于键的查询和更新，不会产生全表扫描。

同时该算法并不依赖关系数据模型和SQL运算，可以轻易地改造为NoSQL。而基于键的操作也很容易引入缓存机制进一步优化性能。

估算一下，树形区间的数目大约为 2billion 个，考虑每个节点的大小，整个结构只需要 几十m 空间。可以在内存建立区间树结构，，通过 user_score 表在 O(n) 时间内初始化区间树。