使用Firebase排行榜排名

Question

我有一个项目,我需要显示前20名的排行榜,如果用户不在排行榜,他们将出现在他们当前排名的第21位.

有效的方法吗？

我使用Cloud Firestore作为数据库.我认为选择它而不是MongoDB是错误的,但我在项目的中间,所以我必须使用Cloud Firestore.

该应用程序将由30K用户使用.没有获得所有30k用户,有没有办法做到这一点？

 this.authProvider.afs.collection('profiles', ref => ref.where('status', '==', 1)
        .where('point', '>', 0)
        .orderBy('point', 'desc').limit(20))

这是我为获得前20名所做的代码,但如果他们不在前20名,那么获得当前登录用户排名的最佳做法是什么？

Answer 1

在排行榜中找到任意玩家的排名,以缩放的方式是数据库的常见难题.

有几个因素会推动您需要选择的解决方案,例如:

• 玩家总数
• 单个玩家添加分数的比率
• 添加新分数的评分(并发参与者*以上)
• 分数范围:有界或无界
• 分数分布(统一,或者是他们的'热门分数')

简单的方法

典型的简单方法是计算所有具有较高分数的玩家,例如SELECT count(id) FROM players WHERE score > {playerScore}.

这种方法工作规模较小,但随着玩家群体的增长,它很快变得既慢又耗资源(在MongoDB和Cloud Firestore中).

Cloud Firestore本身不支持,count因为它是不可扩展的操作.您只需要计算返回的文档,就需要在客户端实现它.或者,您可以使用Cloud Functions for Firebase在服务器端进行聚合,以避免返回文档的额外带宽.

定期更新

而不是给他们一个实时排名,而是将其更改为每隔一小时更新一次.例如,如果您查看Stack Overflow的排名,它们只会每天更新.

对于此方法,您可以安排一个功能,或者如果运行时间超过540秒,则安排App Engine.该函数会将玩家列表写在一个ladder集合中,其中包含一个rank填充了玩家等级的新字段.当玩家现在观看阶梯时,您可以轻松地在O(X)时间内获得顶级X +玩家自己的排名.

更好的是,您可以进一步优化并明确地将顶部X写为单个文档,因此要检索梯形图,您只需要阅读2个文档,top-X和播放器,节省资金并加快速度.

这种方法适用于任何数量的玩家和任何写入率,因为它是在带外完成的.您可能需要根据您的支付意愿调整频率.每小时30K玩家每小时0.072美元(每天1.73美元),除非你做了优化(例如,忽略所有0分的玩家,因为你知道他们最后并列).

倒指数

在这种方法中,我们将创建一些倒置索引.如果有一个有限的得分范围显着小于想要玩家的数量(例如,0-999得分对比30K玩家),则此方法有效.它也适用于无限分数范围,其中独特分数的数量仍然明显小于玩家数量.

使用一个名为"分数"的单独集合,您可以获得一个文档,其中包含每个单独的分数(如果没有人有该分数则不存在),并带有一个名为"分数"的字段player_count.

当玩家获得新的总分时,您将在该scores系列中进行1-2次写入.一次写作是player_count为他们的新分数+1 ,如果不是他们的第一次-1他们的旧分数.这种方法适用于"您的最新分数是您当前的分数"和"您的最高分是您当前的分数"风格梯子.

找出一个玩家的确切排名就像这样简单SELECT sum(player_count)+1 FROM scores WHERE score > {playerScore}.

由于Cloud Firestore不支持sum(),您可以执行上述操作,但在客户端进行总结.+1是因为总和是你之上的玩家数量,所以加1会给你该玩家的等级.

使用这种方法,您需要读取最多999个文档,平均500个以获得玩家排名,但实际上如果删除没有玩家的分数,这将会更少.

新分数的写入率很重要,因为你只能平均每2秒*更新一次单独的分数,对于0-999的完美分布分数,这意味着500分新的分数/秒**.您可以通过为每个分数使用分布式计数器来增加此值.

*每2秒只有1个新分数,因为每个分数产生2次写入
**假设平均游戏时间为2分钟,500个新分数/秒可以支持60000个没有分布式计数器的并发玩家.如果您使用的是"最高得分是您目前的得分",那么实际情况会更高.

Sharded N-ary Tree

这是迄今为止最难的方法,但可以让你为所有玩家提供更快和实时的排名位置.它可以被认为是上面的反向索引方法的读优化版本,而上面的反向索引方法是对此的写优化版本.

您可以按照适用的一般方法,针对"数据存储区中的快速可靠排名"这篇相关文章进行操作.对于这种方法,你需要有一个有界的分数(这可能是无限的,但需要从下面的变化).

我不推荐这种方法,因为您需要为具有半频率更新的任何梯形图的顶级节点执行分布式计数器,这可能会抵消读取时间的好处.

最后的想法

根据您为玩家显示排行榜的频率,您可以结合使用方法来优化这一点.

在更短的时间内将"倒置索引"与"定期更新"相结合,可以为所有玩家提供O(1)排名访问权限.

只要所有玩家在"定期更新"期间查看排行榜> 4次,您就可以省钱并拥有更快的排行榜.

基本上每个时期,比如5-15分钟,你scores按降序阅读所有文件.使用它,保持运行总计players_count.将每个分数重新写入scores_ranking使用新字段调用的新集合中players_above.此新字段包含不包括当前分数的运行总计player_count.

要获得玩家的等级,您现在需要做的就是阅读玩家得分的文件score_ranking- >他们的等级为players_above+ 1.

Answer 2

我将在我的在线游戏中实施并且可能在您的用例中使用的一种此处未提及的解决方案是估计用户的排名，如果他们不在任何可见的排行榜中，因为坦率地说，用户不会知道（或关心？）他们是否排名第 22,882 或 22,838。

如果第 20 名的得分为 250 分并且总共有 32,000 名玩家，那么每个低于 250 的点平均价值 127 个位置，尽管您可能想要使用某种曲线，以便他们向上移动一个点到可见的底部排行榜他们每次都不会准确地跳 127 个位置 - 排名中的大多数跳跃应该更接近于零点。

是否要将此估计排名确定为估计值取决于您，您可以在数字中添加一些随机盐，使其看起来真实：

// Real rank: 22,838

// Display to user:
player rank: ~22.8k    // rounded
player rank: 22,882nd  // rounded with random salt of 44

我会做后者。