Γεννήτρια ULID

Τι είναι ένα ULID;

Ένα ULID (Universally Unique Lexicographically Sortable Identifier, δηλαδή καθολικά μοναδικό λεξικογραφικά ταξινομήσιμο αναγνωριστικό) είναι ένας κωδικός 26 χαρακτήρων που χρησιμοποιείται για την επισήμανση εγγραφών σε μια βάση δεδομένων ή ενός συμβάντος σε ένα κατανεμημένο σύστημα. Συνδυάζει την τρέχουσα χρονική στιγμή με τυχαία δεδομένα, έτσι ώστε μια λίστα ULID ταξινομημένη αλφαβητικά να καταλήγει ταξινομημένη με βάση τον χρόνο δημιουργίας τους. Μια γεννήτρια ULID είναι ένα εργαλείο που παράγει αυτούς τους κωδικούς.

Δομή ULID

Ένα ULID έχει δύο μέρη, τα οποία γράφονται διαδοχικά χωρίς διαχωριστικό:

Χρονοσφραγίδα (10 χαρακτήρες): ο αριθμός των χιλιοστών του δευτερολέπτου από την 1 Ιανουαρίου 1970 (την εποχή Unix), με εύρος έως 48 bit.
Τυχαιότητα (16 χαρακτήρες): 80 bit τυχαίων δεδομένων, ώστε δύο ULID που δημιουργούνται στο ίδιο χιλιοστό του δευτερολέπτου να είναι σχεδόν σίγουρα διαφορετικά.

Και τα δύο μέρη γράφονται με το αλφάβητο Base32 του Crockford: τα ψηφία 0–9 και τα γράμματα A-Z, εκτός από τα I, L, O και U. Αυτά τα τέσσερα γράμματα παραλείπονται επειδή μπορεί να συγχέονται με τα ψηφία 0 και 1 ή μεταξύ τους. Το αποτέλεσμα είναι μια συμβολοσειρά σύντομη, ευανάγνωστη όταν εκφωνείται και ασφαλής για άμεση τοποθέτηση σε URL.

Πώς υπολογίζεται ένα ULID

Μια γεννήτρια ULID δημιουργεί ένα αναγνωριστικό σε τρία βήματα.

Ανάγνωση της τρέχουσας ώρας σε χιλιοστά του δευτερολέπτου από την εποχή Unix. Πρόκειται για αριθμό 48 bit.
Δημιουργία 80 bit τυχαίων δεδομένων, συνήθως από κρυπτογραφικά ασφαλή γεννήτρια τυχαίων αριθμών, που δίνει 10 τυχαία byte.
Ξεχωριστή κωδικοποίηση των δύο μερών με το αλφάβητο Base32 του Crockford: η χρονοσφραγίδα των 48 bit γίνεται 10 χαρακτήρες και η τυχαία τιμή των 80 bit γίνεται 16 χαρακτήρες. Οι δύο κωδικοποιημένες συμβολοσειρές ενώνονται για να σχηματίσουν το τελικό ULID των 26 χαρακτήρων.

Η κωδικοποίηση λειτουργεί διαβάζοντας τον αριθμό ανά 5 bit, επειδή κάθε χαρακτήρας Base32 αντιπροσωπεύει μία από 32 πιθανές τιμές (2^5 = 32). Δέκα χαρακτήρες περιέχουν έως 50 bit, αρκετά για τη χρονοσφραγίδα των 48 bit. Δεκαέξι χαρακτήρες περιέχουν ακριβώς 80 bit, όσα αντιστοιχούν στο τμήμα της τυχαιότητας, χωρίς υπόλοιπο.

Λυμένο παράδειγμα

Ας υποθέσουμε ότι μια γεννήτρια ULID εκτελείται στη χρονική στιγμή 1712345678901 (χιλιοστά του δευτερολέπτου από την εποχή) και λαμβάνει τα τυχαία byte [12, 240, 88, 3, 199, 45, 6, 231, 128, 17].

