Concevoir un raccourcisseur d’URL : le code court est la partie facile

Demandez à n’importe qui de concevoir un raccourcisseur d’URL et la première réponse arrive en quelques secondes : stocker code → url, chercher le code, rediriger. Cette réponse est juste, et c’est aussi la plus petite partie de la conception. Un raccourcisseur est un bon exercice justement parce que son cœur est trivial — chaque décision qui compte porte sur ce qui se passe autour : quel chemin doit être rapide, quel travail peut attendre, et quelle panne a le droit d’atteindre la personne qui a cliqué.

Cet article construit une architecture en quatre étapes. Chaque étape part d’un problème que la précédente ne sait pas traiter, n’ajoute que ce que ce problème exige, et dit ce que cela coûte. Si vous connaissez déjà le terrain, passez directement à l’architecture finale. Si vous êtes là pour apprendre, lisez dans l’ordre : le schéma final ne paraît évident qu’une fois que vous avez vu pourquoi chaque boîte est arrivée.

Les hypothèses

Ce sont les chiffres qui décident de l’architecture, alors voici ceux dont part cette conception. Ce sont des hypothèses pour l’exercice, volontairement arrondies — pas des mesures d’un service réel :

• 50 millions de nouveaux liens par mois, soit environ 20 créations par seconde en moyenne.
• 100 redirections pour chaque lien créé : environ 2 000 redirections par seconde en moyenne, avec des pics dix fois plus élevés quand un lien se propage.
• Environ 500 octets par lien (l’URL longue, le code, un propriétaire, des horodatages) : environ 25 Go de nouvelles données par mois, 300 Go par an.
• Un événement de clic par redirection, conservé pour l’analytique.

Deux choses ressortent déjà. Les écritures sont minuscules : 20 par seconde, ce n’est rien pour n’importe quelle base de données. Et la redirection, c’est le produit : c’est la requête qu’attendent de vraies personnes, des milliers de fois par seconde, et elle se dresse entre elles et la page qu’elles voulaient réellement. Créer un lien peut prendre quelques centaines de millisecondes sans que personne ne le remarque ; une redirection aussi lente donne l’impression que chaque lien est cassé.

La conception détaillée dans Learn part d’un service plus petit, avec d’autres chiffres. La forme de la réponse est la même, et c’est bien là le propos : l’estimation change les tailles, pas le raisonnement.

Étape 1 : faire fonctionner

Commencez par la plus petite chose qui soit correcte. Un client parle à un service sans état, et le service stocke les liens dans une base de données relationnelle. Il y a deux opérations : POST /links stocke une URL longue et renvoie un code, et GET /{code} cherche le code et répond par une redirection.

Même cette première version fait tourner au moins deux instances du service derrière un répartiteur de charge. Ce n’est pas une question d’échelle — une seule instance suffirait pour ce trafic —, c’est le minimum pour la disponibilité : avec une seule instance, chaque déploiement et chaque crash est une interruption de service. Le service ne garde aucun état propre, donc n’importe quelle instance peut répondre à n’importe quelle requête, et ajouter des instances plus tard relève d’un changement de configuration, pas d’une refonte.

En savoir plusConception résolue : un raccourcisseur de liensRépartition de charge et mise à l'échelle horizontaleGénération d'ID uniques

Le code court lui-même

Le modèle de données tient en une seule table — code, URL longue, propriétaire, date de création — avec le code comme clé primaire. La seule vraie décision est la façon de fabriquer les codes, et il y a deux réponses raisonnables.

Codes aléatoires. Tirez sept caractères dans un alphabet de 62 (base62 : 26 lettres minuscules, 26 lettres majuscules et 10 chiffres), insérez, et réessayez si la contrainte d’unicité rejette la ligne. Sept caractères donnent environ 3,5 billions de combinaisons, donc même après un an de ce trafic une collision reste rare et la nouvelle tentative ne s’exécute que rarement. Les codes aléatoires sont aussi pratiquement impossibles à deviner, ce qui compte plus qu’il n’y paraît : avec des codes séquentiels, quiconque détient un lien peut essayer les codes voisins, et les gens raccourcissent souvent des liens qu’ils n’ont jamais eu l’intention de publier.

Codes fondés sur un compteur. Prenez le nombre suivant d’une séquence que la base de données fournit déjà et encodez-le en base62 — pas de collisions, pas de nouvelles tentatives. Le prix, c’est la prévisibilité, puisque des nombres consécutifs donnent des codes consécutifs. La parade habituelle consiste à faire passer le nombre par un brouillage réversible, une permutation à clé, avant de l’encoder : les codes restent uniques mais ne se suivent plus.

Cette conception utilise le compteur brouillé : l’unicité par construction, des codes que personne ne peut énumérer, et aucun nouveau composant, car le nombre vient de la base de données que nous avons déjà, dans la même transaction que l’insertion. Les codes aléatoires seraient tout aussi défendables. Ce qui compte, c’est que le choix soit petit, circonscrit et facile à changer plus tard.

Étape 2 : la redirection devient le chemin chaud

