Otimização de Memória e Codificações Internas do Redis

Ir de "o Redis escolhe uma codificação compacta para coleções pequenas automaticamente" (o comportamento passivo que o conceito Core Data Types cobre) para as três coisas que o Capítulo 9 de Redis in Action, "Reduzindo o uso de memória", mostra você ativamente fazendo para cortar memória ainda mais: manter estruturas curtas o suficiente para merecer essa codificação automática, fazer sharding de uma estrutura lógica grande entre muitas chaves físicas pequenas para que cada shard fique dentro dos limiares de codificação compacta, e empacotar bits e bytes diretamente em Strings para dados que não precisam de uma estrutura de jeito nenhum. Os próprios números do capítulo tornam o que está em jogo concreto: "esses métodos me ajudaram a reduzir o uso de memória de mais de 70 gigabytes, distribuídos em três máquinas, para menos de 3 gigabytes em uma única máquina." Este conceito cobre duas das três técnicas que são genuinamente decisões de design distintas (sharding e empacotamento de bit/byte) em vez da mecânica de limiar de codificação já coberta em Tipos de Dados Principais do Redis: Strings, Lists e Hashes.

• Uma única tabela de lookup que cresceu demais para uma chave: o próprio exemplo do livro: um HASH mapeando mais de 370.000 IDs de cidade para informação de cidade, fragmentado em muitos HASHes menores para que cada shard fique abaixo dos limiares de listpack.
• Contar eventos únicos em uma escala onde um único SET seria grande demais: um SET em shard de IDs de visitante truncados para manter uma contagem ao vivo de visitantes únicos diários sem um SET gigante.
• Armazenar um registro pequeno e de tamanho fixo por ID sequencial para uma população enorme: códigos de localização por usuário (país/estado) empacotados 2 bytes por vez em STRINGs em shard, para uma base de usuário maior do que qualquer String única consegue guardar.
• Cachear milhões de valores string pequenos como um armazenamento chave-valor simples: o mesmo padrão de "divida a chave, use a cauda como um campo de hash" que a própria documentação de otimização de memória do Redis ainda recomenda hoje para exatamente esse caso.
• Flags booleanas ou de contador densas por ID: SETBIT/GETBIT/GETRANGE/SETRANGE em uma String, a mesma primitiva sobre a qual a seção de Bitmaps do conceito Tipos de Dados Avançados se apoia, usada aqui para campos de largura fixa arbitrária em vez de flags de um bit.

Por que estruturas curtas importam aqui, brevemente

O mecanismo em si (codificação compacta estilo ziplist abaixo de um limiar de tamanho configurável, promovida para uma estrutura completa acima disso) é território do Core Data Types do Redis, incluindo a renomeação de ziplist para listpack no Redis 7.0. O que vale a pena reafirmar aqui é por que isso economiza tanto: um nó de LIST duplamente encadeado precisa de "três ponteiros, dois inteiros... mais a string e um byte extra", que o livro mede em "21 bytes de overhead para armazenar 3 bytes reais de dado" para uma string curta, contra os "aproximadamente 2 bytes" de overhead de uma ziplist para a mesma entrada. Essa lacuna é o motivo inteiro pelo qual sharding vale a pena: manter a estrutura de cada shard dentro dos limites de codificação compacta é o que faz as economias de memória abaixo de fato se materializarem, e Redis in Action é direto sobre o preço de perder esse limite: empurrar uma LIST codificada como ziplist de 1.000 para 100.000 entradas derrubou o throughput de RPOPLPUSH de aproximadamente 50.000 ops/seg para 553 ops/seg, porque "ziplists são efetivamente inutilizáveis" uma vez que crescem tanto. Sharding é, na prática, uma forma de continuar aproveitando o desconto de estrutura curta em uma escala que de outra forma forçaria toda estrutura individual a passar de seu limite.

Estruturas em shard: dividindo uma estrutura lógica em muitas chaves físicas

