Entwerfen Sie einen URL-Shortener für 10.000 Anfragen pro Sekunde

Systemdesign: skalierbarer URL-Shortener

Annahmen

1. Der Weiterleitungsverkehr erreicht Spitzen von 10.000 Anfragen pro Sekunde. Ein nominales Lese-Schreib-Verhältnis von 100:1 impliziert bei diesem Spitzenwert etwa 100 Erstellungen pro Sekunde.

2. Dreißig Milliarden Links in fünf Jahren erfordern im Durchschnitt etwa 190 Erstellungen pro Sekunde. Daher werden Speicher und Schreibpfad für mindestens 1.000 Erstellungen pro Sekunde ausgelegt, um diese Zahl zu erreichen und Spitzen abzufangen.

3. Links sind standardmäßig unveränderlich. Wenn Löschung oder Zielbearbeitung später unterstützt wird, erfolgt dies über explizite Versionierung und Cache-Invalidierung.

4. Grundlegende Analysen können letztendlich konsistent sein und während katastrophaler Ausfälle eine sehr geringe Anzahl von Ereignissen verlieren. Die Korrektheit der Weiterleitung hängt nicht von den Analysen ab.

5. Weiterleitungsantworten verwenden HTTP 302 oder 307 anstelle von permanenten 301-Weiterleitungen, um die operative Kontrolle zu erhalten und die Sichtbarkeit der Analysen zu verbessern.

6. Der Dienst läuft aktiv-aktiv in mindestens drei geografischen Regionen und verwendet eine global replizierte Link-Datenbank.

7. Architekturübersicht

Komponenten sind globale DNS- oder Anycast-Weiterleitung, regionale Lastausgleichsmechanismen, zustandslose Weiterleitungsdienste, zustandslose Erstellungsdienste, lokale In-Prozess-Caches, regionale verteilte Caches, eine partitionierte Link-Datenbank, ein dauerhafter Ereignisstrom sowie Analyseprozessoren und -speicher.

Erstellungspfad

1. Ein Client sendet die lange URL und optional einen benutzerdefinierten Alias an die nächstgelegene gesunde Region.
2. Die API authentifiziert oder begrenzt die Anfragen des Aufrufers, validiert die URL-Syntax, begrenzt die URL-Länge, erlaubt nur unterstützte Schemata wie HTTP und HTTPS und prüft reservierte Aliase.
3. Für einen automatisch generierten Link erstellt der Dienst einen kryptografisch zufälligen Code. Für einen benutzerdefinierten Alias normalisiert er den Alias gemäß einer dokumentierten, Groß-/Kleinschreibung beachtenden oder ignorierenden Richtlinie.
4. Der Erstellungsdienst führt eine bedingte Einfügung in die autoritative Datenbank durch: Einfügen nur, wenn der Code oder Alias noch nicht existiert.
5. Bei einer zufälligen Kollision generiert er einen weiteren Code und versucht es erneut. Bei einer Kollision mit einem benutzerdefinierten Alias gibt er HTTP 409 zurück, ohne den angeforderten Alias stillschweigend zu ändern.
6. Nachdem die Datenbank den Schreibvorgang bestätigt hat, fügt der Dienst die neue Zuordnung in den lokalen regionalen Cache ein und sendet eine Cache-Füll- oder Invalidierungsnachricht an andere Regionen.
7. Er gibt die Kurz-URL zurück. Ein Anforderungs-Idempotenzschlüssel kann wiederholte Client-Anfragen demselben Ergebnis zuordnen.

Der Schreibvorgang wird erst nach einem Quorum- oder Konsens-Commit bestätigt. Dies erhöht die Latenz bei übergreifenden Zonen und, je nach Datenbankkonfiguration, übergreifenden Regionen, schafft aber eine autoritative globale Eindeutigkeitsgarantie. Die Erstellung ist weitaus weniger latenzempfindlich als der Weiterleitungsverkehr.

Weiterleitungspfad

1. Die globale Weiterleitung leitet die Anfrage an die nächstgelegene gesunde Region weiter.
2. Der Weiterleitungsdienst validiert und extrahiert den Code.
3. Er prüft einen kleinen In-Prozess-Cache. Wenn nicht vorhanden, prüft er den regionalen verteilten Cache.
4. Bei einem Cache-Miss führt er eine Punktabfrage in einer lokalen Datenbankreplik durch, wobei der Code als Primärschlüssel verwendet wird.
5. Wenn gefunden und aktiv, füllt er beide Cache-Ebenen, sendet asynchron ein Klickereignis und gibt sofort eine 302- oder 307-Antwort mit dem Ziel zurück.
6. Wenn nicht gefunden, gibt er 404 zurück. Negative Ergebnisse werden nur kurzzeitig zwischengespeichert.

Der Weiterleitungspfad hat keine synchrone Analyseoperation und unter normalen Bedingungen keinen übergreifenden Netzwerk-Hop. Zustandslose Dienste skalieren horizontal hinter regionalen Lastausgleichsmechanismen.

2. Generierung und Eindeutigkeit von Kurzcodes

Ein siebenstelliger Base62-Raum enthält 62^7, etwa 3,52 Billionen, Werte und kann technisch 30 Milliarden Links speichern. Bei 30 Milliarden gespeicherten Links sind jedoch nur etwa 0,85 Prozent dieses Namensraums belegt. Ein zufälliger Massenscanner würde daher etwa einen gültigen Link pro 117 Vermutungen entdecken, was nicht die Anforderung erfüllt, dass Codes schwer zu erraten sind.

