KSUID Generator - Stvaranje sortabilnih jedinstvenih identifikatora

Generator KSUID-ova

KSUID (K-Sortable Unique Identifier) kod je od 27 znakova koji se upotrebljava za označavanje zapisa kao što su redci baze podataka, zapisi dnevnika ili zahtjevi API-ja. Kombinira vremensku oznaku sa slučajnim podacima pa se ID-ovi izrađeni kasnije uvijek razvrstavaju nakon ID-ova izrađenih ranije, iako je svaki od njih i dalje praktički jedinstven. Ovaj alat generira jedan KSUID u pregledniku i omogućuje korisniku njegovo kopiranje.

Od čega se sastoji KSUID?

KSUID je dug 20 bajtova i podijeljen je na dva dijela:

• Vremenska oznaka (4 bajta): broj sekundi od fiksne početne točke koja se naziva KSUID epoha.
• Nasumični sadržaj (16 bajtova): podaci koje generira kriptografski generator slučajnih brojeva u pregledniku.

Tih 20 bajtova zatim se pretvara u tekst kodiranjem base62, sustavom koji prikazuje brojeve pomoću 62 znakova: znamenki 0-9, velikih slova A–Z i malih slova a–z. Rezultat se uvijek dopunjava do točno 27 znakova, na primjer 0qjBBlJIfbVLKwnJn4xpLGDr00e.

Budući da vremenska oznaka dolazi prva, dva KSUID-a izrađena u razmaku od jedne sekunde pri usporedbi kao običan tekst obično će se razvrstati istim redoslijedom kao i njihova vremena izrade. Budući da je posljednjih 16 bajtova slučajno, dva KSUID-a izrađena u istoj sekundi gotovo će sigurno biti različita.

KSUID epoha

Većina računalnih sustava računa vrijeme u sekundama od 1. siječnja 1970. (»Unix epoha«). KSUID-ovi upotrebljavaju drugu početnu točku, KSUID epohu: 1.400.000.000 sekundi nakon Unix epohe, što je 13. svibnja 2014. u 16:53:20 UTC.

Kasnija početna točka omogućuje da polje vremenske oznake od 4 bajta obuhvati više korisnih godina prije nego što se popuni. Brojač od 4 bajta (32 bita) može sadržavati najviše 4.294.967.295 sekundi. Računajući od KSUID epohe, to se vremensko razdoblje završava oko 19. lipnja 2150..

Formula KSUID-a

Niz KSUID gradi se u tri koraka.

1. Odredite vrijednost vremenske oznake:

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

2. Generirajte 16 slučajnih bajtova, R, pomoću kriptografski sigurnog generatora slučajnih brojeva.

3. Spojite vremensku oznaku od 4 bajta i 16 slučajnih bajtova u jedan blok od 20 bajtova, a zatim taj blok kodirajte base62 kodiranjem i dopunite rezultat do 27 znakova:

   KSUID = Base62( T ‖ R )

Ovdje ‖ znači »staviti jedno iza drugoga«. Bajtovi vremenske oznake uvijek dolaze prvi, zbog čega se konačni niz ispravno razvrstava prema vremenu.

Primjer s rješenjem

Pretpostavimo da je dio vremenske oznake KSUID-a 100000000. Budući da je KSUID epoha 1.400.000.000 sekundi nakon Unix epohe, ta vremenska oznaka predstavlja 14. srpnja 2017. u 02:40:00 UTC.

Uparivanjem te vremenske oznake sa slijedom od 16 bajtova 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 (koji se ovdje upotrebljava samo radi ponovljivosti primjera; stvarni generator umjesto toga upotrebljava slučajne bajtove) base62 kodiranjem dobiva se:

0qjBBlJIfbVLKwnJn4xpLGDr00e

Taj niz ima 27 znakova, sastoji se samo od znamenki i slova te se može izravno upotrebljavati u URL-u ili nazivu datoteke.

Kako upotrebljavati alat za generiranje KSUID-ova

