Double checked locking

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Double checked locking

Mike Quilleash
Hi there,
 
I have a small piece of code that generates sequential incrementing id's.  The only requirement is that every call to this function return a unique id to every other call in the past.  The code is used on multiple machines so the central "next id" is help in a database table and each JVM occasionally makes a call to fetch a block of ids from the database table which are then consumed by the JVM at which point another block will be fetched and so on.
 
Here's the current code....
 
    private int currentId = -1;
    private int allocatedId = -1;
    public synchronized Integer getNextId()
    {
        if ( allocatedId == -1 || allocatedId == currentId )
        {
            // get the low id allocated
            int lowId = DatabaseIdGenerator.generateId(objectKey, blockSize).intValue();

            allocatedId = lowId + blockSize;

            // set the current id to the low id
            currentId = lowId;
        }

        // create the return value
        Integer ret = new Integer( currentId );

        // increment the current id to the next available id
        currentId++;

        return ret;
    }
 
I've been doing some performance profiling and found a bottleneck in this function, on a multiple CPU there is some scalability loss which is partly caused by blocking on this method's monitor.  So I've changed it to be like this....
 
 
 
    private AtomicInteger nextId = new AtomicInteger( -1 );
 
    public int getNextId() throws HibernateException
    {
        if ( nextId.get() == -1 || allocatedId == nextId.get() )
        {
            synchronized( nextId )
            {
                if ( nextId.get() == -1 || allocatedId == nextId.get() )
                {
                    // get the low id allocated
                    int lowId = HibernateSession.generateId(objectKey, blockSize).intValue();
 
                    allocatedId = lowId + blockSize;
 
                    // set the current id to the low id
                    nextId.set( lowId );
                }
            }
        }
 
        // create the return value
        int ret = nextId.getAndIncrement();
 
        return ret;
    }
 
 
So in theory the synchronization is only required when the local Atomic runs out of ids when it goes to the db to fetch more.  I realize this is using double checked locking which is a bad thing but I wondered if it would work in this case, being slightly different from the lazy intialization that this is usually used for.
 
Or alternatively any better way of doing this.
 
Appreciate any help or comments.
 
Cheers.
 
Mike.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Double checked locking

Bart Jacobs-2
Hi Mike,

This code is obviously wrong. You have a TOCTOU (time of check to time
of use) problem. In particular, you're assuming at the getAndIncrement
call that nextId is less than allocatedId, and you justify that
assumption by the test you do at the top of the method. However, other
threads may intervene in the meantime.

Another source of potential trouble, I think, is that allocatedId might
change under your feet. Therefore, it's probably better to introduce an
IdBlock class.

Here's my proposed tentative implementation. Note: I advise you to
solicit review by others as well before settling on any implementation.
You might even want to go so far as to construct a correctness argument.
(But then you need to learn the rules of the game, which are hard at
this level.)

class IdBlock {
    final int limit;
    final AtomicInteger nextId;

    IdBlock(int start, int limit) {
        this.limit = limit;
        this.nextId = new AtomicInteger(start);
    }
}

final Object mutex = new Object();
IdBlock currentBlock;  // Need not be volatile because has only final
fields?

public int getNextId() throws HibernateException
{
    IdBlock block = currentBlock;
    if (block != null)
    {
        int id = block.nextId.getAndIncrement();
        if (id < block.limit)
            return id;
    }
    synchronized (mutex) {
        // We may have a new block by now, so try again.
        if (currentBlock != null && currentBlock != block)
        {
            int id = currentBlock.nextId.getAndIncrement();
            if (id < currentBlock.limit)
                return id;
        }
        // Allocate a new block
        int lowId = HibernateSession.generateId(objectKey,
blockSize).intValue();
        currentBlock = new IdBlock(lowId + 1, lowId + blockSize);
        return lowId;
    }
}

Performance testing will have to show whether this implementation is
faster than your original synchronized implementation, which has the
great benefit of being simple. So unless a "clever" implementation turns
out to have significant performance benefits, I advise that you stick
with the simple synchronized solution.

Good luck,-
Bart

Mike Quilleash schreef:

>     private AtomicInteger nextId = new AtomicInteger( -1 );
>  
>     public int getNextId() throws HibernateException
>     {
>         if ( nextId.get() == -1 || allocatedId == nextId.get() )
>         {
>             synchronized( nextId )
>             {
>                 if ( nextId.get() == -1 || allocatedId == nextId.get() )
>                 {
>                     // get the low id allocated
>                     int lowId = HibernateSession.generateId(objectKey,
> blockSize).intValue();
>  
>                     allocatedId = lowId + blockSize;
>  
>                     // set the current id to the low id
>                     nextId.set( lowId );
>                 }
>             }
>         }
>  
>         // create the return value
>         int ret = nextId.getAndIncrement();
>  
>         return ret;
>     }
>
>  
>  
> So in theory the synchronization is only required when the local Atomic
> runs out of ids when it goes to the db to fetch more.  I realize this is
> using double checked locking which is a bad thing but I wondered if it
> would work in this case, being slightly different from the lazy
> intialization that this is usually used for.
>  
> Or alternatively any better way of doing this.
>  
>  
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Double checked locking

