Afin de collecter, stocker et traiter les mesures issues de son infrastructure, Facebook a conçu un système nommé Gorillai. Parmi les innovations qu’il apporte : un encodage sans perte et efficace des données.

• Un monde prévisible

Toute technique de compression informatique repose sur l’idée que les données à encoder ne sont pas complètement aléatoires : elles présentent une structure qu’il est possible d’exploiter afin d’en proposer une représentation efficace. Lorsqu’on mesure l’évolution de la température d’un processeur ou celle de l’utilisation de la mémoire vive d’une machine virtuelle, ces données changent continuellement, mais de manière souvent prévisible. Par exemple, la température n’évolue que dans la limite permise par la physique et les systèmes de régulation.

Dans Gorilla, chaque séquence de mesures (qu’on appelle série chronologique) est encodée séparément des autres. Les dates et les valeurs bénéficient également d’un encodage distinct. Dans les deux cas, l’encodage se base sur la dernière ou les deux dernières valeurs enregistrées, ce qui limite la complexité de l’encodeur. Cette approche est appropriée pour l’encodage de mesures à la volée.

• Encodage des dates

Les ingénieurs de Facebook ont remarqué que la très grande majorité (96.4%) des données arrivent à intervalle parfaitement régulier. Lorsque des décalages temporels se produisent, ils sont généralement minimes.
Par exemple, une mesure peut être prise toutes les 60 secondes, avec de temps en temps une seconde d’avance ou de retard. En conséquence, plutôt que d’encoder des dates entières, des delta-de-delta de dates sont enregistrés.

La première date d’une série chronologique est encodée sur 14 bits. Par la suite, pour une date tn, on calcule d1= tn – tn-1 et d2 = tn-1- tn-2. La valeur encodée est alors l’écart entre d1 et d2. En d’autres termes, on n’encode que l’écart entre la variation réelle et celle prédite par les deux valeurs précédentes. L’encodage proprement dit utilise une variante du zig-zag ii qui nécessite moins de bits pour les petites valeurs que pour les grandes.

• Encodage des valeurs

Les valeurs elles-mêmes ont tendance à évoluer relativement lentement. De plus, certaines des valeurs sont, de fait, des entiers. Dans les deux cas, cela signifie que la plupart des bits représentant les valeurs ne changent pas d’une mesure à l’autre. De plus, ces bits inchangés sont situés au début et à la fin de la représentation binaire de la valeur, tandis que les bits modifiés (dits significatifs) se trouvent au cœur de la représentation.

Les valeurs inchangées sont encodées par un simple bit ‘0’. Pour les autres, on détermine si la plage des bits significatifs de la valeur courante est englobée par celle de la valeur précédente. Si c’est le cas, la valeur est encodée par ‘10’, suivi des bits significatifs. Enfin, si la plage n’est pas englobée par la précédente, Gorilla encode ‘11’, suivi du nombre de zéros précédant la plage (sur 5 bits), de la taille de la plage (sur 6 bits), et enfin des bits significatifs.

• Efficacité et adoption de l’encodage

Facebook rapporte un encodage moyen de 1,37 octets par mesure, soit une division du volume de stockage par douze, par rapport à un encodage naïf. En plus de réduire les coûts opérationnels, cette compression améliore
significativement les performances lors des lectures.

Le caractère générique de l’algorithme en fait un bon candidat pour une implémentation dans une bibliothèque logicielle. Des variantes de l’algorithme ont également été implémentées dans les bases de données Prometheus et VictoriaMetrics, qui sont spécialisées dans les séries chronologiques.

• Conclusion

L’algorithme d’encodage de Gorilla a permis aux ingénieurs de Facebook de satisfaire tant les besoins du système de télémétrie du réseau social, que ceux des analystes qui l’exploitent. L’approche, simple et efficace, s’est montrée suffisamment intéressante que pour être adoptée dans d’autres systèmes de gestion des séries chronologiques. Les raffinements qui y ont été apportés depuis la publication de l’algorithme prouvent l’intérêt qu’il suscite.

Source : Mathieu Goeminne, https://mgoeminne.com/2025/10/04/gorilla-un-encodage-efficace-des-series-temporelles/