Leaderboards are (mostly) back online…

As you might have noticed, the leaderboards for SameSame, Brickade2 and my new MeGoo toy game “CuteBrain” have been down for a couple of days. After some heavy re-writing of the server code, they are now back online and should work without any problems [until the next time Google screws up]..

The Technical stuff

If you are interested in the technical details, please read on. If you are not, you can safely ignore the rest of this post.

Why the leaderboards stopped working

The leaderboards are organized as tables in a database running on Google’s cloud computing service, the App Engine. I pay nothing for these particular servers since the amount of computation needed for the leaderboards is (was) well below Google’s daily free quote.

However, a few weeks back Google changed they way they compute their free quota. With the new system, you would get up to 50.000 database fetches for free. Above that you would have to pay Google. While 50.000 may sound a lot, it is actually an extremely small number. In fact, due to Google’s very inefficient database implementation, it is barely enough to look up a single players position in the leaderboard:

SELECT COUNT(*) from samesame_table where score > your_score

Sine this table has around 60.000 entries, the database will have to iterate over 60.000 rows to compute your position. With the new quota system, one such lookup is already above your daily free quota.

How we fixed the leaderboard

With the new quota system, the leaderboards would have cost us around USD 3.000 / year to run. This is simply too much for a hobby project. Besides, you can buy and run your own server for much less.

A much cheaper solution was to re-write the leaderboard software to avoid the expensive database operations. This is exactly what we did:

Use Memcache instead of Datastore

To avoid the expensive database operations, we added the a caching mechanism where common queries are stored to avoid further database lookups. So Instead of always doing a database lookup like this

// SELECT COUNT(*) from samesame_table where score > your_score
PersistenceManager pm = ...
Query q = pm.newQuery(SameSame.class, “this.score > score”);
q.setResult(“COUNT(*)”);
q.declareParameters(“Long score”);
Object count = q.executeWithArray(your_score);

We would do something like this

import com.google.appengine.api.memcache.*;
...
MemcahceService service = MemcacheServiceFactory.getMemcacheService();
Object count = service.get(“your_position_” + your_score); // is it already cached?

if(count == null) {
    PersistenceManager pm = …
    Query q = pm.newQuery(SameSame.class, “this.score > score”);
    q.setResult(“COUNT(*)”);
    q.declareParameters(“Long score”);
    Object count = q.executeWithArray(your_score);

    service.put(“your_position_” + your_score, count); // save it for later use
}

Limit Datastore use even further

With the Memcache, once the caches are filled the number of database accesses will decrease significantly. Our next problem was that since the free quota was set so extremely low, it was not even enough for a single database query. Hence we could never get as far as filling the cache with data.

A small hack we used to get past this was to limit the query size to a subset of the database. Since the rows are fetched in batches of 100, we limited the query size to 99:

Query q = pm.newQuery(SameSame.class, “this.score > score”);
q.setRange(0, 99);
...

While this is not always correct, it was the only way to get thing working. With this hack in place, we can now (barely)run the servers within the free quota

Cleanup your database!

We have also added a daily cron job which cleans the database by removing the lowest ranking entries. This will hopefully shrink the SameSame table a bit since there are a number of total n00b scores in there

Client side changes

A new client app will be introduced soon, which will refuse to submit your score to leaderboard if your score is very low or if it has not increased since the last update.

Lessons learned

If there is anything to be learned from all this is that you should never trust your cloud provider. They can screw up and they can screw up badly, and they have no problems charging your credit card for their mistakes.