使用Firebase排行榜排名 [英] Leaderboard ranking with Firebase

查看:271
本文介绍了使用Firebase排行榜排名的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有项目需要显示前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名中,那么获得当前登录用户排名的最佳做法是什么?

解决方案

查找任意玩家的等级在排行榜中,缩放是数据库常见的难题。



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




  • 玩家总数

  • 个别玩家加分的评分

  • 添加新分数的评分(并发参与者*以上)

  • 分数范围:有界或无界

  • 分数分布(统一,或者是他们的'热门分数')



简单方法



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



此方法适用于低规模,但随着玩家群体的增长,它很快变得既慢又耗资源(两者都很重要)在MongoDB和Cloud Firestore中。



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



定期更新



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



对于这种方法,您可以



最后的想法



取决于您为玩家展示排行榜的频率,你可以结合使用方法来优化这一点。



在较短的时间内将'倒置指数'与'周期性更新'相结合可以给你O(1)排名所有玩家的访问权限。



只要超过所有玩家,在定期更新期间查看排行榜> 4次,您将节省资金并拥有快点 排行榜。



基本上每个时段,比如5-15分钟,您按降序从得分中读取所有文档。使用此功能,运行总计 players_count 。使用新字段 players_above 将每个分数重新写入名为 scores_ranking 的新集合中。此新字段包含不包括当前分数的运行总计 player_count



要获得玩家的等级,您只需要现在要做的是从 score_ranking 中读取玩家得分的文件 - >他们的等级是 players_above + 1。


I have project that I need to display a leaderboard of the top 20, and if the user not in the leaderboard they will appear in the 21st place with their current ranking.

Is there efficient way to this?

I am using Cloud Firestore as a database. I believe it was mistake to choose it instead of MongoDB but I am in the middle of the project so I must do it with Cloud Firestore.

The app will be use by 30K users. Is there any way to do it without getting all the 30k users?

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

This is code I did to get the top 20 but what will be the best practice for getting current logged in user rank if they are not in the top 20?

解决方案

Finding an arbitrary player's rank in leaderboard, in a manner that scales is a common hard problem with databases.

There are a few factors that will drive the solution you'll need to pick, such as:

  • Total Number players
  • Rate that individual players add scores
  • Rate that new scores are added (concurrent players * above)
  • Score range: Bounded or Unbounded
  • Score distribution (uniform, or are their 'hot scores')

Simplistic approach

The typical simplistic approach is to count all players with a higher score, eg SELECT count(id) FROM players WHERE score > {playerScore}.

This method works at low scale, but as your player base grows, it quickly becomes both slow and resource expensive (both in MongoDB and Cloud Firestore).

Cloud Firestore doesn't natively support count as it's a non-scalable operation. You'll need to implement it on the client-side by simply counting the returned documents. Alternatively, you could use Cloud Functions for Firebase to do the aggregation on the server-side to avoid the extra bandwidth of returning documents.

Periodic Update

Rather than giving them a live ranking, change it to only updating every so often, such as every hour. For example, if you look at Stack Overflow's rankings, they are only updated daily.

For this approach, you could schedule a function, or schedule App Engine if it takes longer than 540 seconds to run. The function would write out the player list as in a ladder collection with a new rank field populated with the players rank. When a player views the ladder now, you can easily get the top X + the players own rank in O(X) time.

Better yet, you could further optimize and explicitly write out the top X as a single document as well, so to retrieve the ladder you only need to read 2 documents, top-X & player, saving on money and making it faster.

This approach would really work for any number of players and any write rate since it's done out of band. You might need to adjust the frequency though as you grow depending on your willingness to pay. 30K players each hour would be $0.072 per hour($1.73 per day) unless you did optimizations (e.g, ignore all 0 score players since you know they are tied last).

Inverted Index

In this method, we'll create somewhat of an inverted index. This method works if there is a bounded score range that is significantly smaller want the number of players (e.g, 0-999 scores vs 30K players). It could also work for an unbounded score range where the number of unique scores was still significantly smaller than the number of players.

Using a separate collection called 'scores', you have a document for each individual score (non-existent if no-one has that score) with a field called player_count.

When a player gets a new total score, you'll do 1-2 writes in the scores collection. One write is to +1 to player_count for their new score and if it isn't their first time -1 to their old score. This approach works for both "Your latest score is your current score" and "Your highest score is your current score" style ladders.

Finding out a player's exact rank is as easy as something like SELECT sum(player_count)+1 FROM scores WHERE score > {playerScore}.

Since Cloud Firestore doesn't support sum(), you'd do the above but sum on the client side. The +1 is because the sum is the number of players above you, so adding 1 gives you that player's rank.

Using this approach, you'll need to read a maximum of 999 documents, averaging 500ish to get a players rank, although in practice this will be less if you delete scores that have zero players.

Write rate of new scores is important to understand as you'll only be able to update an individual score once every 2 seconds* on average, which for a perfectly distributed score range from 0-999 would mean 500 new scores/second**. You can increase this by using distributed counters for each score.

* Only 1 new score per 2 seconds since each score generates 2 writes
** Assuming average game time of 2 minute, 500 new scores/second could support 60000 concurrent players without distributed counters. If you're using a "Highest score is your current score" this will be much higher in practice.

Sharded N-ary Tree

This is by far the hardest approach, but could allow you to have both faster and real-time ranking positions for all players. It can be thought of as a read-optimized version of of the Inverted Index approach above, whereas the Inverted Index approach above is a write optimized version of this.

You can follow this related article for 'Fast and Reliable Ranking in Datastore' on a general approach that is applicable. For this approach, you'll want to have a bounded score (it's possible with unbounded, but will require changes from the below).

I wouldn't recommend this approach as you'll need to do distributed counters for the top level nodes for any ladder with semi-frequent updates, which would likely negate the read-time benefits.

Final thoughts

Depending on how often you display the leaderboard for players, you could combine approaches to optimize this a lot more.

Combining 'Inverted Index' with 'Periodic Update' at a shorter time frame can give you O(1) ranking access for all players.

As long as over all players the leaderboard is viewed > 4 times over the duration of the 'Periodic Update' you'll save money and have a faster leaderboard.

Essentially each period, say 5-15 minutes you read all documents from scores in descending order. Using this, keep a running total of players_count. Re-write each score into a new collection called scores_ranking with a new field players_above. This new field contains the running total excluding the current scores player_count.

To get a player's rank, all you need to do now is read the document of the player's score from score_ranking -> Their rank is players_above + 1.

这篇关于使用Firebase排行榜排名的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