Generating Time Based UUIDs

1. Overview

In this article, we’ll learn about UUIDs and time-based UUIDs.

We’ll see the advantages and disadvantages of time-based UUIDs and when to choose them.

We’ll also explore and compare some libraries that will help us implement these different algorithms for producing UUIDs.

2. UUIDs and Time-Based UUIDs

UUID stands for Universally Unique Identifier. It’s a 128-bit identifier expected to be unique every time we generate it.

We use them to identify something uniquely, even if that thing has no inherent identifier. We can use them in various contexts, such as computer systems, databases, and distributed systems, where we require unique identification of objects.

The likelihood of two UUIDs being the same is so tiny that it is considered statistically impossible, making them a reliable way to identify objects in distributed systems.

A time-based UUID, also known as the version 1 UUID, is generated using the current time and a unique identifier specific to the computer or network that produces the UUID. The timestamp ensures the UUID is unique, even if multiple UUIDs are generated simultaneously.

We’ll find two new versions of the standard (v6 and v7) that are time-related in the libraries implemented below.

Version 1 presents several advantages – the time sorted id is fitter to be a primary key in a table, and containing the creation timestamp can help with analysis and debugging. It also has some disadvantages – the chance of collision is slightly higher when generating multiple IDs from the same host. We’ll see if this is an issue later on.

Also, including the host address may present some security flaws, which is why version 6 of the standard attempted to improve security.

3. Benchmark

To make our comparison more straightforward, let’s write a benchmark program to compare the chance of collision and the generation time of the UUIDs. We start by initializing all the necessary variables:

int threadCount = 128;
int iterationCount = 100_000; 
Map<UUID, Long> uuidMap = new ConcurrentHashMap<>();
AtomicLong collisionCount = new AtomicLong();
long startNanos = System.nanoTime();
CountDownLatch endLatch = new CountDownLatch(threadCount);

We’ll run the benchmark on a number of 128 threads with 100.000 iterations each. Also, we’ll use a ConcurentHashMap to store all UUID generated. Besides that, we’ll use a counter for the collisions. To check the speed performance, we store the current timestamp at the start of execution to compare it with the timestamp at the final. And, at the final, we declare a latch to wait for all threads to finish.

After initializing all the variables necessary for our test, we’ll loop and start every thread:

for (long i = 0; i < threadCount; i++) {
    long threadId = i;
    new Thread(() -> {
        for (long j = 0; j < iterationCount; j++) {
            UUID uuid = UUID.randomUUID();
            Long existingUUID = uuidMap.put(uuid, (threadId * iterationCount) + j);
            if (existingUUID != null) {
                collisionCount.incrementAndGet();
            }
        }
        endLatch.countDown();
    }).start();
}

For every line of execution, we’ll integrate again and start generating UUIDs using java.util.UUID class. We’ll insert all the ids with their corresponding count in the map. The UUID will be the key of the map.

So, if we try to insert an existing UUID in the map, the put() method will return us the already existing key. When we get a duplicate UUID, we’ll increment the collision count. At the end of the iteration, we’ll decrement the countdown.

endLatch.await();
System.out.println(threadCount * iterationCount + " UUIDs generated, " + collisionCount + " collisions in "
        + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startNanos) + "ms");

In the end, we’ll use the await() method of the CountDownLatch class to wait until all threads are finished. We’ll print the result of our benchmark consisting of the number of UUIDs generated, the number of collisions, and the execution time.

Now, let’s run the benchmark against the JDK’s built-in UUID generator:

12800000 UUIDs generated, 0 collisions in 4622ms

We can see that all ids were generated without collision. In the following sections, we’ll compare this with the other generators.

4. UUID Creator

4.1. Dependency

The Java UUID Creator library is valuable and flexible for generating UUIDs. It provides various options for generating UUIDs, and its simple API makes it easy to use in a wide range of applications. We can add the library to our project:

<dependency>
    <groupId>com.github.f4b6a3</groupId>
    <artifactId>uuid-creator</artifactId>
    <version>5.2.0</version>
