Comment créer un service Tiny URL pouvant atteindre des milliards?

Comment construire un service URL Shortner?

L'une des contraintes de conception de Twitter est que chaque message est limité à 140 caractères, mais si vous souhaitez publier des URL dans vos messages Twitter comme je le fais, ces 140 caractères deviennent très chers. C’est probablement pour cette raison que Twitter convertit automatiquement les URL de plus de 30 caractères en URL courtes à l’aide du service TinyUrl ou de tout autre service. Plus tard, de nombreux services de raccourcissement d'URL sont apparus sur le marché, notamment Bitly, Google Url Shortner, Rebrandly, etc. De nombreuses entreprises ont également commencé à les utiliser dans leurs campagnes de marketing, leurs campagnes publicitaires, etc. sur divers canaux.

Création d'un identifiant unique et répétable pour une URL
Je pense que le premier réflexe de beaucoup de gens serait peut-être d’opter pour le hachage de la chaîne d’URL - ce n’est pas une bonne idée pour plusieurs raisons:

  • Longueur: la plupart des algorithmes de hachage normaux (par exemple, md5) produisent des chaînes longues, ce qui va à l’encontre du point du raccourcisseur d’URL.
  • Unique-ness: si cet identifiant est un identifiant d’URL, il doit être unique et les hachages, de par leur nature, ne le sont pas - ce qui signifie que vous devez gérer le scénario dans lequel une URL crée un hachage déjà utilisé et a une alternative.
  • Look-up: la plupart des hachages ne sont pas (facilement) réversibles, vous devrez rechercher l'URL en utilisant le hachage comme clé de base de données - ce qui peut ne pas être idéal compte tenu d'un très grand nombre d'URL (imaginez des milliards)

Aujourd'hui, nous discuterons de la façon de créer et de développer un petit service URL. Tout d’abord, divisons en 3 parties: algorithme, conception et mise à l’échelle et ses subtilités.

Algorithme:

Nous avons 62 caractères alphanumériques, c'est-à-dire [az 0–9 AZ], bien que les tirets (-) et les traits de soulignement (_) soient autorisés dans une url. Nous souhaitons néanmoins les éviter, car ce serait une mauvaise URL ressemblant à http: // abc. .com / c0 - rw_ ou http://abc.com/______-.
Voici l’implémentation simple du convertisseur base10 à base62, c’est tout ce dont nous avons besoin pour raccourcir une URL.

Avec 62 caractères et une chaîne unique de 7,8,9,10,11 caractères, nous pouvons raccourcir:

62⁷ = 3,521,614,606,208 urls
62⁸ = 218 340,105,584,896 urls
62⁹ = 13 537 086 546 263 552 urls
62¹⁰ = 839,299,365,868,340,224 urls
62¹¹ = 52 036 560 683 837 093 888 urls

Comme vous pouvez le voir ci-dessus, nous pouvons générer ces 62⁶ = ~ 5 milliards de chaînes possibles & 62⁸ = ~ 218 trillions de chaînes possibles et bien plus encore en fonction des besoins.

Disons donc que nous décidons de générer une URL raccourcie pour le lien ci-dessous.

https://medium.com/@vaibhav0109/cache-refreshing-techniques-446403de1ba2

Nous allons donc générer un identifiant unique en utilisant la base 62, l'ajouter à notre domaine hébergé. Disons que l'identifiant généré est qa12WS4 et que notre domaine hébergé hypothétique est http://short.io.

Maintenant, nous devons juste nous assurer que ce lien est unique et non attribué à nouveau, nous discuterons des stratégies pour stocker dans une partie ultérieure de ce blog.

Vous trouverez ci-dessous les deux fonctions pouvant être utilisées pour générer des chaînes uniques:

char final final privé [] corpus = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" .toCharArray ();
/ *
* Notez que si la valeur de départ est unique, le numéro de base62 généré sera unique. Assurez-vous également que la valeur de la charge n'est pas la même.
* /
public statique final String getBase62From10 (graine finale finale)
{
  Numéro de chaîne = graine + "";
  char [] buf = new char [nombre.longueur ()];
  int charPos = number.length () - 1;
  BigInteger bigIntegerNumber = new BigInteger (nombre);
  BigInteger radix = BigInteger.valueOf (62);
 
  while (bigIntegerNumber.compareTo (radix)> = 0)
  {
   buf [charPos--] = corpus [bigIntegerNumber.mod (radix) .intValue ()];
   bigIntegerNumber = bigIntegerNumber.divide (radix);
  }
  buf [charPos] = corpus [bigIntegerNumber.intValue ()];
  retourne une nouvelle chaîne (buf, charPos, (number.length () - charPos));
}
/ **
* @param longNumber
* un nombre positif en base 62
* @retourner le même nombre, en base 10
* /
public statique final String getBase10From62 (final long longNumber)
{
  Numéro de chaîne = longNumber + "";
  BigInteger valeur = BigInteger.ZERO;
  pour (char c: number.toCharArray ())
  {
    valeur = valeur.multiply (BigInteger.valueOf (62));
    if ('0' <= c && c <= '9')
    {
      valeur = valeur.add (BigInteger.valueOf (c - '0'));
    }
    if ('a' <= c && c <= 'z')
    {
      valeur = valeur.add (BigInteger.valueOf (c - 'a' + 10));
    }
    if ('A' <= c && c <= 'Z')
    {
      valeur = valeur.add (BigInteger.valueOf (c - 'A' + 36));
    }
   }
   valeur de retour.toChaîne ();
}

