Entwerfen Sie einen URL-Verkürzungsdienst

## Systementwurf: URL-Verkürzungsdienst ### A. Architektur auf hoher Ebene Das System wird aus den folgenden Hauptkomponenten bestehen: 1. **Load Balancer (LBs):** Verteilen eingehenden Datenverkehr (sowohl API-Anfragen zum Kürzen als auch Weiterleitungsanfragen) auf mehrere API-Server. Wir werden mehrere Ebenen von LBs verwenden, beginnend mit einem globalen LB (z. B. AWS Route 53) für DNS-basiertes Routing und dann regionale LBs (z. B. AWS ELB/ALB) für die Verteilung des Datenverkehrs innerhalb einer Region. 2. **API-Server (Webserver):** Verarbeiten eingehende Anfragen zum Erstellen kurzer URLs (POST /shorten) und zum Weiterleiten kurzer URLs (GET /{short_code}). Diese Server werden zustandslos sein. 3. **URL-Verkürzungsdienst (Geschäftslogik):** Ein Microservice, der für die Generierung kurzer Codes, die Interaktion mit der Datenbank und möglicherweise das Caching zuständig ist. 4. **Datenbank:** Speichert die Zuordnung zwischen kurzen Codes und ursprünglichen URLs. Die Wahl werden wir in Abschnitt C ausführlich besprechen. 5. **Cache:** Speichert häufig abgerufene Zuordnungen kurzer URLs, um die Datenbanklast und die Latenz bei Weiterleitungen zu reduzieren. Redis oder Memcached werden verwendet. 6. **Nachrichtenwarteschlange (Optional, aber für Skalierbarkeit empfohlen):** Für die asynchrone Verarbeitung von Aufgaben wie der Aktualisierung von Analysen oder der Bearbeitung potenzieller Wiederholungsversuche, obwohl für die Kernfunktionalität nicht unbedingt erforderlich. **Anforderungsfluss:** * **URL-Erstellung (POST /shorten):** 1. Der Client sendet eine POST-Anfrage mit der ursprünglichen URL an das API-Gateway/den Load Balancer. 2. Der LB leitet die Anfrage an einen verfügbaren API-Server weiter. 3. Der API-Server ruft den URL-Verkürzungsdienst auf. 4. Der URL-Verkürzungsdienst generiert einen eindeutigen kurzen Code (siehe Abschnitt B). 5. Der Dienst speichert die Zuordnung (short_code -> original_url) in der Datenbank. 6. Der Dienst schreibt die Zuordnung möglicherweise auch in den Cache. 7. Der API-Server gibt die gekürzte URL (z. B. `https://short.url/{short_code}`) an den Client zurück. * **URL-Weiterleitung (GET /{short_code}):** 1. Der Benutzer gibt eine gekürzte URL in seinen Browser ein. 2. Die Anfrage erreicht den Load Balancer. 3. Der LB leitet die Anfrage an einen verfügbaren API-Server weiter. 4. Der API-Server (oder ein dedizierter Weiterleitungsdienst) prüft zuerst den Cache auf den `short_code`. 5. **Cache-Treffer:** Wenn gefunden, wird die ursprüngliche URL aus dem Cache abgerufen, und der API-Server sendet eine HTTP 301 (dauerhafte Weiterleitung) oder 302 (temporäre Weiterleitung) Antwort an den Client mit der ursprünglichen URL. 6. **Cache-Fehlversuch:** Wenn nicht im Cache gefunden, fragt der API-Server die Datenbank nach dem `short_code` ab. 7. Die Datenbank gibt die ursprüngliche URL zurück. 8. Der API-Server fügt die Zuordnung für zukünftige Anfragen zum Cache hinzu. 9. Der API-Server sendet die HTTP-Weiterleitungsantwort. ### B. Strategie zur Generierung kurzer URLs Wir benötigen eine Strategie, die eindeutige, kurze und möglichst zufällig aussehende Codes generiert. Das Hauptziel ist Eindeutigkeit und Effizienz. * **Hashing (z. B. MD5, SHA-1):** * *Vorteile:* Deterministisch, kann eindeutige Codes generieren. Kann gekürzt werden. * *Nachteile:* Kollisionen sind möglich (wenn auch selten bei gutem Hashing und Kürzung). Codes sind möglicherweise nicht gleichmäßig verteilt, was zu Hotspots führt. Nicht leicht für Menschen lesbar oder merkbar. * **Zählerbasiert (z. B. automatisch inkrementierende ID):** * *Vorteile:* Garantiert Eindeutigkeit. Einfach zu implementieren. * *Nachteile:* Ein zentraler Zähler kann zum Engpass werden. Sequenzielle IDs sind vorhersehbar und können Nutzungsmuster offenlegen. Erfordert ein verteiltes Zählersystem für hohe Verfügbarkeit und Skalierbarkeit. * **Vorgefertigte Schlüsselpools:** * *Vorteile:* Verteilt die Generierungslast. Kann einen großen Pool eindeutiger Codes vorab generieren. * *Nachteile:* Erfordert die Verwaltung des Pools, die Sicherstellung, dass keine Überschneidungen auftreten, und möglicherweise die Vorabgenerierung einer riesigen Anzahl von Schlüsseln. * **Base-62/Base-64-Kodierung eines Zählers:** * *Vorteile:* Generiert kurze, eindeutige Codes durch Kodierung eines monoton steigenden Zählers (z. B. einer 64-Bit-Ganzzahl) in ein Base-62 (0-9, a-z, A-Z) oder Base-64-Alphabet. Dies ist effizient und erzeugt relativ kurze Zeichenketten. Garantiert Eindeutigkeit, wenn der Zähler ordnungsgemäß verwaltet wird. * *Nachteile:* Erfordert einen verteilten Zählerservice, um Engpässe zu vermeiden und die Eindeutigkeit über mehrere API-Server hinweg sicherzustellen. **Gewählte Strategie: Base-62-Kodierung eines verteilten Zählers** Dieser Ansatz bietet die beste Balance aus Eindeutigkeit, Kürze und Skalierbarkeit. Wir verwenden einen verteilten ID-Generierungsdienst (wie Twitter's Snowflake oder Apache ZooKeeper), um eindeutige, sequentielle 64-Bit-IDs zu generieren. Jede ID wird dann in eine Base-62-Zeichenkette kodiert. Dies liefert kurze, eindeutige Codes. Die sequentielle Natur der IDs kann durch die Verwendung einer zufälligen Komponente bei der ID-Generierung oder durch nachträgliches Mischen der Zuordnung verwaltet werden, um vorhersagbare Muster zu vermeiden. ### C. Datenspeicherung **Datenbanktechnologie:** Eine NoSQL-Datenbank wie **Cassandra** oder **ScyllaDB** (eine hochperformante Cassandra-kompatible Datenbank) ist aufgrund ihrer verteilten Natur, hohen Verfügbarkeit und hervorragenden Schreibleistung, die für die URL-Erstellung entscheidend ist, ein starker Kandidat. Alternativ könnte eine geshardete relationale Datenbank (wie PostgreSQL mit Citus oder MySQL mit Vitess) funktionieren, aber NoSQL vereinfacht oft die Skalierung für diese Art von Schlüssel-Wert-Abfragen. Nehmen wir **Cassandra** wegen seiner linearen Skalierbarkeit und Fehlertoleranz an. **Schema:** Wir verwenden ein einfaches Schema in einem Keyspace, der für Lesevorgänge optimiert ist: ```cql CREATE TABLE url_mappings ( short_code text PRIMARY KEY, original_url text, created_at timestamp ); ``` * `short_code`: Der eindeutige generierte kurze Code (z. B. `aBcDeF`). Dies ist der Primärschlüssel. * `original_url`: Die lange URL, zu der weitergeleitet werden soll. * `created_at`: Zeitstempel, wann die URL gekürzt wurde. **Schätzungen des Speicherbedarfs (über 5 Jahre):** * **Neue URLs pro Monat:** 100 Millionen * **Gesamtzahl der URLs über 5 Jahre:** 100 Millionen/Monat * 12 Monate/Jahr * 5 Jahre = 6 Milliarden URLs * **Durchschnittliche Länge des kurzen Codes:** Die Base-62-Kodierung einer 64-Bit-Ganzzahl ergibt etwa 11 Zeichen. Nehmen wir 15 Bytes für den `short_code` an (einschließlich Overhead). * **Durchschnittliche Länge der ursprünglichen URL:** Nehmen wir 2000 Bytes an (URLs können sehr lang sein). * **Overhead:** Nehmen wir 10 % Overhead für die Datenbank-Speicherung an (Replikation, Indizes usw.). **Gesamtspeicher:** (6 Milliarden URLs) * (15 Bytes/short_code + 2000 Bytes/original_url) * 1,10 (Overhead) = 6 * 10^9 * 2015 Bytes * 1,10 ≈ 13,3 * 10^12 Bytes ≈ 13,3 Terabyte (TB) Dies ist eine überschaubare Menge für eine verteilte NoSQL-Datenbank wie Cassandra, die durch Hinzufügen weiterer Knoten horizontal skaliert werden kann. **Warum Cassandra?** * **Skalierbarkeit:** Skaliert linear durch Hinzufügen weiterer Knoten und bewältigt riesige Datenmengen und Datenverkehr. * **Verfügbarkeit:** Entwickelt für hohe Verfügbarkeit ohne Single Point of Failure. Daten werden über mehrere Knoten und Rechenzentren repliziert. * **Schreibleistung:** Hervorragender Schreibdurchsatz, entscheidend für die URL-Erstellung. * **Leseleistung:** Kann für schnelle Schlüssel-Wert-Abfragen optimiert werden, was die Weiterleitung erfordert. ### D. Skalierungsstrategie **1. Caching-Strategie:** * **Cache der Stufe 1 (Verteilter Cache):** Verwenden Sie einen Redis- oder Memcached-Cluster. Speichern Sie `short_code -> original_url`-Zuordnungen. Dies wird die überwiegende Mehrheit der Leseanfragen bedienen (99 % des Datenverkehrs, angesichts des Lese-Schreib-Verhältnisses von 100:1). * **Cache-Invalidierung/Ablauf:** Der Einfachheit halber und angesichts der 5-Jahres-Lebensdauer können wir eine Time-To-Live (TTL) verwenden, die etwas länger ist als das erwartete Zugriffsmuster, oder uns einfach darauf verlassen, dass die Zuordnung einer kurzen URL nach ihrer Erstellung selten geändert wird. Eine gängige Strategie ist das Caching auf unbestimmte Zeit, bis die Anwendung neu gestartet wird oder eine manuelle Invalidierung ausgelöst wird (obwohl dies bei URL-Verkürzern seltener vorkommt). * **Cache-Befüllung:** Wenn eine Weiterleitungsanfrage den Cache nicht trifft, wird die ursprüngliche URL aus der Datenbank abgerufen und dann vor der Rückgabe der Weiterleitung in den Cache geschrieben. **2. Datenbankpartitionierung/Sharding:** * **Cassandra:** Cassandra übernimmt die Partitionierung automatisch basierend auf dem Primärschlüssel (`short_code`). Daten werden mithilfe eines konsistenten Hashing-Algorithmus auf die Knoten verteilt. Dies sharded die Daten inhärent. * **Relationale DB (falls gewählt):** Sharden Sie die Datenbank basierend auf dem `short_code` (z. B. mithilfe eines Hashs des `short_code`, um den Shard zu bestimmen). Dies verteilt die Last und die Daten auf mehrere Datenbankinstanzen. **3. Umgang mit Hot Keys (virale URLs):** * **Caching:** Die primäre Abwehr gegen Hot Keys ist aggressives Caching. Eine virale URL wird im Cache (Redis/Memcached) stark gecached, sodass nachfolgende Anfragen direkt aus dem Speicher bedient werden und die Datenbank umgangen wird. * **Datenbank-Lesereplikate (bei Verwendung von RDBMS):** Wenn die Datenbank selbst mit Caching zum Engpass wird, können Lesereplikate eingesetzt werden, obwohl die verteilte Natur von Cassandra dies bereits gut handhabt. * **Content Delivery Network (CDN):** Bei extrem hohem Datenverkehr könnten die Weiterleitungsantworten selbst potenziell mit einem CDN am Edge gecached werden, obwohl dies die Komplexität erhöht und möglicherweise nicht für alle Weiterleitungstypen (z. B. 302) geeignet ist. Die API-Server selbst könnten jedoch hinter einem CDN für einen schnelleren globalen Zugriff platziert werden. * **Dedizierter Lesepfad:** In extremen Fällen könnte ein separater, auf Lesevorgänge optimierter Datenspeicher oder eine Cache-Schicht in Betracht gezogen werden, aber der primäre Cache sollte die meisten Hot-Key-Szenarien abdecken. ### E. Zuverlässigkeit und Fehlertoleranz **1. Hohe Verfügbarkeit (99,9 % Uptime):** * **Redundanz:** Stellen Sie mehrere Instanzen jeder Komponente (API-Server, Cache-Knoten, Datenbankknoten) über mehrere Verfügbarkeitszonen (AZs) oder sogar Regionen hinweg bereit. * **Load Balancer:** LBs leiten den Datenverkehr automatisch von fehlerhaften Instanzen weg. * **Zustandslose API-Server:** API-Server sind zustandslos, sodass jeder Server jede Anfrage bearbeiten kann. Wenn einer ausfällt, übernehmen andere nahtlos. * **Datenbankreplikation:** Cassandra bietet integrierte Datenreplikation. Wir konfigurieren einen Replikationsfaktor (z. B. 3) über mehrere Knoten und Rechenzentren/AZs hinweg. Wenn ein Knoten ausfällt, dienen Replikate auf anderen Knoten den Daten. * **Cache-Replikation/Clustering:** Redis Sentinel oder Redis Cluster können hohe Verfügbarkeit für den Cache bieten. **2. Behandlung von Komponentenausfällen:** * **API-Server-Ausfall:** LBs erkennen den Ausfall und senden keine Anfragen mehr an die fehlerhafte Instanz. Andere Instanzen bedienen weiterhin Anfragen. * **Cache-Knoten-Ausfall:** Bei Verwendung von Redis Cluster oder Sentinel erfolgt ein automatisches Failover für Cache-Knoten. Wenn ein einzelner Knoten ausfällt, sind möglicherweise einige gecachte Daten vorübergehend nicht verfügbar, aber das System greift auf die Datenbank zurück. * **Datenbankknoten-Ausfall:** Cassandra behandelt Knotenausfälle automatisch. Daten sind von Replikaten auf anderen Knoten verfügbar. Wenn eine ganze AZ ausfällt, sind Daten immer noch von Knoten in anderen AZs verfügbar (bei Multi-AZ-Bereitstellung). **3. Datenreplikation und Failover:** * **Datenbank:** Die Replikationsstrategie von Cassandra gewährleistet Datenhaltbarkeit und Verfügbarkeit. Wir verwenden einen Replikationsfaktor von 3, wobei Replikate über verschiedene physische Standorte (Racks/AZs) verteilt sind. Wenn ein Knoten ausfällt, können Lesevorgänge und Schreibvorgänge weiterhin von anderen Replikaten bedient werden. * **Cache:** Redis Sentinel oder Cluster bietet automatisches Failover für Cache-Knoten. * **Anwendungsebene:** Implementieren Sie Wiederholungsmechanismen für vorübergehende Netzwerkprobleme bei der Kommunikation zwischen Diensten. ### F. Wichtige Kompromisse 1. **Konsistenz vs. Verfügbarkeit (CAP-Theorem):** * **Wahl:** Wir priorisieren **Verfügbarkeit** und **Partitionstoleranz** gegenüber starker Konsistenz für den Weiterleitungsdienst. Für die URL-Erstellung benötigen wir starke Konsistenz, um eindeutige kurze Codes zu gewährleisten. Für die Weiterleitung, wenn eine Datenbankreplik vorübergehend nicht verfügbar ist, würden wir lieber einen veralteten Eintrag aus dem Cache bedienen oder einen Fehler zurückgeben, als Anfragen zu blockieren. * **Begründung:** Die Kernfunktion eines URL-Verkürzers besteht darin, Benutzer schnell und zuverlässig weiterzuleiten. Gelegentliche veraltete Cache-Einträge oder vorübergehende Nichtverfügbarkeit einer bestimmten Kurz-URL-Zuordnung (was bei ordnungsgemäßer Replikation selten wäre) ist akzeptabler als weit verbreitete Serviceausfälle. Für die URL-Erstellung wird ein verteilter ID-Generator mit starken Konsistenzgarantien verwendet, um die Eindeutigkeit sicherzustellen. 2. **Latenz vs. Kosten/Komplexität (Caching-Strategie):** * **Wahl:** Wir haben uns für eine aggressive, mehrstufige Caching-Strategie (In-Memory-Cache wie Redis/Memcached) entschieden, um die Latenzanforderung von unter 50 ms für Weiterleitungen zu erreichen. * **Begründung:** Das Lese-Schreib-Verhältnis von 100:1 und die strenge Latenzanforderung (99,9 % Uptime, <50 ms Latenz im 95. Perzentil) machen Caching unerlässlich. Die direkte Bedienung der meisten Anfragen aus dem RAM reduziert die Datenbanklast und die Antwortzeiten erheblich. Obwohl Caching Komplexität (Cache-Invalidierung, Konsistenzbedenken, zusätzliche Infrastrukturkosten) hinzufügt, ist es ein notwendiger Kompromiss, um die Leistungs- und Verfügbarkeitsziele zu erreichen. Ohne ihn wäre die Datenbank vom Leseverkehr überlastet, was zu höherer Latenz und potenziellen Ausfällen führen würde.

A) High-level architecture Components 1) Edge - DNS + CDN/Anycast edge (optional but strongly recommended for <50ms p95 globally) - WAF + DDoS protection - Global load balancers (GSLB) routing to nearest region 2) Regional stack (at least 2 regions, active-active) - L7 load balancer (ALB/Envoy) - Stateless API service (URL Shortener) - Create API (write path) - Redirect API (read path) - Cache tier - L1 in-process cache (tiny, per instance, very hot keys) - L2 distributed cache (Redis/Memcached cluster) - Persistent storage - Primary KV store (DynamoDB/Cassandra/ScyllaDB-style) for short_code -> long_url mapping - Optional relational store (Postgres/MySQL) for analytics, user accounts, custom aliases (not in critical redirect path) - Async pipeline (non-critical) - Kafka/Kinesis/PubSub for click events, logs, abuse signals - Stream processors / OLAP sink (ClickHouse/BigQuery/S3) Request flow: URL creation (write) 1) Client calls POST /api/shorten with long_url (+ optional custom alias, TTL policy, user auth). 2) Request hits GSLB -> regional LB -> API server. 3) API validates URL (format, allow/deny lists, safe browsing), normalizes it, enforces rate limits. 4) Short code generation service allocates a unique code (details in section B). 5) API writes mapping to KV store (short_code as partition key). - Write includes created_at, expire_at (>=5 years), long_url, owner_id, flags. - Use quorum write (or strongly consistent write depending on store). 6) API populates L2 cache with short_code -> long_url (write-through) and returns short URL. 7) Emit asynchronous events (created, user, spam scoring) to stream; not required for success response. Request flow: URL redirection (read) 1) Browser requests GET /{code}. 2) Edge routes to nearest region; optional CDN can cache 301/302 responses if policy allows. 3) API server parses code. 4) Lookup order: a) L1 in-process cache b) L2 Redis/Memcached c) KV store (if cache miss) 5) If found and not expired/blocked: return HTTP 301/302 redirect with Location: long_url. - Cache fill on miss (set in L2; optionally L1). 6) Emit click event asynchronously (fire-and-forget). 7) If not found: 404 (optionally fallback to origin region if using regional isolation). Latency targets - L2 cache hit should dominate (sub-millisecond to a few ms within region). With edge routing + high cache hit rate, <50ms p95 is feasible. B) Short URL generation strategy Requirements - 100M new shortenings/month ~ 3.3M/day ~ ~38.6 writes/sec average (peaks higher). - Must generate unique, short, URL-safe codes with low collision risk and no coordination bottleneck. Options 1) Hash(long_url) - Pros: deterministic; dedup possible. - Cons: collisions require handling; reveals patterns; hard to support multiple identical long URLs for different users; changing normalization affects stability. 2) Central counter (autoincrement) + base62 encoding - Pros: compact; no collisions; simple. - Cons: single logical bottleneck unless sharded; sequential codes are guessable (security/abuse). 3) Distributed ID (Snowflake-like: time + worker + sequence) then base62 - Pros: no central coordinator; scalable; unique; bounded size. - Cons: slightly longer codes; time-based ordering leaks some info. 4) Pre-generated key pool - Pros: fastest allocation; decouples creation from ID generation. - Cons: requires managing pool, storage, and avoiding reuse; operational complexity. Chosen approach - Use a Snowflake-style 64-bit unique ID generated by each API node (or dedicated ID service) and encode to base62/base64url. - 64 bits in base62 yields up to 11 characters worst-case; typically 10–11 chars, acceptable. - If shorter codes are required, use 56–60 bits (still plenty) with careful epoch/time window and worker bits. - To reduce predictability, optionally apply a reversible permutation (e.g., Feistel network) to the 64-bit ID before base62 encoding; keeps uniqueness but makes codes non-sequential. Why this choice - Eliminates single counter bottleneck. - No collision handling needed. - Works well with multi-region active-active. - Predictability mitigated via permutation. Custom aliases - If user requests custom code, validate availability with a conditional write (put-if-absent) in KV store; if conflict, reject. C) Data storage Database choice - Primary store: a highly available, horizontally scalable KV database (DynamoDB or Cassandra/ScyllaDB). - Reasoning: - Access pattern is key-based reads by short_code. - Read-heavy at high QPS; KV stores excel at low-latency point lookups. - Built-in replication, partitioning, and operational maturity. Schema (single table) Table: url_mapping - Partition key: short_code (string) - Attributes: - long_url (string) - created_at (timestamp) - expire_at (timestamp, must be >= created_at + 5 years; can be null for “never”, but requirement says at least 5 years) - owner_id (string, optional) - status (active/disabled/malicious) - meta (optional: title, campaign, etc.) Indexes (optional) - GSI/secondary index on owner_id + created_at for listing user links (not on redirect path). Storage estimation (5 years) - New URLs: 100M/month * 12 * 5 = 6 billion mappings. - Per record size rough estimate: - short_code: 10–11 bytes (store as ~16 bytes with overhead) - long_url: assume average 100 bytes (could be 50–200; use 120 including overhead) - timestamps/status/owner_id: ~40 bytes average (owner_id optional) - DB overhead (keys, replication metadata, compression): varies; assume ~100 bytes overhead - Total logical per item ~250 bytes (conservative) - Raw logical storage: 6e9 * 250B = 1.5 TB. - With replication factor 3 (common in Cassandra/Scylla): ~4.5 TB. - Add indexes + headroom: plan ~6–10 TB across the cluster over 5 years. Notes - Long URLs can be compressed (dictionary/deflate) at application layer to reduce size; but only if it doesn’t add latency. Many KV stores also compress SSTables. D) Scaling strategy Traffic estimation - Writes: ~38.6/s average; assume peak 10x => ~400/s. - Reads: 100:1 => average ~3,860 reads/s; peak potentially much higher (e.g., 50k–200k/s depending on usage spikes). Scaling reads 1) Caching - L1 in-process cache: tiny (e.g., 10k–100k entries) with short TTL (30–120s) to absorb micro-hotspots and reduce Redis QPS. - L2 Redis/Memcached: - Cache value: long_url + status + expire_at. - TTL strategy: - If links are immutable (common), set long TTL (hours to days). - Still respect expire_at by setting TTL = min(configured_max_ttl, expire_at - now). - Use cache-aside with negative caching: - Cache “not found” for a short TTL (e.g., 30–60s) to reduce DB hits from scanners. - Aim for >95–99% cache hit rate for redirects. 2) CDN caching (optional but powerful) - For 301 redirects that are stable, CDN can cache the redirect response for popular codes. - Must consider ability to disable links quickly; mitigate by: - Short CDN TTL (e.g., 60–300s) + purge on disable - Or keep redirect logic at origin but cache mapping at edge KV (advanced). Database partitioning/sharding - Partition by short_code (consistent hashing / token ring). - Even distribution expected because codes are pseudo-random (post-permutation). - Add nodes to scale linearly. Handling hot keys (viral URLs) - Multi-layer approach: 1) Edge/CDN caches the redirect response for hottest keys with short TTL. 2) L1 + L2 caches reduce origin DB load. 3) Redis cluster scaling: shard by key; enable client-side hashing. 4) Request coalescing / single-flight on cache miss: if many requests miss simultaneously for same key, one request populates cache while others wait briefly. 5) For extreme cases, allow “hot key replication” in cache (store same key in multiple shards) or use a dedicated “hot cache” tier. Write scaling - Writes are modest; ensure conditional writes for uniqueness and idempotency. - Use rate limiting and abuse prevention to avoid write amplification from bots. E) Reliability and fault tolerance (99.9% uptime) Multi-region - Active-active in at least 2 regions. - GSLB health checks route traffic away from unhealthy region. Stateless services - API servers are stateless; scale horizontally; deploy across multiple AZs. Cache tier - Redis/Memcached deployed as a sharded cluster with replicas per shard (or Redis Cluster with replicas). - If cache fails: system falls back to DB; increased latency but still functional. - Protect DB with circuit breakers and adaptive rate limiting if cache outage causes thundering herd. Database replication and failover - DynamoDB option: - Use Global Tables for multi-region active-active replication. - Configure on-demand or provisioned capacity with autoscaling. - Cassandra/Scylla option: - Multi-AZ replication within region (RF=3). - Multi-region replication via NetworkTopologyStrategy; tune consistency (e.g., LOCAL_QUORUM for reads/writes) to keep latency low. - Failure modes: - Single node failure: replica reads/writes continue. - AZ failure: remaining AZs serve traffic (RF across AZs). - Region failure: GSLB shifts to healthy region; data available via replicated store. Data durability - Regular backups/snapshots to object storage (S3/GCS) + point-in-time recovery. - Disaster recovery drills and restore testing. Deployment safety - Rolling deployments + canary releases. - Feature flags. - Automated rollback on error budget burn. Operational controls - SLIs: redirect p95 latency, cache hit rate, DB p95, error rate, replication lag. - SLO: 99.9% availability; design for graceful degradation (e.g., temporarily disable analytics writes). F) Key trade-offs 1) Shortness of code vs distributed generation - Trade-off: A centralized counter can yield very short codes (often 6–8 chars early on), but adds coordination and is harder in multi-region. - Choice: distributed Snowflake-like IDs + base62 (10–11 chars) to ensure scalability, uniqueness, and multi-region compatibility while meeting latency/availability requirements. 2) Strong consistency vs low latency/high availability - Trade-off: Strongly consistent global reads increase latency and reduce availability during partitions. - Choice: use local-quorum/region-local consistency for redirect lookups (fast) with multi-region replication. For create operations, ensure uniqueness with conditional writes and accept eventual cross-region propagation; redirects remain correct because the authoritative mapping exists in at least one region and is quickly replicated. 3) Aggressive caching vs rapid disable/abuse response - Trade-off: Long cache TTLs improve latency and reduce DB load, but make it harder to immediately disable malicious links. - Choice: moderate TTLs + purge mechanisms, plus status checks in cached value and short TTL for CDN; allow “kill switch” by caching disabled status with high priority. Summary - Use edge routing + heavy caching to keep redirects under 50ms p95. - Use distributed unique ID generation (Snowflake + permutation) for scalable code generation. - Store mappings in a replicated KV store with sharding by short_code and multi-region failover. - Maintain 99.9% uptime via multi-AZ + multi-region, stateless services, replicated storage, and graceful degradation paths.