How to synchronize System Time access in a class in Java

Question

I am writing a class that when called will call a method to use system time to generate a unique 8 character alphanumeric as a reference ID. But I have the fear that at some point, multiple calls might be made in the same millisecond, resulting in the same reference ID. How can I go about protecting this call to system time from multiple threads that might call this method simultaneously?

Answer 1

System time is unreliable source for Unique Ids. That's it. Don't use it. You need some form of a permanent source (UUID uses secure random which seed is provided by the OS)

The system time may go/jump backwards even a few milliseconds and screw your logic entirely. If you can tolerate 64 bits only you can either use High/Low generator which is a very good compromise or cook your own recipe: like 18bits of days since beginning of 2012 (you have over 700years to go) and then 46bits of randomness coming from SecureRandom - not the best case and technically it may fail but it doesn't require external persistence.

Answer 2

I'd suggest to add the threadID to the reference ID. This will make the reference more unique. However, even within a thread consecutive calls to a time source may deliver identical values. Even calls to the highest resolution source (QueryPerformanceCounter) may result in identical values on certain hardware. A possible solution to this problem is testing the collected time value against its predecessor and add an increment item to the "time-stamp". You may need more than 8 characters when this should be human readable. The most efficient source for a timestamp is the GetSystemTimeAsFileTime API. I wrote some details in this answer.

Answer 3

You can use the UUID class to generate the bits for your ID, then use some bitwise operators and Long.toString to convert it to base-36 (alpha-numeric).

public static String getId() {
    UUID uuid = UUID.randomUUID();
    // This is the time-based long, and is predictable
    long msb = uuid.getMostSignificantBits();
    // This contains the variant bits, and is random
    long lsb = uuid.getLeastSignificantBits();
    long result = msb ^ lsb; // XOR
    String encoded = Long.toString(result, 36);
    // Remove sign if negative
    if (result < 0)
        encoded = encoded.substring(1, encoded.length());
    // Trim extra digits or pad with zeroes
    if (encoded.length() > 8) {
        encoded = encoded.substring(encoded.length() - 8, encoded.length());
    }
    while (encoded.length() < 8) {
        encoded = "0" + encoded;
    }
}

Since your character space is still smaller compared to UUID, this isn't foolproof. Test it with this code:

public static void main(String[] args) {
    Set<String> ids = new HashSet<String>();
    int count = 0;
    for (int i = 0; i < 100000; i++) {
        if (!ids.add(getId())) {
            count++;
        }
    }
    System.out.println(count + " duplicate(s)");
}

For 100,000 IDs, the code performs well pretty consistently and is very fast. I start getting duplicate IDs when I increase another order of magnitude to 1,000,000. I modified the trimming to take the end of the encoded string instead of the beginning, and this greatly improved duplicate ID rates. Now having 1,000,000 IDs isn't producing any duplicates for me.

Your best bet may still be to use a synchronized counter like AtomicInteger or AtomicLong and encode the number from that in base-36 using the code above, especially if you plan on having lots of IDs.

---

Edit: Counter approach, in case you want it:

private final AtomicLong counter;

public IdGenerator(int start) {
    // start could also be initialized from a file or other
    // external source that stores the most recently used ID
    counter = new AtomicLong(start);
}

public String getId() {
    long result = counter.getAndIncrement();
    String encoded = Long.toString(result, 36);
    // Remove sign if negative
    if (result < 0)
        encoded = encoded.substring(1, encoded.length());
    // Trim extra digits or pad with zeroes
    if (encoded.length() > 8) {
        encoded = encoded.substring(0, 8);
    }
    while (encoded.length() < 8) {
        encoded = "0" + encoded;
    }
}

This code is thread-safe and can be accessed concurrently.