TypeID – typsichere, K-sortierbare, global eindeutige Identifikatoren, inspiriert von Stripe-IDs

• TypeID ist ein typsicherer Identifikator auf Basis einer Erweiterung von UUIDv7, ein Format für global eindeutige Identifikatoren, inspiriert von der Nutzung von Präfixen in der Stripe API
• Die kanonische Zeichenkette besteht aus drei Teilen: einem kleingeschriebenen type prefix in snake_case-ASCII mit maximal 63 Zeichen, einem Trennzeichen _ und einem 26 Zeichen langen UUIDv7-Suffix, das mit modifiziertem base32 kodiert ist
• Mit dem type prefix wird verhindert, dass eine user-ID versehentlich dort verwendet wird, wo eine post-ID erforderlich ist; außerdem lässt sich beim Debugging sofort erkennen, auf welchen Entitätstyp sich ein Identifikator bezieht
• TypeID ist eine Obermenge von UUID; entfernt man die Typinformation und dekodiert den Wert, erhält man eine gültige UUIDv7
• Durch die K-Sortierbarkeit kann TypeID als Primärschlüssel in Datenbanken verwendet werden und soll im Vergleich zu vollständig zufälligen globalen IDs wie UUIDv4 Probleme mit schlechter Datenbank-Locality verringern
• Die base32-Kodierung bietet URL-Sicherheit, Unabhängigkeit von Groß-/Kleinschreibung, vermeidet mehrdeutige Zeichen, ermöglicht Auswahl per Doppelklick und ist kürzer als die traditionelle hexadezimale Kodierung von UUIDs
• Offizielle Implementierungen werden für Go, SQL und TypeScript bereitgestellt; die aktuelle Spec-Version ist v0.3.0
• Mit dem Kommandozeilen-Tool lassen sich TypeIDs erzeugen, UUIDs aus bestehenden TypeIDs dekodieren und UUIDs als TypeID kodieren
  • typeid new prefix erzeugt eine neue TypeID
  • typeid decode prefix_01h2xcejqtf2nbrexx3vqjhp41 gibt type und uuid aus
  • typeid encode prefix 0188bac7-4afa-78aa-bc3b-bd1eef28d881 erzeugt eine TypeID
• Im TypeID Converter von Jetify lassen sich TypeID-Strings in UUIDs umwandeln oder UUIDs im Format prefix:UUID in TypeIDs konvertieren

[GN⁺]

Hacker-News-Kommentare

• Es gibt ein paar Vorschläge: Den Prefix-String sollte man besser festlegen und dokumentieren, bevor es zu spät ist.
  In der Go-Implementierung sieht es mit kleingeschriebenem ASCII gut aus, aber bei zusammengesetzten Typen wie article-comment ist es etwas unklar.
  Komplexe Projekte oder ORMs können Trennzeichen kaum vermeiden, daher wäre es sinnvoll zu prüfen, ob ein einzelnes Trennzeichen erlaubt werden sollte.
  In der Go-Implementierung gibt es keine Tests; da sich der Code leicht per Unit-Tests prüfen lässt, sollte man sie unbedingt hinzufügen.
  In Go wäre es besser, wie bei Googles UUID-Implementierung eine saubere Parsing-Funktion und ein internes Byte-Array zu verwenden, und Strings nur für Rendering und Prefixe zu nutzen.
  Das aktuelle Parsing ist zu großzügig und scheint bei leerem Suffix in einen Erzeugungsmodus zu wechseln; außerdem dürfte die Indexierung nach SplitN panicen, wenn kein Unterstrich vorhanden ist.
  Am Design selbst wollte ich etwas aussetzen, aber am Ende scheint es den Sweet Spot der Trade-offs ziemlich gut zu treffen.

  • Für die kompliziertesten Teile wie die base32-Kodierung gibt es bereits Tests: https://github.com/jetpack-io/typeid-go/blob/main/base32/bas...
    Trotzdem ist der Hinweis berechtigt, und je mehr Implementierungen in verschiedenen Sprachen dazukommen, desto mehr müssen wir sicherstellen, dass sie miteinander kompatibel sind; deshalb planen wir, strengere Testsuiten hinzuzufügen.
    Was den Prefix betrifft, würde mich interessieren, ob die Sorge darin liegt, dass die erlaubte Zeichmenge in der Spezifikation nicht definiert ist.
  • Im README werden weitere Implementierungen angefragt, daher wäre eine Testsuite auch für Third-Party-Code nützlich.
  • Anschließend wurden recht gründliche Tests implementiert: https://github.com/jetpack-io/typeid-go/blob/main/typeid_tes...
    Außerdem wurde der Prefix in der Spezifikation klargestellt.
  • Ich werde versuchen, dafür Tests zu schreiben.
  • Es scheint ein Missverständnis zu geben, dass der Prefix fest vorgegeben sei.
    Der Prefix wird je nach Einsatzdomäne festgelegt.

