f4b6a3 / ksuid-creator

A Java implementation of K-Sortable Unique Identifiers (KSUID).

KSUID Creator

This is a Java implementation of Segment's K-Sortable Globally Unique Identifiers.

In summary:

• Sorted by generation time;
• Can be stored as a string of 27 chars;
• Can be stored as an array of 20 bytes;
• String format is encoded to base-62 (0-9A-Za-z);
• String format is URL safe and has no hyphens.

This project contains a micro benchmark and a good amount of unit tests.

The jar file can be downloaded directly from maven.org.

Read the Javadocs.

Also read the KSUID release post.

How to Use

Create a KSUID:

Ksuid ksuid = KsuidCreator.getKsuid();

Create a KSUID String:

String string = KsuidCreator.getKsuid().toString();

Maven dependency

Add these lines to your pom.xml.

<!-- https://search.maven.org/artifact/com.github.f4b6a3/ksuid-creator -->
<dependency>
  <groupId>com.github.f4b6a3</groupId>
  <artifactId>ksuid-creator</artifactId>
  <version>4.1.1</version>
</dependency>

See more options in maven.org.

Modularity

Module and bundle names are the same as the root package name.

• JPMS module name: com.github.f4b6a3.ksuid
• OSGi symbolic name: com.github.f4b6a3.ksuid

Segment's KSUID

The Segment's KSUID is a 160 bit long identifier (20 bytes). It consists of a 32-bit timestamp and a 128-bit randomly generated payload. Its canonical string representation is 27 characters long.

// Create a KSUID
Ksuid ksuid = KsuidCreator.getKsuid();

Sequence of KSUIDs:

24QbW6CHZpeF5q3KvFxlQpSPuR7
24QbW75lYxOmr1KZP8gi0L7WZMW
24QbW4SpzjSBTs5PMTTo5y8z793
24QbW3RXcN0OFfjTURVCNmLqJch
24QbW3BCODy9IZAjvaAPH6qgr8U
24QbW5DlcuhMlZHEXJVAOddmkeZ
24QbW6PtsLVRl4Xi9rmPAjApl1k
24QbW0TRakXKk6bykUbCSu7BJAj
24QbVznAO74F0zMaOrIShGphXdT
24QbW5HqqFlMtRqiQ1h1BHjORxf
24QbW4bWYmhDe3mZLjWcCUUZyOh
24QbW3iL26DpJmxE31QSHLan4jB
24QbW1gwBP7yClo43pJHTTb1EMU
24QbW3pKgLubTlc8xRT380eDRXb
24QbW4lHWRuUhIY0twbkTaCbQmt
24QbW0rfP04tIdUfReOcFxKaI7o

|----|--------------------|
 time       payload

Sub-second KSUID

The Sub-second KSUID is a variant of Segment's KSUID. A small number of its payload bits are traded for more timestamp bits. Its main advantage is the precision.

The number of sub-second bits depends on Instant.now() resolution. In JDK-8, the usual resolution is millisecond. In JDK-9+, microsecond.

Three sub-second precisions are supported: millisecond, microsecond, and nanosecond. The precision is detected at runtime.

// Create a Sub-second KSUID
Ksuid ksuid = KsuidCreator.getSubsecondKsuid();

Sequence of Sub-second KSUIDs:

24QbW5oYmzZmRWVGuv0ANLv7NxH
24QbW5ofcCGe3QtYlS60qlBmbi5
24QbW5oPZzC4nOeOtzDphnwe9ud
24QbW5omwpeVZLZNATGzcO47FcR
24QbW5ogYyeN3MIKfllQaDl04Gr
24QbW5oZDMWf3uQwk3BgOOLKyza
24QbW5ol0wQ9s0mNcvhisQipr96
24QbW5obEClijP4R7UedowRf8bo
24QbW5oD3yDaFtpZdEsmNIFAg0x
24QbW5oF304l9mj8eSdMQv5ZdsP
24QbW5o1xxkjquiqhWqT6tP4feA
24QbW5oCDHZS6AQJDmM4p22j3PH
24QbW5oI9egLkvY3iQpQXZAZTbk
24QbW5owmgSDnATUZyE4b58wSNz
24QbW5ovHJtU9kM58kDZZGGgCQ5
24QbW5oBsHnmQseJs495DpSCCze

