The best UUID type for a database Primary Key

Imagine having a tool that can automatically detect JPA and Hibernate performance issues. Wouldn’t that be just awesome?

Well, Hypersistence Optimizer is that tool! And it works with Spring Boot, Spring Framework, Jakarta EE, Java EE, Quarkus, or Play Framework.

So, enjoy spending your time on the things you love rather than fixing performance issues in your production system on a Saturday night!

You can earn a significant passive income stream from promoting my book, courses, tools, training, or coaching subscriptions.

If you're interested in supplementing your income, then join my affiliate program.

Introduction

In this article, we are going to see what UUID (Universally Unique Identifier) type works best for a database column that has a Primary Key constraint.

While the standard 128-bit random UUID is a very popular choice, you’ll see that this is a terrible fit for a database Primary Key column.

Standard UUID and database Primary Key

A universally unique identifier (UUID) is a 128-bit pseudo-random sequence that can be generated independently without the need for a single centralized system in charge of ensuring the identifier’s uniqueness.

The RFC 4122 specification defines five standardized versions of UUID, which are implemented by various database functions or programming languages.

For instance, the UUID() MySQL function returns a version 1 UUID number.

And the Java UUID.randomUUID() function returns a version 4 UUID number.

For many devs, using these standard UUIDs as a database identifier is very appealing because:

  • The ids can be generated by the application. Hence no central coordination is required.
  • The chance of identifier collision is extremely low.
  • The id value being random, you can safely send it to the UI as the user would not be able to guess other identifier values and use them to see other people’s data.

But, using a random UUID as a database table Primary Key is a bad idea for multiple reasons.

First, the UUID is huge. Every single record will need 16 bytes for the database identifier, and this impacts all associated Foreign Key columns as well.

Second, the Primary Key column usually has an associated B+Tree index to speed up lookups or joins, and B+Tree indexes store data in sorted order.

However, indexing random values using B+Tree causes a lot of problems:

  • Index pages will have a very low fill factor because the values come randomly. So, a page of 8kB will end up storing just a few elements, therefore wasting a lot of space, both on the disk and in the database memory, as index pages could be cached in the Buffer Pool.
  • Because the B+Tree index needs to rebalance itself in order to maintain its equidistant tree structure, the random key values will cause more index page splits and merges as there is no pre-determined order of filling the tree structure.

If you’re using SQL Server or MySQL, then it’s even worse because the entire table is basically a clustered index.

Clustered Index Table

And all these problems will affect the secondary indexes as well because they store the Primary Key value in the secondary index leaf nodes.

Clustered Index and Secondary Index

In fact, almost any database expert will tell you to avoid using the standard UUIDs as database table Primary Keys:

TSID – Time-Sorted Unique Identifiers

If you plan to store UUID values in a Primary Key column, then you are better off using a TSID (time-sorted unique identifier).

One such implementation is offered by the TSID Creator OSS library, which provides a 64-bit TSID that’s made of two parts:

  • a 42-bit time component
  • a 22-bit random component

The random component has two parts:

  • a node identifier (0 to 20 bits)
  • a counter (2 to 22 bits)

The node identifier can be provided by the tsidcreator.node system property when bootstrapping the application:

-Dtsidcreator.node="12"

The node identifier can also be provided via the TSIDCREATOR_NODE environment variable:

export TSIDCREATOR_NODE="12"

The library is available on Maven Central, so you can get it via the following dependency:

<dependency>
    <groupId>com.github.f4b6a3</groupId>
    <artifactId>tsid-creator</artifactId>
    <version>${tsid-creator.version}</version>
</dependency>

You can create a Tsid object that can use up to 256 nodes like this:

Tsid tsid = TsidCreator.getTsid256();

From the Tsid object, we can extract the following values:

  • the 64-bit numerical value,
  • the Crockford’s Base32 String value that encodes the 64-bit value,
  • the Unix milliseconds since epoch that is stored in the 42-bit sequence

To visualize these values, we can print them into the log:

long tsidLong = tsid.toLong();
String tsidString = tsid.toString();
long tsidMillis = tsid.getUnixMilliseconds();

LOGGER.info(
    "TSID numerical value: {}", 
    tsidLong
);

LOGGER.info(
    "TSID string value: {}", 
    tsidString
);

LOGGER.info(
    "TSID time millis since epoch value: {}", 
    tsidMillis
);

And we get the following output:

TSID numerical value: 388400145978465528
TSID string value: 0ARYZVZXW377R
TSID time millis since epoch value: 1670438610927

When generating ten values:

