海量用戶的積分排序問題算法的分析

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) 時間內初始化區間樹。

Algorithm 4 積分排名數組

Thinking

Algo3的時間復雜度只在n特別大的時候才具有優勢，而實際應用中積分的變化情況往往不大，這時和 O(n) 算法相比沒有明顯優勢。

仔細觀察積分變化對于排名的影響，可以發現某用戶的積分從s變為s+n，只有積分在 [s, s+n) 區間的用戶排名會下降1名。我們可以用一個大小為1M的數組表示積分和排名的對應關系， rank[s] 表示積分s所對應的排名。初始化時，rank數組可以由 user_score 表在 O(n) 的復雜度內計算而來。查詢積分s所對應的排名直接返回 rank[s] 即可，當用戶積分從s變為s+n，只需要把 rank[s] 到 rank[s+n-1] 這n個元素的值加1即可，復雜度為 O(n) 。

參考

1. 某年某月的《碼農》期刊