Concevoir un service de raccourcissement d'URL à grande échelle

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 la création d'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. Les vérifications de santé et les basculements sont configurés. - API Gateway Régionale + Load Balancer (API Gateway / ALB) : Accepte les écritures 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 a 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égions. - 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 de réclamation, 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 la redirection mise en cache -> si succès, renvoie la redirection mise en cache (<5 ms). En cas d'échec, l'Edge transmet au LB régional -> Le Service de Redirection interroge le cache Redis -> si succès, renvoie la redirection et l'Edge la met en cache ; en cas d'échec, 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é Objectifs : Jeton alphanumérique max de 7 caractères, non devinable (pas de jetons séquentiels), faible probabilité de collision, comportement de panne/reprise 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é forcée. Si l'insertion échoue en raison d'une rare collision, réessayer avec un nouveau jeton aléatoire (probabilité de collision attendue négligeable ; reprises attendues << 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 plusieurs variations d'entrée et complique le TTL/la révocation. Schéma de base de données et technologie de stockage (avec justification) Magasin 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égions (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éclamation. 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 d'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 redirection au 95e percentile < 10 ms à grande échelle, minimiser la charge de la base de données, supporter le multi-régions. 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é au TTL restant. 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 microsecondes. Hypothèses de succès de 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'API CDN (ou définir un court TTL de cache à 0 et laisser 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 de réclamation. 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 -> Le 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 miss Edge : la requête est transmise au LB régional -> Service de Redirection. 4. Le Service de Redirection consulte le cache en mémoire (minuscule) -> Redis cluster get(short_id). Le GET Redis est inférieur à la milliseconde en fonction du réseau (généralement <1 ms dans la région). Si succès Redis, le service renvoie la redirection et l'Edge la met en cache avec un TTL approprié. 5. Si miss Redis : le service interroge la base de données principale (DynamoDB GetItem) qui est en millisecondes à un seul chiffre, 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 réduire de moitié le coût RCU). Chemin d'écriture (détaillé) et débit Chemin d'écriture : 1. Le client soumet une demande 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 PutItem conditionnel que short_id n'existe pas (atomique). Si PutItem échoue en raison d'une clé existante (rare), régénérer. L'insertion inclut long_url, created_at, expires_at. 4. Lors de l'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. Renvoyer l'URL courte au client. Dimensionnement du débit pour les écritures : - Base de 39 écritures/sec en moyenne, 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 un 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 que les partitions restent 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 de 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égions et modèle de cohérence Modèle choisi : Multi-régions 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. Justification et compromis CAP : - Exigence : 99,9 % de disponibilité et reprise après sinistre inter-régions. Prioriser 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 pour les 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 cohérente forte 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éclamation d'URL Exigences : TTL configurable par URL courte (par défaut 5 ans), les URL expirées doivent être réclamables. 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éclamation 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 un GSI sur deletion_marked_at ou les événements TTL de la table) et déplacent la clé dans une File de Réclamation avec les métadonnées : short_id, deletion_marked_at, original_expires_at. - Politique de réclamation : Introduire une période de grâce configurable (par exemple, 30 jours) après l'expiration pendant laquelle le short_id est marqué comme effacé (drapeau deleted et enregistrement de 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 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éclamation déplace le short_id dans un Pool de Jetons Réclamables (sujet Kafka ou table de pool de jetons DynamoDB). Les jetons dans le pool peuvent être recyclés ; les jetons réclamés incluent un temps de refroidissement et ne sont jamais immédiatement réattribués 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 recycler les jetons, préférer maintenir le taux de recyclage extrêmement bas car l'espace de 7 caractères est grand. Modes de défaillance et récupération 1) Panne CDN / Edge dans une région ou perturbation globale d'un fournisseur Edge - Impact : La mise en cache Edge s'arrête ; 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 au préalable. Le système accepte cela en échange d'une haute disponibilité. La réconciliation d'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 sur 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 via la pré-extraction des clés les plus chaudes en utilisant l'analyse/les 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 suralimenté à courte durée de vie combiné à un sel HMAC). Ajouter une surveillance du taux de collision ; si le taux de collision > seuil trivial, arrêter d'émettre de nouveaux jetons et renvoyer 5xx jusqu'à résolution. 5) Retard dans la file d'attente des consommateurs du flux d'événements ou panne des workers - Impact : Les invalidations de cache, le traitement de l'analyse et la réclamation sont retardés. - Récupération : Autoscaling des consommateurs, prioriser les sujets d'invalidation et de réclamation, 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. Compromis clés 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égions. 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 sécurisés cryptographiquement 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égions 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éclamation de jetons vs ne jamais réutiliser de jetons - Choisi : Réclamable 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éclamation est requise par la spécification. La sécurité est accrue par la conservation des tombstones et un délai avant la réémission. Le non-réutilisation a été rejeté car après de nombreuses années, il pourrait y avoir un besoin de conserver l'espace de noms si les jetons s'épuisent dans des scénarios pathologiques. 5) Mise en cache à l'Edge vs uniquement origine directe - Choisi : Mise en cache intensive à l'Edge avec des TTL courts. Raison : atteindre une latence au 95e percentile < 10 ms pour les utilisateurs mondiaux. L'origine directe uniquement a été 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 le 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é et 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 base62 de 7 caractères 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égions actif-actif) pour respecter les SLA de disponibilité et de latence, tandis que la réclamation et le TTL sont gérés par le TTL de la DB plus un pipeline de réclamation 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 respecter l'objectif de disponibilité de 99,9 %.

