Google App Engine scalability that doesn’t just work

Now that I’ve got enough of Project Fangorn’s features implemented for it to be playable, I spent some time reflecting on the experience of utilizing Google App Engine’s datastore and it strikes me that there are things about it that actually don’t scale and its API does not provide it-just-works (IJW) scalability. In theory (there are still quotas in place) GAE’s infrastructure will allow GAE hosted applications to scale to hundreds of millions of users accessing billions of pieces of data (GAE entities) but the constraints GAE places on the applications it hosts means this scalability doesn’t just come along for free when writing to the GAE API. Follows are a number of the constraints:

  • Application code is run in response to a user request for web page (i.e. no daemons, services, cron jobs, long running service process, etc.)
  • Application code only has a limited and variable amount of time respond to a user request for a web page (no more then about 10 seconds)
  • GAE limits data store query results to 1000 entities
  • GAE can’t not tell you how many total entities there are of a specific type and it can’t count more then 1000 entities.
  • GAE limits the entities that can be processed in a single transaction to those in the same entity group and only one request processing instance can write to an entire entity group at a time.
  • The GAE entity properties for lists will cause the indexes to explode if they contain more then some undocumented amount (appears to be around 5000).
  • GAE can only run Python code
  • GAE’s version of Python does not include marshall or cpickle, only the slow pickle

One of the problems these restrictions causes is that counting entities is non-trivial, not guaranteed to scale, and has to be designed in from the start. Since you can’t get a count of entities from GAE, your application code as to do it. Since you don’t get any kind of long running process your only opportunity to do the counting in GAE is in processing a user request.

To avoid the contention issues involved with hundreds, thousands, or millions users requests all trying to increment the same counter simultaneously, a single global counter can’t be used, since writes to the counter will be serialized up to limit in a given time frame and then any requests of the limit rejected. One solution is to break the counter up across separate entities and sum fragment when the value of the current value of the counter, but then how many entities is enough? 1 per 10 page requests second? 1 per 100? 1 per 1000000?

It’s hard to say so it would really need to be dynamic (there’s the non-trivial part), but then again there you can only get 1000 records per query and you can only get in so many queries in 10 seconds (or less), so there is a non-deterministic upper limit on how granularly you can fragment a counter that can smack into the amount of fragmentation necessary to process rate of update simultaneous update requests that need to be processed simultaneously (there is the not guaranteed to scale part).

As to the designed in from the start part, that’s because you can’t have a long running process to seed the count of entities if the app hasn’t been counting them from the start, so either you would need to download all of the entities off GAE so you could count them elsewhere, each request would need to do a side task of counting some of the entities in addition to what it actually needs to fulfill the user request, or you need a dedicated page to request to do this work and an offsite client to keep requesting the page until the work is finally done Either way there is a scalability issue. In the first case, is the pipe to your offsite processing center big enough to keep up with the new entities and is offsite farm up to storing and counting the entities? In the second case you’ve only got a very limited amount of time you can spend on a side task thus limiting you to working on only counting up one new counter at a time (or taking a lot longer to do several in parallel).

Another area where GAE doesn’t just work is with numerous small pieces of data strongly associated with another more key of piece of data such that that the small pieces of data aren’t interesting to query on their own. There are two ways to store such small pieces of data. The first is as separate entities that have to be queried for. Even if the limit of 1000 per query doesn’t cause complications to you code, GAE data store queries have to be presumed slower then RDBMS queries. Since they don’t need to be queried for separately from the more key piece of data, the numerous small pieces of data should probably be stored as list elements on the same entity as the key piece of data is stored, assuming there a fewer pieces of data then will cause the indexes to explode.

However, if the small pieces of data consist of more then on field like say a future event type and time to trigger you either need to use a separate list for each field which increases the complexity and fragility of your code, or you need to marshal both fields into a string (or the entire data set into a binary blob), neither of which is IJW. This later one is where the lack of cpickle matters since you’ve either got to use pickle which is pretty slow or if that is too slow you may have to write hand optimized marshalling code for each small piece of data.

A specialized area, where I ran into difficulties with Project Fangorn, was in trying to determine the ranks of players based on their score. This can be done with a simple query in an RDBMS, but GAE queries can’t provide this information unless you limit the number of players to 1000, which definitely doesn’t scale. I’ve got a tentative solution, but I’m not certain that I won’t run into contention issues since the ranks actually have to stored in the data store and updated constantly as player’s scores change. I’m just going to have to see how it holds up and if it doesn’t I’m not quite sure what I’ll be able to do about due to GAE’s locking model. All of the entities definitely can not be group as that would create a single write lock all the player’s would be constantly in contention for. On the other hand ranks have to be updated in a transaction or they could (will eventually) get corrupted. I’ve grouped the entities into small groups with a side entity to use a scratch pad for moving entities between groups so there can still contention for these small groups. Here again there is a question of what the right group size is.

This entry was posted in Web development and tagged , , , , , . Bookmark the permalink.

Have something to say?

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

You are commenting using your 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 )

Connecting to %s