在排行榜中发现任意玩家的排名,其方式是缩放是数据库常见的难题。
有几个因素将推动解决方案,你需要挑选,如:
- 总数球员
- 率,个别选手加分。
- 率新分数加入(并发玩家*上文)
- 分数范围:界或无界
- 分数分布(均匀的,或者是它们的“热分数”)
简单的方法
典型的简单的方法是计算所有玩家有更高的分数,例如SELECT count(id) FROM players WHERE score > {playerScore}
。
这种方法的工作量很小,但随着玩家基础的增长,它很快变得缓慢且资源昂贵(都在MongoDB和Cloud Firestore中)。
Cloud Firestore本身不支持count
,因为它是不可缩放的操作。您只需计算返回的文档即可在客户端实施它。或者,您可以使用Firebase的Cloud Functions在服务器端进行聚合,以避免返回文档的额外带宽。
定期更新
而不是让他们活的排名,将其更改为只更新每隔一段时间,比如每隔一小时。例如,如果您查看Stack Overflow的排名,它们只会每天更新。
对于此方法,如果运行时间超过540秒,则可以使用schedule a function或schedule App Engine。该功能会在ladder
集合中写出玩家列表,并在玩家排名中填入新的rank
字段。当玩家现在观看梯子时,您可以轻松地在O(X)时间内获得顶级X +玩家自己的排名。
更重要的是,你可以进一步优化和明确地写出来顶的X作为一个单一的文件一样,所以检索你只需要阅读两份文件,上面-X &球员的阶梯,节省金钱并使其更快。
这种方法对于任何数量的玩家和任何写入速率都是真正有效的,因为它是在带外完成的。您可能需要根据您的支付意愿调整频率。除非你进行了优化(例如,因为你知道他们最后并列,所以忽略所有0分的玩家),否则每小时30K玩家每小时将获得0.072美元(每天1.73美元)。
倒排索引
在这种方法中,我们会有点倒排索引的创建。如果有一个有限的得分范围,希望玩家的数量要小得多(例如,0-999分与30,000个玩家),则此方法有效。它也可以用于无限分数范围,其中独特分数的数量仍然明显小于玩家数量。
使用一个名为'分数'的单独集合,对于每个单独的分数(如果没有人拥有该分数,则不存在)具有名为player_count
的字段的文档。
当玩家获得新的总分时,您将在scores
集合中做1-2次写入。一个写法是+1到player_count
为他们的新分数,如果它不是他们的第一次-1旧分数。这种方法适用于“你的最新成绩是你当前的成绩”和“你的最高成绩是你现在的成绩”的风格阶梯。
找出球员的确切排名就像SELECT sum(player_count)+1 FROM scores WHERE score > {playerScore}
一样简单。
由于Cloud Firestore不支持sum()
,因此您需要执行上述操作,但总结客户端。 +1是因为总数是你上面的玩家数量,所以加1会给你该玩家的等级。
使用这种方法,您最多需要读取999个文档,平均值为500ish才能获得玩家排名,但实际上,如果您删除玩家数量为零的分数,这个数字会减少。
新分数的写入率很重要,因为您只能平均每2秒更新一次个人分数*,对于0-999的完美分布分数范围,则意味着500个新分数/第二**。您可以通过为每个分数使用distributed counters来增加此值。
*只有自每个分数每2秒1个新得分产生2写入
**假设2分钟平均游戏时间,500个新的得分/第二可支持60000名并发玩家没有分布式计数器。如果你使用“最高分是你目前的分数”,这在实践中将会高得多。
分片N叉树
这是迄今为止最难的做法,但可以让你同时拥有所有玩家更快的实时排名位置。它可以被认为是上面倒置索引方法的读取优化版本,而上面的倒置索引方法是这个的写入优化版本。
您可以按照适用的一般方法,参照'Fast and Reliable Ranking in Datastore'的相关文章。对于这种方法,你会想要一个有界的分数(这可能是无界的,但需要从下面进行更改)。
我不会推荐这种方法,因为您需要为具有半频更新的任何梯子的顶级节点执行分布式计数器,这可能会否定读取时间的好处。
最后的想法
您可以根据自己往往表现球员排行榜上,你可以结合的方法来优化这个多很多。
在较短的时间范围内结合“反向索引”和“定期更新”可以为您提供所有玩家的O(1)排名访问权限。
只要所有玩家在'定期更新'期间查看排行榜超过4次,您就可以省钱并拥有更快的排行榜。
基本上每个周期,比如说5-15分钟,您从scores
降序读取所有文档。使用这个,保持总计players_count
。将每个分数重新写入名为scores_ranking
的新集合,并添加一个新字段players_above
。这个新字段包含排除当前得分的运行总数player_count
。
要获得玩家的排名,你现在需要做的是从score_ranking
读取玩家的得分的文件 - >它们的等级是players_above
+ 1
哇。在stackoverflow上看到的最佳答案。我肯定需要再读几遍你的答案,以了解如何实现它。感谢您的时间来回答。 – haim
谢谢Shimon!没问题,希望它有帮助:) –
很好的答案,但我想添加一个更多的解决方案。它不支持在firebase中,但couchdb可以在查询时始终提供偏移量。具有索引的NoSQL数据库在查询像couchdb时应保持分片计数和总和。可悲的是没有太多的数据库支持这个功能 – Thaina