A ideia central, nas próprias palavras do livro: "em vez de armazenar o valor X na chave Y, vamos armazenar X na chave Y:<shardid>." Uma função shard_key() decide a qual chave física uma dada entrada lógica pertence: para chaves numéricas sequenciais, shard_id = key // shard_size (chaves numericamente adjacentes pousam no mesmo shard); para chaves não numéricas, um checksum CRC32 da chave módulo uma contagem de shard calculada espalha entradas aproximadamente de forma uniforme: "estamos usando CRC32 neste caso porque retorna um inteiro simples sem trabalho adicional, é rápido de calcular... e porque vai funcionar bem o suficiente para a maioria das situações." Tanto total_elements (total de entradas esperado) quanto shard_size (entradas alvo por shard) alimentam esse cálculo, e o livro sinaliza uma restrição operacional real: "você não deveria mudar nenhum desses dois valores, ou quando você mudar, deveria ter um processo para mover seus dados dos shards de dado antigos para os shards de dado novos (isso é geralmente conhecido como resharding)."

HASH em shard. O exemplo resolvido do livro faz sharding do HASH de lookup de cidades de 370.000 entradas por ID numérico de cidade. Todo HSET/HGET se torna shard_hset/shard_hget, que computam a chave do shard e depois delegam para o comando HASH comum naquele shard. O ganho: "em uma máquina de 64 bits, armazenar o HASH único de todas as nossas cidades ocupa aproximadamente 44 megabytes. Mas com essas poucas pequenas mudanças para fazer sharding dos nossos dados... os HASHes em shard juntos ocupam aproximadamente 12 megabytes. Isso é uma redução de 70% no tamanho do dado, o que nos permitiria armazenar 3,5 vezes mais dado do que antes." O livro generaliza isso além de um único HASH grande: "se você se encontrar armazenando muitas strings ou números relativamente curtos como valores STRING simples com chaves nomeadas consistentemente como namespace:id, você pode armazenar esses valores em HASHes em shard para uma redução significativa de memória em alguns casos": o mesmo argumento de overhead por chave que o case study da Instagram do conceito Core Data Types faz (21 GB de chaves String por ID de mídia caindo para aproximadamente 5 GB como Hashes), só aplicado um nível mais adiante ao também dividir o próprio Hash em shards.

SET em shard. Para contar visitantes únicos diários, armazenar UUIDs de 128 bits completos como membros de SET seria tanto grande quanto incapaz de usar a codificação compacta intset. O livro em vez disso trunca cada UUID para seus primeiros 56 bits (mantidos como um inteiro, então set-max-intset-entries ainda se aplica), justificado por um cálculo de colisão de aniversário: "contanto que tenhamos menos de 250 milhões de visitantes únicos em um dado período de tempo... vamos ter no máximo 1% de chance de uma única colisão", e "se tivermos menos de 25 milhões de visitantes únicos, então a chance de não contar um usuário cai a ponto de precisarmos rodar o site por aproximadamente 2.739 anos antes de deixarmos de contar um único usuário." Fazer sharding desse SET de ID truncado (via a mesma função shard_key(), prefixado com um caractere não numérico já que os IDs não são densamente empacotados) e rastrear uma estimativa de tamanho esperado que cresce com a contagem real de ontem produz um número concreto: "o Redis vai usar aproximadamente 9,5 megabytes para armazenar a contagem de visitante único. Sem sharding, o Redis usaria 56 megabytes para armazenar o mesmo dado... Isso é uma redução de 83% no armazenamento com sharding, o que nos deixaria armazenar 5,75 vezes mais dado com o mesmo hardware."

O que o livro deliberadamente não faz sharding. LISTs, porque fazer sharding de uma sem scripting Lua é "difícil": o livro adia isso para uma implementação baseada em Lua de um capítulo posterior. ZSETs, porque comandos como ZRANGE, ZRANGEBYSCORE, ZRANK, e ZCOUNT "exigem operar em todos os shards de um ZSET para calcular seu resultado final", o que "viola quase todas as expectativas sobre quão rápido um ZSET deveria ter desempenho": sharding anularia o motivo inteiro de usar um ZSET. O fallback do livro para um ZSET genuinamente enorme é mais estreito: manter um ZSET auxiliar de score mais alto/mais baixo aparado com ZADD/ZREMRANGEBYRANK, respondendo "quem está no top N" sem nunca materializar as consultas de faixa da estrutura completa em shard.

Empacotando bits e bytes em Strings

Sharding ainda armazena cada valor lógico como um membro de SET/HASH de primeira classe. Empacotamento vai um passo além: armazenar campos de largura fixa como offsets brutos dentro de uma String, usando GETRANGE/SETRANGE (leitura/escrita de faixa de byte) e GETBIT/SETBIT (leitura/escrita de um único bit): "com esses quatro comandos, conseguimos usar STRINGs do Redis para armazenar contadores, strings de comprimento fixo, Booleanos, e mais no formato mais compacto possível sem compressão."

