Comment concevriez-vous TinyURL et Instagram? – Meilleure programmation

Online Coding Courses for Kids

Qu’est-ce que TinyURL?

TinyURL est un service Web de raccourcissement d’URL qui crée des alias plus courts pour les URL longues. Lorsque vous cliquez sur le lien court, les utilisateurs sont redirigés vers l’URL d’origine. Ce service est utile car les liens courts économisent de l’espace et permettent aux utilisateurs de taper plus facilement les URL longues.

Exigences et objectifs du système

Lors de la conception d’une application de type TinyURL, il y a des exigences fonctionnelles et non fonctionnelles à prendre en compte.

Prérogatives non fonctionnelles:

  • Le système doit être hautement disponible. Si le service échoue, tous les liens courts ne seront pas fonctionnels.
  • La redirection d’URL doit se produire en temps réel avec une latence minimale.
  • Les liens raccourcis ne doivent en aucun cas être prévisibles.

Exigences fonctionnelles:

  • Lorsqu’il reçoit une URL, notre service génère un alias plus court de l’URL d’origine. Ce nouveau lien sera considérablement raccourci afin de pouvoir être facilement copié et collé.
  • Le lien court doit rediriger les utilisateurs vers le lien d’origine.
  • Les utilisateurs devraient avoir la possibilité de choisir un lien court personnalisé pour leur URL.
  • Les liens courts expirent après un délai par défaut, mais les utilisateurs peuvent spécifier le délai d’expiration.

Estimation et contraintes de capacité

Notre système sera lourd en lecture. Il y aura un grand nombre de demandes de redirection par rapport aux nouvelles raccourcissements d’URL. Supposons un rapport de 100: 1 entre la lecture et l’écriture.

Estimations du trafic

En supposant que nous aurons 500 millions de nouvelles raccourcissements d’URL par mois avec un rapport de lecture / écriture de 100: 1, nous pouvons nous attendre à 50 milliards de redirections au cours de la même période:

100 * 500M => 50B

Quelles seraient les requêtes par seconde (QPS) pour notre système? Nouvelles raccourcissements d’URL par seconde:

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

Compte tenu du ratio de lecture / écriture de 100: 1, les redirections d’URL par seconde seront:

100 * 200 URL / s = 20K / s

Estimations de stockage

Supposons que nous stockons chaque demande de raccourcissement d’URL (et lien raccourci associé) pendant cinq ans. Puisque nous prévoyons avoir 500 millions de nouvelles URL chaque mois, le nombre total d’objets que nous prévoyons de stocker sera de 30 milliards:

500 millions * 5 ans * 12 mois = 30 milliards

Supposons que chaque objet stocké fera environ 500 octets (juste une estimation approximative – nous y creuserons plus tard). Nous aurons besoin de 15 To d’espace de stockage total:

30 milliards * 500 octets = 15 To

Estimations de la bande passante

Pour les demandes d’écriture, puisque nous attendons 200 nouvelles URL par seconde, le total des données entrantes pour notre service sera de 100 Ko par seconde:

200 * 500 octets = 100 Ko / s

Pour les demandes de lecture, étant donné que nous attendons environ 20 000 URL de redirection par seconde, le total des données sortantes pour notre service serait de 10 Mo par seconde:

20 K * 500 octets = ~ 10 Mo / s

Estimations de la mémoire

Si nous voulons mettre en cache certaines des URL les plus fréquemment consultées, de combien de mémoire aurons-nous besoin pour les stocker? Si nous suivons la règle 80-20, ce qui signifie que 20% des URL génèrent 80% du trafic, nous aimerions mettre ces URL en cache.

Comme nous avons 20 000 requêtes par seconde, nous recevrons 1,7 milliard de requêtes par jour:

20K * 3600 secondes * 24 heures = ~ 1,7 milliard

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

0,2 * 1,7 milliard * 500 octets = ~ 170 Go

Une chose à noter ici est que comme il y aura beaucoup de demandes en double (de la même URL), notre utilisation réelle de la mémoire sera inférieure à 170 Go.

API système

Nous pouvons utiliser des API REST pour exposer les fonctionnalités de notre service. Voici un exemple des définitions des API pour créer et supprimer des URL sans service:

createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)

Paramètres:

  • api_dev_key (chaîne): la clé de développeur API d’un compte enregistré. Cela sera utilisé pour limiter les utilisateurs en fonction de leur quota alloué.
  • original_url (chaîne): URL d’origine à raccourcir.
  • custom_alias (chaîne): clé personnalisée facultative pour l’URL.
  • user_name (chaîne): nom d’utilisateur facultatif à utiliser dans l’encodage.
  • expire_date (chaîne): date d’expiration facultative pour l’URL raccourcie.

Renvoie (chaîne): une insertion réussie renvoie l’URL raccourcie. Sinon, il renvoie un code d’erreur.

deleteURL(api_dev_key, url_key)

le url_key est une chaîne qui délimite l’URL raccourcie qui doit être supprimée. Une suppression réussie reviendra URL Removed.

Conception de base de données

Regardons quelques observations sur les données que nous stockons:

  • Le service doit stocker des milliards d’enregistrements.
  • Le service est lourd en lecture.
  • Chaque objet est petit (moins de 1K).
  • Il n’y a pas de relations entre chaque enregistrement, sauf pour le stockage, que l’utilisateur a créé avec les liens courts.

