Evolução das Estruturas de Dados em Sistemas de Cache
\n
Madelyn Olson, engenheira principal da AWS e mantenedora do projeto Valkey, apresentou na QCon San Francisco 2025 uma análise profunda sobre a reconstrução da hashtable usada pela Valkey, uma alternativa ao Redis. O foco principal foi adaptar estruturas de dados clássicas para a realidade do hardware atual, priorizando eficiência de memória e desempenho sem sacrificar a estabilidade e compatibilidade.
\n\n
Contexto: Do Redis ao Valkey
\n
Valkey surgiu em 2024 após mudanças na licença do Redis, levando ex-contribuidores a criar uma versão que mantém compatibilidade com comandos e funcionalidades do Redis, mas com liberdade para inovações técnicas. O objetivo era modernizar a base, especialmente a estrutura central que gerencia o armazenamento de dados — a hashtable.
\n\n
Desafios das Hashtables Tradicionais
\n
As hashtables clássicas, como as usadas em Redis, são baseadas em técnicas conhecidas desde os anos 2000, com muitos ponteiros e acessos dispersos na memória. Essa estrutura gera um alto overhead de ponteiros (endereços), que prejudica a densidade de armazenamento e a eficiência do cache da CPU, impactando o desempenho.
\n
Olson destacou que, apesar dessas limitações, a prioridade era não regredir em estabilidade e compatibilidade, pois caches são componentes críticos que não podem falhar ou apresentar comportamentos inesperados.
\n\n
Características do Valkey e o Cenário de Uso
\n
- \n
- Tamanho médio das chaves: cerca de 16 bytes, baseado em dados reais do AWS ElastiCache.
- Tamanho médio dos valores: mediana de 80 bytes, com variações amplas.
- Suporte a TTL (time to live): variado, incluindo itens voláteis e não voláteis, com diferentes durações.
- Compatibilidade: suporte a comandos complexos e tipos de dados variados, como conjuntos e sorted sets.
\n
\n
\n
\n
\n\n
A Nova Abordagem: “Swedish” Tables
\n
Para aumentar a densidade de memória e reduzir o número de ponteiros, a equipe adotou o conceito das chamadas “Swedish” tables, que são hashtables cache-aware, projetadas para minimizar cache misses e maximizar o uso eficiente da memória. Essa estrutura evita o tradicional pointer-chasing ao manter os dados mais compactos e sequenciais, facilitando a prefetching de memória pelo processador.
\n\n
Insights sobre Intuição de Sistemas e Prefetching
\n
Olson enfatizou a importância de uma boa intuição sobre o funcionamento do hardware e do sistema operacional para otimizar estruturas de dados. O entendimento detalhado de como a CPU lida com cache, prefetching e alinhamento de memória foi fundamental para garantir ganhos reais de desempenho.
\n\n
Testes Rigorosos para Sistemas Críticos
\n
Como o Valkey é usado em aplicações onde o cache não pode falhar, a equipe investiu em testes extensivos para assegurar que a nova implementação não introduzisse regressões ou inconsistências. Isso inclui testes de compatibilidade com comandos avançados e cenários de uso variados, garantindo que a migração para a nova hashtable seja transparente para os usuários.
\n\n
Impactos Práticos e Próximos Passos
\n
Com essa modernização, o Valkey consegue oferecer melhor uso da memória e maior velocidade, sem perder a robustez necessária para ambientes de produção. A iniciativa demonstra como é possível atualizar estruturas de dados clássicas para aproveitar o hardware moderno, beneficiando sistemas de cache e bancos de dados em geral.
\n\n
Links úteis
\n