|------|------------------|
  time       payload

Monotonic KSUID

The Monotonic KSUID is another variant of Segment's KSUID. Its payload is incremented by 1 whenever the current second is equal to the previous one. Its main advantage is speed.

This implementation is derived from Monotonic ULID. It's like Segment's sequence.go generator, which generates sequential KSUIDs, but there's a difference. You must pass a seed to sequence.go generator. In Monotonic KSUID, the seed is regenerated every second.

// Create a Monotonic KSUID
Ksuid ksuid = KsuidCreator.getMonotonicKsuid();

Sequence of Monotonic KSUIDs:

24QcJGoCufA6t80z28wBpCWdE10
24QcJGoCufA6t80z28wBpCWdE11
24QcJGoCufA6t80z28wBpCWdE12
24QcJGoCufA6t80z28wBpCWdE13
24QcJGoCufA6t80z28wBpCWdE14
24QcJGoCufA6t80z28wBpCWdE15
24QcJGoCufA6t80z28wBpCWdE16
24QcJGoCufA6t80z28wBpCWdE17
24QcJRYPLFj3bIqFnNpoP7Rv6Hs < second changed
24QcJRYPLFj3bIqFnNpoP7Rv6Ht
24QcJRYPLFj3bIqFnNpoP7Rv6Hu
24QcJRYPLFj3bIqFnNpoP7Rv6Hv
24QcJRYPLFj3bIqFnNpoP7Rv6Hw
24QcJRYPLFj3bIqFnNpoP7Rv6Hx
24QcJRYPLFj3bIqFnNpoP7Rv6Hy
24QcJRYPLFj3bIqFnNpoP7Rv6Hz
     ^ look               ^ look

|----|--------------------|
 time       payload

More Examples

Create a quick KSUID:

Ksuid ksuid = Ksuid.fast();

---

Create a KSUID from a canonical string (27 chars, base-62):

Ksuid ksuid = Ksuid.from("0123456789ABCDEFGHIJKLMNOPQ");

---

Get the creation instant of a KSUID:

Instant instant = ksuid.getInstant(); // 2014-06-05T09:06:29Z

// static method
Instant instant = Ksuid.getInstant("0123456789ABCDEFGHIJKLMNOPQ"); // 2014-06-05T09:06:29Z

---

A key generator that makes substitution easy if necessary:

package com.example;

import com.github.f4b6a3.ksuid.KsuidCreator;

public class KeyGenerator {
    public static String next() {
        return KsuidCreator.getKsuid().toString();
    }
}

String key = KeyGenerator.next();

---

A KsuidFactory with java.util.Random:

// use a `java.util.Random` instance for fast generation
KsuidFactory factory = KsuidFactory.newInstance(new Random());

// use the factory
Ksuid ksuid = factory.create();

---

A KsuidFactory with SplittableRandom:

// use a random function that returns a long value
SplittableRandom random = new SplittableRandom();
KsuidFactory factory = KsuidFactory.newInstance(() -> random.nextLong());

// use the factory
Ksuid ksuid = factory.create();

---

A KsuidFactory with RandomGenerator (JDk 17+):

// use a random function that returns a long value
RandomGenerator random = RandomGenerator.getDefault();
KsuidFactory factory = KsuidFactory.newInstance(() -> random.nextLong());

// use the factory
Ksuid ksuid = factory.create();

---

A KsuidFactory with ThreadLocalRandom:

// use a random function that returns a byte array
KsuidFactory factory = KsuidFactory.newInstance((length) -> {
    final byte[] bytes = new byte[length];
    ThreadLocalRandom.current().nextBytes(bytes);
    return bytes;
});


// use the factory
Ksuid ksuid = factory.create();

Benchmark

This section shows benchmarks comparing KsuidCreator to UUID.randomUUID().

