Concevoir un raccourcisseur d'URL

La rue qu'on renumérote

Le plan d'adressage parisien actuel date de 1805 : numéros pairs d'un côté, impairs de l'autre, comptage qui démarre depuis la Seine. Avant lui, plusieurs systèmes concurrents ont coexisté, et chaque réforme a rendu caduques les adresses écrites sous la précédente.

Un numéro de rue est une clé courte qui désigne un endroit long à décrire. Il ne vaut que par une promesse : dans dix ans, le 14 de la rue désignera toujours la même porte. Le jour où la promesse tombe, ce ne sont pas les numéros qui se cassent, ce sont tous les documents qui les citaient.

Un raccourcisseur d'URL fait exactement ce travail. Il attribue une clé de quelques caractères à une destination de deux cents, et il s'engage à tenir la correspondance bien plus longtemps que ce que dure la mode qui l'a fait naître.

C'est le système que tout le monde croit trivial : une table à deux colonnes et une redirection. La difficulté n'est pas dans la table, elle est dans la longueur de la clé, dans la façon de la produire sans coordination, et dans la durée pendant laquelle il faudra l'honorer.

Ce billet déroule la méthode complète, dans l'ordre où on la pose au tableau. Les exigences, l'estimation chiffrée, le calcul de la longueur de clé en base 62, les trois façons de générer un identifiant, le schéma de données, l'architecture, le chemin de lecture avec son choix entre 301 et 302, puis le tableau des arbitrages. Aucune étape ne se saute : chacune donne un chiffre dont la suivante a besoin.

Les exigences

Un service d'urbanisme ne pose pas de plaques avant d'avoir écrit sa règle : quel format, qui l'attribue, combien de temps il engage la commune. Le premier geste de l'étude de cas est identique, et il tient en une page.

Côté fonctionnel, trois choses. Raccourcir une URL longue en une clé courte. Rediriger cette clé vers l'original. Permettre une durée de vie, parce qu'un lien de campagne n'a pas vocation à survivre dix ans.

Côté non fonctionnel, la redirection est sur le chemin critique de contenus publiés dans des courriels, des articles et des affiches que personne ne peut plus corriger. Elle doit être rapide et disponible, très au-delà de ce qu'exige la création.

Reste une exigence qu'on oublie systématiquement : la clé ne doit pas être devinable. Martin Georgiev et Vitaly Shmatikov l'ont montré publiquement en 2016 dans « Gone in Six Characters: Short URLs Considered Harmful for Cloud Services ». En balayant l'espace des jetons de six caractères de services de raccourcissement, ils ont retrouvé des liens de partage OneDrive et des itinéraires Google Maps que leurs auteurs croyaient privés.

Une clé courte et séquentielle est une invitation au balayage. L'imprévisibilité n'est pas un raffinement de sécurité ajouté après coup, c'est une exigence qui contraint le générateur d'identifiants dès la première ligne du schéma.

L'estimation

Avant la première canalisation, on chiffre le débit. Le raccourcisseur a la particularité d'être un système très déséquilibré : on écrit peu, on lit énormément, et on conserve longtemps. Les trois chiffres qui comptent sont le débit d'écriture, le débit de lecture et le volume cumulé.

Les hypothèses, posées noir sur blanc parce que tout le reste en découle : cent millions de liens créés par jour, un ratio de dix lectures pour une écriture, une conservation de dix ans, cinq cents octets par enregistrement.

100 000 000  liens créés par jour
/ 100 000    (86 400 s, arrondi)         =        1 000  écritures par seconde
x 10         ratio lecture / écriture    =       10 000  lectures par seconde
x 2          facteur de pointe           =       20 000  lectures par seconde en pic

L'arrondi de 86 400 à 100 000 sous-estime le résultat d'environ 13 %. Sans importance à ce stade, et le facteur de pointe le rattrape largement. Ce qu'on cherche à savoir, c'est qu'on joue en dizaines de milliers de requêtes par seconde et pas en millions.

100 000 000  liens par jour
x 365        jours                       =   36 500 000 000  liens par an
x 10         années de conservation      =  365 000 000 000  liens au total

365 000 000 000  enregistrements
x 500            octets par enregistrement
=  182 500 000 000 000 octets            =  182,5 To

Cent quatre-vingts téraoctets ne tiennent pas sur une machine : le partitionnement est acquis avant même d'avoir choisi le magasin. La clé de partition sera la clé courte, puisque c'est le seul critère de lecture. Le sharding et le hachage cohérent traitent la mécanique.

