Actualización: El algoritmo está ahora licenciado bajo WTFPLv2. Los códigos fuente están disponibles en https://github.com/schizofreny/middle-out.
La compresión Middle-Out ya no es una invención ficticia del programa de HBO Silicon Valley. Inspirados tanto por el programa de televisión como por los nuevos conjuntos de instrucciones vectoriales, hemos ideado un nuevo algoritmo de compresión sin pérdidas para datos de series temporales. La compresión es siempre un compromiso entre la velocidad y el ratio, y nunca es fácil equilibrar estas compensaciones, pero el concepto de middle-out nos permite llevar la puntuación de Weissman aún más lejos.
Simplemente rompe la dependencia de los datos. Si necesitamos un valor anterior para calcular uno actual, necesitamos todos los valores antecedentes. Pero si empezamos a procesar desde varias posiciones del fragmento, sólo dependemos de los valores antecedentes dentro de este fragmento. Esto nos permite, por ejemplo, utilizar eficazmente las instrucciones SIMD.
¿Cómo funciona?
En principio, el algoritmo calcula el XOR de un nuevo valor y el anterior. De esta manera obtenemos una especie de diferencia entre los valores y podemos almacenar esta diferencia sola. En los conjuntos de datos de series temporales esta diferencia suele tener un número de ceros iniciales y/o finales. Por lo tanto, la información que necesitamos almacenar suele ser significativamente menor, pero también necesitamos almacenar el recuento de ceros iniciales y la longitud del fragmento XOR distinto de cero.
Estos conceptos se utilizan generalmente en los algoritmos de compresión actuales, por ejemplo, Gorilla de Facebook. En aras de la eficiencia de la compresión, Gorilla opera a nivel de bits, pero estas operaciones son bastante amplias. Hemos diseñado nuestra compresión para que sea lo más rápida posible, por lo que pasamos de la granularidad de bits a la de bytes. Como consecuencia, uno esperaría una peor relación de compresión, pero ese no es siempre el caso.
Con respecto al middle-out, la compresión opera en bloques de datos, pero esto no es un problema ya que las bases de datos de series temporales utilizan bloques de todos modos.
¿Qué pasa con la relación de compresión?
Examinemos la relación de compresión en dos escenarios diferentes. El primer escenario – tomamos una serie de dobles (es decir, 0,1, 0,2, 0,3, …) y medimos la relación de compresión en función de la porción de puntos repetidos. Para comparar utilizamos la compresión Gorilla de Facebook. Por defecto, Gorilla comprime tanto los valores como las marcas de tiempo de los datos de las series temporales. Para nuestras pruebas, la compresión de las marcas de tiempo está desactivada.
No es sorprendente encontrar que Gorilla tiene una relación de compresión ligeramente mejor para este tipo de datos. Podemos ver la misma tendencia con las secuencias de enteros largos.
Segundo escenario – conjuntos de datos. Los conjuntos de datos A y B comparten los mismos datos de stock de minutos. En el caso del conjunto de datos A, los puntos de precio se comprimen como números de coma flotante. En el conjunto de datos B, estos números se multiplican primero para desplazar el punto decimal y, por lo tanto, podemos representar estos números como largos sin perder precisión.
Los conjuntos de datos C y D se generan utilizando una herramienta de evaluación comparativa de InfluxData : representan las escrituras en disco y el uso de memoria de redis. En el caso del conjunto de datos A, Gorilla comprime los datos ligeramente mejor que nuestro algoritmo, con un ratio de 1,45 frente a 1,3. Otros conjuntos de datos que utilizan números enteros se comprimen mejor con nuestro nuevo algoritmo. La mayor diferencia se observa en el conjunto de datos D, donde la relación de compresión de Middle-out es de 3,3, mientras que Gorilla sólo puede comprimir estos datos con una relación de 1,84. La relación de compresión depende sustancialmente de la entrada de datos y, obviamente, hay conjuntos de datos en los que un algoritmo comprime mejor que otro. Pero si el rendimiento es su preocupación – siga leyendo.
Rendimiento de la compresión
Actualmente tenemos dos implementaciones compatibles del algoritmo. Una utiliza un nuevo conjunto de instrucciones AVX-512 disponible en las CPUs Skylake-X. La segunda implementación está dirigida a ordenadores que no soportan este conjunto de instrucciones.
El rendimiento se mide en un solo núcleo de Skylake-X funcionando a 2,0 GHz.
Los siguientes gráficos muestran la velocidad de compresión y descompresión de ambas implementaciones en comparación con Gorilla de Facebook.
Este gráfico muestra el rendimiento de la compresión medido en los cuatro conjuntos de datos comentados anteriormente, además del rendimiento de una serie con el respectivo porcentaje de valores repetidos.
El rendimiento de la compresión Gorilla varía entre 120-440 MB/s con una velocidad media de 185 MB/s. El rendimiento más bajo de nuestra implementación escalar comprime alrededor de 670 MB/s para el 50% de los valores que se repiten. Esto se debe a una alta proporción de errores de predicción de bifurcación. La velocidad media de compresión es de 1,27 GB/s. El algoritmo que utiliza instrucciones vectoriales no sufre los errores de predicción de bifurcación y comprime los datos de 2,33 GB/s a 2,59 GB/s, con una velocidad media de 2,48 GB/s. No está mal para un chip de un solo núcleo de 2 GHz.
Gorilla puede descomprimir estos datos a velocidades que van de 100 MB/s a 430 MB/s . Pero como se puede ver, nuestra descompresión de los mismos datos es incluso más rápida que una compresión. La descompresión no vectorizada funciona a una velocidad mínima de 2,36 GB/s y 2,7 GB/s de media. Los códigos vectorizados descomprimen los datos a partir de 3,4 GB/s, llegando a 4,86 GB/s para el conjunto de datos D. De media, es capaz de descomprimir los datos a 4,0 GB/s.
El aumento de velocidad global medio para la compresión es de 6,8x (implementación escalar) y 13,4x (implementación vectorizada). El aumento de velocidad medio para la descompresión es de 16,1 veces y 22,5 veces respectivamente.
Sobre nosotros
En Schizofreny nos dedicamos al rendimiento y creemos que siempre se pueden superar los límites. Nos encantan los retos y estamos aquí para ayudarte con tus problemas de HPC.
Parte II
www.vldb.org/pvldb/vol8/p1816-teller.pdf
https://github.com/influxdata/influxdb-comparisons/