ULID – die bessere UUID

Ich bin langjähriger Befürworter von UUIDs für Primärschlüssel in Datenbanken, aber trotzdem ständig auf der Suche nach effizienteren und innovativeren Lösungen. Daher freut es mich, hier eine bessere Variante der UUIDs vorzustellen, die Vorteile beider Welten kombiniert: die ULIDs!

In der NoSQL-Welt sind UUIDs als Primärschlüssel schon lange üblich. Der wesentliche Vorteil hier: Es gibt keine Probleme mit doppelten Primärschlüsseln bei der Replizierung oder Skalierung.

Aber auch bei relationalen Datenbanken gibt es einige Vorteile:

• UUIDs können von der Anwendung erstellt werden, ohne dass eine Sequenz ausgelesen werden muss. Das reduziert die Datenbankzugriffe.
• Jeder Datensatz in jeder Tabelle hat eine eindeutige ID. Eine UUID, die man in einem Log oder einem Kommentar findet, kann eindeutig einem Datensatz zugeordnet werden. Verwechslungen sind ausgeschlossen.
• Und auch hier gilt: Datensätze können einfach zwischen Datenbanken oder Tabellen kopiert und verschoben werden, ohne Gefahr zu laufen, doppelte Primärschlüsseln zu erhalten.

Es gibt aber auch ein paar wesentliche Nachteile von UUIDs als Primärschlüssel.

• UUIDs brauchen mit 16 Byte viel Speicherplatz. Int nur 4 Byte bzw. Bigint 8 Byte.
  Aber Speicher ist selten unser größtes Problem.
• Man kann nicht danach sortieren, um zu erfahren, in welcher Reihenfolge die Einträge angelegt wurden.
  Aber dafür hat man ja in der Regel einen Zeitstempel gespeichert.
• Performance Probleme bei Verwendung von „clustered indexes“.
  Und die können ganz gravierend werden, insbesondere wenn viele Datensätze geschrieben werden!

Ein Clustered Index ist ein Index, der die physische Reihenfolge der Datensätze in einer Tabelle beeinflusst. Er ordnet die Daten direkt in der physischen Reihenfolge des Index-Schlüssels und wird normalerweise auf einer eindeutigen ID-Spalte erstellt (PK oder unique FK, wenn es keinen PK gibt). Dadurch werden Abfragen beschleunigt. Der Index wird normalerweise mit einem B-Tree (Balanced Tree) erstellt.

UUIDs als Primärschlüssel in einem Clustered Index verlangsamen das Einfügen (CREATE) von Datensätzen, da neue Datensätze nicht einfach am Ende des Indexes hinzugefügt werden können, sondern aufgrund der Zufälligkeit der UUID an der richtigen Stelle im Index eingefügt werden müssen.

Das Konzept der ULIDs schlägt einen UUID-kompatiblen Datentyp (16 Byte) vor, der mit einem Zeitstempel beginnt und mit einer Zufallszahl endet. Dadurch sind ULIDs im Gegensatz zu UUIDs lexikografisch sortierbar.

Daher stammt auch der Name ULID, der die Abkürzung für Universally Unique Lexicographically Sortable Identifier ist.

01AN4Z07BY      79KA1307SR9X4MV3
 
  |----------|             |----------------|
 Zeitstempel                Zufallswert
   48 Bits                         80 Bits

Der Zeitstempel zählt die vergangenen Millisekunden seit dem 1. Januar 1970. Die 48 Bits reichen noch für die nächsten paar tausend Jahre.

Durch diese Methode ist schon mal sichergestellt, dass ULIDs, die mit einem zeitlichen Unterschied von min. 1 Millisekunde erstellt werden, richtig sortiert sind und einfach am Ende des Index hinzugefügt werden können.

Werden auf einem System in einer Millisekunde mehrere ULIDs erstellt, so können „monotone“ ULIDs verwendet werden. Bei dieser Art von ULIDs wird bei allen ULIDs, die in der selben Millisekunde erzeugt werden, einfach die letzte Stelle des Zufallswerts erhöht, anstatt dass er immer komplett neu berechnet wird:

01BX5ZZKBKACTAV9WEVGEMMVRY
01BX5ZZKBKACTAV9WEVGEMMVRZ
01BX5ZZKBKACTAV9WEVGEMMVS0
01BX5ZZKBKACTAV9WEVGEMMVS1

Ps.: ULIDs werden mit Crockford’s base32 dargestellt, können aber auch in eine UUID konvertiert und entsprechend dargestellt werden.

Hier sieht man schön, dass ULIDs (in Form von UUIDs in PostgreSQL) ähnlich beginnen, wenn sie zu einem ähnlichen Zeitpunkt erstellt wurden. Die ersten zwei Einträge wurden zum exakt selben Zeitpunkt erstellt, weshalb sich die UUIDs daher nur in der letzten Stelle unterscheiden (2->3).

Bei der Verwendung von UUIDs, insbesondere der Version 4 wo Zufallswerte verwendet werden, ist das Risiko von Kollisionen – also das Auftreten von zwei identischen UUIDs – extrem gering. In der Praxis wird dieses Risiko als so minimal angesehen, dass es vernachlässigt werden kann. Bei ULIDs, die ebenfalls auf Zufallsgenerierung basieren, ist das Kollisionsrisiko theoretisch etwas höher als bei UUIDs, aber dennoch immer noch so gering, dass es in den meisten Anwendungen ignoriert werden kann.

Und wie nutze ich ULIDs in Java? Ganz einfach! Dafür gibt es bereits mehrere Bibliotheken, die einen Generator für ULIDs zur Verfügung stellen, wie zum Beispiel ulid-creator und ulid4j. In den folgenden Beispielen zeige ich, wie der ulid-creator verwendet werden kann.

Zuerst muss die Abhängigkeit ergänzt werden. Hier der Code für Maven bzw. Gradle:

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

implementation group: 'com.github.f4b6a3', name: 'ulid-creator', version: '5.2.0'

Die neuste Version findet sich hier: https://mvnrepository.com/artifact/com.github.f4b6a3/ulid-creator

Mit dem folgenden Code kann eine „monotone“ ULID generiert werden, was sich besonders beim Erstellen von großen Mengen Primärschlüssel anbietet:

final Ulid ulid = UlidCreator.getMonotonicUlid();

Außerdem können ULIDs auch basierend auf einer Zeichenkette erstellt werden. Das ist deterministisch, wodurch zum Beispiel geprüft werden kann, ob eine ULID für einen gewissen String erstellt wurde:

final var username = "JohnDoe";
final Ulid usernameUlid = UlidCreator.getHashUlid(time, userName);
 
// ....
 
// verify ULID belongs to John Doe
if(Arrays.equals(theUlidToCheck.getRandom(), usernameUlid.getRandom())) {
    // the random part of theUlidToCheck equals the random part of the JohnDoe ULID
}

Um ULIDs beispielsweise mit Hibernate und einer PostgreSQL Datenbank zu verwenden, kann als Primärschlüssel einfach eine UUID verwendet werden:

@Entity
public class Event implements Serializable {
    @Id
    @Column(name = 'event_id', unique = true, nullable = false)
    @Type(type = "org.hibernate.type.PostgresUUIDType")
    private UUID id;
 
    @Column(name = "creation_date")
    @CreationTimestamp
    private LocalDateTime creationDate;
 
    // ...
}

Beim Erzeugen der neuen Entitäten muss dann nur die ULID vor dem Persistieren generiert und als UUID gespeichert werden:

events.forEach(event -> event.setId(UlidCreator.getMonotonicUlid().toUuid()));
eventRepo.saveAll(events);

Das war’s schon!

Während UUIDs ihre Vorteile haben und in manchen Situationen weiterhin eine gute Wahl sein können, bieten ULIDs dank ihrer lexicographischen Sortierbarkeit und ihrer Eindeutigkeit eine interessante Alternative, insbesondere für Systeme, die eine hohe Schreibdurchsatzrate aufweisen oder wo die Reihenfolge der Erstellung wichtig ist.

Für Projekte, die eine effiziente und dennoch eindeutige Identifikationsmethode benötigen, sind ULIDs definitiv eine Überlegung wert!