Artikel teilen

Das Valkey-Team ersetzt in Version 9.2 die Skiplist hinter großen Sorted Sets durch einen B+-Baum. Der Speicheraufwand für die Sortierung sinkt je Eintrag um 36 bis 43 %, gemessen mit 5 Millionen Einträgen. Das Aktualisieren von Punktwerten mit ZADD läuft in den Tests mehr als doppelt so schnell.

Ein Klick · kostenlosDr. Web bei Google bevorzugenMarkieren Sie drweb.de als bevorzugte Quelle. Dann sehen Sie unsere Artikel öfter unter den Top-Meldungen.Jetzt hinzufügen
Inhalt 4 Abschnitte
  1. Warum kostet die Skiplist so viel Speicher?
  2. Was macht der B+-Baum anders?
  3. Was sollten Betreiber vor dem Umstieg prüfen?
  4. Mehr Newshunger?

Das Team hinter der Open-Source-Datenbank Valkey hat am 16. November in seinem Blog beschrieben, wie die Version 9.2 große Sorted Sets verwaltet.[1] Statt der Skiplist ordnet ein B+-Baum namens fbtree die Einträge. Die Version 9.2 steht als Testversion bereit, die Befehle bleiben unverändert.[1]

Auf einen Blick

Das Wichtigste in Kürze

  • Der Speicheraufwand für die Ordnung sinkt von 50,3 Byte je Eintrag auf 28,5 Byte beim fortlaufenden und 32,0 Byte beim zufälligen Einfügen.[1]
  • Das Team misst bis zu 105 % mehr Durchsatz bei ZADD und 76 % mehr bei ZREM. ZSCORE und ZPOPMIN ändern sich kaum.[1]
  • Nur der Befehl OBJECT ENCODING meldet für große Sorted Sets jetzt btree statt skiplist.[1]

Warum kostet die Skiplist so viel Speicher?

Weißer Würfel-Baum mit Anhänger „61 pro Knoten“ und Wollknäuel auf weißem Grund
Sorted Sets in Valkey nutzen Hashtabelle und Skiplist. Jeder Eintrag benötigt etwa 37 Byte für Zeiger, Spannweiten und Punktwert

Ein Sorted Set hält Einträge nach Punktwert geordnet, etwa für Ranglisten oder Warteschlangen mit Priorität. Große Sets bestehen in Valkey aus einer Hashtabelle für den Zugriff per Name und einer Skiplist für die Reihenfolge.[1] Jeder Eintrag sitzt dort in einem eigenen Knoten, der rund 37 Byte für Zeiger, Spannweiten und Punktwert braucht, noch ohne den Namen des Eintrags.[1]

Die Knoten liegen verstreut im Speicher, deshalb wartet der Prozessor bei jedem Suchschritt auf den Arbeitsspeicher. Ein solcher Zugriff dauert nach Angaben des Teams rund 100 Nanosekunden, ein Treffer im Cache etwa eine.[1] Eine Studie von 2025, auf die das Team verweist, zählte bei Skiplists das 2,4- bis 4,8-Fache an Cache-Fehlzugriffen gegenüber einem vergleichbaren B-Baum, an anderen Implementierungen als Valkey.[1]

Was macht der B+-Baum anders?

Der fbtree packt bis zu 61 Einträge in einen Knoten und speichert Punktwert und Name zusammen.[1] Die Skiplist verzweigt im Schnitt etwa vierfach, der Baum 61-fach. Das sind weniger Ebenen und weniger Zugriffe auf den Arbeitsspeicher.[1]

Dank vier Byte langer Merkmale findet der Baum den richtigen Zweig oft, ohne den Knoten zu laden.[1] Die Blätter sind verkettet, deshalb laufen Bereichsabfragen wie ZRANGE von Blatt zu Blatt.[1]

Sorted Sets in Valkey 9.2
Messwerte des Valkey-Teams zum neuen B+-Baum fbtree
43 %
Weniger Speicheraufwand je Eintrag bei fortlaufendem Einfügen, 36 % bei zufälligem
109 MB
Eingespart bei 5 Millionen Einträgen, 92 MB bei zufälliger Reihenfolge
+105 %
Durchsatz bei ZADD mit aktualisiertem Punktwert, gemessen an 3 Millionen Einträgen
Mehr Durchsatz je Befehl
ZADD +105 %
Punktwert eines vorhandenen Eintrags aktualisieren
ZREM +76 %
Zufällig hinzufügen und entfernen im Wechsel
ZCOUNT +27 %
Einträge in einem Punktbereich zählen
ZRANK +19 %
Rang eines Eintrags nachschlagen

Valkey spart Speicher, ohne dass Anwender einen Befehl ändern müssen. Genau das macht den Test mit eigenen Daten so billig.

Markus Seyfferth, Chefredakteur Dr. Web
Zitat teilen

Was sollten Betreiber vor dem Umstieg prüfen?

Valkey entstand am 28. März 2024 unter dem Dach der Linux Foundation als Fork von Redis 7.2.4, nachdem Redis die Lizenz geändert hatte. Das Projekt steht unter der BSD-Lizenz, Amazon Web Services, Google Cloud, Oracle, Ericsson und Snap unterstützen es.[2] Der Beitrag stammt von Rain Valentine von AWS und Dragos Andriciuc von Percona. Valentine hat nach eigener Angabe auch die Hashtabelle des Kerns und die Speicherung von Strings überarbeitet.[1]

Die Durchsatzwerte hat das Team auf einem Graviton3-Server mit 64 Kernen an einem Vorläuferstand gemessen und nicht erneut an der veröffentlichten Fassung.[1] Auch der Speichergewinn betrifft nur den Index: Er schrumpft im Verhältnis zum Gesamtspeicher, je länger die Namen der Einträge sind.[1]

Betreiber eigener Valkey-Server testen die Vorabversion mit einer Kopie ihrer Last, vor allem mit ZADD, ZREM, ZRANK und ZCOUNT.[1] Monitoring und Tests, die nach dem Text skiplist suchen, müssen btree erkennen.[1]

Der WordPress-Hoster Rackspeed nutzt Valkey als Object- und Session-Store. Bei solchen Tarifen bestimmt der Hoster, wann 9.2 kommt, und ein reiner Schlüssel-Wert-Cache braucht keine Sorted Sets. Wie sich Hoster unterscheiden, zeigt der WordPress-Hosting-Vergleich. Einen tiefen Eingriff bringt auch PostgreSQL 19, am 19. November erschienen: Der neue Befehl REPACK verkleinert aufgeblähte Tabellen, ohne dass Lese- und Schreibzugriffe warten müssen.

Quellen

2 Quellen anzeigenQuellen ausblenden
  1. ValkeyFrom Skiplists to B+ Trees: Making Valkey Sorted Sets More Memory Efficient16.11.2026
  2. Linux FoundationLinux Foundation Launches Open Source Valkey Community28.03.2024

Mehr Newshunger?

4,4 17 Bewertungen

Wie hat Ihnen dieser Artikel gefallen?

Dr. Web Newsletter

Jede Woche ein bisschen klüger.

Der Dr. Web Newsletter: die besten Artikel, Anbieter-Tipps und neue Tools, kompakt zusammengefasst, jeden Donnerstag. Kostenlos und jederzeit abbestellbar.