Reste la mémoire. La règle des 80/20 veut qu'une petite part des liens concentre l'essentiel des clics : on dimensionne le cache pour absorber un cinquième des lectures d'une journée.

10 000       lectures par seconde
x 86 400     secondes                       =  864 000 000  lectures par jour
x 20 %       des lectures du jour (80/20)   =  172 800 000  entrées à garder
x 500        octets par entrée              =   86 400 000 000 octets  =  86,4 Go

Quatre-vingt-six gigaoctets se logent dans la mémoire de quelques machines. Le cache se dimensionne donc dès maintenant, au même titre que la base.

Le raccourcisseur est un système en lecture seule, à 99 %, sur un jeu de données qui ne change jamais après sa création. Cette phrase, à elle seule, décide du cache, de l'index et du choix de magasin.

Le détail de la méthode et les ordres de grandeur à connaître de tête sont dans l'estimation à la louche.

La longueur de la clé

Combien de chiffres faut-il à un plan d'adressage pour numéroter une métropole entière ? La réponse ne se devine pas, elle se calcule, et elle ne se reprend pas ensuite sans invalider tout ce qui est déjà gravé.

L'alphabet retenu est la base 62 : dix chiffres, vingt-six minuscules, vingt-six majuscules. Tous ces caractères passent sans encodage dans un chemin d'URL, ce qui n'est pas le cas des symboles de la base 64.

L'estimation demande 365 milliards de clés. Six caractères en offrent 56,8 milliards, soit six fois moins que le besoin : insuffisant. Sept caractères en offrent 3 521 milliards, et dix ans d'exploitation en consomment 365, soit 10,4 % de l'espace.

Sept caractères, donc. Une marge d'un facteur dix sur l'hypothèse de départ, ce qui est exactement ce qu'on veut d'un choix irréversible.

L'autre voie consiste à hacher l'URL longue. Elle échoue sur la longueur : MD5 produit 128 bits, soit 32 caractères hexadécimaux, et SHA-1 en produit 160, soit 40 caractères. Même réencodés en base 62, les 128 bits de MD5 occupent encore 22 caractères. Un raccourcisseur qui rallonge n'a plus d'objet.

Tronquer le hachage à sept caractères ramène alors le problème des collisions, et pas dans un futur lointain. L'ordre de grandeur où deux clés se percutent est la racine carrée de l'espace, par le paradoxe des anniversaires : la racine de 3 521 614 606 208 vaut environ 1,88 million. Autrement dit, les collisions cessent d'être théoriques autour de deux millions de liens, ce qu'un service atteint en quelques jours.

Un hachage tronqué garantit qu'on aura des collisions, et pas qu'on n'en aura pas. Il faut alors une lecture avant chaque écriture pour vérifier, et une stratégie de reprise en cas de choc : exactement la coordination qu'on cherchait à éviter.

Générer l'identifiant

Qui attribue le numéro de rue ? Un guichet unique en mairie, une règle mécanique liée à la position dans l'avenue, ou une plage confiée à chaque arrondissement. Les trois existent, et chacune se paie.

Le serveur de tickets

Un compteur central délivre un entier croissant, qu'on encode ensuite en base 62. Flickr a publié ce motif en 2010 sous le nom de serveur de tickets : une table dédiée dans une base relationnelle, un auto-incrément, rien de plus.

C'est simple, exact et facile à raisonner. C'est aussi un point de passage unique sur le chemin d'écriture, et un point de défaillance qu'il faut doubler, généralement avec deux serveurs configurés l'un sur les nombres pairs, l'autre sur les impairs.

L'horodatage type Snowflake

Twitter a publié en 2010 le générateur Snowflake, qui construit un entier sur 64 bits sans aucune coordination à l'exécution : un bit de signe inutilisé, 41 bits d'horodatage en millisecondes depuis une époque arbitraire, 10 bits d'identifiant de machine, 12 bits de séquence.

Les chiffres se lisent directement dans la structure. Les 41 bits d'horodatage couvrent 2^41 millisecondes, soit environ 69 ans. Les 10 bits de machine autorisent 1 024 instances distinctes. Les 12 bits de séquence permettent 4 096 identifiants par milliseconde et par machine, soit plus de quatre millions par seconde.