Βήμα 1 – κωδικοποίηση της χρονοσφραγίδας. Διαιρούμε επανειλημμένα το 1712345678901 με το 32, κρατώντας κάθε φορά το υπόλοιπο και διαβάζοντας τα ψηφία από το τελευταίο προς το πρώτο (αυτή είναι η τυπική μετατροπή βάσης). Έτσι προκύπτει η συμβολοσειρά 10 χαρακτήρων 01HTQW311N.

Βήμα 2 – κωδικοποίηση της τυχαιότητας. Συσκευάζουμε τα 10 τυχαία byte σε ροή 80 bit και στη συνέχεια διαβάζουμε ανά 5 bit, μετατρέποντας κάθε τμήμα 5 bit σε χαρακτήρα Base32. Έτσι προκύπτει η συμβολοσειρά 16 χαρακτήρων 1KR5G0Y75M3EF00H.

Βήμα 3 – ένωση των μερών. Το τελικό ULID είναι:

101HTQW311N 1KR5G0Y75M3EF00H
2

γραμμένο χωρίς το κενό: 01HTQW311N1KR5G0Y75M3EF00H, συνολικά 26 χαρακτήρες.

Χρήση αυτής της γεννήτριας

Η γεννήτρια εκτελείται στο πρόγραμμα περιήγησης. Κάθε ULID δημιουργείται από το ρολόι του προγράμματος περιήγησης και 80 νέα τυχαία bit που λαμβάνονται από την κρυπτογραφική γεννήτρια τυχαίων αριθμών του προγράμματος περιήγησης, επομένως κανένα αναγνωριστικό δεν αποστέλλεται σε διακομιστή ούτε ανακτάται από αυτόν.

Αριθμός ULID δέχεται έναν ακέραιο αριθμό από 1 έως 50. Η προεπιλογή είναι 1.
Δημιουργία ULID παράγει μια νέα ομάδα. Η αλλαγή του αριθμού παράγει επίσης νέα ομάδα.
Η επιλογή Αντιγραφή σε ένα αποτέλεσμα αντιγράφει το συγκεκριμένο ULID. Όταν εμφανίζονται περισσότερα από ένα, η επιλογή Αντιγραφή όλων αντιγράφει ολόκληρη τη λίστα, ένα ULID ανά γραμμή.
Η επιλογή Επαναφορά επαναφέρει τον αριθμό σε 1 και δημιουργεί ένα νέο ULID.

Κάτω από τα αποτελέσματα, το πλαίσιο Δομή ULID χωρίζει το πρώτο ULID της ομάδας στα δύο μέρη του: τους πρώτους 10 χαρακτήρες (τη χρονοσφραγίδα) και τους τελευταίους 16 (την τυχαιότητα).

ULID έναντι UUID

Χαρακτηριστικό	ULID	UUID (έκδοση 4)
Μήκος	26 χαρακτήρες	36 χαρακτήρες (με ενωτικά)
Ταξινομήσιμο κατά χρόνο δημιουργίας	Ναι	Όχι
Κωδικοποίηση	Crockford Base32	Δεκαεξαδικό
Περιέχει χρονοσφραγίδα	Ναι (48 bit)	Όχι
Ασφαλές για URL χωρίς διαφυγή χαρακτήρων	Ναι	Ναι

Και οι δύο μορφές αποσκοπούν στη δημιουργία αναγνωριστικών που είναι μοναδικά σε διαφορετικά συστήματα, χωρίς μια κεντρική αρχή να εκχωρεί αριθμούς. Η βασική πρακτική διαφορά είναι η ταξινόμηση: επειδή ένα ULID αρχίζει με χρονοσφραγίδα, η ταξινόμηση των ULID ως απλού κειμένου τα ταξινομεί επίσης χρονικά. Ένα τυχαίο UUID δεν έχει αυτή την ιδιότητα, επειδή κάθε τμήμα του είναι τυχαίο.

Συνήθεις χρήσεις

