Detaillierte Erläuterung von Distributed-ID-Generierungsschemata und dem Snowflake-Algorithmus

I. Hintergrund

In Internet-Business-Systemen gibt es verschiedene Arten von IDs. Diese IDs müssen die globale Eindeutigkeit gewährleisten, und solche IDs werden als verteilte IDs bezeichnet. Verteilte IDs müssen Eigenschaften wie Eindeutigkeit, steigende Tendenz, hohe Verfügbarkeit und hohe Leistung erfüllen.

Der Snowflake-Algorithmus ist ein verteiltes ID-Generierungsschema, das von Twitter für seine internen verteilten Projekte angewendet wurde. Nachdem dieser Algorithmus als Open Source veröffentlicht wurde, wurde er von großen Unternehmen anerkannt. Unter diesem Einfluss haben große Unternehmen sukzessive verteilte ID-Generatoren mit ihren eigenen Eigenschaften entwickelt. Bevor man sich eingehend mit dem Snowflake-Algorithmus beschäftigt, ist es notwendig, einen Überblick über die gängigen verteilten ID-Generierungsschemata zu geben.

II. Verteilte ID-Generierungsschemata

2.1 UUID

Die Kernidee dieses Algorithmus ist die Generierung einer UUID durch die Kombination der Netzwerkkarte der Maschine, der lokalen Zeit und einer Zufallszahl.

• Vorteile: Sie kann lokal generiert werden. Der Generierungsprozess ist einfach, mit guter Leistung, und es besteht kein Risiko von Problemen mit hoher Verfügbarkeit.
• Nachteile: Die generierte ID ist zu lang, was zu Speicherredundanz führt. Außerdem ist die ID ungeordnet und nicht lesbar, was zu einer geringen Abfrageeffizienz führt.

2.2 Datenbank Auto-Incrementing ID

Verwenden Sie die Auto-Increment-Strategie der Datenbank, wie z. B. auto_increment von MySQL. Um eine hohe Verfügbarkeit zu erreichen, können mehrere Datenbanken verwendet und unterschiedliche Schrittweiten festgelegt werden, um nicht-wiederholende IDs zu generieren.

• Vorteile: Die von der Datenbank generierten IDs sind absolut geordnet, und die Art und Weise, eine hohe Verfügbarkeit zu erreichen, ist relativ einfach.
• Nachteile: Es erfordert eine unabhängige Bereitstellung von Datenbankinstanzen, was kostspielig ist, und es gibt einen Leistungsengpass.

2.3 ID-Generierung durch Redis

Alle Befehlsoperationen in Redis sind Single-Threaded. Redis selbst bietet Auto-Increment-Atom-Befehle wie incr und increby, so dass sichergestellt werden kann, dass die generierten IDs eindeutig und geordnet sind. Um den Leistungsengpass eines einzelnen Knotens zu bewältigen, kann ein Redis-Cluster verwendet werden, um einen höheren Durchsatz zu erzielen. In einem Cluster mit 5 Redis-Knoten können beispielsweise die Anfangswerte jedes Redis auf 1, 2, 3, 4 bzw. 5 gesetzt werden, und die Schrittweite auf 5. Die von jedem Redis generierten IDs sind wie folgt:

• A: 1, 6, 11, 16, 21
• B: 2, 7, 12, 17, 22
• C: 3, 8, 13, 18, 23
• D: 4, 9, 14, 19, 24
• E: 5, 10, 15, 20, 25

Die Schrittweite und der Anfangswert müssen im Voraus festgelegt werden. Die Verwendung eines Redis-Clusters kann auch das Single-Point-of-Failure-Problem vermeiden. Darüber hinaus eignet sich Redis besser für die Generierung von Seriennummern, die jeden Tag bei 0 beginnen. Zum Beispiel kann die Bestellnummer die Form "Datum + täglich automatische Inkrementierungsnummer" annehmen. Ein Key wird jeden Tag in Redis generiert und durch INCR inkrementiert.

• Vorteile: Es hängt nicht von der Datenbank ab, ist flexibel und bequem zu verwenden und hat eine bessere Leistung als die Datenbank; die numerische ID ist natürlich geordnet, was sehr hilfreich für Szenarien wie Paginierung oder solche, die eine Sortierung erfordern, ist.
• Nachteile: Wenn Redis nicht im System verwendet wird, erhöht die Einführung dieser Komponente die Systemkomplexität, und der Aufwand für die Kodierung und Konfiguration ist ebenfalls relativ groß.

2.4 Snowflake-Algorithmus

Der Snowflake-Algorithmus wurde von Twitter für seine internen verteilten Projekte angewendet und wurde von großen inländischen Unternehmen nach der Open-Source-Veröffentlichung weithin anerkannt. Twitter stellte diesen Algorithmus über seinen offiziellen Blog am Kindertag 2010 vor, um jeden Tweet zu identifizieren.

+--------------------------------------------------------------------------+
| 1 Bit Unused | 41 Bit Timestamp |  10 Bit NodeID  |   12 Bit Sequence ID |
+--------------------------------------------------------------------------+

Der Snowflake-Algorithmus verwendet 64 Bits, um die ID zu speichern:

• Das höchste Bit ist reserviert und wird vorerst nicht verwendet.
• Die nächsten 41 Bits werden als Zeitstempel verwendet, wobei die kleinste Zeiteinheit Millisekunden beträgt. Der 41-Bit-Zeitstempel kann für ca. 69 Jahre verwendet werden (2^41 -1). Um den Zeitdarstellungsbereich voll auszuschöpfen, kann der Zeitstempel ab dem Zeitpunkt der ersten Bereitstellung des Systems gezählt werden, z. B. 2020-02-02 00:00:00.
• Die nächsten 10 Bits werden als Maschinen-ID (Worker-ID) verwendet, die 1024 Maschinen unterstützen kann. Die 10 Bits können auch in zwei Teile aufgeteilt werden, ein Teil als Datenzentrums-ID und ein Teil als Maschinen-ID. Wenn sie beispielsweise im Verhältnis 5:5 aufgeteilt werden, können sie 32 Datenzentren unterstützen, und jedes Datenzentrum kann maximal 32 Maschinen aufnehmen.
• Die letzten 12 Bits sind die Auto-Inkrement-ID innerhalb einer Zeiteinheit (Millisekunde), die 4096 IDs darstellen kann, d.h. jede Maschine kann maximal 4096 IDs pro Millisekunde generieren.

Die Anzahl der von Zeitstempel, Maschinen-ID und Auto-Inkrement-ID belegten Bits kann je nach der tatsächlichen Situation angepasst werden. Der Snowflake-Algorithmus hat eine grundlegende Sequentialität, da seine ersten Bits der Zeitstempel sind und die IDs nach der Zeit sortiert werden können.

III. Detaillierte Erläuterung des Snowflake-Algorithmus

3.1 Golang Kerncode

var (
    // Es kann als der Zeitpunkt festgelegt werden, an dem das System zum ersten Mal gestartet wurde, in Millisekunden. Es belegt 41 Bits und kann für 69 Jahre verwendet werden.
    Epoch int64 = 12345688374657

    // Die ID der Instanz belegt 10 Bits und kann bis zu 1024 Instanzen unterstützen.
    NodeBits uint8 = 10

    // Die Schrittweite belegt 12 Bits. Jede Instanz kann maximal 2^12 = 4096 nicht-wiederholende Daten pro Millisekunde erzeugen.
    StepBits uint8 = 12
)

// Generierungsalgorithmus
func (n *Node) Generate() ID {

    n.mu.Lock()
    // Die Anzahl der Millisekunden, die von dem eingestellten Zeitstempel bis jetzt vergangen sind
    now := time.Since(n.epoch).Nanoseconds() / 1000000
    // Wenn es mit der zuletzt aufgezeichneten Zeit übereinstimmt, inkrementiere Schritt um 1; andernfalls setze Schritt auf 0 zurück
    if now == n.time {
        n.step = (n.step + 1) & n.stepMask

        if n.step == 0 {
            for now <= n.time {
                now = time.Since(n.epoch).Nanoseconds() / 1000000
            }
        }
    } else {
        n.step = 0
    }

    n.time = now
    // Zeitstempel 41 Bits | Knoten 10 Bits | Schritt 12 Bits
    r := ID((now)<<n.timeShift |
        (n.node << n.nodeShift) |
        (n.step),
    )

    n.mu.Unlock()
    return r
}

Die spezifische Bit-Zuordnung kann je nach Ihren eigenen Bedürfnissen angepasst werden, z. B. (41, 10, 12), (41, 6, 16) usw. Das vollständige Golang-Code-Repo: snowflake github.

3.2 Vorteile

• Weniger Speicherplatz: Es werden nur 8 Bytes benötigt.
• Hohe Lesbarkeit: Die ID hat eine bestimmte Struktur und Bedeutung.
• Gute Leistung: IDs können zentral oder auf unabhängigen Knoten generiert werden.

3.3 Nachteile

Zeit-Rollback führt zur wiederholten Generierung von IDs.

3.4 Lösungen für Clock Rollback

2 Bits können von den 10 Bits der Maschinen-ID als Clock-Rollback-Bits entnommen werden. Wenn ein Clock-Rollback erkannt wird, wird die Anzahl der Rollback-Bits um 1 erhöht, und wenn sie den Maximalwert erreicht, wird sie von 0 an durchlaufen. Passen Sie beispielsweise die 10-Bit-Maschinennummer an eine 8-Bit-Maschinennummer + 2-Bit-Rollback-Bits an. Jedes Mal, wenn ein Clock-Rollback erkannt wird, wird die Anzahl der Rollback-Bits um 1 erhöht. Wenn die Rollback-Bits größer als der Maximalwert (3) sind, setzen Sie sie auf 0 zurück. Im gleichen Zeitraum wird das Clock-Rollback bis zu 3 Mal unterstützt. Nach jedem Rollback sind die endgültig generierten IDs aufgrund der unterschiedlichen Clock-Rollback-Bits ebenfalls unterschiedlich.

Leapcell: Das Beste von Serverless Web Hosting

Schließlich möchte ich eine Plattform empfehlen, die sich am besten für die Bereitstellung von Go-Diensten eignet: Leapcell

🚀 Erstellen Sie mit Ihrer bevorzugten Sprache

Entwickeln Sie mühelos in JavaScript, Python, Go oder Rust.

🌍 Stellen Sie unbegrenzt Projekte kostenlos bereit

Zahlen Sie nur für das, was Sie verbrauchen – keine Anfragen, keine Gebühren.

⚡ Pay-as-You-Go, keine versteckten Kosten

Keine Leerlaufgebühren, nur nahtlose Skalierbarkeit.

📖 Entdecken Sie unsere Dokumentation

🔹 Folgen Sie uns auf Twitter: @LeapcellHQ