Der Standardcode verwendet daher 11 URL-sichere Base62-Zeichen, die aus einer kryptografisch sicheren Zufallsquelle generiert werden. Dies bietet etwa 65,5 Bit und 5,2 × 10^19 Möglichkeiten. Bei 30 Milliarden aktiven Links gelingt eine zufällige Vermutung mit einer Wahrscheinlichkeit von etwa 5,8 × 10^-10. Ratenbegrenzung und Missbrauchserkennung schränken die Enumeration weiter ein. Der Kompromiss ist ein vier Zeichen längerer Link. Siebenstellige Aliase können weiterhin erlaubt sein, wenn sie ausdrücklich von Benutzern gewählt werden, aber sie erhalten nicht die gleiche Garantie der Nicht-Enumerierbarkeit.

Die Zufallsgenerierung vermeidet die Offenlegung der Erstellungsreihenfolge und verteilt die Schlüssel gleichmäßig. Eine bedingte Primärschlüsseleinfügung ist die endgültige Eindeutigkeitsautorität. Geburtstags-Kollisionen über die gesamte Historie hinweg sind in einem Zufallssystem zu erwarten, aber nur gleichzeitige Kandidaten-Kollisionen sind betrieblich relevant: Jeder Einfügungsversuch wird geprüft und wiederholt. Bei der geplanten Belegung des 11-stelligen Raums sind Wiederholungen praktisch nicht vorhanden.

Eine Alternative wäre die Verschlüsselung oder Anwendung einer schlüsselbasierten Permutation auf eine Sequenznummer. Dies garantiert eindeutige generierte Eingaben, erfordert aber die Verwaltung des Schlüssel-Lebenszyklus und die Zuweisung von Sequenzen. Zufallsgenerierung plus bedingte Einfügung ist einfacher, entfernt die zentrale ID-Zuweisung und ist bei dieser Namensraumgröße ausreichend effizient.

Benutzerdefinierte Aliase teilen sich denselben Primärschlüssel-Namensraum wie generierte Codes. Die Alias-Normalisierung erfolgt vor der Einfügung, und eine global konsistente bedingte Einfügung entscheidet über den Gewinner von gleichzeitigen Anfragen. Reservierte Pfade wie Gesundheit, API, Admin und statisch werden abgelehnt. Wenn Aliase Groß-/Kleinschreibung ignorieren, ist die normalisierte Kleinbuchstabenform der Schlüssel, während die angeforderte Anzeigeform separat gespeichert werden kann.

3. Datenmodell und Datenbank

Die Felder des autoritativen Link-Datensatzes sind:

code: Primärschlüssel
long_url: Ziel-URL
created_at: Zeitstempel
owner_id: optionale Konto-ID
status: aktiv, deaktiviert oder gelöscht
ttl_or_expiry: optional
version: monoton steigender Wert für Cache-Invalidierung
custom_alias: boolesch

Klickzählungen werden bei jeder Weiterleitung nicht in diesem Datensatz aktualisiert, da dies beliebte Links zu Schreib-Hotspots machen würde.

Der Link-Speicher ist eine verteilte, partitionierte Schlüssel-Wert-Datenbank, die für den Primärschlüsselzugriff optimiert ist, wie z. B. DynamoDB, Bigtable, Cassandra mit sorgfältig verwalteter Konsistenz oder ein äquivalentes intern betriebenes System. Für global eindeutige bedingte Schreibvorgänge muss die ausgewählte Implementierung eine linearisierbare bedingte Erstellung für einen Schlüssel bieten, entweder nativ oder über Shard-weite Konsensführer. Relationale Joins und Bereichsscans sind auf dem Weiterleitungspfad nicht erforderlich.

Der primäre Partitionsschlüssel ist ein Hash des vollständigen Codes. Die Hash-Verteilung verhindert chronologische Hotspots und verteilt sowohl generierte Codes als auch benutzerdefinierte Aliase gleichmäßig. Der logische Schlüsselraum ist in Tausende von virtuellen Shards unterteilt, die neu zugewiesen werden, wenn Knoten hinzugefügt werden. Jeder Shard hat mindestens drei Replikate über Verfügbarkeitszonen hinweg, mit zusätzlichen übergreifenden regionalen Replikaten.

Kapazitätsschätzung

Angenommen, eine durchschnittliche URL von 400 Bytes und etwa 200 Bytes für Schlüssel, Metadaten, Kodierung, Indizes und Overhead der Speicher-Engine. Bei etwa 600 Bytes pro Datensatz benötigen 30 Milliarden Datensätze etwa 18 TB logische Daten. Unter Berücksichtigung längerer URLs, Kompaktierungs-Overhead, Tombstones und operativen Spielraums budgetieren wir 30 TB logische Daten. Drei dauerhafte Replikate erfordern etwa 90 TB, und Backups sowie übergreifende Kopien können die Flottenzuweisung auf etwa 150–250 TB erhöhen. Dies liegt gut im beabsichtigten Bereich von horizontal partitionierten Schlüssel-Wert-Speichern, ist aber für eine einzelne herkömmliche Datenbankinstanz ungeeignet.