Πρωτεύοντα κλειδιά βάσεων δεδομένων: τα ULID επιτρέπουν σε μια βάση δεδομένων να δημιουργεί ευρετήριο για τις νέες γραμμές περίπου με τη σειρά εισαγωγής τους, κάτι που πολλές μηχανές βάσεων δεδομένων διαχειρίζονται αποδοτικότερα από πλήρως τυχαία κλειδιά.
Κατανεμημένα συστήματα: ξεχωριστοί διακομιστές μπορούν να δημιουργούν ULID ανεξάρτητα, χωρίς συντονισμό με έναν κεντρικό μετρητή, και τα αποτελέσματα παραμένουν σχεδόν σίγουρα μοναδικά.
Αρχεία συμβάντων: επειδή τα ULID ταξινομούνται χρονικά, μια λίστα αναγνωριστικών συμβάντων μπορεί να λειτουργεί και ως κατά προσέγγιση χρονολόγιο.
Αναγνωριστικά API και αρχείων: η σταθερή μορφή των 26 χαρακτήρων, ασφαλής για URL, λειτουργεί καθαρά σε διευθύνσεις ιστού και ονόματα αρχείων.

Στις σχετικές μορφές αναγνωριστικών περιλαμβάνονται τα KSUID, τα οποία επίσης κωδικοποιούν χρονοσφραγίδα για ταξινόμηση, και τα αναγνωριστικά Snowflake, που χρησιμοποιούνται από το Twitter και άλλους και συνδυάζουν χρονοσφραγίδα, αναγνωριστικό μηχανήματος και μετρητή.

Παραδείγματα κώδικα

Κάθε παράδειγμα παρακάτω δημιουργεί ένα ULID με τον ίδιο τρόπο που περιγράφεται στην προδιαγραφή ULID: κωδικοποιεί τη χρονοσφραγίδα των 48 bit ως 10 χαρακτήρες Crockford Base32, κωδικοποιεί 80 bit τυχαιότητας ως 16 επιπλέον χαρακτήρες και τα ενώνει.

JavaScript

1const ENCODING_CHARS = '0123456789ABCDEFGHJKMNPQRSTVWXYZ';
2
3function encodeULID(time, randomBytes) {
4  // Timestamp: 48 bits -> 10 characters
5  let timestampStr = '';
6  let t = time;
7  for (let i = 0; i < 10; i++) {
8    timestampStr = ENCODING_CHARS[t % 32] + timestampStr;
9    t = Math.floor(t / 32);
10  }
11
12  // Randomness: 80 bits -> 16 characters
13  let result = timestampStr;
14  let bits = 0;
15  let bitCount = 0;
16  for (let i = 0; i < 10; i++) {
17    bits = (bits << 8) | randomBytes[i];
18    bitCount += 8;
19    while (bitCount >= 5) {
20      bitCount -= 5;
21      result += ENCODING_CHARS[(bits >> bitCount) & 0x1f];
22    }
23  }
24  return result;
25}
26
27function generateULID() {
28  const randomBytes = crypto.getRandomValues(new Uint8Array(10));
29  return encodeULID(Date.now(), randomBytes);
30}
31
32console.log(generateULID());
33

Python

1import os
2import time
3
4ENCODING_CHARS = "0123456789ABCDEFGHJKMNPQRSTVWXYZ"
5
6def encode_ulid(time_ms, random_bytes):
7    # Timestamp: 48 bits -> 10 characters
8    chars = []
9    t = time_ms
10    for _ in range(10):
11        chars.append(ENCODING_CHARS[t % 32])
12        t //= 32
13    timestamp_part = "".join(reversed(chars))
14
15    # Randomness: 80 bits -> 16 characters
16    bits = 0
17    bit_count = 0
18    random_part = []
19    for byte in random_bytes:
20        bits = (bits << 8) | byte
21        bit_count += 8
22        while bit_count >= 5:
23            bit_count -= 5
24            random_part.append(ENCODING_CHARS[(bits >> bit_count) & 0x1F])
25
26    return timestamp_part + "".join(random_part)
27
28def generate_ulid():
29    return encode_ulid(int(time.time() * 1000), os.urandom(10))
30
31print(generate_ulid())
32

