Un téléspectateur passe à 4 min 12 s d'un clip tendance de 9 minutes, regarde pendant 40 secondes, revient à l'intro, puis rebondit. Multipliez cela par les quelques centaines de milliers de sessions quotidiennes qui touchent un agrégateur de taille moyenne et vous obtenez la question que chaque responsable produit finit par se poser : quelles parties de cette vidéo les gens regardent-ils réellement et combien de personnes distinctes ont regardé chaque partie ?
La réponse naïve est unewatch_eventstableau : une ligne par(utilisateur, vidéo, seconde). Cela fonctionne jusqu'à ce que ce ne soit plus le cas. Une vidéo de 9 minutes dure 540 secondes. Un téléspectateur qui regarde le tout génère 540 lignes. Un million de visiteurs de notre catalogue génèrent des centaines de millions de lignes par jour, et la seule requête que quiconque leur lance est :COUNT(DISTINCT user_id) GROUPE PAR seconde. QueCOMTE(DISTINCT)est un tri ou un hachage sur toute la partition à chaque fois que quelqu'un ouvre l'onglet d'analyse.
Chez TopVideoHub, nous regroupons les vidéos tendances dans toute la région Asie-Pacifique, de sorte qu'un seul clip populaire peut passer de zéro à un demi-million de sessions en un après-midi lorsqu'il arrive simultanément dans les flux JP et KR. Nous ne voulions pas d'une table de faits qui s'allongeait de centaines de millions de lignes par jour pour répondre à une question dont la réponse est à peu près correcte. "Environ 41 000 téléspectateurs uniques ont vu le crochet à 0:08" est tout aussi exploitable que "41 287". Cette tolérance à l'approximation est exactement la raison pour laquelle HyperLogLog est conçu, et Postgres dispose d'une extension testée au combat pour cela.
Cet article est la conception sur laquelle nous avons atterri : des esquisses HLL de taille fixe, une par(vidéo, time_bucket), que vous pouvez fusionner, découper et unir entre régions en quelques millisecondes. L'application principale est PHP 8.4 sur LiteSpeed derrière Cloudflare, avec notre couche de recherche sur SQLite FTS5 ; le magasin d'analyse est une instance Postgres distincte, et HLL est ce qui a rendu ce magasin abordable.
HyperLogLog estime la cardinalité d'un ensemble en utilisant une quantité fixe de mémoire, quel que soit le nombre d'éléments que vous lui lancez. L'intuition : hachez chaque élément, examinez la plus longue séquence de zéros non significatifs que vous avez vue et utilisez-la pour estimer combien d'éléments distincts ont dû traverser pour produire une séquence aussi longue. Les implémentations réelles divisent l'espace de hachage en plusieurs registres et font la moyenne avec une moyenne harmonique corrigée du biais,...
[Courte citation de 8% de l'article original]