Java volatile and/or synchronized

Question

I have a static method that is supposed to generate a unique ID based on the current timestamp as shown in the codes below. To ensure that the newly generated ID is not the same as the previously generated ID (due to very fast computer such that the millisecond does not change), I put in a loop to compare the newly generated ID against the previously generated one. If they are the same, it will generate another ID.

public class Util {

    protected static String uniqueID;

    public static String generateUniqueID() {
        SimpleDateFormat timstampFormat = new SimpleDateFormat("yyyyMMddHHmmssSSS");
        do {
            String timestamp = timstampFormat.format(new Date());
            if (!timestamp.equals(uniqueID)) {
                uniqueID = timestamp;
                return uniqueID;
            }
        } while (true);
    }

}

I want the above codes to work when the method is called by multiple threads.

If I merely put the volatile keyword to the uniqueID variable, would that be good enough? Do I still need to have a synchronized block?

How about having a synchronized block but without the volatile keyword?

Thanks in advance.

ADDED:

If I changed to below codes, would the volatile keyword still required?

public class Util {

    private static volatile String uniqueID;

    public static synchronized String generateUniqueID() {
        uniqueID = UUID.randomUUID().toString();
        return uniqueID;
    }

}

Answer 1

There are multiple issues with this code.

Never use a timestamp as UID, unless you're absolutely positive, there won't be ever generated multiple UIDs within a time that is smaller than the lowest resolution of the timestamp you're using. I'd recommend switching to a completely different approach. Either append a counter to the timestamp, if you absolutely want to keep the timestamp-format in use or simply use a counter. Another alternative would be to use System.nanoTime() in addition to the normal systemtime, though that approach might provide quite a few pitfalls.

Your while-loop will loop for up to an entire millisecond, if you try to generate two UIDs within the same millisecond. There's no fast computer needed to make this a total waste of CPU-time. The loop will at least run several thousand times without proper result.

Marking a variable volatile won't do. You have to mark the entire block that is run within the method synchronized to prevent multiple threads from running it at the same time. But consider a case, where you want to generate 1000 UIDs within a single ms. What should be done within no time now suddenly takes a full second. You're creating an enormous bottleneck.

My recommendation:
Delete that method immediately. There's not much that could fix this code to the point where it would actually be acceptable in terms of performance and correctness. Read this tutorial about concurrency. Get a new approach for generating UIDs and start over from scratch.

Alternatively:
Why even write code for something that already exists? Use the UID-class provided by Oracle. Another good approach would be to use UUID, which is part of the utility package and quite likely more general than UID. Depends on your demands on the generated UID.

Answer 2

You have a problem that you busy wait for each milli-second and if multiple threads are waiting, they will all wait, possibly endlessly. This will happen regardless of how you provide thread safety. A better approach is to use a counter which is always >= to the time or a counter which is many times the current time.

You can do

private static final AtomicLong time = new AtomicLong(0);
public static long uniqueTimedId() {
    while(true) {
         long now = System.currentTimeMillis();
         long value = time.get();
         long next = now > value ? now : value + 1;
         if (time.compareAndSwap(value, next))
            return next;
    }
}

This will give you an id for each milli-second, without waiting. When you have multiple ids in the same milli-second, some will be in the future. You can turn this into a String of your format if you want. This still has a problem that you can't have more than 1 per milli-second without drifting from the current time.

private static final AtomicLong time = new AtomicLong(0);
public static long uniqueTimedId() {
    while(true) {
         long now = System.currentTimeMillis() * 1000;
         long value = time.get();
         long next = now > value ? now : value + 1;
         if (time.compareAndSwap(value, next))
            return next;
    }
}

This gives you a unique id which at 1000x the current time. This means you can have 1000 ids per milli-second without drift, and when you convert to a String you need to divide by 1000 to get the time in millis and attach x % 1000 as three digits on the end.

A simpler compromise might be to multiply by 10. This gives you 10 ids per millisecond.

If an instance variable is modified/accessed through synchronized blocks, does that mean the latest modification can be seen by all threads.

Synchronized blocks use read/write memory barriers implemented by the CPU to ensure this happens.

Note: if you use synchronized you don't need to use volatile. In fact using both is could be slower.

If I changed to below codes, would the volatile keyword still required?

synchronized is needed as you are using a variable which is shared. The volatile is redundant and doesn't help.

private static String uniqueID;

public static synchronized String generateUniqueID() {
    uniqueID = UUID.randomUUID().toString();
    // without synchronized, one thread could read what another thread wrote
    return uniqueID;
}

If you use a local variable you wouldn't need synchronzied or volatile as nothing is shared.

// nothing is shared, so no thread safety issues.
public static String generateUniqueID() {
    return UUID.randomUUID().toString();
}

Answer 3

Like others, I would heavily recommend getting rid of busy-loop, timestamp as identifier as well as synchronized-volatile thinking. Volatile will not work, synchronized would work but would be horribly inefficient.

What I would recommend however, is to

• use compareAndSet of AtomicReference for your checking, as it is able to use actual atomic operations as supported by your CPU
• use an identifier that is not bound on time, so you can avoid the bottleneck of waiting for time changes
• if you insist on using timestamp as your identifier, at least sleep while you wait!

Answer 4

Your field uniqueID must be volatile in order to make sure that all threads will see the latest modification and you should rely on UUID (stands for Universally unique identifier) to generate unique ids (that will even be unique in a cluster as it relies on the date time but also on the MAC address), your code will then be as next:

public static String generateUniqueID() {
    return UUID.randomUUID().toString();
}

public static UUID randomUUID()

Static factory to retrieve a type 4 (pseudo randomly generated) UUID. The UUID is generated using a cryptographically strong pseudo random number generator.