Deux réserves. L'unicité repose entièrement sur le fait que deux machines n'ont jamais le même numéro : si l'attribution dérape, la collision est silencieuse. Et un entier de 64 bits réencodé en base 62 réclame 11 caractères, contre les 7 qu'on vient de calculer.

Les plages réservées

Chaque instance demande une plage à un service de coordination, par exemple un million de valeurs, puis la consomme localement sans parler à personne. Quand elle l'épuise, elle en demande une autre. Apache ZooKeeper est l'outil habituel de ce rôle.

La coordination passe d'une fois par identifiant à une fois par million d'identifiants. Le prix est cosmétique : une instance qui redémarre abandonne le reste de sa plage, et la numérotation se retrouve trouée. Personne ne compte les numéros manquants d'un raccourcisseur.

Aucune des trois premières méthodes ne produit une clé imprévisible : elles délivrent toutes des valeurs croissantes. La parade tient en une ligne d'arithmétique. Multiplier le compteur par un entier premier avec 62^7, modulo 62^7, est une bijection : chaque entrée donne une sortie différente, l'espace reste intégralement couvert, et l'ordre disparaît. On garde l'absence de collision du compteur et on perd sa lisibilité.

Le multiplicateur devient alors un secret d'exploitation. Sa fuite ne casse rien immédiatement, mais elle rend l'énumération de tout le catalogue possible en quelques heures.

Le schéma de données

Le cadastre range une fiche par parcelle et se consulte par un seul critère : la référence. Le registre du raccourcisseur est de la même nature : une seule question, posée des dizaines de milliers de fois par seconde.

CREATE TABLE short_url (
  id          BIGINT        NOT NULL,
  short_key   CHAR(7)       NOT NULL,
  long_url    VARCHAR(2048) NOT NULL,
  owner_id    BIGINT,
  created_at  TIMESTAMP     NOT NULL,
  expires_at  TIMESTAMP,
  PRIMARY KEY (id),
  UNIQUE KEY uk_short_key (short_key)
);

Une seule requête compte sur le chemin critique, et elle filtre sur short_key. L'index unique sur cette colonne porte à lui seul tout le système.

Le détail a des conséquences mesurables. Dans un moteur à index groupant comme InnoDB, l'index secondaire renvoie vers la clé primaire, ce qui impose une seconde traversée pour atteindre la ligne. Faire de short_key la clé primaire supprime cette traversée, au prix d'insertions en ordre aléatoire qui fragmentent les pages. L'arbitrage complet est dans l'indexation.

Aucune jointure, aucune requête transversale, un accès par clé exacte, un volume qui impose le partitionnement : le profil décrit mot pour mot un magasin clé-valeur. Une base relationnelle partitionnée sur short_key fait le travail aussi, tant qu'on accepte de ne jamais rien lui demander d'autre.

Le partitionnement sur la clé courte rend l'analytique impossible en direct. Compter les clics par propriétaire de lien exigera un pipeline séparé, alimenté en asynchrone. C'est une décision d'architecture, pas un manque à corriger plus tard.

L'architecture

La ville met un agent au carrefour, une épicerie au coin de la rue et le cadastre à la mairie. Le raccourcisseur reprend les mêmes pièces, dans le même ordre.

Deux détails méritent qu'on s'y arrête. Le service de création et le service de redirection sont séparés parce que leurs charges n'ont aucun rapport : mille écritures par seconde d'un côté, vingt mille lectures en pointe de l'autre. Les dimensionner ensemble reviendrait à payer le maximum des deux sur toute la flotte.

Et le cache est un vrai magasin, pas un accessoire. Sur un jeu de données immuable après création, l'invalidation se réduit à une expiration et à la suppression explicite d'un lien retiré. C'est le cas le plus favorable qu'on rencontre jamais.

Le chemin de lecture

Un clic sur un lien court déclenche une redirection HTTP. Le code retourné n'est pas un détail de protocole : il décide de qui verra les clics suivants.

Une réponse 301 annonce un déplacement permanent. Le navigateur a le droit de la mettre en cache par défaut, et il le fait : le deuxième clic du même utilisateur ne touche plus jamais le service. Une réponse 302 annonce un déplacement temporaire, qui n'est mis en cache que si la réponse le demande explicitement. Chaque clic revient donc au service.

Le choix se déduit du modèle du produit. Un raccourcisseur qui vend la mesure d'audience prend 302 et assume la charge. Un raccourcisseur qui vise le coût minimal prend 301 et renonce à compter au-delà du premier clic.

