Java游戏服务器-百万规模实时排行榜实现

有人的地方就有对比，游戏中自然也少不了排行榜。

当前项目设计目标是，每个服务器玩家数量为百万左右。每个玩家都有战力、经验等属性，战力最大值在50万以内。

现在期望能有战力排行榜，有以下几点需求：

• 全部角色参与排行，能实时知道某个角色的排名
• 排行榜显示前100名玩家详情

排名规则是战力越高排名越前，战力相同则比较经验，经验再相同则比较创建时间。

排行榜算法并不少见，这篇文章介绍的就不错。根据上述需求分析，最适合采用文中的算法3，即树形分区设计，具体算法文中有详细介绍。

采用该算法，时间复杂度在O(log(n))，在百万规模下空间消耗也就几十M。但有两个问题待解决：

• 战力相同时如何确定具体排名
• 如何获得TOP N

针对问题1，假定游戏设计的战力相对均匀（尽管高战力显然更分散），那么战力相同的玩家数量会在一个较小规模内。依然以战力构建排行树，相同战力为同一个节点。节点可以存在一个有序列表，以经验、创建时间排序。这里有个小技巧，以玩家ID等效于创建时间，就直接记录了相应玩家，同时也保证了唯一性。这在增加删除（排名改变时）尤为有用。

针对问题2，排行树算法决定了最终战力节点都是叶子节点，同时在叶子节点层，战力总是从左向右递增的。在树构建过程中，可以分别使用一个前向和后向节点，将所有叶子节点连成一个双向链表。这样就可以做到既能得到前N名，也可以得到后N名，时间复杂度都是O(N)。

下面show the code，完整代码请参看文末。

 public class LeaderboardTree<Extra extends LeaderboardExtra> {   class LeaderboardNode {   public int lowerKey = 0;   public int upperKey = 0;   public int number = 0;    public ArrayList<Extra> extraList = new ArrayList<Extra>();    public LeaderboardNode left = null;   public LeaderboardNode right = null;    public LeaderboardNode prev = null;   public LeaderboardNode next = null;  }   LeaderboardNode root = null;   LeaderboardNode head = null;  LeaderboardNode tail = null;   public void setup(int lowerKey, int upperKey) {   root = setupNode(root, lowerKey, upperKey);  }   public void insert(int score, Extra extra) {   insertIntoNode(root, score, extra);  }   public void remove(int score, Extra extra) {   removeFromNode(root, score, extra);  }   public void change(int oldKey, int newKey, Extra extra) {   remove(oldKey, extra);   insert(newKey, extra);  }   public int getRanking(int score, Extra extra) {   return getRankingOfNode(root, score, extra) + 1;  }   public ArrayList<LeaderboardData> getTopN(int n) {   ArrayList<LeaderboardData> dataList = new ArrayList<LeaderboardData>();    int count = 0;   LeaderboardNode cursor = tail;   while (cursor != null) {    for (Extra extra : cursor.extraList) {     LeaderboardData data = new LeaderboardData();     data.ranking = ++count;     data.key = cursor.lowerKey;     data.extra = extra;     dataList.add(data);     if (count >= n) {      return dataList;     }    }    cursor = cursor.prev;   }   return dataList;  }   private LeaderboardNode setupNode(LeaderboardNode node, int lowerKey, int upperKey) {   if (lowerKey > upperKey) {    return null;   }    node = new LeaderboardNode();   node.lowerKey = lowerKey;   node.upperKey = upperKey;   node.number = 0;   node.extraList.clear();    if (isLeafNode(node)) {    if (head == null) {     head = node;    }     if (tail != null) {     tail.next = node;     node.prev = tail;    }     tail = node;    return node;   }    if (upperKey > lowerKey) {    final int middleKey = getMiddleKey(lowerKey, upperKey);    node.left = setupNode(node.left, lowerKey, middleKey);    node.right = setupNode(node.right, middleKey + 1, upperKey);   }    return node;  }   private void insertIntoNode(LeaderboardNode node, int score, Extra extra) {   if (node == null) {    return;   }    if (!isInsideNode(node, score)) {    return;   }    ++node.number;    if (isLeafNode(node)) {    node.extraList.add(extra);    node.extraList.sort((Extra left, Extra right) -> left.compareTo(right));    return;   }    final int middleKey = getMiddleKey(node.lowerKey, node.upperKey);   if (score <= middleKey) {    insertIntoNode(node.left, score, extra);   } else {    insertIntoNode(node.right, score, extra);   }  }   private void removeFromNode(LeaderboardNode node, int score, Extra extra) {   if (node == null) {    return;   }    if (!isInsideNode(node, score)) {    return;   }    --node.number;    if (isLeafNode(node)) {    node.extraList.remove(extra);    node.extraList.sort((Extra left, Extra right) -> left.compareTo(right));    return;   }    final int middleKey = getMiddleKey(node.lowerKey, node.upperKey);   if (score <= middleKey) {    removeFromNode(node.left, score, extra);   } else {    removeFromNode(node.right, score, extra);   }  }   private int getRankingOfNode(LeaderboardNode node, int score, Extra extra) {   int ranking = 0;    if (node == null) {    return ranking;   }    if (score < node.lowerKey) {    ranking += node.number;    return ranking;   }    if (score > node.upperKey) {    ranking += 0;    return ranking;   }    if (isLeafNode(node)) {    ranking += Math.max(node.extraList.indexOf(extra), 0);    return ranking;   }    final int middleKey = getMiddleKey(node.lowerKey, node.upperKey);   if (score <= middleKey) {    ranking += node.right != null ? node.right.number : 0;    ranking += getRankingOfNode(node.left, score, extra);   } else {    ranking += getRankingOfNode(node.right, score, extra);   }    return ranking;  }   private int getMiddleKey(int lowerKey, int upperKey) {   final int middleKey = lowerKey + ((upperKey - lowerKey) >> 1);   return middleKey;  }   private boolean isInsideNode(LeaderboardNode node, int score) {   return score >= node.lowerKey && score <= node.upperKey;  }   private boolean isLeafNode(LeaderboardNode node) {   return node.lowerKey == node.upperKey;  } }

针对我们的需求，key就是战力，extra包含玩家经验和ID。

采用这种做法，需要在服务器启动时重新构建排行树，先确定排行战力区间，然后依次插入每个玩家战力等数据。运行期间，玩家战力等改变时，先删除旧的排行，再插入新的排行。

该算法在处理千万数据时依然有效，但再大规模性能会不足，占用空间也客观。如果战力分布不均，同战力玩家过多，性能也会大幅退化，可将ArrayList替换为更高效的数据结构，或变通需求。

公共库仓库： JMetazion

服务器示例仓库： JGameDemo

服务器架构QQ交流群：330459037