• Ich verwende so einen Ansatz seit einigen Jahren, mit zwei Unterschieden.
  Erstens gehe ich nicht davon aus, dass Menschen die Werte tatsächlich von Hand eingeben, daher kümmere ich mich nicht besonders um die Verwechslung von l und 1.
  Stattdessen verwende ich base32 ohne die Vokale eiou, um die Wahrscheinlichkeit zu verringern, dass zufällig Wörter entstehen, insbesondere Schimpfwörter.
  Zweitens füge ich zwei base32-Zeichen mit Salt als Prüfsumme hinzu.
  So muss man bei fehlerhaften oder böswilligen Werten nicht erst den Datenspeicher abfragen; ich verstehe nicht, warum andere Implementierungen das nicht machen.

  • Vor ein paar Jahren wurde einmal analrita als automatisch generiertes Passwort ausgegeben, woraufhin sich jemand beschwert hat.
    Man könnte erwägen, auch a zu den ausgeschlossenen Zeichen hinzuzufügen.
  • Ich stimme dem Hinzufügen einer Prüfsumme zu, aber der Teil mit „fehlerhaft oder böswillig“ macht mich neugierig.
    Wenn man nicht davon ausgeht, dass Menschen die Werte von Hand eingeben, frage ich mich, über welchen Weg versehentlich falsche Werte überhaupt hineingeraten.
    Kopier-/Einfügefehler oder Fälle, in denen eine Seite alles in Großbuchstaben rendert, kann es natürlich geben, aber bei base32 könnte man Groß-/Kleinschreibung normalisieren.
    Außerdem würde mich interessieren, wie eine 2-Byte-Prüfsumme, die kryptografisch nicht sicher ist, im Fall von böswilliger Eingabe helfen soll.
  • Die Idee mit der Prüfsumme ist interessant.
    Wir prüfen gerade, ob sie in die TypeID-Spezifikation aufgenommen werden sollte.
  • Vor ein paar Monaten habe ich den zweiten Ansatz als Teil des Kodierungsverfahrens implementiert.
    Ich weiß nicht, wie viele Datenbankabfragen dadurch eingespart wurden, aber es ist angenehm zu sehen, dass man beim Dekodieren nicht in undeutlichere Fehlerzustände läuft.

