Les avantages d’un système imparfait : la timeline lossy de Bluesky

• Lors de la conception d’un système, il est en pratique difficile de satisfaire simultanément une cohérence parfaite, une haute disponibilité, une faible latence et un débit élevé
  • Il est important de trouver une conception adaptée en recherchant le bon point d’équilibre pour l’application
• Dans la conception du fil suivi / de la timeline de Bluesky, un compromis a été appliqué consistant à sacrifier partiellement la cohérence afin d’améliorer les performances d’écriture
  • Résultat : une réduction de plus de 96 % de la latence P99, sans impact négatif pour les utilisateurs

Fanout de la timeline

• Lorsqu’un utilisateur publie un message sur Bluesky, celui-ci est indexé par le système, stocké dans la base de données, puis servi dans les réponses de l’API
• En parallèle, il passe par un processus de « fanout » qui insère ce message dans la table de timeline de chacun de ses abonnés
• Cela consiste à consulter la liste des abonnés, puis à effectuer des insertions en ordre inverse dans la table de timeline de chaque abonné
• Les tables de timeline sont partitionnées par utilisateur et stockées dans une base de données distribuée (ScyllaDB), puis répliquées sur plusieurs shards pour assurer une haute disponibilité
  • Chaque utilisateur peut être affecté à un shard différent
• Pour économiser l’espace de stockage, les timelines qui dépassent une certaine longueur suppriment périodiquement les références aux anciens messages

Le problème des hot shards

• Bluesky compte environ 32 millions d’utilisateurs, et la base de données de timelines est répartie sur plusieurs centaines de shards
• Dans un système utilisé par des millions de personnes, il peut exister des utilisateurs avec un nombre extrêmement élevé de relations de suivi
  • Exemple : des utilisateurs qui suivent plusieurs centaines de milliers de comptes
• Un même shard stocke les timelines de nombreux utilisateurs
• Si un utilisateur provoque un très grand nombre d’écritures, le shard concerné entre en surcharge (« hot shard »)
• Ces hot shards concentrent les opérations de lecture ou d’écriture, ce qui propage la latence aux autres utilisateurs hébergés sur le même shard

Accumulation de latence

• Si un utilisateur a 2 000 000 d’abonnés, une écriture séquentielle peut prendre plus de 20 minutes
• Pour réduire ce délai, le fanout peut être parallélisé, ce qui raccourcit la latence moyenne
• Mais la latence P99 (d’environ 15 millisecondes ou plus) peut se produire à répétition et retarder l’ensemble du traitement parallèle
• Lorsqu’un utilisateur a énormément d’abonnés, la latence P99 ou P99.9 peut faire grimper le temps total de fanout, dans le pire des cas, de plusieurs minutes à plusieurs dizaines de minutes

Timelines lossy

• Pour les utilisateurs qui suivent un nombre excessivement élevé de comptes, il est en pratique impossible d’afficher tous les messages exactement dans l’ordre
• Il est d’ailleurs difficile pour une personne de réellement consommer tous ces messages
• Bluesky a donc introduit une approche consistant à « ignorer » probabilistiquement certaines écritures dans la timeline des utilisateurs dont le nombre d’abonnements dépasse un certain seuil (par ex. reasonable_limit)
• La formule utilisée est loss_factor = min(reasonable_limit / num_follows, 1)
• Lors du fanout, une valeur aléatoire est générée, et si elle est supérieure à loss_factor, l’écriture dans la timeline est omise
• Cela permet de limiter les écritures excessives sur la timeline d’un utilisateur donné et d’éviter une dégradation globale des performances du shard

À propos du cache

• Comme les écritures de timeline dépassent le million par seconde, interroger directement la base de données pour connaître le nombre d’abonnements d’un utilisateur à chaque écriture créerait une charge énorme
• À la place, les comptes ayant un nombre élevé d’abonnements sont mis en cache dans Redis sous forme de sorted set
• Les instances du service de fanout chargent ces informations de cache en mémoire toutes les 30 secondes
• Il devient ainsi possible de consulter rapidement les informations sur les utilisateurs à fort volume d’abonnements pendant le processus de fanout
• Comme il n’est pas nécessaire que ces données de cache soient parfaitement à jour, cette approche accepte une certaine imperfection en échange de meilleures performances et d’une meilleure scalabilité

Résultats

• Après l’introduction des timelines lossy, les hot shards ont pratiquement disparu de la base de données Timelines
• La latence P99 pour traiter une page de fanout a diminué de plus de 90 %
• Pour l’ensemble du travail de fanout, les traitements qui prenaient 5 à 10 minutes au P99 ont été ramenés à moins de 10 secondes
• Cela montre qu’il est possible de préserver la scalabilité à grande échelle tout en répondant pleinement aux attentes des utilisateurs du service, même en sacrifiant partiellement la cohérence
• L’architecture de timeline de Bluesky peut encore être améliorée, mais ce changement a déjà considérablement accru le débit d’écriture et la scalabilité

