阿巴可懂的實時排行榜系統(tǒng)設(shè)計和實現(xiàn)思路。

大家好，我是魚皮，暑假快到了，我的老弟小阿巴聽說我家有很多好康的，就跑來找我玩。

結(jié)果我擺出了幾個以前開發(fā)過的小系統(tǒng)，準備在這段時間帶著小阿巴多做些作品，學(xué)習(xí)編程項目的設(shè)計思路。這樣等他開學(xué)了，就可以更輕松地跟著老師做做項目了。

今天，就先帶他做一個很常見的小功能：用戶實時積分排行榜。

實時積分排行榜

需求

先描述下需求，在我的編程導(dǎo)航項目（https://www.code-nav.cn）中，為了鼓勵大家共同維護網(wǎng)站，用戶可以通過推薦資源、積極評論、舉報違規(guī)資源等方式獲取積分。

為了進一步激勵大家，網(wǎng)站需要提供一個用戶積分排行榜，分為 實時總積分榜 、 周榜 和 月榜，均 只取前 10 名 。所有用戶都能夠查看當前排行榜，以及查看自己的 實時 總積分排名，后續(xù)管理員就可以給上榜用戶頒發(fā)獎品了。

效果如下圖：

點擊 我的排名 按鈕，可以查看自己的實時排名：

本文篇幅有限，先僅討論 實時總積分榜 的設(shè)計實現(xiàn)。

聽了需求后，小阿巴爽朗一笑：這有啥難的？且讓我設(shè)計一波，再給你娓娓道來。

設(shè)計實現(xiàn)

先看下數(shù)據(jù)庫的結(jié)構(gòu)，總共有 2 個表：用戶表 和 用戶積分表。

用戶表存儲了用戶信息，以及用戶的總積分（實時更新），也就是說總積分榜需要的數(shù)據(jù)可以直接從這里取到，不需要再去計算。

用戶表內(nèi)容：

用戶 id用戶名積分（score）1小阿巴102李魚皮10003小李100......

100李老熱66

如果要取前 10 名，只需要把所有用戶的信息先取出來，再排個序就好啦，寫 SQL 語句查詢的話就是：

select?*?from?`user`?order?by?score;


然后如果要取自己的總排名，就對查到的有序數(shù)據(jù)進行一次遍歷，找到自己所在的位置下標就行，偽代碼如下：

//?從數(shù)據(jù)庫查詢?nèi)坑脩袅斜?/span>
list?=?getAllDataList()
for(i?=?0;?i?<?total;?i++)?{
??//?找到自己的位置
??if(list[i].id?==?'我的id')?{
????return?i?+?1;
??}
}


小阿巴得意到：這不就實現(xiàn)總積分榜了么？你這需求太簡單，嘖嘖。

我笑到：還不錯，總積分榜的思路是正確的，起碼知道要對所有的數(shù)據(jù)進行排序。但如果用戶數(shù)特別多呢？比如幾十萬個，你只需要查自己的總排名，還需要把全部的數(shù)據(jù)都做一個排序么？

小阿巴陷入沉思，想了半天，沒想出來。

于是我提示到：假如在一次考試中你想知道自己的排名，是不是只需要知道有多少人的分數(shù)比自己高就行了，不用去管其他人排第幾對吧？

小阿巴一拍腦袋：對啊，我只需要先查出自己的分數(shù)，然后統(tǒng)計分數(shù)大于我的用戶數(shù)量，不就知道自己的排名了？

先用 SQL 語句查出用戶的分數(shù)：

/*?只取需要的列?*/
select?score?as?myScore
from?`user`
where?id?=?"用戶?id";


然后再用 SQL 語句統(tǒng)計分數(shù)大于該用戶分數(shù)的數(shù)量：

select?count(*)?from?`user`
where?score?>?myScore;


最后只需要將該查詢結(jié)果加 1，就是自己的排名啦~

小阿巴感嘆到：原來轉(zhuǎn)換一點點思路，就能省去多余的排序帶來的性能開銷，起飛~

更多思考

魚皮：先別起飛，其實對于一般用戶量的系統(tǒng)，上面的方案就已經(jīng)足夠了。下面讓我們加大難度，假如用戶數(shù)再多一點點呢，比如說一億個，怎么實時獲取前 10 名呢？

小阿巴：還真是 “億點點”，就您那破編程導(dǎo)航還想著有一億個用戶？

魚皮：少廢話，夢想還是要有的，萬一有億個用戶呢？快想想系統(tǒng)怎么做！

小阿巴：且不說對一億個數(shù)據(jù)排序有多慢，能不能存的下都是個問題啊。。。啊，等等，這難道就是面試常見的 Top N 問題！

魚皮：不錯，我面試的時候被問過好幾次 Top N 問題，如何從海量數(shù)據(jù)中找出前 N 個數(shù)呢？

小阿巴：這我完全不懂啊，算法不會，真要命。

魚皮：其實 Top N 問題的核心在于保證空間和時間復(fù)雜度，先要考慮數(shù)據(jù)能存入內(nèi)存運算，在怎樣算得更快。

通常 Top N 問題有下列幾種解決方案。

Top N 解決方案

全部排序

直接對所有數(shù)據(jù)進行排序（快排等），缺點是需要將數(shù)據(jù)一次性加載到內(nèi)存中。

局部淘汰

內(nèi)存中維護一個大小為 N 的容器，再讓剩余的數(shù)一個個進入容器，并淘汰容器內(nèi)的最小值。最終容器內(nèi)剩下的數(shù)就是前 N 名。優(yōu)點是能節(jié)省內(nèi)存，缺點是太慢了。

分治

把數(shù)據(jù)分為多個小組，小組內(nèi)先分別選出前 N 名小組長，最后再讓這些小組長同臺競技，選出最終的前 N 名。

哈希預(yù)處理

假如數(shù)據(jù)重復(fù)度很高，可以通過 hash 的方式，去掉很多重復(fù)數(shù)據(jù)。比如 1 億個數(shù)據(jù)里，一半是 0，一半是 1，那么取前 10 名時，可以直接淘汰掉另一半為 0 的數(shù)據(jù)。

但是預(yù)處理本身也需要時間和空間，這就需要我們對數(shù)據(jù)的重復(fù)度有一個清晰的判斷，否則自作聰明、適得其反。

小根堆

面試算法中的高頻考點 —— 堆排序，可以先取前 N 個數(shù)組成小根堆，堆頂始終是最小值。 然后遍歷后續(xù)數(shù)字，大于堆頂就替換掉堆頂并調(diào)整最小堆結(jié)構(gòu)。該算法時間復(fù)雜度和空間復(fù)雜度（為 N，常數(shù)）都不錯，所以必須要掌握。

但是具體選擇哪種方案呢？還是要結(jié)合我們實際的項目和業(yè)務(wù)場景來分析。

實際解決

由于我們的數(shù)據(jù)庫來記錄積分，所以當用戶量級很大時，首先要 分庫分表 ，通常是水平分表，根據(jù)一定規(guī)則（比如 id）把用戶數(shù)據(jù)行分批存儲在多個數(shù)據(jù)表中。

然后就和大數(shù)據(jù) Map / Reduce 處理機制一樣了，可以采用 分治 的方式 并行計算 每個表的前 10 名（map），都計算好后，再匯總到一起計算最終的前 10 名（reduce）。

用這種方式，別說 1 億了，2 億、3 億的計算模式都是一樣的，加機器水平擴容就好了~

所以遇到 Top N 問題的時候，大家可以先答一下上面的幾種方案，再結(jié)合具體的場景分析，分治和最小堆是我覺得相對 核心 的點。

Redis

最后，對于實時排行榜的設(shè)計，肯定很多背過八股文面試題的朋友在第一時間會想到使用 Redis 的有序集合 zset，的確也是一種方案，但也要結(jié)合場景去分析利弊，不要秒答。

使用基于內(nèi)存的 Redis zset 的確運算更快，且天然支持排序、使用方便。但數(shù)據(jù)量大時同樣面臨數(shù)據(jù)更新、維護、同步、持久化存儲等問題，而且對于我們這種實時性要求不高的需求來說，有些大材小用了哈哈。

我是魚皮，肝文不易，點贊 還是要求一下的，祝大家都能心想事成、發(fā)大財、行大運。

最后再送大家一些 幫助我拿到大廠 offer 的學(xué)習(xí)資源 ，視頻教程 + 習(xí)題 + 答案 + 源碼、編程書籍、大廠面經(jīng)、實戰(zhàn)項目等。

指路：跑了，留下 6T 的資源！(https://t.1yb.co/qOJG)

我是如何從零開始通過自學(xué)，拿到騰訊、字節(jié)等大廠 offer 的，可以看這篇文章，不再迷茫！

指路：我學(xué)計算機的四年，共勉！(https://t.1yb.co/q0mS)