À 2 000 redirections par seconde, la première étape tient sans problème. Au pic — 20 000 par seconde pendant qu’un lien circule partout —, chaque redirection reste une requête en base, et la base de données doit être dimensionnée pour la pire minute du mois. C’est une façon coûteuse de servir une lecture qui ne change presque jamais.

La destination d’un lien est écrite une fois et lue des milliers de fois, ce qui en fait le cas d’école pour un cache. Le service applique le cache-aside : lors d’une redirection, il cherche d’abord le code dans le cache. En cas de hit, il répond immédiatement ; en cas de miss, il lit la base de données, stocke le résultat dans le cache avec une durée de vie (TTL), et répond.

Le service interroge d’abord le cache ; la base de données ne répond qu’aux miss.

En savoir plusCouches de mise en cacheClés chaudes et tempêtes de cache (cache stampede)

Trois détails décident si ce cache aide ou nuit :

• La base de données reste la source de vérité. Créer un lien écrit dans la base de données et ne rend la main qu’après le commit ; le cache est rempli à la première lecture. Si le cache disparaissait, chaque lien existerait toujours — les redirections seraient simplement plus lentes.
• Le TTL est une affirmation sur le changement. Les liens changent rarement, donc un TTL long — des heures ou des jours — ne pose pas de problème. Quand un lien est supprimé ou que sa destination est modifiée, le service supprime aussi l’entrée du cache, et le TTL borne la durée pendant laquelle une suppression manquée peut survivre.
• Les codes inconnus ont eux aussi une réponse en cache. Les scanners demandent sans arrêt des codes aléatoires. Mettre en cache « introuvable » pendant une minute les tient à l’écart de la base de données. Seul un vrai « introuvable » est mis en cache ainsi — jamais une erreur de base de données —, et créer un lien supprime toute entrée « introuvable » pour son code.

Le cache change aussi la manière dont le système tombe en panne. S’il est indisponible, les redirections se rabattent sur la base de données — toujours correctes, mais plus lentes —, et la base de données doit soudain encaisser toute la charge que le cache absorbait. Soit la base de données est dimensionnée pour y survivre, soit le service déleste la charge (il répond immédiatement à certaines requêtes par une erreur au lieu de les mettre en file d’attente) jusqu’au retour du cache. La popularité ajoute un second risque : un lien viral est une seule clé chaude, et si son entrée expire au pire moment, une foule de requêtes fait un miss au même instant et chacune d’elles va chercher la même ligne dans la base de données. Cette panne a droit à son propre article sur ce blog, en lien à la fin.

Étape 3 : compter les clics sans ralentir les redirections

Le produit veut maintenant de l’analytique : combien de fois chaque lien a été cliqué, d’où, et quand. L’implémentation évidente écrit une ligne à chaque redirection. C’est aussi la mauvaise, parce qu’elle place une écriture — plus lente que la lecture en cache juste à côté — sur le chemin de latence de chaque clic, sans exception.

La leçon de cette étape tient en une phrase : rediriger le lecteur et enregistrer le clic n’ont pas besoin du même contrat de latence. Le lecteur a besoin d’une redirection en quelques millisecondes. L’analytique a besoin que le clic finisse par arriver, compté correctement. Le service publie donc un petit événement de clic dans une file de messages et répond à la redirection sans rien attendre d’autre. Un worker consomme la file et écrit les événements, par lots, dans un stockage conçu pour l’analytique.

En savoir plusFiles de messages et workers asynchronesIdempotence et illusions de l'exactement-une-fois

Les hypothèses expliquent pourquoi les clics ont leur propre stockage. Les liens grossissent de 25 Go par mois. Les clics arrivent à 2 000 par seconde — environ 170 millions d’événements par jour — et, à environ 100 octets chacun, cela fait autour de 500 Go par mois, vingt fois le volume des liens. Le plus gros jeu de données d’un raccourcisseur d’URL, ce ne sont pas les liens, et la base de données qui répond aux redirections ne devrait pas être aussi celle qui compte les clics par pays de la semaine dernière.

La frontière asynchrone a des coûts, et ils méritent d’être énoncés franchement :

• La livraison est « au moins une fois ». Un worker qui plante après avoir écrit un lot mais avant de l’avoir acquitté recevra ce lot à nouveau. Chaque événement porte un ID et le côté analytique ignore les ID qu’il a déjà vus, donc le consommateur est idempotent et une nouvelle tentative ne peut pas compter deux fois.
• Les comptages sont en retard. Un clic apparaît dans l’analytique quelques secondes après la redirection, ou plus si le worker prend du retard. Pour de l’analytique, c’est acceptable, et c’est une décision plutôt qu’un accident.
• La file peut tomber en panne. Si la publication échoue, la redirection réussit quand même : le service peut garder quelques secondes d’événements en local et abandonner le reste. Perdre une poignée de clics pendant une panne est le prix que paie cette conception pour qu’un problème d’analytique ne devienne jamais un problème de redirection.

Étape 4 : quand la base de données est le point de défaillance unique