Conception:

Passons maintenant à la partie conception de l'application. Il peut y avoir plusieurs approches en fonction de la charge du système ou si l'application est derrière l'équilibreur de charge, etc. Tout d'abord, la plus simple et, en second lieu, une amélioration par rapport à la première.

Dans le cas le plus simple, nous pourrions probablement nous en tirer avec les colonnes suivantes:

  • id (ID de séquence généré par la base de données)
  • original_url - valeur de l'URL d'origine
  • shorten_url
  • date de création
  • date d'expiration

Générer l'identifiant à partir d'une base de données

  1. Désormais, si vous fournissez une valeur String URL, votre code doit simplement l'insérer dans le tableau avec la date de création. La ligne et l'ID unique seront créés.
  2. Ensuite, récupérez cet ID numérique unique et convertissez-le en base-62 (cela convertira la valeur numérique en représentation en base 62 (plutôt que base10, il autorisera 0–9, az, AZ en tant que caractères. Cela vous donnera un identifiant sous la forme qa12WS4.
  3. Ajoutez maintenant la chaîne base62 à l’URL de base de votre domaine court http://short.io et voila, vous obtenez une URL raccourcie sous la forme http://short.io/qa12WS4 et mettez-la à jour dans la colonne URL courte avec la date d’expiration.
  4. Maintenant, vous devez simplement écrire la logique de redirection, car quels que soient les contacts avec cette URL raccourcie, vous extrayez les détails de Db et redirigez-le vers l’URL originale.

Cette approche présente 2 inconvénients:

  • Premièrement, nous effectuons deux opérations dans la base de données, insertion et mise à jour.
  • Deuxièmement, lors de la migration de la base de données, les identifiants de séquence ne peuvent pas être fusionnés car nous pourrions avoir le même identifiant de séquence généré dans deux tables.

Parlons maintenant des améliorations, nous pouvons améliorer deux choses. Premièrement, la structure de la base de données et, deuxièmement, au lieu des insertions et des mises à jour, nous ne pouvons effectuer que des insertions uniques. Structure de la base de données comme suit:

  • id_hash (chaîne générée en base 62 en tant que clé primaire)
  • original_url
  • shorten_url
  • date de création
  • date d'expiration

Maintenant, pour avoir id_hash en tant que clé primaire, nous avons besoin d’un service centralisé qui me donne des jetons uniques. Par exemple, nous utilisons la fonctionnalité d’auto-incrémentation de Redis (de nature atomique). travaillera également derrière deux instances en équilibre de charge. Un certain nombre d'approches peuvent être construites pour obtenir des semences uniques en fonction des besoins.

Échelle et complexités de ce système:

Estimations de trafic: pour 500 millions de nouvelles adresses URL réduites par mois, nous pouvons nous attendre à des redirections (100 * 500 millions => 50 milliards) au cours de la même période. Que seraient les requêtes par seconde (QPS) pour notre système?

Nouveaux raccourcissements d'URL par seconde:

a) 500 millions / (30 jours * 24 heures * 3600 secondes) = ~ 192 URL / s

b) 1000 millions / (30 jours * 24 heures * 3600 secondes) = ~ 386 URL / s

URL de redirection par seconde, en considérant un rapport lecture / écriture de 100: 1:

a) 100 * 500M = 50 milliards de redirections

50 milliards / (30 jours * 24 * 3600) = ~ 19K / s

b) 100 * 1000 millions = 100 milliards de redirections

100 milliards / (30 jours * 24 heures * 3600 sec) = ~ 38K / s

Estimation de stockage: Supposons que nous stockons chaque demande de réduction d’URL (et le lien raccourci associé) pendant 2 ans. Comme nous prévoyons avoir 1 milliard de nouvelles URL par mois, le nombre total d'objets que nous prévoyons de stocker sera de 30 milliards:

1000 millions * 2 ans * 12 mois = 24 milliards

Supposons que chaque objet stocké aura environ 500 octets (juste une estimation approximative - nous y reviendrons plus tard). Nous aurons besoin de 15 To de stockage total:

24 milliards * 500 octets = 12 To

Estimation de la bande passante: pour les demandes d'écriture, comme nous prévoyons 386 nouvelles URL par seconde, le total des données entrantes pour notre service sera de 100 Ko par seconde:

386 * 500 octets = ~ 200 Ko / s

Pour les demandes de lecture, étant donné que nous prévoyons des redirections d'environ 19 000 URL par seconde, le total des données sortantes de notre service serait de 9 Mo par seconde.

38 Ko * 500 octets = ~ 18 Mo / s

Estimation de la mémoire: si nous voulons mettre en cache certaines des URL les plus fréquemment consultées, de combien de mémoire disposerons-nous pour les stocker? Si nous suivons la règle 80–20, c'est-à-dire que 20% des URL génèrent 80% du trafic, nous aimerions mettre en cache ces 20% URL chaudes.

Avec 38 000 requêtes par seconde, nous recevrons 3,4 milliards de requêtes par jour:

38 K * 3600 secondes * 24 heures = ~ 3,4 milliards

Pour mettre en cache 20% de ces demandes, nous aurons besoin de 340 Go de mémoire.

0,2 * 3,4 milliards * 500 octets = ~ 340 Go

Maintenant que nous avons une brève idée d’échelle, nous pouvons concevoir des contraintes pour construire le système, ce qui signifie que nous pouvons limiter les utilisateurs à un certain nombre de créations d’URL et de redirections par période.

Et nous devons également gérer la charge sur la base de données (SQL ou NoSQL). Passons maintenant aux complexités relatives à l'échelle. Pour l'échelle DB, nous aurons besoin de:

une. Partitionnement basé sur les plages: nous pouvons stocker les URL dans des partitions distinctes en fonction de la première lettre de l'URL ou de la clé de hachage ou en fonction de la date de création ou de la date d'expiration. Cette approche s'appelle le partitionnement basé sur la plage.

Le principal problème de cette approche est qu’elle peut conduire à des partitions déséquilibrées.

b. Partitionnement basé sur le hachage: Dans ce schéma, nous prenons un hachage de l'objet que nous stockons. Nous calculons ensuite la partition à utiliser en fonction du hachage.

Notre fonction de hachage distribue de manière aléatoire des URL dans différentes partitions (notre fonction de hachage peut par exemple toujours mapper toute clé sur un nombre compris entre [1… 256]) et ce nombre représente la partition dans laquelle nous stockons notre objet.

Purge des données de la base de données:

Les entrées doivent-elles rester pour toujours ou doivent-elles être purgées? Si un délai d'expiration spécifié par l'utilisateur est atteint, qu'adviendra-t-il du lien?

Si nous choisissions de rechercher activement les liens arrivés à expiration pour les supprimer, la base de données serait soumise à de fortes pressions. Au lieu de cela, nous pouvons supprimer lentement les liens expirés et effectuer un nettoyage paresseux. Notre service veillera à ce que seuls les liens expirés soient supprimés, même si certains liens expirés peuvent vivre plus longtemps mais ne seront jamais renvoyés aux utilisateurs.

  • Chaque fois qu'un utilisateur tente d'accéder à un lien arrivé à expiration, nous pouvons le supprimer et lui renvoyer une erreur.
  • Un service de nettoyage séparé peut être exécuté périodiquement pour supprimer les liens périmés de notre mémoire de stockage et de notre cache. Ce service doit être très léger et son exécution ne peut être planifiée que lorsque le trafic utilisateur devrait être faible.
  • Nous pouvons avoir un délai d'expiration par défaut pour chaque lien (par exemple, deux ans).
  • Devrions-nous supprimer les liens qui n’ont pas été visités depuis un certain temps, six mois, par exemple? Cela pourrait être délicat. Le stockage devenant peu coûteux, nous pouvons décider de conserver les liens pour toujours.

La mise en cache est un autre aspect complexe pour les URL à accès fréquent.

Combien de cache devrions-nous avoir?

Nous pouvons commencer avec 20% du trafic quotidien et, en fonction du modèle d'utilisation des clients, nous pouvons ajuster le nombre de serveurs de cache dont nous avons besoin. Comme estimé ci-dessus, nous avons besoin de 340 Go de mémoire pour mettre en cache 20% du trafic quotidien.

Quelle politique d’expulsion de cache conviendrait le mieux à nos besoins?

volatile - ttl, LRU, etc sont de multiples options.

Références :

https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600916475904

Il pourrait y avoir beaucoup plus de problèmes d'échelle. J'ai essayé de couvrir les exigences minimales de base tout en construisant un service d'URL de raccourcissement évolutif.

Des questions ? Suggestions ? Commentaires ?

Et après? Suivez-moi sur Medium pour être le premier à lire mes histoires.