Java

1import java.security.SecureRandom;
2import java.time.Instant;
3
4public class ULIDGenerator {
5    private static final SecureRandom random = new SecureRandom();
6    private static final char[] ENCODING_CHARS =
7        "0123456789ABCDEFGHJKMNPQRSTVWXYZ".toCharArray();
8
9    public static String generateULID() {
10        long timestamp = Instant.now().toEpochMilli();
11        byte[] randomBytes = new byte[10];
12        random.nextBytes(randomBytes);
13
14        // Timestamp: 48 bits -> 10 characters
15        char[] timestampChars = new char[10];
16        long t = timestamp;
17        for (int i = 9; i >= 0; i--) {
18            timestampChars[i] = ENCODING_CHARS[(int) (t % 32)];
19            t /= 32;
20        }
21
22        // Randomness: 80 bits -> 16 characters
23        StringBuilder result = new StringBuilder(new String(timestampChars));
24        long bits = 0;
25        int bitCount = 0;
26        for (byte b : randomBytes) {
27            bits = (bits << 8) | (b & 0xFF);
28            bitCount += 8;
29            while (bitCount >= 5) {
30                bitCount -= 5;
31                result.append(ENCODING_CHARS[(int) ((bits >> bitCount) & 0x1F)]);
32            }
33        }
34        return result.toString();
35    }
36
37    public static void main(String[] args) {
38        System.out.println(generateULID());
39    }
40}
41

Συχνές ερωτήσεις

Σε τι χρησιμοποιείται ένα ULID; Ένα ULID χρησιμοποιείται ως μοναδικό αναγνωριστικό για μια γραμμή βάσης δεδομένων, έναν πόρο API ή ένα καταγεγραμμένο συμβάν, όταν είναι επίσης χρήσιμη η ταξινόμηση με βάση τον χρόνο δημιουργίας.

Πόσο μεγάλο είναι ένα ULID; Ένα ULID έχει πάντα μήκος 26 χαρακτήρες: 10 χαρακτήρες για τη χρονοσφραγίδα και 16 για το τυχαίο μέρος.

Ποια κωδικοποίηση χρησιμοποιεί ένα ULID; Ένα ULID χρησιμοποιεί το αλφάβητο Base32 του Crockford, το οποίο αποτελείται από τα ψηφία 0–9 και τα γράμματα A-Z, με αφαίρεση των I, L, O και U για την αποφυγή σύγχυσης με άλλους χαρακτήρες.

Πώς διαφέρει ένα ULID από ένα UUID; Ένα ULID ταξινομείται με βάση τον χρόνο δημιουργίας και έχει μήκος 26 χαρακτήρες. Ένα τυχαίο UUID (έκδοση 4) δεν ταξινομείται χρονικά και έχει μήκος 36 χαρακτήρες, συμπεριλαμβανομένων των ενωτικών.

Πόσο πιθανή είναι μια σύγκρουση μεταξύ δύο ULID; Τα 80 bit τυχαιότητας καθιστούν τις συγκρούσεις εξαιρετικά απίθανες. Θα απαιτούνταν η δημιουργία περίπου 1,3 τρισεκατομμυρίων ULID μέσα στο ίδιο χιλιοστό του δευτερολέπτου για να επιτευχθεί πιθανότητα 50% να ταιριάξουν δύο.

Μπορούν να δημιουργηθούν ULID χωρίς σύνδεση στο διαδίκτυο; Ναι. Ένα ULID χρειάζεται μόνο το τοπικό ρολόι και μια γεννήτρια τυχαίων αριθμών, επομένως μπορεί να δημιουργηθεί εξ ολοκλήρου εκτός σύνδεσης.

Παραπομπές

"ULID Specification." GitHub, https://github.com/ulid/spec.
"Crockford's Base32 Encoding." http://www.crockford.com/base32.html.

Γεννήτρια ULID - Δημιουργία Μοναδικών Ταξινομήσιμων Αναγνωριστικών Online Δωρεάν

Τεκμηρίωση