bbtree macht die Skiplist in LSM-Trees bis zu 6,83-mal schneller
Bbtree: Fastest Ordered Map
Ein neuer B-Tree namens bbtree ersetzt die übliche Skiplist im Memtable von LSM-Trees und beschleunigt fjall, SlateDB, Tonbo und Lance um das 1,37- bis 6,83-Fache. Statt bei jedem Knoten einen Cache-Miss zu kassieren, berührt eine Suche nur wenige Cache-Lines. Inline-Keys und Prefix-Keys machen auch String-Schlüssel effizient, und ein Batch-Modus mit Rust-Async-State-Machines versteckt die Latenz von Cache-Misses.
In bbtree behandeln wir einen Cache-Miss als Future und awaiten ihn ebenfalls.
- geraneum
Produktionsreif durch formale Verifikation, Model Checking, deterministische Simulation, Fuzzing und jede Menge Tests.
Was bedeutet hier Model Checking?
- tyilo
Kein Mensch kann besseren Code schreiben als LLMs.
Kühne Behauptung...
- jared_hulbert
Sehr schöne Arbeit. Ich arbeite an Zeug... das dem hier wohl benachbart ist, schätze ich. Ich predige ständig die Ideen, dass wir viel eher zu Intrinsics greifen müssen, laserfokussiert auf die Cache Lines sein sollten, DRAM eher wie ein asynchrones Blockgerät behandeln sollten, aber ich kann nicht glauben, dass ich nicht daran gedacht habe, die Auswirkungen von Coherence-Traffic zu zeigen! Wenn ich etwas Zeit habe, versuche ich vielleicht, einige meiner Tricks auf bbtree anzuwenden. Schreib mir eine DM. Ich würde mich freuen, mich melden zu können, wenn es so weit ist.