Ranklist for Relative Leaderboards for Mobile App

[Clint Doriot]

I'm just beginning to use ranklist for my project. I've read through the code documentation and all the threads on this page, so I have some ideas on how to integrate it. However, I was wondering if I could get some feedback on the design to make sure I'm approaching this correctly. I wrote out a lot of details just in case it helps with understanding the use case (and a second opinion is always welcome), but the real questions come into play with the "Proposed Solution for Relative Leaderboards".

Basic Requirements

• Creating a leaderboard for a mobile app to track both total points earned and 
  
• Leaderboards further divided into a global leaderboard space, and a relative leaderboard space (see only your Twitter friends' scores, and gets rank relative to them).
  
• No need for paging. Users will only ever see the top X number of players, and the X players above and below them (X=3-5)
  
• User's update their score much more frequently than they fetch the leaderboards... scores are updated as often as once per minute, but the typical user (currently) only plays in bursts of 10 minutes, a few times per day.
  

Proposed Solution for Global Leaderboards:

• Basics:
• GlobalUserScore model contains a user's ID (a string, which also serves as the Key of that user's full User entity), total_points, daily_points, username, picture_url and daily_points_day (datetime that specifies the last time the points were updated).
• When a player submits their game (and causes updates to the total points / daily points), I trigger a push task queue to update their corresponding GlobalUserScore, and set it as 'dirty'
• The request handler to fetch the leaderboards will need to get() the current player's data, and do three queries to populate the leaderboard values (one for the top X players, one for the X players above the current player, and one for the X players below the current player).
• I include additional user data (picture url, twitter handle, and other stats that are displayed in the leaderboard) so that I only have to query this model, and not fetch the users from the DB after the queries.
• Incorporating Ranklist:
• One ranklist for the total_points, and one for the daily_points (a new one created each day, and the old one deleted after the new one is created).
• Use a pull task queue (or cron job?) to fetch dirty GlobalUserScores, and batch update the ranklist
• The request handler to fetch the leaderboards will use the ranklist to determine the player's rank. The client will compute the ranks of all other players based the current player's rank ('R') (1,2,3 .... R-3,R-2,R-1,current player, R+1, R+2, R+3... with some special logic for displaying ties)

Proposed Solution for Relative Leaderboards:

• Here is where I'm the most worried about the design
  
• Basics
• Basically my current thought is to do nearly the same thing as I'm doing with the GlobalUserScore model, except that its a RelativeUserScore model. There would be one entity per user -> friend relationship, and it would store the user_id, the friend's user id (friend_id), and all the data (scores, picture url, twitter handle, etc.) of that friend.
• The background task for updating scores after game submission would now need to query for, and update, all RelativeUserScores where the submitting player is the friend. All those score objects get set to dirty 
• Same type of request handler, except modifying the query with an additional filter to only fetch the current player's RelativeUserScores (ie, user_id = current_user.key.id())
• (I saw some other posts about just storing friendships in a list, but that seemed like it was more geared toward solving the problem of displaying pages of leaderboards, which I wont need to do. Are there other benefits that I'm missing with that suggestion?)
• Incorporating Ranklist
• Here's where I'm really scratching my head :)
• Is it as simple as having a separate ranklist for each user? I could just tie the ranklist key string to the user's key string, and it would make it very easy to get. But would the number of RankScores and RankNodes that it generates make this too cumbersome?
• For bulk updates a ranklist, I'd likely grab a single dirty RelativeUserScore model, and then do a query to get all RelativeUserScore models with the same user. Then update that user's ranklist in a bulk.
• This could be overkill, as most users will not have a ton of friends.
• I could instead just do a count query to determine the rank, but it wouldn't be as precise, in the case of ties.
• This also creates a potential bottle neck for some smaller subset of users who do have a large network playing the game.
• Maybe  for users with large networks, they can have their own ranklist, and for users with smaller networks we fall back on querying directly? 

So, if you have any suggestions on using ranklist for the relative leaderboards, or the proposed solution in general, I'd very much appreciate them!

Thank you!

[Bartholomew Furrow]

OK, here are a few thoughts. TLDR: you're on the right track for all of this, but keep in mind that a simple solution that will work until your game hits it big will let you concentrate on making your game hit it big sooner. The complex solution will still be waiting.

For your global leaderboard, Ranklist makes a lot of sense to use. Note that doing a query that just counts is definitely an option, and if you don't mind it taking a few seconds, it could take you over 10k users comfortably and with perfect accuracy; but if you want it to take less time, or want to scale further, ranklist wins for "what's my rank?" hands down, *except* for complexity of setup. With the usage pattern you've described, you'll probably want to update the ranklist offline, which probably means setting up a cron job of some kind.

For the relative list, I don't see a great solution. You could:
- Update one Entity for each of my followers every time I score.
- Query for all the people I follow every time I want to know my rank, and compare my score.

Either way you're potentially dealing with a large number of Entities, which isn't something Datastore excels at. At least you can do the first one offline.

With that said, option 2 isn't going to be a problem until you have a user playing your game who follows more than a thousand people who *also* play your game. A good problem to have.

Once you get to that point, I'd recommend something like the following monstrosity:
- For each user, keep a boolean indicating whether he or she is following a lot of game players. Keep it in the Entity that says "A is following B" for easy querying by B.
- When I score, query for the people who are following me who have that bit set. Mark the "A is following B" Entity dirty, so a cron job can pick it up.

