Improvement on Hi-Lo Id generator

Question

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.

Answer 2

I'd bet, you're over-optimizing. A batch size of one million means that you hit the DB on every millionth insert. If you used one thousand instead, you'd see no performance difference and waste much fewer IDs. Sure, with long it doesn't matter much.

Doing the above thing in every thread would mean that you're wasting up to one million IDs per thread. No big deal with long, I know.

It'd also increase the start up cost needlessly and possibly leave a lot of thread-local garbage. Again, no big deal, but what's the advantage? A short code like above takes a few nanoseconds while a DB access takes many orders of magnitude more. So no contention could really slow you down.

However, the proper way to optimize this is probably via AtomicLong. It has a much lower overhead than synchronization. Use getAndIncrement and only enter a synchronized block, when you overrun your nextFetchId. In this block, first recheck if another thread did the work you're gonna do and if not, get the next id from the database.

A much simpler way is using the hibernate HiLoOptimizer or a better variant thereof.