Valkey 9.2 substitui skiplist por B+ tree e reduz memória de sorted sets em até 43%

- Leitura
- 5 min
- Tabelas
- 1
- Fontes
- 1
A versão 9.2, em fase de release candidate, troca a estrutura interna que ordena sorted sets por uma B+ tree chamada fbtree. O resultado: menos memória por membro e comandos como ZADD e ZREM bem mais rápidos.
Quem roda Valkey (o fork open source↳Open source71 conteúdosComo o Open Source Está Liberando o Poder da Automação para TodosDev (Back & Front) · out 2025Código aberto: programadores criam software da NASA sem saberDev (Back & Front) · abr 2021N8N: O que é a ferramenta open source que está revolucionando a automação em TI?Dev (Back & Front) · dez 2025Ver tudo em Dev (Back & Front) → do Redis mantido pela Linux↳Linux34 conteúdosKali Linux em um Servidor VPS: como, quando e por que usar?DevSecOps · dez 2024Construindo um Windows Service ou Linux Daemon com Worker Service & .NET Core – Parte 2Dev (Back & Front) · jul 2020Criando uma WebApi utilizando .NET, Linux e VSCodeDev (Back & Front) · ago 2019Ver tudo em DevSecOps → Foundation) com sorted sets grandes em produção vai sentir uma mudança de bastidores na versão 9.2, hoje em fase de release candidate. Num post técnico publicado em 16 de novembro de 2026, os engenheiros Rain Valentine e Dragos Andriciuc detalham a troca da skiplist, estrutura usada desde sempre para ordenar sorted sets, por uma variante de B+ tree batizada de fbtree.
A mudança é interna e não altera a API: ZADD, ZRANGE, ZSCORE e companhia continuam funcionando exatamente como antes. Mas quem opera sorted sets grandes em memória vai perceber dois efeitos práticos: menos RAM consumida por membro armazenado e ganhos de throughput relevantes em operações de escrita.
Por que a skiplist pesava tanto
Sorted sets grandes (acima do limite de listpack) sempre usaram uma combinação de hashtable, para buscas por membro em O(1), com uma skiplist, para buscas ordenadas por rank ou score em O(log n). O problema é que a skiplist é uma estrutura probabilística: cada nó tem 25% de chance de ganhar mais um nível, o que dá um fator de ramificação efetivo de apenas 4.
Na prática, isso significa um ponteiro de retrocesso (8 bytes), em média 1,33 níveis de ponteiros e valores de span (cerca de 29 bytes) e o score (8 bytes) por nó, somando algo em torno de 37 bytes de overhead puro antes mesmo de contar a string do membro. Pior: cada nó é uma alocação separada, espalhada pela heap, e seguir a estrutura exige uma sequência de acessos dependentes de memória, cada um potencialmente um cache miss.
O post cita um estudo de 2025 sobre índices concorrentes em memória que mediu skiplists tradicionais com 2,4 a 4,8 vezes mais cache misses que uma B-tree comparável, com throughput de 2 a 8 vezes menor nos workloads testados (não é um teste do Valkey, mas ilustra o problema estrutural).
fbtree: fanout alto, menos saltos de memória
A fbtree usa fanout de 61, ou seja, cada nó guarda até 61 entradas ou ponteiros filhos, contra o fator 4 efetivo da skiplist. Isso reduz drasticamente o número de níveis a percorrer numa busca e, principalmente, o número de saltos de memória dependentes entre si.
Três decisões de design sustentam o ganho:
- Dados compactos: nós folha de 512 bytes cabem em até 61 ponteiros de valor, e cada entrada guarda score e membro juntos, num único valor empacotado, eliminando um nível de indireção.
- Busca via SIMD: nós internos guardam um "feature" de 4 bytes por filho (derivado do prefixo do membro), permitindo comparar vários candidatos em paralelo via SIMD antes mesmo de buscar o nó filho na memória.
- Folhas encadeadas: os nós folha formam uma lista duplamente ligada, então comandos de range como
ZRANGEpercorrem o conjunto sem subir e descer a árvore a cada passo, e a leitura pode avançar para a próxima folha enquanto processa as 61 entradas atuais.
Para operações nas pontas do conjunto, como ZPOPMIN, a fbtree mantém cache das folhas mais à esquerda e à direita, preservando acesso O(1) como na skiplist, em vez de regredir para O(log n).
Os números: memória e throughput
No teste de referência, inserir 5 milhões de membros de 20 bytes reduziu o overhead por membro (sem contar o dado em si) de 50,3 bytes para 28,5 bytes em inserção sequencial, uma queda de 43%, e para 32 bytes em inserção aleatória, uma queda de 36%. Em termos absolutos, isso representa até 109 MB economizados no conjunto de 5 milhões de membros com inserção sequencial, e 92 MB com inserção aleatória.
Os benchmarks de comando, rodados numa instância Graviton3 c7g.metal com 64 cores, nove threads de I/O e um sorted set de 3 milhões de membros, mostram ganhos de throughput desiguais entre comandos:
| Comando | Workload | Ganho de throughput |
|---|---|---|
| ZADD | Atualização de score | +105% |
| ZREM | Add/remove aleatório 50/50 | +76% |
| ZCOUNT | Contagem por faixa de score | +27% |
| ZRANK | Busca de rank pontual | +19% |
| ZRANGE | Varredura de 100 elementos por rank | +6% |
| ZRANDMEMBER | 100 amostras aleatórias | +2% |
| ZSCORE | Busca de score pontual | +2% |
| ZRANGEBYSCORE | Varredura de 100 elementos por score | +1% |
| ZPOPMIN | Pop + append | ~0% |
O padrão faz sentido: ZADD e ZREM reposicionam elementos na árvore, então se beneficiam diretamente da estrutura mais rasa e com menos atualizações de ponteiro. Já ZSCORE e ZRANDMEMBER praticamente não mudam porque dependem da hashtable, não do índice ordenado, que foi o único componente trocado.
O que muda para quem opera em produção
Para quem administra instâncias Valkey com sorted sets grandes (filas de prioridade, leaderboards, rate limiting por score, índices de proximidade), a conta é direta: menos RAM por conjunto significa mais conjuntos cabendo na mesma instância, ou a possibilidade de rodar com menos memória alocada. O ganho relativo é maior em sets com muitos membros pequenos e encolhe à medida que o tamanho médio do membro cresce.
Há um ponto de atenção operacional: o comando OBJECT ENCODING passa a retornar btree em vez de skiplist para sorted sets grandes. Qualquer monitoramento, teste automatizado ou ferramenta de observabilidade que faça match literal na string skiplist precisa ser atualizado antes da migração. Sorted sets pequenas, que já usavam a representação listpack, não são afetadas de forma alguma.
Vale lembrar que os benchmarks de comando foram medidos numa branch de pull request (PR #4206) e não foram re-executados contra o commit final que foi mergeado, então os números de throughput servem como ordem de grandeza, não como garantia contratual para qualquer workload.
O que ainda está em aberto
Valkey 9.2 segue em fase de release candidate, sem data de GA (general availability) divulgada na fonte. A recomendação da própria equipe é testar o RC com workload real antes do lançamento final, principalmente se sorted sets grandes ou os comandos ZADD, ZREM, ZRANK ou ZCOUNT forem críticos para a aplicação, e reportar problemas encontrados via issue no GitHub do projeto.
Para quem já roda Redis ou Valkey em produção com sorted sets pesadas, o caminho natural é subir um ambiente de staging com o RC, repetir a carga de trabalho típica e comparar memória residente e latência de ZADD/ZREM antes e depois da troca de encoding, em vez de confiar apenas nos números publicados no post.
Fonte: Hacker News
Highlights
- Valkey 9.2 substitui skiplist por fbtree em sorted sets grandes; reduz overhead por membro em até 43%
- Benchmarks mostram ganhos de throughput de +105% em ZADD e +76% em ZREM; economiza até 109 MB em 5 milhões de membros
- OBJECT ENCODING passa a retornar 'btree' em vez de 'skiplist'; monitoramento precisará ser atualizado
- Versão 9.2 está em release candidate; recomendação é testar em staging antes da migração
- Comandos que dependem da hashtable (ZSCORE, ZRANDMEMBER) têm ganho mínimo pois só o índice ordenado foi trocado
Este artigo foi escrito por Redação iMasters. Conteúdo produzido por agente de IA da redação iMasters, sob revisão editorial humana. Saiba como produzimos no expediente.
Apple contrata engenheiros para construir seu próprio agente de IA
Vaga de emprego identificada pela Bloomberg mostra que a Apple busca um engenheiro para liderar um agente capaz de navegar na web, operar entre apps e até escrever código, entrando na disputa com Meta, OpenAI, Anthropic e Google.













