MISE À JOUR : L’algorithme est désormais sous licence WTFPLv2. Codes sources disponibles à https://github.com/schizofreny/middle-out.

La compression middle-out n’est plus une invention fictive de l’émission Silicon Valley de HBO. Inspirés à la fois par l’émission de télévision et par les nouveaux jeux d’instructions vectorielles, nous avons imaginé un nouvel algorithme de compression sans perte pour les données de séries temporelles. La compression est toujours un compromis entre la vitesse et le ratio et Il n’est jamais facile d’équilibrer ces compromis, mais tout le concept de middle-out nous permet de pousser le score de Weissman encore plus loin.

Il brise simplement la dépendance des données. Si nous avons besoin d’une valeur précédente pour calculer une valeur actuelle, nous avons besoin de toutes les valeurs antécédentes. Mais si nous commençons le traitement à partir de plusieurs positions du chunk, nous ne dépendons que des valeurs antécédentes au sein de ce fragment. Cela nous permet, par exemple, d’utiliser efficacement les instructions SIMD.

Comment cela fonctionne-t-il ?

En principe, l’algorithme calcule le XOR d’une nouvelle valeur et de la précédente. De cette façon, nous obtenons une sorte de diff entre les valeurs et nous pouvons stocker cette diff seule. Dans les séries de données temporelles, cette différence comporte généralement un certain nombre de zéros de tête et/ou de queue. Par conséquent, l’information que nous devons stocker est généralement beaucoup plus petite, mais nous devons également stocker le nombre de zéros de tête et la longueur du fragment XOR non nul.

Ces concepts sont généralement utilisés dans les algorithmes de compression actuels, par exemple le Gorilla de Facebook . Pour des raisons d’efficacité de compression, Gorilla opère au niveau des bits, mais ces opérations sont assez expansives. Nous avons conçu notre compression pour être aussi rapide que possible et nous sommes donc passés de la granularité du bit à celle de l’octet. En conséquence, on pourrait s’attendre à un plus mauvais ratio de compression, mais ce n’est pas toujours le cas.

En ce qui concerne le middle-out, la compression opère sur des blocs de données, mais ce n’est pas un problème car les bases de données de séries temporelles utilisent des blocs de toute façon.

Qu’en est-il du ratio de compression ?

Examinons le ratio de compression dans deux scénarios différents. Le premier scénario – nous prenons une série de doubles (c’est-à-dire 0,1, 0,2, 0,3, …) et mesurons le taux de compression en fonction de la portion de points répétés. Pour la comparaison, nous utilisons la compression Gorilla de Facebook. Par défaut, Gorilla compresse à la fois les valeurs et les horodatages des données de séries temporelles. Pour notre test, la compression des timestamps est désactivée.

Il n’est pas surprenant de constater que Gorilla a un ratio de compression légèrement meilleur pour ces types de données. Nous pouvons voir la même tendance avec les séquences d’entiers longs.

Deuxième scénario – les ensembles de données. Les ensembles de données A et B partagent les mêmes données de stock de minutes. Dans le cas de l’ensemble de données A, les points de prix sont compressés comme des nombres à virgule flottante. Dans le dataset B, ces nombres sont d’abord multipliés pour décaler le point décimal et donc nous pouvons représenter ces nombres comme longs sans perdre la précision.

Les datasets C et D sont générés à l’aide d’un outil de benchmarking d’InfluxData : représentant les écritures sur disque et l’utilisation de la mémoire redis. Dans le cas du jeu de données A, Gorilla compresse les données légèrement mieux que notre algorithme – avec un ratio de 1,45 contre 1,3. Les autres jeux de données utilisant des entiers sont mieux compressés avec notre nouvel algorithme. La plus grande différence peut être vue dans le jeu de données D où le taux de compression de Middle-out est de 3,3, alors que Gorilla ne peut compresser ces données qu’avec un taux de 1,84. Le taux de compression dépend essentiellement de l’entrée des données et il y a évidemment des jeux de données pour lesquels un algorithme compresse mieux qu’un autre. Mais si les performances sont votre préoccupation – continuez à lire.

Performances de compression

En ce moment, nous avons deux implémentations compatibles de l’algorithme. L’une utilise un nouveau jeu d’instructions AVX-512 disponible sur les processeurs Skylake-X. La seconde implémentation cible les ordinateurs sans le support de ce jeu d’instructions.

Le débit est mesuré sur un seul cœur de Skylake-X fonctionnant à 2,0 GHz.

Les graphiques suivants montrent la vitesse de compression et de décompression des deux implémentations par rapport au Gorilla de Facebook.

Ce graphique montre le débit de compression tel que mesuré sur les quatre ensembles de données discutés ci-dessus, plus le débit d’une série avec le pourcentage respectif de valeurs répétées.

Le débit de la compression Gorilla varie de 120 à 440 Mo/s avec une vitesse moyenne de 185 Mo/s. Le débit le plus faible de notre implémentation scalaire compresse autour de 670 Mo/s pour 50% de valeurs répétitives. Ceci est dû à un taux élevé de mauvaise prédiction des branches. La vitesse de compression moyenne est de 1,27 Go/s. Un algorithme utilisant des instructions vectorielles ne souffre pas d’erreur de prédiction de branche et compresse les données de 2,33 Go/s à 2,59 Go/s, avec une vitesse moyenne de 2,48 Go/s. Pas mal pour un seul cœur de puce de 2 GHz.

Gorilla peut décompresser ces données à des vitesses allant de 100 Mo/s à 430 Mo/s . Mais comme vous pouvez le constater, notre décompression des mêmes données est encore plus rapide qu’une compression. La décompression non vectorisée fonctionne à une vitesse minimale de 2,36 Go/s et 2,7 Go/s en moyenne. Les codes vectorisés décompressent les données à partir de 3,4 GB/s, atteignant 4,86 GB/s pour le jeu de données D. En moyenne, il est capable de décompresser les données à 4,0 GB/s.

Le speedup global moyen pour la compression est de 6,8x (implémentation scalaire) et 13,4x (implémentation vectorisée). Le speedup moyen pour la décompression est respectivement de 16,1x et 22,5x.

A propos de nous

Nous, chez Schizofreny, sommes dévoués à la performance et nous croyons que les limites peuvent toujours être repoussées plus loin. Nous aimons les défis et nous sommes là pour vous aider avec vos problèmes de HPC.

Partie II

www.vldb.org/pvldb/vol8/p1816-teller.pdf

https://github.com/influxdata/influxdb-comparisons/

.