It's essentially what you suggested, with some details filled in: keep a ranklist only for people who follow a lot of other people so their lookups are fast, but not for everyone else so keeping those lists updated is fast. In particular, you want to make it so that you can quickly query for only the people whose scores have changed for each megafollower. The problem then becomes O(#people followed by megafollowers), and it's an offline problem. This sounds like a pain to get right, and well worth delaying until it's needed.

One last thing: if you have a lot of ranklists, make sure their Keys all have different ancestors. Don't make a common ancestor of all ranklists: make the ancestor specific to the user. If things haven't changed in the last several years, which they might well have, this will be the difference between indefinite scaling and capping out in a hurry.

Bartholomew

On Sun, Apr 26, 2015, 15:26 Clint Doriot <clint...@gmail.com> wrote:

I'm just beginning to use ranklist for my project. I've read through the code documentation and all the threads on this page, so I have some ideas on how to integrate it. However, I was wondering if I could get some feedback on the design to make sure I'm approaching this correctly. I wrote out a lot of details just in case it helps with understanding the use case (and a second opinion is always welcome), but the real questions come into play with the "Proposed Solution for Relative Leaderboards".

Basic Requirements

Creating a leaderboard for a mobile app to track both total points earned and 
Leaderboards further divided into a global leaderboard space, and a relative leaderboard space (see only your Twitter friends' scores, and gets rank relative to them).
No need for paging. Users will only ever see the top X number of players, and the X players above and below them (X=3-5)
User's update their score much more frequently than they fetch the leaderboards... scores are updated as often as once per minute, but the typical user (currently) only plays in bursts of 10 minutes, a few times per day.

Proposed Solution for Global Leaderboards:

Basics:GlobalUserScore model contains a user's ID (a string, which also serves as the Key of that user's full User entity), total_points, daily_points, username, picture_url and daily_points_day (datetime that specifies the last time the points were updated).When a player submits their game (and causes updates to the total points / daily points), I trigger a push task queue to update their corresponding GlobalUserScore, and set it as 'dirty'The request handler to fetch the leaderboards will need to get() the current player's data, and do three queries to populate the leaderboard values (one for the top X players, one for the X players above the current player, and one for the X players below the current player).I include additional user data (picture url, twitter handle, and other stats that are displayed in the leaderboard) so that I only have to query this model, and not fetch the users from the DB after the queries.Incorporating Ranklist:One ranklist for the total_points, and one for the daily_points (a new one created each day, and the old one deleted after the new one is created).Use a pull task queue (or cron job?) to fetch dirty GlobalUserScores, and batch update the ranklistThe request handler to fetch the leaderboards will use the ranklist to determine the player's rank. The client will compute the ranks of all other players based the current player's rank ('R') (1,2,3 .... R-3,R-2,R-1,current player, R+1, R+2, R+3... with some special logic for displaying ties)

Proposed Solution for Relative Leaderboards:

Here is where I'm the most worried about the design

BasicsBasically my current thought is to do nearly the same thing as I'm doing with the GlobalUserScore model, except that its a RelativeUserScore model. There would be one entity per user -> friend relationship, and it would store the user_id, the friend's user id (friend_id), and all the data (scores, picture url, twitter handle, etc.) of that friend.The background task for updating scores after game submission would now need to query for, and update, all RelativeUserScores where the submitting player is the friend. All those score objects get set to dirty Same type of request handler, except modifying the query with an additional filter to only fetch the current player's RelativeUserScores (ie, user_id = current_user.key.id())(I saw some other posts about just storing friendships in a list, but that seemed like it was more geared toward solving the problem of displaying pages of leaderboards, which I wont need to do. Are there other benefits that I'm missing with that suggestion?)Incorporating RanklistHere's where I'm really scratching my head :)Is it as simple as having a separate ranklist for each user? I could just tie the ranklist key string to the user's key string, and it would make it very easy to get. But would the number of RankScores and RankNodes that it generates make this too cumbersome?For bulk updates a ranklist, I'd likely grab a single dirty RelativeUserScore model, and then do a query to get all RelativeUserScore models with the same user. Then update that user's ranklist in a bulk.This could be overkill, as most users will not have a ton of friends.I could instead just do a count query to determine the rank, but it wouldn't be as precise, in the case of ties.This also creates a potential bottle neck for some smaller subset of users who do have a large network playing the game.Maybe  for users with large networks, they can have their own ranklist, and for users with smaller networks we fall back on querying directly? 

So, if you have any suggestions on using ranklist for the relative leaderboards, or the proposed solution in general, I'd very much appreciate them!

Thank you!

--
You received this message because you are subscribed to the Google Groups "Google App Engine Ranklist" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-app-engine-r...@googlegroups.com.
To post to this group, send email to google-app-en...@googlegroups.com.
Visit this group at http://groups.google.com/group/google-app-engine-ranklist.
For more options, visit https://groups.google.com/d/optout.

[Clint Doriot]

Sounds like we have enough users to warrant the global ranker, but have some time before needing the relative rankers. I'm torn between how much time I'm willing to let the leaderboard request take: on one hand, we could fetch it when they open the app, and only do periodic updates while they are playing, so we dont care if it takes a few seconds. On the other hand, I'd prefer to not make the request until they actually select the leaderboards, as many users probably wont even load the leaderboard every time they play (but if its done on the fly, then it needs to be pretty responsive).

