Efficient Global Counters

I had the chance to spend some time at the Google I/O last week, and it was amazing -- great knowledge exchange and a couple of really interesting speakers. One of my favorite sessions was a talk by Brett Slatkin called "Building Scalable Web Applications with Google App Engine." He talked about quite a few gotchas to be aware of when trying to get most out of the datastore.

One of his examples shows was a more efficient way of building a global counter: the naive approach I have been guilty of in the past (store the count in an entity and update it in a transaction) turns out to be a performance bottleneck, because this means that all transactions have to wait on a single lock for the entity. Instead, he suggested to split the counter into several shards, thus distributing the locking over more than one entity group. I don't recall the exact implementation from memory, but it went something like this:

from google.appengine.ext import db
import random

SHARDS_PER_COUNTER = 20

class CounterShard(db.Model):
  name = db.StringProperty(required=True)
  count = db.IntegerProperty(default=0)

def GetCount(nameOfCounter):
  result = 0
  for shard in CounterShard.gql('WHERE name=:1', nameOfCounter):
    result += shard.count
  return result

def ChangeCount(nameOfCounter, delta):
  shard_id = '/%s/%s' % (
     nameOfCounter, random.randint(1, SHARDS_PER_COUNTER))
  def update():
   shard = CounterShard.get_by_key_name(shard_id)
   if shard:
     shard.count += delta
   else:
     shard = CounterShard(
         key_name=shard_id, name=nameOfCounter, count=delta)
   shard.put()
  db.run_in_transaction(update)

Pretty nice, and it gets even better: using the newly announced Memcache API, we can keep the counter in memory and only update it once in a while (which is acceptable for many use cases). The following modification keeps the counter in memory for a minute before reloading it:

def GetCount(nameOfCounter):
  memcache_id = '/CounterShard/%s' %  nameOfCounter
  result = memcache.get(memcache_id)
  if not (result == None):
    return result
  result = 0
 for shard in CounterShard.gql('WHERE name=:1', nameOfCounter):
   result += shard.count
  memcache.set(memcache_id, result, 60)
  return result

Brett, thanks for giving this talk. I'm looking forward to trying this out in my applications!