• Unabhängig vom Haupttext gibt es noch einen Link zum „Crockford's alphabet“: https://www.crockford.com/base32.html
  Dieses Base32-Schema schließt aus den alphanumerischen Zeichen I und L aus, die mit 1 verwechselt werden, O, das mit 0 verwechselt wird, sowie U.
  Auf der Seite heißt es, der Grund für das Weglassen von U sei „versehentliche Obszönität“, aber ich verstehe ehrlich gesagt nicht, was damit gemeint ist.

  • Das hat Crockford scherzhaft geschrieben.
    Um aus nicht leicht verwechselbaren alphanumerischen Zeichen ein brauchbares Base32-Alphabet zu bauen, müsste man nur O, I und L weglassen.
    Dann bleiben aber noch 33 Zeichen übrig, also muss noch eines weg, und da es egal ist, welches, hat er dem letzten ausgeschlossenen Zeichen einfach einen willkürlichen Grund gegeben.
    Für IDs, die Nutzer zu Gesicht bekommen, ist das kein völlig abwegiger Grund, aber natürlich verhindert es überhaupt nichts perfekt.
  • Wenn man I und O bereits ausgeschlossen hat und dann auch noch U entfernt, kann man ziemlich viele grob wirkende Drei- oder Vierbuchstabenkombinationen vermeiden.
    Natürlich gibt es mit A weiterhin mögliche Kombinationen, aber die Wahrscheinlichkeit ist sehr gering.
  • Für einen echten Latinisten existierte U zu Ciceros Zeiten noch nicht und ist daher ein vulgärer Buchstabe, fast schon obszön.
  • Es gibt noch mehr davon: Base58 im Stil von Satoshi/Bitcoin https://en.wikipedia.org/wiki/Binary-to-text_encoding#Base58, „base62“ aus Keybases saltpack https://github.com/keybase/saltpack, das berühmte „Adobe 85“ https://en.wikipedia.org/wiki/Ascii85, basE91 https://base91.sourceforge.net
    Im Unternehmen haben wir mehrere neue „Basen“ für QR-Codes definiert; ich persönlich halte das für einen in der Informatik eher untergenutzten Bereich.
  • Etwa vier Jahre vor Crockford habe ich mir mit einem Kollegen fast denselben Zeichensatz ausgedacht.
    Wir arbeiteten an einem Problem mit URL-Slugs, und weil die ziemlich lang waren, hielten wir 5 Bit pro Byte für sinnvoll, um den Aufwand beim Abschreiben zu verringern.
    Am Ende hatten wir noch Spielraum, weitere Zeichen wegzulassen, und als alle anderen schon Feierabend hatten, saßen wir zu zweit da und ordneten Flüche nach ihrem Beleidigungsgrad, um zu entscheiden, welche Zeichen entfernt werden sollten.
    Später habe ich dann überzeugt, dass abwertende Bezeichnungen das größere Problem sind, und wir haben uns darauf konzentriert, statt u lieber n zu entfernen.
    tggr ist einfach nur niedlich, aber n**r hätte zu unangenehmen Gesprächen mit mehreren HR-Teams geführt.
    Der endgültige Zeichensatz ist inzwischen etwas verschwommen in meiner Erinnerung, aber normalerweise arbeiteten wir mit [a-z][0-9], und es gab viele Zeichen, die man nicht in URLs verwenden konnte oder die sich schlecht vorlesen ließen.
    Soweit ich mich erinnere, haben wir 0, l und 1 alle entfernt, und wir gingen davon aus, dass alles entweder komplett in Groß- oder komplett in Kleinbuchstaben abgeschrieben würde.
    0o war kein Problem, und 1L ebenso wenig.