Bei 10.000 Weiterleitungen pro Sekunde erzeugt selbst ein vollständiger Cache-Ausfall nur 10.000 zufällige Punktlesevorgänge pro Sekunde. Die Datenbank ist für mindestens 20.000–30.000 Lesevorgänge pro Sekunde pro bedienender Region während eines Failovers und mindestens 1.000 bedingte Erstellungen pro Sekunde ausgelegt. Die Kapazität wird mehr durch die Datensatzgröße, Replikation und Failover-Reserve als durch den normalen Anfrage-Durchsatz bestimmt.

Analysen verwenden separaten Speicher. Ein Stream-Prozessor schreibt pro Code, zeitlich gebündelte Zählungen in einen Analyse-Schlüssel-Wert- oder spaltenorientierten Speicher mit einem Modell wie Code plus Tag oder Stunde als Schlüssel und Zählung als Wert. Eine kompakte Summe kann asynchron aufrechterhalten werden. Die Trennung der Analysen verhindert, dass Zähler für beliebte Links mit Weiterleitungsabfragen konkurrieren.

4. Caching-Strategie

Jeder Weiterleitungsprozess verfügt über einen begrenzten LRU- oder TinyLFU-In-Memory-Cache für die heißesten Zuordnungen. Ein regionaler Redis- oder Memcached-kompatibler Cluster bildet die zweite Ebene. Zwischengespeicherte Werte umfassen Ziel, Status, Ablaufdatum und Datensatzversion.

Ein repräsentatives Ziel ist eine regionale Cache-Trefferquote von 95–99 Prozent. Zipf-ähnliche URL-Popularität macht dies im Allgemeinen machbar, auch wenn der gesamte Korpus sehr groß ist. Der Cache speichert heiße Objekte, nicht alle 30 Milliarden Links. Zum Beispiel verbrauchen 100 Millionen Einträge zu je etwa 600 Bytes vor Cache-Overhead und vielleicht 100–150 GB in der Praxis, verteilt über einen regionalen Cache-Cluster.

Zuordnungen sind standardmäßig unveränderlich, daher können positive Einträge eine lange TTL haben, z. B. 6–24 Stunden mit Jitter. Wenn Bearbeitung, Deaktivierung oder Löschung unterstützt wird, wird der autoritative Schreibvorgang zuerst committet und dann eine Invalidierung mit dem Code und der neuen Version an alle Regionen gesendet. Kürzere TTLs begrenzen die Zeit für die Auslieferung veralteter Daten, falls eine Invalidierung verloren geht. Sicherheitskritische Deaktivierungsoperationen können auch eine kleine globale Sperrliste in jedem Weiterleitungsprozess platzieren.

Negative Ergebnisse werden etwa 5–30 Sekunden lang zwischengespeichert, um wiederholte Scans abzuwehren. Der Erstellungspfad invalidiert negative Cache-Einträge, nachdem ein Code erfolgreich beansprucht wurde. Die kurze negative TTL begrenzt ein Rennen, bei dem eine andere Region kurzzeitig einen Miss zwischengespeichert hat, bevor die Replikation oder Invalidierung eintraf.

Bei einem Cache-Miss liest der Weiterleitungsdienst die regionale Datenbankreplik und füllt beide Cache-Ebenen. Anforderungskoaleszenz stellt sicher, dass gleichzeitige Misses für einen neu beliebten Code eine Datenbankanfrage statt Tausende auslösen. TTL-Jitter vermeidet synchronisierte Abläufe. Die Datenbank ist so dimensioniert, dass sie die gesamte Last von 10.000 Anfragen pro Sekunde tragen kann, wenn der verteilte Cache ausfällt, wobei eine etwas höhere Latenz akzeptiert wird, während sie funktionsfähig bleibt.

Der Kompromiss von langen Cache-TTLs ist die potenzielle Veralterung nach Bearbeitungen. Unveränderlichkeit, versionierte Invalidierungen und begrenzte TTLs machen diesen Kompromiss explizit. Die Korrektheit der Weiterleitung für neu erstellte Links kann durch synchrone Füllung der erstellenden Region und Weiterleitung einer sofortigen Leseanfrage an diese Region bei Bedarf verbessert werden.

5. Skalierung und Latenz

Weiterleitungsdienste sind zustandslos und skalieren horizontal basierend auf Anfragen pro Sekunde, CPU und p99-Latenz. Wenn eine Instanz sicher 1.000 Anfragen pro Sekunde verarbeitet, könnte jede Region mindestens 15–20 Instanzen für eine regionale Failover-Last von 10.000 Anfragen pro Sekunde betreiben, zuzüglich Headroom für Bereitstellung und Zonenfehler. Die tatsächliche Dimensionierung wird durch Lasttests ermittelt.

Ein normales Latenzbudget für Cache-Treffer beträgt etwa 2–5 ms für Lastausgleich und Anwendungsarbeit, 1–3 ms für eine In-Prozess-Suche oder 2–8 ms für eine regionale verteilte Cache-Suche und einige Millisekunden für die Erstellung der Antwort. Ein Cache-Miss-Budget weist etwa 10–25 ms für eine lokale replizierte Datenbank-Punktabfrage zu. Diese Budgets lassen Raum, um die p99-Latenz auf der Serverseite unter 50 ms zu halten.

Strikte Hop-zu-Hop-Timeouts verhindern, dass ein beschädigter Cache oder eine beschädigte Replik das gesamte Latenzbudget verbraucht. Der Cache-Zugriff kann auf etwa 8 ms und der Datenbankzugriff auf etwa 25–30 ms begrenzt sein, mit Wiederholungsversuchen nur, wenn noch genügend Budget vorhanden ist. Hedged Reads zu einer zweiten lokalen Replik können für das langsamste Perzentil verwendet werden, sind aber verzögert und ratenbegrenzt, um die normale Last nicht zu verdoppeln.

