如何對遊戲伺服器全服玩家進行排名？

01-13

遇到需求，要求對全服的玩家，按照等級，金錢，戰力等屬性排名，然每個玩家知道自己所在的排名。
目前我所想到有兩種方式：
1.定時排序（幾個小時），使用std::sort，排序後，此數據是存放在內存中，然後同步保存到資料庫中（保存數據有其他線程處理）。
2.維護一個實時的有序鏈表，當玩家這幾個屬性發現變化時候，使用二分查找，找到玩家所在的節點，然後在查找應該存放的位置，也就是所需要查找兩次。

伺服器的玩家數據會隨著時間推移不斷變大，第一次處理這種問題，我感覺兩種方式感覺消耗比較大，請問大家遇到這種排名問題是怎麼處理的？

https://gist.github.com/chenshuo/1966839

居然有很多兄弟又是組件又是論文演算法。一看就不是做遊戲伺服器的或者實用系統的。你們以為是多大一個事情呀？

全服排名？請問你的服是多少人？

1000人？隨便你怎麼排。冒泡演算法都可以。

1000萬人？只要你的數據不是太大，更新頻道不是特別高，每次更新，或者定時更新的時候排序就可以了。紅黑樹大致也只用找20次。內存？64位的系統還要考慮內存。就算每個用戶256位元組。你算算才要多少數據？256*1000W=256*10M=2.5G。

但如果從架構上考慮，需要一台排序伺服器來做這個事情。其實這也就是樓主的方法2而已。

1億用戶？其實前面已經證明了。上面的方法是可以搞的。內存25G就可以了。一台機器也就可以了。

10億？全服能超過1億用戶的遊戲，中國目前數估計不超過10個。CF，DNF，LOL這類還是分區遊戲，不用考慮。主要是QQGAme的鬥地主，天天飛車，天天酷跑，天天愛消除這類手游產品。當年如果你成了這種產品，成本看上去不再是問題了。

增加10台機器好像也不是太大問題，只是架構上。。。。。好像更麻煩了。

那麼？

第一，你要那麼及時嗎？不要，直接上DB，一天導出一次就OK了。

第二，你要那麼準確嗎？忽悠用戶是否可以？直接做一個很細緻的分段出來就OK了。

還是一台伺服器就搞掂了。

100億？你不是在做遊戲把。。

最後的最後，請問一下你的策劃同學，當一個用戶看到自己是第2000W名的時候，他對這個排名的感想？

什麼年代了，還在用全區排序這種落後的設計。告訴你們的策劃，我很BS他們。

排好top100就好了，屌絲玩家排個鎚子哦，真要排也隨便個區間給他看看就好了，不要在意細節

你這個需求也許可以改改。

實際上遊戲上的排行榜，比如戰力，金幣等，大家只關注最前面的N名，沒有必要進行全服排序。沒到這個範圍的，可以提示比如」百名開外」這樣的用詞。

做了這個設計上的簡化之後，這就是一個堆排序的top N的問題了。

至於其他人提到的可以做全局排序的方案，你權且看看當開闊眼界吧。做產品的時候，還是先找平衡的方式實現需求，而不是為了炫技。

我是 @阮行止。

排序有兩種：離線排序和在線排序。

離線排序，就是給你一個數組，你把它排好序，然後萬事大吉。

這種排序直接std::sort，因此下面不談。

在線排序，要求你維護一個有序序列。在任意時刻可以進行插入、刪除、修改、查詢排名操作。

提供兩種思路。

一、平衡樹

平衡樹中，查詢一個節點的排名是 $O(log n)$ 的複雜度（對每個節點記下子樹大小）

題目描述中的有序鏈表思路，我懷疑題主根本沒有實現過。因為普通鏈表是不能二分的，需要使用「跳錶」——平衡樹的一種。

使用平衡樹，上述四種操作均可以 $O(log n)$ 完成。常數較大。

二、樹狀數組

首先明確「權值」的概念：w[i]記錄有多少個元素的值為i。譬如有序列[3,1,5,1,3]，則w[1]=2,w[3]=2,w[5]=1.

那麼，如果我們要查詢一個人的排名（他的分數為c），實際上是查詢有多少個人比他分數高——也就是查詢，比c大的權值和，即： $sum _{p>c}w[p]$ .