for (int i = 0; i < 10; i++) {
    LOGGER.info(
        "TSID numerical value: {}",
        TsidCreator.getTsid256().toLong()
    );
}

We can see that the values are monotonically increasing:

TSID numerical value: 388401207189971936
TSID numerical value: 388401207189971937
TSID numerical value: 388401207194165637
TSID numerical value: 388401207194165638
TSID numerical value: 388401207194165639
TSID numerical value: 388401207194165640
TSID numerical value: 388401207194165641
TSID numerical value: 388401207194165642
TSID numerical value: 388401207194165643
TSID numerical value: 388401207194165644

Awesome, right?

Using the TSID in your application

Because the default TSID factories provided via the TsidCreator utility comes with a synchronized random value generator, it’s better to use a custom TsidFactory that provides the following optimizations:

  • It can generate the random values using a ThreadLocalRandom, therefore avoiding Thread blocking on synchronized blocks
  • It can use a small number of node bits, therefore leaving us more bits for the random-generated numerical value.

So, we can define the following TsidUtil that provides us a TsidFactory to use whenever we want to generate a new Tsid object:

public static class TsidUtil {
    public static final String TSID_NODE_COUNT_PROPERTY = 
        "tsid.node.count";
    public static final String TSID_NODE_COUNT_ENV = 
        "TSID_NODE_COUNT";

    public static TsidFactory TSID_FACTORY;

    static {
        String nodeCountSetting = System.getProperty(
            TSID_NODE_COUNT_PROPERTY
        );
        if(nodeCountSetting == null) {
            nodeCountSetting = System.getenv(
                TSID_NODE_COUNT_ENV
            );
        }

        int nodeCount = nodeCountSetting != null ?
            Integer.parseInt(nodeCountSetting) :
            256;

        int nodeBits = (int) (Math.log(nodeCount) / Math.log(2));

        TSID_FACTORY = TsidFactory.builder()
            .withRandomFunction(length -> {
                final byte[] bytes = new byte[length];
                ThreadLocalRandom.current().nextBytes(bytes);
                return bytes;
            })
            .withNodeBits(nodeBits)
            .build();
    }
}

And to demonstrate that we don’t get any collision even when using multiple threads on the same application node, we can use the following test case:

int threadCount = 16;
int iterationCount = 100_000;

CountDownLatch endLatch = new CountDownLatch(threadCount);

ConcurrentMap<Tsid, Integer> tsidMap = new ConcurrentHashMap<>();

long startNanos = System.nanoTime();

for (int i = 0; i < threadCount; i++) {
    final int threadId = i;
    new Thread(() -> {
        for (int j = 0; j < iterationCount; j++) {
            Tsid tsid = TsidUtil.TSID_FACTORY.create();
            assertNull(
                "TSID collision detected",
                tsidMap.put(
                    tsid, 
                    (threadId * iterationCount) + j
                )
            );
        }

        endLatch.countDown();
    }).start();
}

LOGGER.info("Starting threads");
endLatch.await();

LOGGER.info(
    "{} threads generated {} TSIDs in {} ms",
    threadCount,
    new DecimalFormat("###,###,###").format(
        threadCount * iterationCount
    ),
    TimeUnit.NANOSECONDS.toMillis(
        System.nanoTime() - startNanos
    )
);

When running this test, we get the following result:

16 threads generated 1,600,000 TSIDs in 781 ms

Not only the TSID generate was collision-free, but we managed to generate 1.6 million ids in less than 800 milliseconds.

Using the TSID as a Primary Key value

Since the TSID is a time-sorted 64-bit number, the best way to store it in the database is to use a bigint column type:

CREATE TABLE post (
    id bigint NOT NULL,
    title varchar(255),
    PRIMARY KEY (id)
)

And, on application side, you need to use a 64-bit numer, like the Java Long object type:

@Entity
@Table(name = "post")
public class Post {

    @Id
    private Long id;

    private String title;
    
}

That’s it!

If you enjoyed this article, I bet you are going to love my Book and Video Courses as well.

And there is more!

You can earn a significant passive income stream from promoting all these amazing products that I have been creating.

If you're interested in supplementing your income, then join my affiliate program.

Conclusion

Using the standard UUID as a Primary Key value is not a good idea unless the first bytes are monotonically increasing.

For this reason, using a time-sorted TSID is a much better idea. Not only that it requires half the number of bytes as a standard UUID, but it fits better as a B+Tree index key.

While SQL Server offers a time-sorted GUID via the NEWSEQUENTIALID, the size of the GUID is 128 bits, so it’s twice as large as a TSID.