Schlüssel werden über virtuelle Shards hash-partitioniert. Zufällig generierte Codes gleichen den Datenverkehr natürlich aus, während ein außergewöhnlich heißer einzelner Link durch In-Prozess- und regionale Caches absorbiert wird. Wenn ein heißer Schlüssel die Datenbank erreicht, verhindern Anforderungskoaleszenz und replizierte Lesevorgänge, dass ein Speicher-Knoten zum Engpass wird.

Autoskalierung sorgt für ausreichende Kapazität für den Verlust einer gesamten Verfügbarkeitszone und mindestens eine Region, die Weiterleitungsverkehr von einem ausgefallenen Partner empfängt. Regionen laufen unter etwa 50–60 Prozent der Spitzenkapazität. Der Kompromiss ist höhere Leerlaufkosten im Austausch für das Verfügbarkeitsziel von 99,99 Prozent.

6. Zuverlässigkeit und Fehlerbehandlung

Verfügbarkeitsziel

Ein monatliches Ziel von 99,99 Prozent erlaubt etwa 4,4 Minuten Nichtverfügbarkeit in einem 30-Tage-Monat. Kein einzelner Cache-Knoten, keine Anwendungsinanz, keine Verfügbarkeitszone oder Region darf für Weiterleitungen erforderlich sein.

Ausfall einer Anwendungsinanz oder -zone

Health Checks entfernen ausgefallene Instanzen und Lastausgleichsmechanismen verteilen Anfragen über mindestens drei Zonen. Dienste verwenden Rolling- oder Canary-Deployments, Connection Draining und automatisiertes Rollback. Die regionale Kapazität übersteht den Verlust einer Zone.

Ausfall eines Cache-Knotens oder -Clusters

Cache-Knoten werden innerhalb einer Region geshardet und repliziert. Wenn ein einzelner Knoten ausfällt, übernimmt seine Replik. Wenn der gesamte Cache nicht verfügbar ist, verwenden Weiterleitungsdienste Circuit Breaker, überspringen Cache-Aufrufe und fragen die Datenbank direkt ab. Datenbankkapazität und Anwendungspool sind explizit für diesen Modus ausgelegt. Admission Control schützt die Datenbank vor unbegrenztem Scanner-Verkehr.

Ausfall eines Datenbank-Knotens

Jeder Shard wird über Zonen hinweg mit Quorum oder Konsens repliziert. Ein ausgefallener Leader wird automatisch ersetzt; Lesevorgänge verwenden eine andere gesunde lokale Replik. Bedingte Erstellungen bleiben während der kurzen Wahl für einen Shard nicht verfügbar, anstatt doppelte Eigentümerschaft zu riskieren. Weiterleitungen können von Replikaten und Caches fortgesetzt werden. Dies bevorzugt die Korrektheit bei der Erstellung, während die Lese-Verfügbarkeit erhalten bleibt.

Ausfall einer Region

Die globale gesundheitsbasierte Weiterleitung entfernt die ausgefallene Region und leitet den Verkehr an die nächstgelegene gesunde Region weiter. Jede bedienende Region verfügt über eine replizierte Kopie der Link-Daten und eine unabhängige Infrastruktur für Weiterleitung, Cache und Ereigniserfassung. Die Cache-Trefferquote ist nach einem Failover zunächst niedriger, daher behalten Standby-Regionen warme Caches für global heiße Links und genügend Datenbank-/Lese-Kapazität für den Kalt-Cache-Anstieg bei.

Bei generierten Codes kann die globale Replikation nach einer konsensgestützten autoritativen Einfügung asynchron erfolgen, wenn die Datenbankarchitektur jeden Schlüssel an einen Home-Shard weiterleitet. Bei benutzerdefinierten Aliassen muss die autoritative bedingte Einfügung global serialisiert bleiben. Wenn ein neu erstellter Link eine überlebende Region vor einem katastrophalen Verlust nicht erreicht hat, kann der Dienst kurzzeitig einen wiederholbaren Fehler anstelle einer falschen Zuordnung zurückgeben. Eine stärkere synchrone Multi-Region-Replikation reduziert dieses Recovery-Point-Fenster, erhöht aber die Erstellungslatenz. Die bevorzugte Konfiguration committet die Link-Erstellung über Replikate in mindestens zwei Regionen, da Schreibvorgänge relativ geringvolumig sind.

Backups und Korruption

Die Datenbank verwendet Prüfsummen, Point-in-Time-Wiederherstellung, unveränderliche Snapshots und regelmäßig getestete Wiederherstellungsverfahren. Löschungen verwenden Tombstones und eine Aufbewahrungsfrist anstelle einer sofortigen physischen Entfernung. Backups schützen vor logischer Korruption, sind aber kein Teil des normalen Weiterleitungs-Failovers.

Verhalten bei Überlastung

Ratenbegrenzungen gelten nach Quelle, Konto und verdächtigen Code-Scanning-Mustern. Erstellungs- und Analyse-Traffic haben eine niedrigere Priorität als Weiterleitungen. Load Shedding lehnt missbräuchliche oder übermäßige Erstellungsanfragen ab, bevor die Weiterleitungs-Kapazität beeinträchtigt wird. Circuit Breaker, begrenzte Warteschlangen und Timeouts verhindern kaskadierende Fehler.

