Valkey fa occupare meno RAM ai grandi sorted set
Valkey 9.2 sostituisce la skiplist dei grandi sorted set con un albero B+. Nei test del progetto l’overhead per elemento cala del 36–43%; comandi invariati e versione ancora in release candidate.
Che succede
In Valkey, il database in memoria, un sorted set può spendere più spazio per tenere ordinati gli elementi che per conservarne il contenuto. Questi insiemi associano a ogni voce un punteggio e permettono di leggerle in ordine: è una struttura adatta, per esempio, a una classifica. Valkey 9.2 sostituisce la skiplist dei grandi sorted set con fbtree, una variante degli alberi B+. I comandi restano gli stessi; cambia come i dati vengono organizzati in RAM.
La skiplist assegna a ogni elemento un nodo separato, con puntatori verso gli altri nodi. Oltre allo spazio occupato dai collegamenti, c’è il costo di seguirli: trovare il prossimo elemento può richiedere un altro accesso alla memoria. fbtree raccoglie invece fino a 61 riferimenti agli elementi nella stessa foglia da 512 byte. Molti elementi condividono la struttura, e la CPU può lavorare su dati vicini anziché inseguire tanti indirizzi sparsi.
Nel test pubblicato dal progetto, con cinque milioni di elementi da 20 byte, l’overhead per elemento scende da 50,3 a 28,5 byte con inserimenti sequenziali, oppure a 32 byte con inserimenti casuali. Sono riduzioni del 43% e del 36% nella memoria aggiuntiva necessaria alla struttura, escluso il contenuto degli elementi: circa 109 o 92 MB risparmiati in quel test. Con valori più grandi, lo stesso risparmio per voce incide meno sulla memoria totale.
Anche i tempi di lavoro possono beneficiarne. Nei benchmark del progetto, ZADD per aggiornare punteggi e ZREM nel carico misto di aggiunte e rimozioni guadagnano rispettivamente il 105% e il 76% di throughput. Altri comandi cambiano pochissimo. Queste misure vengono da un ramo della pull request su Graviton3 e non sono state ripetute sul commit integrato.
Valkey 9.2 è ancora in release candidate. I piccoli sorted set conservano la rappresentazione compatta listpack, quindi non sono coinvolti. Per quelli grandi, la differenza visibile dall’esterno è OBJECT ENCODING: restituisce btree al posto di skiplist. È l’unico nome da cambiare negli strumenti che controllano esplicitamente quella codifica.
Perché conta
Un sorted set pieno di valori minuscoli paga la propria contabilità milioni di volte. Condividere un nodo fra molte voci rende quel costo meno ingombrante: Valkey recupera RAM dall’organizzazione dei dati, senza chiedere all’applicazione di rinunciare a contenuti o comandi.
Leggi le fonti
Valkey — struttura, test e limiti di fbtreeValkey — implementazione nella pull request 4206Vuoi sapere di più su pillole come questa?