I'm getting a little lost in the specifics of your response. Just to be clear: The relative scores model indicates user A follows user B's score. For all these records, indicate if A is a megafollower (someone interested in a lot of other people's scores). When B updates his or her score, this should trigger A's ranker to get updated offline. I've detailed out the long version of my current understanding below, but I understand if you dont have time to read through it. I likely wont implement this full solution any time soon, but it may prove useful to have on record for myself and others down the line.

Regarding the ancestors: I'm not familiar with the direct datastore api, only ndb, and briefly db. But, yes, each ranker and its nodes and records need to be its own entity group, or else they can't run transactions at the same time. My plan was to tie the ranker to the user by convention (using the same key string, the user's id), but not explicitly put them in the same entity group together. (I want to make sure updates to the user model are fast and don't conflict with offline tasks, and I'm less concerned about leaderboard showing a slightly out of data score compared to the user's profile page).

One last question: you mentioned doing a cron job to pick up all the dirty entries. Any reason to use that over a Pull Queue Task, as they suggest here. I haven't used either yet (only push queues, so I'm not really sure which is most appropriate or easiest).

Thanks again for all your input on this! Its been a huge help!

-Clint

Full details of current and long-term plans:

#--- Models

class GlobalScoreRecord (ndb.Model):

    '''key => immutable user id'''

    score => integer property (not indexed)

    num_of_friends = integer property (not indexed)

    # other property specific to the user profile

class GlobalScoreRecord (ndb.Model):

    ''' key => user_id '''

    score = integer (indexed)

    ranker_dirty = boolean (indexed)

    # other properties that need to be displayed in the actual leaderboard on the client

class RelativeScoreRecord (ndb.Model):

    user_id = key property (indexed)  # aka, the follower

    friend_id = key property (indexed)  # aka, the person being followed

    score = integer (indexed)

    user_is_megafollower = boolean (indexed)

    ranker_dirty = boolean (indexed)

    # other properties that need to be displayed in the actual leaderboard on the client

    

#--- Handlers

Save Game Handler (user_id, game_id):

   1. process and save game results

   2. update user entity

   3. add push task to update score records

Get Global Leaderboard Handler (user_id):

   1. Query for Top X GlobalScoreRecords

   2. Query for X GlobalScoreRecords with score > user.score

   3. Query for X+1 GlobalScoreRecords with score <= user.score

   4. Get  GlobalScoreRecord for user. Use Global Ranker to determine rank. Let the client figure out the ranks of everyone above or below the user

Get Relative Leaderboard Handler (user_id):

   1. Same as Global, except run the queries against the RelativeScoreRecord, and add a filter for RelativeScoreRecord.user_id = user_id

   2. If user.num_of_friends < threshold: do a query against all records, and record the count as the rank.

   3. If user.num_of_friends >= threshold: use the relative ranker for that user, keyed on user_id

Auth Handler (user_id):

    1. Authenticate

    2. If num_of_friends != authentication_service.num_of_friends: run update friends task

#--- Tasks

Update Friends Push Task (user_id):

    1. Query authentication service for all friends from the authentication service. 

    2. Query datastore to match friends with corresponding user ids

    3. Update RelativeScoreRecords (add or delete as necessary)

    4. If num_of_friends > threshold

        - update all RelativeScoreRecords (where RelativeScoreRecords.user_id = user_id), with user_is_megafollower = True

        - create relative ranker (keyed on user_id)

    4. if num_of_friends > (threshhold * .66):

        - send me an email to actually implement this full solution :)

Update Scores Push Task (user_id, new_score):

    1. get() entity for global score, update score, set ranker_dirty to True, and save

    2. query for all RelativeScoreRecords (friend_id = user_id) #(find all records that follow me)

    3. for each person interested in my score:

        - update that RelativeScoreRecord's score

        - if user_is_megafollower: set the ranker_dirty to True

Update Global Ranker Pull Task / Cron Job (GlobalScoreRecord.key):

    * Runs as fast as possible, maybe with a longer delay if it notices that its being idle frequently

    1. Fetch a bunch of new score updates

    2. Bulk update the global ranker

    3. Set the GlobaScoreRecord dirty = False.

Update Relative Ranker Push Task (user_id):

    * Runs in response to being queued up. Task name is based on user_id, so that only one update relative ranker tasks exists for a given person

    1. Query on RelativeScoreRecord (RelativeScoreRecord.user_id = user_id, RelativeScoreRecord.ranker_dirty = True)

    2. Get the relative ranker for that user, and bulk updates with all the score changed

    3. Sets the dirty flag to False for all those RelativeScoreRecords

  

    

[Bartholomew Furrow]

I'm torn between how much time I'm willing to let the leaderboard request take: on one hand, we could fetch it when they open the app, and only do periodic updates while they are playing, so we dont care if it takes a few seconds. On the other hand, I'd prefer to not make the request until they actually select the leaderboards, as many users probably wont even load the leaderboard every time they play (but if its done on the fly, then it needs to be pretty responsive).

That's a tough tradeoff. In Code Jam we decided to make information about ranks load asynchronously after everything critical about the page has loaded (though it takes hundreds of milliseconds rather than seconds).

 

