This is a technical post on how we generate a growing sequence of unique numbers within the Google AppEngine environment.
In one of the service extensions we are developing we need to uniquely identify requests of certain type, with the ability to determine the relative order of the requests. We did not need to serialize the requests, though – multiple simultaneous requests from different clients can be assigned numbers in arbitrary order, but we needed to be sure that consecutive requests from the same client were assigned ordered (growing) IDs. And we needed this construct to be scalable.
After some deliberations we came up with this solution – please let us know if there are any holes. It would also be interesting to know if the algorithm can be improved so that the sequence does not skip numbers when step 2 is invoked.
The main idea: we are combining GAE’s sharding counters technique with atomic counters in Memcache to implement sequences. Our Sequence class has one (overloaded) static method: long Sequence.next(String sSequenceName). The method itself performs three simple steps:
Step 1. Increment both the datastore counter (sharding) and the memcache counter (atomic), if the latter is present. If it is, return its new value. This step is scalable.
Step 2. If the memcache counter is not present, “serially” synchronize it with the datastore counter. This step can be viewed as an analog of Step 3. Repeat step 1. Our resulting sequence is "growing" and unique because: We use Objectify to access GAE Datastore. Full source code.lock(Sequence); synchronize counters; unlock(Sequence);
Sequence.next(...) implementation:
// step 1: try to get it from memcache
ShardedCounter dbCounter = ShardedCounter.get(
sSequenceName, nShards );
dbCounter.increment(1);
MemcacheService cacheCounter =
MemcacheServiceFactory.getMemcacheService();
if( cacheCounter == null ) throw new RuntimeException(
"The memcache service is unavailable.");
Long res = cacheCounter.increment(sSequenceName, 1);
if( res != null ) return res;
// step 2: set memcache in a transactional way
util.debug("Sequence [" + sSequenceName +
"] not available in MemCache. Doing DB counter sync.");
Objectify ofy = ObjectifyService.beginTransaction();
try {
// need to get our counter with a transaction-ing ofy
dbCounter = ShardedCounter.get( ofy, sSequenceName );
long nCount = dbCounter.getCount();
dbCounter.incrementSerial(1);
cacheCounter.put( sSequenceName, nCount, null,
SetPolicy.ADD_ONLY_IF_NOT_PRESENT );
ofy.getTxn().commit();
} catch( Exception e ){
if( ofy.getTxn().isActive() ) ofy.getTxn().rollback();
// we continue from here, because the transaction
// could have been
// aborted due to contention, and cacheCounter is
// set by a parallel request
}
// step 3: let's try once more
dbCounter = ShardedCounter.get( sSequenceName );
dbCounter.increment(1);
res = cacheCounter.increment(sSequenceName, 1);
if( res != null ) return res;
throw new RuntimeException(
"The memcache service is not working.");