The same issue is with version 7 of the UUID specification, which provides a time-sorted UUID. However, it uses the same canonical format (128 bits) which is way too large. The impact of the Primary Key column storage is amplified by every referencing Foreign Key columns.

If all your Primary keys are 128-bit UUIDs, then the Primary Key and Foreign Key indexes are going to require a lot of space, both on the disk and in the database memory, as the Buffer Pool holds both table and index pages.

Transactions and Concurrency Control eBook

32 Comments on “The best UUID type for a database Primary Key

  1. Hi Vlad,
    Thank you for the great article.
    Can we use Tsid in production? What do you think? What about Maintenance and contribution?
    What do you think about the other approaches like Instagram or Flickr?
    Instagram:
    https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c
    Flickr:
    https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

    I am still trying to decide what I should use for my new project. Could you give me a hint? That would be great.

    BR,
    Chris

    • Hi. I’m glad you liked the article. Here are my answers to your questions:

      Can we use Tsid in production? What do you think?

      As long as you have integration tests and system tests to prove they work as expected based on your business requirements, then you could use it in production.

      What about Maintenance and contribution?

      The TSID Creator is OSS, and the license is MIT. Even if the original author doesn’t maintain it, you can always fork it and push any change you want.

      What do you think about the other approaches like Instagram or Flickr?

      Instagram uses the first 41 bits for the timestamp data, and TSID uses 42. Instagram uses the next 13 bits for the logical shard, while TSID uses at most 12 bits The remaining bits are sequential in Instagram while random in TSID.

      So, the Instagram solution is actually nice if you use a database function to generate your Ids while TSID is useful if you generate the ids in the application without calling the DB for that.

      • Thank you! I will try both generators and play around. I think this topic should be mentioned in books too.

        BR,
        Chris

  2. Doesn’t this result in guessable IDs if multiple IDs are generated within the same millisecond? If the TSID is also used within an web API an attacker could guess other valid/used TSIDs, right? With a UUID guessing IDs is (nearly) impossible but with TSIDs it seams quite easy (just increment/decrement). An attacker who could create one TSID every millisecond, even every used TSID could be generated.
    So the security of an application should not rely on the TSID IMHO. Or am I missing something?

    • Doesn’t this result in guessable IDs if multiple IDs are generated within the same millisecond?

      A SEQUENCE or IDENTITY generates even more easily guessable ids, yet this problem can be addressed by the data adapter layer.

      If the TSID is also used within a web API, an attacker could guess other valid/used TSIDs, right?

      No one said you have to expose the ids externally. The auto-generated ids are the most common PK option, and there are ways you can prevent this situation using externalIds. The same pattern applies to TSIDs.

      With a UUID guessing IDs is (nearly) impossible but with TSIDs it seams quite easy (just increment/decrement).

      Yes, you can use a UUID as the external id. Just don’t save it in the DB.

      So the security of an application should not rely on the TSID IMHO.

      The security of your app is not derived from the PK column type. Paying the performance penalty for using a UUID PK doesn’t make your app secure. All you need to do is make sure you never expose a guessable id externally. Just like you don’t expose your JPA entities externally, and you’re using external DTOs or Value Objects to decouple the web and the data access layer, you can replace the guessable ids with external ids.

      • What do you mean by:
        Yes, you can use a UUID as the external id. Just don’t save it in the DB.

        How to use UUID without saving it in the DB? Please can you give more details/scenario?

      • You can use the UUID as the externalId that you can store in Redis in a key/value collection where the key is the UUID that you send to the client and the value is the sequential database identifier that you never expose to the outside world.

  3. I never knew of about TSID. Many thanks, for educating people like me.

  4. The problem with tsid is that they require too much precision to be used in REST APIs with javascript clients.
    E.g. 395228849641804517 cannot be properly represented in a javascript application
    “`
    let foo = 395228849641804517;
    console.log(“foo”, foo);
    => 395228849641804540

  5. Great article, thanks! Do you have any suggestions on how to get a node id in a simple way on Kubernetes?

  6. Hey Vlad, which representation do you recommend to be persisted on the database, the string format, or the long one?

  7. Interesting. I know you’re taking here about SQL, but UUID is pretty much the standard for record identifiers in NoSQL I believe (certainly seems to be in Mongo, which is the only one I’ve used much). Foreign keys aren’t so much of an issue there, but indexing still is. How have they got round the indexing issues – or should we be using something else there too?

    • For LSM storages, the fact that UUID is not time-sorted is not an issue, but the extra space is.

      Many applications could do just fine with a 64-bit Tsid. The fact that many use UUID is that they have no idea there are better alternatives.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.