I'm getting a little lost in the specifics of your response. Just to be clear: The relative scores model indicates user A follows user B's score. For all these records, indicate if A is a megafollower (someone interested in a lot of other people's scores). When B updates his or her score, this should trigger A's ranker to get updated offline. I've detailed out the long version of my current understanding below, but I understand if you dont have time to read through it. I likely wont implement this full solution any time soon, but it may prove useful to have on record for myself and others down the line.

Essentially yes. More details below.

My plan was to tie the ranker to the user by convention (using the same key string, the user's id), but not explicitly put them in the same entity group together

Sounds reasonable.

One last question: you mentioned doing a cron job to pick up all the dirty entries. Any reason to use that over a Pull Queue Task, as they suggest here. I haven't used either yet (only push queues, so I'm not really sure which is most appropriate or easiest).

First of all, thanks for linking that article! I'm delighted to see that ranklist was useful to those people, and to see that they managed to optimise it like crazy.

I suspect the pull queue is better than the dirty entries for most purposes, though note that they had a little trouble scaling it (but they sorted it out). As for how to pull stuff off the queue, either a cron job or a backend should work. I don't have experience with the latter.

One way in which the dirty entities works well is that you can query for all dirty entities that indicate someone is a friend of A, and update A's ranklist all at once.

Thanks again for all your input on this! Its been a huge help!

You're welcome!

-Clint

Full details of current and long-term plans:

#--- Models

class GlobalScoreRecord (ndb.Model):

    '''key => immutable user id'''

    score => integer property (not indexed)

    num_of_friends = integer property (not indexed)

    # other property specific to the user profile

class GlobalScoreRecord (ndb.Model):

    ''' key => user_id '''

    score = integer (indexed)

    ranker_dirty = boolean (indexed)

    # other properties that need to be displayed in the actual leaderboard on the client

class RelativeScoreRecord (ndb.Model):

    user_id = key property (indexed)  # aka, the follower

    friend_id = key property (indexed)  # aka, the person being followed

    score = integer (indexed)

    user_is_megafollower = boolean (indexed)

    ranker_dirty = boolean (indexed)

    # other properties that need to be displayed in the actual leaderboard on the

client

I think you want the friend's score here rather than the user's score.

Also, I suspect it will be much more common to have many game players following one game player than to have one game player following many game players. Presumably lots of players will want to follow the person in rank 1, but not many will want to follow the top thousand.

Because of this, I'd avoid ever doing something of the form "every time A scores, do X for each of her followers."

In the simpler scheme, I think that means not keeping scores in these Entities. Rather, when you want to look up your relative rank, query for who all your friends are (maybe even store a list in one Entity rather than having many Entities) and then do an ndb.get_multi on their User objects, or smaller objects that have just the fields you need.

In the more complicated scheme, that means keeping scores in those Entities only for megafollowers. When A scores, query for RelativeScoreRecord objects for which A is the friend, and the user is a megafollower. Update the score in all of those.

Apologies if I missed something lower down; I'll admit that I skimmed once I got to the handlers.

Classic strategy. :-) Make sure to rate limit it. ;-)

Update Scores Push Task (user_id, new_score):

    1. get() entity for global score, update score, set ranker_dirty to True, and save

    2. query for all RelativeScoreRecords (friend_id = user_id) #(find all records that follow me)

    3. for each person interested in my score:

        - update that RelativeScoreRecord's score

        - if user_is_megafollower: set the ranker_dirty to True

Update Global Ranker Pull Task / Cron Job (GlobalScoreRecord.key):

    * Runs as fast as possible, maybe with a longer delay if it notices that its being idle frequently

    1. Fetch a bunch of new score updates

    2. Bulk update the global ranker

    3. Set the GlobaScoreRecord dirty = False.

Update Relative Ranker Push Task (user_id):

    * Runs in response to being queued up. Task name is based on user_id, so that only one update relative ranker tasks exists for a given person

    1. Query on RelativeScoreRecord (RelativeScoreRecord.user_id = user_id, RelativeScoreRecord.ranker_dirty = True)

    2. Get the relative ranker for that user, and bulk updates with all the score changed

    3. Sets the dirty flag to False for all those RelativeScoreRecords

  

    

--

[Clint Doriot]

"One way in which the dirty entities works well is that you can query for all dirty entities that indicate someone is a friend of A, and update A's ranklist all at once."

Pull tasks have a new beta feature, called tags, that could potentially serve that need once its out of beta. I haven't played with it yet, but it seems like I would just set the tag to A's user_id, and then fetch all tasks with that tag (after fetching the first tag to find out the tag). 

"I think you want the friend's score here rather than the user's score."

Yes- I should update the model to reflect that. Also all the "other properties that need to be displayed in the actual leaderboard on the client" are properties of the friend, not the user.

[Bartholomew Furrow]

That all sounds great! I'd love to get an update down the line about how this all went. Good luck, and don't hesitate to ask if you have any more questions!

[Clint Doriot]

Sorry for the late response. I've been hoping to respond earlier, but I'm still trying to get the solution running in a stable manner, and got pulled onto putting out fires in some other projects. Anyways.

First, I've implemented the basics. A push task queue to sync a user's network with Twitter, a push task queue to update leaderboard objects when games are submitted, and a pull task queue to batch update the ranker.

I did have to change the RelativeUserScores Model. Now, instead of tracking 1 friend to 1 follower, I have a list property that tracks 1 friend to many followers. This way I have less objects to update when people change their info, or submit scores, but I can still use the index created by this model to query for all of a given user's friends. I need to make this a sharded model eventually, but its not the next pressing thing.

