cloud-test: Reducing ranking latency from one hour to five seconds using Cloud Datastore

Google Cloud Platform Blog

Reducing ranking latency from one hour to five seconds using Cloud Datastore

Thursday, July 31, 2014

We recently published a case study, Fast and Reliable Ranking in Datastore, that describes how we helped one of our Google App Engine customers shorten their ranking latency from one hour to five seconds. They applied unique design patterns such as job aggregation to achieve over 300 updates per second with strong consistency on Cloud Datastore. The following are highlights from the article.The problem of rankingApplibot

Tomoaki Suzuki, App Engine lead engineer at Applibot, Inc. and their game Legend of Criptids (#1 ranked game in the Apple App Store North America gaming category in October 2012)

Your game has hundreds of thousands (or more!) players.

Whenever a player fights enemies (or performs other activities), their score changes.

You want to show the latest ranking for the player on a web portal page.

SELECT count(key) FROM Players WHERE Score > YourScore

The easiest way: scan all players

MemcacheLooking for an O(log n) Algorithmplatinum support contracttree algorithmsGoogle Code Jam Ranking Library

Getting the rank of a score in a tertiary tree with google Code Jam Ranking Library

Concurrent Updates Limit Scalabilityentity groupBalancing Strong and Eventual Consistency with Google Cloud Datastoreone transaction per secondDatastore Team's Solution: Job AggregationMegastoreVoltDbRedisProposed Solution Runs at 300 Updates per Second Sustainedpull queueTask Queue