- Publié le 26 juin 2024, One Million Checkboxes était un site où tout le monde manipulait en temps réel le même million de cases à cocher, et il a traité plus de 650 millions de coches avant sa fermeture deux semaines plus tard
- L’état lui-même ne représentait que 1 million de bits, soit 125 Ko, mais l’architecture initiale fondée sur nginx, Flask/gunicorn et Redis pubsub a rapidement atteint ses limites face à un trafic inattendu
- Quand des dizaines de milliers de personnes ont afflué depuis Hacker News, Reddit, Mastodon et Twitter, une série de problèmes est apparue : épuisement des connexions Redis, explosion de la bande passante, absence de validation des entrées et application de mises à jour obsolètes
- La réponse s’est concentrée sur des mesures rapides à déployer : montée en charge des serveurs et de Redis, traitement des mises à jour par lots, réduction du format de transmission, plafond de bande passante à 250 Mbit/s via Linux
tc, et scripts de redémarrage de processus - Le backend a ensuite été réécrit en Go pour être stabilisé, puis la logique de gel des cases a été traitée de façon atomique avec des scripts Lua Redis, jusqu’à la clôture du site le 11 juillet 2024 à 16:35, heure de l’Est
Le site et la conception initiale
- One Million Checkboxes (OMCB) est un site web lancé le 26 juin 2024, proposant 1 million de cases à cocher globales
- Quand un utilisateur coche ou décoche une case, le changement est immédiatement répercuté sur l’écran de tous les autres utilisateurs
- Sa création a pris 2 jours, et le nombre d’utilisateurs attendu ne dépassait au mieux que quelques centaines
- La réaction réelle a été bien plus importante que prévu
- En quelques heures après le lancement, des dizaines de milliers de personnes sont arrivées et ont manipulé plusieurs millions de cases
- Le trafic provenait de Hacker News, /r/InternetIsBeautiful, Mastodon et Twitter
- Quelques jours plus tard, le site a aussi été présenté dans le Washington Post et le New York Times
- Une partie des logs du tout début du premier jour n’a pas été conservée
- Au départ, seul le dernier million d’entrées de log de la journée était gardé
- La stabilisation a commencé dès le deuxième jour, avec plus de 50 millions de cases cochées ce jour-là
- Avant la fermeture du site, le total cumulé a dépassé 650 millions de coches
L’architecture d’origine centrée sur Redis
- L’état des cases à cocher était représenté par 1 million de bits
- Une case cochée valait
1, une case non cochée valait0 - La taille de l’état complet était de 125 Ko
- Le client stockait ce bitset et s’y référait au moment du rendu
- Une case cochée valait
- Le client était conçu pour éviter de surcharger le DOM
- Les 1 million d’éléments n’étaient pas tous injectés dans le DOM
- react-window était utilisé pour ne rendre que les cases visibles à l’écran, avec un petit tampon autour
- La configuration serveur restait simple et pensée pour une montée en charge horizontale
- nginx servait le contenu statique et transférait les requêtes API ainsi que les connexions websocket vers des serveurs Flask
- Les serveurs Flask correspondaient à deux instances exécutées avec gunicorn
- Redis servait à la fois au stockage de l’état des cases et de file de messages
- L’usage de Redis était lui aussi direct
- Les primitives de manipulation de bits de Redis étaient utilisées pour modifier l’état de chaque case individuellement
- Quand un client envoyait un événement de coche, Flask inversait le bit correspondant dans Redis et écrivait l’événement dans pubsub
- Les deux serveurs Flask lisaient pubsub et annonçaient les changements aux clients connectés chez eux
- Les instantanés complets de l’état servaient à corriger les mises à jour manquées
- Ils permettaient de resynchroniser les clients dont l’onglet était resté en arrière-plan et avait raté des mises à jour
- Dans l’implémentation initiale, l’état complet était envoyé toutes les 30 secondes
Principes de mise à l’échelle
- Le coût devait pouvoir être plafonné
- Une autoscaling illimitée pouvant faire exploser les coûts a été écartée
- Il a été jugé préférable que le système casse au-delà de la charge attendue
- La durée de popularité était supposée brève
- Les réponses faisables en quelques heures ont été privilégiées à des solutions plus abouties demandant plusieurs jours ou semaines
- La dette technique induite a été acceptée
- Les choix techniques privilégiaient la simplicité et l’exploitation directe
- L’idée était de pouvoir se connecter directement aux serveurs, lancer des commandes et déboguer sur place
- Les dépendances principalement retenues étaient celles qu’il était possible d’exploiter et de déboguer soi-même
- L’expérience centrale du site reposait sur la synchronisation globale
- Il fallait voir des changements immédiats où que l’on se trouve dans la page
- L’architecture n’a pas été étendue en n’envoyant que les cases visibles pour chaque utilisateur
Premier jour : ajout de serveurs et goulot d’étranglement Redis
- Dans les 30 minutes suivant le lancement, la charge a fortement grimpé, et le site fonctionnait encore mais n’aurait pas tenu longtemps ainsi
- L’amélioration la plus évidente était d’ajouter des serveurs
- nginx pouvait facilement faire du reverse proxy vers des instances Flask sur d’autres VM, et l’état était déjà dans Redis
- Un deuxième serveur a été ajouté vers 12:30 PM et a immédiatement atteint 100 % de charge
- Au début, on pensait qu’un ou deux serveurs supplémentaires suffiraient
- En pratique, le trafic augmentait au même rythme que l’infrastructure
- Le site est monté en tête de Hacker News, et l’activité sur Twitter a fortement augmenté
- Les connexions entre les serveurs Flask et Redis sont devenues le goulot d’étranglement
- Il n’y avait pas de pool de connexions Redis, et Redis approchait d’un état de pénurie de connexions
- Le système a été modifié pour envoyer les mises à jour par lots
- La compatibilité avec les anciens clients n’a pas été prise en compte, en partant du principe que les utilisateurs rechargeraient la page
- Un pool de connexions Redis a aussi été ajouté, mais il ne fonctionnait pas proprement avec la combinaison gunicorn + Flask
- Il semble malgré tout avoir aidé à réduire le nombre de connexions Redis
- Le problème n’a pas été approfondi ensuite, la transition vers Go ayant pris le relais
- La limitation de débit de création de session a été supprimée
- Son état était stocké dans Redis, alors que Redis était déjà en train d’épuiser ses connexions
- Le problème ne venait pas d’une explosion de nouvelles sessions, mais d’une seule session envoyant beaucoup de données
- C’était risqué à court terme, mais jugé acceptable
- L’instance Redis a aussi été montée en gamme
- Le service utilisé était Digital Ocean managed Redis
- L’instance est passée d’une petite configuration à 1 CPU partagé et 2 Go de RAM à une configuration avec 4 CPU dédiés et 32 Go de RAM
- Le redimensionnement a pris environ 30 minutes
Problèmes de bande passante et réduction du volume transmis
- Au départ, le coût de la bande passante n’avait pas été suffisamment pris en compte
- Digital Ocean facture $0.01 par Go au-delà du quota gratuit
- Un quota gratuit de 1 To existait déjà grâce à un projet précédent, et l’idée était qu’OMCB n’aurait pas un impact majeur
- Les instantanés complets de l’état pouvaient consommer très vite la bande passante
- 1 million de bits, c’est 1 Mbit
- Envoyés toutes les 30 secondes à 1 000 personnes, cela représente environ 2 Go par minute, soit 120 Go par heure
- Ce calcul ne tient même pas compte des mises à jour incrémentales
- La vérification de la bande passante et la définition d’un plafond de coût ont été réalisées sur la machine nginx
- Le nombre d’octets envoyés était vérifié avec
ip -s link show dev eth0 - Comme un unique reverse proxy nginx était utilisé, il était facile d’en déduire l’origine de la bande passante
- Le nombre d’octets envoyés était vérifié avec
- La réduction du volume transmis a suivi deux axes
- Diminuer la fréquence des instantanés complets de l’état
- Réduire le format des mises à jour incrémentales
- Le format des mises à jour par lots a été fortement compressé
- Le format initial était une liste de dictionnaires du type
{ "index": 123, "value": true } - Le format final était une paire de tableaux d’index true et false, sous la forme
[[123, 125], [124]] - Cette méthode était 5 fois plus courte que l’implémentation d’origine
- Le format initial était une liste de dictionnaires du type
- Un hard cap a été mis en place avec Linux
tcpour éviter une dérive incontrôlée des coûts- Le trafic de l’interface publique
eth0a été limité à 250 Mbit/s - Cela représente environ 2 Go par minute, soit un peu moins de 3 To par jour
- Avec un tarif de $0.01 par Go, cela évitait qu’une facture incontrôlable ne s’accumule pendant la nuit
- Le trafic de l’interface publique
Deuxième jour : absence de validation des entrées et réplica Redis
- Le lendemain matin, le site était hors service, et la cause était l’absence de validation des entrées
- Rien n’empêchait de cibler des cases à cocher avec un index supérieur à 1 million
- Quelqu’un a manipulé des cases avec des index se comptant en centaines de millions
- Le site a alors semblé avoir atteint 1 million de cases cochées, ce qui a fait croire qu’il était terminé
- Les données Redis ont aussi grossi inutilement
- Des millions de
0ont été ajoutés entre le 1 000 000e bit et le 100 000 000e bit - Les données envoyées au client sont devenues 100 fois plus volumineuses
- Des millions de
- La récupération a été rapide
- nginx a été arrêté
- Seuls les 1 million de premiers bits du bitset existant ont été copiés dans un nouveau bitset
- L’ancien bitset a été conservé pour le débogage
- Le code a été modifié pour pointer vers le nouveau bitset, et une validation des entrées a été ajoutée
- Le chargement initial de la page était lui aussi devenu lent
- Redis était très chargé, et un bug du pool de connexions créait aussi trop de connexions
- Plutôt que de déboguer le problème du pool de connexions, un réplica Redis a été ajouté pour répartir la charge et les connexions du primaire
- L’adresse IP privée du réplica a dû être trouvée manuellement
- Comme l’indiquait la documentation Digital Ocean, le DNS public fonctionnait avec le préfixe
replica-, mais pas le DNS privé - Utiliser l’IP publique semblait risqué, car cela aurait fait transiter le trafic par l’Internet public avec un risque de facturation de bande passante
- Des tentatives ont été faites sur des adresses proches des IP privées du primaire et des autres serveurs, et l’IP privée du réplica a été trouvée au troisième ou quatrième essai
- Cette IP a ensuite été codée en dur
- Comme l’indiquait la documentation Digital Ocean, le DNS public fonctionnait avec le préfixe
Redémarrage des processus et correction des mises à jour obsolètes
- Les processus Flask continuaient à crasher, apparemment à cause du manque de connexions Redis
- Au lieu d’un débogage approfondi, un script bash a été écrit pour vérifier le nombre de processus Flask en cours d’exécution
- Si moins de 3 processus tournaient, l’unité systemd était redémarrée
- Le script a été ajouté au crontab
- La configuration nginx a aussi été ajustée
- Les serveurs en panne étaient temporairement retirés de la rotation
- Après ce changement, le site s’est stabilisé
- La synchronisation d’état côté client avait un bug de stale update
- Le client recevait à la fois des mises à jour incrémentales et des instantanés complets
- Comme aucun horodatage n’était associé à ces mises à jour, un ancien lot incrémental pouvait être appliqué après réception d’un instantané plus récent
- Résultat : l’utilisateur pouvait voir un état totalement incorrect jusqu’au prochain instantané complet
- Une atténuation basée sur les horodatages a été ajoutée
- Un horodatage a été ajouté aux instantanés complets
- Chaque mise à jour écrite dans Redis pubsub s’est aussi vue attribuer un horodatage
- Chaque lot envoyé au client a reçu l’horodatage maximal des mises à jour incrémentales qu’il contenait
- Le client a été modifié pour ignorer les lots plus anciens que son dernier instantané complet
- Cette solution n’était pas parfaite
- S’il y avait au moins une mise à jour récente dans un lot, celui-ci pouvait encore être appliqué même si la plupart des autres mises à jour étaient anciennes
- Malgré cela, la situation s’est nettement améliorée
Réécriture en Go et stabilisation
- Le lendemain matin, le site tenait toujours, et l’effort s’est ensuite concentré sur la réécriture du backend
- Un e-mail du Washington Post était déjà arrivé
- La façon de mettre fin au site faisait aussi partie des réflexions
- Le plan de fermeture consistait à geler les cases cochées si elles n’étaient pas décochées assez vite
- Ce changement pouvait provoquer un nouveau pic d’activité et du travail serveur supplémentaire
- Rien ne garantissait que l’architecture existante à base de Flask puisse l’absorber
- Le backend a été réécrit en Go avec l’aide d’un ami, Eliot
- De 2 PM à 2 AM le dimanche, l’implémentation a été discutée puis l’ensemble du backend a été porté
- La structure générale n’a pas été profondément modifiée
- Certains points ont ralenti le travail, comme la recherche d’une bibliothèque Go
socketiocompatible avec le protocole le plus récent
- Le gain de performance a été très important
- L’application montait tellement bien en charge que des bots pouvaient désormais y injecter beaucoup trop de trafic
- Une meilleure limitation de débit est devenue nécessaire
- Un DDoS a aussi eu lieu le dimanche soir
- La réponse a consisté à placer le site derrière Cloudflare et à modifier légèrement la configuration nginx
La logique de fermeture du site
- Après la réécriture en Go, le site a fonctionné de manière stable
- Pendant une semaine, il a surtout fallu répondre aux interviews et à l’attention suscitée
- Ensuite, le travail sur la fermeture du site a commencé
- Le mode de fermeture reposait sur le gel des cases à cocher
- Si une case cochée n’était pas décochée assez vite, elle passait à l’état frozen
- Avec le temps, l’ensemble du site finissait entièrement frozen
- Redis a dû stocker un état supplémentaire
- Une table de hachage conservait l’instant où chaque case avait été cochée pour la dernière fois
- Cet état était trop volumineux pour être envoyé au client, mais restait acceptable dans Redis
- Une valeur
time_to_freezeétait aussi stockée
- Le gel était décidé au moment du uncheck
- Si
now - last_checked > time_to_freeze, alors la case n’était pas décochée - À la place,
frozen_bitsetétait mis à jour pour indiquer que cette case était frozen frozen_bitsetétait distribué aux clients de la même façon que l’état checked- Le client désactivait les cases dont le bit frozen était activé
- Si
- Un traitement séparé a été ajouté pour que le gel se produise même si personne ne décochait
- Il cherchait périodiquement les bits qui devaient être gelés mais ne l’étaient pas encore, puis les passait à l’état frozen
- La logique correspondante a été placée dans un script Lua Redis pour une exécution atomique
- Cela facilitait l’évitement des race conditions
- Le changement de fermeture a été déployé 2 semaines et 1 jour après le lancement
- Le 11 juillet 2024 à 16:35, heure de l’Est, la case 491915 a été cochée, mettant fin au site
Coûts et enseignements
- Le coût d’exploitation du site a été d’environ $850
- Les dons ont couvert une bonne partie de cette somme
- Le bilan est qu’il ne s’agissait pas d’une grosse perte
- Le choix de Redis et nginx est considéré comme satisfaisant
- Redis et nginx sont jugés très utiles
- Le fait de les avoir opérés directement a facilité le débogage et les corrections
- Le seul léger inconfort venait du manque de contrôle total sur l’instance Redis managée
- Le choix de ne pas concevoir longuement la montée en charge dès le départ est évalué positivement
- Il est difficile de prévoir ce qui fonctionnera vraiment sur Internet
- Si plusieurs semaines avaient été passées à réfléchir au scale dès le début, le site n’aurait peut-être jamais été lancé
- Le grand nombre d’utilisateurs a aidé à maintenir la motivation et à fixer les priorités de maintenance
- Une demande pour les interactions anonymes limitées a aussi été confirmée
- Les gens montrent de l’intérêt pour des sites permettant d’interagir avec des inconnus de manière restreinte
- Cela a renforcé la confiance dans l’idée de continuer à créer ce type de site
1 commentaires
Avis de Hacker News
C’était un article dont on pouvait beaucoup apprendre, avec une bonne dose de savoir historique sur les systèmes distribués.
En dehors du stockage, j’ai l’impression qu’ils ont rencontré presque tous les types de points d’interruption et de défaillance, et c’était intéressant de voir comment ils les ont résolus.
Je ne savais pas que Redis prenait en charge Lua ; en voyant ça, ça me donne envie de l’essayer comme magasin d’état alternatif.
La bande passante est l’une de mes plus grosses frustrations avec les services cloud, parce qu’il n’y a pas de limite stricte pour éviter les dépassements de facturation.
Cela dit, ni l’un ni l’autre n’a été un gros problème, et c’était assez étonnant d’avoir un projet où le stockage n’était pas un enjeu significatif. Pour moi, c’était une expérience nouvelle.
La bande passante, en revanche, a vraiment été pénible. Pendant environ deux jours, je suis resté tendu à vérifier les octets sortants de la NIC et à refaire les calculs, et l’absence de hard cap faisait peur. Et pourtant, Digital Ocean a des prix plutôt raisonnables.
Je n’ai pas essayé les services serverless populaires, mais si je comprends bien, là-bas les coûts de bande passante peuvent frapper assez fort.
Et Lua dans Redis est vraiment puissant : si on peut accepter une légère perte de performances, ça permet d’éviter beaucoup de problèmes difficiles et pleins de conditions de concurrence, et c’était agréable à utiliser.
Excellent article, et le site mérite aussi des félicitations.
Mais à titre personnel, je pense que cet article rédigé est ce dont il peut être le plus fier.
Le passage clé, à mon avis, est celui disant que « construire le site en deux jours en se souciant très peu de la scalabilité était un bon choix ».
C’est particulièrement quelque chose que les ingénieurs en début de carrière devraient apprendre. La scalabilité n’est pas un problème tant qu’elle n’en devient pas un.
Et quand elle le devient, c’est plutôt un bon problème à avoir, et ce n’est pas forcément aussi difficile à corriger qu’on l’imagine.
J’ai vu beaucoup de systèmes où les microservices étaient devenus le « choix évident », non pas pour permettre le passage à l’échelle ou la séparation des équipes, mais simplement parce que les développeurs en avaient envie.
Faire monter ce genre de système en charge est un vrai calvaire.
Article récent lié : One Million Checkboxes - https://news.ycombinator.com/item?id=40800869 - juin 2024, 305 commentaires
Ce genre de projet est amusant.
Il y a environ 6 ans, j’ai lancé Pixmap sur Android, une petite application collaborative d’édition de pixels qui prenait en charge de plus grandes grilles, comme 1024x1024.
Il y avait une file qui appliquait chaque événement à une image PNG, et quand un client se connectait, il chargeait le PNG initial, puis chaque événement de dessin de pixel n’était reçu que comme un petit objet.
De cette manière, on peut tirer parti de la compression d’image au chargement initial, et les ensembles de changements ultérieurs restent très petits. De plus, comme tous les événements sont stockés dans un log, on peut aussi « rembobiner » l’image [0].
[0] 22mb : https://blog.winricklabs.com/images/pixmap-rewind-demo.gif
Du coup, je bricole plutôt un canvas adressable via des appels API.
https://x.com/RussTheMagic/status/1816749136487588311
Bon article. Je me demande combien cela a finalement coûté.
Le coût total était d’environ 850 dollars, et les dons ont presque couvert ce montant.
Après le passage à Go, j’ai fait l’erreur de ne pas vraiment réduire l’infrastructure, et j’aurais aussi pu supprimer le deuxième réplica Redis que j’avais ajouté. Si je m’étais concentré sur les coûts, je pense que j’aurais pu les diviser par deux.
Mais les dons couvraient presque les coûts, et j’avais trop d’autres choses à faire, donc je ne me suis pas vraiment concentré là-dessus.
Même après l’arrêt du site, j’ai gardé l’infrastructure quelque temps pour préparer les graphiques, etc., ce qui a coûté un peu plus cher ; aujourd’hui je suis légèrement dans le rouge, mais pas énormément.
En tant que personne qui découvre le backend, je me demande s’il existe une architecture alternative plus simple pour ce projet.
Ce serait bien d’avoir un moyen plus facile d’héberger et de synchroniser avec les clients l’état d’un million de bits. Certaines solutions de l’article étaient difficiles à comprendre.
Les projets de l’auteur sont excellents.
J’aurais voulu expliquer plus longuement les technologies utilisées, mais l’article était déjà très long et j’ai eu l’impression qu’il était difficile d’en ajouter davantage.
Si tu as des questions, je serai ravi d’y répondre.
Honnêtement, je ne sais pas trop comment simplifier beaucoup plus l’architecture. Il existe sans doute des services qu’on peut utiliser pour ce genre de chose, mais à mes yeux cela revient surtout à transférer la complexité à quelqu’un d’autre.
Au final, il faut une base de données pour suivre les cases cochées, un moyen d’insérer les données dans cette base, un moyen d’indiquer l’état actuel aux clients, un moyen pour les clients de signaler au serveur qu’ils ont coché une case et de mettre à jour l’état, un moyen d’informer les clients quand une case est cochée ou décochée, et une manière d’éviter de rendre en permanence un million d’éléments DOM.
Ici, Redis stockait l’état des cases ; par simplicité, on stockait directement le million de bits, et on envoyait l’ensemble du million de bits aux clients. C’était pratique parce que les données n’étaient pas si volumineuses.
Flask et WebSocket géraient les événements de coche et les mises à jour ; on envoyait à la fois les mises à jour de cases individuelles et la mise à jour complète du million de cases, et react-window permettait d’éviter les problèmes de rendu.
Le reste — contenu statique nginx et reverse proxy — servait surtout à faciliter la montée en charge ; l’implémentation est possible sans ces détails et le site fonctionne quand même. Il ne supporte simplement pas la même charge.
Au lieu d’une base de données, on peut stocker l’ensemble de bits dans un fichier et l’utiliser avec mmap. Au lieu d’un reverse proxy, l’application pourrait aussi gérer directement les requêtes HTTP et les connexions WebSocket.
C’est une configuration avec quelques serveurs web derrière lesquels se trouvent un cache et une file de publication/abonnement.
On aurait pu tout traiter en mémoire sur une seule grosse machine, mais si elle ne suivait pas la demande, ou si elle échouait pour une raison quelconque, tout se serait retrouvé complètement bloqué.
À part une approche non scalable du genre mettre une liste globale d’un million de booléens dans le même processus que l’API backend.
(checked, start_x, start_y, end_x, end_y). Ce n’est pas complètement évident ?Génial.
Je me demande si le prochain article sera une analyse statistique indiquant quelles cases ont été le moins ou le plus cochées.
Je me souviens avoir été un peu triste quand une case que j’avais choisie après avoir beaucoup fait défiler la page a été décochée presque instantanément.
Avant ça, il y a encore une histoire à raconter sur le site.
Je me demande si le jeu est encore en ligne.
Quand je vais sur https://onemillioncheckboxes.com/, aucune case n’est cochée, et la console JS n’affiche que ceci :
{"total":0,"totalGold":0,"totalRed":0,"totalGreen":0,"totalPurple":0,"totalOrange":0,"recentlyChecked":false}Comme exemple exactement opposé d’une implémentation scalable, il existe une implémentation de One Million Checkboxes en moins de 1000 caractères. Version Deno.
https://gist.github.com/jeff-hykin/4cdebafd8698298d021f103e2...