Deux autres codes reviennent souvent dans la discussion. Les 307 et 308 préservent la méthode HTTP d'origine, ce qui n'apporte rien ici puisqu'un clic sur un lien est toujours un GET. Les propriétés exactes de chacun de ces codes sont posées dans la RFC 9110.

Choisir 301 revient à confier son plan d'adressage aux navigateurs des visiteurs. On y gagne beaucoup de charge, et on y perd la capacité de corriger une destination pour ceux qui ont déjà cliqué.

Ce qu'on a arbitré

Le conseil municipal tranche, écrit sa décision et vit avec. Le tableau ci-dessous est la sortie utile de l'exercice, celle qu'on relit dans deux ans quand quelqu'un demande pourquoi le système est fait comme ça.

Chaque ligne de cette liste coûte quelque chose, et c'est bien le sujet. Un schéma sans colonne « prix payé » n'est pas une conception, c'est une liste de souhaits.

La question posée en entretien n'est jamais « quel est le bon schéma ». Elle est « qu'est-ce que tu perds avec celui-là », et la seule mauvaise réponse est « rien ».

Scénario B : la fin de goo.gl

Google a lancé son raccourcisseur goo.gl en 2009. En mars 2018, un billet du Google Developers Blog intitulé « Transitioning Google URL Shortener to Firebase Dynamic Links » a annoncé son retrait progressif : plus de nouveaux comptes, puis plus de création de liens du tout, avec la promesse explicite que les liens existants continueraient de rediriger. Les utilisateurs étaient invités à migrer vers Firebase Dynamic Links.

En 2024, Google a annoncé l'étape suivante : les liens goo.gl cesseraient de fonctionner, avec une page d'avertissement affichée avant la date butoir du 25 août 2025. Firebase Dynamic Links, le remplaçant recommandé six ans plus tôt, avait de son côté été programmé pour fermer à cette même date.

L'histoire s'est terminée sur une nuance, annoncée publiquement en 2025 : après examen de l'usage réel, Google a indiqué que les liens encore actifs continueraient de fonctionner, l'arrêt ne visant que ceux qui ne servaient plus. Le sursis ne change rien à la leçon.

Un lien court est une dépendance externe déposée dans du contenu qu'on ne contrôle plus. Une fois imprimé sur une affiche, cité dans un article ou collé dans un courriel envoyé il y a huit ans, il ne sera jamais corrigé. Sa disparition ne casse pas le service qui l'a émis : elle casse tout ce qui l'a recopié.

Un raccourcisseur d'URL n'est pas une fonctionnalité, c'est un engagement de durabilité pris au nom de gens qui n'ont pas été consultés. Avant de compter les requêtes par seconde, il faut savoir qui honorera la promesse dans quinze ans.

Points clés

• La longueur de la clé se calcule, elle ne se choisit pas : 365 milliards de liens sur dix ans imposent 7 caractères en base 62, parce que 6 n'en couvrent que 56,8 milliards.
• Un hachage brut rallonge au lieu de raccourcir, et sa troncature ramène les collisions dès environ 1,88 million de liens, la racine carrée de l'espace disponible.
• Générer l'identifiant sans coordination permanente se fait par plages réservées ; rendre la clé imprévisible se fait par une bijection modulaire, pas par du hasard vérifié à chaque écriture.
• Le choix entre 301 et 302 est un choix de produit déguisé en détail de protocole : il arbitre entre la charge du service et la mesure des clics.
• Le vrai coût du système n'est ni le stockage ni la latence, c'est la promesse de durabilité que chaque lien émis fait porter à l'exploitant.

Dans la série

Palier 3 : Tenir les registres. Domaine : Études de cas.

• Précédent : Transactions distribuées : 2PC, 3PC, SAGA et verrous
• Suivant : Concevoir un magasin clé-valeur
• Vue d'ensemble : System design : par où commencer

Pour aller plus loin

• L'estimation à la louche : chiffrer avant de construire, pour la méthode de calcul reprise en entier dans ce billet.
• L'indexation : ce qui se passe vraiment sous une requête, pour l'arbitrage entre index groupant et index secondaire sur la clé courte.
• Sharding et hachage cohérent : découper sans tout déménager, pour le découpage des 182 To sur plusieurs machines.
• Base62 pour l'encodage, et la RFC 9110 pour la sémantique exacte des codes de redirection.
• La documentation Apache ZooKeeper pour le service de coordination qui distribue les plages d'identifiants.