---------------------------------------------------------------------------------
THROUGHPUT (operations/msec)              Mode  Cnt     Score      Error   Units
---------------------------------------------------------------------------------
UUID_randomUUID                          thrpt    5   3387.205 ±  10.224  ops/ms (1.00)
UUID_randomUUID_toString                 thrpt    5   2810.942 ±  58.598  ops/ms
-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
Ksuid_fast                               thrpt    5  19777.514 ± 998.524  ops/ms (5.84)
Ksuid_fast_toString                      thrpt    5   2998.873 ± 192.978  ops/ms
-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
KsuidCreator_getKsuid                    thrpt    5   2932.173 ±  59.416  ops/ms (0.87)
KsuidCreator_getKsuid_toString           thrpt    5   1626.184 ±  66.695  ops/ms
-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
KsuidCreator_getSubsecondKsuid           thrpt    5   2963.775 ±  38.594  ops/ms (0.87)
KsuidCreator_getSubsecondKsuid_toString  thrpt    5   1550.485 ± 124.456  ops/ms
-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
KsuidCreator_getMonotonicKsuid           thrpt    5  16123.933 ± 226.742  ops/ms (4.76)
KsuidCreator_getMonotonicKsuid_toString  thrpt    5   3020.113 ±  56.734  ops/ms
---------------------------------------------------------------------------------
Total time: 00:03:22
---------------------------------------------------------------------------------

System: CPU i7-8565U, 16G RAM, Ubuntu 22.04, JVM 11, rng-tools installed.

To execute the benchmark, run ./benchmark/run.sh.

Other identifier generators

Check out the other ID generators from the same family:

• UUID Creator: Universally Unique Identifiers
• ULID Creator: Universally Unique Lexicographically Sortable Identifiers
• TSID Creator: Time Sortable Identifiers

License

This library is Open Source software released under the MIT license.

ksuid-creator's Issues

Add support for RandomGenerator in Java 17

implement monotonic KSUID

Implement Monotonic KSUID inspired on Monotonic ULID.

handle clock drift

Keep monotonicity in case of small clock drift.

Add constructors in KsuidFactory for random generators

New constructors:

public KsuidFactory(Random random) { }

public KsuidFactory(RandomGenerator randomGenerator) { }

First version

Version 3.0.0

Optimize comparison

Version 2.0.0

Sonatype Lift analysis report

BadShiftAmount
Tool: ErrorProne (JDK8)
File: src/main/java/com/github/f4b6a3/ksuid/factory/KsuidFactory.java
Line: 150
Description: Shift by an amount that is out of range

ksuid-creator/src/main/java/com/github/f4b6a3/ksuid/factory/KsuidFactory.java

Line 150 in b021ed5

payload[0] = (byte) ((subsecs >>> 0x38) & 0xffL);

Add benchmark code to compare KSUID with UUID

Rewrite docs

Add a fast method to generate identifiers

Implement a convenience method to generate quick KSUIDs.

Ksuid ksuid = Ksuid.fast();

SplittableRandom will be employed by this method.

Security-sensitive applications that require a cryptographically strong pseudo-random generator should continue to use KsuidCreator.getKsuid().

Optimize internal representation and comparison operation

1. Replace the internal field byte[20] bytes with two fields: int seconds and byte[16] payload.
2. Optimize the Ksuid.compareTo() method after the change in the internal representation.

Module name for Java 9+

Add this line to MANIFEST.MF:

Automatic-Module-Name: com.github.f4b6a3.ksuid

Provide OSGI support

Sonatype Lift analysis report

IntLongMath
Tool: ErrorProne (JDK8)
File: src/main/java/com/github/f4b6a3/ksuid/factory/KsuidFactory.java
Line: 180
Description: Expression of type int may overflow before being assigned to a long

ksuid-creator/src/main/java/com/github/f4b6a3/ksuid/factory/KsuidFactory.java

Line 180 in 8a9ec93

final long subsecs = (nanoseconds << 2) | (payload[3] & 0b00000011);