問題
某海量用戶網站，用戶擁有積分，積分可能會在使用過程中隨時更新。現(xiàn)在要為該網站設計一種算法，在每次用戶登錄時顯示其當前積分排名。用戶最大規(guī)模為2億；積分為非負整數(shù)，且小于100萬。
PS: 據(jù)說這是迅雷的一道面試題，不過問題本身具有很強的真實性，所以本文打算按照真實場景來考慮，而不局限于面試題的理想環(huán)境。
存儲結構
首先，我們用一張用戶積分表user_score來保存用戶的積分信息：
表結構：
示例數(shù)據(jù)：
下面的算法會基于這個基本的表結構來進行。
算法1：簡單SQL查詢
首先，我們很容易想到用一條簡單的SQL語句查詢出積分大于該用戶積分的用戶數(shù)量：
select 1 + count(t2.uid) as rank
from user_score t1, user_score t2
where t1.uid = @uid and t2.score > t1.score
對于4號用戶我們可以得到下面的結果：
算法1總結
優(yōu)點：簡單，利用了SQL的功能，不需要復雜的查詢邏輯，也不引入額外的存儲結構，對小規(guī)模或性能要求不高的應用不失為一種良好的解決方案。
缺點：需要對user_score表進行全表掃描，還需要考慮到查詢的同時若有積分更新會對表造成鎖定，在海量數(shù)據(jù)規(guī)模和高并發(fā)的應用中，性能是無法接受的。
算法2：均勻分區(qū)設計
在許多應用中緩存是解決性能問題的重要途徑，我們自然會想能不能把用戶排名用Memcached緩存下來呢？不過再一想發(fā)現(xiàn)緩存似乎幫不上什么忙，因為用戶排名是一個全局性的統(tǒng)計性指標，而并非用戶的私有屬性，其他用戶的積分變化可能會馬上影響到本用戶的排名。然而，真實的應用中積分的變化其實也是有一定規(guī)律的，通常一個用戶的積分不會突然暴增暴減，一般用戶總是要在低分區(qū)混跡很長一段時間才會慢慢升入高分區(qū)，也就是說用戶積分的分布總體說來是有區(qū)段的，我們進一步注意到高分區(qū)用戶積分的細微變化其實對低分段用戶的排名影響不大。于是，我們可以想到按積分區(qū)段進行統(tǒng)計的方法，引入一張分區(qū)積分表score_range：
表結構：
數(shù)據(jù)示例：
表示[from_score, to_score)區(qū)間有count個用戶。若我們按每1000分劃分一個區(qū)間則有[0, 1000), [1000, 2000), …, [999000, 1000000)這1000個區(qū)間，以后對用戶積分的更新要相應地更新score_range表的區(qū)間值。在分區(qū)積分表的輔助下查詢積分為s的用戶的排名，可以首先確定其所屬區(qū)間，把高于s的積分區(qū)間的count值累加，然后再查詢出該用戶在本區(qū)間內的排名，二者相加即可獲得用戶的排名。
乍一看，這個方法貌似通過區(qū)間聚合減少了查詢計算量，實則不然。最大的問題在于如何查詢用戶在本區(qū)間內的排名呢？如果是在算法1中的SQL中加上積分條件：
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
在理想情況下，由于把t2.score的范圍限制在了1000以內，如果對score字段建立索引，我們期望本條SQL語句將通過索引大大減少掃描的user_score表的行數(shù)。不過真實情況并非如此，t2.score的范圍在1000以內并不意味著該區(qū)間內的用戶數(shù)也是1000，因為這里有積分相同的情況存在！二八定律告訴我們，前20%的低分區(qū)往往集中了80%的用戶，這就是說對于大量低分區(qū)用戶進行區(qū)間內排名查詢的性能遠不及對少數(shù)的高分區(qū)用戶，所以在一般情況下這種分區(qū)方法不會帶來實質性的性能提升。
算法2總結
優(yōu)點：注意到了積分區(qū)間的存在，并通過預先聚合消除查詢的全表掃描
缺點：積分非均勻分布的特點使得性能提升并不理想
算法3：樹形分區(qū)設計
均勻分區(qū)查詢算法的失敗是由于積分分布的非均勻性，那么我們自然就會想，能不能按二八定律，把score_range表設計為非均勻區(qū)間呢？比如，把低分區(qū)劃密集一點，10分一個區(qū)間，然后逐漸變成100分，1000分，10000分 … 當然，這不失為一種方法，不過這種分法有一定的隨意性，不容易把握好，而且整個系統(tǒng)的積分分布會隨著使用而逐漸發(fā)生變化，最初的較好的分區(qū)方法可能會變得不適應未來的情況了。我們希望找到一種分區(qū)方法，既可以適應積分非均勻性，又可以適應系統(tǒng)積分分布的變化，這就是樹形分區(qū)。
我們可以把[0, 1,000,000)作為一級區(qū)間；再把一級區(qū)間分為兩個2級區(qū)間[0, 500,000), [500,000, 1,000,000)，然后把二級區(qū)間二分為4個3級區(qū)間[0, 250,000), [250,000, 500,000), [500,000, 750,000), [750,000, 1,000,000)，依此類推，最終我們會得到1,000,000個21級區(qū)間[0,1), [1,2) … [999,999, 1,000,000)。這實際上是把區(qū)間組織成了一種平衡二叉樹結構，根結點代表一級區(qū)間，每個非葉子結點有兩個子結點，左子結點代表低分區(qū)間，右子結點代表高分區(qū)間。樹形分區(qū)結構需要在更新時保持一種不變量(Invariant)：非葉子結點的count值總是等于其左右子結點的count值之和。
以后，每次用戶積分有變化所需要更新的區(qū)間數(shù)量和積分變化量有關系，積分變化越小更新的區(qū)間層次越低。總體上，每次所需要更新的區(qū)間數(shù)量是用戶積分變量的log(n)級別的，也就是說如果用戶積分一次變化在百萬級，更新區(qū)間的數(shù)量在二十這個級別。在這種樹形分區(qū)積分表的輔助下查詢積分為s的用戶排名，實際上是一個在區(qū)間樹上由上至下、由粗到細一步步明確s所在位置的過程。比如，對于積分499,000，我們用一個初值為0的排名變量來做累加；首先，它屬于1級區(qū)間的左子樹[0, 500,000)，那么該用戶排名應該在右子樹[500,000, 1,000,000)的用戶數(shù)count之后，我們把該count值累加到該用戶排名變量，進入下一級區(qū)間；其次，它屬于3級區(qū)間的[250,000, 500,000)，這是2級區(qū)間的右子樹，所以不用累加count到排名變量，直接進入下一級區(qū)間；再次，它屬于4級區(qū)間的…；直到最后我們把用戶積分精確定位在21級區(qū)間[499,000, 499,001)，整個累加過程完成，得出排名！
雖然，本算法的更新和查詢都涉及到若干個操作，但如果我們?yōu)閰^(qū)間的from_score和to_score建立索引，這些操作都是基于鍵的查詢和更新，不會產生表掃描，因此效率更高。另外，本算法并不依賴于關系數(shù)據(jù)模型和SQL運算，可以輕易地改造為NoSQL等其他存儲方式，而基于鍵的操作也很容易引入緩存機制進一步優(yōu)化性能。
算法3總結
優(yōu)點：結構穩(wěn)定，不受積分分布影響；每次查詢或更新的復雜度為積分最大值的log(n)級別，且與用戶規(guī)模無關，可以應對海量規(guī)模；不依賴于SQL，容易改造為NoSQL等其他存儲方式
缺點：算法相對更復雜
總結
上面介紹了用戶積分排名的3種算法，算法1簡單易于理解和實現(xiàn)，適用于小規(guī)模和低并發(fā)應用；算法3引入了更復雜的樹形分區(qū)結構，但是性能優(yōu)越，可以應用于海量規(guī)模和高并發(fā)。本問題是一個開放性的問題，相信一定還有其他優(yōu)秀的算法和解決方案，歡迎探討！