一個mmorpg游戲，玩家眾多，需要對玩家戰斗力進行排行，并且戰斗力變化時需要及時刷新。需要設計一個這樣的排行榜。
關于海量數據排行榜的做法，云風在他的博客里給過思路，談談陌陌爭霸在數據庫方面踩過的坑(排行榜篇)。主要思路是利用桶排序思路，對于大量相同分數玩家的處理則直接劃歸為同一等級。即游戲排行榜主要是對前n名玩家進行插入排序，這里的n可以取幾百或更多，這樣大為減少了排序壓力。
陌陌爭霸怎樣做排行榜的？
在上一篇里就有同學問道，如果你們不用數據庫，怎么做排行榜呢？ 其實我在上一篇正文里就有解答：
“服務器只是在不斷的創造新數據并讓這些數據在內存中流通而已，它沒有任何需要從外部讀取數據。如果內存無限大，且服務器永遠不會當機，數據庫這個設施沒有存在的必要。”
排行榜單也是數據之一，游戲服務器開服一刻起，沒有任何玩家有排名信息。隨著玩家名次更替，榜單才逐步形成。我們只需要在玩家分數變化的時候同步榜單的變化即可。而玩家查詢僅僅是取走有序的榜單而已。
你看，這個過程和數據庫無關不是？需要設計的是調整榜單的算法，和榜單的數據結構以保證維持榜單的性能足夠強就好了。因為玩家名詞更替的頻率遠小于玩家網絡包的頻率，那么這個模塊的處理能力所需要的下限很容易滿足。我們不用考慮處理不過來的情況。
針對陌陌爭霸我們是這樣做的：
陌陌爭霸中用于排名的分數區間不大，也就是 0 分到 5000 分。而參與排名的人數眾多，數以百萬計。對百萬用戶做插入排序，每個插入即使是 O(N) 的也不可接受。可事實是大量玩家的分數相同，都是并列排名的。所以我們只需要做 5000 個桶，每個桶里僅記錄這個分數有多少個人就可以了。
當玩家分數變遷，把原來的桶減一，新的桶加一。這個操作就是 O(1) 的。
而排行榜的查詢僅需要把當前分數靠前的桶累加，就能獲知查詢者的名次。對于上百萬玩家，看到哪些人和你并列的人的名字是沒有意義的。這個查詢雖然是 O(n) 復雜度，但 n 只有區區 5000 ，還可以做 cache 以應對查詢頻率遠高于更新頻率的情況。
真正需要精確知道人名的是榜單的前 200 個人，而對前 200 個人做插入排序也很快，所以并不會造成性能問題。
我們在系統的單點做排行榜的維持，完全沒有外部數據庫操作，它只是一小段操作普通內存結構的 c 代碼。而這個單點遠遠成為不了整個系統的熱點。
我們在系統臨時退出時，把已經排好的榜單落地，下次啟動的時候恢復。但也不必完全信任落地的數據，可以用離線腳本檢索整個數據庫重新生成一份正確的榜單。所以數據庫中的榜單只是被 cache 起來而已，系統運行期間是不需要寫入數據庫的，也不用擔心數據丟失。
關于桶排序，貼一個wikepedia的簡要算法介紹：
桶排序 (Bucket sort)或所謂的箱排序，是一個排序算法，工作的原理是將數組分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
桶排序以下列程序進行：
- 設置一個定量的數組當作空桶子。
- 尋訪序列，并且把項目一個一個放到對應的桶子去。
- 對每個不是空的桶子進行排序。
- 從不是空的桶子里把項目再放回原來的序列中。
偽代碼如下：
思路比較簡單，每個桶使用鏈表，插入至相應桶（鏈表）時保持有序，排序時歸并鏈表。c++實現如下：
假設數據分布在［0，100）之間，每個桶內部用鏈表表示，在數據入桶的同時插入排序。 然后把各個桶中的數據合并。
#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;
struct ListNode{
explicit ListNode(int i=0):mData(i),mNext(NULL){}
ListNode* mNext;
int mData;
};
ListNode* insert(ListNode* head,int val){
ListNode dummyNode;
ListNode *newNode = new ListNode(val);
ListNode *pre,*curr;
dummyNode.mNext = head;
pre = &dummyNode;
curr = head;
while(NULL!=curr && curr->mData<=val){
pre = curr;
curr = curr->mNext;
}
newNode->mNext = curr;
pre->mNext = newNode;
return dummyNode.mNext;
}
ListNode* Merge(ListNode *head1,ListNode *head2){
ListNode dummyNode;
ListNode *dummy = &dummyNode;
while(NULL!=head1 && NULL!=head2){
if(head1->mData <= head2->mData){
dummy->mNext = head1;
head1 = head1->mNext;
}else{
dummy->mNext = head2;
head2 = head2->mNext;
}
dummy = dummy->mNext;
}
if(NULL!=head1) dummy->mNext = head1;
if(NULL!=head2) dummy->mNext = head2;
return dummyNode.mNext;
}
void BucketSort(int n,int arr[]){
vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
for(int i=0;i<n;++i){
int index = arr[i]/BUCKET_NUM;
ListNode *head = buckets.at(index);
buckets.at(index) = insert(head,arr[i]);
}
ListNode *head = buckets.at(0);
for(int i=1;i<BUCKET_NUM;++i){
head = Merge(head,buckets.at(i));
}
for(int i=0;i<n;++i){
arr[i] = head->mData;
head = head->mNext;
}
}
文章列表
留言列表