這就是一個區間和。只需要樹狀數組就能搞定。因此上面四種操作體現為：

如果一個人的分數為c。

插入：w[c]加1， $O(log n)$ .

刪除：w[c]減1， $O(log n)$ .

修改分數為d：w[c]減1，w[d]加1， $O(log n)$ .

查詢排名：輸出w[c+1,MAX]的區間和， $O(log n)$ .

由於樹狀數組常數小，因此比平衡樹稍快。

這個做法的特點是：無論有多少個人，我們都需要開MAX的空間，而且上面的 $n= ext{MAX}$ （值域大小）.

在人數很少或者值域很大的時候，這個演算法是不優秀的——前者浪費時間，後者浪費空間。

但如果值域小（例如，所有人的分數都在100000以內），權值樹狀數組的優勢會立刻體現出來：

即使有二十億個人，上面的n仍然控制在10w，時間優勢很大（平衡樹的這個n會變成20億）；空間仍然只佔用10w個int，不會由於人多而爆空間。

缺點是，值域不允許小數。（可以乘上10、100……來解決，然而這樣值域也會暴漲）

另，依照權值的思路，可以離線O(n)求出每個元素的排名——「桶排序」。

感謝被邀請。

關於需求：

既然是一個線上遊戲，那麼這個需求可以跟策劃談談，個人認為沒有任何必要做到實時全服玩家排序。

一方面，真的需要實時嗎，其實就算伺服器實時排序，然後玩家點開排行榜，客戶端去伺服器取到數據，這個過程中其實全服玩家的數據已經發生了變化對吧，而且這個變化其實玩家是不在意的。

既然這裡面一定存在一定時間差，那麼我們何不變成1分鐘更新一次或者5分鐘更新一次。不論是1分鐘還是5分鐘，只要不是實時排序，那麼伺服器端其實只要每個間隔跑一次排序就好。如有必要可以再維持一個記錄，記錄此間隔期間哪些用戶數據發生過變化，在已有的序列中重插下這些變化過的用戶數據即可。

另外一方面真的需要全服所有玩家的排行嗎，不知道你們一個伺服器的玩家數量控制在多少，但是在大部分情況下，排序前3000名足夠了。

如果真的想全部排序，那麼注意下玩家比例中很大一部分都屬於，剛玩就流失的，他們的數據可能就是等級1啊，等級10啊，其他值也不會太高。如果你們需要告訴每一個玩家自己的名次，讓他體會到從新手開始每一步的成長，直接弄一個統計，統計出來每一個排行裡面低等級各個階段的大致數量，給玩家的名次直接按這個統計值返回，玩家關鍵數據變化後就去伺服器取一個值的事。這個統計老服按天，新服更新頻率要高一些，按玩家分布具體來調整。

另外數據獲取方面，分頁取數據，取數據時間間隔之類就不多說了。

總之就是這個需求對遊戲來說是一個很小很小的需求，所以呢沒有特別的策劃考慮，沒有必要給伺服器增加太大的壓力。

雙向索引，初始化排序一次，之後實時小範圍冒泡排序。

桶排序？……算了，我不知道，錯了就摺疊我吧

我做了5年的遊戲伺服器開發，還是有則個回答這個問題的。直接用stl自帶的sort排序就行，因為一個區也就就幾十萬，上百萬玩家，開服的時候排一次序，平時一個伺服器活躍玩家也就幾千，頂多上萬，等級，金錢又變化進行事實排序，完全沒有問題。我們伺服器目前就是這麼做的，64位伺服器，32g內存，8核2g主頻的cpu

題主你首先要明確這麼幾個問題，才能進行設計：

1 運營進入穩定期後，單服玩家角色的總數量

2 單服最高在線人數

3 排行榜個數

我根據我們的數據說下思路：

1 &<1600萬個角色

2 &<60000人

3 &<128個

和策劃約定排行榜更新有兩個時機：定時和下線。定時更新周期暫定為1小時，根據玩家ID分散開。

每個角色的在每個排行榜的數據結構如下：

struct RANK_NODE

{

RANK_NODE* pPrev;

RANK_NODE* pNext;

RANK_NODE* pParent;

RANK_NODE* pLeft;

RANK_NODE* pRight;

INT64 llKey;

INT64 llValue;

INT32 nRank;

};

