Entwurf eines URL-Kürzungsdienstes

A) API-Design 1) Kurze URL erstellen - Endpunkt: POST /v1/urls - Request JSON: - long_url (string, erforderlich, max. z. B. 8KB) - custom_alias (string, optional; falls angegeben, muss eindeutig sein und erlaubte Zeichen/Länge bestehen) - expire_at (Zeitstempel, optional) - metadata (Objekt, optional: z. B. Kampagne, user_id) - Antwort (201): - code (string) - short_url (string) - long_url (string) - created_at (Zeitstempel) - expire_at (Zeitstempel|null) - Fehler: - 400 ungültige URL/Alias - 409 Alias existiert bereits - 429 Ratenbegrenzung 2) Auflösen/Umleiten - Endpunkt: GET /{code} - Verhalten: - Standardmäßig 301 Moved Permanently (oder 302, falls Tracking/Experimentierung dies erfordert) - Location-Header = long_url - Optional: GET /v1/urls/{code} gibt JSON anstelle einer Umleitung zurück (für API-Clients) - Fehler: - 404 nicht gefunden/abgelaufen 3) Löschen/Deaktivieren (optional, zur Missbrauchs-/Benutzerkontrolle) - Endpunkt: DELETE /v1/urls/{code} - Authentifizierung erforderlich - Antwort: 204 4) Analysen (optional, kann asynchron/ungefähr sein) - Endpunkt: GET /v1/urls/{code}/stats?from=&to= - Gibt aggregierte Zähler zurück (Klicks pro Tag, Referrer, Geo usw.) Hinweise: - Authentifizierung: API-Schlüssel/OAuth für Erstellung und Verwaltung; Umleitungen bleiben öffentlich. - Idempotenz: Unterstützt Idempotency-Key-Header bei POST, um Duplikate bei Wiederholungsversuchen zu vermeiden. B) Datenmodell und Speicher Workload - Schreibvorgänge: 100 Mio. neu/Monat ≈ 3,33 Mio./Tag ≈ 38,6 Schreibvorgänge/Sek. im Durchschnitt (höherer Spitzenwert). - Lesevorgänge: 100:1 => 10 Mrd. Umleitungen/Monat ≈ 3,86 Tsd. Lesevorgänge/Sek. im Durchschnitt (Spitzenwerte viel höher). Speicherauswahl - Primärspeicher: verteilte Key-Value-/Wide-Column-Speicher (z. B. DynamoDB/Cassandra/ScyllaDB), optimiert für sehr hohe Lese-QPS, geringe Latenz, horizontale Skalierung und Multi-DC-Replikation. - Begründung: Zugriffsmuster ist hauptsächlich Schlüsselsuche nach kurzem Code; Wert ist klein; hoher Bedarf an hoher Verfügbarkeit und vorhersehbarer Latenz. - Sekundäre Systeme: - Cache: Redis/Memcached-Cluster pro Region. - Analyse-Pipeline: Kafka/PubSub + Stream-Verarbeitung + OLAP-Speicher (nicht im kritischen Pfad). Schema 1) url_mapping (primär) - Partitionsschlüssel: code (string) - Spalten: - long_url (string) - created_at (Zeitstempel) - expire_at (Zeitstempel|null) - user_id (string|null) - status (aktiv/gelöscht) - checksum (optional für Integrität) - TTL: Wenn expire_at gesetzt ist, native TTL verwenden, damit abgelaufene Einträge automatisch entfernt werden. 2) alias_reservation (optional, wenn benutzerdefinierte Aliase mit Eindeutigkeit unterstützt werden) - Schlüssel: custom_alias - Wert: code / Besitzmetadaten 3) idempotency (optional) - Schlüssel: (user_id, idempotency_key) - Wert: code - TTL: z. B. 24h Speicherschätzung (10 Jahre) - Neue URLs in 10 Jahren: 100 Mio./Monat * 12 * 10 = 12 Mrd. Zuordnungen. - Größe pro Datensatz grobe Ordnung: - code: ~8 Bytes (oder bis zu ~10 Zeichen) - long_url: Durchschnittlich 200 Bytes annehmen (konservativ), plus Overhead - Metadaten/Spalten/Index-Overhead: ~100–200 Bytes annehmen, je nach Speicher - Gesamteffektiv (inkl. Replikations-Overhead noch nicht gezählt): ~400 Bytes/Datensatz (vernünftiger Planungswert). - Rohdaten: 12 Mrd. * 400 Bytes = 4,8 TB. - Mit Speicher-Engine-Overhead + Kompaktierung + sekundären Indizes: ca. 2–3x planen => ~10–15 TB. - Replikation: - Innerhalb der Region (RF=3): ~30–45 TB. - Multi-Region (z. B. 2 Regionen aktiv-aktiv): verdoppeln => ~60–90 TB insgesamt über alle Regionen. (Dies sind Planungszahlen; genaue Werte hängen von der durchschnittlichen URL-Länge und dem DB-Overhead ab.) C) Generierung kurzer URLs Ziele - So kurz wie möglich - Kollisionsfrei bei hoher Skalierung - Unterstützt mindestens 10 Jahre Wachstum Keyspace-Mathematik - Gesamtzahl der benötigten Codes in 10 Jahren: 12 Mrd. - Base62-Zeichensatz verwenden: [0-9][a-z][A-Z] => 62 Symbole. - Länge L Kapazität: 62^L. - 62^6 ≈ 56,8 Mrd. (ausreichend für 12 Mrd.) - 62^7 ≈ 3,52 Billionen (mehr Spielraum) Auswahl - Variable Länge mit einem Minimum von 6 Zeichen verwenden. - Beginnen Sie mit 6 Zeichen für die ersten ~56,8 Milliarden Codes; das deckt bereits den 10-Jahres-Bedarf mit erheblichem Spielraum ab (56,8 Mrd./12 Mrd. ≈ 4,7x). - Möglichkeit behalten, in Zukunft auf 7 Zeichen umzusteigen, ohne bestehende Links zu brechen. Generierungsalgorithmus (keine Kollisionen) Ausgewählte Option: global eindeutige numerische IDs + Base62-Kodierung. - Einen monoton steigenden 64-Bit-ID-Raum aufrechterhalten. - ID in Base62 kodieren, um den Code zu erzeugen. - Kollisionsvermeidung: nicht erforderlich, da IDs konstruktionsbedingt eindeutig sind. Wie man IDs in großem Maßstab generiert - Einen verteilten ID-Allocator ähnlich wie Snowflake verwenden oder einen zentralen „ID-Dienst“ mit Bereichsvermietung: 1) ID-Dienst speichert einen Zähler in einem stark konsistenten Speicher (z. B. etcd/Spanner) pro Region. 2) Jeder App-Server mietet einen ID-Block (z. B. 1 Mio. IDs) zur lokalen Generierung. 3) Wenn der Block erschöpft ist, wird ein neuer Block angefordert. - Dies vermeidet Konflikte pro Schreibvorgang und gewährleistet gleichzeitig die Eindeutigkeit. Umgang mit benutzerdefinierten Aliassen - Wenn custom_alias angegeben ist: - Zeichenkette/Länge validieren - Bedingte Schreiboperation (compare-and-set) auf url_mapping mit Schlüssel=alias; wenn vorhanden, 409 zurückgeben. D) Skalierung und Leistung Architektur auf hoher Ebene - Anycast/GeoDNS -> Globaler Load Balancer -> Regionale L7 Load Balancer -> zustandslose API/Redirect-Server. - Separate Dienste: - Schreibpfad: URL-Erstellungsdienst - Lesepfad: Redirect-Dienst - Gemeinsamer Speicher + Cache Skalierung von Lese- und Schreibvorgängen unabhängig voneinander - Redirect-Dienst horizontal skaliert basierend auf QPS/Latenz (wahrscheinlich dominierende Kosten). - Erstellungsdienst skaliert basierend auf Schreibdurchsatz. - Separate Autoscaling-Gruppen und unabhängige Bereitstellungspipelines verwenden. Datenpartitionierung - Partitionierung nach Code-Hash (oder nach Code selbst) über DB-Knoten hinweg. - Gleichmäßige Verteilung, da Codes bei Base62-Kodierung effektiv gleichmäßig über den ID-Raum verteilt sind. Caching-Strategie - Primär: CDN/Edge-Caching für Umleitungen + regionaler In-Memory-Cache. 1) CDN: - Cache 301/302-Antworten, die nach Pfad (Code) mit TTL (z. B. 5–60 Minuten oder expire_at beachten) indiziert sind. - Für extrem heiße Links kann CDN den Großteil des Traffics global absorbieren. 2) Regionaler Cache (Redis/Memcached): - Schlüssel: code - Wert: long_url + expire_at + status - TTL: min(default_ttl, expire_at-now) - Verdrängung: LRU oder LFU (bevorzugt LFU für verzerrte Popularität). Erwartete Trefferquote - URL-Zugriffe sind typischerweise stark verzerrt (Zipf). Mit CDN + regionalem Cache ist eine Trefferquote von 95–99 % für Umleitungen machbar; selbst 90 % sind hilfreich. - Cache-Aufwärmung: Beim Schreiben die Zuordnung in den Cache pushen; auch negatives Caching für Misses (kurze TTL), um wiederholte DB-Treffer für ungültige Codes zu reduzieren. Erfüllung der <50ms p95 Redirect-Latenz - Kritischer Pfad für Cache-Treffer: - Edge/CDN-Treffer: oft <20ms. - Regionaler Cache-Treffer: LB + App + Redis-Lookup + Antwort: typischerweise 5–15ms innerhalb der Region. - Bei Cache-Miss: - Einzelner DB-Lesevorgang von lokaler regionaler Replik: Ziel 5–20ms. - Redirect-Server über Multi-Region + Edge nah an den Benutzern halten. - Keep-Alive, HTTP/2 zwischen Komponenten, Connection Pooling zu Redis/DB verwenden. - Asynchrone Analysen vermeiden; Klickereignisse asynchron an eine Warteschlange senden. Schreibleistung - Schreibvorgänge sind im Vergleich zu Lesevorgängen gering; Bursts trotzdem bewältigen. - Schreibfluss: 1) ID/Code generieren 2) In DB schreiben (Quorum/Mehrheit innerhalb der Region) 3) Write-Through zum Cache 4) Antwort zurückgeben - Optional: Duplikate identischer long_url durch Speichern eines Hash->Code-Index deduplizieren (Kompromiss; siehe F). E) Zuverlässigkeit und Fehlertoleranz Verfügbarkeitsziel: 99,9% - Multi-AZ innerhalb jeder Region für alle zustandsbehafteten Komponenten. - Mindestens zwei Regionen aktiv-aktiv für Redirect-Traffic. Replikationsstrategie - Innerhalb der Region: Replikationsfaktor 3 über AZs hinweg. - Regionenübergreifend: - Asynchrone Replikation für url_mapping, um die Schreiblatenz niedrig und die Verfügbarkeit hoch zu halten. - Umleitungen werden aus der lokalen Region bedient; wenn die lokale Zuordnung aufgrund von Replikationsverzögerungen fehlt, Fallback auf eine andere Region (siehe unten). Umgang mit Rechenzentrums-/Regionenausfällen (anmutige Verschlechterung) - Globale Load Balancer Health Checks verwenden: - Wenn eine Region nicht fehlerfrei ist, Traffic an die nächstgelegene fehlerfreie Region weiterleiten. - Für Redirect-Anfragen: - Wenn der regionale Cache/DB beeinträchtigt ist, kann der Redirect-Dienst: 1) Cache versuchen 2) Lokale DB versuchen 3) Wenn lokale DB nicht verfügbar ist, einen Remote-Region-Leseendpunkt abfragen (mit striktem Timeout) oder eine regionenübergreifende Lese-Replik verwenden. 4) Wenn alles fehlschlägt, ein schnelles 503 mit Retry-After zurückgeben (anmutiges Scheitern). - Für Schreibanfragen: - Lokale regionale Schreibvorgänge bevorzugen; wenn die Region ausgefallen ist, Failover zu einer anderen Region. - ID-Zuweisung: Jede Region hat ihren eigenen ID-Block-Namensraum (oder verwendet Regionsbits in Snowflake), um Konflikte während des Failovers zu vermeiden. CAP-Theorem-Kompromiss - Verfügbarkeit über starke Konsistenz für globale Operationen wählen: - Umleitungen müssen hochverfügbar sein; veraltete Lesevorgänge sind kurzzeitig akzeptabel. - Regionenübergreifende Replikation ist asynchron: Eine neu erstellte Kurz-URL wird möglicherweise für ein kurzes Zeitfenster in einer anderen Region nicht aufgelöst. Milderungen: - Nach der Erstellung eine Kurz-URL zurückgeben, die auf derselben Regionsdomäne gehostet wird (oder Edge verwenden, das für die ersten paar Minuten zur Ursprungsregion weiterleitet). - Bei der Erstellung optional einen synchronen Schreibvorgang in zwei Regionen für Premium-/Enterprise-Kunden durchführen (höhere Latenz/Kosten). Backups und Notfallwiederherstellung - Periodische Snapshots + inkrementelle Backups in Objektspeicher. - Regelmäßige Wiederherstellungsübungen. F) Kompromissdiskussion 1) ID-basierte Codegenerierung vs. zufällige Tokens - Gewählt: ID-basiert (Bereich vermietet/Snowflake) + Base62. - Vorteile: - Keine Kollisionen, keine Notwendigkeit für Wiederholungsschleifen. - Vorhersehbare Kapazitätsplanung und einfachere DB-Beschränkungen. - Schnellere Schreibvorgänge. - Nachteile: - Codes sind erratbar/sequenziell (Sicherheit durch Obskurität wird nicht geboten). Milderung: - Optionale „gesalzene Permutation“ (z. B. Feistel-Netzwerk) über die numerische ID vor der Base62-Kodierung hinzufügen, um Codes nicht-sequenziell zu machen und gleichzeitig die Eindeutigkeit zu erhalten. 2) Asynchrone regionenübergreifende Replikation (AP) vs. synchrone Multi-Region (CP) - Gewählt: asynchrone regionenübergreifende Replikation. - Vorteile: - Geringere Schreiblatenz, höhere Verfügbarkeit bei Teilausfällen. - Bessere Fähigkeit, Umleitungen auch bei beeinträchtigter Region zu bedienen. - Nachteile: - Eventual Consistency: kurzes Fenster, in dem eine neu erstellte URL in einer anderen Region möglicherweise nicht lesbar ist. Milderung: - Read-Repair/Fallback zur Ursprungsregion für frische Links; optionaler Dual-Write für Kunden mit hohem SLA. 3) Starkes Caching/CDN vs. immer DB treffen - Gewählt: CDN + regionaler Cache. - Vorteile: - Erfüllt leicht <50ms p95 und reduziert die DB-Last drastisch. - Bewältigt Traffic-Spitzen für virale Links. - Nachteile: - Komplexität der Cache-Invalidierung (z. B. gelöschte/abgelaufene Links). Milderung: - Kurze TTLs, expire_at beachten und explizites Löschen bei Löschung für CDN, wo unterstützt; Statusflags und negatives Caching sorgfältig verwenden.

A) API-Design: 1. **URL-Verkürzen-Endpunkt:** * **Methode:** `POST` * **Pfad:** `/shorten` * **Anforderungsrumpf (JSON):** ```json { "long_url": "string", "custom_short_code": "string" (optional), "expires_at": "ISO 8601 datetime string" (optional) } ``` * **Antwortrumpf (JSON - 201 Created):** ```json { "short_url": "string", "long_url": "string", "custom_short_code": "string" (falls angegeben), "expires_at": "ISO 8601 datetime string" (falls angegeben) } ``` * **Fehlerantworten:** * `400 Bad Request`: Ungültiges `long_url`-Format oder fehlend. * `409 Conflict`: `custom_short_code` existiert bereits. * `500 Internal Server Error`: Allgemeiner Serverfehler. 2. **Kurz-URL-Weiterleitungs-Endpunkt:** * **Methode:** `GET` * **Pfad:** `/{shortCode}` * **Antwort:** `302 Found` HTTP-Weiterleitung zur `long_url`. * **Fehlerantworten:** * `404 Not Found`: `shortCode` existiert nicht oder ist abgelaufen. * `500 Internal Server Error`: Allgemeiner Serverfehler. B) Datenmodell und Speicherung: **Speicherwahl:** Eine geshardete relationale Datenbank (z. B. PostgreSQL) mit Lese-Replikaten. **Begründung:** * **Starke Konsistenz für Schreibvorgänge:** Wesentlich für die Gewährleistung der Einzigartigkeit von Kurzcodes. Relationale Datenbanken bieten ACID-Eigenschaften, die für eine zuverlässige Datenintegrität bei der URL-Erstellung entscheidend sind. * **Gut verstandenes Sharding:** PostgreSQL unterstützt verschiedene Sharding-Strategien (z. B. bereichsbasiert, hashbasiert), um die Schreiblast zu verteilen und horizontal zu skalieren. * **Effiziente Indizierung:** B-Tree-Indizes sind für Punkt-Lookups auf `short_code` hocheffizient, was die primäre Operation für Weiterleitungen ist. * **Lese-Replikate:** Unterstützt problemlos die Skalierung von Lesevorgängen (Weiterleitungen) durch Hinzufügen mehrerer schreibgeschützter Replikate. * **Reife und Ökosystem:** Robuste Werkzeuge für Überwachung, Sicherung und Wiederherstellung. **Schema:** `urls`-Tabelle: * `id`: BIGINT, Primärschlüssel, automatisch inkrementierend (oder generiert von einem verteilten ID-Dienst). Wird als Grundlage für den Kurzcode verwendet. * `short_code`: VARCHAR(7), Eindeutiger Index, NICHT NULL. Der tatsächliche kurze String, der in der URL verwendet wird. * `long_url`: TEXT, NICHT NULL. Die ursprüngliche lange URL. * `created_at`: TIMESTAMP WITH TIME ZONE, NICHT NULL, Standard: `NOW()`. * `expires_at`: TIMESTAMP WITH TIME ZONE (nullable). Wann die Kurz-URL ablaufen soll. * `user_id`: BIGINT (nullable, Fremdschlüssel zu einer `users`-Tabelle, falls Benutzerkonten unterstützt werden). **Speicherschätzung (über 10 Jahre):** * **Volumen:** 100 Millionen neue URLs/Monat * 12 Monate/Jahr * 10 Jahre = 12 Milliarden URLs. * **Datensatzgrößen-Schätzung:** * `id`: 8 Bytes (BIGINT) * `short_code`: 7 Bytes (VARCHAR(7)) * `long_url`: Durchschnittlich 100 Bytes (TEXT, variable Länge) * `created_at`: 8 Bytes (TIMESTAMP) * `expires_at`: 8 Bytes (TIMESTAMP) * Gesamt pro Datensatz: ~131 Bytes. * **Größe der Rohdaten:** 12 Milliarden Datensätze * 131 Bytes/Datensatz = 1,572 TB. * **Mit Indizes und Overhead:** Berücksichtigt man Indizes (insbesondere auf `short_code` und `id`), Replikation und Datenbank-Overhead, könnten die Gesamtspeicherkosten über 10 Jahre etwa 3-5 TB betragen. Dies ist mit einer geshardeten Datenbankarchitektur gut handhabbar. C) Generierung von Kurz-URLs: **Algorithmus:** 1. Wenn eine neue Anfrage zur URL-Verkürzung eingeht, wird eine eindeutige, monoton steigende ID abgerufen. Diese ID kann generiert werden durch: * **Datenbank-Auto-Inkrement:** Bei Verwendung einer geshardeten Datenbank kann jeder Shard mit einem eindeutigen ID-Bereich konfiguriert werden (z. B. Shard 1 verwendet IDs 1, 11, 21..., Shard 2 verwendet 2, 12, 22...). * **Verteilter ID-Generator:** Ein dedizierter Dienst wie Snowflake (oder eine ähnliche benutzerdefinierte Implementierung) kann global eindeutige, zeitlich geordnete 64-Bit-Integer generieren. 2. Diese eindeutige ID wird dann in eine Base62-Zeichenkette umgewandelt. Base62 verwendet 62 Zeichen (0-9, a-z, A-Z), was eine kompakte Darstellung ermöglicht. **Kollisionsvermeidung:** * Durch die Ableitung des Kurzcodes von einer global eindeutigen ID (entweder über geshardetes Auto-Inkrement oder einen verteilten ID-Generator) werden Kollisionen inhärent vermieden. Jede generierte ID ist eindeutig, und ihre Base62-Darstellung wird ebenfalls eindeutig sein. * Bei Anfragen für `custom_short_code` versucht das System, den vom Benutzer bereitgestellten Code einzufügen. Wenn ein Konflikt auftritt (wegen eines vorhandenen Eintrags), wird dem Benutzer ein `409 Conflict`-Fehler zurückgegeben. **Zeichensatz und Länge:** * **Zeichensatz:** Base62 (0-9, a-z, A-Z) – 62 eindeutige Zeichen. * **Länge:** Anfangs 6 Zeichen. **Mathematische Begründung für die Schlüsseleräumungseignung:** * **Erforderliches Volumen:** 12 Milliarden eindeutige URLs über 10 Jahre. * **Schlüsseleräumung mit 6 Zeichen:** 62^6 = 56.800.235.584 (ungefähr 56,8 Milliarden eindeutige Codes). * Diese Schlüsseleräumung (56,8 Milliarden) ist deutlich größer als die erforderlichen 12 Milliarden URLs und bietet ausreichend Spielraum für Wachstum und Gewährleistung der Eignung für mindestens 10 Jahre. Sollte der Dienst diese überschreiten, könnte die Länge des Kurzcodes auf 7 Zeichen erweitert werden, was 62^7 (ungefähr 3,5 Billionen) eindeutige Codes liefert. D) Skalierung und Leistung: **Skalierung von Lesevorgängen (Weiterleitungen):** * **Verteilter Cache (z. B. Redis Cluster):** Der primäre Skalierungsmechanismus für Lesevorgänge. `short_code` zu `long_url`-Zuordnungen werden in einem hochverfügbaren, verteilten Cache gespeichert. Angesichts des Lese/Schreib-Verhältnisses von 100:1 werden die meisten Weiterleitungsanfragen direkt aus dem Cache bedient. * **Datenbank-Lese-Replikate:** Die geshardeten PostgreSQL-Instanzen werden mehrere Lese-Replikate haben. Bei einem Cache-Miss fällt die Anfrage auf ein Lese-Replikat zurück. Load Balancer verteilen Abfragen über diese Replikate. * **Content Delivery Network (CDN):** Obwohl die 302-Weiterleitung nicht direkt gecached wird, kann ein CDN statische Assets bereitstellen und potenziell das Routing für anfängliche Anfragen optimieren, wodurch die Latenz für geografisch verteilte Benutzer reduziert wird. **Skalierung von Schreibvorgängen (Verkürzungen):** * **Datenbank-Sharding:** Die Kernstrategie. Daten werden über mehrere PostgreSQL-Instanzen basierend auf einem Sharding-Schlüssel (z. B. der `id`, von der der `short_code` abgeleitet wird) partitioniert. Dies verteilt die Schreiblast und die Speicheranforderungen. * **Verbindungspooling:** Verwaltet effizient Datenbankverbindungen, um den Overhead zu reduzieren. * **Asynchrone Verarbeitung:** Für nicht kritische Aufgaben (z. B. Analysen, Protokollierung, Aktualisierung von Statistiken) können Nachrichtenwarteschlangen (z. B. Kafka, RabbitMQ) Arbeit vom primären Schreibpfad entlasten und die Reaktionsfähigkeit verbessern. **Caching-Strategie:** * **Cache-Typ:** Verteilter In-Memory-Cache (z. B. Redis Cluster). * **Gespeicherte Daten:** `short_code` zu `long_url`-Zuordnungen. * **Cache-Befüllung:** Bei einer erfolgreichen URL-Verkürzung wird die neue Zuordnung sowohl in die Datenbank als auch in den Cache geschrieben. Bei einem Cache-Miss während einer Weiterleitung wird die Zuordnung aus der Datenbank abgerufen und dann in den Cache geschrieben (Write-Through/Write-Aside). * **Eviction-Richtlinie:** LRU (Least Recently Used) ist geeignet. Beliebte URLs bleiben im Cache, während weniger häufig aufgerufene zur Platzschaffung verdrängt werden. Time-to-Live (TTL) kann ebenfalls angewendet werden, insbesondere für URLs mit einem `expires_at`-Feld. * **Erwartete Trefferquote:** Angesichts des Lese/Schreib-Verhältnisses von 100:1 und der Potenzgesetzverteilung des URL-Zugriffs (ein kleiner Prozentsatz der URLs macht einen großen Prozentsatz des Traffics aus) ist eine Cache-Trefferquote von 90-95 %+ sehr gut erreichbar, was die Datenbanklast erheblich reduziert. **Erfüllung der p95-Latenzanforderung von 50 ms:** * **Hohe Cache-Trefferquote:** Die überwiegende Mehrheit der Weiterleitungsanfragen wird vom verteilten Cache bedient, der in Millisekunden im einstelligen Bereich antworten kann. * **Optimierter Datenbankzugriff:** Bei Cache-Misses stellt die effiziente Indizierung auf `short_code` in der geshardeten Datenbank schnelle Lookups sicher. * **Nähe und Netzwerk:** Bereitstellung von Diensten in mehreren Regionen nahe bei den Benutzern und Nutzung von Hochgeschwindigkeits-Netzwerkinfrastruktur mit geringer Latenz. * **Lastverteilung:** Effiziente Verteilung von Anfragen auf gesunde Service-Instanzen und Datenbank-Replikate. * **Zustandslose Anwendungsserver:** Ermöglicht eine einfache horizontale Skalierung der API-Schicht und stellt sicher, dass genügend Kapazität vorhanden ist, um Spitzenlasten zu bewältigen, ohne zu einem Engpass zu werden. D) Zuverlässigkeit und Fehlertoleranz: **Rechenzentrumsfehler:** * **Multi-Region-Bereitstellung:** Der gesamte Dienst (API-Server, Cache-Cluster, Datenbank-Shards) wird in mindestens zwei geografisch getrennten Rechenzentren/Regionen bereitgestellt. * **Globale Lastverteilung (z. B. DNS-basiertes Verkehrsmanagement):** Leitet den Benutzerverkehr zur nächstgelegenen gesunden Region. Wenn eine Region ausfällt, wird der Verkehr automatisch zur betriebsbereiten Region umgeleitet. * **Automatisches Failover:** Datenbankcluster sind für automatisches Failover innerhalb einer Region (Primär zu Replikat) und über Regionen hinweg (Aktiv-Passiv oder Aktiv-Aktiv-Konfiguration) konfiguriert. **Datenreplikationsstrategie:** * **Datenbank (PostgreSQL):** * **Innerhalb einer Region:** Synchrone Streaming-Replikation wird zwischen der primären Datenbankinstanz und ihren lokalen Replikat(en) verwendet. Dies gewährleistet keinen Datenverlust im Falle eines Ausfalls des Primärsystems innerhalb desselben Rechenzentrums. * **Über Regionen hinweg:** Asynchrone Streaming-Replikation wird vom Primärsystem in der aktiven Region zu einem Replikat in der passiven/Standby-Region verwendet. Dies bietet Disaster-Recovery-Fähigkeiten mit minimalen Leistungsauswirkungen auf den primären Schreibpfad. In einer Aktiv-Aktiv-Konfiguration würde das Primärsystem jeder Region asynchron zum anderen replizieren. * **Verteilter Cache (Redis Cluster):** Daten werden über mehrere Knoten innerhalb jedes Redis-Clusters geshardet und repliziert. Jeder Shard hat ein Primärsystem und mindestens ein Replikat. Im Falle eines Knotenausfalls wird ein Replikat zum Primärsystem befördert. **Kompromisse (CAP-Theorem):** * **Wahl:** Priorisierung von **Verfügbarkeit (A)** und **Partitionstoleranz (P)** gegenüber starker **Konsistenz (C)** für Lesevorgänge (Weiterleitungen), während starke Konsistenz für Schreibvorgänge (Verkürzungen) innerhalb eines Datenbank-Shards beibehalten wird. * **Begründung:** Für einen URL-Verkürzungsdienst ist es wichtiger, dass der Dienst auch bei Netzwerkteilungen oder Rechenzentrumsfehlern verfügbar und reaktionsschnell (geringe Latenz) bleibt. Benutzer erwarten, dass Weiterleitungen schnell funktionieren. * **Wie es erreicht wird:** * **Verfügbarkeit:** Multi-Region-Bereitstellung, globale Lastverteilung, Datenbank-Lese-Replikate und ein hochverfügbarer verteilter Cache stellen sicher, dass Anfragen immer bedient werden können. * **Partitionstoleranz:** Die verteilte Natur des Systems (Sharding, Replikation) bewältigt inhärent Netzwerkteilungen. * **Konsistenz:** Für Schreibvorgänge wird starke Konsistenz innerhalb eines Datenbank-Shards aufrechterhalten. Die regionsübergreifende Replikation ist asynchron, was bedeutet, dass es ein kleines Konsistenzfenster zwischen den Regionen für neu erstellte URLs geben kann. Der Cache dient ebenfalls als Schicht mit eventualer Konsistenz, da er bei Schreibvorgängen und bei Cache-Misses aktualisiert wird. F) Kompromissdiskussion: 1. **Konsistenz vs. Verfügbarkeit für Weiterleitungen (CAP-Theorem):** * **Wahl:** Priorisierung von **Verfügbarkeit** und **Partitionstoleranz** gegenüber **sofortiger starker Konsistenz** für den Weiterleitungspfad. * **Warum:** Das Hauptziel eines URL-Verkürzers ist die Bereitstellung schneller und zuverlässiger Weiterleitungen. Wenn eine neu erstellte URL einige Sekunden braucht, um sich auf alle Lese-Replikate und Caches weltweit zu verteilen, ist dies eine geringfügige Unannehmlichkeit. Wenn das System jedoch auf globale Konsistenz wartet, bevor es eine Weiterleitung bedient, würde dies erhebliche Latenz einführen und die Verfügbarkeit während Netzwerkteilungen oder regionalen Ausfällen verringern. Benutzer würden seltene 404er für eine brandneue URL eher in Kauf nehmen als häufige Timeouts oder langsame Weiterleitungen. * **Opfer:** Ein kleines Fenster der eventualen Konsistenz. Ein Benutzer könnte eine URL in Region A erstellen und wenn er sie sofort von Region B aus aufruft (bevor die asynchrone Replikation abgeschlossen ist), könnte er vorübergehend eine 404 erhalten. In extremen Multi-Region-Ausfallszenarien mit asynchroner Replikation besteht ein geringes Risiko von Datenverlust für sehr neue Schreibvorgänge, wenn die primäre Region katastrophal ausfällt, bevor die Replikation zur sekundären Region abgeschlossen ist. * **Gewinn:** Hohe Verfügbarkeit (99,9 % Betriebszeit) und extrem niedrige Latenz (p95 unter 50 ms) für die überwiegende Mehrheit der Weiterleitungsanfragen, die die häufigsten Operationen sind. Das System bleibt auch dann betriebsbereit und reaktionsschnell, wenn ein Rechenzentrum ausfällt. 2. **Methode zur Generierung von Kurzcodes (Sequentielle ID zu Base62 vs. Hashing der langen URL):** * **Wahl:** Generierung von Kurzcodes durch Umwandlung einer eindeutigen, sequenziell steigenden ID (von einem verteilten ID-Generator oder geshardetem Auto-Inkrement) in Base62. * **Warum:** Diese Methode garantiert Einzigartigkeit durch Design, vereinfacht den Schreibpfad und verbessert die Leistung. Sie vermeidet die Komplexität und den Leistungsaufwand, der mit der Kollisionserkennung und -auflösung verbunden ist, die bei Hash-basierten Ansätzen inhärent sind. * **Opfer:** Die Kurzcodes erscheinen möglicherweise etwas sequenziell (z. B. `abcde1`, `abcde2`) und nicht völlig zufällig. Dies könnte für einige Benutzer ein geringfügiges ästhetisches Problem sein, beeinträchtigt jedoch nicht die Funktionalität. Außerdem erfordert es einen robusten Mechanismus zur verteilten ID-Generierung, der eine Komponente zur Architektur hinzufügt. * **Gewinn:** * **Garantierte Einzigartigkeit:** Keine Kollisionen, wodurch Datenbank-Lookups und Wiederholungsversuche während der Kurzcode-Generierung entfallen, was für einen hohen Schreibdurchsatz (100 Mio./Monat) entscheidend ist. * **Einfacherer Schreibpfad:** Der Prozess der Erstellung einer neuen Kurz-URL ist nach der ID-Generierung ein einfacher Einfügevorgang. * **Vorhersehbare Schlüsseleräumung:** Einfacher zu verwalten und sicherzustellen, dass die Schlüsseleräumung für zukünftiges Wachstum ausreichend ist. * **Flexibilität:** Ermöglicht die mehrfache Verkürzung derselben `long_url`, was zu unterschiedlichen `short_code`s führt, falls gewünscht (z. B. für die Verfolgung verschiedener Kampagnen), was mit einem einfachen Hash der `long_url` nicht möglich ist.