Ce système de conception décrit un service de raccourcissement d'URL robuste, évolutif et hautement disponible, capable de gérer 100 millions de nouveaux raccourcissements et 10 milliards de redirections par mois, avec des exigences strictes en matière de latence et de disponibilité. Description de l'architecture de haut niveau : L'architecture est conçue pour une haute disponibilité, une évolutivité et une faible latence, en tirant parti d'une approche de microservices. Les composants clés comprennent : 1. **Équilibreurs de charge (par exemple, AWS ELB/GCP Load Balancer/Nginx)** : distribuent le trafic entrant entre les instances de service. 2. **API Gateway (par exemple, AWS API Gateway/Kong)** : gère les requêtes API, l'authentification, la limitation de débit et achemine le trafic vers les services backend appropriés. 3. **Service de raccourcissement (Chemin d'écriture)** : un microservice sans état responsable du traitement des requêtes de création de nouvelles URL courtes. Il interagit avec le service de génération de clés et la base de données. 4. **Service de redirection (Chemin de lecture)** : un microservice sans état hautement optimisé, responsable de la résolution des URL courtes en URL longues et de l'exécution de la redirection HTTP 301/302. Il repose fortement sur la mise en cache. 5. **Service de génération de clés** : un service dédié responsable de la pré-génération et de la gestion d'un pool de clés d'URL courtes uniques et aléatoires. Il garantit la non-devinabilité et évite les collisions. 6. **Base de données (par exemple, Apache Cassandra)** : le stockage persistant principal pour les mappages d'URL courtes. Choisi pour son débit d'écriture/lecture élevé, son évolutivité horizontale et ses capacités de réplication multi-régions. 7. **Cache distribué (par exemple, Redis Cluster)** : stocke les mappages d'URL courtes fréquemment consultés pour réduire la charge de la base de données et atteindre une faible latence de redirection. 8. **File d'attente de messages (par exemple, Apache Kafka/AWS SQS)** : utilisée pour la communication asynchrone entre les services, telle que la publication d'événements pour l'analyse, l'invalidation du cache et l'expiration des URL. 9. **Service d'analyse** : consomme les événements de la file d'attente de messages pour suivre les nombres de clics, générer des rapports et surveiller les modèles d'utilisation. 10. **Service d'expiration et de récupération** : un service de travail en arrière-plan responsable de l'identification des URL expirées, de leur marquage et du retour de leurs clés dans le pool du service de génération de clés pour réutilisation. 11. **CDN (Réseau de diffusion de contenu, par exemple, Cloudflare/Akamai)** : facultatif mais fortement recommandé pour la mise en cache des redirections en périphérie, réduisant davantage la latence et la charge du serveur d'origine pour les utilisateurs mondiaux. Interactions : * **Chemin d'écriture** : Utilisateur -> Équilibreur de charge -> API Gateway -> Service de raccourcissement -> Service de génération de clés (obtient la clé) -> Base de données (écrit le mappage) -> File d'attente de messages (publie l'événement 'new_url') -> Cache (met à jour/écrit via). * **Chemin de lecture** : Utilisateur -> Équilibreur de charge -> CDN (si succès, redirige) -> Service de redirection (vérifie le cache local -> cache distribué -> base de données) -> Redirection. Algorithme de raccourcissement d'URL et stratégie de génération de clés : Pour garantir la non-devinabilité, l'unicité et respecter la limite de 7 caractères, une stratégie de pré-génération est employée : 1. **Service de génération de clés** : Ce service génère en continu des chaînes alphanumériques aléatoires de 7 caractères (par exemple, en utilisant un générateur de nombres pseudo-aléatoires cryptographiquement sécurisé). L'ensemble de caractères comprend `a-z`, `A-Z`, `0-9`, soit un total de 62 caractères. Une chaîne de 7 caractères permet 62^7 clés uniques, soit environ 3,5 billions, dépassant largement l'exigence de 100 millions d'URL/mois. 2. **Vérification d'unicité** : Avant d'ajouter au pool, chaque clé générée est vérifiée pour son unicité par rapport à la base de données (ou un magasin de clés uniques dédié). Il s'agit d'une vérification unique lors de la génération, et non lors des requêtes de raccourcissement. 3. **Pool de clés** : Les clés uniques sont stockées dans un pool hautement disponible et à accès rapide (par exemple, un ensemble Redis ou une table dédiée dans Cassandra avec un champ 'status' comme 'available'). Le service de génération de clés maintient un grand tampon (par exemple, plusieurs milliards de clés) pour garantir que les clés sont toujours facilement disponibles. 4. **Processus de raccourcissement** : Lorsqu'un utilisateur demande une nouvelle URL courte, le service de raccourcissement demande une clé au service de génération de clés. Le service de génération de clés extrait atomiquement une clé disponible de son pool, la marque comme 'en cours d'utilisation' et la renvoie. Cela évite la contention lors de charges d'écriture élevées. 5. **Évitement des collisions** : En pré-générant et en attribuant atomiquement des clés uniques, les collisions lors de la requête de raccourcissement réelle sont pratiquement éliminées. La base de données impose également une contrainte d'unicité sur la `short_url_key` comme dernière sauvegarde. Schéma de base de données et choix de la technologie de stockage : Choix de la base de données : **Apache Cassandra** (ou AWS DynamoDB comme alternative gérée). Justification : * **Débit d'écriture/lecture élevé** : Cassandra est conçu pour des opérations à haut volume et à faible latence, parfait pour le ratio lecture/écriture de 100:1 et les milliards de lectures. * **Évolutivité horizontale** : Évolue facilement en ajoutant plus de nœuds, en distribuant les données et la charge sur le cluster. * **Haute disponibilité et tolérance aux pannes** : Les données sont répliquées sur plusieurs nœuds et centres de données, garantissant un fonctionnement continu même en cas de défaillance de nœuds. * **Cohérence éventuelle** : Acceptable pour ce cas d'utilisation. Bien qu'une nouvelle URL puisse prendre quelques millisecondes pour se propager dans les régions, cela n'affecte pas la fonctionnalité principale. * **Recherches clé-valeur simples** : Le modèle d'accès principal est `short_url_key` vers `long_url`, ce que Cassandra gère excellemment. Schéma (Keyspace : `url_shortener`, Table : `short_urls`) : ``` CREATE TABLE url_shortener.short_urls ( short_url_key text PRIMARY KEY, -- Clé de partition, 7 caractères alphanumériques long_url text, user_id text, -- Facultatif, pour les URL spécifiques à l'utilisateur created_at timestamp, expires_at timestamp, click_count counter, -- Type compteur Cassandra pour incréments atomiques status text -- 'active', 'expired', 'reclaimed' ); ``` Stratégie de mise en cache et approche d'invalidation du cache : La mise en cache est essentielle pour atteindre la latence de redirection <10 ms et gérer 10 milliards de redirections/mois. Stratégie : 1. **Mise en cache multi-niveaux** : * **CDN (Cache périphérique)** : met en cache les redirections dans des points de présence géographiquement distribués. C'est la première ligne de défense pour les requêtes de lecture. * **Cache distribué (Redis Cluster)** : un cache central haute performance stockant les mappages `short_url_key` vers `long_url`. Chaque entrée stocke également `expires_at`. * **Cache en mémoire** : chaque instance du service de redirection maintient un petit cache en mémoire rapide pour les URL les plus consultées. 2. **Lecture directe (Read-Through)** : Lorsque le service de redirection reçoit une requête, il vérifie d'abord son cache en mémoire, puis le cluster Redis. S'il n'est pas trouvé, il récupère depuis Cassandra, stocke le mappage dans Redis et son cache local, puis redirige. 3. **Écriture directe (Write-Through)** : Lorsqu'une nouvelle URL est raccourcie, le service de raccourcissement écrit le mappage dans Cassandra, puis l'écrit immédiatement dans le cluster Redis. Invalidation du cache : 1. **Expiration basée sur TTL** : les entrées de cache dans Redis et les caches en mémoire ont un TTL configurable (par exemple, 5 minutes ou aligné sur `expires_at` de l'URL). Cela gère la cohérence éventuelle et garantit que les données obsolètes ne persistent pas indéfiniment. 2. **Invalidation explicite** : Lorsqu'une URL expire ou est récupérée par le service d'expiration et de récupération, un événement est publié dans la file d'attente de messages. Les travailleurs d'invalidation de cache consomment cet événement et suppriment explicitement l'entrée correspondante du cluster Redis. Les caches CDN sont invalidés via des appels API ou en définissant des en-têtes `Cache-Control` appropriés avec un `max-age` court pour les redirections. Chemin de lecture et chemin d'écriture avec calculs de débit : Hypothèses : 1 mois = 2 592 000 secondes. Chemin d'écriture (100 millions de nouveaux raccourcissements d'URL par mois) : * **Débit moyen** : 100 000 000 URL / 2 592 000 secondes ≈ 38,6 écritures/seconde. * **Débit de pointe** : En supposant que le pic est 3 fois la moyenne, concevoir pour ~120 écritures/seconde. * **Flux** : Équilibreur de charge -> API Gateway -> Service de raccourcissement (demande une clé au service de génération de clés, écrit dans Cassandra, écrit dans Redis, publie un événement dans Kafka). * **Composants** : Plusieurs instances du service de raccourcissement, du service de génération de clés, des nœuds Cassandra, des nœuds Redis, des courtiers Kafka. * **Cible de latence** : Moins de 100 ms pour les écritures (moins critique que les lectures). Chemin de lecture (10 milliards de redirections par mois) : * **Débit moyen** : 10 000 000 000 redirections / 2 592 000 secondes ≈ 3 858 lectures/seconde. * **Débit de pointe** : En supposant que le pic est 3 fois la moyenne, concevoir pour ~12 000 lectures/seconde. * **Flux** : Utilisateur -> CDN (si succès, redirige) -> Équilibreur de charge -> Service de redirection (vérifie le cache en mémoire -> cluster Redis -> Cassandra) -> Redirection. * **Taux de succès du cache** : Viser un taux de succès du cache >95 % (CDN + Redis) pour décharger Cassandra. * **Lectures DB effectives** : 12 000 lectures/sec * 5 % (taux d'échec du cache) = 600 lectures/seconde vers Cassandra. * **Cible de latence** : Moins de 10 ms au 95e percentile. * **Composants** : De nombreuses instances du service de redirection, des nœuds de cluster Redis, des nœuds Cassandra. Le CDN joue un rôle crucial. Stratégie d'évolutivité : 1. **Évolutivité horizontale (Services sans état)** : Tous les services sans état (API Gateway, Service de raccourcissement, Service de redirection, Service de génération de clés, Service d'analyse, Service d'expiration et de récupération) sont déployés comme plusieurs instances derrière des équilibreurs de charge. Ils peuvent être mis à l'échelle en ajoutant plus d'instances en fonction de l'utilisation du CPU, de la mémoire ou de la profondeur de la file d'attente de requêtes (par exemple, en utilisant Kubernetes HPA ou AWS Auto Scaling Groups). 2. **Évolutivité de la base de données (Cassandra)** : Cassandra évolue horizontalement en ajoutant plus de nœuds au cluster. Les données sont automatiquement rééquilibrées. Cela permet d'augmenter la capacité de stockage et le débit de lecture/écriture. 3. **Évolutivité du cache (Redis Cluster)** : Redis Cluster fournit le partitionnement et la réplication, lui permettant de s'adapter horizontalement en ajoutant plus de nœuds maîtres et répliques. 4. **Évolutivité de la file d'attente de messages (Kafka)** : Kafka est intrinsèquement évolutif, permettant d'augmenter le débit en ajoutant plus de courtiers et de partitions. 5. **CDN** : décharge une partie importante du trafic de lecture des serveurs d'origine, ce qui permet de mettre à l'échelle le chemin de lecture à l'échelle mondiale. 6. **Microservices** : L'architecture modulaire permet de mettre à l'échelle les services individuels indépendamment en fonction de leurs besoins de charge spécifiques. Déploiement multi-régions et modèle de cohérence des données : Pour atteindre 99,9 % de disponibilité et de reprise après sinistre, le service sera déployé dans une configuration Active-Active sur au moins deux régions géographiques (par exemple, US-East et EU-West). Déploiement : * Chaque région héberge une pile complète et indépendante de tous les services (Équilibreurs de charge, API Gateway, Services de raccourcissement/redirection, Service de génération de clés, cluster Cassandra, cluster Redis, cluster Kafka, etc.). * Un équilibreur de charge global (par exemple, AWS Route 53 avec routage basé sur la latence ou un gestionnaire de trafic mondial) dirige les utilisateurs vers la région saine la plus proche. Modèle de cohérence des données : * **Réplication multi-centres de données Cassandra** : la `NetworkTopologyStrategy` de Cassandra est utilisée pour répliquer les données de manière asynchrone entre les clusters régionaux. Chaque région conserve une copie complète des données. * **Écritures** : les écritures sont généralement effectuées avec une cohérence `LOCAL_QUORUM` au sein de la région principale pour une faible latence. La réplication intégrée de Cassandra assure la cohérence éventuelle entre les régions. Une nouvelle URL courte créée dans la région A sera éventuellement propagée à la région B. * **Lectures** : les lectures sont également généralement effectuées avec une cohérence `LOCAL_QUORUM` pour une faible latence, en servant les données du cluster Cassandra ou du cache de la région locale. Si une clé n'est pas trouvée localement (par exemple, en raison d'un décalage de réplication pour une URL très récente), un recours à une lecture inter-régions pourrait être implémenté, mais cela entraînerait une latence plus élevée. Compte tenu de la nature intensive en lecture et de la mise en cache, cela est rare. Compromis (Théorème CAP) : * **Choisi** : Prioriser la **disponibilité** et la **tolérance aux partitions** par rapport à la **cohérence** forte entre les régions. * **Raisonnement** : Pour un service de raccourcissement d'URL, il est plus critique que le service soit toujours disponible et performant rapidement, même si une URL nouvellement créée prend quelques millisecondes pour être accessible mondialement. Une cohérence forte entre des centres de données géographiquement dispersés introduirait une latence d'écriture et une complexité inacceptables. La cohérence éventuelle est un compromis approprié. Mécanisme d'expiration TTL et de récupération d'URL : 1. **Expiration** : L'horodatage `expires_at` dans la table `short_urls` est utilisé. Le service d'expiration et de récupération (un ensemble de travailleurs en arrière-plan) scanne périodiquement la table `short_urls` pour les entrées où `expires_at` est dans le passé et `status` est 'active'. * Lors de l'identification d'une URL expirée, le service met à jour son `status` à 'expired' dans Cassandra. * Il publie ensuite un événement 'url_expired' dans la file d'attente de messages, déclenchant l'invalidation du cache pour cette `short_url_key` dans Redis et le CDN. 2. **Récupération** : Après une période de grâce configurable (par exemple, 24-48 heures) suivant l'expiration (pour s'assurer que tous les caches sont effacés et qu'aucune redirection en cours n'est affectée), le service d'expiration et de récupération identifie les URL avec le `status` 'expired' qui ont dépassé leur période de grâce. * Il met ensuite à jour leur `status` à 'reclaimable'. * La `short_url_key` est ensuite ajoutée au pool de clés disponibles du service de génération de clés. Cela garantit que l'espace de clés alphanumériques à 7 caractères est réutilisé efficacement au fil du temps. * Une vérification finale d'unicité avant de réintégrer le pool peut être effectuée, bien que la conception du service de génération de clés doive empêcher les collisions réelles. Modes de défaillance et récupération : 1. **Défaillance d'un nœud de base de données (par exemple, crash d'un nœud Cassandra)** : * **Détection** : Les systèmes de surveillance détectent l'inaccessibilité du nœud ou des taux d'erreur élevés. * **Récupération** : L'architecture distribuée de Cassandra avec un facteur de réplication (RF) de 3 (ou plus) garantit la redondance des données. Si un nœud échoue, d'autres répliques servent les données. Le cluster reste opérationnel. Le nœud défaillant peut être remplacé automatiquement ou remis en ligne manuellement. Aucune perte de données, interruption minimale du service. 2. **Défaillance du service de génération de clés** : * **Détection** : Les vérifications de santé et la surveillance détectent l'indisponibilité du service ou l'épuisement du pool de clés. * **Récupération** : Le service de génération de clés est déployé avec plusieurs instances. Si l'une échoue, les autres prennent le relais. Si l'ensemble du service échoue, les requêtes de raccourcissement de nouvelles URL échoueront temporairement car elles ne pourront pas obtenir de clé unique. Cependant, les redirections existantes continueront de fonctionner normalement. Les groupes d'auto-mise à l'échelle lanceront de nouvelles instances. Un grand tampon de clés pré-générées (milliards de clés) réduit considérablement l'impact des pannes temporaires. 3. **Défaillance du cluster de cache (par exemple, panne du cluster Redis)** : * **Détection** : La surveillance détecte l'indisponibilité d'un nœud ou du cluster Redis. * **Récupération** : Le service de redirection est conçu pour se rabattre sur la base de données Cassandra si le cache est indisponible. Cela entraînera une latence de redirection accrue (de <10 ms à potentiellement 50-100 ms) et une charge plus élevée sur Cassandra, mais le service restera pleinement fonctionnel (performances dégradées). Redis Cluster avec réplication offre une haute disponibilité, atténuant les pannes complètes du cluster. 4. **Panne de région entière** : * **Détection** : L'équilibreur de charge global (par exemple, les vérifications de santé de Route 53) détecte que tous les services d'une région sont non sains. * **Récupération** : L'équilibreur de charge global redirige automatiquement tout le trafic vers la région secondaire saine. Les utilisateurs pourraient connaître une brève augmentation de la latence pendant le basculement, mais le service reste disponible. La cohérence des données peut être légèrement en retard, mais le système est conçu pour tolérer la cohérence éventuelle. Compromis clés effectués et alternatives considérées : 1. **Cohérence vs Disponibilité/Latence (Théorème CAP)** : * **Choisi** : Cohérence éventuelle pour la réplication des données inter-régions et la haute disponibilité/faibles lectures de latence. * **Rejeté** : Cohérence forte entre les régions. * **Raisonnement** : La cohérence forte introduirait une latence significative pour les écritures et les lectures inter-régions, ce qui est inacceptable pour un service de redirection à haut débit et à faible latence. Quelques millisecondes d'incohérence pour un nouveau mappage d'URL sont un compromis mineur par rapport aux avantages de la haute disponibilité et des performances. 2. **Stratégie de génération de clés (Pré-générées vs Hachage à la volée/Séquentiel)** : * **Choisi** : Clés alphanumériques aléatoires pré-générées via un service dédié. * **Rejeté** : Hachage de l'URL longue (par exemple, MD5, SHA-256 tronqué) ou utilisation d'un encodeur base-62 sur un ID auto-incrémenté. * **Raisonnement** : Le hachage peut entraîner des collisions (surtout avec une limite de 7 caractères) nécessitant une logique de résolution de collisions complexe, ajoutant de la latence et de la complexité au chemin d'écriture. La base-62 sur des ID auto-incrémentés rend les URL séquentielles et devinables, violant une exigence clé. La pré-génération garantit l'unicité, la non-devinabilité et la récupération rapide des clés lors des écritures, simplifiant le processus de raccourcissement. 3. **Choix de la base de données (NoSQL vs SQL relationnel)** : * **Choisi** : Apache Cassandra (NoSQL). * **Rejeté** : PostgreSQL/MySQL (SQL relationnel). * **Raisonnement** : Les bases de données relationnelles peinent avec le débit extrême de lecture/écriture et les exigences d'évolutivité horizontale de ce service sans complexité de partitionnement significative. Les bases de données NoSQL comme Cassandra sont conçues sur mesure pour cette échelle, cette haute disponibilité et ces performances, en particulier pour les recherches simples clé-valeur, qui constituent le modèle d'accès principal. 4. **Implémentation TTL (Service d'arrière-plan vs TTL de base de données)** : * **Choisi** : Service d'expiration et de récupération dédié scannant `expires_at`. * **Rejeté** : S'appuyer uniquement sur le TTL au niveau de la base de données (par exemple, le TTL intégré de Cassandra). * **Raisonnement** : Bien que le TTL de la base de données puisse expirer automatiquement les données, il ne facilite pas facilement la récupération contrôlée de la `short_url_key` dans un pool réutilisable ni le déclenchement d'une invalidation explicite du cache. Un service dédié offre un contrôle plus granulaire sur le cycle de vie complet, y compris la période de grâce et la réutilisation sûre des clés.