Java Top

Get started with Spring 5 and Spring Boot 2, through the Learn Spring course:

>> CHECK OUT THE COURSE

1. Overview

UUID (Universally Unique Identifier), also known as GUID (Globally Unique Identifier), is a 128-bit value that is unique for all practical purposes. Their uniqueness doesn't depend on a central registration authority or coordination between the parties generating them, unlike most other numbering schemes.

In this tutorial, we'll see two different implementation approaches to generate UUID identifiers in Java.

2. Structure

Let's have a look at an example UUID, followed by the canonical representation of a UUID:

123e4567-e89b-42d3-a456-556642440000
xxxxxxxx-xxxx-Bxxx-Axxx-xxxxxxxxxxxx

The standard representation is composed of 32 hexadecimal (base-16) digits, displayed in five groups separated by hyphens, in the form 8-4-4-4-12, for a total of 36 characters (32 hexadecimal characters and 4 hyphens).

The Nil UUID is a special form of UUID in which all bits are zero.

2.1. Variants

In the standard representation above, A indicates the UUID variant, which determines the layout of the UUID. All other bits in the UUID depend on the setting of the bits in the variant field.

The variant is determined by the three most significant bits of A:

  MSB1    MSB2    MSB3
   0       X       X     reserved (0)
   1       0       X     current variant (2)
   1       1       0     reserved for Microsoft (6)
   1       1       1     reserved for future (7)

The value of A in the mentioned UUID is “a”. The binary equivalent of “a” (=10xx) shows the variant as 2.

2.1. Versions

Looking again at the standard representation, B represents the version. The version field holds a value that describes the type of the given UUID. The version (value of B) in the example UUID above is 4.

There are five different basic types of UUIDs:

  1. Version 1 (Time-Based): based on the current timestamp, measured in units of 100 nanoseconds from October 15, 1582, concatenated with the MAC address of the device where the UUID is created.
  2. Version 2 (DCE – Distributed Computing Environment): uses the current time, along with the MAC address (or node) for a network interface on the local machine. Additionally, a version 2 UUID replaces the low part of the time field with a local identifier such as the user ID or group ID of the local account that created the UUID.
  3. Version 3 (Name-based): The UUIDs are generated using the hash of namespace and name. The namespace identifiers are UUIDs like Domain Name System (DNS), Object Identifiers (OIDs), and URLs.
  4. Version 4 (Randomly generated): In this version, UUID identifiers are randomly generated and do not contain any information about the time they are created or the machine that generated them.
  5. Version 5 (Name-based using SHA-1): Generated using the same approach as version 3, with the difference of the hashing algorithm. This version uses SHA-1 (160 bits) hashing of a namespace identifier and name.

3. The UUID Class

Java has a built-in implementation to manage UUID identifiers, whether we want to randomly generate UUIDs or create them using a constructor.

The UUID class has a single constructor:

UUID uuid = new UUID(long mostSignificant64Bits, long leastSignificant64Bits);

If we want to use this constructor, we need to provide two long values. However, it requires us to construct the bit pattern for the UUID ourselves.

For convenience, there are three static methods to create a UUID.

The first method creates a version 3 UUID from the given byte array:

UUID uuid = UUID.nameUUIDFromBytes(byte[] bytes);

Second, the randomUUID() method creates a version 4 UUID. This is the most convenient way of creating a UUID instance:

UUID uuid = UUID.randomUUID();

The third static method returns a UUID object given the string representation of a given UUID:

UUID uuid = UUID.fromString(String uuidHexDigitString);

Let's now look at some implementations for generating UUIDs without using the built-in UUID class.

4. Implementations

We're going to separate the implementations into two categories depending on the requirement. The first category will be for identifiers that only need to be unique, and for that purpose, UUIDv1 and UUIDv4 are the best options. In the second category, if we need to always generate the same UUID from a given name, we would need a UUIDv3 or UUIDv5.

Since RFC 4122 does not specify the exact generation details, we won't look at an implementation of UUIDv2 in this article.

Let's now see the implementation for the categories we mentioned.

4.1. Versions 1 and 4

First of all, if privacy is a concern, UUIDv1 can alternatively be generated with a random 48-bit number instead of the MAC address. In this article, we'll look at this alternative.

First, we'll generate the 64 least and most significant bits as long values:

private static long get64LeastSignificantBitsForVersion1() {
    Random random = new Random();
    long random63BitLong = random.nextLong() & 0x3FFFFFFFFFFFFFFFL;
    long variant3BitFlag = 0x8000000000000000L;
    return random63BitLong + variant3BitFlag;
}

