Time-Sorted Unique Identifiers with Hypersistence TSID

1. Introduction

In this tutorial, we’re going to look at Time-Sorted Unique Identifiers (TSIDs). In particular, we’re going to look at the Hypersistence TSID library to work with these IDs in Java.

2. What are TSIDs

TSIDs, or Time-Sorted Unique Identifiers, are identifiers we can guarantee are unique and can be naturally sorted by the time they were generated. Additionally, we can retrieve values from these IDs to determine the exact time each ID was generated.

The Hypersistence TSID library then allows us to represent these generated IDs as either a 64-bit integer or a Base-32 encoded 13-character string. This allows us to store or transfer the ID in formats optimized for either machine processing or human readability.

2.1. TSID Structure

Hypersistence TSIDs store values as 64-bit integers. This consists of three portions:

• Milliseconds since the epoch. This is always 42 bits in size.
• Node ID. We can configure this to be between 0 and 20 bits in size.
• Counter. This is between 2 and 22 bits in size, depending on the size of the Node ID.

By default, the node ID is 10 bits in length. This then means the counter is 12 bits long.

The counter portion exists to ensure unique values are generated even within the same millisecond. The default size of 12 bits means we can generate 2^12 = 4,096 unique values per millisecond. Increasing this up to 22 bits would instead allow us to generate up to 4,194,304 unique values per millisecond.

The node ID portion then acts as an identifier of the exact node that generated the ID. This allows us to generate unique IDs across different servers without any complex coordination. We can simply assign each server a different node ID, and this then guarantees values generated on different nodes will never be able to collide.

For example, we might have an ID value of 38,352,658,567,418,867. This breaks down as:

00000000 10001000 01000001 10001010 00101110 00011010 01010011 11110011
|-----------||---------||---------------------------------------------|
|  Counter  || Node ID ||                  Timestamp                  |

• Timestamp = 1,692,990,591,987. This represents Friday, 25 August 2023 19:09:51.987 UTC.
• Node ID = 528
• Counter = 8

The next ID generated in the same millisecond by this node will have a counter value of 9. And an ID generated by a different node will have a different node ID value. As such, all of those IDs would be safely unique.

3. Dependencies

Before using Hypersistence TSID, we need to include the latest version in our build, which is 2.1.4 at the time of writing.

If we’re using Maven, we can include this dependency in our pom.xml file:

<dependency>
    <groupId>io.hypersistence</groupId>
    <artifactId>hypersistence-tsid</artifactId>
    <version>2.1.4</version>
</dependency>

At this point, we’re ready to start using it in our application.

4. Generating TSIDs

Once we have Hypersistence TSID available, we’re ready to use it to generate our IDs.

Normally, we’ll create TSIDs using a factory. We can get started quickly by using a provided singleton instance:

TSID.Factory tsidFactory = TSID.Factory.INSTANCE;

Alternatively, we can create our own instance:

TSID.Factory tsidFactory = TSID.Factory.builder().build();

We’ll see later how we can customise this to our needs.

Our TSID Factory is threadsafe. As such, we should create one instance per node and reuse it everywhere we need to generate new IDs to ensure that they’re always unique.

Once we have a TSID Factory, we can use it to generate TSIDs using generate():

TSID tsid = tsidFactory.generate();

This will always return the next unique TSID, respecting the current system time, the current counter value and the configured node value.

Our TSID instances correctly implement equals() and hashCode(), and are also Comparable, so we can safely use them in whatever context we need.

If we’re using the singleton factory, we also have a shorthand that we can use:

TSID tsid = TSID.Factory.getTsid();

This is exactly the same as above, though slightly shorter to write.

Alternatively, we have a simple option to very efficiently get a TSID:

TSID tsid = TSID.fast();

This prioritizes speed, so it cuts some corners during generation. In particular, it ignores the settings for the node from which we generate the ID, and the counter simply increments indefinitely without resetting when the time changes. However, if performance is more important than accuracy, then this is a good option.

4.1. TSID Factory

We’ve seen how to create a TSID Factory used to generate new TSIDs. When we do this, we have several ways to configure it to better suit our needs.

Most usefully, we can specify the value for the node section of the generated ID. We can specify this in a number of ways:

• The withNode() method on our factory builder.
• The system property tsid.node.
• The environment variable TSID_NODE.
• Using a random number.

This lets us fully control which value to use while still ensuring that a value is always provided.

We can set the number of bits used for the node in a similar manner:

• The withNodeBits() method on our factory builder.
• The system property tsid.node.count.
• The environment variable TSID_NODE_COUNT.
• The default value “10”.

By setting these values through system properties and environment variables, we can easily vary them across different instances of our application, helping ensure that the generated IDs remain unique.

In addition to specifying the node, we can also customize the generation of the timestamp portion. We’re able to provide an additional clock instead of using the system clock, and even specify the value to use for the epoch instead of the default:

TSID.Factory factory = TSID.Factory.builder()
    .withClock(clock)
    .withCustomEpoch(Instant.parse("2000-01-01T00:00:00Z"))
    .build();

Here we provide a custom clock and set the epoch to be January 1st 2000, instead of 1970.

5. Serializing TSIDs

Once we’ve generated a TSID instance, we need to be able to serialize, and potentally deserialize, them.

The TSID class has support for converting the generated ID to either a Long – structured as described above – or to a String:

long tsidLong = tsid.toLong(); // 809100737063473402
String tsidString = tsid.toString(); // 0PEM0TNJ2SM7T

Both represent the same ID, only in different formats. We can use these as appropriate. For example, the long integer format is more memory-efficient and easier to work with, but may have issues in certain languages (e.g. JavaScript uses a floating-point format for numbers, so it may have accuracy issues with numbers of this size).

We can also convert these string and long formats back into TSID instances using TSID.from():

TSID tsid = TSID.from(tsidLong);
TSID tsid = TSID.from(tsidString);

These produce exactly the same value that the system originally generated. This means we can store or transfer our IDs however we wish and restore them to their original state.

We can also extract the timestamp portion of the TSID if needed. This can be either as an Instant or as milliseconds since the epoch:

Instant instant = tsid.getInstant();
long millis = tsid.getUnixMilliseconds();

We can’t access the node or counter values. We’d need to know how many bits are assigned to each to get this, and the TSID doesn’t store that information.

6. Summary

In this article, we looked at the concept of Time-Sorted Unique Identifiers and used the Hypersistence TSID library to work with them in Java. Next time you need to generate unique IDs, why not give it a try?

As usual, all of the examples from this article are available over on GitHub.