7. Klick-Analysen

Nach Auswahl des Weiterleitungsziels erstellt der Dienst ein kompaktes Ereignis mit einer Ereignis-ID, einem Code, einem Zeitstempel, einer Region und optional groben Verweis- oder User-Agent-Feldern. Er platziert das Ereignis in einen begrenzten lokalen asynchronen Puffer und gibt die Weiterleitung zurück, ohne auf die Bestätigung der Analysen zu warten.

Ein regionaler Collector bündelt Ereignisse in einen dauerhaften replizierten Stream wie Kafka, Pulsar oder Kinesis. Stream-Prozessoren aggregieren Ereignisse nach Code und Zeit-Bucket und schreiben dann gebündelte Inkremente in den Analyse-Speicher. Regelmäßige Kompaktierung erzeugt Gesamt-Klickzahlen. Dashboards und APIs lesen den Analyse-Speicher, niemals die autoritative Weiterleitungs-Tabelle.

Ereignis-IDs ermöglichen die nachgelagerte Deduplizierung, wenn Collector erneut versuchen. Die Partitionierung des Streams direkt nach Code würde einen viralen Link auf eine Partition konzentrieren, daher kann der Ingestionsschlüssel Code plus ein zufälliges Stripe sein. Prozessoren aggregieren zuerst gestreifte Zähler und verschmelzen sie dann. Dies ermöglicht die horizontale Skalierung von Hot-Link-Analysen.

Ein rein asynchroner In-Memory-Puffer kann Ereignisse verlieren, wenn ein Weiterleitungsprozess abstürzt. Wenn eine stärkere Dauerhaftigkeit erforderlich ist, kann jeder Host oder Sidecar Batches in ein lokales Write-Ahead-Log anhängen, bevor er sie weiterleitet, aber Weiterleitungsantworten sollten immer noch nicht auf den zentralen Stream warten. Der akzeptierte Kompromiss für grundlegende Analysen ist die endgültige Konsistenz und eine kleine, gemessene Unterzählung während schwerer Ausfälle, im Austausch für die Beibehaltung der Weiterleitungs-Latenz und -Verfügbarkeit.

Ergebnis

Der normale Weiterleitungspfad ist eine lokale Cache-Suche, gefolgt, nur bei Misses, von einer lokalen partitionierten Schlüssel-Wert-Suche. Zufällige 11-stellige Codes verhindern sequentielle Offenlegung und machen erfolgreiches Raten im großen Stil unpraktisch. Bedingte Einfügungen sorgen für Eindeutigkeit, Hash-Partitionierung unterstützt den 30-Milliarden-Datensatz-Korpus, aktiv-aktive regionale Bedienung eliminiert regionale Single Points of Failure und asynchrone gestreifte Analysen halten Zähler-Schreibvorgänge vollständig vom Latenz-kritischen Pfad fern.

Systemdesign: URL-Kürzer (10.000 Anfragen pro Sekunde)

Annahmen:

• Wir entwickeln zunächst für eine einzelne Region, wobei Multi-Region eine zukünftige Verbesserung darstellt.
• Der Schwerpunkt liegt aufgrund des Lese-Schreib-Verhältnisses von 100:1 auf dem Weiterleitungspfad.
• Benutzerdefinierte Aliase sind eine sekundäre Funktion und können im Vergleich zu Standardweiterleitungen etwas höhere Latenzzeiten oder gelegentliche Nichtverfügbarkeit tolerieren.
• Klickanalysen sind nicht streng in Echtzeit und können eine leichte Verzögerung aufweisen.

1. High-Level-Architektur und Anfragefluss

Schreibpfad (Kurzlink erstellen):

1. API-Gateway: Empfängt die POST-Anfrage mit der langen URL und dem optionalen benutzerdefinierten Alias.
2. Lastverteiler: Verteilt Schreibanfragen auf die Instanzen der URL-Shortening-Service (US) API.
3. US API (Schreibdienst):
   • Validiert die Eingabe-URL.
   • Generiert einen Kurzcode (siehe Abschnitt 2).
   • Wenn ein benutzerdefinierter Alias angegeben ist, versucht er zuerst, diesen zu reservieren (siehe Abschnitt 2).
   • Speichert die Zuordnung (Kurzcode -> ursprüngliche URL, benutzerdefinierter Alias -> Kurzcode) im Datenspeicher.
   • Gibt die generierte Kurz-URL an den Client zurück.

Lesepfad (Weiterleitung):

1. API-Gateway: Empfängt die GET-Anfrage für eine Kurz-URL.
2. Lastverteiler: Verteilt Leseanfragen auf die US-API-Instanzen.
3. US API (Lesedienst):
   • Extrahiert den Kurzcode aus dem URL-Pfad.
   • Cache-Abfrage: Überprüft einen verteilten Cache (z. B. Redis Cluster) auf den Kurzcode.
     • Cache-Treffer: Wenn gefunden, wird die ursprüngliche URL abgerufen und eine HTTP-301/302-Weiterleitungsantwort zurückgegeben.
     • Cache-Fehlgriff: Wenn nicht gefunden, wird der primäre Datenspeicher abgefragt.
   • Datenspeicher-Abfrage: Fragt den primären Datenspeicher nach der ursprünglichen URL ab, die dem Kurzcode zugeordnet ist.
   • Cache-Aktualisierung: Wenn im Datenspeicher gefunden, wird die ursprüngliche URL für zukünftige Anfragen in den Cache geschrieben.
   • Weiterleitung: Gibt eine HTTP-301/302-Weiterleitungsantwort mit der ursprünglichen URL zurück.
   • Fehlerbehandlung: Wenn nicht gefunden, wird ein 404 Not Found zurückgegeben.
