📻 Versión en audio: si prefieres escuchar en vez de leer, el resumen del artÃculo está justo aquà arriba.
Si tienes un Valkey o un Redis corriendo como caché en tu VPS, hay una pregunta incómoda que casi nadie se hace: ¿cuánta RAM estás pagando solo por mantener los datos ordenados? Los datos son una cosa, la estructura que sigue la cuenta es otra, y esa estructura escondÃa un impuesto que Valkey 9.2 acaba de eliminar.
El equipo de Valkey enterró la skiplist, la estructura que ordenaba los sorted sets desde hace tres décadas, y la reemplazó por un B+ tree afinado para ese caso, bautizado fbtree. La motivación es honesta y brutal: en un sorted set grande, se gastaba más memoria describiendo el orden de los elementos que guardando los elementos mismos. En un test con 5 millones de miembros de 20 bytes, la sobrecarga por elemento cayó de 50,3 a 28,5 bytes con inserciones secuenciales: un corte de 43%, unos 109 MB ahorrados en ese solo test. Con inserciones aleatorias, como pasa en la vida real, la baja es de 36%, unos 92 MB. Nada mal para un cambio que no toca ni una sola clase de comando.
Por qué la skiplist gastaba tanto
La skiplist es elegante en papel: una lista enlazada con niveles probabilÃsticos que te da búsqueda O(log n). El problema es fÃsico. Cada nodo era una asignación aparte en el heap, regada por donde el allocator quisiera, cargando punteros de niveles y spans: alrededor de 37 bytes de sobrecarga por miembro antes de contar el dato mismo, unos 50 bytes reales. Peor para el CPU: cada salto entre nodos es una lectura a RAM potencialmente en otra cacheline, y esas lecturas son dependientes, asà que el core queda esperando. Un estudio de 2025 sobre Ãndices en memoria midió que una skiplist clásica sufre entre 2,4 y 4,8 veces más cache misses que un B-tree comparable.
La solución de Valkey empaca cada hoja en un nodo de 512 bytes con fanout de 61 entradas, guarda score y miembro juntos como un valor binario, y le agrega un truco fino: los nodos internos separan el prefijo común de los anclas y comparan 4 bytes de «feature» con SIMD para elegir el hijo correcto sin ir a buscar el string completo. Las hojas van enlazadas como lista doble, asà que ZRANGE camina secuencial sin volver a subir al árbol.
Lo que cambia (y no cambia) para ti
Funcionalmente, nada. Los sorted sets chicos, bajo el umbral de listpack, ni se enteran: nunca usaron skiplist. El único detalle visible es que OBJECT ENCODING ahora devuelve btree en vez de skiplist para sets grandes, y si tienes un dashboard o un test que compara contra ese string literal, se cayó. Revisa tus grep.
En rendimiento, los que reposicionan elementos son los que se llevan el premio: ZADD sube 105% y ZREM 76% de throughput, con ZCOUNT a +27% y ZRANK a +19%, medidos sobre un set de 3 millones de miembros en un Graviton3. Los comandos que pasan por la hashtable tipo ZSCORE ni se mueven, lo cual es coherente: el cambio es en el Ãndice ordenado, no en la tabla.
Valkey 9.2 está en release candidates y todavÃa no llega al GA. Mi consejo, habiendo aprendido a cachear de todo en estos años: si tus sorted sets son el corazón de rankings, feeds o contadores, bájate la RC y corre tu carga real antes de actualizar con auto-update, no el benchmark del blog. Y si tu VPS lleva meses con el RSS del caché creciendo sin explicación aparente, este cambio es exactamente la explicación que no encontrabas.
A mà me caló hondo el detalle metodológico: antes de mergear, corrieron fbtree contra la skiplist dentro del servidor completo y optimizaron hasta empatar o superar en todos los comandos. Eso es ingenierÃa seria, no un benchmark de vitrina. Reemplazar una estructura de 1990 porque la jerarquÃa de cachés de los CPU modernos cambió el terreno de juego es justo la clase de mantenimiento silencioso que después hace tu servidor más barato.
Fuente: From Skiplists to B+ Trees: Making Valkey Sorted Sets More Memory Efficient, del blog oficial de Valkey.
Fuente de inspiración: From Skiplists to B+ Trees: Making Valkey Sorted Sets More Memory Efficient