Pour le schéma, nous avons besoin d’une table pour stocker des informations sur les mappages d’URL et d’une autre base de données pour les données de l’utilisateur qui a créé les liens courts.

Le meilleur type de base de données à utiliser serait un magasin de bases de données NoSQL comme DynamoDB ou Cassandra car nous stockons des milliards de lignes sans relations entre les objets.

Conception et algorithme de base du système

La plus grande question pour notre service est de savoir comment générer une clé courte et unique lorsqu’elle reçoit une URL. L’approche que nous examinerons aujourd’hui consiste à coder l’URL réelle.

Nous pouvons calculer un hachage unique (par exemple MD5, SHA256, etc.) de l’URL donnée. Le hachage peut ensuite être encodé pour l’affichage. Cet encodage pourrait être en base36 ([a-z ,0–9]) ou base62 ([A-Z, a-z, 0–9]). Si nous ajoutons + et /, nous pouvons utiliser l’encodage Base64. Une question raisonnable serait: «Quelle devrait être la longueur de la touche courte? 6, 8 ou 10 caractères? “

  • En utilisant le codage base64, une clé à six lettres entraînerait 64⁶ = ~ 68,7 milliards de chaînes possibles.
  • En utilisant l’encodage base64, une clé de huit lettres entraînerait 64⁸ = ~ 281 billions de chaînes possibles
  • Avec 68,7 milliards de chaînes uniques, supposons que des clés à six lettres suffiraient pour notre système.

Si nous utilisons l’algorithme MD5 comme fonction de hachage, il produira une valeur de hachage de 128 bits. Après le codage base64, nous obtiendrons une chaîne de plus de 21 caractères (puisque chaque caractère base64 code six bits de la valeur de hachage). Maintenant, nous n’avons plus d’espace que pour huit caractères par touche courte. Comment allons-nous alors choisir notre clé?

Nous pouvons prendre les six (ou huit) premières lettres pour la clé. Cela pourrait entraîner une duplication clé. Pour résoudre ce problème, nous pouvons choisir d’autres caractères dans la chaîne de codage ou échanger certains caractères.

Obstacles potentiels lors de l’adoption de cette approche:

  • Si plusieurs utilisateurs entrent la même URL, ils obtiendront le même lien court.
  • Certaines parties de l’URL peuvent être encodées en URL.

Solutions de contournement:

  • Pour résoudre certains de ces problèmes, nous pouvons ajouter un numéro d’une séquence à chaque URL de lien court. Cela le rend unique même si plusieurs utilisateurs fournissent la même URL.
  • Une autre solution potentielle consiste à ajouter l’ID utilisateur à l’URL d’entrée. Cela ne fonctionnerait pas si l’utilisateur n’était pas connecté et nous devions générer une clé d’unicité.

Partitionnement et réplication des données

Inévitablement, nous devrons faire évoluer notre base de données, ce qui signifie que nous devons la partitionner afin de pouvoir stocker des informations sur des milliards d’URL.

Partitionnement basé sur une plage: nous pouvons stocker les URL dans des partitions distinctes en fonction de la première lettre de leur clé de hachage. Donc, nous enregistrons toutes les URL avec la première lettre de leur clé de hachage étant A dans une partition et ainsi de suite.

Cette approche est problématique car elle conduit à des serveurs de bases de données déséquilibrés, créant une charge inégale.

Partitionnement basé sur le hachage: avec le partitionnement basé sur le hachage, nous pouvons prendre un hachage de l’objet stocké, puis calculer la partition à utiliser. La fonction de hachage distribuera au hasard les données dans différentes partitions.

Parfois, cette approche conduit à des partitions surchargées, qui peuvent ensuite être résolues à l’aide d’un hachage cohérent.

Cache

Notre service devrait pouvoir mettre en cache les URL qui sont fréquemment consultées. Nous pouvons le faire grâce à une solution comme Memcached, qui peut stocker des URL complètes avec des hachages respectifs.

Quelle quantité de mémoire cache devrions-nous avoir? Dans un premier temps, nous pouvons commencer avec environ 20% du trafic quotidien et ajuster en fonction des modèles d’utilisation. Sur la base de nos estimations précédentes, nous aurons besoin de 170 Go de mémoire pour mettre en cache 20% du trafic quotidien.

Quelle politique d’éviction du cache devrions-nous utiliser? Parce que nous voulons remplacer un lien par une URL plus populaire, nous pouvons utiliser la stratégie LRU (Least Latest Used) pour notre système.

Équilibreur de charge (LB)

Il existe trois endroits où nous pouvons ajouter une couche d’équilibrage de charge à notre système:

  • Entre les clients et les serveurs d’applications
  • Entre les serveurs d’applications et les serveurs de bases de données
  • Entre les serveurs d’applications et les serveurs de cache

Au début, nous pourrions simplement utiliser une approche Round Robin qui répartit les demandes entrantes également entre les serveurs. Ceci est facile à mettre en œuvre et ne crée pas de surcharge.

Si le serveur devient surchargé avec cette approche, l’équilibreur de charge n’arrêtera pas d’envoyer de nouvelles demandes à ce serveur. Pour gérer ce problème, une solution d’équilibrage de charge plus intelligente peut être développée qui ajuste périodiquement le trafic en fonction de sa charge.

Photo de l’auteur.

Close Menu