O exemplo resolvido do livro empacota dados de localização por usuário (país mais, quando disponível, estado ou província dos EUA/Canadá) em exatamente 2 bytes por usuário: um byte como um offset em uma tabela COUNTRIES ordenada, um byte como um offset na tabela STATES daquele país (0 significando "não encontrado", então dado não inicializado lê corretamente como "desconhecido" em vez de um índice válido). Como STRINGs do Redis têm um teto de 512 MB e uma população de "750 milhões de usuários hoje... precisaria de mais de 1,5 gigabytes de espaço", o livro faz sharding dos dados empacotados também entre muitas STRINGs: USERS_PER_SHARD = 2**20 (cerca de 1.048.576 usuários, "pouco mais de 1 milhão de entradas") por shard, cada shard pousando em "cerca de 2 megabytes por STRING." SETRANGE escreve o código de 2 bytes de cada usuário em offset = (user_id % USERS_PER_SHARD) * 2 no shard location:<shard_id>; um ZSET companheiro rastreia o maior ID de usuário visto até agora, para que uma passada de agregação saiba quantos shards de fato precisam ser varridos. Ler de volta procede em blocos: puxar pedaços dos bytes brutos de um shard, decodificar todo par de 2 bytes de volta em um par país/estado via as mesmas tabelas de lookup, e acumular contagens, que é como o livro computa distribuições de país/estado sobre toda a população ou uma lista arbitrária fornecida de IDs de usuário (análise de localização de seguidores, por exemplo), agrupando lookups em pipelines em vez de uma ida e volta por usuário.

O livro é explícito de que isso é a extensão natural de SETBIT/GETBIT, não uma técnica diferente: "armazenamos múltiplos bytes de dado por usuário, [mas] podemos usar GETBIT e SETBIT de forma idêntica para armazenar bits individuais, ou até grupos de bits": a mesma ideia de String-como-array-de-largura-fixa que a seção de Bitmap do conceito de Tipos de Dados Avançados usa para flags de um bit por usuário escala limpamente para registros de 2 bytes, 4 bytes, ou largura arbitrária com GETRANGE/SETRANGE.

Livro vs. hoje

A renomeação de ziplist para listpack da qual tanto esta técnica quanto sua codificação subjacente dependem é coberta em Tipos de Dados Principais do Redis: Strings, Lists e Hashes; não repetida aqui.

O padrão de HASH em shard ainda é orientação oficial do Redis hoje, não um workaround da era do livro. A documentação atual de otimização de memória do Redis dedica uma seção completa, "Usando hashes para abstrair um armazenamento chave-valor simples muito eficiente em memória por cima do Redis", a essencialmente a mesma ideia: dividir uma chave como object:1234 em uma chave HASH (object:12) e um nome de campo (34) para que "todo hash acabe contendo 100 campos, que é um compromisso ideal entre CPU e memória economizada." Seu próprio benchmark contra 100.000 chaves STRING simples: "USE_OPTIMIZATION definido como true: 1,7 MB de memória usada. USE_OPTIMIZATION definido como false: 11 MB de memória usada": mais de 6x menor, a mesma ordem de grandeza que o exemplo de sharding de HASH do livro reporta. Curiosamente, essa mesma página de documentação atual ainda carrega um nome de diretiva de configuração de sua redação original da era Redis 2.2, hash-max-zipmap-entries: um nome de antes de a ziplist existir, uma renomeação mais antiga do que a mudança de ziplist para listpack; no Redis atual o botão equivalente é hash-max-listpack-entries. Então a técnica é atual, mas esse canto específico da documentação preserva o valor de duas renomeações de terminologia obsoleta em uma caixa de aviso.