64bit時，整個結構60位元組。如果維護全部玩家的數據的話，內存佔用量為60 * 16M * 128，約為128GB。我們的策劃只需要前1000名，所以內存佔用只有60 * 1000 * 128，約為8MB。

這個結構中，pPrev和pNext將整排行榜里的角色用鏈表串起來，pParent、pLeft和pRight用來維護紅黑樹，llKey存儲對象ID（一般是角色ID，也可能是戰隊ID之類的），llValue存儲需要排序的數值（比如等級、經驗），nRank存儲第幾名。

當一個角色的新的數據發來時，我們先根據其角色ID用紅黑樹找到對應的排序節點，再根據新的數值

在鏈表中上下移動節點，一般數值變化都不會太大，移動的距離都是很短的。如果找不到排序節點，則從最後一名往前比。

redis zset就可以。

用參數化的辦法給分數的分布建個模型，比如正態分布。然後你只要維護那些參數就行了。

來個人要排名，代到模型里算一算，給個百分比。

最極端是情況是強行假設均勻分布，然後維護最大最小值。

坦克世界的xvm排名似乎就是用的正態分布。然後每天算一遍。

就是個，OI玩家們都會做的，演算法題，吧。

隨便一種平衡樹，記錄本子樹節點數，記錄父節點。

更新就刪掉再插入。

求自己的排名就一路向上，根據自己是不是右子節點，判斷是否加上左子樹大小。

（剛剛腦抽，直接用分數來查找也可以，只是只能log時間得到lower_bound而不是現在在樹中的真正排名位置（其實一定程度上也該這樣，並列的，都算最高的那一個排名嘛））

完畢。

題主原諒我刷你的屏，實在是我動腦子之後就是停不下來的節奏（ＴДＴ）

剛剛又想了想，感覺之前的回答有點沒看清題目作答的意思。

我這裡有一個比較簡單的答案，前提是題主對於登錄時長的精度只到秒級別。

一天一共多少秒嘛，24×60×60＝86400秒

那麼設定數組time(1 to 86400)

對於每個元素time(i)的值所代表的含義是登錄時長為i秒的用戶的數量

按照這個意思，其實就很簡單了。

對於登錄時長為i的用戶的排名可以用如下VB演算法計算

rank = 0

For timesec = 1 to i

rank = rank + time(timesec)

只要累加幾次就行了，這樣是不是很簡單？

ヾ(*′?｀*)?

——————————我還是令人作嘔的分割線——————————剛剛在公交車上作答，現在回來補充一下

對於其他的我其實沒什麼想說的，雖然我不是什麼計算機專業的，僅為拋磚引玉之用。以下回答可能有時偏頗，還請題主和知友指出（求輕拍，答主心靈脆弱……～～）

關於最初的排序演算法，因為實在有太多了，我就不啰嗦了。

答主比較關心登錄時顯示排名這個問題，我就來說說我的幾點看法。

對於一個已經排序的有n個元素的數組s()，答主想要給他post一個值，然後返回其排名，有著很多演算法。

第一部分（沒有索引）

一、逐個比較

最容易理解的就是逐個比較，不過效率實在不高，搞不好要比較n-1次，排除。

二、二分法或者多分法

最簡單的二分法為例：因為s()已經是排好順序的了，所以二分法最差的情況只要比較log2(n)次，就能得到排名，比n-1好很多了吧。繼續尋找最優演算法。

三、正態分布預測法

其實這個方法是我自xia創bai的。

先來說說他是怎麼一回事。

首先，因為題主的問題是登錄時間排名的問題，再加上已經存在了一個s()，所以我在這裡姑且認為n較大（其實上千就行了）。然後在後台空閑的時候大致計算出一個擬合度較好的正態分布函數f(x)，假設f(x)函數圖像如圖

（原諒我又秀了一次下限，沒辦法重度手機控(￣(エ)￣)ゞ）

橫軸代表登錄時間，縱軸代表分布概率或者絕對量。

1、首先我們也是post一個登錄時間X給f(y)〔f(y)是f(x)的反函數〕然後返回一個精確的值X"，然後根據一個保守設定的σ分別計算f(x-σ)和f(x+σ)並與X比較。〔如果都是大於或者小於的可以再擴大至f(x-2σ)或f(x+2σ)〕確定好一個比較小的區間之後，再用二分法去精確找值就行了。

