前言
游戏排行榜是每个游戏都必备的一个功能。有日常常驻的排行榜，比如游戏的战力排行榜，游戏的财富排行榜等。还有就是各种排行活动中的排行榜。我们随便举几个游戏中排行榜的例子。
我们可以看到一般游戏只会列举排行前100或者200名的名单，之外的就是暂未上榜，不给出具体排名，上述游戏中有的榜单会实时更新，有的会定时更新。
思考和设计
根据一般游戏的需求，我提炼出一个游戏排行榜需要具备一下功能
- 前100或者200（数值可指定，一般小于200）的排名是精准无误的，并且能够有足够的信息展示给玩家
- 排行榜的排名最好可以做到实时更新
- 对于未上榜的排名能够给出一个比较准确的估计值将是更好的
- 具备高性能
- 支持并发
看到高性能 、并发 等字眼，感觉好像很困难，但万事开头难，我们先不关心这个，我们先考虑怎么保证业务。
如果设计一个通用的排行榜呢？那首先需要一个通用的排行数据，对于排行数据我抽象为下面这个类
基准排行类设计
public class RankData : IComparable<RankData>, IEquatable<RankData>, ICloneable
{
/// <summary>
/// 排序主键
/// </summary>
public long Id { get; set; }
/// <summary>
/// 排序值
/// </summary>
public long Value { get; set; }
/// <summary>
/// 附加参数 - int类型
/// </summary>
public int[] Params { get; set; }
/// <summary>
/// 附加参数 - object类型
/// </summary>
public object[] ExtraParams { get; set; }
/// <summary>
/// 达到该分数的时间
/// </summary>
public long UpdateTime { get; set; }
public bool Equals(RankData other)
{
if (null == other)
{
return false;
}
return Id == other.Id;
}
public int CompareTo(RankData other)
{
if (null == other)
{
return 1;
}
// 分数高的排前面
if (Value > other.Value)
{
return -1;
}
if (Value < other.Value)
{
return 1;
}
// 更新时间早的排前面
if (UpdateTime > other.UpdateTime)
{
return 1;
}
if (UpdateTime < other.UpdateTime)
{
return -1;
}
// Id小的排前面
if (Id < other.Id)
{
return -1;
}
return Id == other.Id ? 0 : 1;
}
public object Clone()
{
return new RankData
{
Id = Id, Value = Value, Params = Params, StrParams = StrParams,
};
}
}
对于这个类的设计意图如下：
-
Id是排行对象的唯一标识，比如如果是游戏内的排行榜一般是玩家Id -
Value是用于排行的数值，数值越大排行越靠前。比如战力排行榜就是战力值 -
Params是用于排行的附加数据，一般用于辅助显示，假设一个足球游戏的联赛排行榜，积分是用于排行，那Params里可以存储胜场次、负场次，平场次用于辅助排行榜显示 -
ExtraParams和Params是类似用途 -
UpdateTime是用于记录玩家达到该排行榜分数的时间戳，对于相同分数的玩家我们可以根据该字段判断达成时间越早的排在越前面
我想大部分的排行榜都可以转化为该对象，再交给专用的排行榜管理类统一进行排序，这样我们迈进了第一步，有了统一的基准排序对象。
那接下来就是选用什么数据结构去用于排序，我选用的是大家最常用的数据结构List , List基于数组实现，有高效的访问效率。我们维护一个有序的数组，那么对于后续插入数据只需要采用二分查找找到合适的插入位置，整个排行榜在运行期间，无需做任何一次排序运算，性能是很高的。
对于排名我是分为精确排名 + 估计排名
- 精确排名，
RankData存储在List中 - 估计排名，我们根据他的排行分数已一个固定分数间隔进行分桶，记录每个桶中玩家数量
排行榜类设计
对于排行类（Rank）我的设计如下
public class Rank : IDisposable
{
private int _pointInterval; // 分数区间基准
private readonly int _maxNum; // 精确排名最大值
private int _totalNum; // 参与排行玩家总数
private readonly List<RankData> _rankList; // 精确排名列表
private List<int> _extraRankList; // 非精确排名列表
private volatile bool _stopRankFlag; // 停止排名标志
private readonly ReaderWriterLockSlim _rwLock; // 读写锁
private readonly int _maxExtraRankRangeCount; // 默认非精确排名最大区间数量
/// <summary>
/// 构造函数
/// </summary>
public Rank(int maxNum, int pointInterval, int maxExtraRankRangeCount = 10000)
{
_rwLock = new ReaderWriterLockSlim();
_maxNum = maxNum;
_pointInterval = pointInterval;
_rankList = new List<RankData>();
_extraRankList = new List<int>();
_stopRankFlag = false;
_maxExtraRankRangeCount = maxExtraRankRangeCount;
}
}
-
_rankList用于存储精确排名的玩家，存储了完整的RankData -
_extraRankList用于存储精确排名之外的每个桶中玩家数量 -
_maxExtraRankRangeCount用于限制桶的最大数量，用于提高性能 -
_maxNum用于定义精确排名的最大数量 -
_pointInterval用于定义分桶基准
排行榜类API设计
对于排行榜我定义了一下接口
/// <summary>
/// 更新排行数据
/// </summary>
public void AddRankData(RankData data);
/// <summary>
/// 更新排行数据
/// </summary>
public void UpdateRankData(RankData data, long srcValue, long srcUpdateTime);
/// <summary>
/// 从排行榜中剔除
/// </summary>
public void RemoveRankData(RankData data);
/// <summary>
/// 获取自身排名
/// </summary>
public int GetMyRank(RankData data);
/// <summary>
/// 获取排行榜数据
/// </summary>
public List<RankData> GetRankList(int start, int end);
下面我们一个一个来看每个API的具体实现
- 添加排行数据
用于系统启动时候初始化排行榜，或者新进榜玩家
public void AddRankData(RankData data)
{
if (_stopRankFlag)
{
return;
}
_rwLock.EnterWriteLock();
try
{
_totalNum++;
if (_rankList.Count >= _maxNum)
{
// 精确排行榜已满，与队尾比较
var last = _rankList[_rankList.Count - 1];
if (data.Value <= last.Value)
{
// 不满足上榜需求，直接添加到非精确排名
AddToExtraRankList(data);
}
else
{
// 可以上榜，添加到排行榜，并且淘汰队尾
AddToRankList(data);
RemoveTail();
}
return;
}
// 未满情况下直接进入精确排行榜
AddToRankList(data);
}
finally
{
_rwLock.ExitWriteLock();
}
}
结合注释应该很容易看懂，后续会给出几个通用方法的实现代码
- 更新排行榜数据
用于已经进行过排行的玩家，排行数值发生变化，需要更新排行榜
/// <summary>
/// 更新排行数据
/// </summary>
public void UpdateRankData(RankData data, long srcValue, long srcUpdateTime)
{
if (_stopRankFlag)
{
return;
}
_rwLock.EnterWriteLock();
try
{
// 构造变更前的排行数据，该数据必须准确，一般可以根据数据库记录
var srcData = data.Clone() as RankData;
srcData.Value = srcValue;
srcData.UpdateTime = srcUpdateTime;
var last = _rankList[_rankList.Count - 1];
if (_rankList.Count >= _maxNum && data.Value < last.Value && rcData.Value < last.Value)
{
// 精确排名已满，老值和新值都不足以进入精确排名
AddAndRemoveExtraRankList(data, srcData);
}
else
{
// 查找之前的排名数据
var myIndex = _rankList.BinarySearch(srcData);
if (myIndex >= 0)
{
// 在精确排名中
_rankList.RemoveAt(myIndex);
AddToRankList(data);
}
else
{
myIndex = _rankList.BinarySearch(data); // 获取实时排名
if (Math.Abs(myIndex) <= _maxNum)
{
// 晋升到精确排名
AddToRankList(data);
// 从非精确排名剔除自己
RemoveExtraRankList(srcData);
// 移除精确排名队尾，保证数量
RemoveTail();
}
else if (_rankList.Count < _maxNum)
{
AddToRankList(data);
}
else
{
AddAndRemoveExtraRankList(data, srcData);
}
}
}
}
finally
{
_rwLock.ExitWriteLock();
}
}
- 从排行榜中移除
这个操作一般很少用到
/// <summary>
/// 从排行榜中剔除
/// </summary>
public void RemoveRankData(RankData data)
{
if (_stopRankFlag)
{
return;
}
_rwLock.EnterWriteLock();
try
{
_totalNum--;
var last = _rankList[_rankList.Count - 1];
if (_rankList.Count >= _maxNum && data.Value < last.Value)
{
RemoveExtraRankList(data);
}
else
{
var myIndex = _rankList.BinarySearch(data);
if (myIndex >= 0)
{
_rankList.RemoveAt(myIndex);
}
}
}
finally
{
_rwLock.ExitWriteLock();
}
}
- 获取指定区间的排行数据
用于展示前100名排行榜数据
/// <summary>
/// 获取排行榜数据
/// </summary>
public List<RankData> GetRankList(int start, int end)
{
var resultList = new List<RankData>();
if (start >= end)
{
return resultList;
}
_rwLock.EnterReadLock();
try
{
end = Math.Min(end, _rankList.Count);
for (var i = start; i < end; i++)
{
resultList.Add(_rankList[i]);
}
return resultList;
}
finally
{
_rwLock.ExitReadLock();
}
}
- 获取自身排名
用于获取特定玩家的排行榜
/// <summary>
/// 获取自身排名
/// </summary>
public int GetMyRank(RankData data)
{
if (data == null || _rankList.Count <= 0)
{
return -1;
}
_rwLock.EnterReadLock();
try
{
var last = _rankList[_rankList.Count - 1];
int index;
if (data.Value >= last.Value)
{
// 在精确排名中
index = _rankList.BinarySearch(data);
if (index >= 0)
{
return index + 1;
}
}
// 在非精确排名中
return GetRankFromExtraRankList(data);
}
finally
{
_rwLock.ExitReadLock();
}
}
- 内部方法
下面给出上述对外API用的内部方法实现
/// <summary>
/// 从非精确排名中获取评估排名
/// </summary>
private int GetRankFromExtraRankList(RankData data)
{
int myRank;
var index = (int)(data.Value / _pointInterval);
var beforeNum = _rankList.Count;
var lowPoint = (index + 1) * _pointInterval - 1;
for (var i = _extraRankList.Count - 1; i > index; i--)
{
beforeNum += _extraRankList[i];
}
if (index <= _extraRankList.Count - 1)
{
var avg = _pointInterval * 1.0 / (_extraRankList[index] + 1);
beforeNum += (int)Math.Floor((lowPoint - data.Value) / avg);
myRank = beforeNum;
}
else
{
myRank = beforeNum + 1;
}
return myRank;
}
private void RemoveExtraRankList(RankData data)
{
var index = (int)(data.Value / _pointInterval);
if (_extraRankList.Count > index)
{
_extraRankList[index] -= 1;
}
}
private void AddAndRemoveExtraRankList(RankData newData, RankData oldData)
{
var newIndex = (int)(newData.Value / _pointInterval);
var oldIndex = (int)(oldData.Value / _pointInterval);
if (newIndex != oldIndex)
{
RangeCehck(oldIndex, _extraRankList);
_extraRankList[oldIndex] -= 1;
RangeCehck(newIndex, _extraRankList);
_extraRankList[newIndex] += 1;
}
AdjustExtraRankList();
}
private void AddToExtraRankList(RankData data)
{
var index = (int)(data.Value / _pointInterval);
RangeCehck(index, _extraRankList);
_extraRankList[index] += 1;
AdjustExtraRankList();
}
private void AddToRankList(RankData data)
{
var myIndex = _rankList.BinarySearch(data);
if (myIndex >= 0)
{
_rankList[myIndex] = data;
}
else
{
_rankList.Insert(~myIndex, data);
}
}
private void RemoveTail()
{
if (_rankList.Count >= _maxNum)
{
var data = _rankList[_rankList.Count - 1];
_rankList.RemoveAt(_rankList.Count - 1);
AddToExtraRankList(data);
}
}
private void RangeCehck(int index, List<int> rankList)
{
if (rankList.Count <= index)
{
for (var i = rankList.Count; i <= index; i++)
{
rankList.Add(0);
}
}
}
/// <summary>
/// 动态调整ExtraRankList
/// </summary>
private void AdjustExtraRankList()
{
if (_extraRankList.Count > _maxExtraRankRangeCount)
{
var count = (int)Math.Ceiling(_extraRankList.Count * 1.0 / _maxExtraRankRangeCount);
_pointInterval *= count;
var newList = new List<int>(_maxExtraRankRangeCount);
for (var i = 0; i < _extraRankList.Count; i++)
{
var newIndex = i / count;
if (newList.Count > newIndex)
{
newList[newIndex] += _extraRankList[i];
}
else
{
newList.Add(_extraRankList[i]);
}
}
_extraRankList = newList;
}
}
排行榜正确性和性能测试
对于上述的实现，是否正确呢？性能是否足够呢？我设计了以下测试类
[TestClass]
public class RankTest
{
// 正确性测试
[TestMethod]
public void Test()
{
var rank = new Rank(100, 100);
var dict = new Dictionary<int, long>();
var random = new Random();
var max = 100000;
// 1. 初始化数据
var time = Stopwatch.StartNew();
time.Start();
for (int i = 0; i < max; i++)
{
dict[i] = random.Next();
}
time.Stop();
Console.WriteLine($"dict add time:{time.ElapsedMilliseconds}");
// 2. 插入到排行榜
time.Restart();
for (int i = 0; i < max; i++)
{
rank.AddRankData(new RankData { Id = i, Value = dict[i] });
}
time.Stop();
Console.WriteLine($"add time:{time.ElapsedMilliseconds}");
// 3. 打印排行榜数据
List<RankData> _rankList = rank.GetRankList(0, 100);
foreach (var data in _rankList)
{
Console.WriteLine($"{data.Id},{data.Value}");
}
Console.WriteLine();
Console.WriteLine("---------------------------------------");
// 4. 更新排行榜
time.Restart();
for (int i = 0; i < max; i++)
{
var id = random.Next(max);
var value = random.Next();
rank.UpdateRankData(new RankData { Id = id, Value = value }, dict[id]);
dict[id] = value;
}
time.Stop();
Console.WriteLine($"update time:{time.ElapsedMilliseconds}");
// 5. 获取排名API测试
time.Restart();
for (int i = 0; i < max; i++)
{
var myRank = rank.GetMyRank(new RankData { Id = i, Value = dict[i] });
}
time.Stop();
Console.WriteLine($"get rank time:{time.ElapsedMilliseconds}");
// 6. 再次打印排行榜
_rankList = rank.GetRankList(0, 100);
foreach (var data in _rankList)
{
Console.WriteLine($"{data.Id},{data.Value}");
}
Console.WriteLine();
Console.WriteLine("---------------------------------------");
// 7. 计算估算排名的方差
var list = dict.Values.ToList();
list.Sort();
double sum = 0;
int n = 10000;
for (int i = 0; i < n; i++)
{
var id = random.Next(max);
var myRank = rank.GetMyRank(new RankData { Id = id, Value = dict[id] });
var realRank = list.Count - (list.BinarySearch(dict[id]) + 1);
sum += Math.Pow(Math.Abs(realRank - myRank), 2);
}
Console.WriteLine($"方差：{sum/n}");
}
// 性能测试
[TestMethod]
public void MultiThreadTest()
{
var rank = new Rank(100, 100);
var random = new Random();
var max = 100000;
var threadNum = 10;
List<Task> taskList = new List<Task>();
for (int i = 0; i < threadNum; i++)
{
// 每个线程分别插入1遍数据，更新1遍数据，获取1遍排名
var task1 = Task.Run(() =>
{
var start = i * max;
var end = (i + 1) * max;
var time = Stopwatch.StartNew();
time.Start();
var dict = new Dictionary<int, long>();
for (int i = start; i < end; i++)
{
dict[i] = random.Next();
}
for (int i = start; i < end; i++)
{
rank.AddRankData(new RankData { Id = i, Value = dict[i] });
}
for (int i = start; i < end; i++)
{
var id = random.Next(start, end);
var value = random.Next();
rank.UpdateRankData(new RankData { Id = id, Value = value }, dict[id]);
dict[id] = value;
}
for (int i = start; i < end; i++)
{
var myRank = rank.GetMyRank(new RankData { Id = i, Value = dict[i] });
}
time.Stop();
Console.WriteLine($"thread:{System.Threading.Thread.CurrentThread.ManagedThreadId}, time:{time.ElapsedMilliseconds}");
});
taskList.Add(task1);
}
Task.WaitAll(taskList.ToArray());
}
}
大家可以自己跑一下这个代码
- 基准测试得到的精确排名是完全正确的
- 预估排名方差大概在3~4之间，我感觉已经足够了
- 对于多线程测试，对于这样的操作我的机器是
2.2s完成，平均每个线程1s左右。性能够用了
结语
至此我们实现一个可以实时更新的排行榜，并且理论上是可以无限数量玩家参与的排行榜。对于未上榜的玩家也能给出比较准确的预估值，可以用于游戏内各种排行榜。您是怎么实现游戏内排行榜的内，欢迎留言交流！