The next pressing issue I'm running into is that I can only get a throughput of about 40 updates / second for the batch ranker updates, before it stops being able to keep up. For my game, this translates to only about 5-6K CCU (and we need to get much much higher before we can release it). The article I linked to earlier suggested they were able to get to 200 requests per second. I've included my source code below. If you have any ideas as to why I'm falling so short, I'd love to hear your input!

Around the time that this starts getting overloaded, I start getting Transaction Collisions with updating the ranker. Pretty frequently. I only have one thread that is doing updates to the ranker object, and its never operating in parallel. I do however have lots of processes that are going on that are reading from the ranker, to get an individual's current rank. Could this be the cause of the Transaction Collisions? This would be a huge limitation if so.

Also, do you understand what that article was suggesting in the section "Queue Sharding for Stable Performance"? I'm not quite following what problem they are solving here, but I'm assuming I'll need to do it at some point. 

Finally, I remember seeing something about an optimization that can be done to the ranker if you have a disproportionate amount of low vs high scores. As this a global, lifetime points leaderboards, my situation definitely falls into that category. We have to put a pretty big cap on the ranker (currently 1,000,000 pts), so that we dont risk hitting that ceiling any time soon. However, most players will generally be pretty low on board, especially early on (in the thousands to tens of thousands). My branching factor is currently 100. The optimization I saw was to basically spread out buckets in logarithmic way instead of linear. If I implemented this, where would I expect to see the gains in this optimization?

If you have any more suggestions on this, I'd really appreciate it! Thanks again for all your help so far. Despite the long delay, I haven't forgotten about this thread, and I'll definitely be posting back here once its wrapped up and shipped!

========== Code for batch updates to Ranker ==========

# -*- coding: utf-8 -*-

"""Worker handler and thread for processing the pull queue associated with the global lifetime leaderboard ranker"""

#--- Imports

# System imports

import time

import logging

# GAE Imports

import webapp2

from google.appengine.api import background_thread

from google.appengine.api import taskqueue

from google.appengine.runtime import apiproxy_errors

# Project Imports

import configuration as config

import models.leaderboards as leaderboards

#--- Worker Thread

def merge_score_updates(score_updates):

    '''

    Given any number of rank_updates, shallow copy and merge into a new dict

    '''

    result = {}

    for update in score_updates:

        user_id = update['user_id']

        score = None

        try:

            score = [int(update['score'])]

        except:

            pass

        if score:

            current_score = result.get(user_id,[None])

            result[user_id] = max(score, current_score)

        else:

            result[user_id] = score

    return result

def process_global_lifetime_ranker_pull_queue():

    

    q = taskqueue.Queue(config.RANKER_GLOBAL_LIFETIME)

    while True:

        start_time = time.time()

        tasks=None    

        try:

            tasks = q.lease_tasks(3600, 1000, deadline=60)

        except (taskqueue.TransientError, apiproxy_errors.DeadlineExceededError) as e:

            logging.exception(e)

            time.sleep(1)

            continue

        if tasks:

            try:

                task_count = len(tasks)

                score_updates = merge_score_updates([t.extract_params() for t in tasks])

                ranker = leaderboards.GetOrCreateRanker(config.LEADERBOARD_GLOBAL_LIFETIME)

                ranker.SetScores(score_updates)

                q.delete_tasks(tasks)

                elapsed_time = time.time() - start_time

                logging.info("Process Global Lifetime Ranker: %s tasks in %s seconds" % (task_count, elapsed_time))

            except Exception as e:

                logging.exception(e)

#--- Start Up Handler

class GlobalLifetimeRankerPullQueueStarter(webapp2.RequestHandler):

    # TODO: creating locking mechanism to ensure only 1 thread, and that the thread is always running

    def get(self):

        """Creates background tasks to indefinitely update the global lifetime ranker."""

        t = background_thread.BackgroundThread(target=process_global_lifetime_ranker_pull_queue) 

        t.start()     

        self.response.write('')  

#--- WSGI Application

application = webapp2.WSGIApplication(

    [

        webapp2.Route('/_ah/start', GlobalLifetimeRankerPullQueueStarter),

    ],

    config=config.API_HANDLER_CONFIGURATION,

    debug=config.DEV_SERVER)

========== leaderboards.GetOrCreateRanker function ==========

def GetOrCreateRanker(key_name):

    # use ranker key to attempt to obtain existing ranker

    ranker_key = datastore_types.Key.from_path("ranker", key_name)

    try:

        r = ranker.Ranker(ranker_key)    

    except datastore_errors.EntityNotFoundError:

        r = None  

    # if the ranker doesn't exist, create it

    if not r:

        board_config = config.LEADERBOARDS[key_name]

        # TODO: error handling around missing config

        r = ranker.Ranker.Create(

            [board_config['min'], board_config['max']],

            board_config['branching'],

            ranker_key_name=key_name)

    # return the ranker

    return r

--
You received this message because you are subscribed to a topic in the Google Groups "Google App Engine Ranklist" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/google-app-engine-ranklist/QZGuiXV4m3k/unsubscribe.
To unsubscribe from this group and all its topics, send an email to google-app-engine-r...@googlegroups.com.

[Clint Doriot]

One more thing: Is there a way of finding approximate ranks? (I see an FindScoreApproximate, but not FindRankApproximateRank)

