rankings in a high score server

[riq]

Hi,

Thanks for releasing this project.

I've implemented a high score server in GAE ( http://code.google.com/p/cocoslive/
).
And I would like to implement rankings in it using your code.

I'm been playing with your code, and I must confess that I'm not an
expert neither in GAE nor in DB/sharding stuff.

I would like to know if the following features are possible:

1) It is possible to have multiple rankings running ?
From what I've seen, it is possible to store a new ranker in any
Entity, right ?

contest = datastore.Entity('contest_1')
rank = ranker.Ranker.Create([0, 10000, -999999, 1], 100)
contest['ranker'] = rank.rootkey
datastore.Put(contest)

contest = datastore.Entity('contest_2')
rank = ranker.Ranker.Create([0, 10000, -999999, 1], 100)
contest['ranker'] = rank.rootkey
datastore.Put(contest)

etc...


2) If I would like to know the ranking in ascendant order, what
changes should I do and where ? (lower score is the better)

3) Is is possible to support floats instead of intengers ? What
changes should I do to support it ?


Thanks in advance,

riq.

[Bartholomew Furrow]

1) It is possible to have multiple rankings running ?
From what I've seen, it is possible to store a new ranker in any
Entity, right ?

Yup!  Your sample code should, if I'm not forgetting anything, do exactly what you want.

2) If I would like to know the ranking in ascendant order, what

changes should I do and where ? (lower score is the better)

Our example ranker, which you built above, has such a score -- we just have a positive score (in our case a time), multiply it by -1 and put it in the ranker.  If you want to make one of your own:

rank = ranker.Ranker.Create([-10, 1], 100)

Then you just put -score into the ranker and it can take scores from 0 to 10.

3) Is is possible to support floats instead of intengers ? What

changes should I do to support it ?

The easiest way is to pick a precision and stick to it.  Suppose you wanted scores between 0 and 100, accurate to 3 decimal  to go to three decimal places, with lower scores being better.  Then you'd want a ranker:

ranker.Ranker.Create([-100 * 10**3, 1], 100)   #  == 100000 == 10**5

Then when putting score in (sorry if I get the library's syntax wrong; it's been a while)

score = 53.1234

rank.add(int(score * -1000))

...which adds -53123 into your ranker.  The ranker will claim this is a tie with score=53.1235, but do you really care?

[Bartholomew Furrow]

I should add that if you do really care, and if you do need to support floats, it's a little tricky -- and we deliberately decided not to do it.  One thing you could do is add an extra level to the tree, and the bottom level could be a list of the scores inside.  So there would be a node for -53123 that contained the list [-53123.4, -53123.5].

Again, this is tricky, has painful performance edge cases and quite possibly solves a problem that you could more easily work around in another way.

By the way, the transformation could be pretty much anything.  Rather than multiplying by -1000, you could apply an arbitrary function to get the amount of precision you wanted in the areas where you needed it (e.g. near 0).

[riq]

Thanks Bartholomew!

riq.

--
http://blog.sapusmedia.com
http://monodiario.blogspot.com

[Bartholomew Furrow]

Sure thing!  If it works out for you, let us know!

--~--~---------~--~----~------------~-------~--~----~ You received this message because you are sub...

[riq]

On Tue, Apr 28, 2009 at 6:32 PM, Bartholomew Furrow <fur...@gmail.com> wrote:
> Sure thing!  If it works out for you, let us know!

Hi,

Yes, I did some initial tests and it seems that everything is working Ok.

Since the highscore server is hosting lots of games, and each game can
have different "categories" (eg: easy, hard, etc...) I'm creating the
entity like the following:
app = datastore.Entity("Ranking", name=category, parent=game.key() )
app["ranker"] = r.rootkey

Thanks,

[Bartholomew Furrow]

That looks about right.  Is the Put of a score transactionally linked to the AddScore in the ranker?

[riq]

On Wed, Apr 29, 2009 at 7:31 PM, Bartholomew Furrow <fur...@google.com> wrote:
> That looks about right.  Is the Put of a score transactionally linked to the
> AddScore in the ranker?

No. How can I do that ?

Since I can't nest transactions in GAE, what's the best approach ?

I'm doing the following:

scores.add_score(...) # runs in a transaction.
ranker.SetScore(...) # runs in another transaction

if ranker.SetScore() fails, how can I rollback the 1st trasaction ?

Also,
Is is possible to delete an score from the ranker ?

Thanks!

[Sebastian Kanthak]

On Thu, Apr 30, 2009 at 3:46 AM, riq <ricardo...@gmail.com> wrote:

On Wed, Apr 29, 2009 at 7:31 PM, Bartholomew Furrow <fur...@google.com> wrote:
> That looks about right.  Is the Put of a score transactionally linked to the
> AddScore in the ranker?

No. How can I do that ?

Since I can't nest transactions in GAE, what's the best approach ?

I'm doing the following:

scores.add_score(...)  # runs in a transaction.
ranker.SetScore(...)    # runs in another transaction

if ranker.SetScore() fails, how can I rollback the 1st trasaction ?

You're right that you can't achieve this directly because you cannot nest transactions.

One way to achieve something similar is by adding a boolean "dirty" attributes to score and have a cron job that cleans up dirty scores. Something like this:

# Whenever a score changes or a new score arrives:
score = ...
scores.add_score(score)  # runs in a transaction and marks score as dirty
ranker.SetScore(...)   # runs in a transaction
scores.mark_clean(score)  # runs in a transaction and marks score as clean if it wasn't changed concurrently


# In a cron job that runs at a regular interval
<retrieve all scores that are dirty, i.e. where the ranker wasn't updated>
<update the ranker and mark the scores as clean>

Also,
Is is possible to delete an score from the ranker ?

Yes: ranker.SetScore(name, None).

Sebastian

[Bartholomew Furrow]

One way to achieve something similar is by adding a boolean "dirty" attributes to score and have a cron job that cleans up dirty scores. Something like this:

# Whenever a score changes or a new score arrives:
score = ...
scores.add_score(score)  # runs in a transaction and marks score as dirty
ranker.SetScore(...)   # runs in a transaction
scores.mark_clean(score)  # runs in a transaction and marks score as clean if it wasn't changed concurrently

I should note, though, that if the user is expecting a response some time soon, you can reduce the response time by just stopping before the SetScore and letting the cron job clean everything up.

# In a cron job that runs at a regular interval
<retrieve all scores that are dirty, i.e. where the ranker wasn't updated>
<update the ranker and mark the scores as clean>

One addition to that second point: "mark the scores as clean" should be done in a transaction -- Get, Verify Unchanged, if changed Mark Dirty, else Mark Clean, Put.

Notice, by the way, that what Sebastian's doing is first updating the score -- which you can do as many times as you like without doing damage -- and then verifying that it's right and marking the row as clean.  While this doesn't all happen in a transaction, the order in which it's done guarantees that any failures will only impact repeatable parts of the process.

[riq]

Thank you for the tips!

I'll implement it after the weekend.

Thanks again,