假使我們之用一次這個正態分布函數，那麼我們將最多只用比較4次〔即擴大到f(x-2σ)或f(x+2σ)〕即可確定一個區間，具體大小我懶得去算了（也不太會囧rz）這樣在很大數據量下我覺得還是比二分法要快很多的。當然這也取決於你的正態函數擬合度高低。

第二部分（帶索引）

其實這個真和不帶索引的差不多，不過既然展開了，我就稍微談談我自己的理解。

所謂帶索引，就是在s()中特定的位置加入幾個指示標誌而已。例如書籤一般

要在厚厚的一本書中找到之前讀的第XX頁，最二的不就是一頁一頁去找么……

有了這個東西，一本幾十萬頁的書，插幾個書籤指示特定的章節之後，找位置那還不so easy嗎？

不過書籤（索引）的分布也是有講究的，和前面的正態分布結合起來的話估計會事半功倍吧，分布多的地方多方書籤，少的地方少放幾個。嗯嗯，就是醬紫的。

至於具體演算法嘛，我覺得題主比我要精通多了，我這種徘徊在業務邊緣的渣渣就不在這獻醜了～～

另外我是真的只對比過幾個什麼冒泡排序，二分法排序這類的簡單到爆的排序方法的效率，真心不好意思拿出來說，而且這些方法根據源數據的特點不同，它的效率也不同，這個就有待題主自己去決定了。

答題沒有匿名的習慣，不匿了。只求輕拍，謝謝了。

———————————沒錯，我就是討厭的分割線—————————————

我覺得它只用排一次序啊，第一次排好了，接下來只要插值不就行了？

我覺得二分法插值或者一些比較常規的演算法不也挺快的么？

另外好的伺服器都是專業的企業解決方案，動不動就是N多核心，硬碟組個RAID(Redundan Array of Inexpensive Disk)列陣性能提升看得見啊，答主怎麼能用常規的個人電腦思維去考慮呢？

鏈表不能二分的...

參見：

【ZJOI2006】GameZ遊戲排名系統

【HAOI2008】排名系統

（兩道題一模一樣的說）

以前策劃就提出過這樣的需求。

目前方案使用過redis中的zset，不過zset有個問題，只能是score對應一個string，兩個相同的score，是根據sring的字母順序來排序，所以string的生成比較重要，並且將其他信息保存在資料庫中。

有人建議過c++直接使用伺服器內存，這個時候如果涉及到多台伺服器需要維護一個排行榜，則就在一個伺服器中建立排行榜，其他的與該伺服器通信。

做遊戲以來一直需要考慮的問題。。。

最近看redis的源碼，裡面有個zset，可以實現題主的要求。zset的實現是skiplist https://zh.wikipedia.org/wiki/%E8%B7%B3%E8%B7%83%E5%88%97%E8%A1%A8

skiplist的增刪改查的時間複雜度都是O(logN)，針對某一個排名範圍[max, min]的查詢，時間複雜度是O(logN + max - min)，存儲的空間複雜度是O(N)，可以查詢某一個排名範圍的所有數據。

redis中zset的比較是先優先比較score值，再比較key的值。在遊戲中，通常不會這麼簡單，所以需要自己設計score的計算表達式。

比如說，我們會有需求設計戰鬥力排行榜。先比較戰鬥力，如果相同，再比較玩家等級，如果等級也相同，再比較出生時間。這樣一來，你的score計算式需要設計的比較精巧，而且會隨著開發需要不斷調整。

考慮到跨平台和跨語言使用，參考redis的源碼，自己用C寫了一個類似的skiplist，可以自定義比較函數。並實現了lua的庫綁定。

目前在macOS 64bit 2.5GHz Intel Core i5上做了一些測試：

1000k次隨機插入 1.2 seconds

1000k次隨機查詢 0.3seconds

通常情況下可以滿足大部分遊戲的需求，換成bind給lua的庫，效率大概是C版本的1/10

rocaltair/skiplist

cloudwu有寫陌陌爭霸？排行榜的排序問題的post，你可以參考下。

redis.zset，桶排序

set就可以吧插入刪除logn複雜度應該夠了吧