[GN⁺]

Commentaires sur Hacker News

• En tant qu’amateur de systèmes, je fais partie des gens qui aiment ce genre d’articles. Il est facile de tomber dans l’état d’esprit du « il faut que ce soit parfait »

  • J’ai construit un index « eventually consistent » pour le backend du moteur de recherche Blekko. Cela permettait de fournir des mises à jour plus rapidement aux utilisateurs, mais deux personnes lançant la même requête pouvaient obtenir des résultats légèrement différents
  • Il y a beaucoup de théorie des systèmes en jeu, avec une possibilité d’oscillation en présence de rétroaction positive. Dans un moteur de recherche, le classeur qui pondère les liens sur lesquels les utilisateurs cliquent fournit cette rétroaction positive
  • Il était important de garder le système « en amortissement critique ». Cela lui permettait de converger rapidement
  • Le fait que la timeline des utilisateurs soit shardée et qu’il y ait des boucles de rétroaction (par ex. les « J’aime » ou les reposts) semble constituer un espace de problèmes intéressant

• Je me demande pourquoi ne pas implémenter la timeline de manière hybride selon la popularité du compte

  • Pour les comptes de célébrités, au lieu de diffuser tous les messages à des millions d’abonnés, il serait moins coûteux de récupérer puis fusionner les publications de la célébrité au moment de servir la timeline des abonnés
  • Si des millions d’abonnés font cela, il serait peu coûteux de les récupérer en lecture seule depuis un hot cache

• Une solution intéressante à un problème intéressant. Merci du partage

  • J’ai eu du mal à comprendre le passage où l’auteur passe des « célébrités » aux « bots »
  • On avait l’impression que l’auteur introduisait un concept complètement différent, celui de la « timeline avec pertes »

• Je m’interroge sur cette stratégie qui sacrifie la cohérence. Je me demande s’il y a des réflexions sur d’autres approches que le fan-out complet à la lecture ou à l’écriture

  • Au lieu d’écrire dans la timeline de tous les utilisateurs, j’imagine une méthode consistant à n’écrire qu’une seule fois dans chaque shard ayant au moins un abonné
  • À la lecture, on récupère le contenu pour un utilisateur donné, puis on filtre selon les abonnés réels
  • Comme la lecture reste localisée dans le shard, la latence est faible
  • Pour les méga-followers, la page ne verrait pas d’éléments anciens

• Il n’est pas nécessaire de fournir dans un ordre parfaitement chronologique tout ce que publient les milliers de personnes que chacun suit, mais il semble raisonnable de fournir suffisamment de contenu pour qu’il y ait toujours du contenu frais dans la timeline

  • La solution semblait ne pas être un ordre chronologique imparfait, mais plutôt des publications manquantes dans le fil

• Je me demande comment fonctionnerait l’idée de limiter le nombre d’abonnés pour éviter le problème des hot shards

  • Chaque utilisateur aurait une timeline distincte par tranche de 1 000 abonnés, et le client les fusionnerait
  • Si nécessaire, on pourrait ne charger qu’une partie de la vraie timeline afin d’introduire l’aspect avec pertes

• AWS a une approche générale élégante pour ce problème

  • Elle consiste à affecter chaque utilisateur à plusieurs shards, afin de réduire la probabilité que d’autres utilisateurs partagent exactement tous les mêmes shards
  • S’ils avaient fait du shuffle sharding dès le départ, ils auraient peut-être pu résoudre de nouveaux problèmes sans affecter autant d’autres utilisateurs

• Les comptes qui suivent des centaines de milliers d’utilisateurs sont clairement des bots qui aspirent le contenu. Je les bloquerais, point final

  • J’aime lire sur les défis techniques. Twitter a une architecture spéciale pour les célébrités ayant des millions d’abonnés
  • Si Bluesky est un clone similaire, je me demande pourquoi ils n’ont pas suivi cette voie

• Quand on va directement sur le profil d’un utilisateur pour voir toutes ses publications, il arrive que des posts qui devraient être dans la timeline n’y soient pas

  • Cela explique pourquoi, sur Bluesky, bien que je suive moins de 100 utilisateurs, il m’arrive de ne pas voir leurs publications dans ma timeline

• Je me demande pourquoi ils ont implémenté le fan-out de façon à ce que chaque « page » bloque la récupération de la suivante

  • L’activité de récupération des pages devrait enchaîner la récupération des abonnés et ne pas attendre que tous les éléments d’une page aient été mis à jour
  • Je pense à un composant de récupération qui irait chercher une page, la stockerait dans S3, puis publierait dans une file (SQS) les métadonnées et l’emplacement S3
  • Dans ce système, on pourrait mieux contrôler la concurrence et ralentir le travail en partitionnant la file avec le shard comme clé