</dependency>

4.2. Usage

This library provides us with three ways to generate time-based UUIDs:

• UuidCreator.getTimeBased() – the time-based version with gregorian epoch specified in RFC-4122
• UuidCreator.getTimeOrdered() – the time-ordered version with gregorian epoch proposed as a new UUID format
• UuidCreator.getTimeOrderedEpoch() – the time-ordered version with Unix epoch proposed as a new UUID format

We can use them directly in our code after adding the dependency:

System.out.println("UUID Version 1: " + UuidCreator.getTimeBased());
System.out.println("UUID Version 6: " + UuidCreator.getTimeOrdered());
System.out.println("UUID Version 7: " + UuidCreator.getTimeOrderedEpoch());

And we can see in the output that all three have the same classic UUID format:

UUID Version 1: 0da151ed-c82d-11ed-a2f6-6748247d7506
UUID Version 6: 1edc82d0-da0e-654b-9a98-79d770c05a84
UUID Version 7: 01870603-f211-7b9a-a7ea-4a98f5320ff8

This article will focus on the getTimeBased() method that uses the traditional version 1 UUID. It has three parts: timestamp, clock sequence, and node identifier.

Time-based UUID structure

 00000000-0000-v000-m000-000000000000
|1-----------------|2---|3-----------|

1: timestamp
2: clock-sequence
3: node identifier

4.3. Benchmark

In this section, we’ll run the benchmark from the previous part, but we’ll generate de UUIDs with the UuidCreator.getTimeBased() method. After that, we get the result:

12800000 UUIDs generated, 0 collisions in 2595ms

We can see that this algorithm also managed to generate all the UUIDs without duplicates. Besides this, it even managed to get a better time than the JDK one. This is just a basic benchmark, though there are more detailed benchmarks available.

5. Java UUID Generator (JUG)

5.1. Dependency

Java UUID Generator (JUG) is a set of Java classes for working with UUIDs. It includes generating UUIDs using standard methods, efficiently outputting, sorting, etc. It generates UUIDs according to the UUID specification (RFC-4122).

To use the library, we should add the Maven dependency:

<dependency>
    <groupId>com.fasterxml.uuid</groupId>
    <artifactId>java-uuid-generator</artifactId>
    <version>4.1.0</version>
</dependency>

5.2. Usage

This library also provides three methods to create time-based UUIDs (the classic version 1 and the new versions 6 and 7). We can generate them by selecting a kind of generator and then calling its generate() method:

System.out.println("UUID Version 1: " + Generators.timeBasedGenerator().generate());
System.out.println("UUID Version 6: " + Generators.timeBasedReorderedGenerator().generate());
System.out.println("UUID Version 7: " + Generators.timeBasedEpochGenerator().generate());

Then we can check the UUIDs in the console:

UUID Version 1: e6e3422c-c82d-11ed-8761-3ff799965458
UUID Version 6: 1edc82de-6e34-622d-8761-dffbc0ff00e8
UUID Version 7: 01870609-81e5-793b-9e4f-011ee370187b

5.3. Benchmark

Like the previous section, we’ll focus on the first variant of UUID offered by this library. We can also test the chance of a collision by replacing the generation of the UUID from the previous example with the following:

UUID uuid = Generators.timeBasedGenerator().generate();

And after running the code, we can see the results:

12800000 UUIDs generated, 0 collisions in 15795ms

From this, we can see that we also got no duplicates of UUID, like in the previous example. But also, we see a difference in the execution time. Even if the difference seems large, both libraries generated many IDs quickly.

The documentation of this library tells us that generation speed is unlikely to be a bottleneck, and choosing based on the stability of packages and API is better.

6. Conclusion

In this tutorial, we saw the time-based UUIDs’ structure, advantages, and disadvantages. We implemented them in our code using two of the most popular libraries for UUIDs and compared them afterward.

We saw that choosing a type of UUID or library might depend on our needs.