Our client is set up to be pretty smart, and merge the various leaderboard outputs (rank, top X players, X players above the requested user, X players below the current user), and merge them into a consistent view. For example, the ranker says the player is #4 in the ranking, but we only find 2 players above the requesting user, we know that some information hasn't been fully processed, and that the player's rank is really #3. And if they aren't in the top X players, the leaderboard shows a gap (1,2,3, ... 98, 99, me, 101, 102). So, I don't really care if we tell the user they are #100 or #101 or #99. Its close enough to get a ballpark, and more importantly, it looks consistent to the end user. So, even with some conflicting data from the leaderboard request, we can create a consistent view for the player, even if its not 100% up to date or accurate.

What I'm thinking is that with the loads we need to hit (100K CCU), we're going to need to shard the entire ranklist, even if we do manage to hit 300 updates per second for a single ranklist. We'll probably need somewhere between 3-10 shards. The GAE article posted earlier suggest sharding is the next step, and then getting a player's rank by querying and adding the ranks returned by all shards. Since there may be a lot of rank look up requests, I'm trying to see if I can't optimize that part too by just finding approximate ranks.

[Bartholomew Furrow]

I'll respond to your second email first, since it's easier:

The reason FindScoreApproximate exists is because finding a score for a rank requires O(log(score range)) RPCs. It cuts off as soon as it can confidently say "this is the highest rank with a score below X" since that's all a lot of users need anyway. Cutting off saves some of those multiple RPCs.

FindRank(s) has O(1) RPCs (I think it's just 1), because we already know which nodes of the tree we need to retrieve in order to figure out someone's rank. I don't see an obvious way to improve it, though it's certainly possible that one exists.

OK, here's one. Periodically precompute the scores for all rounded integer powers of 1.01. That's 1400 scores for a million users, and an extra 230 for every factor of ten after that. Store the resulting list in memcache and look it up when people want their approximate ranks. Interpolate to get your rank to within 1%, and probably better on average.

I'll leave it to you to figure out how to effectively call FindScoreApproximate 1400 times efficiently. If all else fails you could write FindScores and find them all at once, for O(log (score range)) very large RPCs.

Bartholomew

[Bartholomew Furrow]

OK, next sub-response: logarithmic distribution, which you may have seen in an earlier email on this list from me. Rather than spacing the buckets out exponentially, which is how I probably should have said it, the approach I'd take is to take X*log(score) and put that into the ranklist instead of score itself.

If you have a score distribution that looks Zipfian, this will help you end up with your scores evenly distributed in tree nodes, instead of focused on just the first ones. Better distribution means fewer transactional collisions if you have multiple threads updating the ranklist.

A couple of other thoughts:
- Don't bother putting people with a score of 0 into your ranklist, in case that helps.
- Another way to make everything approximate is to round people's scores. Instead of score, put score/100 in, and you will need a smaller score range and thus fewer nodes.

[Bartholomew Furrow]

A few thoughts, since nothing obvious is popping out:
- Are you sure the collisions are in the update tasks rather than the read tasks? Read tasks should collide when something is updated out from under them, but I don't know what a write task would collide with. Maybe there's such a thing as a reader lock here.
- What happens when you go above the maximum number of CCU that you've gotten so far? Does the task queue grow, or does the job pulling from it start throwing exceptions, or what?
- I believe you can actually get more throughput by adding more updaters.
- We're talking about your global ranklist rather than one for friends, right?
- Good solution for the friends.
- Can you add more logging to your updater job? Does the time go to pulling tasks from the queue, or updating the ranker, or what? Can I see some output?
- Can I see the board config for the global ranklist?

> GetOrCreateRanker

For the global leaderboard, you should assume it exists; otherwise you're getting the root an extra time for no reason. Make yourself an Init function that you run in the interactive console every time you start dev app server on a new machine, or something.

[Clint Doriot]

I'm consolidating your various responses back into one, and go back up through the comments.... Your responses in bold.

Are you sure the collisions are in the update tasks rather than the read tasks? Read tasks should collide when something is updated out from under them, but I don't know what a write task would collide with. Maybe there's such a thing as a reader lock here.

Definitely in the write task- Its on its own module with separate logs. All the readers read just fine without errors. I'm pretty sure the readers wouldn't lock it; I can't find the GAE documentation that says that, but that was my working assumption, and I asked a GAE support engineer earlier today.

What happens when you go above the maximum number of CCU that you've gotten so far? Does the task queue grow, or does the job pulling from it start throwing exceptions, or what?

The task queue starts growing and I get a lot of warnings: "Transaction collision. Retrying...." (no other details). Less frequently I get an actual error:

The transaction could not be committed. Please try again. Traceback (most recent call last): File "/base/data/home/apps/s~leaderboard-load-test/ranker-global-lifetime:3.384473439320731824/ranker-global-lifetime.py", line 68, in process_global_lifetime_ranker_pull_queue ranker.SetScores(score_updates) File "/base/data/home/apps/s~leaderboard-load-test/ranker-global-lifetime:3.384473439320731824/lib/ranker/common.py", line 30, in transactional_operation return datastore.RunInTransaction(operation, *args, **kwargs) File "/base/data/home/runtimes/python27/python27_lib/versions/1/google/appengine/api/datastore.py", line 2487, in RunInTransaction return RunInTransactionOptions(None, function, *args, **kwargs) File "/base/data/home/runtimes/python27/python27_lib/versions/1/google/appengine/api/datastore.py", line 2631, in RunInTransactionOptions 'The transaction could not be committed. Please try again.') TransactionFailedError: The transaction could not be committed. Please try again.

I believe you can actually get more throughput by adding more updaters.

> GetOrCreateRanker...