Jeremy Manson
In reply to this post by Mike Quilleash
Mike,

 From a double-checked locking point of view, it is generally okay to
use an AtomicInteger as the guard variable, because it provides the same
guarantees as a volatile variable.

 From a concurrency point of view, this code allows one thread to call
nextId.getAndIncrement() between the if statement and the
getAndIncrement() of another.  You can end up with:

Initially, nextId = 1 and allocatedId = 2

Thread 1:

(1) if (nextId.get() == -1 || // returns false
(2)    allocatedId == nextId.get())  // returns false
       ...
(6) int ret = nextId.getAndIncrement(); // returns "3"

Thread 2:

(3) if (nextId.get() == -1 || // returns false
(4)    allocatedId == nextId.get())  // returns false
       ...
(5) int ret = nextId.getAndIncrement(); // returns "2"

If these are really ints, and performance is really, truly an issue, you
can do something pretty clever with compareAndSet and AtomicLongs
instead (subject to someone other than myself saying this is correct):

AtomicLong currAndMax = new AtomicLong();

public int getNextId() throws HibernateException {
   long current;
   long newCurrent, newMax;
   do {
     current = currAndMax.get();
     if ((current & 0xFFFFFFFFL) == (current >> 32)) {
       newCurrent = (long) HibernateSession.generateId(objectKey,
blockSize).intValue();
       newMax = newCurrent + blockSize;
     } else {
       newCurrent = (current &  0xFFFFFFFFL) + 1L;
       newMax = current >> 32;
     }
   } while (!currAndMax.compareAndSet(current,
                                     (newMax << 32) |  newCurrent));
   return (int) newCurrent;
}

This stores both the maximum id and the current id in a single variable,
where the maximum id is the high-order 32 bits, and the current id is
the low order 32 bits.  Both variables are simultaneously, atomically
updated by the compareAndSet.  If someone performed an update to the
variable between when the get() occurs and when the compareAndSet()
occurs, then your updates get discarded and you try the method again.

This does open you up to potentially throwing away calls to generateId,
so if you can't do that, then this won't work.  Also, it is very
confusing, so maintainability might be an issue.

                                        Jeremy

Mike Quilleash wrote:

> Hi there,
>  
> I have a small piece of code that generates sequential incrementing
> id's.  The only requirement is that every call to this function return a
> unique id to every other call in the past.  The code is used on multiple
> machines so the central "next id" is help in a database table and each
> JVM occasionally makes a call to fetch a block of ids from the database
> table which are then consumed by the JVM at which point another block
> will be fetched and so on.
>  
> Here's the current code....
>  
>     private int currentId = -1;
>     private int allocatedId = -1;
>     public synchronized Integer getNextId()
>     {
>         if ( allocatedId == -1 || allocatedId == currentId )
>         {
>             // get the low id allocated
>             int lowId = DatabaseIdGenerator.generateId(objectKey,
> blockSize).intValue();
>
>             allocatedId = lowId + blockSize;
>
>             // set the current id to the low id
>             currentId = lowId;
>         }
>
>         // create the return value
>         Integer ret = new Integer( currentId );
>
>         // increment the current id to the next available id
>         currentId++;
>
>         return ret;
>     }
>  
> I've been doing some performance profiling and found a bottleneck in
> this function, on a multiple CPU there is some scalability loss which is
> partly caused by blocking on this method's monitor.  So I've changed it
> to be like this....
>  
>  
>  
>     private AtomicInteger nextId = new AtomicInteger( -1 );
>  
>     public int getNextId() throws HibernateException
>     {
>         if ( nextId.get() == -1 || allocatedId == nextId.get() )
>         {
>             synchronized( nextId )
>             {
>                 if ( nextId.get() == -1 || allocatedId == nextId.get() )
>                 {
>                     // get the low id allocated
>                     int lowId = HibernateSession.generateId(objectKey,
> blockSize).intValue();
>  
>                     allocatedId = lowId + blockSize;
>  
>                     // set the current id to the low id
>                     nextId.set( lowId );
>                 }
>             }
>         }
>  
>         // create the return value
>         int ret = nextId.getAndIncrement();
>  
>         return ret;
>     }
>  
>  
> So in theory the synchronization is only required when the local Atomic
> runs out of ids when it goes to the db to fetch more.  I realize this is
> using double checked locking which is a bad thing but I wondered if it
> would work in this case, being slightly different from the lazy
> intialization that this is usually used for.
>  
> Or alternatively any better way of doing this.
>  
> Appreciate any help or comments.
>  
> Cheers.
>  
> Mike.
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Double checked locking

Mike Quilleash
In reply to this post by Mike Quilleash
Thanks for your replies.

Unfortunately I need to use the same system for longs as well as ints so
I couldn't use this solution for both (although it is very cunning!).  

I'm going to try out Bart's suggestion first as it looks good and
eliminates the synchronization except when loading a new id block (the
id blocks tend to be sized 10k - 1m) so this should be fine.  The
function is heavily travelled esp on a multi cpu box (maybe tens of
thousands of hits per second) so eliminating this may help.

