問  題

某海量用戶網(wǎng)站，用戶擁有積分，積分可能會(huì)在使用過程中隨時(shí)更新?，F(xiàn)在要為該網(wǎng)站設(shè)計(jì)一種算法，在每次用戶登錄時(shí)顯示其當(dāng)前積分排名。用戶***規(guī)模為2億；積分為非負(fù)整數(shù)，且小于100萬。

PS: 據(jù)說這是迅雷的一道面試題，不過問題本身具有很強(qiáng)的真實(shí)性，所以本文打算按照真實(shí)場(chǎng)景來考慮，而不局限于面試題的理想環(huán)境。

存儲(chǔ)結(jié)構(gòu)

首先，我們用一張用戶積分表user_score來保存用戶的積分信息。

表結(jié)構(gòu)：

示例數(shù)據(jù)：

下面的算法會(huì)基于這個(gè)基本的表結(jié)構(gòu)來進(jìn)行。

算法1：簡(jiǎn)單SQL查詢

首先，我們很容易想到用一條簡(jiǎn)單的SQL語(yǔ)句查詢出積分大于該用戶積分的用戶數(shù)量：

select 1 + count(t2.uid) as rank
from user_score t1, user_score t2
where t1.uid = @uid and t2.score > t1.score

對(duì)于4號(hào)用戶我們可以得到下面的結(jié)果：

算法特點(diǎn)

優(yōu)點(diǎn)：簡(jiǎn)單，利用了SQL的功能，不需要復(fù)雜的查詢邏輯，也不引入額外的存儲(chǔ)結(jié)構(gòu)，對(duì)小規(guī)模或性能要求不高的應(yīng)用不失為一種良好的解決方案。

缺點(diǎn)：需要對(duì)user_score表進(jìn)行全表掃描，還需要考慮到查詢的同時(shí)若有積分更新會(huì)對(duì)表造成鎖定，在海量數(shù)據(jù)規(guī)模和高并發(fā)的應(yīng)用中，性能是無法接受的。

算法2：均勻分區(qū)設(shè)計(jì)

在許多應(yīng)用中緩存是解決性能問題的重要途徑，我們自然會(huì)想能不能把用戶排名用Memcached緩存下來呢？不過再一想發(fā)現(xiàn)緩存似乎幫不上什么忙，因?yàn)橛脩襞琶且粋€(gè)全局性的統(tǒng)計(jì)性指標(biāo)，而并非用戶的私有屬性，其他用戶的積分變化可能會(huì)馬上影響到本用戶的排名。然而，真實(shí)的應(yīng)用中積分的變化其實(shí)也是有一定規(guī)律的，通常一個(gè)用戶的積分不會(huì)突然暴增暴減，一般用戶總是要在低分區(qū)混跡很長(zhǎng)一段時(shí)間才會(huì)慢慢升入高分區(qū)，也就是說用戶積分的分布總體說來是有區(qū)段的，我們進(jìn)一步注意到高分區(qū)用戶積分的細(xì)微變化其實(shí)對(duì)低分段用戶的排名影響不大。于是，我們可以想到按積分區(qū)段進(jìn)行統(tǒng)計(jì)的方法，引入一張分區(qū)積分表 score_range：

表結(jié)構(gòu)：

數(shù)據(jù)示例：

表示[from_score, to_score)區(qū)間有count個(gè)用戶。若我們按每1000分劃分一個(gè)區(qū)間則有[0, 1000), [1000, 2000), …, [999000, 1000000)這1000個(gè)區(qū)間，以后對(duì)用戶積分的更新要相應(yīng)地更新score_range表的區(qū)間值。在分區(qū)積分表的輔助下查詢積分為s的用戶的排名，可以首先確定其所屬區(qū)間，把高于s的積分區(qū)間的count值累加，然后再查詢出該用戶在本區(qū)間內(nèi)的排名，二者相加即可獲得用戶的排名。

乍一看，這個(gè)方法貌似通過區(qū)間聚合減少了查詢計(jì)算量，實(shí)則不然。***的問題在于如何查詢用戶在本區(qū)間內(nèi)的排名呢？如果是在算法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以內(nèi)，如果對(duì)score字段建立索引，我們期望本條SQL語(yǔ)句將通過索引大大減少掃描的user_score表的行數(shù)。不過真實(shí)情況并非如此，t2.score的范圍在1000以內(nèi)并不意味著該區(qū)間內(nèi)的用戶數(shù)也是1000，因?yàn)檫@里有積分相同的情況存在！二八定律告訴我們，前20%的低分區(qū)往往集中了80%的用戶，這就是說對(duì)于大量低分區(qū)用戶進(jìn)行區(qū)間內(nèi)排名查詢的性能遠(yuǎn)不及對(duì)少數(shù)的高分區(qū)用戶，所以在一般情況下這種分區(qū)方法不會(huì)帶來實(shí)質(zhì)性的性能提升。

