Improvement on Hi-Lo Id generator

Question

Hi all,

I have a hi-lo Id generator which I use in a multi-threaded environment. The generator can be called up to 100k times per second per thread

I have a reasonably good (and safe) implementation which works fine. IdAllocator is the object that fetches the next "batch" of ids. You can assume this is threadsafe. I also set the batchSize pretty high (1 million)

private final IdAllocator idAllocator;
private final String idKey;
private final int batchSize;

private final Object lock = new Object();

private long currentId = 0;
private long nextFetchId = -1;

IdGeneratorImpl( IdAllocator idAllocator, String idKey, int batchSize )
{
    this.idAllocator = idAllocator;
    this.idKey = idKey;
    this.batchSize = batchSize;
}

public long getNextId()
{
    synchronized ( lock )
    {
        if ( currentId < nextFetchId )
        {
            long localCurrent = currentId;
            currentId++;
            return localCurrent;
        }

        currentId = idAllocator.allocateBatch( idKey, batchSize );
        nextFetchId = currentId + batchSize;

        return getNextId();
    }
}

At the moment I mostly, but not always, use this in a uncontended manner. However in the future it will be called by multiple threads.

I have considered instantiating one instance of this per thread, which will probably be the best approach. However as an intellectual/learning experience I wondered is there anyway I can improve on this implementation, specifically to reducing the potential contention in getNextId() when multiple threads are calling it frequently?

Answer 1

If you look at the Hibernate TableHiLoGenerator, it uses a simple synchronized in the generation method, which means that multiple threads will wait so that only one of them executes the method at a time. You have done the same with your lock (which is a bit redundant - the synchronized method does the same). So I'd conclude your implementations is fine.