Regardez ce qui est encore seul. Le service tourne sur plusieurs instances. Le cache peut disparaître sans perte de données. La file absorbe un worker lent ou en panne. La base de données est une seule machine qui détient l’unique copie de chaque lien : si elle tombe, la création s’arrête et chaque miss de cache échoue, et un disque perdu emporte tout ce qui a été écrit depuis la dernière sauvegarde.

La solution est un réplica de secours qui reçoit une copie de chaque écriture peu après son commit, et qui peut être promu pour prendre la place du primaire. Remarquez à quoi il sert : la disponibilité et la durabilité, pas la capacité de lecture. Le cache a déjà retiré la charge de lecture de la base de données, donc un réplica ajouté « pour les lectures » resterait la plupart du temps inactif. Un réplica et un cache répondent à des questions différentes, et un autre article de ce blog explique cette distinction.

En savoir plusRéplication et réplicas de lectureSharding et partitionnement

Ici, la réplication est asynchrone, ce qui est un compromis en soi : le primaire confirme une écriture sans attendre le réplica. Si le primaire tombe, les dernières écritures peuvent ne jamais atteindre le réplica, de sorte qu’un lien créé une seconde avant la panne pourrait être perdu. La réplication synchrone comble cet écart au prix d’écritures plus lentes et d’un chemin de création qui dépend de deux machines. À 20 créations par seconde, l’une comme l’autre est abordable ; le choix dépend de la réponse à une question : « votre nouveau lien a disparu », est-ce acceptable de loin en loin ?

Ce que cette étape n’ajoute délibérément pas, c’est le sharding. Répartir les liens sur plusieurs bases de données résout un autre problème — plus de données ou plus d’écritures qu’un seul primaire ne peut en supporter —, et à 300 Go par an et 20 écritures par seconde, ce problème est encore à des années. Quand il arrivera, la clé de partitionnement est déjà évidente : chaque recherche se fait par code, donc partitionner selon un hash du code fait que chaque redirection ne touche qu’une seule partition. Partitionner plutôt par plages du numéro de séquence brut enverrait chaque nouveau lien vers la même partition, la plus récente ; c’est le hachage de la clé qui répartit les écritures.

L’architecture finale, lue à travers ses pannes

Quatre étapes et neuf boîtes, chacune présente pour une raison que les étapes ont fournie. La façon la plus utile de lire le schéma final, c’est par les pannes — ce qui casse, et qui s’en aperçoit :

• Une instance du service meurt → le répartiteur de charge cesse de lui envoyer du trafic. Personne ne s’en aperçoit.
• Le répartiteur de charge tombe en panne → tout tombe en panne. Il est dessiné comme une seule boîte parce qu’il s’agit généralement d’un service géré et redondant plutôt que d’une machine que vous exploitez vous-même ; si c’en est une, il en faut une paire.
• Le cache est indisponible → les redirections sont servies depuis la base de données, plus lentement, tant que la base de données tient la charge. Rien ne devient incorrect.
• La file ou le worker est indisponible → les redirections ne sont pas affectées ; les clics sont mis en tampon, retardés ou, lors d’une longue panne, en partie perdus.
• Le stockage d’analytique est lent → le worker prend du retard et les comptages aussi. Les redirections ne s’en soucient pas.
• La base de données primaire tombe en panne → la création de liens s’arrête jusqu’à ce que le réplica de secours soit promu. Les liens populaires continuent de rediriger depuis le cache ; les autres échouent jusqu’à la fin de la promotion.

Cette liste, c’est la vraie conception. Les boîtes sont les moyens ; les décisions portent sur le chemin que chaque panne a le droit d’atteindre. La redirection dépend du moins de choses possible — le répartiteur de charge, le service, le cache, et la base de données seulement pour les miss — et tout le reste s’y rattache de façon asynchrone.

Ce que cette conception laisse ouvert

Certaines décisions relèvent du produit plutôt que de l’architecture, et une revue de conception devrait les nommer au lieu de faire comme si elles étaient résolues :

• Les abus. Un raccourcisseur masque la destination d’un lien, ce qui le rend attrayant pour le phishing et les logiciels malveillants. Les vrais services vérifient les destinations à la création d’un lien et limitent le débit de ceux qui peuvent en créer.
• Les alias personnalisés. Laisser les gens choisir leur propre code en fait une clé unique fournie par l’utilisateur, avec des mots réservés et du squatting à gérer.
• L’expiration et la suppression. Les liens qui expirent exigent une tâche de nettoyage et un cache qui les oublie à temps.
• Les régions. Des lecteurs répartis sur plusieurs continents voudraient le cache, et peut-être la redirection elle-même, plus près d’eux. Le trafic de cet exercice n’en a pas encore besoin.

Le code court a pris deux paragraphes. Tout le reste — le chemin chaud, la frontière asynchrone, la source de vérité, la panne que chaque boîte a le droit de provoquer — constitue la vraie conception, et c’est la partie qui se transpose à tous les autres systèmes que vous dessinerez.