Social game: efficient implementation of top table with rating/rank of the user

Some time ago I designed very efficient pattern of top-n table implementation for social games. There are a lot of users (few millions). Our goal is quickly compose top-n table for any user. Generally, each user has its own top-n table, because the table contains information about the user either he’s in the top or not. Let’s assume users has the score and we build the top-n table by that score. So, most top user in the table (rank=1) has max. score.
As we have social game, so, it’s ok to have not exactly actual top-n table, but some version cached for an hour or 20 minutes. We will update the table in the cache every 20 minutes. The question is about how to represent information of the user (current one). His score is available, but his rank in the actual top-n table is not available if the user is not in the top. It should be calculated on fly. Keep in mind, that we don’t cache whole users table ordered by the score, but only n top records.
The idea is to avoid full table scan but and use linear interpolation to gues approximate rank for user out of top table.
If user has the same score as last user in the top then the rank is N+1.
In other case:
rank = -(UsersCount – N – 1)*(score – Max)/Max + N + 1,
where
UsersCount is total number of users,
N is the size of top table,
score is the score of the user,
Max is the score of last user in the top table.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: