Ikai Lan says

I say things!

App Engine datastore tip: monotonically increasing values are bad

with 20 comments

When saving entities to App Engine’s datastore at a high write rate, avoid monotonically increasing values such as timestamps. Generally speaking, you don’t have to worry about this sort of thing until your application hits 100s of queries per second. Once you’re in that ballpark, you may want to examine potential hotspots in your application that can increase datastore latency.

To explain why this is, let’s examine what happens to the underlying Bigtable of an application with a high write rate. When a Bigtable tablet, a contiguous unit of storage, experiences a high write rate, the tablet will have to “split” into more than one tablet. This “split” allows new writes to shard. Here’s a visual approximation of what happens:

There’s a moment of pain – this is one of the causes of datastore timeouts in high write applications, as discussed in Nick Johnson‘s article, “Handling Datastore Errors“.

Remember that for indexed values, we must write corresponding index rows. When values are randomly or even semi-randomly distributed, like, say, user email addresses, tablet splits function well. This is because the work to write multiple values is distributed amongst several Bigtable tablets:

The problems appear when we start saving monotonically increasing values like timestamps, or insert dictionary words in alphabetical order:

The new writes aren’t evenly distributed, and whichever tablet they end up going to end up becoming a new hot tablet in need of a split.

As a developer, what can you do to avoid this situation?

  • Avoid indexes unless you need to query against the values. No index = no hot tablet on increasing value
  • Lower your write rate, or figure out how to better distribute values. A pure random distribution is best, but even a distribution that isn’t random will be better than a predictable, monotonically increasing value
  • Prefix a shard identifier to your value. This is problematic if you plan on doing queries, as you will need to prefix and unprefix the values, then join the results in memory – but it will reduce the error rate of your writes

The tips are applicable whether you are on Master-Slave or High Replication datastore. And one more tip: don’t prematurely optimize for this case, since chances are, you won’t run into it. You can be spending that time working on features.

- Ikai

P.S. Yes, I drew those doodles. No, I do not have any formal art training (how could you tell?!)

About these ads

Written by Ikai Lan

January 25, 2011 at 6:26 pm

20 Responses

Subscribe to comments with RSS.

  1. I have a ‘last modified’ property on all of my datastore objects. Will having this cause a significant slow down if my app starts getting tons of writes?

    Kyle

    January 25, 2011 at 6:57 pm

  2. Thanks so much for the tips! I think my app has such problem as it has an index on “updated_at” which the entity is updated on every request (for a single user).

    Ray C.

    January 25, 2011 at 7:10 pm

  3. Great article

    Karan

    January 25, 2011 at 7:23 pm

  4. Hard to say – again, you have to be doing hundreds of QPS for this to matter.

    Ikai Lan

    January 25, 2011 at 8:39 pm

  5. Not necessarily. Again, you have to be doing LOTS of QPS before this should matter.

    Ikai Lan

    January 25, 2011 at 8:39 pm

  6. I won’t pretend to understand what i have just read, but i was definitely entertained by your tablets. :)

    Jamal

    January 25, 2011 at 10:04 pm

  7. I barely used AppStore but I enjoyed the doodles :-)

    What I became more interested about is actually how BigTable functions and does that whole tablet auto-sharding…

    Emilian Bold

    January 25, 2011 at 11:26 pm

  8. Very fun explanation.

    Alexandre Verri

    January 26, 2011 at 3:12 am

  9. Hi, Ikai,

    your post is useful, but my particular interest was picked by your cartoon style. Did you do it by hand or did you use any illustration software?

    Thanks a bunch!

    Mark Kerzner

    January 26, 2011 at 11:14 am

  10. Hilarious! Thanks for the comment. I just doodled them on a whim and scanned them in.

    No software, though I thought about redoing them in illustrator or putting some Photoshop filters to clean up my mistakes … but then I realized that the imperfections better, not worse.

    Ikai Lan

    January 26, 2011 at 11:18 am

  11. I know you said it’s probably not worth worrying about, or optimizing for this, but I got to thinking about auto_now datetimes (like other folks) and came up with this ShardedDateTimeProperty:

    https://gist.github.com/797802

    Would this work?

    Calvin

    January 26, 2011 at 4:16 pm

  12. How can i control the splitting….

    Can i say tell it to split by user or account number…..

    kcw

    February 1, 2011 at 3:41 am

  13. I am impressed by your drawing skills =)

    Kaan Soral

    February 15, 2011 at 1:09 pm

  14. Does it make a difference that I use the AsyncDatastoreService? Maybe it can compensate the higher latency during the table split?

    Nikolaus Pohle

    April 4, 2011 at 9:10 am

  15. It’ll make things easier for you because it won’t cause your web facing requests to slow down, but there is a possibility you will lose writes. The standard DatastoreService is a very thin layer over the Async service – it just blocks until the Future returns. If it fails, you’ll throw an exception. If you launch an Async write and don’t wait for a response, there’s a possibility the write will time out, and since you’re not catching exceptions, won’t be retried.

    Ikai Lan

    April 4, 2011 at 9:46 am

  16. Hi Ikai,

    I have a clarification question:

    Say there are a lot of timestamped log events coming from many machines. I could use a composite ‘machine_time’ key to avoid the problem but I also need to query just by ‘time’. If I create an index on ‘time’, the index implementation will hit the same problem, is that right?

    Is there any way to have monotonically increasing keys streaming in, having inserts load balanced among machines, and being able to index them?

    The only solution I can think of would be to store the events in intermediate memcached and batch them once in a while.

    Actually I’d like to use HBase (or MongoDB) but the systems should be similar in this respect.

    Thanks!

    Martin

    May 4, 2011 at 12:36 am

  17. [...] entity contention: sharing counter, entity group hot table: 2011 ikai post [...]

  18. [...] entity contention: sharing counter, entity group hot table: 2011 ikai post [...]

  19. [...] http://ikaisays.com/2011/01/25/app-engine-datastore-tip-monotonically-increasing-values-are-bad/ Categories: Uncategorized LikeBe the first to like this post. Comments (0) Trackbacks (0) Leave a comment Trackback [...]

  20. Does this apply to automatically-allocated ids, which appear to be vaguely monotonic?

    Riley

    January 30, 2012 at 2:38 pm


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