4. Klickanalysen (Asynchron): Ein separater Dienst oder Mechanismus (siehe Abschnitt 7) zeichnet Klickereignisse asynchron auf.

Kompromisse:

• Trennung von Belangen: Die Trennung von Lese- und Schreibdiensten ermöglicht unabhängige Skalierung und Optimierung. Der Lesepfad ist für geringe Latenz und hohen Durchsatz optimiert.
• API-Gateway/Lastverteiler: Führt einen einzigen Fehlerpunkt ein, wenn er nicht für hohe Verfügbarkeit konfiguriert ist, ist aber für Skalierung und Verkehrsmanagement unerlässlich.
• Cache-Fehlgriff-Strafe: Ein Cache-Fehlgriff verursacht aufgrund der Datenspeicherabfrage höhere Latenzzeiten, dies wird jedoch durch einen großen Cache und eine hohe Trefferquote gemildert.

2. Strategie zur Generierung von Kurzcodes

Strategie: Base62-Kodierung mit einem Zähler/ID-Generator.

1. ID-Generierung: Wir verwenden einen verteilten ID-Generierungsdienst (z. B. Snowflake-ähnlich oder einen dedizierten Dienst mit ZooKeeper/etcd), um eindeutige, monoton steigende 64-Bit-Integer zu generieren. Dies gewährleistet Eindeutigkeit und vermeidet Kollisionen an der Quelle.
   • Kompromiss: Erfordert einen hochverfügbaren und performanten ID-Generierungsdienst. Wenn er ausfällt, können keine neuen Kurzlinks erstellt werden.
2. Base62-Kodierung: Jeder generierte 64-Bit-Integer-ID wird in eine Base62-Zeichenkette (0-9, a-z, A-Z) umgewandelt. Eine 64-Bit-ID kann bis zu 2^64 eindeutige Werte darstellen. Die ersten 6 Zeichen können ungefähr 68 Milliarden eindeutige Werte darstellen (62^6), und 7 Zeichen können ungefähr 4,1 Billionen (62^7) darstellen. Für 30 Milliarden Links über 5 Jahre sind 7 Zeichen ausreichend und bieten viel Spielraum für Wachstum.
   • Kompromiss: Die Base62-Kodierung ist etwas komplexer als einfaches Hashing, liefert aber kürzere URLs und vermeidet im Vergleich zu sequenziellen IDs eine Erratbarkeit.
3. Benutzerdefinierte Aliase:
   • Wenn ein Benutzer einen benutzerdefinierten Alias anfordert (z. B. /mein-link), prüft der Schreibdienst zuerst, ob der Alias in einer dedizierten Tabelle/einem Index im Datenspeicher (z. B. Tabelle custom_aliases, die alias -> short_code abbildet) bereits vergeben ist.
   • Wenn der Alias verfügbar ist, wird er reserviert und dem neu generierten Kurzcode zugeordnet.
   • Wenn der Alias vergeben ist, gibt die API eine Fehlermeldung an den Benutzer zurück.
   • Kollisionsbehandlung: Die ID-Generierung und Base62-Kodierung gewährleisten die Eindeutigkeit für generierte Kurzcodes. Benutzerdefinierte Aliase werden über eine separate, atomare Prüf-und-Setz-Operation im Datenspeicher behandelt, um Kollisionen zu vermeiden.
   • Kompromiss: Abfragen benutzerdefinierter Aliase verursachen einen geringen Mehraufwand für den Schreibpfad. Die Verfügbarkeit benutzerdefinierter Aliase ist nicht garantiert.

Eindeutigkeitsgarantie: Erreicht durch den verteilten ID-Generator. Jede ID ist eindeutig, und ihre Base62-Darstellung wird ebenfalls eindeutig sein.

Nicht erratbar: Base62-kodierte IDs sind nicht sequenziell und verraten nicht die Reihenfolge der Erstellung oder die Gesamtzahl der Links. Sie sind effektiv zufällig aussehende Zeichenketten.

3. Datenmodell und Datenspeicher

Wahl des Datenspeichers: Ein verteilter NoSQL-Schlüssel-Wert-Speicher (z. B. Cassandra, DynamoDB oder eine geshardete relationale Datenbank wie Vitess) für die primäre Link-Zuordnung und ein separates System für Analysen.

Primärer Datenspeicher (Link-Zuordnung):

• Schema:

  • links-Tabelle/Sammlung:
    • short_code (Primärschlüssel, String, z. B. "aBcDeFg")
    • original_url (String)
    • created_at (Zeitstempel)
    • user_id (Optional, für Eigentümerschaft/Verwaltung)
  • custom_aliases-Tabelle/Sammlung:
    • alias (Primärschlüssel, String, z. B. "mein-link")
    • short_code (String, Fremdschlüssel zu links.short_code)