• Crockford-Encoding gefällt mir nicht besonders.
  Wenn ich tatsächlich kodierte Werte dieser Art supporten oder analysieren musste, fühlte es sich wie ein offensichtlicher Fehler an.
  Dieses Alphabet wurde auf ein in der Praxis eher seltenes Ziel hin entworfen, nämlich Identifikatoren am Telefon vorzulesen, und führt dadurch Mehrdeutigkeit ein.
  Wenn man anhand des kodierten Strings selbst Logs grepen oder Querverweise herstellen will, ist das katastrophal, und die erlaubten Bindestriche sind zudem eine Hauptquelle für Copy-and-paste- und Zeilenumbruchfehler.
  Objektkennungen tippt man zwar nur selten direkt ein, aber man kopiert und fügt sie ständig zwischen Anwendungen, Chats und Foren ein, verschickt sie per E-Mail und sucht in Logdateien danach.
  Unter solchen Bedingungen ist Aussprechbarkeit bedeutungslos, Groß-/Kleinschreibungsinsensitivität eher hinderlich, und was man braucht, sind Konsistenz sowie Robustheit gegenüber Einfügen und Zeilenumbrüchen.
  base58 ist dafür eine deutlich besser passende bijektive Kodierung und sogar noch kürzer.
  Von Stripe inspiriert verwende ich seit Jahren Base58-kodierte UUIDs mit Typ-Präfixen wie user_1BzGURpnHGn6oNru84B3Ri als Objektkennungen.
  Man sollte allerdings berücksichtigen, dass Douglas Crockfords Base32-Kodierung vor 20 Jahren entworfen wurde, in einer Zeit mit recht anderen Einsatzbedingungen.

  • Ich habe auch über base58 oder base64url nachgedacht, und die kürzere Kodierung gefiel mir durchaus.
    Ich wollte mich aber letztlich nicht auf Groß-/Kleinschreibung verlassen, daher tendierte ich am Ende eher zu base32.
    Es kann zum Beispiel sein, dass man IDs als Dateinamen verwenden möchte und dabei an eine Umgebung mit case-insensitivem Dateisystem gebunden ist.
    TypeID verwendet nur das Crockford-Alphabet immer in Kleinbuchstaben, nicht das vollständige Crockford-Encoding-Regelwerk.
    In TypeID sind Bindestriche nicht erlaubt, und es ist auch nicht erlaubt, dieselbe ID auf mehrere Arten zu kodieren, indem man mehrdeutige Zeichen anders schreibt.
  • Ich stimme zu, dass man Identifikatoren nur selten am Telefon vorliest.
    Aber es kommt gelegentlich vor, dass man Kennungen aus Screenshots oder Screen-Sharing eingeben muss oder von einem anderen Gerät, auf dem sich die Kennung nicht leicht übernehmen lässt.
  • base58 oder das von KSUID verwendete base62 haben viele Vorteile.
    Crockford-Base32 funktioniert zwar, überzeugt mich aber auch nicht völlig.
    Persönlich wäre meine erste Wahl ein KSUID mit Typ-Präfix.
    Damit bekommt man eine 160-Bit-K-sortierbare ID in Base62-Kodierung, und solange man nicht aus Kompatibilitätsgründen unbedingt eine 128-Bit-ID braucht, passt das sehr gut.
  • Ich weiß nicht, wo bei Crockford Base32 die Bindestriche herkommen sollen: https://en.wikipedia.org/wiki/Base32#Crockford's_Base32
    Meine bevorzugte base32-Kodierung ist z-base-32, die ich augenfreundlicher finde: https://philzimmermann.com/docs/human-oriented-base-32-encod...
    Das größte Problem von base58 ist, dass es sich gut für Ganzzahlen eignet, aber weniger für beliebige Binärdaten wie kryptografische Schlüssel, und dass Zeichenketten mit Groß-/Kleinschreibung nicht besonders gut aussehen.

• Sauber
  Mir gefällt das Prefix für „Typensicherheit“.
  In unserem ORM nannten wir eine ähnliche Methode, bei der automatisch entity-spezifische Tags an Integer-IDs in der DB angehängt werden, tagged ids: https://joist-orm.io/docs/advanced/tagged-ids
  Wir haben : als Trennzeichen verwendet, aber im Hinblick auf Copy-and-Paste per Doppelklick bereue ich ein wenig, nicht _ genommen zu haben.
  Theoretisch wäre es für Joist wohl auch sehr einfach, eine „UUID-Spalte in der DB“ in eine „TypeID im Domain-Modell“ umzuwandeln, aber aktuell scheint das nicht allein über Konfiguration im User-Bereich möglich zu sein.
  Trotzdem eine gute Idee.

  • Reddit ist ähnlich, verwendet aber ein für die Stringlänge optimiertes Format.
    Element-IDs sehen etwa so aus: t3_15bfi0, wobei t3_ das Typ-Prefix ist.
    t3 steht für Beiträge, t1 für Kommentare, t5 für Subreddits, und der Rest ist eine Base36-Codierung des autoinkrementierenden Primärschlüssels.
  • Das typisierte interne ID-System in unserer Firma nutzte anfangs Doppelpunkte als Trennzeichen, wechselte aber bald zu Punkten (.).
    Doppelpunkte wurden in der URL-Codierung zu %-Escapes, wodurch die IDs länger wurden und die URLs hässlich und lang aussahen, was extrem nervig war.

• UUIDv7 ist auf HN seit Jahren beliebt, und ich frage mich, wann es zu einem echten Standard wird und wann Libraries, Datenbanken und der Rest des Ökosystems es nativ unterstützen werden.

  • Ich weiß nicht, welche Art von Unterstützung du erwartest.
    Die meiste Software kümmert sich nicht um bestimmte Bits innerhalb einer UUID, also kann man sie auch heute schon verwenden.
    Falls es Software gibt, die sich für bestimmte Bits interessiert, kann man sie einfach wie UUIDv4 aussehen lassen, und auch solche Bits können zufällig erzeugt werden.
    Wenn ein Erzeugungsverfahren nötig ist, kann man es selbst schreiben; das ist nicht schwer.
  • Es scheint sich bei der IETF in der letzten Phase der Standardisierung zu befinden: https://datatracker.ietf.org/doc/draft-ietf-uuidrev-rfc4122b...
  • Es hat Entwürfe und Verbesserungen durchlaufen, ist der Standardisierung sehr nahe und viele Libraries unterstützen es bereits oder fügen die neuen Features hinzu.
    Ich betreue zum Beispiel die Dart-UUID-Library, und im neuesten Beta-Major-Release sind v6, v7 und benutzerdefinierte v8 enthalten.
    Irgendwo gibt es auch eine Implementierungsliste, und ich stehe auf dieser Seite als Library-Maintainer, sodass ich benachrichtigt werde, wenn ein neuer Draft erscheint.