I could definitely see staging this so that I'm simultaneously calling SetScores, and leasing / preprocessing the next batch of scores. But I'm not sure how...

- I don't think a single thread can do it, since there is no asynchronous method for leasing tasks or for setting scores.

- Wouldn't having two threads potentially trying to write to the ranker be more likely to cause TransactionFailedErrors? Could I rely on the transactional nature to get them to align properly?

We're talking about your global ranklist rather than one for friends, right?

Yes. I'd only need ranklist if the player had a lot of friends (is the mega follower). I'm currently assuming this isn't going to happen, at least in the near future.

For the relative leaderboards, I just do a query count, filtered by objects where the player is the follower, and the score is higher.

Good solution for the friends.

Thanks :)

Can you add more logging to your updater job? Does the time go to pulling tasks from the queue, or updating the ranker, or what? Can I see some output?

I'll add that for the next test, but wont be able to test and get back to you until tomorrow. Right now, the logs are just filled with the warnings, the occasional errors, and the frequent ("Process Global Lifetime Ranker: 22 tasks in 1.27134013176 seconds"), that is being logged from the current code.

Can I see the board config for the global ranklist?

LEADERBOARDS = {

    '_global_lifetime' : {

        'min' : 0,

        'max' : 1000000,

        'branching' : 100

    }    

}

Don't bother putting people with a score of 0 into your ranklist, in case that helps.

I'm not. Its only trigger when the player has a positive score. There is a potential for a player to be removed from the leaderboard if they disconnect their Twitter account, but I'm treating that as simply writing ( user_id, [None] ) in the update process-- and that doesn't apply to these tests, as my player bots cant disconnect

Another way to make everything approximate is to round people's scores. Instead of score, put score/100 in, and you will need a smaller score range and thus fewer nodes.

Hmmm, thats an interesting idea. That would help the reads, but not necessarily the writes, correct?

OK, next sub-response: logarithmic distribution, which you may have seen in an earlier email on this list from me. Rather than spacing the buckets out exponentially, which is how I probably should have said it, the approach I'd take is to take X*log(score) and put that into the ranklist instead of score itself.

If you have a score distribution that looks Zipfian, this will help you end up with your scores evenly distributed in tree nodes, instead of focused on just the first ones. Better distribution means fewer transactional collisions if you have multiple threads updating the ranklist.

Oh, nice! I'm pretty confident its going to be a Zipfian distribution, so I'll incorporate that in the next test. I take it X is just configuration point, where it trades off precision in rank with number of nodes needed in the algorithm? 

In that other thread you wrote "Take log(score), multiply it by 1e10, and put that in. Make your ranklist go up to something like 1e14. You'll have a ton of precision, and it will automatically treat close scores as ties that you can deal with outside the ranklist"

So, I'm inputing scores as 1e10*math.log(actual_score), and the ranklist is [0,1e14) ? Isn't that more nodes to deal with? Any recommendation on branching factor here?

How does this decrease transactional collisions, if all the ranklist objects have the same ancestor? Wouldn't all modifications in one SetScores preclude modifications in another SetScores call, even if the ranker_nodes and ranker_scores are mutually exclusive between the two calls?

The reason FindScoreApproximate exists is because finding a score for a rank requires O(log(score range)) RPCs. It cuts off as soon as it can confidently say "this is the highest rank with a score below X" since that's all a lot of users need anyway. Cutting off saves some of those multiple RPCs.

FindRank(s) has O(1) RPCs (I think it's just 1), because we already know which nodes of the tree we need to retrieve in order to figure out someone's rank. I don't see an obvious way to improve it, though it's certainly possible that one exists.

OK, here's one. Periodically precompute the scores for all rounded integer powers of 1.01. That's 1400 scores for a million users, and an extra 230 for every factor of ten after that. Store the resulting list in memcache and look it up when people want their approximate ranks. Interpolate to get your rank to within 1%, and probably better on average.

I'll leave it to you to figure out how to effectively call FindScoreApproximate 1400 times efficiently. If all else fails you could write FindScores and find them all at once, for O(log (score range)) very large RPCs.

Ok, you lost me here :) Mainly that suggested optimization about "periodically precomputing the scores..."

Honestly, I dont understand the usage of FindScores / FindScoresApproximate, except maybe using it page through the leaderboards (for example, you know want to show the leaderboard for ranks 10-20). If that is true, we don't really need to use for this application, since they player can't page through results, they only get small subset. 

Unless I'm paging through results on a backend thread to generate periodically updated pages, and then caching those somewhere?

Bottom line seems to be that reading the rank is fast. Reading 10 ranks across sharded ranklists is slower, but likely still fast enough?

[Bartholomew Furrow]

Thanks for consolidating: I'm mostly writing from my phone, so it's harder for me.

One immediate recommendation: make the maximum 999999. You'll save a level of depth, because it's inclusive-inclusive.

[Bartholomew Furrow]

>

I'm pretty sure the readers wouldn't lock it; I can't find the GAE documentation that says that, but that was my working assumption, and I asked a GAE support engineer earlier today.

I'd love to hear the answer. As an alternative, you could do a loadtest or something with only single-threaded writes and see if it still happens.

> tasks = q.lease_tasks(3600, 1000, deadline=60)

It looks like you're pulling a thousand tasks at once. Can you give me a breakdown of what happens when you get a thousand tasks? A hundred? Ten? How long does it take to run, and how often does it fail? Let's try to find the optimal number of tasks to pull.

