Valkey 9.2 Otimiza Sorted Sets com B+ Trees, Prometendo Economia de Memória
Aprofundamento CEVIU
Aprofundamento
A versão 9.2 do Valkey, que está em fase de candidatos a lançamento, implementa uma mudança interna importante na gestão de grandes sorted sets. A estrutura de dados skiplist, usada anteriormente, foi substituída por uma variante de B+ tree chamada fbtree (Feature B+ Tree). O skiplist tradicionalmente dispersa os nós na memória, resultando em maior consumo e latência devido a acessos não contíguos e múltiplos cache misses. O fbtree organiza os dados em nós de tamanho fixo, que podem conter até 61 entradas ou ponteiros filhos, o que compacta o armazenamento e reduz o overhead por membro.
A fbtree otimiza as operações de busca através de features e utiliza instruções SIMD para processamento paralelo, acelerando a identificação do nó filho correto. Para comandos de alcance como ZRANGE, as folhas do fbtree são ligadas por uma lista duplamente encadeada, permitindo varreduras sequenciais eficientes. Além disso, a nova estrutura armazena o score e o membro como um valor empacotado, removendo indireções de ponteiro. Internamente, para comandos como ZPOPMIN, o fbtree mantém um cache dos nós mais à esquerda e mais à direita, garantindo complexidade O(1) para essas operações.
O que mudou
Esta atualização do Valkey 9.2 representa uma evolução significativa em relação às versões anteriores. Antes, sorted sets grandes dependiam da estrutura skiplist para ordenar seus elementos. Essa implementação gerava um overhead de memória considerável, como detalhado no artigo, devido à dispersão dos nós e a múltiplos acessos à memória. Com o fbtree no Valkey 9.2, há uma mudança fundamental na estrutura interna. Testes internos mostram uma redução de 36% a 43% no overhead de memória por membro em conjuntos de cinco milhões de elementos, comparado ao uso da skiplist.
Por que isso importa
Para desenvolvedores que utilizam sorted sets extensivamente, especialmente com grandes volumes de dados, essa otimização no Valkey 9.2 significa uma economia substancial de memória e um ganho de desempenho em operações como ZADD e ZREM. A mudança para a estrutura fbtree, que usa B+ trees e otimizações como SIMD e nós ligados, reduz o overhead por membro e melhora a eficiência do cache. Isso pode resultar em sistemas mais escaláveis e com menor custo operacional, especialmente em ambientes com restrições de memória ou que exigem alta performance para manipulação de dados ordenados. O comportamento dos comandos existentes permanece inalterado, minimizando o impacto na lógica da aplicação, e apenas a saída de OBJECT ENCODING para sorted sets grandes muda para 'btree'.
Linha do tempo
PostgreSQL implementa a Blink-tree de Alta Concorrência para índices B-tree.
Salvatore Sanfilippo submete PR adicionando um novo tipo de dado, arrays, ao Redis.
Anunciado o etcd 3.7.0-beta.0, com foco em otimização de consultas.
Redis 8.2 tem seu status e próximos passos discutidos.
ScyllaDB adota índice baseado em trie como padrão e triplica throughput.
Redis Adota Bitmaps Comprimidos para Otimizar Armazenamento.
Valkey 9.2 Otimiza Sorted Sets com B+ Trees, Prometendo Economia de Memória.
Perguntas frequentes
O que é o fbtree no Valkey 9.2?
Fbtree é uma variante de B+ tree (Feature B+ Tree) que substitui a skiplist no Valkey 9.2 para gerenciar grandes sorted sets. Ela agrupa entradas em nós de tamanho fixo e utiliza otimizações como buscas assistidas por SIMD para melhorar a eficiência e reduzir o consumo de memória.
Como a nova estrutura fbtree afeta o consumo de memória?
A fbtree reduz o overhead de memória por membro em sorted sets grandes, com testes mostrando uma economia de 36% a 43%. Isso ocorre porque ela armazena dados de forma mais compacta em nós de tamanho fixo, em vez de espalhar os nós pela memória como a skiplist fazia.
Quais operações do Valkey são impactadas pela fbtree?
Comandos que manipulam elementos em sorted sets, como ZADD e ZREM, devem apresentar ganhos de throughput. Operações de range, como ZRANGE, também se beneficiam da estrutura mais eficiente. Comandos que dependem apenas do hashtable, como ZSCORE e ZRANDMEMBER, não são significativamente impactados.
Preciso alterar meu código para usar o Valkey 9.2?
Não. O comportamento dos comandos de sorted sets permanece o mesmo. A única alteração visível é que OBJECT ENCODING retornará 'btree' em vez de 'skiplist' para sorted sets grandes. Se você tem monitoramento ou testes que verificam essa string, precisará atualizá-los.
Fontes
- valkey.iofonte original
- Categoria
- CEVIU Web Dev
- Publicado
- 17 de novembro de 2026
- Editoria
- CEVIU Web Dev