• Mir gefällt der Teil mit „per Doppelklick kopieren/einfügen“.
  Details sind wichtig.

• Ich habe ein paar Beschwerden über UUIDs.
  Ich verstehe nicht, warum man nicht einfach Zeit + Zufall kombinieren kann, statt dieses ganze Ritual um UUID-Versionierung zu betreiben.
  Wenn Lokalität nicht wichtig ist, kann man einfach direkt 128 Bit Zufallsdaten verwenden.
  Meiner Erfahrung nach glauben die meisten Leute, UUIDs müssten in ihrer menschenlesbaren hexadezimalen Darstellung gespeichert werden, sogar mit Bindestrichen.
  Das verschwendet in Datenbanken, Netzwerken und im Speicher viel zu viel Platz.

  • Das haben viele Leute genauso gesehen.
    Zum Beispiel ist ULID https://github.com/ulid/spec kürzer, speichert Zeit und ist lexikografisch sortierbar.
  • Im UUID-Umfeld wird oft so getan, als stünde ein einzelner Use Case für alles und als gäbe es deshalb genau ein bestes UUID-Format.
    In Wirklichkeit ist es wie bei anderen Engineering-Problemen auch: Man schreibt die Anforderungen auf und schaut, was sie erfüllt.
    Es ist hilfreich, über die Vorteile verschiedener Formate zu lesen, weil man dadurch von dem profitiert, was andere mühsam gelernt haben.
    Sortierbarkeit und zeitbasierte Lokalität kommen einem nicht unbedingt von selbst in den Sinn, aber wenn man sie braucht, ist es viel besser, das vorher zu wissen, als vier Jahre später im Projekt festzustellen, dass man diese Daten weggeworfen hat.
    Manche UUID-Formate haben sich auch kleine Sicherheitsprobleme selbst eingebaut; Dinge wie das Leaken der MAC-Adresse bei UUID v1 sollte man besser vermeiden.
    Wenn eine bestehende Lösung für den passenden Use Case richtig ist, dann nutze sie einfach.
    Wenn nicht, muss man sich auch keine allzu großen Sorgen machen.
    Persönlich habe ich dort, wo ich UUIDs am häufigsten benutze, einfach festgelegt: „Schickt einfach irgendeinen eindeutigen String; wenn es euch ein gutes Gefühl gibt, benutzt die UUID-Library eurer Wahl.“
    In diesem System scheint es je nach Datenquelle unterschiedliche eindeutige Formate zu geben, aber das ist in Ordnung.
    Wir liegen nur bei einigen Zehntausend Vorgängen pro Tag, also gibt es auch kein Skalierungsproblem, und niemand muss nach UUID sortieren.
    Es ist weniger eine echte Kennung als ein eindeutiges Token, das der Sender pro Nachricht erzeugt, um in einem heterogenen System mit mehreren Queues doppelt eintreffende Nachrichten nachgelagert zu erkennen.
    Es muss nicht einmal global eindeutig sein, sondern nur innerhalb eines kleinen Shards, und prinzipiell wäre es auch in Ordnung, wenn es sich im Lauf der Zeit wiederholt.
    Der Einfachheit halber halten wir das System aber über die gesamte Laufzeit hinweg eindeutig.
    Wenn wir sie selbst erzeugen, lesen wir Daten aus /dev/urandom und kodieren sie als Base64; dabei haben wir eine Größe gewählt, die nicht auf == endet.
    Auch das war kein echtes Problem, sondern nur eine Frage der Ästhetik.
  • Zeit und Zufall zu kombinieren garantiert keine globale Eindeutigkeit.
  • Für mich ist der einzig wirklich wertvolle UUID-Standard v4, also einfach Zufall.
    Trotzdem verstehe ich immer noch nicht, warum die Bindestriche nötig sind, und die anderen Versionen halte ich für wenig sinnvoll.
  • Das Schlimmste an Bindestrichen ist, dass man nicht einfach die ganze UUID per Doppelklick kopieren/einfügen kann.

