Papers
Gorilla: A Fast, Scalable, In-Memory Time Series Database
Tuomas Pelkonen, Scott Franklin, Justin Teller, Paul Cavallaro, Qi Huang, Justin Meza, Kaushik Veeraraghavan · VLDB (Proceedings of the VLDB Endowment, Vol. 8, No. 12), 2015
O Problema: Monitorar Milhões de Métricas por Segundo
O Facebook precisava monitorar a saúde de milhares de máquinas espalhadas por vários data centers, e para isso usava um banco de séries temporais (TSDB) construído sobre HBase, parte do sistema chamado ODS. No começo de 2013 a equipe percebeu que esse armazenamento não aguentaria a carga de leitura futura: o percentil 90 das consultas já levava vários segundos, o que travava a automação de alertas, e os usuários evitavam análises interativas porque consultas maiores levavam dezenas de segundos ou estouravam o tempo limite. O perfil de uso era peculiar. As escritas dominam: a taxa podia passar de dezenas de milhões de pontos por segundo, enquanto as leituras são ordens de grandeza menos frequentes, vindas sobretudo de dashboards e de sistemas automáticos de alarme. Além disso, os autores observaram que ao menos 85% das consultas ao ODS pediam dados das últimas 26 horas. A intuição de projeto é que quem monitora sistemas quase não liga para um ponto individual, e sim para agregações, e que dados recentes valem muito mais do que antigos, porque saber que algo está quebrado agora é mais útil do que saber que quebrou há uma hora. Daí a proposta: usar um banco em memória como cache write-through dos dados mais recentes, deixando o HBase para o armazenamento de longo prazo. Os requisitos listados incluem 2 bilhões de séries, 700 milhões de pontos por minuto e leituras em menos de um milissegundo.
Comprimindo Timestamps com Delta-of-Delta
Para caber bilhões de séries na memória, o Gorilla comprime cada série separadamente, mas em fluxo, ponto a ponto, usando só informação dos pontos anteriores. Cada ponto original tem 16 bytes (timestamp de 64 bits e valor double de 64 bits). Quanto aos timestamps, os autores notaram que a grande maioria dos dados chegava em intervalo fixo, por exemplo um ponto a cada 60 segundos, às vezes com um ou dois segundos de atraso ou adiantamento. Em vez de gravar o timestamp inteiro, o Gorilla calcula a diferença entre timestamps consecutivos (o delta) e depois a diferença entre deltas sucessivos (o delta-of-delta). Se os deltas são 60, 60, 59 e 61, os deltas-of-delta são 0, -1 e 2. A codificação usa tamanho variável: um único bit '0' quando o delta-of-delta é zero; cabeçalho '10' mais 7 bits para valores entre -63 e 64; '110' mais 9 bits para o intervalo de -255 a 256; '1110' mais 12 bits para -2047 a 2048; e '1111' mais 32 bits para o resto. O cabeçalho do bloco guarda o timestamp inicial, alinhado a uma janela de duas horas, e o primeiro delta ocupa 14 bits. Esses limites foram escolhidos amostrando séries reais. Numa amostra de 440 mil timestamps reais, cerca de 96% cabem em um único bit. Quando falta um ponto, o delta-of-delta ainda cai nas faixas menores, então a perda de um dado não destrói a compressão.
Comprimindo Valores com XOR e o Resultado: 1,37 Byte por Ponto
Para os valores de ponto flutuante, o Gorilla se inspirou em esquemas de compressão usados em computação científica, mas trocou a previsão cara por algo simples. Os autores viram que em muitas séries o valor muda pouco entre pontos vizinhos, e que muitas fontes gravam apenas inteiros. Quando dois doubles são próximos, sinal, expoente e os primeiros bits da mantissa coincidem, então o XOR entre o valor atual e o anterior tem muitos zeros à esquerda e à direita, com os bits relevantes agrupados no meio. A codificação é: o primeiro valor vai sem compressão; se o XOR é zero (valor igual ao anterior), grava-se um único bit '0'; se não, grava-se '1' seguido de um bit de controle. Com controle '0', os bits significativos cabem no mesmo bloco de zeros do valor anterior e só eles são gravados. Com controle '1', gravam-se o número de zeros à esquerda (5 bits), o comprimento do trecho significativo (6 bits) e os bits significativos. Numa amostra de 1,6 milhão de valores reais, mais da metade cabe em um bit, cerca de 30% usam o caso de controle '10' (média de 26,6 bits) e cerca de 19% usam o '11' (média de 36,9 bits). O conjunto das duas técnicas levou o custo médio de 16 bytes para 1,37 byte por ponto, uma redução de 12x. Há um trade-off: blocos maiores comprimem melhor, mas obrigam consultas curtas a decodificar mais dados, e acima de duas horas o ganho é pequeno.
Memória como Cache Write-Through e Persistência sem ACID
O Gorilla funciona como cache write-through das últimas 26 horas de dados, escritos de forma durável no HBase para o longo prazo. Os dados ficam em memória numa estrutura chamada TSmap, composta por um vetor de ponteiros para séries e um mapa case-insensitive do nome da série para a mesma série. O vetor permite varreduras paginadas eficientes, e o mapa permite busca em tempo constante. Cada série é uma sequência de blocos fechados (dados com mais de duas horas, que nunca mais mudam) e um único bloco aberto, de apenas anexar, que recebe os pontos mais novos. A chave da série é um nome em string, e o sharding por essa chave permite escalar apenas adicionando máquinas: no lançamento, as 26 horas de dados couberam em 1,3 TB de RAM distribuídos em 20 máquinas, e depois o cluster foi dobrado duas vezes, chegando a 80 máquinas. Para sobreviver à queda de um host, os dados são gravados no GlusterFS, um sistema de arquivos distribuído compatível com POSIX com replicação 3x. Cada shard mantém um log de apenas anexar, com buffer de até 64 kB (normalmente um ou dois segundos de dados), e a cada duas horas copia os blocos comprimidos para um arquivo de bloco. Os autores afirmam que o Gorilla não oferece garantias ACID e que esse log não é um write-ahead log tradicional: aceitam perder poucos dados em uma queda em troca de maior vazão e disponibilidade de escrita.
Disponibilidade acima de Consistência: Regiões, Falhas e Ferramentas
O desenho de tolerância a falhas parte de uma prioridade explícita: quando há conflito, privilegiar a disponibilidade de dados recentes sobre a completude dos antigos, pois o HBase atende consultas históricas e os sistemas de detecção automática funcionam bem com dados parciais, desde que recentes. Para sobreviver à perda de uma região inteira, o Gorilla mantém duas instâncias totalmente independentes em regiões distintas. Cada escrita é enviada às duas, sem qualquer tentativa de garantir consistência entre elas, e as leituras vão para a instância disponível mais próxima. Se uma região cai, as leituras são tentadas na outra. Dentro de cada região, um sistema baseado em Paxos chamado ShardManager atribui shards a nós. Durante a movimentação de shards, os clientes de escrita guardam em buffer até 1 minuto de dados e descartam os pontos mais velhos. Depois da falha, um shard fica parcialmente indisponível até ser relido do disco, e a consulta devolve resultado marcado como parcial. A biblioteca cliente tenta então a outra região e, se as duas devolverem resultado parcial, entrega ao chamador com um sinalizador de dados incompletos. Os autores também relatam ferramentas novas viabilizadas pela baixa latência, como um motor de correlação de séries temporais que faz busca por força bruta em até 1 milhão de séries por vez.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.