UPDATE: Algoritmo agora licenciado sob WTFPLv2. Códigos fonte disponíveis em https://github.com/schizofreny/middle-out.
Compressão de saída média já não é uma invenção fictícia do programa da HBO Silicon Valley. Inspirado tanto pelo programa de TV quanto pelos novos conjuntos de instruções vetoriais, criamos um novo algoritmo de compressão sem perdas para dados de séries temporais. A compressão é sempre sobre um compromisso entre velocidade e relação e nunca é fácil equilibrar estes trade-offs, mas todo o conceito de middle-out nos permite empurrar ainda mais Weissman para a pontuação.
Simplesmente quebra a dependência dos dados. Se precisarmos de um valor anterior para calcular um valor atual, precisamos de todos os valores antecedentes. Mas se começarmos a processar a partir de múltiplas posições do pedaço, dependemos apenas dos valores antecedentes dentro deste fragmento. Isto permite-nos, por exemplo, utilizar eficazmente as instruções SIMD.
Como funciona?
Em princípio, o algoritmo calcula o XOR de um novo valor e o anterior. Desta forma obtemos uma espécie de diferença entre os valores e podemos armazenar esta diferença sozinhos. Em conjuntos de dados de séries temporais esta diferença tipicamente tem um número de zeros à esquerda e/ou à direita. Assim, as informações que precisamos armazenar são geralmente significativamente menores, mas também precisamos armazenar a contagem de zeros iniciais e o comprimento do fragmento XOR não-zero.
Estes conceitos são geralmente usados em algoritmos de compressões atuais, por exemplo, o Gorilla do Facebook . Por uma questão de eficiência de compressão, o Gorilla opera no nível de bits, mas estas operações são bastante expansivas. Nós projetamos nossa compressão para ser o mais rápido possível, então passamos de granularidade de bit para byte. Como consequência, seria de esperar uma taxa de compressão pior, mas nem sempre é o caso.
Com relação ao middle-out, a compressão opera em blocos de dados, mas isso não é um problema, já que as bases de dados de séries temporais usam blocos de qualquer forma.
E quanto à taxa de compressão?
Vamos examinar a taxa de compressão em dois cenários diferentes. O primeiro cenário – tomamos uma série de duplas (isto é, 0.1, 0.2, 0.3, …) e medimos a taxa de compressão dependendo da porção de pontos de repetição. Para comparação, usamos a compressão Gorilla do Facebook. Por padrão a Gorilla comprime tanto os valores como os timestamps dos dados da série temporal. Para nossos testes, a compressão dos timestamps é desativada.
Não é surpreendente descobrir que o Gorilla tem uma taxa de compressão ligeiramente melhor para estes tipos de dados. Podemos ver a mesma tendência com sequências deinteiros longos.
Segundo cenário – conjuntos de dados. Os conjuntos de dados A e B compartilham os mesmos dados de estoque minuto. No caso do conjunto de dados A, os pontos de preço são comprimidos como números de pontos flutuantes. No conjunto de dados B estes números são primeiro multiplicados para deslocar o ponto decimal e assim podemos representar estes números como longos sem perder precisão.
Datasets C e D são gerados usando uma ferramenta de benchmarking do InfluxData : representando gravações em disco e uso de memória redis. No caso do conjunto de dados A, o Gorilla comprime os dados ligeiramente melhor do que o nosso algoritmo – com uma razão de 1.45 vs 1.3. Outros conjuntos de dados usando inteiros são melhor compactados com o nosso novo algoritmo. A maior diferença pode ser vista no conjunto de dados D onde a razão de compressão Middle-out é 3,3, enquanto o Gorilla pode comprimir esses dados apenas com uma razão de 1,84. A taxa de compressão depende substancialmente da entrada de dados e existem obviamente conjuntos de dados onde um algoritmo comprime melhor do que outro. Mas se o desempenho é sua preocupação – continue lendo.
Desempenho de Compressão
Atualmente temos duas implementações compatíveis do algoritmo. Uma utiliza um novo conjunto de instruções AVX-512 disponível nas CPUs Skylake-X. A segunda implementação visa computadores sem o suporte deste conjunto de instruções.
O rendimento é medido em um único núcleo do Skylake-X rodando a 2.0 GHz.
Os gráficos a seguir mostram a velocidade de compressão e descompressão de ambas as implementações em comparação com o Gorilla do Facebook.
>
Este gráfico mostra a taxa de compressão medida nos quatro conjuntos de dados discutidos acima, mais a taxa de compressão de uma série com a respectiva percentagem de valores repetidos.
A taxa de compressão do Gorilla varia de 120-440 MB/s com uma velocidade média de 185 MB/s. O menor rendimento da nossa implementação escalar comprime cerca de 670 MB/s para 50% dos valores de repetição. Isto é devido a uma alta taxa de erros de previsão do ramo. A velocidade média de compressão é de 1,27 GB/s. Um algoritmo que utiliza instruções vetoriais não sofre de erros de previsão de ramos e comprime dados de 2,33 GB/s a 2,59 GB/s, com uma velocidade média de 2,48 GB/s. Nada mal para um único núcleo de 2 GHz.
Gorilla pode descomprimir estes dados a velocidades que variam de 100 MB/s a 430 MB/s . Mas como você pode ver, nossa descompressão dos mesmos dados é ainda mais rápida do que uma compressão. A descompressão não vetorizada opera a uma velocidade mínima de 2,36 GB/s e 2,7 GB/s em média. Os códigos vetorizados descomprimem os dados a partir de 3,4 GB/s, atingindo 4,86 GB/s para o conjunto de dados D. Em média é capaz de descomprimir os dados a 4,0 GB/s.
A velocidade média geral de compressão é de 6,8x (implementação escalar) e 13,4x (implementação vetorizada). A velocidade média para descompressão é de 16,1x e 22,5x respectivamente.
Sobre nós
Nós na Schizofreny somos dedicados ao desempenho e acreditamos que os limites podem sempre ser empurrados ainda mais. Adoramos desafios e estamos aqui para ajudar com seus problemas de HPC.
Parte II
>
www.vldb.org/pvldb/vol8/p1816-teller.pdf
https://github.com/influxdata/influxdb-comparisons/