Generate ID fast and with high probability of uniqueness

Question

I want to generate ID to event that occur in my application.

The event frequency is up to the user load, so it might occur hundreds-thousand of time per second.

I can't afford using UUID.randomUUID() because it might be problematic in performance matters - Take a look at this.

I thought of generating ID as follows:

System.currentTimeMillis() + ";" + Long.toString(_random.nextLong())

When _random is a static java.util.Random my class is holding.

My questions are:

1. Do you think the distribution of this combination will be good enough to my needs?
2. Does Java's Random implementation related to the current time and therefore the fact I'm combining the two is dangerous?

Answer 1

I would use the following.

final AtomicLong counter = new AtomicLong(System.currentTimeMillis() * 1000);

and

long l = counter.getAndIncrement(); // takes less than 10 nano-seconds most of the time.

This will be unique within your system and across restarts provided you average less than one million per second.

Even at this rate, the number will not overflow for some time.

class Main {
    public static void main(String[] args) {
        System.out.println(new java.util.Date(Long.MAX_VALUE/1000));
    }
}

prints

Sun Jan 10 04:00:54 GMT 294247

EDIT: In the last 8 years I have switched to using nanosecond wall clock and memory-mapped files to ensure uniqueness across processes on the same machine. The code is available here. https://github.com/OpenHFT/Chronicle-Bytes/blob/ea/src/main/java/net/openhft/chronicle/bytes/MappedUniqueTimeProvider.java

Answer 2

To prevent possible collisions I would suggest you to somehow integrate users' unique ids into the generated id. You can do this either adding user id to directly to the generated id

System.currentTimeMillis() + ";" + Long.toString(_random.nextLong()) + userId

or you can use separate _random for each user that uses the user's id as its seed.

Answer 3

UUID uuid = UUID.randomUUID(); is less than 8 times slower, after warming up, 0.015 ms versus 0.0021 ms on my PC. That would be a positive argument for UUID - for me.

1. One could shift the random long a bit to the right, so time is more normative, sequencing.
2. No, there is a pseudo random distribution involved.