Como funciona a descompressão de valores para o Gorilla do Facebook no caso em que a contagem de zeros à esquerda não é armazenada
-
29-09-2020 - |
Pergunta
Refiro-me a este artigo: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf
Minha pergunta é em relação à seção 4.1.2, onde diz:
Quando o XOR não for zero, calcule o número de zeros líderes e à direita no XOR, armazene '1' seguido por a) ou b):
(a) (Bit de controle '0') Se o bloco de bits significativos se enquadra no bloco de bits significativos anteriores, ou seja, existem pelo menos tantos zeros líderes e tantos zeros à direita quanto no valor anterior, use essas informações para a posição do bloco e basta armazenar o valor Xorle significativo.
Ao descompactar, como sabemos se devemos adicionar zeros à esquerda ou zeros à cauda?Por exemplo, digamos que temos os seguintes números de 48 bits:
A = 0xfff ffff fffff
B = 0xfff 0000 fffff
C = 0xfff 0ff0 fffff
e
A xor B = 0x000 ffff 00000
B xor C = 0x000 0ff0 00000
Se seguirmos o algoritmo de compressão para A xor B
armazenaremos o número de zeros à esquerda, que é 12
, bem como os bits significativos ffff
.
Para agora B xor C
porque "há pelo menos tantos zeros à esquerda e tantos zeros à direita quanto no valor anterior", então armazenamos apenas os bits significativos ff
.Quando eu quero decodificar ff
, com base nos bits compactados anteriores, sei que tenho pelo menos 12 zeros iniciais e 20 zeros finais, mas ainda preciso preencher 8 zeros;Eu deveria fazer ff00
ou 00ff
ou outra combinação?
Solução
Encontrei minha resposta depois de ler a implementação de referência: https://github.com/facebookarchive/beringei/blob/92784ec6e22572f28500c76b669276007635c875/beringei/lib/TimeSeriesStream.cpp
O uso do termo “pedaços significativos” no artigo é ambíguo.Eu pensei que a frase "use essas informações para a posição do bloco e apenas armazene o valor XOREILED SIGNIFICADO". significa armazenar os pedaços com todos os zeros à direita e à esquerda foram removidos porque "valor XOR significativo" é um valor sem zero à esquerda e à direita.Mas, de acordo com a implementação de referência, você apenas remove a mesma quantidade de zeros à esquerda e à direita do valor delta anterior;os bits significativos neste caso ainda podem conter alguns zeros à esquerda e à direita.
Então, para o exemplo da questão, devemos armazenar 0ff0
como bits significativos em vez de apenas ff
.