算法特點(diǎn)

優(yōu)點(diǎn)：注意到了積分區(qū)間的存在，并通過預(yù)先聚合消除查詢的全表掃描。

缺點(diǎn)：積分非均勻分布的特點(diǎn)使得性能提升并不理想。

算法3：樹形分區(qū)設(shè)計(jì)

均勻分區(qū)查詢算法的失敗是由于積分分布的非均勻性，那么我們自然就會(huì)想，能不能按二八定律，把score_range表設(shè)計(jì)為非均勻區(qū)間呢？比如，把低分區(qū)劃密集一點(diǎn)，10分一個(gè)區(qū)間，然后逐漸變成100分，1000分，10000分 … 當(dāng)然，這不失為一種方法，不過這種分法有一定的隨意性，不容易把握好，而且整個(gè)系統(tǒng)的積分分布會(huì)隨著使用而逐漸發(fā)生變化，最初的較好的分區(qū)方法可能會(huì)變得不適應(yīng)未來的情況了。我們希望找到一種分區(qū)方法，既可以適應(yīng)積分非均勻性，又可以適應(yīng)系統(tǒng)積分分布的變化，這就是樹形分區(qū)。

我們可以把[0, 1,000,000)作為一級(jí)區(qū)間；再把一級(jí)區(qū)間分為兩個(gè)2級(jí)區(qū)間[0, 500,000), [500,000, 1,000,000)，然后把二級(jí)區(qū)間二分為4個(gè)3級(jí)區(qū)間[0, 250,000), [250,000, 500,000), [500,000, 750,000), [750,000, 1,000,000)，依此類推，最終我們會(huì)得到1,000,000個(gè)21級(jí)區(qū)間[0,1), [1,2) … [999,999, 1,000,000)。這實(shí)際上是把區(qū)間組織成了一種平衡二叉樹結(jié)構(gòu)，根結(jié)點(diǎn)代表一級(jí)區(qū)間，每個(gè)非葉子結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，左子結(jié)點(diǎn)代表低分區(qū)間，右子結(jié)點(diǎn)代表高分區(qū)間。樹形分區(qū)結(jié)構(gòu)需要在更新時(shí)保持一種不變量(Invariant)：非葉子結(jié)點(diǎn)的count值總是等于其左右子結(jié)點(diǎn)的count值之和。

以后，每次用戶積分有變化所需要更新的區(qū)間數(shù)量和積分變化量有關(guān)系，積分變化越小更新的區(qū)間層次越低?？傮w上，每次所需要更新的區(qū)間數(shù)量是用戶積分變量的log(n)級(jí)別的，也就是說如果用戶積分一次變化在***，更新區(qū)間的數(shù)量在二十這個(gè)級(jí)別。在這種樹形分區(qū)積分表的輔助下查詢積分為s的用戶排名，實(shí)際上是一個(gè)在區(qū)間樹上由上至下、由粗到細(xì)一步步明確s所在位置的過程。比如，對(duì)于積分499,000，我們用一個(gè)初值為0的排名變量來做累加；首先，它屬于1級(jí)區(qū)間的左子樹[0, 500,000)，那么該用戶排名應(yīng)該在右子樹[500,000, 1,000,000)的用戶數(shù)count之后，我們把該count值累加到該用戶排名變量，進(jìn)入下一級(jí)區(qū)間；其次，它屬于3級(jí)區(qū)間的[250,000, 500,000)，這是2級(jí)區(qū)間的右子樹，所以不用累加count到排名變量，直接進(jìn)入下一級(jí)區(qū)間；再次，它屬于4級(jí)區(qū)間的…；直到***我們把用戶積分精確定位在21級(jí)區(qū)間[499,000, 499,001)，整個(gè)累加過程完成，得出排名！

