Entwurf eines URL-Kürzungsdienstes

A. Strategie zur Generierung kurzer URLs 1. Anforderungsbasierte Auswahl - Neue Schreibvorgänge: 100 Mio./Monat ≈ 3,3 Mio./Tag ≈ 38,6 Schreibvorgänge/Sek. im Durchschnitt. - Lesevorgänge im Verhältnis 100:1 ≈ 3,3 Mrd./Monat ≈ 1.270 Lesevorgänge/Sek. im Durchschnitt, mit Spitzenwerten wahrscheinlich 10–50x höher. - Wir benötigen kompakte, global eindeutige IDs mit sehr schnellem Nachschlagen. 2. Code-Generierungsansatz Ich würde einen deterministischen ID-Generierungsdienst plus Base62-Kodierung verwenden. Fluss: - Eine global eindeutige numerische ID wird generiert. - Diese Ganzzahl wird mit Zeichen [0-9a-zA-Z] in Base62 kodiert. - Beispiel: 125 -> „21“ in Base62. Warum dieser Ansatz: - Kein Kollisionsrisiko, wenn IDs eindeutig sind. - Sehr schnell zu generieren. - Einfach zu betreiben im Vergleich zur Kollisionsprüfung zufälliger Codes. - Vorhersehbares Längenwachstum des Codes. 3. Design des ID-Generators Bevorzugte Option: - Verwenden Sie einen Snowflake-ähnlichen 64-Bit-ID-Generator oder einen zentralisierten Bereichszuweiser. - ID-Felder können Zeitstempel + Maschinen-ID + Sequenz enthalten, oder wir können App-Servern monoton steigende Bereiche zuweisen. Zwei gute Implementierungen: - Snowflake-ähnliche IDs: dezentral, hoher Durchsatz, geringe Koordination. - Bereichszuweisung aus dem Metadatenspeicher: Jeder Schreibknoten least einen Block von IDs, z. B. 1 Mio. IDs auf einmal. Ich bevorzuge die Bereichszuweisung zur Vereinfachung, da der Schreibdurchsatz moderat ist. Jeder Schreibserver kann IDs lokal aus seinem zugewiesenen Bereich generieren und vermeidet so eine zentrale Abhängigkeit. 4. Kodierungsschema und erwartete Länge Base62-Kapazität: - 62^6 ≈ 56,8 Mrd. - 62^7 ≈ 3,52 Billionen Gesamte Links über 5 Jahre: - 100 Mio./Monat * 60 Monate = 6 Mrd. Links Daher reichen 6 Base62-Zeichen für langfristige Spielräume nicht aus, wenn IDs global dicht genutzt werden, aber 7 Zeichen sind mehr als genug. Erwartete Länge: - Beginnen Sie mit 6 Zeichen für die frühe Lebensdauer, falls gewünscht. - In der Praxis standardisieren Sie auf 7 Zeichen, um die Implementierung einfach zu halten und Längenänderungen bei den Erwartungen der Benutzer zu vermeiden. 5. Kollisionsbehandlung Mit deterministischen eindeutigen IDs: - Keine Kollisionen auf Code-Ebene. - Eine eindeutige Datenbankbeschränkung für `short_code` bietet ein letztes Sicherheitsnetz. - Wenn ein sehr seltener Duplikat aufgrund eines Softwarefehlers oder einer ID-Fehlkonfiguration beobachtet wird, generieren Sie eine neue ID und lösen Sie einen Alarm aus. 6. Erschöpfungsstrategie - 7-stellige Base62 bietet 3,52 Billionen Kombinationen, weit mehr als die benötigten 6 Milliarden in 5 Jahren. - Wenn die zukünftige Skalierung erheblich wächst, unterstützen Sie nahtlos 8-stellige Codes. - Der Weiterleitungsdienst sollte die Code-Länge als variabel behandeln, sodass keine Migrationsprobleme entstehen. 7. Optionale benutzerdefinierte Aliase Wenn das Produkt benutzerdefinierte Aliase unterstützt: - Speichern Sie in derselben Zuordnungstabelle mit erzwungener Eindeutigkeit. - Reservieren Sie blockierte Wörter und missbräuchliche Begriffe. - Wenden Sie strengere Ratenbegrenzungen an, da benutzerdefinierte Aliase ein Engpass sind. B. Datenspeicherung 1. Auswahl der primären Datenbank Verwenden Sie einen verteilten, hochverfügbaren Key-Value-Speicher für die URL-Zuordnung, wie z. B.: - DynamoDB / Bigtable / Cassandra Warum: - Das primäre Zugriffsmuster ist eine einfache Schlüssel-Nachschlageoperation nach `short_code`. - Benötigt horizontale Skalierung, hohe Verfügbarkeit und Multi-Replika-Lesevorgänge. - Schreibvorgänge sind moderat, Lesevorgänge dominieren. - Key-Value-Zugriff ist ideal für Weiterleitungslatenzen von unter 50 ms. Ich würde konzeptionell eine DynamoDB-ähnliche oder Cassandra-ähnliche Speicherung wählen: - Partitionierung nach `short_code`-Hash. - Replikation über Verfügbarkeitszonen hinweg. - Optimiert für schnelle Punkt-Lesezugriffe. 2. Sekundäre Speicher - Relationale Datenbank für Metadaten der Steuerungsebene, Abrechnung, Benutzer, Domänen, Richtlinien. - Objektspeicher + Data Lake für Analysen/Klickprotokolle. - Optionaler Such-/Indexspeicher, wenn Administratoren nach Ersteller, Datum, Tags usw. abfragen müssen. 3. Schema-Design Primäre Zuordnungstabelle: - `short_code` (PK) - `destination_url` - `created_at` - `expires_at` (optional) - `owner_id` (optional) - `status` (aktiv, deaktiviert, gelöscht) - `redirect_type` (301/302) - `checksum` oder `normalized_url`-Hash (optional) - `metadata_pointer` (optional) Optionale Deduplizierungstabelle, wenn das Produkt für denselben langen URL denselben kurzen URL pro Mandant zurückgeben möchte: - `dedup_key` = hash(tenant_id + canonicalized_url) - `short_code` Dies ist optional; viele URL-Shortener deduplizieren nicht global, da die Semantik je nach Benutzer, Kampagne oder Analyseanforderungen unterschiedlich ist. 4. Speicherabschätzung über 5 Jahre Gesamte Links: - 6 Mrd. Datensätze Grober Schätzwert pro Datensatz: - `short_code`: ~8 Bytes Rohäquivalent - `destination_url`: durchschnittlich 200 Bytes angenommen - Zeitstempel/Status/Flags: ~24 Bytes - Replikations-/Versions-/Index-Overhead: erheblich in realen Systemen - Speicher-Engine-Overhead: insgesamt effektiv ~350–500 Bytes pro Datensatz in der primären DB angenommen Bei 400 Bytes/Datensatz: - 6 Mrd. * 400 Bytes = 2,4 TB rohe logische Daten Mit Replikationsfaktor 3: - 7,2 TB Indizes, Kompaktierungs-Overhead, Tombstones, Metadaten, operativer Spielraum hinzugefügt: - Planen Sie 10–15 TB primären Speicher über 5 Jahre ein Analysen/Klickprotokolle sind viel größer als Zuordnungen. Bei 100 Lesevorgängen pro Schreibvorgang: - 600 Mrd. Weiterleitungen über 5 Jahre Wenn jedes Klickprotokoll-Ereignis im Durchschnitt selbst nur 100 Bytes komprimiert wäre, wären das ~60 TB komprimiert, wahrscheinlich viel mehr mit reichhaltigeren Feldern. Daher sollten Protokolle im günstigen Objektspeicher und nicht in der Serving-Datenbank gespeichert werden. 5. Partitionierungs-/Sharding-Strategie Sharding der primären Tabelle: - Partitionsschlüssel: `short_code` oder hash(`short_code`) - Gleichmäßig verteilt, da IDs aus gut verteilten numerischen IDs oder entsprechend gemischten Bereichs-IDs kodiert werden Wichtiger Hinweis: - Reine sequentielle IDs können in einigen Datenbanken Hot Partitions erstellen, wenn die Schlüssel-Lokalität wichtig ist. - Um dies zu vermeiden, entweder: 1. Hashen Sie den `short_code` für die Partitionsplatzierung, oder 2. Verwenden Sie IDs mit genügend Entropie in den unteren Bits, oder 3. Präfix mit Shard-Bits vor der Base62-Kodierung Ich würde explizit Hash-Partitionierung auf `short_code` durchführen, um eine gleichmäßige Verteilung zu gewährleisten. C. Read Path Architektur 1. Read Path Übersicht Anforderungsfluss: - Benutzer ruft https://sho.rt/abc1234 auf - DNS leitet zum nächstgelegenen Edge/CDN weiter - CDN leitet an den regionalen Weiterleitungsdienst weiter, wenn kein Cache-Treffer vorliegt - Der Weiterleitungsdienst prüft den In-Memory/Redis-Cache - Bei Cache-Miss wird aus dem verteilten KV-Speicher gelesen - Gibt HTTP 301/302 mit `Location`-Header zurück - Asynchrone Emission eines Klickereignisses an die Analyse-Pipeline 2. Erreichen von <50ms p95 Latenz Der Weiterleitungspfad muss extrem leichtgewichtig sein. Latenzbudget-Beispiel: - Edge/CDN-Routing: klein, geografisch lokal - Anwendungsverarbeitung: 1–3 ms - Redis/In-Memory-Cache-Treffer: 1–5 ms - DB-Miss-Pfad innerhalb der Region: typisch 5–15 ms - Gesamte p95 unter 50 ms sind mit regionalem Serving und aggressivem Caching erreichbar 3. Caching-Schichten Schicht 1: CDN/Edge-Caching - Cache-Weiterleitungsantworten für beliebte Links am Edge. - Sehr effektiv, da viele beliebte Kurzlinks wiederholt aufgerufen werden. - Verwenden Sie `Cache-Control`-Header mit TTL, z. B. Minuten bis Stunden, abhängig von der Änderbarkeit. - Wenn Links schnell deaktiviert werden können, wählen Sie eine kürzere TTL oder unterstützen Sie das Leeren des Caches. Schicht 2: Anwendungs-lokaler Cache - Jeder Weiterleitungsknoten speichert einen LRU-Cache von beliebten Zuordnungen. - Ultra-niedrige Latenz, vermeidet Netzwerk-Hop zu Redis. - Gut für die am häufigsten angeforderten Codes. Schicht 3: Verteilter Cache (Redis/Memcached) - Gemeinsamer Cache für die regionale Flotte. - Speichert `short_code` -> `destination_url`, Status, Weiterleitungstyp. - TTL kann für unveränderliche Links lang sein; kürzer für veränderliche/admin-kontrollierte Links. 4. Replikationsstrategie für Lesevorgänge - Multi-AZ-Replikate innerhalb jeder Region. - Lesevorgänge von lokalen regionalen Speicherreplikaten bedienen. - Aktiv-aktiv über mehrere Regionen hinweg für globalen Traffic. - Verwenden Sie Geo-DNS oder Anycast, um zur nächstgelegenen gesunden Region zu leiten. 5. Cache-Befüllungsstrategie - Read-through bei Miss: Die Anwendung ruft die DB ab, befüllt Redis und den lokalen Cache. - Negativ-Caching für nicht existierende/deaktivierte Codes mit kurzer TTL, um Missbrauch und Tippfehler-Stürme abzufangen. - Cache vorwärmen für Trend-Links, falls aus Analysen bekannt. 6. Weiterleitungssemantik - Standardmäßig 302, wenn das Ziel sich ändern kann oder wenn Analyse-/Tracking-Richtlinien Flexibilität erfordern. - 301 für permanente Links, bei denen Clients und CDNs aggressiv cachen können. - Produktentscheidung kann beide Optionen anbieten. 7. Missbrauchshandhabung im Read Path - Ratenbegrenzung nach IP / ASN / Token für verdächtige Hochgeschwindigkeitsanfragen. - WAF und Bot-Filter am CDN. - Schutz des Ursprungs vor Brute-Force-Scans von Kurzcodes. D. Write Path Architektur 1. Write Path Übersicht Anforderungsfluss: - Client sendet lange URL und optionale Metadaten/benutzerdefinierten Alias. - API-Gateway authentifiziert und begrenzt die Rate. - URL-Validierung und -Normalisierung erfolgen in der zustandslosen App-Schicht. - Die App erhält/generiert einen Kurzcode. - Speichert die Zuordnung im primären KV-Speicher. - Befüllt Caches asynchron oder synchron für sofortige Verfügbarkeit. - Emission eines Erstellungsereignisses an eine Warteschlange für Analysen, Missbrauchsscans und nachgelagerte Indizierung. 2. Kapazität 100 Mio./Monat sind für moderne Systeme nicht hoch: - Durchschnittlich ~39 Schreibvorgänge/Sek. - Selbst 100-facher Burst sind nur wenige tausend Schreibvorgänge/Sek. Die Hauptziele sind daher Zuverlässigkeit, Idempotenz und betriebliche Einfachheit und nicht extremer Schreibdurchsatz. 3. Validierungsschritte - URL-Syntax validieren. - Erlaubte Protokolle erzwingen, normalerweise nur http/https. - Optionale Safe-Browsing- oder Malware-Scans asynchron durchführen; wenn ein Risiko gefunden wird, Link deaktivieren. - URL kanonisieren für optionale Deduplizierungslogik. 4. Warteschlangen und asynchrone Arbeit Verwenden Sie eine dauerhafte Warteschlange oder ein Protokoll wie Kafka/SQS/PubSub für Nebeneffekte: - Analyseereignis für die Erstellung eines neuen Links - Erkennung von Missbrauch/Betrug/Phishing - Cache-Aufwärmung - Suchindizierung - Benachrichtigungs-/Audit-Pipeline Der kritische Pfad sollte nur das enthalten, was zur Erstellung der Zuordnung und zur Rückgabe der gekürzten URL erforderlich ist. 5. Konsistenzmodell Für die Erstellungsantwort verwenden Sie Write-after-Create-Konsistenz für den neuen Kurzcode: - Sobald die API Erfolg zurückgibt, sollte die Weiterleitung sofort funktionieren. Wie: - Speichern Sie die Zuordnung in einem Quorum/Leader in der primären DB, bevor Sie sie bestätigen. - Optional Write-through zu Redis nach DB-Commit. - Der Weiterleitungspfad greift bei Cache-Miss auf die DB zurück, sodass Verzögerungen bei der Cache-Weitergabe die Korrektheit nicht beeinträchtigen. 6. Idempotenz Unterstützen Sie Idempotenzschlüssel für API-Clients, um Duplikate von Links bei Wiederholungsversuchen zu vermeiden. - Speichern Sie `request_id` -> `short_code` für eine begrenzte TTL in einem schnellen Speicher. - Besonders nützlich für mobile/Netzwerk-Wiederholungsszenarien. 7. Ratenbegrenzung - Kontingente pro Benutzer/API-Schlüssel zur Kontrolle von Missbrauch. - Stärkere Beschränkungen für Anfragen mit benutzerdefinierten Aliasen. - Globale Schutzmaßnahmen, um durch Angriffe induzierte Schreibverstärkung zu verhindern. E. Zuverlässigkeit und Fehlertoleranz 1. Verfügbarkeitsziel: 99,9% 99,9 % Betriebszeit erlauben etwa 43,8 Minuten Ausfallzeit pro Monat. Dies ist mit Multi-AZ-Bereitstellung und regionalem Failover erreichbar. 2. Fehlerbehandlung Knotenausfall: - Zustandlose App-Knoten hinter Load Balancern; fehlerhafte Instanzen werden automatisch ersetzt. - Lokale Caches sind wegwerfbar. - Redis wird als hochverfügbarer Cluster/Sentinel-Modus bereitgestellt. AZ-Ausfall: - App-Schicht über mindestens 3 AZs verteilt. - Primäre DB über AZs repliziert. - Load Balancer entfernt fehlerhafte AZ. Regionale/DC-Ausfall: - Aktiv-aktive Lese-Bereitstellung über mehrere Regionen hinweg. - Daten werden asynchron oder nahezu synchron über Regionen hinweg repliziert, abhängig von den Fähigkeiten der DB. - DNS/Traffic-Manager leitet Benutzer zur gesunden Region um. 3. Datendauerhaftigkeit - Primäre DB-Replikationsfaktor 3 über AZs hinweg. - Periodische Snapshots/Backups in Objektspeicher. - WAL/Commit-Log-Archivierung, falls unterstützt. - Cross-Region-Backup-Kopien für die Notfallwiederherstellung. 4. Backup- und Wiederherstellungsstrategie - Tägliche vollständige Snapshots plus inkrementelle Backups. - Point-in-Time-Wiederherstellung für versehentliches Löschen/Beschädigung. - Regelmäßige Wiederherstellungsübungen in Staging, um RTO/RPO zu überprüfen. - Backup-Aufbewahrung im Einklang mit der 5-Jahres-Zugänglichkeitsanforderung und Compliance-Anforderungen. Angemessene Ziele: - RPO: Minuten bis 1 Stunde, abhängig vom Cross-Region-Replikationsmodell - RTO: unter 1 Stunde für regionales Failover, länger für vollständige Speicherwiederherstellung, aber das sollte selten sein 5. Cache-Invalidierungsstrategie Wenn Links größtenteils unveränderlich sind, ist das Caching einfach. Für veränderliche Links (deaktivieren/Ziel ändern/Ablaufdatum ändern): - Zuerst DB aktualisieren. - Invalidierungsereignis veröffentlichen. - Redis-Schlüssel und lokale Cache-Einträge löschen. - CDN-Cache leeren, wenn Edge-Caching für diesen Code verwendet wird. - Verwenden Sie eine begrenzte TTL, damit der veraltete Cache sich selbst heilt, auch wenn die Invalidierung fehlschlägt. 6. Schutz vor Datenbeschädigung und Missbrauch - DB-Eindeutigkeitsbeschränkungen für `short_code`. - Prüfsummen/Versionsfelder für Datensätze. - Audit-Protokolle für Administratoraktionen. - Soft Delete oder deaktivierter Status anstelle von Hard Delete, wo immer möglich. - Malware-/Phishing-Scan- und Takedown-Tools. F. Wichtige Kompromisse 1. Deterministische ID-Generierung vs. zufällige Kurzcodes Optionen: - Deterministische sequentielle/bereichsbasierte IDs: einfach, keine Kollisionen, kompakt, schnell. - Zufällige Codes: weniger vorhersagbar/aufzählbar, erfordern aber Kollisionsprüfungen und mehr Komplexität. Wahl: - Ich wähle deterministische IDs, kodiert in Base62. Warum: - Einfacher, schneller und betrieblich sicherer für diese Skala. - Kollisionsfrei ohne Wiederholungsschleifen. - Besser geeignet, da der Durchsatz moderat ist und die größte Herausforderung die Latenz beim Lesen ist. Kosten: - Codes können besser aufzählbar/vorhersagbar sein. Milderung: - Ratenbegrenzung, Bot-Erkennung, optional längere/nicht-sequentielle Aliase für sensible Links. 2. Stärkere Konsistenz bei der Erstellung vs. überall eventual consistency Optionen: - Eventual Consistency könnte die Schreiblatenz reduzieren und Multi-Region-Schreibvorgänge vereinfachen. - Starke Bestätigung nach dauerhaftem Schreiben stellt sicher, dass ein zurückgegebener Kurzcode sofort funktioniert. Wahl: - Starke Konsistenz für den Single-Link-Erstellungspfad innerhalb einer Heimatregion; eventual consistency für sekundäre Caches und Cross-Region-Propagation. Warum: - Bessere Benutzererfahrung: Sobald die API zurückkehrt, sollte die Weiterleitung erfolgreich sein. - Das Schreibvolumen ist gering genug, dass wir die Konsistenz beim kritischen Schreibvorgang nicht lockern müssen. 3. Aggressives Edge-Caching vs. schnelle Invalidierung Optionen: - Lange CDN-TTLs maximieren die Leseleistung und reduzieren die Ursprungskosten. - Kurze TTLs machen Deaktivierungs-/Aktualisierungsoperationen schneller übertragbar. Wahl: - Moderate TTL mit explizitem Leeren für veränderliche/admin-verwaltete Links; längere TTL für unveränderliche Links. Warum: - Die meisten gekürzten URLs sind praktisch unveränderlich, daher bietet Caching erhebliche Latenz- und Kostenvorteile. - Aber Missbrauch-Takedowns erfordern eine einigermaßen schnelle Invalidierung. 4. Einfachheit vs. Analyse-Reichtum im Weiterleitungspfad Optionen: - Synchrone Klickprotokollierung bietet sofortige Analysegarantien, erhöht aber die Latenz und die Fehlerkopplung. - Asynchrone Ereignisemission hält Weiterleitungen schnell, aber Analysen können bei Fehlern verzögert sein oder kleine Mengen verlieren. Wahl: - Asynchrone Analysen. Warum: - Die harte SLA des Produkts ist die Weiterleitungslatenz und -verfügbarkeit, nicht die verlustfreie Echtzeit-Analyse. - Der Weiterleitungspfad sollte niemals von nachgelagerten Protokollsystemen blockiert werden. Zusammenfassende Architektur - Kurzcode-Generierung: Bereichsweise zugewiesene oder Snowflake-ähnliche eindeutige 64-Bit-IDs, kodiert in Base62, standardmäßige 7-stellige Codes. - Primärspeicher: verteilte KV-Datenbank, hash-partitioniert nach `short_code`, RF=3, Multi-AZ. - Read Path: CDN + lokaler Cache + Redis + KV-Speicher-Fallback; Multi-Region Aktiv-Aktiv-Lesevorgänge. - Write Path: zustandslose API + dauerhafter DB-Schreibvorgang + asynchrone Warteschlange für Nebeneffekte; Idempotenz und Ratenbegrenzungen. - Zuverlässigkeit: Multi-AZ, Cross-Region-Replikation, Backups, Cache-Invalidierungsereignisse, DNS-Failover. - Dieses Design unterstützt problemlos 100 Mio. neue URLs/Monat, ein Lese-/Schreibverhältnis von 100:1, 5-Jahres-Aufbewahrung, 99,9 % Betriebszeit und Weiterleitungen unter 50 ms p95.

## Design einer URL-Verkürzungsdienstes Dieses Dokument beschreibt das Design eines URL-Verkürzungsdienstes, der 100 Millionen neue URLs pro Monat, ein Lese-Schreib-Verhältnis von 100:1, eine Datenspeicherung von 5 Jahren, eine Verfügbarkeit von 99,9 % und eine Weiterleitungs-Latenz von unter 50 ms im 95. Perzentil bewältigen kann. ### A. Strategie zur Generierung kurzer URLs **Kodierungsschema**: Wir verwenden die Base62-Kodierung (0-9, a-z, A-Z). Dieses Schema ist URL-sicher und bietet eine kompakte Darstellung für eindeutige Bezeichner. **Erwartete URL-Länge**: Über 5 Jahre muss der Dienst 100 Millionen URLs/Monat * 12 Monate/Jahr * 5 Jahre = 6 Milliarden eindeutige URLs unterstützen. Eine 6-stellige Base62-Zeichenkette bietet 62^6 = 56.800.235.584 mögliche eindeutige Schlüssel, was für 6 Milliarden URLs mehr als ausreichend ist. Wir beginnen mit 6 Zeichen und haben die Flexibilität, auf 7 Zeichen zu erweitern (62^7 ≈ 352 Milliarden Schlüssel), falls der Schlüsselraum jemals erschöpft ist. **Generierungsmethode**: Wir werden einen **Key Generation Service (KGS)** einsetzen. Dieser Dienst ist für die Generierung eindeutiger, monoton steigender numerischer IDs verantwortlich. Diese IDs werden dann Base62-kodiert, um die Kurz-URL-Codes zu erzeugen. Der KGS kann einen verteilten ID-Generierungsalgorithmus verwenden (z. B. einen modifizierten Snowflake ID-Generator oder einen dedizierten Dienst, der einen Zähler inkrementiert und ID-Blöcke an mehrere KGS-Instanzen vorab zuweist, um Konflikte zu vermeiden). Dieser Ansatz garantiert Eindeutigkeit und vermeidet Kollisionen durch Design, wodurch Datenbankabfragen während der Schlüsselgenerierung entfallen. **Kollisionsbehandlung**: Da der KGS eindeutige numerische IDs generiert, werden Kollisionen von vornherein vermieden. Jede generierte ID ist eindeutig, und ihre Base62-Kodierung wird ebenfalls eindeutig sein. Wenn eine zufällige Generierungsstrategie gewählt würde, würde die Kollisionsbehandlung die Überprüfung der Existenz in der Datenbank und die Neugenerierung bei Kollision beinhalten, was Latenz und Komplexität hinzufügt. **Erschöpfung des Schlüsselraums**: Wie bereits erwähnt, bietet ein 6-stelliger Base62-Schlüssel ausreichend Platz für 6 Milliarden URLs. Sollte der Dienst über diese Kapazität hinauswachsen, würde die Erweiterung der Schlüssellänge auf 7 Zeichen erheblich mehr Kapazität bieten. Der KGS wäre so konzipiert, dass er diesen Übergang nahtlos bewältigt, indem er bei Bedarf längere IDs generiert. ### B. Datenspeicherung **Datenbankauswahl**: Für die Kernzuordnung von `short_code` zu `long_url` verwenden wir einen **verteilten NoSQL-Schlüssel-Wert-Speicher** wie **Apache Cassandra**. Cassandra ist hochgradig skalierbar, fehlertolerant und für Lese- und Schreibvorgänge mit hohem Volumen und geringer Latenz optimiert, was ihn ideal für unsere Lese-lastige Arbeitslast macht. Seine verteilte Natur und die integrierten Replikationsfunktionen gewährleisten hohe Verfügbarkeit und Datenhaltbarkeit. **Speicherschätzung**: * Gesamtzahl der URLs über 5 Jahre: 6 Milliarden. * Jeder Eintrag speichert: * `short_code`: 6-7 Zeichen (ca. 7 Bytes) * `long_url`: Durchschnittlich 100 Zeichen (ca. 100 Bytes) * `created_at`: Zeitstempel (8 Bytes) * `expires_at`: Zeitstempel (8 Bytes, für 5-jährige Aufbewahrung) * `click_count`: Zähler (8 Bytes) * `user_id` (optional): z. B. 36 Bytes für UUID * Gesamt pro Eintrag (konservative Schätzung, einschließlich Overhead): ~150 Bytes. * Gesamter Rohspeicher: 6 Milliarden URLs * 150 Bytes/URL = 900 Milliarden Bytes = 0,9 TB. * Mit einem Replikationsfaktor von 3 (üblich für Cassandra für hohe Verfügbarkeit): 0,9 TB * 3 = **2,7 TB**. **Schema-Design (Cassandra)**: ```sql CREATE TABLE short_urls ( short_code text PRIMARY KEY, -- Partitionsschlüssel für gleichmäßige Verteilung long_url text, created_at timestamp, expires_at timestamp, click_count counter, user_id text ); ``` **Partitionierungs-/Sharding-Strategie**: Cassandra verwaltet nativ die Datenpartitionierung und das Sharding basierend auf dem Primärschlüssel (`short_code`). Der Base62 `short_code` sorgt für eine gute Verteilung der Daten über die Cluster-Knoten, verhindert Hotspots und gewährleistet eine effiziente Datenabfrage. Wir konfigurieren Cassandra mit einem Replikationsfaktor von 3 über mehrere Rechenzentren oder Verfügbarkeitszonen für Fehlertoleranz und hohe Verfügbarkeit. ### C. Lese-Pfad-Architektur **Durchsatz**: Bei 100 Mio. Schreibvorgängen/Monat und einem Lese-Schreib-Verhältnis von 100:1 erwarten wir 10 Milliarden Lesezugriffe/Monat, was durchschnittlich etwa 3.858 Lesezugriffe/Sekunde entspricht. Spitzenlasten könnten 5-10x höher sein und 20.000-40.000 Lesezugriffe/Sekunde erreichen. **Architekturkomponenten**: 1. **Load Balancer (z. B. AWS ELB, Nginx)**: Verteilt eingehende HTTP-Anfragen für kurze URLs auf mehrere Redirect-Service-Instanzen. 2. **Verteilter Cache (z. B. Redis Cluster)**: Dies ist entscheidend für die Erfüllung der Latenz- und Durchsatzanforderungen. Der Cache speichert `short_code`-zu-`long_url`-Zuordnungen. Angesichts des Lese-Schreib-Verhältnisses von 100:1 wird eine sehr hohe Cache-Trefferquote (z. B. 95 %+) erwartet, was die Last auf der Datenbank erheblich reduziert. * **Cache-Invalidierung**: Kurz-URL-Zuordnungen sind im Allgemeinen unveränderlich. Cache-Einträge können eine sehr lange TTL haben oder permanent sein. Wenn eine `long_url` jemals aktualisiert werden muss (selten), wird eine explizite Cache-Invalidierung ausgelöst. 3. **Redirect Service (Anwendungsserver)**: Eine Flotte zustandsloser Anwendungsserver (z. B. in Go, Java oder Node.js) hinter dem Load Balancer. * Bei Erhalt einer Kurz-URL-Anfrage prüft der Dienst zuerst den Redis-Cache. * Bei einem Cache-Treffer wird sofort eine HTTP 301 (Permanent) oder 302 (Temporary) Weiterleitung zur `long_url` ausgegeben. * Bei einem Cache-Miss wird die Cassandra-Datenbank nach dem `short_code` abgefragt. * Nach dem Abruf aus Cassandra wird die Zuordnung in Redis für zukünftige Anfragen gespeichert und dann die Weiterleitung ausgegeben. * Klickzähler werden asynchron aktualisiert (z. B. durch Senden von Nachrichten an eine Kafka-Warteschlange zur Verarbeitung durch einen separaten Analyse-Dienst oder durch direktes Inkrementieren eines Zählers in Cassandra, das atomare Inkremente unterstützt). 4. **Datenbank (Cassandra Cluster)**: Dient als persistenter Speicher für alle URL-Zuordnungen und verarbeitet Cache-Misses. Seine verteilte Natur und Replikation gewährleisten hohe Verfügbarkeit und latenzarme Datenabfrage für die erforderliche Skalierung. **Replikationsstrategien**: * **Anwendungsserver**: Mehrere Instanzen, die über verschiedene Verfügbarkeitszonen verteilt und von Auto-Scaling-Gruppen verwaltet werden. * **Cache**: Redis Cluster mit Master-Replica-Konfigurationen für jeden Shard, um hohe Verfügbarkeit und Datenredundanz zu gewährleisten. * **Datenbank**: Cassandras native Multi-Datacenter-Replikation (z. B. 3-facher Replikationsfaktor über mindestens zwei Rechenzentren) bietet starke Fehlertoleranz und Disaster-Recovery-Fähigkeiten. ### D. Schreib-Pfad-Architektur **Durchsatz**: 100 Millionen neue URLs pro Monat entsprechen durchschnittlich etwa 38 Schreibvorgängen/Sekunde. Spitzenlasten könnten 300-400 Schreibvorgänge/Sekunde erreichen. **Architekturkomponenten**: 1. **Load Balancer**: Verteilt eingehende Anfragen für neue URL-Verkürzungen an die Write-Service-Instanzen. 2. **Write Service (API Gateway/Anwendungsserver)**: * Empfängt die `long_url` vom Benutzer. * Ruft den **Key Generation Service (KGS)** auf, um einen eindeutigen `short_code` zu erhalten. * Erstellt die Zuordnung von `short_code` zu `long_url`. * Veröffentlicht diese Zuordnung in einer **Message Queue (z. B. Apache Kafka)**. Dies entkoppelt den Write-Service von der Datenbank, bietet Pufferung und erhöht die Zuverlässigkeit. * Gibt den generierten `short_code` an den Benutzer zurück. 3. **Key Generation Service (KGS)**: Wie in Abschnitt A beschrieben, generiert dieser Dienst eindeutige numerische IDs und kodiert sie in Base62 `short_code`s. Er kann Schlüsselblöcke vorab generieren, um die Latenz während Spitzen-Schreibzeiten zu minimieren. 4. **Worker-Prozesse (Consumer)**: Ein Pool von Worker-Prozessen verbraucht Nachrichten aus der Kafka-Warteschlange. * Für jede Nachricht schreibt der Worker den `short_code` und die `long_url` in die **Cassandra-Datenbank**. * Anschließend schreibt er sofort die Zuordnung in den **Redis-Cache**, um sicherzustellen, dass die neu erstellte Kurz-URL sofort für Lesezugriffe verfügbar ist. 5. **Datenbank (Cassandra Cluster)**: Speichert die neuen URL-Zuordnungen persistent. **Konsistenzüberlegungen**: * Für die Zuordnung von `short_code` zu `long_url` ist starke Konsistenz erwünscht. Indem wir mit entsprechenden Konsistenzebenen (z. B. `QUORUM`) in Cassandra schreiben und dann sofort den Cache befüllen, stellen wir sicher, dass eine Kurz-URL, sobald sie dem Benutzer zurückgegeben wird, korrekt aufgelöst wird. * Die Verwendung einer Message Queue sorgt für eventual consistency für die Persistenzschicht, aber die sofortige Cache-Aktualisierung stellt sicher, dass der Lese-Pfad für neue URLs konsistent ist. Wenn die Cache-Aktualisierung fehlschlägt, wird der Lese-Pfad schließlich die Datenbank treffen, die konsistent sein wird. ### E. Zuverlässigkeit und Fehlertoleranz **Knotenausfälle**: * **Anwendungsserver (Redirect & Write Services)**: Zustandslos und in Auto-Scaling-Gruppen über mehrere Verfügbarkeitszonen verteilt. Load Balancer leiten den Verkehr automatisch von ausgefallenen Instanzen weg, und neue Instanzen werden gestartet, um sie zu ersetzen. * **Verteilter Cache (Redis Cluster)**: Konfiguriert mit Master-Replica-Replikation. Wenn ein Master-Knoten ausfällt, wird automatisch eine Replica zum Master befördert, was Ausfallzeiten und Datenverlust für gecachte Elemente minimiert. * **Datenbank (Cassandra Cluster)**: Ausgelegt für hohe Verfügbarkeit mit einem Replikationsfaktor von 3 über mehrere Knoten und Rechenzentren. Wenn ein Knoten ausfällt, sind seine Daten auf anderen Replicas verfügbar, und Cassandra kümmert sich automatisch um die Datenreparatur und den Ersatz des ausgefallenen Knotens. * **Key Generation Service (KGS)**: Mit mehreren Instanzen hinter einem Load Balancer bereitgestellt. Der zugrunde liegende verteilte ID-Generierungsmechanismus (z. B. unter Verwendung von Zookeeper zur Koordination oder eines hochverfügbaren Zählers) stellt sicher, dass auch bei Ausfall einiger KGS-Instanzen eindeutige IDs generiert werden können. * **Message Queue (Kafka)**: Als Cluster mit Replikation bereitgestellt. Wenn ein Broker ausfällt, arbeiten andere Broker weiter, und Daten werden repliziert, um sicherzustellen, dass keine Nachrichten verloren gehen. **Rechenzentrums-Ausfälle**: Das gesamte System wird in mindestens zwei geografisch getrennten Rechenzentren oder mehreren Verfügbarkeitszonen innerhalb einer Region bereitgestellt. Load Balancer werden für Failover über Zonen/Regionen hinweg konfiguriert. Cassandras Multi-Datacenter-Replikation gewährleistet Datenhaltbarkeit und Verfügbarkeit, selbst wenn ein ganzes Rechenzentrum ausfällt. **Cache-Invalidierung**: Da `short_code`-zu-`long_url`-Zuordnungen weitgehend unveränderlich sind, ist eine explizite Cache-Invalidierung selten erforderlich. Cache-Einträge können eine sehr lange TTL haben. Wenn eine `long_url` jemals aktualisiert werden muss (z. B. aus rechtlichen Gründen), würde der Write-Service die Datenbank aktualisieren und dann den entsprechenden Eintrag im Redis-Cache explizit invalidieren/aktualisieren. **Backup- und Wiederherstellungsstrategie**: * **Datenbank**: Regelmäßige, automatisierte Snapshots des Cassandra-Cluster-Daten werden erstellt und in einem hochgradig dauerhaften Objektspeicher-Dienst (z. B. AWS S3, Google Cloud Storage) gespeichert. Diese Backups ermöglichen eine Point-in-Time-Wiederherstellung im Falle von Datenbeschädigung oder versehentlicher Löschung. Cassandras inkrementelle Backups und Commit-Logs können ebenfalls für eine granularere Wiederherstellung verwendet werden. * **Konfiguration**: Alle Infrastruktur- (Infrastructure as Code) und Anwendungskonfigurationen werden versioniert (z. B. Git) und über automatisierte Pipelines bereitgestellt, was eine schnelle Wiederherstellung von Service-Konfigurationen ermöglicht. * **Überwachung und Alarmierung**: Umfassende Überwachung (z. B. Prometheus, Grafana) wird vorhanden sein, um Systemzustand, Leistungsmetriken und Fehlerraten zu verfolgen. Automatisierte Alarme benachrichtigen Betriebsteams über Anomalien oder Ausfälle, was eine schnelle Reaktion und Wiederherstellung ermöglicht. ### F. Wichtige Kompromisse 1. **Konsistenz vs. Verfügbarkeit (für `short_code`-zu-`long_url`-Zuordnung)** * **Gewählter Kompromiss**: Wir priorisieren starke Konsistenz für die Kernzuordnung von `short_code` zu `long_url`, während wir für Hilfsdaten wie Klickzähler eine eventual consistency zulassen. * **Erklärung**: Der Hauptzweck eines URL-Verkürzers ist die zuverlässige Weiterleitung einer Kurz-URL zu ihrer korrekten Lang-URL. Eine inkonsistente Zuordnung (z. B. Weiterleitung zur falschen URL oder fehlgeschlagene Weiterleitung) würde das Benutzererlebnis erheblich beeinträchtigen und den Kernvertrag des Dienstes brechen. Daher stellen wir sicher, dass eine Kurz-URL, sobald sie erstellt und dem Benutzer zurückgegeben wurde, korrekt aufgelöst wird. Dies wird erreicht, indem mit starken Konsistenzebenen (z. B. `QUORUM`) in Cassandra geschrieben und der Redis-Cache sofort befüllt wird. Die Verfügbarkeit wird durch umfangreiche Replikation und verteilte Architektur aufrechterhalten, um sicherzustellen, dass der Dienst auch bei starken Konsistenzanforderungen für den kritischen Pfad betriebsbereit bleibt. Klickzähler können jedoch leichte Verzögerungen bei der Aktualisierung tolerieren, wodurch eventual consistency für diese nicht kritischen Daten akzeptabel ist. 2. **Einfachheit vs. Skalierbarkeit/Leistung (Schlüsselgenerierungsstrategie)** * **Gewählter Kompromiss**: Wir haben uns für einen dedizierten Key Generation Service (KGS) mit einem verteilten Zähler und Base62-Kodierung entschieden, der komplexer ist, gegenüber einem einfacheren Ansatz der Generierung zufälliger Base62-Zeichenketten und der Überprüfung auf Kollisionen. * **Erklärung**: Während die Generierung zufälliger Zeichenketten und die Überprüfung auf Kollisionen in der Datenbank anfangs einfacher zu implementieren ist, birgt sie mehrere Herausforderungen in Bezug auf Skalierbarkeit und Leistung. Wenn der Schlüsselraum voller wird, nimmt die Wahrscheinlichkeit von Kollisionen zu, was zu mehr Wiederholungsversuchen und höherer Latenz auf dem Schreibpfad führt. Dieses Read-before-write-Muster kann unter hoher Schreiblast zu einem Engpass werden. Der gewählte KGS-Ansatz, obwohl komplexer in Design und Wartung (erfordert einen verteilten ID-Generator), garantiert eindeutige Schlüssel ohne Kollisionen. Er ermöglicht die Vorabgenerierung von Schlüsselblöcken, was die Latenz der Schlüsselbeschaffung für den Schreibdienst erheblich reduziert. Diese anfängliche Komplexität wird durch die Notwendigkeit einer vorhersagbaren, hochleistungsfähigen und hochgradig skalierbaren Schlüsselgenerierung über die 5-jährige Lebensdauer des Dienstes gerechtfertigt und stellt sicher, dass der Schreibpfad mit wachsendem System effizient und zuverlässig bleibt.