1. Otvorite stranicu generatora KSUID-ova.
2. Odaberite gumb »Generate KSUID«.
3. Alat stvara jedan novi KSUID koristeći trenutačno vrijeme i nove slučajne bajtove te ga prikazuje na stranici.
4. Odaberite gumb »Copy KSUID« da biste vrijednost kopirali u međuspremnik.
5. Odaberite »Reset« da biste izbrisali rezultat. Gumb Reset pojavljuje se tek nakon generiranja KSUID-a.

Svaki klik na »Generate KSUID« proizvodi točno jedan identifikator. Da biste stvorili nekoliko KSUID-ova, ponovno kliknite gumb za svaki novi; alat nema ugrađen skupni način rada ni izvoz u datoteku.

Generator se oslanja na Web Crypto API ugrađen u moderne preglednike. Ako taj API nije dostupan, alat prikazuje pogrešku umjesto da proizvede ID jer generator slučajnih brojeva koji nije kriptografski siguran može proizvesti identifikatore koje je lakše pogoditi ili koji se mogu podudarati.

KSUID u usporedbi s UUID-om

UUID (Universally Unique Identifier) uobičajen je alternativni format identifikatora. Najčešće upotrebljavana inačica, UUID v4, duga je 36 znakova i gotovo se u potpunosti sastoji od slučajnih bitova, pa dva UUID-a ne daju nikakav podatak o tome koji je od njih prvi stvoren.

KSUID se razlikuje na tri načina:

• Razvrstavanje prema vremenu. Početni bajtovi vremenske oznake znače da se običnim abecednim razvrstavanjem nizova KSUID-a oni razvrstavaju i prema vremenu izrade.
• Kraći je. KSUID ima 27 znakova, u usporedbi s 36 znakova standardnog UUID-a.
• Nema razdjelnika. UUID se obično zapisuje s crticama (xxxxxxxx-xxxx-...), a KSUID ih nema.

Oba se formata mogu generirati neovisno na različitim računalima bez provjere sa središnjim poslužiteljem pa se oba izbjegavaju usko grlo brojača s automatskim povećavanjem u zajedničkoj bazi podataka.

Često postavljana pitanja

Što znači KSUID? K-Sortable Unique Identifier. Slovo »K« odnosi se na činjenicu da se može razvrstavati (»kind of sortable« u izvornim bilješkama o dizajnu tvrtke Segment, koja je stvorila taj format).

Koliko je dug KSUID? 27 znakova, kodiranih pomoću base62 kodiranja (znamenke 0-9, velika slova, mala slova).

Što je KSUID epoha? 13. svibnja 2014. u 16:53:20 UTC, što je 1.400.000.000 sekundi nakon standardne Unix epohe 1. siječnja 1970..

Mogu li se dva KSUID-a podudarati? To je iznimno malo vjerojatno. Svaki KSUID sadržava 16 slučajnih bajtova (128 bitova), generiranih kriptografski sigurnim generatorom slučajnih brojeva. Čak i generiranje velikog broja KSUID-ova u istoj sekundi ostavlja astronomski malu vjerojatnost da se dva slučajno podudare.

Mogu li iz KSUID-a dobiti vrijeme izrade? Da. Prva 4 bajta dekodirane vrijednosti predstavljaju vremensku oznaku. Dodavanjem tog broja sekundi KSUID epohi dobiva se izvorno vrijeme izrade.

Podržava li ovaj alat generiranje više KSUID-ova odjednom? Ne. Alat generira jedan KSUID po kliku na gumb »Generate KSUID«. Ne postoji unos količine, polje za prilagođenu vremensku oznaku ni mogućnost izvoza ili preuzimanja.

Može li se KSUID sigurno staviti u URL? Da. Base62 kodiranje upotrebljava samo znamenke i slova pa za KSUID nije potrebno dodatno escapiranje kada se pojavljuje u URL-u, nazivu datoteke ili ključu baze podataka.

Reference

1. Segmentovo GitHubovo spremište KSUID-a: https://github.com/segmentio/ksuid
2. "Generating good unique identifiers" autora Petera Bourgona: https://peter.bourgon.org/blog/2019/05/20/generating-good-unique-ids.html