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