O padrão de SET em shard para contagem única aproximada, porém, foi substancialmente superado, por uma ferramenta que o livro não tinha. O HyperLogLog (coberto em Tipos de Dados Avançados) responde exatamente a pergunta que o exemplo de SET em shard do livro resolve ("aproximadamente quantos visitantes distintos hoje") em um ~12 KB fixo independentemente da escala, contra o próprio resultado de 9,5 MB em shard do livro (e 56 MB sem shard) para uma contagem de visitante comparável. A troca que o HyperLogLog faz e que o SET em shard do livro não faz é abrir mão de contagens exatas e consultas de pertencimento; quando essa troca é aceitável (e para "quantos visitantes únicos" geralmente é), o HyperLogLog é tanto mais simples de implementar quanto muito menor do que fazer sharding manual de um SET. A técnica de SET em shard permanece correta e relevante para casos que precisam de contagens exatas ou respostas de pertencimento (SETs em shard ainda suportam SISMEMBER em um shard específico, o HyperLogLog fundamentalmente não consegue); é o caso de "só me dê uma contagem aproximada" que hoje tem uma resposta feita sob medida e menor, que o capítulo do livro antecede.

Os limiares padrão maiores do Redis desde a era do livro reduzem, mas não eliminam, com que frequência sharding manual é necessário. hash-max-listpack-entries tem padrão de 512 hoje (Redis 7+), o mesmo padrão que o hash-max-ziplist-entries do livro usava, então um Hash precisa das mesmas poucas centenas de entradas antes de precisar de sharding de qualquer forma; nada ali afrouxou. O que mudou é que as codificações compactas do Redis agora cobrem mais da superfície de tipo (Sets ganharam set-max-listpack-entries no Redis 7.2, além do intset da era do livro), então uma faixa mais ampla de coleções pequenas ganha o desconto automático sem nenhum sharding em nível de aplicação de jeito nenhum. Sharding manual ainda é o movimento documentado e correto uma vez que uma única coleção lógica é esperada a exceder esses limiares por ordens de grandeza; ele só agora precisa ser usado com menos frequência do que em 2013.

• Sharding troca a superfície de comando completa de uma única estrutura por um subconjunto dela, de propósito. O livro faz sharding de HASHes e SETs mas explicitamente se recusa a fazer sharding de ZSETs ou LISTs sem maquinaria extra, porque sharding só compensa para os comandos que conseguem ser respondidos tocando um shard (HGET, SADD, SISMEMBER); comandos que inerentemente precisam da estrutura inteira (ZRANGE, ZRANK, acesso ordenado a LIST) ou exigem espalhar para todo shard, anulando sua garantia de desempenho original, ou precisam ser implementados como um algoritmo genuinamente diferente (LISTs em shard com script Lua) em vez de uma substituição direta.
• total_elements e shard_size são um compromisso, não um ajuste. Mudar qualquer um deles depois que dados já foram escritos muda a qual shard toda chave mapeia, dividindo silenciosamente uma coleção lógica entre atribuições de shard antigas e novas a menos que uma migração de resharding real mova os dados. Esse é um custo operacional mais pesado do que ajustar hash-max-listpack-entries, que só afeta a codificação interna, não em qual chave um valor mora.
• Strings empacotadas com bit/byte são a opção mais eficiente em memória e a mais frágil. Não há nome de campo, nem tag de tipo, nem autodescrição em uma String empacotada; as tabelas de offset COUNTRIES/STATES que o livro mantém no código da aplicação são a única coisa que torna um registro de 2 bytes significativo. Uma incompatibilidade de versão entre o código que escreveu o dado e o código que o lê de volta (uma lista de país atualizada com offsets diferentes, por exemplo) decodifica silenciosamente todo registro para o local errado sem nenhum erro levantado.
• Uma única String grande tem um teto de 512 MB, e crescer uma perto desse limite é em si caro. O livro observa que "devido à limpeza de dado que o Redis faz ao definir um valor além do fim de uma STRING existente, definir o primeiro valor no fim de uma STRING longa vai levar mais tempo do que seria esperado para uma simples chamada SETBIT": mais um motivo para dado empacotado ser fragmentado entre muitas STRINGs bem antes de atingir o teto de 512 MB, não só para ficar abaixo dele.
• Estruturas curtas, sharding, e empacotamento se compõem, mas cada otimização estreita o que ainda é fácil de mudar depois. Uma vez que dados de cidade moram em HASHes em shard com uma contagem fixa de shard, ou dados de localização moram em códigos empacotados de 2 bytes em STRINGs em shard, adicionar um campo novo ou mudar o formato de codificação significa tocar o dado de todo shard, não editar o valor de uma chave: o mesmo tipo de custo de migração que o conceito Core Data Types sinaliza para trocar um objeto com chave String por um Hash, só um nível mais fundo.