Efficient Global Counters, revisited

Although it is almost a year old, the post on efficient global counters from last June is still the third most frequently visited page on my blog. That makes me kindof feel bad: not only am I mostly rehashing a tech talk by Brett Slatkin without adding much to it, the technology described in the post is not even up to "code" any more. Sure the code still works, but since the introduction of memcache, there are even more efficient ways to achive the same goal. The following post is an attempt to outline those ways and to provide a more efficient implementation for Java App Engine. It is based on some discussions I had with Brett on this subject, whom I'd like to give a big thanks! You can also take a look at the Javdoc or get the source code from the open source project. If you need a python version: this open source implementation is actually very close to what I am doing in this blog post :-).

Reliable counters have many different uses, from statistics for the hits on a web page to creating ids for pagination (key ids and timestamps are good approximations in App Engine, but they are not 100% guaranteed to yield the right results). The problem is that building a reliable counter is hard -- especially if it is supposed to be fast! My previous implementation of counters was suggesting to keep memcache to store a snapshot of the counter (for a minute) and then reload from the database as needed. Turns out that this is not ideal: not only is the result of the counter up to 60 seconds old, it also requires me to hit the database once a minute at least to re-compute the value.

One of the many cool things that memache has is a transaction API. Amongst other things, I can

• Get a numeric value out of memcache


• Write a value to memcache, but only if it does not already exist. Let's call this optional set for now.


• atomically fetch, increment, and store a given integer (or long) value that is stored in memcache. It's almost like running in a transaction :-)

So, if memcache can do transactions for me, why not use it for computing the new value of a counter? The idea is as following:

• Instead of sharding the counter on the store and adding up the results, we only shard the current counter value. Assumed that the counter can never decrease, all we have to do to load it from the store is run over all shards and compute the maximum persisted value.


• Whenever we need to access the counter, we check if the counter is populated in memcache. If that is not the case, we do the maximum computation mentioned before and update memcache. It is important to use the optional set mechanism for that, since a second parallel App Engine request could have done the same process and is already overwriting the cached value.


• Whenever we increase the counter, we store the new maximum in a random shard. If we do not need 100% reliability (in other words, it is ok to loose a count every now and then), we can also write to the store less often.

So, how do we implement this in Java? Let's take a look at a class with the following fields and constructor:

public class Counter {

  private static final String PARTITION = "common:counter";
  private final Random random;
  private final Persistence<Long> persistence;
  private final MemcacheService memcache;
  private final double chanceToWrite;
  private final String prefix;
  private final String memcacheKey;
  private final int numShards;

  /**
   * Constructor
   * 
   * @param random
   *          a random number generator
   * @param persistence
   *          a persistence that can be used to write to the
   *          datastore
   * @param memcache
   *          a memcache service for quick access to shared
   *          transactional numbers
   * @param chanceToWrite
   *          a value between 0.0 and 1.0 (inclusive). Each
   *          time the counter gets increased, a random
   *          throw of the dice decides whether to write to
   *          the store. A chanceToWrite of 1.0 means that
   *          every change in the counter will be persisted;
   *          a chanceToWrite of 0.0 means that no change
   *          will be persisted
   * @param key
   *          a key that is used to persist the counter shards
   *          in the datastore and memcache. must not
   *          contain any slashes
   * @param numShards
   *          the number of shards that should be used to
   *          store the value. The more shards the less the
   *          chance of collision on writes, but the longer
   *          it will take to load shards from the store if
   *          memcache has been evicted
   */
  public Counter(Random random,
      Persistence<byte[]> persistence,
      MemcacheService memcache, double chanceToWrite,
      String key, int numShards) {
    super();
    Preconditions.checkNotNull(random);
    Preconditions.checkNotNull(memcache);
    Preconditions.checkNotNull(memcache);
    Preconditions.checkArgument(chanceToWrite >= 0.0
        && chanceToWrite <= 1.0,
        "chanceToWrite must be bewteen 0.0 and 1.0");
    Preconditions.checkArgument(key.indexOf('/') < 0,
        "key must not contain any slashes: " + key);
    Preconditions
        .checkArgument(numShards > 0 && numShards < 1000,
            "there must be at least one shard, but no more than 999");
    this.random = random;
    this.persistence = new LongPersistence(persistence);
    this.memcache = memcache;
    this.chanceToWrite = chanceToWrite;
    this.prefix = '/' + key + '/';
    this.memcacheKey = "aef/c/" + key;
    this.numShards = numShards;
  }

We inject all objects the Counter depends on in the constructor to make it easier to replace any of them with mocks for unit tests (if you're interested in the how, look at the test class). Access to the datastore is wrapped in a simple Persistence interface (see my previous post for details).

Let's take a look at how the memcache is populated:

  /**
   * Makes sure that the memcache is populated. If the
   * memcache is prepopulated, or this process was
   * successful in updating memcache from the datastore,
   * return the known value. Otherwise, return null.
   */
  private Long populateMemcache() {
    Long result = (Long) memcache.get(memcacheKey);
    if (result == null) {
      long max = 0;
      for (Entry<String, Long> shard : Utilities
          .scanByPrefix(persistence, prefix, 1000)) {
        max = Math.max(max, shard.getValue());
      }
      boolean changed =
          memcache.put(memcacheKey, max, null,
              SetPolicy.ADD_ONLY_IF_NOT_PRESENT);
      if (changed) {
        result = max;
      }
    }
    return result;
  }

The method checks if there is currently a value in the cache. If that is the case, it will return the current value (no need to do a second lookup later on if we don't have to) If the value is not there, it will load all shards from the store and compute the maximum value. If it can compute and set the value in memcache, it returns that result. Otherwise, it assumes that the data in memcache has already changed and returns null instead.

With this tool method implemented, getting the current value for the counter is easy:

  public long get() {
    Long prepopulated = populateMemcache();
    return (prepopulated != null) ? prepopulated
        : (Long) memcache.get(memcacheKey);
  }

How about setting the value, though? Well, we just peform the steps alrady outlined above:

• Make sure that memcache is initialized (by calling populateMemcache).


• Increment the value in memcache and store the result


• If we decide to write the data to the store, select a random shard and persist the data. Since we are working in a transaction, another server process could have picked the same shard to write an updated value, so be sure to do a maximum-computation before writing the data.

Here's the method in code:

  public long increment(long delta) {
    Preconditions.checkArgument(delta > 0,
        "delta must be a positive value");
    populateMemcache();
    final Long result =
        memcache.increment(memcacheKey, delta);
    if (random.nextDouble() <= chanceToWrite) {
      String shardKey = prefix + random.nextInt(numShards);
      persistence.mutate(shardKey,
          new Function<Long, Long>() {
            @Override
            public Long apply(Long oldValue) {
              if (oldValue == null) {
                return result;
              }
              return Math.max(oldValue, result);
            }
          });
    }
    return result;
  }

As always, take what I am writing here with a huge grain of salt. There is always the possibility that I have not considered all edge cases, or that I simply have a bug in this implementation. In other words, please do not hesitate to post comments to this blog with questions or errors you may find! If you'd like to take a look at the entire source or use the code in a project of your own, you can find it all in this open source project.