If anyone has any comments on Bart's solution I'd appreciate it.  I'll
let you know if it helps my performance.

Thanks again.

-----Original Message-----
From: Jeremy Manson [mailto:[hidden email]]
Sent: 10 April 2006 16:16
To: Mike Quilleash
Cc: [hidden email]
Subject: Re: [concurrency-interest] Double checked locking

Mike,

 From a double-checked locking point of view, it is generally okay to
use an AtomicInteger as the guard variable, because it provides the same
guarantees as a volatile variable.

 From a concurrency point of view, this code allows one thread to call
nextId.getAndIncrement() between the if statement and the
getAndIncrement() of another.  You can end up with:

Initially, nextId = 1 and allocatedId = 2

Thread 1:

(1) if (nextId.get() == -1 || // returns false
(2)    allocatedId == nextId.get())  // returns false
       ...
(6) int ret = nextId.getAndIncrement(); // returns "3"

Thread 2:

(3) if (nextId.get() == -1 || // returns false
(4)    allocatedId == nextId.get())  // returns false
       ...
(5) int ret = nextId.getAndIncrement(); // returns "2"

If these are really ints, and performance is really, truly an issue, you
can do something pretty clever with compareAndSet and AtomicLongs
instead (subject to someone other than myself saying this is correct):

AtomicLong currAndMax = new AtomicLong();

public int getNextId() throws HibernateException {
   long current;
   long newCurrent, newMax;
   do {
     current = currAndMax.get();
     if ((current & 0xFFFFFFFFL) == (current >> 32)) {
       newCurrent = (long) HibernateSession.generateId(objectKey,
blockSize).intValue();
       newMax = newCurrent + blockSize;
     } else {
       newCurrent = (current &  0xFFFFFFFFL) + 1L;
       newMax = current >> 32;
     }
   } while (!currAndMax.compareAndSet(current,
                                     (newMax << 32) |  newCurrent));
   return (int) newCurrent;
}

This stores both the maximum id and the current id in a single variable,
where the maximum id is the high-order 32 bits, and the current id is
the low order 32 bits.  Both variables are simultaneously, atomically
updated by the compareAndSet.  If someone performed an update to the
variable between when the get() occurs and when the compareAndSet()
occurs, then your updates get discarded and you try the method again.

This does open you up to potentially throwing away calls to generateId,
so if you can't do that, then this won't work.  Also, it is very
confusing, so maintainability might be an issue.

                                        Jeremy

Mike Quilleash wrote:
> Hi there,
>  
> I have a small piece of code that generates sequential incrementing
> id's.  The only requirement is that every call to this function return

> a unique id to every other call in the past.  The code is used on
> multiple machines so the central "next id" is help in a database table

> and each JVM occasionally makes a call to fetch a block of ids from
> the database table which are then consumed by the JVM at which point
> another block will be fetched and so on.
>  
> Here's the current code....
>  
>     private int currentId = -1;
>     private int allocatedId = -1;
>     public synchronized Integer getNextId()
>     {
>         if ( allocatedId == -1 || allocatedId == currentId )
>         {
>             // get the low id allocated
>             int lowId = DatabaseIdGenerator.generateId(objectKey,
> blockSize).intValue();
>
>             allocatedId = lowId + blockSize;
>
>             // set the current id to the low id
>             currentId = lowId;
>         }
>
>         // create the return value
>         Integer ret = new Integer( currentId );
>
>         // increment the current id to the next available id
>         currentId++;
>
>         return ret;
>     }
>  
> I've been doing some performance profiling and found a bottleneck in
> this function, on a multiple CPU there is some scalability loss which
> is partly caused by blocking on this method's monitor.  So I've
> changed it to be like this....
>  
>  
>  
>     private AtomicInteger nextId = new AtomicInteger( -1 );
>  
>     public int getNextId() throws HibernateException
>     {
>         if ( nextId.get() == -1 || allocatedId == nextId.get() )
>         {
>             synchronized( nextId )
>             {
>                 if ( nextId.get() == -1 || allocatedId == nextId.get()
)

>                 {
>                     // get the low id allocated
>                     int lowId = HibernateSession.generateId(objectKey,
> blockSize).intValue();
>  
>                     allocatedId = lowId + blockSize;
>  
>                     // set the current id to the low id
>                     nextId.set( lowId );
>                 }
>             }
>         }
>  
>         // create the return value
>         int ret = nextId.getAndIncrement();
>  
>         return ret;
>     }
>  
>  
> So in theory the synchronization is only required when the local
> Atomic runs out of ids when it goes to the db to fetch more.  I
> realize this is using double checked locking which is a bad thing but
> I wondered if it would work in this case, being slightly different
> from the lazy intialization that this is usually used for.
>  
> Or alternatively any better way of doing this.
>  
> Appreciate any help or comments.
>  
> Cheers.
>  
> Mike.
>
>
> ----------------------------------------------------------------------
> --
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest