Design eines URL-Shortening-Dienstes im großen Maßstab

Architecture de haut niveau (diagramme textuel et composants) - Clients : navigateurs web, applications mobiles. Ils accèdent aux URL courtes (short.example/abc1234) et à l'API d'écriture pour créer des URL courtes. - CDN / Edge (CloudFront, Fastly) : Couche Edge qui reçoit les requêtes d'URL courtes entrantes. L'Edge mettra en cache les réponses de redirection (HTTP 301/302) et les servira sans toucher à l'origine autant que possible pour respecter le SLA de latence. - Routage Edge / DNS global (Route53, anycast) : Route les appels de l'API d'écriture vers la région la plus proche et les accès aux URL courtes vers l'Edge/région la plus proche. Des vérifications de santé et des basculements sont configurés. - API Gateway régionale + Load Balancer (API Gateway / ALB) : Accepte les écritures des clients et les appels de gestion. Route vers les services d'écriture déployés dans des conteneurs (ECS/Kubernetes) à travers les zones de disponibilité. - Service d'écriture (microservice sans état) : Valide l'entrée, génère un jeton court via le module de génération d'ID, écrit le mappage dans la base de données principale, publie des événements dans le flux, met à jour les caches et renvoie l'URL courte. - Services de chemin de lecture / Service de redirection (sans état) : Reçoit les misses de cache de l'Edge ou les accès directs, interroge le cache local (cluster Redis), se rabat sur la base de données, renvoie la redirection avec les en-têtes de cache appropriés. - Cache distribué (clusters Redis par région, clusterisé/répliqué) : Les recherches à chaud sont stockées ici pour des réponses en microsecondes. Chaque région possède son propre cluster Redis avec réplication entre les AZ. - Stockage principal (DynamoDB ou alternative Cassandra/Scylla) : Stocke le mappage short_id -> long_url, les métadonnées, l'expiration, le propriétaire, le timestamp de création. Choisi pour son débit élevé en lecture/écriture, son support TTL et sa réplication multi-région. - Flux d'événements (Kinesis / Kafka) : Toutes les écritures produisent des événements pour l'analyse, les mises à jour d'index, les messages d'invalidation de cache et le traitement asynchrone. - Workers d'arrière-plan (conteneurisés) : Gèrent le nettoyage TTL, la file d'attente de récupération, l'analyse et les vérifications de réplication asynchrone. - Surveillance & Ops : Prometheus/Grafana, CloudWatch, alertes, runbooks automatisés. Interactions des composants (lecture) : L'utilisateur accède à une URL courte -> Le cache Edge vérifie le cache de redirection -> si trouvé, renvoie la redirection mise en cache (<5 ms). Si manquant, l'Edge transfère vers le LB régional -> Le service de redirection interroge le cache Redis -> si trouvé, renvoie la redirection et l'Edge la met en cache ; si manquant, le service de redirection interroge la base de données principale -> renvoie la redirection -> Redis est mis à jour et l'Edge met en cache la redirection. Interactions des composants (écriture) : Le client appelle l'API -> API Gateway -> Service d'écriture -> Le générateur d'ID produit un jeton -> Le service d'écriture écrit le mappage dans la base de données principale avec TTL -> Le service d'écriture publie un événement dans le flux -> Le service d'écriture écrit dans le cache Redis et renvoie l'URL courte. Les workers d'arrière-plan répliquent de manière asynchrone les événements vers l'analyse et d'autres régions si nécessaire. Algorithme de raccourcissement d'URL et stratégie de génération de clés Objectifs : Jeton alphanumérique max de 7 caractères, non devinable (pas de jetons séquentiels), faible probabilité de collision, comportement de panne/réessai reproductible. Espace et contraintes : 62^7 ~= 3,52e12 jetons possibles. La cible mensuelle de 100 millions de nouveaux jetons est infime par rapport à l'espace, mais nous devons garantir qu'il n'y a pas d'énumération facile. Stratégie choisie (principale) : - Utiliser une génération aléatoire cryptographiquement sécurisée par nouvelle URL courte. Générer un entier aléatoire de 64 bits cryptographiquement sécurisé, appliquer un échantillonnage par rejet pour mapper dans l'intervalle [0, 62^7 - 1] sans biais de modulo, puis encoder en base62 en exactement 7 caractères. Cela produit des jetons uniformément aléatoires dans l'espace de 7 caractères et aucune séquentialité. - Avant de valider, tenter une insertion atomique dans la base de données avec short_id comme clé primaire et unicité garantie. Si l'insertion échoue en raison d'une rare collision, réessayer avec un nouveau jeton aléatoire (probabilité de collision attendue négligeable ; réessais attendus << 1). Pourquoi pas d'ID séquentiels ou d'encodage bijectif d'un compteur croissant : les ID séquentiels ou dérivés d'horodatages sont devinables et permettent l'énumération et le scraping. Nous les rejetons pour répondre à l'exigence de non-devinabilité. Alternative considérée et rejetée : hachages cryptographiques tronqués de l'URL longue (par exemple, les 7 premiers caractères base62 de SHA256). Rejetée car le mappage déterministe rend les jetons devinables si un attaquant peut hacher des URL populaires ; les collisions sont également plus fréquentes lors de la troncature. Nous aurions pu utiliser HMAC(longURL, secret) pour être déterministe et non devinable, mais le mappage déterministe empêche la réutilisation de jetons courts pour différentes variations d'entrée et complique le TTL/la révocation. Schéma de base de données et technologie de stockage (avec justification) Stockage principal choisi : DynamoDB (AWS) ou Cassandra/Scylla géré si auto-hébergé. Raison principale : service géré, évolutivité horizontale, débit élevé en lecture/écriture, support TTL intégré, réplication multi-région (DynamoDB Global Tables) et accès en millisecondes à un seul chiffre si provisionné de manière appropriée. Ceci est important pour une disponibilité de 99,9 % et des opérations simples. Schéma (logique, style DynamoDB) : - Table : url_map - Clé de partition : short_id (chaîne, 7 caractères) - Attributs : long_url (chaîne), created_at (timestamp), expires_at (timestamp), owner_id (chaîne), metadata (blob JSON), version (int), deleted (booléen), deletion_marked_at (timestamp), click_count (numérique, optionnel), analytics_shard_id (pour le sharding des clics) - Attribut TTL : expires_at pour l'expiration automatique par la fonctionnalité TTL de la base de données Index : aucun index secondaire global supplémentaire requis pour le chemin de redirection. Optionnellement un GSI sur owner_id pour la gestion et la suppression en masse par utilisateur, et un GSI sur deletion_marked_at pour le traitement de la récupération. Justification : Le modèle d'accès clé-valeur correspond bien à DynamoDB. Le short_id est la clé unique naturelle. Le TTL est intégré. Pour les autres fournisseurs cloud, utiliser Cosmos DB avec TTL ou Scylla/Cassandra avec TTL par ligne. Stratégie de mise en cache et d'invalidation Objectifs : Atteindre une latence de redirection au 95e percentile < 10 ms à grande échelle, minimiser la charge de la base de données, supporter le multi-région. Couches : - Mise en cache CDN (Edge) des réponses de redirection. L'Edge met en cache les 301/302 avec un TTL de cache calculé à partir de l'expiration du mappage ; le TTL de cache max est limité à la durée restante du TTL. Pour les URL courtes nouvellement créées, définir un court TTL de cache pendant les N premières secondes pour permettre la cohérence. - Cluster Redis régional (ElastiCache Redis Cluster avec mode cluster activé). Redis stocke le mappage short_id -> réponse de redirection sérialisée et les métadonnées d'expiration. Le TTL de la mise à jour Redis est égal à l'expiration du mappage. - Cache LRU local en mémoire (petit) dans le service de redirection pour les accès fréquents. Hypothèses de succès du cache et dimensionnement : - Supposer un taux de succès CDN de 70 % pour les URL courtes (liens populaires) ; taux de succès Redis pour les misses Edge ~85 % pour les modèles d'accès régionaux. Ceux-ci sont ajustables en fonction de l'utilisation. Population et invalidation du cache : - À l'écriture : Le service d'écriture écrit dans la base de données et écrit immédiatement dans Redis régional et publie un événement d'invalidation de cache dans le flux auquel toutes les régions s'abonnent. Cela garantit que les caches sont chauds et cohérents en quasi temps réel. - Lors de la mise à jour ou de la suppression : Le service d'écriture met à jour la base de données et publie un événement d'invalidation ; les abonnés suppriment les clés de Redis et invalident les caches Edge via les en-têtes cache-control ou en envoyant une requête PURGE/Cache à l'CDN (ou en définissant un court TTL de cache à 0 et en laissant l'Edge récupérer les données fraîches). Les appels de purge sont maintenus au minimum ; préférer l'expiration basée sur TTL et l'invalidation pub/sub. - Pour l'expiration TTL : s'appuyer sur le TTL de la base de données pour supprimer la ligne et les workers d'arrière-plan pour publier un événement d'invalidation afin de nettoyer les caches et d'ajouter le jeton à la file d'attente de récupération. Chemin de lecture (détaillé) et calculs de débit Calculs de trafic (mensuel de base -> par seconde) : - Écritures : 100 000 000 / 30 / 24 / 3600 ~= 38,6 écritures/sec en moyenne. Facteur de pic de 5 supposé pour le trafic diurne/soudain -> ~193 écritures/sec en pic. - Lectures (redirections) : 10 000 000 000 / 30 / 24 / 3600 ~= 3 858 lectures/sec en moyenne. Facteur de pic de 5 -> ~19 290 lectures/sec en pic. - Ratio lecture/écriture : 100:1 comme spécifié. Chemin de lecture (optimisé pour la latence) : 1. Le client demande short.example/abc1234 -> DNS résout vers le nœud Edge du CDN. 2. Recherche dans le cache Edge : si la redirection est mise en cache, renvoyer immédiatement HTTP 301/302. Cela couvre la majorité des requêtes pour les liens populaires. 3. Si le cache Edge est manquant : la requête est transférée vers le LB régional -> Service de redirection. 4. Le service de redirection consulte le cache en mémoire (minuscule) -> Redis cluster get(short_id). La requête GET Redis est inférieure à la milliseconde en fonction du réseau (généralement <1 ms dans la région). Si Redis est trouvé, le service renvoie la redirection et l'Edge la met en cache avec le TTL approprié. 5. Si Redis est manquant : le service interroge la base de données principale (DynamoDB GetItem) qui prend quelques millisecondes, typiquement 3-6 ms. Le service renvoie la redirection et remplit Redis et le cache Edge. Capacité de débit et exemples de dimensionnement : - Cluster Redis : supposer un pic de 20k lectures/sec. Déployer 3-5 shards avec réplication pour gérer 50k+ ops/sec et fournir une marge. Chaque shard dimensionné pour ~10k ops/sec (type de nœud approprié). Réplicas de lecture dans chaque AZ pour la haute disponibilité. - DynamoDB : besoin de capacité pour les écritures ~200 TPS en pic et les lectures pour les misses de cache. Si le taux de succès du cache est de 90 % au total, la charge de lecture de la base de données = 19 290 * 0,10 ~= 1 929 lectures/sec en pic. Avec des pics éventuels et un facteur de sécurité de 2, provisionner pour 4k lectures/sec cohérentes (ou utiliser des lectures éventuellement cohérentes pour diviser par deux le coût RCU). Chemin d'écriture (détaillé) et débit Chemin d'écriture : 1. Le client soumet la requête de création à l'API -> API Gateway -> LB régional -> Service d'écriture. 2. Le service d'écriture valide l'URL (nettoyage, vérifications de logiciels malveillants en option), vérifie les limites de débit et les quotas. 3. Générateur d'ID : utilise CSPRNG pour créer un jeton ; tente d'insérer dans la base de données avec une condition PutItem que short_id n'existe pas (atomique). Si PutItem échoue en raison d'une clé existante (rare), réessaie la génération. L'insertion inclut long_url, created_at, expires_at. 4. En cas d'insertion réussie, le service d'écriture écrit dans Redis pour un préchauffage immédiat du cache et publie un événement dans le flux pour l'analyse et la propagation inter-régions. 5. Renvoie l'URL courte au client. Dimensionnement du débit pour les écritures : - 39 écritures/sec en moyenne de base, pic provisionné ~200 écritures/sec. DynamoDB supporte facilement des milliers d'écritures/sec avec une capacité appropriée ou en mode à la demande. - Service d'écriture sans état, mis à l'échelle horizontalement : supposer que chaque instance peut gérer 200-500 req/s ; définir un groupe d'autoscaling pour maintenir une marge. À 200 écritures/sec en pic, 2-4 instances sont suffisantes ; allouer 10-20 pour la redondance et d'autres traitements comme la limitation de débit. Stratégie de mise à l'échelle et gestion d'une croissance 10x Scénario : une croissance 10x signifie 1 milliard d'écritures/mois et 100 milliards de redirections/mois. Stratégies : - Autoscaling : Tous les services sans état (écriture/redirection) s'adaptent automatiquement en fonction du CPU/RPS et de la latence des requêtes. Utiliser le cluster autoscaler pour les conteneurs. - Mise à l'échelle du cache : Ajouter des shards Redis et augmenter la mémoire. Le mode cluster Redis permet le re-sharding dynamique. Le CDN gère automatiquement la mise à l'échelle Edge. - Mise à l'échelle de la base de données : DynamoDB supporte la mise à l'échelle à la demande, ou augmenter la capacité d'écriture/lecture ; pour Cassandra/Scylla auto-hébergé, ajouter des nœuds et rééquilibrer les jetons. - Partitionnement : La clé de hachage DynamoDB distribue déjà sur les partitions. Pour Cassandra, s'assurer qu'il y a suffisamment de nœuds pour maintenir les partitions petites. - Limitation de débit et backpressure : Pour les pics soudains, appliquer des limites de débit par utilisateur et par clé d'API, et mettre en file d'attente les tâches d'arrière-plan pour le travail non critique (analyse). Implémenter une dégradation gracieuse (par exemple, refuser les nouvelles créations pour les clients abusifs) plutôt que d'impacter les redirections. - Trafic mondial : Ajouter plus de régions et répliquer les données. Ajouter des réplicas de lecture Redis inter-régions ou s'appuyer sur la mise en cache locale remplie par des lectures à la demande. Estimation de la capacité après 10x : - Pics de lecture ~200k/sec. Avec un taux de succès de cache de 90 %, les lectures de base de données en pic ~20k/sec. DynamoDB/DAX ou une mise en cache gérée devant la base de données seront nécessaires. Le cluster Redis sera mis à l'échelle à des centaines de shards, et le CDN restera le principal moyen de réduire la charge mondiale. Déploiement multi-région et modèle de cohérence Modèle choisi : Multi-région actif-actif avec cohérence éventuelle entre les régions pour les données non critiques. Utiliser DynamoDB Global Tables ou la réplication multi-DC de Cassandra. Logique et compromis CAP : - Exigence : 99,9 % de disponibilité et reprise après sinistre inter-régions. Privilégier la Disponibilité et la Tolérance aux Partitions (AP) par rapport à la Cohérence stricte (CP) car les redirections doivent rester disponibles même en cas de partitions régionales. Un léger retard dans la réplication des URL courtes nouvellement créées dans une autre région est acceptable ; l'utilisateur qui a créé l'URL l'utilise généralement immédiatement dans la même région et la verra grâce à l'écriture locale et au préchauffage du cache. - Implémentation : Le service d'écriture écrit dans la base de données de la région locale (DynamoDB local ou table de la même région) puis la réplication vers d'autres régions se fait via les tables globales. Les lectures dans une région lisent préférentiellement localement. Pour une cohérence locale forte lecture-après-écriture, utiliser une lecture fortement cohérente de DynamoDB dans la même région immédiatement après l'écriture, ou simplement s'appuyer sur le préchauffage immédiat du cache pour garantir que la redirection fonctionne dans la région de l'écrivain. Compromis : - La cohérence éventuelle simplifie la disponibilité mondiale et réduit la latence des lectures. Elle permet une courte fenêtre où une URL courte créée dans la région A peut ne pas être visible dans la région B tant que la réplication n'est pas terminée. Nous acceptons cela car les principaux SLA concernent la disponibilité et la latence des redirections. - Si une cohérence inter-régions stricte était requise, nous devrions implémenter un modèle CP avec réplication synchrone inter-régions, ce qui augmenterait considérablement la latence d'écriture et réduirait la disponibilité pendant les partitions ; donc rejeté. Expiration TTL et mécanisme de récupération d'URL Exigences : TTL configurable par URL courte (par défaut 5 ans), les URL expirées doivent être récupérables. Mécanisme : - Utiliser l'attribut TTL de la base de données (expires_at). DynamoDB supprime automatiquement les éléments après l'expiration du TTL, mais la suppression est éventuellement cohérente et peut ne pas être immédiate (peut prendre jusqu'à 48 heures dans certains systèmes). Par conséquent, nous implémentons un pipeline de récupération actif. - Lorsque expires_at approche (par exemple, dans les 24 heures), les workers d'arrière-plan marquent l'URL comme expirant et envoient un événement via le flux. Cela permet aux caches de définir des TTL courts et de préparer la purge. - Lors de l'expiration réelle, les workers d'arrière-plan recherchent les lignes expirées (en utilisant le GSI sur deletion_marked_at ou les événements TTL de la table) et déplacent la clé dans une file d'attente de récupération avec les métadonnées : short_id, deletion_marked_at, original_expires_at. - Politique de récupération : Introduire une période de grâce configurable (par exemple, 30 jours) après l'expiration pendant laquelle le short_id est marqué comme 'tombstone' (drapeau deleted et enregistrement tombstone conservés) pour éviter la réutilisation immédiate et pour se protéger contre le retard de réplication et les litiges des utilisateurs. Pendant la période de tombstone, le short_id résout en 404 ou en une page « ce lien a expiré » ; les clics sont enregistrés pour audit. - Après la période de grâce, le worker de récupération déplace le short_id dans un pool de jetons récupérables (sujet Kafka ou table de pool de jetons DynamoDB). Les jetons du pool peuvent être recyclés ; les jetons récupérés incluent un temps de refroidissement et ne sont jamais immédiatement réémis au même propriétaire sauf demande explicite. - Pour éviter les collisions de réutilisation et les abus, maintenir un index de tombstones pour les jetons récemment utilisés (taille limitée, par exemple, conservés pendant 1 an dans une table séparée) et vérifier avant la réutilisation. Alternativement, au lieu de réutiliser les jetons, préférer maintenir le taux de recyclage extrêmement bas car l'espace de 7 caractères est grand. Pannes et récupération 1) Panne CDN / Edge dans une région ou perturbation globale du fournisseur Edge - Impact : La mise en cache Edge est arrêtée ; plus de requêtes atteignent les services de redirection régionaux et les caches backend, augmentant la charge et la latence. - Récupération : Le trafic est redirigé par DNS/anycast vers d'autres Edges ou une origine de secours. Autoscaling de la flotte de redirection et augmentation du nombre d'instances. Utiliser Origin Shield et configurer le basculement d'origine. Servir les redirections directement depuis l'origine jusqu'à ce que l'Edge récupère. 2) Panne de la région de la base de données principale (panne complète AZ/région) - Impact : La base de données locale est indisponible ; les écritures et les lectures ne peuvent pas être servies depuis cette région. - Récupération : Basculement vers une autre région via les tables globales. Rediriger le DNS et l'API Gateway vers les régions saines. Comme les données sont répliquées de manière asynchrone, les écritures récentes dans la région défaillante peuvent être perdues pendant une courte période, sauf si les écritures ont été répliquées auparavant. Le système accepte cela en échange d'une haute disponibilité. La réconciliation en arrière-plan tente de réparer les conflits une fois la région revenue. 3) Panne ou partition du cluster Redis - Impact : Augmentation des misses de cache entraînant une charge accrue de la base de données et une latence accrue. - Récupération : Les clients se rabattent sur les lectures de la base de données ; augmenter la capacité de lecture de la base de données ou activer DAX (DynamoDB Accelerator) ou des nœuds Redis supplémentaires. Reconstruire le cluster Redis à partir d'instantanés de la base de données ou précharger les caches en récupérant les clés les plus chaudes à l'aide de l'analyse/listes de clés chaudes. Utiliser Redis Sentinel ou un cluster Redis géré avec basculement automatique pour assurer la redondance au niveau des nœuds. 4) Bug du service générateur d'ID provoquant des collisions ou l'épuisement des limites de débit - Impact : Échecs d'écriture, erreurs de jeton en double, ou incapacité à créer de nouveaux jetons. - Récupération : Concevoir le générateur comme un CSPRNG sans état ; si un bug est détecté, revenir à une version stable précédente et router les requêtes vers une implémentation de générateur de secours (par exemple, une bibliothèque RNG différente ou un compteur de secours à courte durée combiné à un sel HMAC). Ajouter une surveillance du taux de collision ; si le taux de collision dépasse un seuil trivial, arrêter d'émettre de nouveaux jetons et renvoyer 5xx jusqu'à résolution. 5) Retard dans la file d'attente du consommateur du flux d'événements ou panne du worker - Impact : Les invalidations de cache, le traitement de l'analyse et la récupération sont retardés. - Récupération : Autoscaling des consommateurs, prioriser les sujets d'invalidation et de récupération, et définir la rétention pour que les nouveaux consommateurs puissent rattraper. Reconstruire l'état à partir de la base de données si nécessaire. Principaux compromis et alternatives considérées 1) Choix du stockage : DynamoDB (NoSQL géré) vs RDBMS vs Cassandra/Scylla - Choisi : DynamoDB (ou Cassandra géré). Raison : échelle horizontale, TTL, service géré, tables globales pour le multi-région. RDBMS rejeté en raison de la complexité de mise à l'échelle, du sharding et de la latence de ligne unique plus lente à échelle extrême. 2) Génération de jetons : Jeton aléatoire vs compteur séquentiel vs hachage de l'URL longue - Choisi : Jetons aléatoires cryptographiquement sécurisés mappés en base62 sur 7 caractères. Raison : non devinable, distribution uniforme, mise à l'échelle triviale, faible probabilité de collision résolue par insertion conditionnelle DB. Compteurs séquentiels rejetés car devinables. Hachage déterministe rejeté en raison d'un risque de collision plus élevé et de la prévisibilité. 3) Multi-région actif-actif vs basculement actif-passif - Choisi : Actif-actif avec cohérence éventuelle. Raison : meilleure disponibilité et routage client plus simple vers la région la plus proche avec une faible latence. Actif-passif offre une cohérence plus forte mais augmente le temps de basculement et pourrait violer les exigences de latence/disponibilité. 4) Récupération de jetons vs ne jamais réutiliser de jetons - Choisi : Récupérable avec période de grâce/tombstone. Raison : l'espace de jetons est grand donc la réutilisation n'est pas souvent nécessaire, mais la récupération est requise par la spécification. La sécurité est accrue par la conservation des tombstones et un temps de refroidissement avant la réémission. Jamais réutiliser rejeté car après de nombreuses années, il pourrait y avoir un besoin de conserver l'espace de noms si les jetons sont épuisés dans des scénarios pathologiques. 5) Mise en cache Edge vs origine seule - Choisi : Mise en cache Edge intensive avec des TTL courts. Raison : atteindre une latence au 95e percentile < 10 ms pour les utilisateurs mondiaux. L'origine seule rejetée car la latence de l'origine et les sauts inter-régions dépasseraient le SLA de latence. Considérations opérationnelles et chiffres - SLO : 99,9 % de disponibilité ; surveiller la santé et la latence à l'Edge, Redis, DB et service d'écriture. Définir des seuils d'alerte pour les taux d'erreur et la latence au 95e percentile. - Exemples de planification de capacité : pour le trafic de base, provisionner la DB pour ~4k lectures/sec et ~200 écritures/sec en pic ; cluster Redis dimensionné pour ~30k ops/sec. Pour une échelle 10x, provisionner la DB pour ~40k lectures/sec et Redis pour ~300k ops/sec avec des shards en autoscaling. - Sécurité & atténuation des abus : limitation de débit par clé d'API/IP, analyse d'URL pour les logiciels malveillants (asynchrone optionnel), application de quotas par compte. Protéger les points d'accès avec WAF et clés d'API. - Rétention des données et confidentialité : Fournir des API de gestion pour que les utilisateurs suppriment/étendent le TTL ; sémantique de suppression logique pour l'auditabilité et conservation des tombstones. Résumé Cette conception utilise une approche de mise en cache multi-couches (Edge CDN + Redis régional) soutenue par un magasin NoSQL évolutif horizontalement (DynamoDB ou Cassandra) et des microservices sans état pour répondre aux exigences de débit et de latence. La génération de jetons utilise des jetons de 7 caractères base62 basés sur CSPRNG avec résolution des collisions basée sur la DB pour garantir la non-devinabilité. Le système privilégie la disponibilité et la tolérance aux partitions (cohérence éventuelle multi-région actif-actif) pour répondre aux SLA de disponibilité et de latence, tandis que la récupération et le TTL sont gérés par le TTL de la DB plus un pipeline de récupération avec une fenêtre de grâce de tombstone pour éviter les réutilisations accidentelles. L'architecture s'adapte horizontalement avec l'autoscaling et le sharding pour accueillir une croissance 10x, et inclut des chemins de récupération pour les modes de défaillance courants afin de répondre à l'objectif de disponibilité de 99,9 %.

Architekturübersicht: Die Architektur ist auf hohe Verfügbarkeit, Skalierbarkeit und geringe Latenz ausgelegt und nutzt einen Microservices-Ansatz. Zu den Schlüsselkomponenten gehören: 1. **Load Balancer (z. B. AWS ELB/GCP Load Balancer/Nginx)**: Verteilen eingehenden Datenverkehr auf Service-Instanzen. 2. **API Gateway (z. B. AWS API Gateway/Kong)**: Verarbeitet API-Anfragen, Authentifizierung, Ratenbegrenzung und leitet Datenverkehr an die entsprechenden Backend-Services. 3. **Shortening Service (Schreibpfad)**: Ein zustandsloser Microservice, der für die Verarbeitung von Anfragen zur Erstellung neuer kurzer URLs zuständig ist. Er interagiert mit dem Key Generation Service und der Datenbank. 4. **Redirect Service (Lesepfad)**: Ein hochoptimierter, zustandsloser Microservice, der für die Auflösung kurzer URLs zu langen URLs und die Durchführung der HTTP 301/302-Umleitung zuständig ist. Er stützt sich stark auf Caching. 5. **Key Generation Service**: Ein dedizierter Dienst, der für die Vorabgenerierung und Verwaltung eines Pools eindeutiger, zufälliger kurzer URL-Schlüssel zuständig ist. Er sorgt für Nicht-Erkennbarkeit und vermeidet Kollisionen. 6. **Datenbank (z. B. Apache Cassandra)**: Der primäre persistente Speicher für Short-URL-Mappings. Ausgewählt wegen seines hohen Schreib-/Lese-Durchsatzes, seiner horizontalen Skalierbarkeit und seiner Multi-Region-Replikationsfähigkeiten. 7. **Verteilter Cache (z. B. Redis Cluster)**: Speichert häufig abgerufene Short-URL-Mappings, um die Datenbanklast zu reduzieren und eine geringe Redirect-Latenz zu erreichen. 8. **Message Queue (z. B. Apache Kafka/AWS SQS)**: Wird für die asynchrone Kommunikation zwischen Services verwendet, z. B. zum Veröffentlichen von Ereignissen für Analysen, Cache-Invalidierung und URL-Ablauf. 9. **Analytics Service**: Verbraucht Ereignisse aus der Message Queue, um Klickzahlen zu verfolgen, Berichte zu erstellen und Nutzungsmuster zu überwachen. 10. **Expiration & Reclamation Service**: Ein Hintergrund-Worker-Service, der für die Identifizierung abgelaufener URLs, deren Kennzeichnung und die Rückgabe ihrer Schlüssel an den Pool des Key Generation Service zur Wiederverwendung zuständig ist. 11. **CDN (Content Delivery Network, z. B. Cloudflare/Akamai)**: Optional, aber dringend empfohlen für das Caching von Redirects am Edge, um die Latenz und die Last auf den Origin-Servern für globale Benutzer weiter zu reduzieren. Interaktionen: * **Schreibpfad**: Benutzer -> Load Balancer -> API Gateway -> Shortening Service -> Key Generation Service (holt Schlüssel) -> Datenbank (schreibt Mapping) -> Message Queue (veröffentlicht 'new_url'-Ereignis) -> Cache (aktualisiert/schreibt durch). * **Lesepfad**: Benutzer -> Load Balancer -> CDN (wenn Treffer, leitet weiter) -> Redirect Service (prüft lokalen Cache -> verteilten Cache -> Datenbank) -> Redirect. URL-Shortening-Algorithmus und Schlüsselgenerierungsstrategie: Um Nicht-Erkennbarkeit und Eindeutigkeit zu gewährleisten und das 7-Zeichen-Limit einzuhalten, wird eine Vorabgenerierungsstrategie angewendet: 1. **Key Generation Service**: Dieser Dienst generiert kontinuierlich zufällige alphanumerische Zeichenfolgen von 7 Zeichen (z. B. unter Verwendung eines kryptografisch sicheren Pseudozufallszahlengenerators). Der Zeichensatz umfasst `a-z`, `A-Z`, `0-9`, insgesamt 62 Zeichen. Eine 7-Zeichen-Zeichenfolge ermöglicht 62^7 eindeutige Schlüssel, was ungefähr 3,5 Billionen entspricht und damit die Anforderung von 100 Millionen URLs/Monat weit übertrifft. 2. **Eindeutigkeitsprüfung**: Bevor jeder generierte Schlüssel dem Pool hinzugefügt wird, wird seine Eindeutigkeit anhand der Datenbank (oder eines dedizierten Speichers für eindeutige Schlüssel) überprüft. Dies ist eine einmalige Prüfung während der Generierung, nicht während der Anfragen zur Verkürzung. 3. **Schlüsselpool**: Eindeutige Schlüssel werden in einem hochverfügbaren, schnell zugänglichen Pool gespeichert (z. B. einem Redis-Set oder einer dedizierten Tabelle in Cassandra mit einem 'status'-Feld wie 'available'). Der Key Generation Service unterhält einen großen Puffer (z. B. mehrere Milliarden Schlüssel), um sicherzustellen, dass Schlüssel jederzeit verfügbar sind. 4. **Verkürzungsprozess**: Wenn ein Benutzer eine neue kurze URL anfordert, fordert der Shortening Service einen Schlüssel vom Key Generation Service an. Der Key Generation Service zieht atomar einen verfügbaren Schlüssel aus seinem Pool, markiert ihn als 'in use' und gibt ihn zurück. Dies vermeidet Konflikte bei hoher Schreiblast. 5. **Kollisionsvermeidung**: Durch die Vorabgenerierung und atomare Zuweisung eindeutiger Schlüssel werden Kollisionen während der eigentlichen Verkürzungsanfrage praktisch eliminiert. Die Datenbank erzwingt außerdem eine eindeutige Einschränkung für den `short_url_key` als letzte Sicherheitsmaßnahme. Datenbankschema und Wahl der Speichertechnologie: Datenbankwahl: **Apache Cassandra** (oder AWS DynamoDB als verwaltete Alternative). Begründung: * **Hoher Schreib-/Lese-Durchsatz**: Cassandra ist für Operationen mit hohem Volumen und geringer Latenz ausgelegt, perfekt für das Lese-Schreib-Verhältnis von 100:1 und Milliarden von Lesevorgängen. * **Horizontale Skalierbarkeit**: Lässt sich einfach durch Hinzufügen weiterer Knoten skalieren, wodurch Daten und Last auf dem Cluster verteilt werden. * **Hohe Verfügbarkeit und Fehlertoleranz**: Daten werden über mehrere Knoten und Rechenzentren repliziert, um den kontinuierlichen Betrieb auch bei Knotenausfällen zu gewährleisten. * **Eventual Consistency**: Für diesen Anwendungsfall akzeptabel. Obwohl eine neue URL Millisekunden zur Replikation über Regionen hinweg benötigen kann, beeinträchtigt dies die Kernfunktionalität nicht. * **Einfache Schlüssel-Wert-Abfragen**: Das primäre Zugriffsmuster ist `short_url_key` zu `long_url`, bei dem Cassandra hervorragend abschneidet. Schema (Keyspace: `url_shortener`, Tabelle: `short_urls`): ``` CREATE TABLE url_shortener.short_urls ( short_url_key text PRIMARY KEY, -- Partition Key, 7 alphanumerische Zeichen long_url text, user_id text, -- Optional, für benutzerspezifische URLs created_at timestamp, expires_at timestamp, click_count counter, -- Cassandra Counter-Typ für atomare Inkremente status text -- 'active', 'expired', 'reclaimed' ); ``` Caching-Strategie und Cache-Invalidierungsansatz: Caching ist entscheidend, um die Redirect-Latenz von <10ms zu erreichen und 10 Milliarden Redirects/Monat zu bewältigen. Strategie: 1. **Mehrstufiges Caching**: * **CDN (Edge Cache)**: Cacht Redirects an geografisch verteilten Points of Presence. Dies ist die erste Verteidigungslinie für Leseanfragen. * **Verteilter Cache (Redis Cluster)**: Ein zentraler Hochleistungs-Cache, der `short_url_key` zu `long_url`-Mappings speichert. Jeder Eintrag speichert auch `expires_at`. * **In-Memory-Cache**: Jede Redirect Service-Instanz unterhält einen kleinen, schnellen In-Memory-Cache für die heißesten URLs. 2. **Read-Through**: Wenn der Redirect Service eine Anfrage erhält, prüft er zuerst seinen In-Memory-Cache, dann den Redis Cluster. Wenn nichts gefunden wird, ruft er Daten aus Cassandra ab, speichert das Mapping in Redis und seinem lokalen Cache und leitet dann weiter. 3. **Write-Through**: Wenn eine neue URL gekürzt wird, schreibt der Shortening Service das Mapping in Cassandra und dann sofort in den Redis Cluster. Cache-Invalidierung: 1. **TTL-basierte Ablaufzeit**: Cache-Einträge in Redis und In-Memory-Caches haben eine konfigurierbare TTL (z. B. 5 Minuten oder ausgerichtet an `expires_at` der URL). Dies behandelt die Eventual Consistency und stellt sicher, dass veraltete Daten nicht unbegrenzt bestehen bleiben. 2. **Explizite Invalidierung**: Wenn eine URL abläuft oder vom Expiration & Reclamation Service zurückgefordert wird, wird ein Ereignis an die Message Queue gesendet. Cache-Invalidierungs-Worker verbrauchen dieses Ereignis und löschen explizit den entsprechenden Eintrag aus dem Redis Cluster. CDN-Caches werden über API-Aufrufe oder durch Setzen geeigneter `Cache-Control`-Header mit kurzer `max-age` für Redirects invalidiert. Read Path und Write Path mit Durchsatzberechnungen: Annahmen: 1 Monat = 2.592.000 Sekunden. Schreibpfad (100 Millionen neue URL-Verkürzungen pro Monat): * **Durchschnittlicher Durchsatz**: 100.000.000 URLs / 2.592.000 Sekunden ≈ 38,6 Schreibvorgänge/Sekunde. * **Spitzendurchsatz**: Bei einer Spitzenlast von 3x dem Durchschnitt, Auslegung für ~120 Schreibvorgänge/Sekunde. * **Ablauf**: Load Balancer -> API Gateway -> Shortening Service (fordert Schlüssel vom Key Generation Service an, schreibt in Cassandra, schreibt in Redis, veröffentlicht Ereignis an Kafka). * **Komponenten**: Mehrere Instanzen von Shortening Service, Key Generation Service, Cassandra-Knoten, Redis-Knoten, Kafka-Broker. * **Latenzziel**: Unter 100 ms für Schreibvorgänge (weniger kritisch als Lesevorgänge). Lesepfad (10 Milliarden Redirects pro Monat): * **Durchschnittlicher Durchsatz**: 10.000.000.000 Redirects / 2.592.000 Sekunden ≈ 3.858 Lesevorgänge/Sekunde. * **Spitzendurchsatz**: Bei einer Spitzenlast von 3x dem Durchschnitt, Auslegung für ~12.000 Lesevorgänge/Sekunde. * **Ablauf**: Benutzer -> CDN (wenn Treffer, leitet weiter) -> Load Balancer -> Redirect Service (prüft In-Memory-Cache -> Redis Cluster -> Cassandra) -> Redirect. * **Cache-Trefferquote**: Ziel >95% Cache-Trefferquote (CDN + Redis), um Cassandra zu entlasten. * **Effektive DB-Lesevorgänge**: 12.000 Lesevorgänge/Sek. * 5% (Cache-Fehlrate) = 600 Lesevorgänge/Sekunde an Cassandra. * **Latenzziel**: Unter 10 ms im 95. Perzentil. * **Komponenten**: Zahlreiche Instanzen von Redirect Service, Redis Cluster-Knoten, Cassandra-Knoten. CDN spielt eine entscheidende Rolle. Skalierungsstrategie: 1. **Horizontale Skalierung (Zustandslose Services)**: Alle zustandslosen Services (API Gateway, Shortening Service, Redirect Service, Key Generation Service, Analytics Service, Expiration & Reclamation Service) werden als mehrere Instanzen hinter Load Balancern bereitgestellt. Sie können durch Hinzufügen weiterer Instanzen basierend auf CPU-Auslastung, Speicher oder Anforderungswarteschlangentiefe skaliert werden (z. B. mit Kubernetes HPA oder AWS Auto Scaling Groups). 2. **Datenbankskalierung (Cassandra)**: Cassandra skaliert horizontal durch Hinzufügen weiterer Knoten zum Cluster. Daten werden automatisch neu verteilt. 3. **Cache-Skalierung (Redis Cluster)**: Redis Cluster bietet Sharding und Replikation, wodurch er horizontal durch Hinzufügen weiterer Master- und Replikaknoten skaliert werden kann. 4. **Message Queue-Skalierung (Kafka)**: Kafka ist von Natur aus skalierbar und ermöglicht einen höheren Durchsatz durch Hinzufügen weiterer Broker und Partitionen. 5. **CDN**: Entlastet einen erheblichen Teil des Leseverkehrs von den Origin-Servern und skaliert effektiv den Lesepfad global. 6. **Microservices**: Die modulare Architektur ermöglicht es, einzelne Services basierend auf ihren spezifischen Lastanforderungen unabhängig zu skalieren. Multi-Region-Bereitstellung und Datenkonsistenzmodell: Um eine Verfügbarkeit von 99,9 % und Disaster Recovery zu erreichen, wird der Dienst in einer Active-Active-Konfiguration über mindestens zwei geografische Regionen (z. B. US-Ost und EU-West) bereitgestellt. Bereitstellung: * Jede Region beherbergt einen vollständigen, unabhängigen Stack aller Dienste (Load Balancer, API Gateway, Shortening/Redirect Services, Key Generation Service, Cassandra Cluster, Redis Cluster, Kafka Cluster usw.). * Ein globaler Load Balancer (z. B. AWS Route 53 mit latenzbasierter Weiterleitung oder ein globaler Traffic Manager) leitet Benutzer zur nächstgelegenen gesunden Region. Datenkonsistenzmodell: * **Cassandra Multi-Datacenter-Replikation**: Cassandras `NetworkTopologyStrategy` wird verwendet, um Daten asynchron zwischen den regionalen Clustern zu replizieren. Jede Region behält eine vollständige Kopie der Daten. * **Schreibvorgänge**: Schreibvorgänge werden typischerweise mit `LOCAL_QUORUM`-Konsistenz innerhalb der primären Region für geringe Latenz durchgeführt. Cassandras integrierte Replikation sorgt für Eventual Consistency über Regionen hinweg. Eine neue kurze URL, die in Region A erstellt wurde, wird schließlich nach Region B repliziert. * **Lesevorgänge**: Lesevorgänge werden ebenfalls typischerweise mit `LOCAL_QUORUM`-Konsistenz für geringe Latenz durchgeführt und bedienen Daten aus dem Cassandra-Cluster oder Cache der lokalen Region. Wenn ein Schlüssel lokal nicht gefunden wird (z. B. aufgrund von Replikationsverzögerungen für eine sehr neue URL), könnte ein Fallback auf einen Cross-Region-Lesevorgang implementiert werden, dies würde jedoch höhere Latenz verursachen. Angesichts der Leseintensität und des Caches ist dies selten. Kompromisse (CAP-Theorem): * **Gewählt**: Priorisierung von **Verfügbarkeit** und **Partitionstoleranz** gegenüber starker **Konsistenz** über Regionen hinweg. * **Begründung**: Für einen URL-Shortening-Dienst ist es wichtiger, dass der Dienst immer verfügbar und schnell ist, auch wenn eine neu erstellte URL einige Millisekunden benötigt, um global zugänglich zu sein. Starke Konsistenz über geografisch verteilte Rechenzentren hinweg würde inakzeptable Schreiblatenz und Komplexität einführen. Eventual Consistency ist ein geeigneter Kompromiss. TTL-Ablauf und URL-Rückgewinnungsmechanismus: 1. **Ablauf**: Der Zeitstempel `expires_at` in der Tabelle `short_urls` wird verwendet. Der Expiration & Reclamation Service (eine Reihe von Hintergrund-Workern) scannt periodisch die Tabelle `short_urls` nach Einträgen, bei denen `expires_at` in der Vergangenheit liegt und `status` 'active' ist. * Nach Identifizierung einer abgelaufenen URL aktualisiert der Dienst ihren `status` in Cassandra auf 'expired'. * Anschließend wird ein 'url_expired'-Ereignis an die Message Queue gesendet, was die Cache-Invalidierung für diesen `short_url_key` in Redis und CDN auslöst. 2. **Rückgewinnung**: Nach einer konfigurierbaren Kulanzfrist (z. B. 24-48 Stunden) nach dem Ablauf (um sicherzustellen, dass alle Caches geleert sind und keine laufenden Redirects betroffen sind), identifiziert der Expiration & Reclamation Service URLs mit dem `status` 'expired', die ihre Kulanzfrist überschritten haben. * Anschließend wird ihr `status` auf 'reclaimable' aktualisiert. * Der `short_url_key` wird dann wieder dem Pool verfügbarer Schlüssel des Key Generation Service hinzugefügt. Dies stellt sicher, dass der 7-Zeichen-Schlüsselraum im Laufe der Zeit effizient wiederverwendet wird. * Eine abschließende Prüfung auf Eindeutigkeit vor der Rückgabe in den Pool kann durchgeführt werden, obwohl das Design des Key Generation Service echte Kollisionen verhindern sollte. Fehlermodi und Wiederherstellung: 1. **Datenbankknotenausfall (z. B. Absturz eines Cassandra-Knotens)**: * **Erkennung**: Überwachungssysteme erkennen die Nichterreichbarkeit des Knotens oder hohe Fehlerraten. * **Wiederherstellung**: Cassandras verteilte Architektur mit einem Replikationsfaktor (RF) von 3 (oder höher) gewährleistet Datenredundanz. Wenn ein Knoten ausfällt, bedienen andere Replikate die Daten. Der Cluster bleibt betriebsbereit. Der ausgefallene Knoten kann automatisch ersetzt oder manuell wieder online gebracht werden. Kein Datenverlust, minimale Serviceunterbrechung. 2. **Ausfall des Key Generation Service**: * **Erkennung**: Health Checks und Überwachung erkennen die Nichtverfügbarkeit des Dienstes oder die Erschöpfung des Schlüsselpools. * **Wiederherstellung**: Der Key Generation Service wird mit mehreren Instanzen bereitgestellt. Wenn eine ausfällt, übernehmen andere. Wenn der gesamte Dienst ausfällt, schlagen neue URL-Verkürzungsanfragen vorübergehend fehl, da sie keinen eindeutigen Schlüssel erhalten können. Bestehende Redirects funktionieren jedoch weiterhin normal. Auto-Scaling-Gruppen starten neue Instanzen. Ein großer vorab generierter Schlüsselpuffer (Milliarden von Schlüsseln) reduziert die Auswirkungen vorübergehender Ausfälle erheblich. 3. **Ausfall des Cache-Clusters (z. B. Redis Cluster-Ausfall)**: * **Erkennung**: Überwachung erkennt die Nichtverfügbarkeit von Redis-Knoten oder -Clustern. * **Wiederherstellung**: Der Redirect Service greift auf die Cassandra-Datenbank zurück, wenn der Cache nicht verfügbar ist. Dies führt zu einer erhöhten Redirect-Latenz (von <10ms auf potenziell 50-100ms) und einer höheren Last auf Cassandra, aber der Dienst bleibt voll funktionsfähig (eingeschränkte Leistung). Redis Cluster mit Replikation bietet hohe Verfügbarkeit und mildert vollständige Cluster-Ausfälle. 4. **Ausfall einer gesamten Region**: * **Erkennung**: Globaler Load Balancer (z. B. Route 53 Health Checks) erkennt, dass alle Dienste in einer Region nicht fehlerfrei sind. * **Wiederherstellung**: Der globale Load Balancer leitet automatisch den gesamten Datenverkehr zur gesunden sekundären Region um. Benutzer können während des Failovers einen kurzen Latenzanstieg erleben, aber der Dienst bleibt verfügbar. Die Datenkonsistenz kann leicht hinterherhinken, aber das System ist darauf ausgelegt, Eventual Consistency zu tolerieren. Getroffene Schlüsselkompromisse und erwogene Alternativen: 1. **Konsistenz vs. Verfügbarkeit/Latenz (CAP-Theorem)**: * **Gewählt**: Eventual Consistency für die plattformübergreifende Datenreplikation und hohe Verfügbarkeit/geringe Latenz bei Lesevorgängen. * **Abgelehnt**: Starke Konsistenz über Regionen hinweg. * **Begründung**: Starke Konsistenz würde erhebliche Latenz für Schreibvorgänge und plattformübergreifende Lesevorgänge einführen, was für einen hochvolumigen, latenzarmen Redirect-Dienst inakzeptabel ist. Wenige Millisekunden Inkonsistenz für ein neues URL-Mapping sind ein geringer Kompromiss im Vergleich zu den Vorteilen hoher Verfügbarkeit und Leistung. 2. **Schlüsselgenerierungsstrategie (Vorabgeneriert vs. On-the-fly-Hashing/Sequenziell)**: * **Gewählt**: Vorabgenerierte zufällige alphanumerische Schlüssel über einen dedizierten Dienst. * **Abgelehnt**: Hashing der langen URL (z. B. MD5, SHA-256 gekürzt) oder Verwendung eines Base-62-Encoders auf einer automatisch inkrementierenden ID. * **Begründung**: Hashing kann zu Kollisionen führen (insbesondere bei einem 7-Zeichen-Limit), was eine komplexe Kollisionslösungslogik erfordert und den Schreibpfad verlangsamt und komplexer macht. Base-62 auf automatisch inkrementierenden IDs macht URLs sequenziell und leicht zu erraten, was eine Schlüsselanforderung verletzt. Vorabgenerierung gewährleistet Eindeutigkeit, Nicht-Erkennbarkeit und schnelle Schlüsselabfrage während des Schreibens, was den Verkürzungsprozess vereinfacht. 3. **Datenbankwahl (NoSQL vs. Relational SQL)**: * **Gewählt**: Apache Cassandra (NoSQL). * **Abgelehnt**: PostgreSQL/MySQL (Relational SQL). * **Begründung**: Relationale Datenbanken haben Schwierigkeiten mit dem extremen Lese-/Schreibdurchsatz und den Anforderungen an die horizontale Skalierbarkeit dieses Dienstes ohne erhebliche Sharding-Komplexität. NoSQL-Datenbanken wie Cassandra sind speziell für diese Skalierung, hohe Verfügbarkeit und Leistung ausgelegt, insbesondere für einfache Schlüssel-Wert-Abfragen, was das primäre Zugriffsmuster ist. 4. **TTL-Implementierung (Hintergrunddienst vs. Datenbank-TTL)**: * **Gewählt**: Dedizierter Expiration & Reclamation Service, der `expires_at` scannt. * **Abgelehnt**: Sich ausschließlich auf die Datenbank-TTL verlassen (z. B. die integrierte TTL von Cassandra). * **Begründung**: Obwohl die Datenbank-TTL Daten automatisch ablaufen lassen kann, erleichtert sie nicht die kontrollierte Rückgewinnung des `short_url_key` in einen wiederverwendbaren Pool oder die Auslösung expliziter Cache-Invalidierungen. Ein dedizierter Dienst bietet eine granularere Kontrolle über den gesamten Lebenszyklus, einschließlich der Kulanzfrist und der sicheren Schlüsselwiederverwendung.