• Wenn UUIDv7 oder UUID nicht zwingend erforderlich sind, bietet https://github.com/segmentio/ksuid einen deutlich größeren Schlüsselraum
  Wenn ein Namespace benötigt wird, kann man einfach einen String-Präfix anhängen, und die Wahrscheinlichkeit einer KSUID-Kollision ist viel geringer als bei jeder UUID-Version
  Unter den universellen ID-Generatoren mit sortierbarem Zeitstempel war ksuid für mich am besten, und es gibt Bibliotheken für die meisten Sprachen
  UUID v1~v7 sind verschwenderisch

  • Ich habe ein schlankes JavaScript-Paket veröffentlicht, das KSUIDs mit Typ-Präfix erzeugt
    Wenn man sich die zusätzlichen Bits leisten kann, was meistens der Fall sein dürfte, ist KSUID ein hervorragendes Format
    [1] https://github.com/sophiabits/resource-id
  • Der Grund für den Wechsel zu ULID war, dass es immer kleingeschrieben ist und sich daher ohne Unterscheidung von Groß- und Kleinschreibung behandeln lässt
  • Ich pflege einige populäre ksuid-Bibliotheken, mag ksuid und nutze es auch tatsächlich
    Das große Problem von ksuid ist allerdings, dass es 160 Bit hat und deshalb nicht zu nativen UUID-Typen in Datenbanken wie PostgreSQL passt, was Performance-Kosten verursacht
    1: https://github.com/svix/rust-ksuid
    2: https://github.com/svix/python-ksuid

• K-sortierbar ist ein großartiges Konzept, und schwach sortierte Schlüssel lösen viele Anwendungsfälle
  Auch die typisierte kompakte String-Darstellung gefällt mir
  Ich frage mich allerdings, ob der unbeabsichtigte Nebeneffekt von UUID v7 viele Sicherheitsprobleme verursachen wird
  Man sollte UUIDs weder als Token noch als Primärschlüssel der DB verwenden, aber in der Praxis wird genau das getan
  UUID v4 ist praktisch kryptografischer Zufall, daher sind viele Sicherheitslücken bisher wohl eher zufällig glimpflich ausgegangen
  Ich dachte bei UUID v7, dass die tatsächlichen Zufallsdaten auf 32 Bit hinauslaufen, und meinte, man müsse Entwickler stärker darauf hinweisen, dass UUIDs vorhersagbar sein können
  Korrektur: Offenbar habe ich mich bei der Vorhersagbarkeit von v7-UUIDs geirrt
  Im Entwurf wird für die Zufallsbits ein CSPRNG empfohlen, die Entropie beträgt mindestens 74 Bit und sie sind so ausgelegt, dass sie „nicht vorhersagbar“ sind
  Für sicherheitsrelevante Zwecke wird zwar empfohlen, „UUID v4“ zu verwenden, aber das könnte sich vermutlich auf die Bedeutung des Zeitstempels beziehen

  • Es gibt ein interessantes Usability-Problem
    Wenn die Namen UUIDv4 und UUIDv7 lauten, führt das dann nicht zu endloser Verwirrung darüber, welches für Datenbanken gut ist und welches für Einmal-Token?
    Mir ist auch keine gute rückwärtskompatible Lösung bekannt
    In Elixir verwendet man für das Erzeugen einer v4-UUID die Funktion UUID.uuid4()
    Theoretisch könnte man den Code nach Verwendungen durchsuchen, aber all das erhöht die Fehleranfälligkeit
  • Ich sehe durchaus einige sinnvolle Einsatzfälle, aber jedes Mal, wenn ich früher teilweise sequentielle UUIDs wie v1 oder v5 gesehen habe, wurden sie missbraucht
    Dasselbe galt für hashbasierte Varianten wie v3
    v4 ist einfach und weniger anfällig für Missbrauch