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

发表于 分类于

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

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

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

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

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