private static long get64MostSignificantBitsForVersion1() {
    LocalDateTime start = LocalDateTime.of(1582, 10, 15, 0, 0, 0);
    Duration duration = Duration.between(start, LocalDateTime.now());
    long seconds = duration.getSeconds();
    long nanos = duration.getNano();
    long timeForUuidIn100Nanos = seconds * 10000000 + nanos * 100;
    long least12SignificatBitOfTime = (timeForUuidIn100Nanos & 0x000000000000FFFFL) >> 4;
    long version = 1 << 12;
    return 
      (timeForUuidIn100Nanos & 0xFFFFFFFFFFFF0000L) + version + least12SignificatBitOfTime;
}

We can then pass these two values to the constructor of the UUID:

public static UUID generateType1UUID() {

    long most64SigBits = get64MostSignificantBitsForVersion1();
    long least64SigBits = get64LeastSignificantBitsForVersion1();

    return new UUID(most64SigBits, least64SigBits);
}

We'll now see how to generate UUIDv4. The implementation uses random numbers as the source. The Java implementation is SecureRandom, which uses an unpredictable value as the seed to generate random numbers in order to reduce the chance of collisions.

Let’s generate a version 4 UUID:

UUID uuid = UUID.randomUUID();

And then, let's generate a unique key using “SHA-256” and a random UUID:

MessageDigest salt = MessageDigest.getInstance("SHA-256");
salt.update(UUID.randomUUID().toString().getBytes("UTF-8"));
String digest = bytesToHex(salt.digest());

4.2. Versions 3 and 5

The UUIDs are generated using the hash of namespace and name. The namespace identifiers are UUIDs like Domain Name System (DNS), Object Identifiers (OIDs), and URLs. Let's look at the pseudocode of the algorithm:

UUID = hash(NAMESPACE_IDENTIFIER + NAME)

The only difference between UUIDv3 and UUIDv5 is the hashing algorithm — v3 uses MD5 (128 bits), while v5 uses SHA-1 (160 bits).

For UUIDv3 we'll use the method nameUUIDFromBytes() from the UUID class, which takes an array of bytes and apply the MD5 hash.

So let's first extract the bytes representation from the namespace and the specific name, and join them into a single array to send it to the UUID api:

byte[] nameSpaceBytes = bytesFromUUID(namespace);
byte[] nameBytes = name.getBytes("UTF-8");
byte[] result = joinBytes(nameSpaceBytes, nameBytes);

The final step will be to pass the result we got from the previous process to the nameUUIDFromBytes() method. This method will also set the variant and version fields:

UUID uuid = UUID.nameUUIDFromBytes(result);

Let's now see the implementation for UUIDv5. It is important to notice that Java doesn't provide a built-in implementation to generate version 5.

Let's check the code to generate the least and most significant bits, again as long values:

public static long getLeastAndMostSignificantBitsVersion5(final byte[] src, final int offset, final ByteOrder order) {
    long ans = 0;
    if (order == ByteOrder.BIG_ENDIAN) {
        for (int i = offset; i < offset + 8; i += 1) {
            ans <<= 8;
            ans |= src[i] & 0xffL;
        }
    } else {
        for (int i = offset + 7; i >= offset; i -= 1) {
            ans <<= 8;
            ans |= src[i] & 0xffL;
        }
    }
    return ans;
}

Now, we need to define the method that will take a name to generate the UUID. This method will use the default constructor defined in UUID class:

private static UUID generateType5UUID(String name) { 
    byte[] bytes = name.getBytes(StandardCharsets.UTF_8);
    MessageDigest md = MessageDigest.getInstance("SHA-1");
    byte[] hash = md.digest(bytes);
    long msb = getLeastAndMostSignificantBitsVersion5(hash, 0, ByteOrder.BIG_ENDIAN);
    long lsb = getLeastAndMostSignificantBitsVersion5(hash, 8, ByteOrder.BIG_ENDIAN);
    msb &= ~(0xfL << 12);
    msb |= ((long) 5) << 12;
    lsb &= ~(0x3L << 62);
    lsb |= 2L << 62;
    return new UUID(msb, lsb);
}

5. Conclusion

In this article, we saw the main concepts about UUID identifiers and how to generate them using a built-in class. We then saw some efficient implementations for different versions of UUIDs and their application scopes.

As always, the complete code for this article is available over on GitHub.

Java bottom

Get started with Spring 5 and Spring Boot 2, through the Learn Spring course:

>> CHECK OUT THE COURSE
Generic footer banner
Comments are closed on this article!