Construindo um banco de dados de séries temporais do zero

• Escrito em Go, mas em grande parte independente de linguagem

• Dados de séries temporais são uma coleção de vários valores com timestamp. Cada item é um ponto de dados

→ O volume é grande. Só faz sentido quando há muito dado. Em muitos casos, a captura acontece milhões de vezes por segundo

→ Append-only, ordenação cronológica, prioridade para dados recentes

→ Leitura em lote por unidades específicas de tempo

→ Alta cardinalidade (a unidade do conjunto é muito grande)

→ Na maioria dos casos, usa-se lendo dados recentes

• Desenvolveu-se em Go a biblioteca de engine de banco TStorage, refletindo o fato de que dados de séries temporais são, em geral, muito mais intensivos em escrita

• Modelo de dados

→ Modelo de dados linear

→ Particionamento dos pontos de dados por unidade de tempo

→ Cada partição funciona como um banco independente separado, contendo todos os dados daquele intervalo de tempo

→ Apenas o head e a partição seguinte ficam no heap, podendo ser modificados como partições em memória

→ Para evitar perda de dados, grava-se no WAL (Write Ahead Log) antes de escrever

→ Os dados das partições anteriores são armazenados em disco como arquivo único. As partições em disco são somente leitura

• Partição em memória

→ A lista de pontos de dados é representada no heap como um array (semelhante ao slice do Go)

→ Por causa de latência e sincronização, ocorrências out-of-order são frequentes. Se estiverem na mesma partição, podem ser reordenadas no momento do armazenamento via buffering; se estiverem em partições diferentes, isso é possível adicionando atrás de uma partição anterior que não seja o head

→ Armazena exatamente os mesmos dados que são realmente gravados no WAL, permitindo recuperação mesmo em caso de falha

• Partição em disco

→ Em um diretório por partição, armazena metadados e os dados reais comprimidos (uma versão reduzida do Prometheus V3 Storage)

→ Formato de dados memory-mapped (pode ser cacheado pelo kernel com mmap)

→ Os metadados formam um índice em formato JSON

• A codificação dos dados, representados como tuplas de timestamp e valor, usa o método de codificação proposto no artigo Gorilla do Facebook

→ Timestamps e valores são codificados com métodos diferentes

→ O timestamp usa um valor inteiro sem sinal de 64 bits com codificação Delta-of-delta

✓ Codificação Delta: método que registra apenas a diferença entre o valor anterior e o atual

✓ Codificação Delta-of-Delta: como normalmente ocorre em intervalos regulares de tempo, registra-se apenas o delta do delta

✓ Como é codificado com comprimento variável, Delta-of-Delta usa o menor espaço

→ Os values usam valores de ponto flutuante com sinal de 64 bits e codificação XOR

✓ O primeiro valor é armazenado como está

✓ Faz-se XOR com o próximo valor; se der 0, é igual ao valor anterior, então armazena-se apenas um bit 0

✓ Se não for 0, calcula-se com base nos outros bits (Meaningful Bit)

✓ Calcula-se a quantidade de zeros à frente/atrás; se a quantidade for igual, armazena-se apenas 0 e os bits significativos, caso contrário armazena-se a quantidade de leading zeros, a quantidade de Meaningful Bits e os próprios bits