KSUID-generator - Skapa sorteringsbara unika identifierare

KSUID-generator

En KSUID (K-Sortable Unique Identifier) är en kod på 27 tecken som används för att märka poster som databasrader, loggposter eller API-förfrågningar. Den kombinerar en tidsstämpel med slumpdata, så ID:n som skapas senare alltid sorteras efter ID:n som skapades tidigare, även om varje ID fortfarande i praktiken är unikt. Det här verktyget genererar en enda KSUID i webbläsaren och låter användaren kopiera den.

Vad består en KSUID av?

En KSUID är 20 byte lång och uppdelad i två delar:

• Tidsstämpel (4 byte): antalet sekunder sedan en fast startpunkt som kallas KSUID-epoken.
• Slumpmässig nyttolast (16 byte): data som skapas av webbläsarens kryptografiska slumptalsgenerator.

Dessa 20 byte omvandlas sedan till text med base62-kodning, ett system som representerar tal med 62 tecken: siffrorna 0-9, versalerna A–Z och gemenerna a–z. Resultatet fylls alltid ut till exakt 27 tecken, till exempel 0qjBBlJIfbVLKwnJn4xpLGDr00e.

Eftersom tidsstämpeln kommer först sorteras två KSUID:er som skapats med en sekunds mellanrum normalt i samma ordning som de skapades när de jämförs som vanlig text. Eftersom de sista 16 byten är slumpmässiga är det fortfarande nästan säkert att två KSUID:er som skapats under samma sekund skiljer sig åt.

KSUID-epok

De flesta datorsystem räknar tid i sekunder sedan 1 januari 1970 (”Unix-epoken”). KSUID använder en annan startpunkt, KSUID-epoken: 1 400 000 000 sekunder efter Unix-epoken, vilket är 13 maj 2014, 16:53:20 UTC.

En senare startpunkt gör att tidsstämpelfältet på 4 byte kan täcka fler användbara år innan utrymmet tar slut. En räknare på 4 byte (32 bitar) kan rymma högst 4 294 967 295 sekunder. Räknat från KSUID-epoken räcker den tidsperioden till omkring 19 juni 2150.

KSUID-formeln

En KSUID-sträng byggs i tre steg.

1. Hitta tidsstämpelvärdet:

   T = floor(current_unix_time_in_seconds) − 1,400,000,000

2. Generera 16 slumpmässiga byte, R, med en kryptografiskt säker slumptalsgenerator.

3. Slå ihop tidsstämpeln på 4 byte och de 16 slumpmässiga byten till ett block på 20 byte och koda sedan blocket i base62. Fyll ut resultatet till 27 tecken:

   KSUID = Base62( T ‖ R )

Här betyder ‖ ”placera den ena efter den andra”. Tidsstämpelbyten kommer alltid först, vilket gör att den slutliga strängen sorteras korrekt efter tid.

Löst exempel

Anta att tidsstämpeldelen av en KSUID är 100000000. Eftersom KSUID-epoken infaller 1 400 000 000 sekunder efter Unix-epoken motsvarar denna tidsstämpel 14 juli 2017, 02:40:00 UTC.

Kombinera den tidsstämpeln med sekvensen på 16 byte 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 (som här används enbart för att göra exemplet reproducerbart; en verklig generator använder slumpmässiga byte), så ger base62-kodningen:

0qjBBlJIfbVLKwnJn4xpLGDr00e

Den strängen är 27 tecken lång, består enbart av siffror och bokstäver och kan användas direkt i en URL eller ett filnamn.

Så använder du KSUID-generatorverktyget

1. Öppna sidan för KSUID-generatorn.
2. Välj knappen ”Generate KSUID”.
3. Verktyget skapar en ny KSUID med aktuell tid och nya slumpmässiga byte och visar den på sidan.
4. Välj knappen ”Copy KSUID” för att kopiera värdet till urklipp.
5. Välj ”Reset” för att rensa resultatet. Knappen Reset visas endast efter att en KSUID har genererats.

Varje klick på ”Generate KSUID” skapar exakt en identifierare. Om flera KSUID:er ska skapas klickar du på knappen igen för varje ny identifierare; verktyget har inget inbyggt batchläge eller någon funktion för filexport.

Generatorn använder Web Crypto API, som finns inbyggt i moderna webbläsare. Om API:et inte är tillgängligt visar verktyget ett fel i stället för att skapa ett ID, eftersom en slumptalsgenerator som inte är kryptografiskt säker kan skapa identifierare som är lättare att gissa eller som kolliderar.

KSUID jämfört med UUID

En UUID (Universally Unique Identifier) är ett vanligt alternativt identifierarformat. Den mest använda versionen, UUID v4, är 36 tecken lång och består nästan helt av slumpmässiga bitar, så två UUID:er ger ingen ledtråd om vilken som skapades först.

En KSUID skiljer sig på tre sätt:

• Sorterbar efter tid. De inledande tidsstämpelbyten gör att alfabetisk sortering av KSUID-strängar också sorterar dem efter när de skapades.
• Kortare. En KSUID består av 27 tecken, jämfört med 36 för en standard-UUID.
• Inga avgränsare. En UUID skrivs normalt med bindestreck (xxxxxxxx-xxxx-...); en KSUID har inga.

Båda formaten kan genereras oberoende på olika datorer utan kontakt med en central server, så båda undviker flaskhalsen med en autoinkrementerande räknare i en delad databas.

Vanliga frågor och svar

Vad står KSUID för? K-Sortable Unique Identifier. ”K” syftar på att identifieraren kan sorteras (”kind of sortable” i de ursprungliga designanteckningarna från Segment, företaget som skapade formatet).

Hur lång är en KSUID? 27 tecken, kodade med base62 (siffrorna 0-9, versaler och gemener).

Vad är KSUID-epoken? 13 maj 2014, 16:53:20 UTC, vilket är 1 400 000 000 sekunder efter Unix-epokens standardstart 1 januari 1970.

Kan två KSUID:er kollidera? Det är extremt osannolikt. Varje KSUID innehåller 16 slumpmässiga byte (128 bitar), som genereras med en kryptografiskt säker slumptalsgenerator. Även om många KSUID:er genereras under samma sekund är sannolikheten astronomiskt liten att två av en slump blir identiska.

Kan jag återställa skapandetiden från en KSUID? Ja. De första 4 byten i det avkodade värdet är tidsstämpeln. Läggs det antalet sekunder till KSUID-epoken får man den ursprungliga skapandetiden.

Har det här verktyget stöd för att generera många KSUID:er samtidigt? Nej. Verktyget genererar en KSUID per klick på knappen ”Generate KSUID”. Det finns inget fält för antal, inget fält för en anpassad tidsstämpel och ingen funktion för export eller nedladdning.

Är det säkert att placera en KSUID i en URL? Ja. Base62-kodning använder endast siffror och bokstäver, så en KSUID behöver inte kodas om för att förekomma i en URL, ett filnamn eller en databasnyckel.

Referenser

1. Segments KSUID-repositorium på GitHub: https://github.com/segmentio/ksuid
2. "Generating good unique identifiers" av Peter Bourgon: https://peter.bourgon.org/blog/2019/05/20/generating-good-unique-ids.html