• Begründung des Datenspeichertyps: Ein verteilter NoSQL-Schlüssel-Wert-Speicher wird wegen seiner hohen Verfügbarkeit, horizontalen Skalierbarkeit und hervorragenden Leseleistung für Schlüsselabfragen bevorzugt, was für den Weiterleitungspfad entscheidend ist. Er kann die massive Skalierung von 30 Milliarden Einträgen bewältigen.

• Kapazitäts-/Speicherschätzung:

  • Links-Tabelle: 30 Milliarden Einträge.
    • short_code: ca. 7 Bytes (Base62, 7 Zeichen)
    • original_url: Durchschnittlich 100 Bytes (kann stark variieren, Durchschnitt annehmen)
    • created_at, user_id: ca. 10 Bytes
    • Gesamt pro Eintrag: ca. 117 Bytes. Aufrunden auf 150 Bytes für Overhead und Replikation.
    • Gesamtspeicher: 30 Milliarden * 150 Bytes = 4,5 * 10^12 Bytes = 4,5 TB.
  • Tabelle für benutzerdefinierte Aliase: Angenommen, 10 % der Links haben benutzerdefinierte Aliase (3 Milliarden).
    • alias: Durchschnittlich 15 Bytes (kürzer als lange URLs).
    • short_code: ca. 7 Bytes.
    • Gesamt pro Eintrag: ca. 22 Bytes. Aufrunden auf 50 Bytes für Overhead.
    • Gesamtspeicher: 3 Milliarden * 50 Bytes = 150 * 10^9 Bytes = 0,15 TB.
  • Gesamtspeicher primär: ca. 4,65 TB. Dies ist für verteilte NoSQL-Systeme überschaubar.

• Partitionierung/Sharding: Der Datenspeicher wird nach short_code (für die links-Tabelle) und alias (für die custom_aliases-Tabelle) geshardet. Dies ermöglicht eine gleichmäßige Verteilung von Daten und Last über die Knoten.

Kompromisse:

• NoSQL vs. SQL: Ein NoSQL-Speicher wird wegen seiner Schemaflexibilität und horizontalen Skalierbarkeit bevorzugt. Eine relationale Datenbank könnte funktionieren, würde aber eine komplexere Sharding-Verwaltung erfordern (z. B. Vitess).
• Datenredundanz: NoSQL-Speicher replizieren Daten typischerweise zur Verfügbarkeit, was den Speicherbedarf erhöht, aber die Fehlertoleranz verbessert.
• Tabelle für benutzerdefinierte Aliase: Eine separate Tabelle wird verwendet, um die Verfügbarkeit von Aliasen effizient zu prüfen, ohne die Haupttabelle links durchsuchen zu müssen, was ineffizient wäre.

4. Caching-Strategie

Strategie: Verteilter In-Memory-Cache (z. B. Redis Cluster, Memcached).

• Was wird gecacht: Häufig abgerufene Zuordnungen von short_code zu original_url.
• Cache-Schlüssel: short_code (z. B. "aBcDeFg")
• Cache-Wert: original_url (z. B. "https://www.sehrlangeurl.com/...")
• Cache-Größe: Ausgelegt, um einen erheblichen Teil der Hot-Links zu speichern. Angesichts von 10.000 Anfragen pro Sekunde und einem Verhältnis von 100:1 erwarten wir Millionen von aktiven Links pro Sekunde. Ein Cache mit 1-5 Millionen Einträgen sollte für Hot-Links eine hohe Trefferquote bieten.
• Cache-Invalidierung:
  • Keine explizite Invalidierung für Standardlinks erforderlich: Sobald Links erstellt sind, sind sie unveränderlich. Die Zuordnung ändert sich nicht.
  • Für benutzerdefinierte Aliase: Wenn ein benutzerdefinierter Alias geändert wird (normalerweise nicht erlaubt, aber wenn es so wäre), würde die alte Zuordnung short_code -> original_url im Cache verbleiben. Die Standardpraxis ist jedoch, dass benutzerdefinierte Aliase eindeutig und nach der Festlegung dauerhaft sind. Wenn ein Link gelöscht wird (keine übliche Funktion für URL-Kürzer), würde der Eintrag aus dem Cache entfernt.
• Behandlung von Cache-Fehlgriffen:
  1. Bei einem Cache-Fehlgriff fragt die US-API (Lesedienst) den primären Datenspeicher nach der original_url unter Verwendung des short_code ab.
  2. Wenn im Datenspeicher gefunden, wird die original_url mit einer Time-To-Live (TTL) (z. B. 24-48 Stunden) zurück in den Cache geschrieben, bevor sie an den Client zurückgegeben wird.
  3. Wenn im Datenspeicher nicht gefunden, wird ein 404 zurückgegeben und kein Eintrag in den Cache aufgenommen.

Kompromisse:

• Cache-Veralterung: TTL-basiertes Caching bedeutet, dass es ein kleines Zeitfenster gibt, in dem ein Link aktualisiert werden könnte (wenn Updates erlaubt wären) und der Cache veraltet wäre. Bei unveränderlichen Links ist dies jedoch kein Problem.
• Cache-Verfügbarkeit: Der Cache ist eine kritische Komponente. Wenn er ausfällt, erhöht sich die Latenz aufgrund von Datenspeicherabfragen erheblich, aber der Dienst bleibt verfügbar (wenn auch langsamer).
• Kosten: Große In-Memory-Caches können teuer sein.

5. Skalierungsstrategie

Skalierung des Lesepfads (Weiterleitungen):