雖然，本算法的更新和查詢都涉及到若干個(gè)操作，但如果我們?yōu)閰^(qū)間的from_score和to_score建立索引，這些操作都是基于鍵的查詢和更新，不會(huì)產(chǎn)生表掃描，因此效率更高。另外，本算法并不依賴于關(guān)系數(shù)據(jù)模型和SQL運(yùn)算，可以輕易地改造為NoSQL等其他存儲(chǔ)方式，而基于鍵的操作也很容易引入緩存機(jī)制進(jìn)一步優(yōu)化性能。進(jìn)一步，我們可以估算一下樹形區(qū)間的數(shù)目大約為200,000,000，考慮每個(gè)結(jié)點(diǎn)的大小，整個(gè)結(jié)構(gòu)只占用幾十M空間。所以，我們完全可以在內(nèi)存建立區(qū)間樹結(jié)構(gòu)，并通過user_score表在O(n)的時(shí)間內(nèi)初始化區(qū)間樹，然后排名的查詢和更新操作都可以在內(nèi)存進(jìn)行。一般來講，同樣的算法，從數(shù)據(jù)庫(kù)到內(nèi)存算法的性能提升常?？梢赃_(dá)到10^5以上；因此，本算法可以達(dá)到非常高的性能。

算法特點(diǎn)

優(yōu)點(diǎn)：結(jié)構(gòu)穩(wěn)定，不受積分分布影響；每次查詢或更新的復(fù)雜度為積分***值的O(log(n))級(jí)別，且與用戶規(guī)模無關(guān)，可以應(yīng)對(duì)海量規(guī)模；不依賴于SQL，容易改造為NoSQL或內(nèi)存數(shù)據(jù)結(jié)構(gòu)。

缺點(diǎn)：算法相對(duì)更復(fù)雜。

算法4：積分排名數(shù)組

算法3雖然性能較高，達(dá)到了積分變化的O(log(n))的復(fù)雜度，但是實(shí)現(xiàn)上比較復(fù)雜。另外，O(log(n))的復(fù)雜度只在n特別大的時(shí)候才顯出它的優(yōu)勢(shì)，而實(shí)際應(yīng)用中積分的變化情況往往不會(huì)太大，這時(shí)和O(n)的算法相比往往沒有明顯的優(yōu)勢(shì)，甚至可能更慢。

考慮到這一情況，仔細(xì)觀察一下積分變化對(duì)排名的具體影響，可以發(fā)現(xiàn)某用戶的積分從s變?yōu)閟+n，積分小于s或者大于等于s+n的其他用戶排名實(shí)際上并不會(huì)受到影響，只有積分在[s,s+n)區(qū)間內(nèi)的用戶排名會(huì)下降1位。我們可以用于一個(gè)大小為100,000,000的數(shù)組表示積分和排名的對(duì)應(yīng)關(guān)系，其中rank[s]表示積分s所對(duì)應(yīng)的排名。初始化時(shí)，rank數(shù)組可以由user_score表在O(n)的復(fù)雜度內(nèi)計(jì)算而來。用戶排名的查詢和更新基于這個(gè)數(shù)組來進(jìn)行。查詢積分s所對(duì)應(yīng)的排名直接返回rank[s]即可，復(fù)雜度為O(1)；當(dāng)用戶積分從s變?yōu)閟+n，只需要把rank[s]到 rank[s+n-1]這n個(gè)元素的值增加1即可，復(fù)雜度為O(n)。

算法特點(diǎn)

優(yōu)點(diǎn)：積分排名數(shù)組比區(qū)間樹更簡(jiǎn)單，易于實(shí)現(xiàn)；排名查詢復(fù)雜度為O(1)；排名更新復(fù)雜度O(n)，在積分變化不大的情況下非常高效。

缺點(diǎn)：當(dāng)n比較大時(shí)，需要更新大量元素，效率不如算法3。

總  結(jié)

上面介紹了用戶積分排名的幾種算法，算法1簡(jiǎn)單易于理解和實(shí)現(xiàn)，適用于小規(guī)模和低并發(fā)應(yīng)用；算法3引入了更復(fù)雜的樹形分區(qū)結(jié)構(gòu)，但是 O(log(n))的復(fù)雜度性能優(yōu)越，可以應(yīng)用于海量規(guī)模和高并發(fā)；算法4采用簡(jiǎn)單的排名數(shù)組，易于實(shí)現(xiàn)，在積分變化不大的情況下性能不亞于算法3。本問題是一個(gè)開放性的問題，相信一定還有其他優(yōu)秀的算法和解決方案，歡迎探討！