> GetOrCreateRanker...
This is still worth changing.

I believe you can actually get more throughput by adding more updaters.

I could definitely see staging this so that I'm simultaneously calling SetScores, and leasing / preprocessing the next batch of scores. But I'm not sure how...

- I don't think a single thread can do it, since there is no asynchronous method for leasing tasks or for setting scores.

This isn't what I had in mind, but it looks like the background task api just spawns a thread to run a function. Once you've figured out how long each thing takes, you could (for example, if the timing worked out that way) always run UpdateScores in a separate thread, and wait for it to return before calling it again.

.

Wouldn't having two threads potentially trying to write to the ranker be more likely to cause TransactionFailedErrors? Could I rely on the transactional nature to get them to align properly?

Yes it would, but it's worth a shot to see if it's faster anyway. It's an easy thing to try, and if the transaction is actually a small piece of the running time, it would help.

We're talking about your global ranklist rather than one for friends, right?

Yes. I'd only need ranklist if the player had a lot of friends (is the mega follower). I'm currently assuming this isn't going to happen, at least in the near future.

For the relative leaderboards, I just do a query count, filtered by objects where the player is the follower, and the score is higher.

Solid decision IMO.

Can I see some output?

("Process Global Lifetime Ranker: 22 tasks in 1.27134013176 seconds"), that is being logged from the current code.

I really, really want to see a time vs. number of tasks distribution, even if only very roughly.

Can I see the board config for the global ranklist?

LEADERBOARDS = {

    '_global_lifetime' : {

        'min' : 0,

        'max' : 1000000,

        'branching' : 100

    }    

}

Revising my previous advice after reading the code: I would still set max to be 999999, but I believe it's fine not to do that.

Another way to make everything approximate is to round people's scores. Instead of score, put score/100 in, and you will need a smaller score range and thus fewer nodes.

Hmmm, thats an interesting idea. That would help the reads, but not necessarily the writes, correct?

Fewer nodes means fewer nodes to write. Heck, with scores between 0 and a million, I'd just give it a branching factor of 10000 and store it all in a list in the root node. But another option is to use a branching factor of 1000 and not do the division. You would have a very manageable 1001 nodes to work with, and many score updates would only affect one node. I don't know if it would be better, but again it's easy to try and worth benchmarking.

OK, next sub-response: logarithmic distribution, which you may have seen in an earlier email on this list from me. Rather than spacing the buckets out exponentially, which is how I probably should have said it, the approach I'd take is to take X*log(score) and put that into the ranklist instead of score itself.

If you have a score distribution that looks Zipfian, this will help you end up with your scores evenly distributed in tree nodes, instead of focused on just the first ones. Better distribution means fewer transactional collisions if you have multiple threads updating the ranklist.

Oh, nice! I'm pretty confident its going to be a Zipfian distribution, so I'll incorporate that in the next test. I take it X is just configuration point, where it trades off precision in rank with number of nodes needed in the algorithm? 

Yes. An equivalent way to think of it is as log base Y of score. Make Y 1.01 and your ranklist only needs to keep track of 1389 numbers. But if that precision isn't good enough, you can raise it.

If you really want to get fancy you could have score ranges that increase exponentially with bucket index:  the first bucket gets 1, the second bucket gets 2-10, the third bucket gets 11-100, etc. For your scenario, with a million possible scores: not worth it.

A quick aside: since you have so few possible scores, I wonder whether there's a simpler solution than using ranklist.

T

he ranklist is [0,1e14) ? Isn't that more nodes to deal with? Any recommendation on branching factor here?

Yeah, those numbers wouldn't work for you. :-) I almost think the logarithmic thing is pointless given that you can get two layers of nodes with a simple branching factor of 1000.

How does this decrease transactional collisions, if all the ranklist objects have the same ancestor? Wouldn't all modifications in one SetScores preclude modifications in another SetScores call, even if the ranker_nodes and ranker_scores are mutually exclusive between the two calls?

No, actually. It has do to some extra bookkeeping, which is a little slow, but that doesn't cause a collision.

Periodically precompute the scores for all rounded integer powers of 1.01. That's 1400 scores for a million users, and an extra 230 for every factor of ten after that. Store the resulting list in memcache and look it up when people want their approximate ranks. Interpolate to get your rank to within 1%, and probably better on average.

I'll leave it to you to figure out how to effectively call FindScoreApproximate 1400 times efficiently. If all else fails you could write FindScores and find them all at once, for O(log (score range)) very large RPCs.

Ok, you lost me here :) Mainly that suggested optimization about "periodically precomputing the scores..."

Revised suggestion: have a cron job periodically call GetRanks(range(100) + range(100, 1000, 10) + range (1000, 10000, 100) + ...)
Then stick the result in memcache. That's about a list of 460 integers, so it's small. To  get an approximate rank, pull that list from memcache. Interpolate to get your approximate rank. If you might be in the top , 100, go to the ranklist: your exact rank is probably important.

This is my favourite idea so far for getting reads out of the way and making them fast if that would help. You could, of course, get more precision by refining my rough calls to range.

Ho

nestly, I dont understand the usage of FindScores / FindScoresApproximate, except maybe using it page through the leaderboards (for example, you know want to show the leaderboard for ranks 10-20).

That's what it's for. :-)

As far as I can tell, I've responded to everything so far, but I have a niggling feeling that I missed something. Please assume it wasn't intentional, and sorry for the abominable formatting.

Bartholomew