• Zustandslose API-Server: Die US-API-Instanzen, die Weiterleitungen verarbeiten, sind zustandslos. Dies ermöglicht es uns, sie hinter einem Lastverteiler unbegrenzt horizontal zu skalieren.
• Verteilter Cache: Ein geshardeter und replizierter verteilter Cache (wie Redis Cluster) kann Millionen von Anfragen pro Sekunde verarbeiten und bietet geringe Latenz. Er ist für die horizontale Skalierung ausgelegt.
• Datenspeicher-Skalierung: Der gewählte verteilte NoSQL-Datenspeicher (Cassandra, DynamoDB) ist für die horizontale Skalierung ausgelegt. Wir können weitere Knoten hinzufügen, um den Durchsatz und die Kapazität zu erhöhen.
• Lastverteiler: Lastverteiler auf mehreren Ebenen (API-Gateway, Service-zu-Service-intern) verteilen den Verkehr gleichmäßig.

Datenpartitionierung/Sharding:

• Datenspeicher-Sharding: Wie in Abschnitt 3 erwähnt, wird der primäre Datenspeicher nach short_code (oder einem Hash davon) für die links-Tabelle und alias für die custom_aliases-Tabelle geshardet. Dies verteilt Daten und Lese-/Schreiblast über mehrere Knoten.
• Cache-Sharding: Der verteilte Cache ist von Natur aus geshardet und verteilt Schlüssel über seine Knoten.
• ID-Generierungsdienst: Dieser Dienst muss ebenfalls skalierbar sein, möglicherweise unter Verwendung mehrerer Instanzen, die von ZooKeeper/etcd oder einem verteilten Konsensprotokoll koordiniert werden.

Kompromisse:

• Komplexität: Sharding und verteilte Systeme erhöhen die betriebliche Komplexität erheblich.
• Hotspots: Obwohl Sharding hilft, könnten extrem beliebte Links immer noch Hotspots auf bestimmten Cache-Shards oder Datenspeicherpartitionen erzeugen. Strategien wie konsistentes Hashing oder fortschrittlichere Lastverteilung können dies mildern.

6. Zuverlässigkeit und Fehlerbehandlung

Verfügbarkeitsziel (99,99 %): Erfordert Redundanz auf jeder Ebene.

• Ausfall eines Datenspeicherknotens:
  • Strategie: Daten werden über mehrere Knoten (z. B. 3-5 Replikate) und möglicherweise über Verfügbarkeitszonen innerhalb einer Region repliziert.
  • Behandlung: Der Datenspeicher-Cluster behandelt Knotenausfälle automatisch, indem er ein Replikat befördert und weiterhin Anfragen bedient. Lese- und Schreibvorgänge können während eines Failovers eine kurze Latenzspitze erfahren, aber der Dienst bleibt verfügbar.
  • Kompromiss: Erhöhte Speicherkosten aufgrund der Replikation.
• Ausfall eines Cache-Knotens:
  • Strategie: Verteilte Caches wie Redis Cluster sind mit Replikation und Sharding konzipiert. Wenn ein Knoten ausfällt, können seine Replikate übernehmen oder die Daten neu verteilt werden.
  • Behandlung: Cache-Fehlgriffe nehmen vorübergehend zu, während der Cache neu aufgebaut wird oder ein Failover stattfindet. Das System greift auf den Datenspeicher zurück, was zu höheren Latenzen, aber fortgesetzter Verfügbarkeit führt.
  • Kompromiss: Vorübergehende Leistungsverschlechterung bei Cache-Ausfall.
• Ausfall eines API-Servers:
  • Strategie: Mehrere Instanzen der zustandslosen US-API-Server hinter Lastverteilern ausführen.
  • Behandlung: Lastverteiler erkennen fehlerhafte Instanzen und hören auf, ihnen Verkehr zuzusenden. Der Verkehr wird automatisch an fehlerfreie Instanzen weitergeleitet.
  • Kompromiss: Erfordert robuste Lastverteilung und Zustandsprüfung.
• Ausfall einer Region:
  • Strategie: Den Dienst über mehrere Verfügbarkeitszonen (AZs) innerhalb einer Region bereitstellen. Für höhere Verfügbarkeit kann ein Multi-Region-Aktiv-Aktiv- oder Aktiv-Passiv-Setup implementiert werden.
  • Behandlung: Wenn eine AZ ausfällt, wird der Verkehr an fehlerfreie AZs weitergeleitet. Wenn eine gesamte Region ausfällt, wird der Verkehr an eine sekundäre Region weitergeleitet (erfordert globale Lastverteilung und Datenreplikation).
  • Kompromiss: Erhebliche Erhöhung der Komplexität und Kosten für Multi-Region-Bereitstellungen.

Erreichen des Verfügbarkeitsziels: Redundanz, automatische Failover und schrittweise Verschlechterung (Rückgriff auf den Datenspeicher bei Cache-Fehlgriff) sind entscheidend. Überwachung und Alarmierung sind unerlässlich, um Fehler schnell zu erkennen und darauf zu reagieren.

7. Erfassung von Klickanalysen

Strategie: Asynchrone Verarbeitung, um den kritischen Weiterleitungspfad nicht zu beeinträchtigen.

1. Ereigniserzeugung: Wenn eine Weiterleitung stattfindet (nachdem die ursprüngliche URL abgerufen wurde und bevor die Weiterleitungsantwort gesendet wird), veröffentlicht die US-API (Lesedienst) ein leichtgewichtiges