Toute technique de compression informatique repose sur l’id\u00e9e que les donn\u00e9es \u00e0 encoder ne sont pas compl\u00e8tement al\u00e9atoires : elles pr\u00e9sentent une structure qu’il est possible d’exploiter afin d’en proposer une repr\u00e9sentation efficace. Lorsqu\u2019on mesure l\u2019\u00e9volution de la temp\u00e9rature d\u2019un processeur ou celle de l\u2019utilisation de la m\u00e9moire vive d\u2019une machine virtuelle, ces donn\u00e9es changent continuellement, mais de mani\u00e8re souvent pr\u00e9visible. Par exemple, la temp\u00e9rature n\u2019\u00e9volue que dans la limite permise par la physique et les syst\u00e8mes de r\u00e9gulation. <\/p>\n\n
Dans Gorilla, chaque s\u00e9quence de mesures (qu\u2019on appelle s\u00e9rie chronologique) est encod\u00e9e s\u00e9par\u00e9ment des autres. Les dates et les valeurs b\u00e9n\u00e9ficient \u00e9galement d\u2019un encodage distinct. Dans les deux cas, l\u2019encodage se base sur la derni\u00e8re ou les deux derni\u00e8res valeurs enregistr\u00e9es, ce qui limite la complexit\u00e9 de l\u2019encodeur. Cette approche est appropri\u00e9e pour l\u2019encodage de mesures \u00e0 la vol\u00e9e. <\/p>\n\n
- \n
- Encodage des dates<\/li>\n<\/ul>\n\n
Les ing\u00e9nieurs de Facebook ont remarqu\u00e9 que la tr\u00e8s grande majorit\u00e9 (96.4%) des donn\u00e9es arrivent \u00e0 intervalle parfaitement r\u00e9gulier. Lorsque des d\u00e9calages temporels se produisent, ils sont g\u00e9n\u00e9ralement minimes.
![\"\"](\"https:\/\/myrmidons.net\/wp-content\/uploads\/2025\/11\/0.png\")
Pourcentages des \u00e9carts observ\u00e9s sur 440 000 deltas de dates r\u00e9elles dans Gorilla. Le nombre entre parenth\u00e8ses est la taille, en bits, de leur encodage [i]. <\/figcaption><\/figure>\n\n La premi\u00e8re date d\u2019une s\u00e9rie chronologique est encod\u00e9e sur 14 bits. Par la suite, pour une date tn, on calcule d1= tn \u2013 tn-1 et d2 = tn-1- tn-2. La valeur encod\u00e9e est alors l’\u00e9cart entre d1 et d2. En d\u2019autres termes, on n’encode que l’\u00e9cart entre la variation r\u00e9elle et celle pr\u00e9dite par les deux valeurs pr\u00e9c\u00e9dentes. L\u2019encodage proprement dit utilise une variante du zig-zag ii qui n\u00e9cessite moins de bits pour les petites valeurs que pour les grandes. <\/p>\n\n
- \n
- Encodage des valeurs<\/li>\n<\/ul>\n\n
Les valeurs elles-m\u00eames ont tendance \u00e0 \u00e9voluer relativement lentement. De plus, certaines des valeurs sont, de fait, des entiers. Dans les deux cas, cela signifie que la plupart des bits repr\u00e9sentant les valeurs ne changent pas d\u2019une mesure \u00e0 l\u2019autre. De plus, ces bits inchang\u00e9s sont situ\u00e9s au d\u00e9but et \u00e0 la fin de la repr\u00e9sentation binaire de la valeur, tandis que les bits modifi\u00e9s (dits significatifs) se trouvent au c\u0153ur de la repr\u00e9sentation. <\/p>\n\n
![\"\"](\"https:\/\/myrmidons.net\/wp-content\/uploads\/2025\/11\/0-1.png\")
Repr\u00e9sentation d’une s\u00e9quence de valeurs d\u00e9cimales. Les bits significatifs sont en rouge. [https:\/\/www.vldb.org\/pvldb\/vol8\/p1816-teller.pdf] <\/a><\/figcaption><\/figure>\n\n Les valeurs inchang\u00e9es sont encod\u00e9es par un simple bit \u20180\u2019. Pour les autres, on d\u00e9termine si la plage des bits significatifs de la valeur courante est englob\u00e9e par celle de la valeur pr\u00e9c\u00e9dente. Si c\u2019est le cas, la valeur est encod\u00e9e par \u201810\u2019, suivi des bits significatifs. Enfin, si la plage n\u2019est pas englob\u00e9e par la pr\u00e9c\u00e9dente, Gorilla encode \u201811\u2019, suivi du nombre de z\u00e9ros pr\u00e9c\u00e9dant la plage (sur 5 bits), de la taille de la plage (sur 6 bits), et enfin des bits significatifs. <\/p>\n\n
- \n
- Efficacit\u00e9 et adoption de l’encodage<\/li>\n<\/ul>\n\n
Facebook rapporte un encodage moyen de 1,37 octets par mesure, soit une division du volume de stockage par douze, par rapport \u00e0 un encodage na\u00eff. En plus de r\u00e9duire les co\u00fbts op\u00e9rationnels, cette compression am\u00e9liore
Le caract\u00e8re g\u00e9n\u00e9rique de l\u2019algorithme en fait un bon candidat pour une impl\u00e9mentation dans une biblioth\u00e8que logicielle. Des variantes de l\u2019algorithme ont \u00e9galement \u00e9t\u00e9 impl\u00e9ment\u00e9es dans les bases de donn\u00e9es Prometheus et VictoriaMetrics, qui sont sp\u00e9cialis\u00e9es dans les s\u00e9ries chronologiques. <\/p>\n\n
- \n
- Conclusion<\/li>\n<\/ul>\n\n
L\u2019algorithme d\u2019encodage de Gorilla a permis aux ing\u00e9nieurs de Facebook de satisfaire tant les besoins du syst\u00e8me de t\u00e9l\u00e9m\u00e9trie du r\u00e9seau social, que ceux des analystes qui l\u2019exploitent. L\u2019approche, simple et efficace, s\u2019est montr\u00e9e suffisamment int\u00e9ressante que pour \u00eatre adopt\u00e9e dans d\u2019autres syst\u00e8mes de gestion des s\u00e9ries chronologiques. Les raffinements qui y ont \u00e9t\u00e9 apport\u00e9s depuis la publication de l\u2019algorithme prouvent l\u2019int\u00e9r\u00eat qu\u2019il suscite. <\/p>\n\n
\n
- Conclusion<\/li>\n<\/ul>\n\n
- Efficacit\u00e9 et adoption de l’encodage<\/li>\n<\/ul>\n\n
- Encodage des valeurs<\/li>\n<\/ul>\n\n