Η αρχιτεκτονική προσέγγιση του bbtree
Το bbtree επαναπροσδιορίζει την υλοποίηση των ordered maps, εστιάζοντας στο μοντέλο κόστους του σύγχρονου υλικού. Σε αντίθεση με τα παραδοσιακά skiplists που κυριαρχούν στα memtables των LSM-trees, το bbtree βελτιστοποιεί τη χρήση της ιεραρχίας μνήμης (memory hierarchy), δίνοντας προτεραιότητα στη μείωση των cache misses, τα οποία αποτελούν το κύριο σημείο συμφόρησης (bottleneck) σε συστήματα υψηλής απόδοσης.
Βελτιστοποίηση μέσω inline keys και prefix compression
Η διαχείριση των keys, ειδικά όταν πρόκειται για String ή Vec<u8>, αποτελεί πρόκληση λόγω της αποθήκευσης στο heap. Το bbtree εισάγει την τεχνική των inline keys, όπου ένα σταθερό τμήμα του key αποθηκεύεται απευθείας στον κόμβο του B-tree. Σε συνδυασμό με τη χρήση prefix keys, το bbtree επιτυγχάνει:
- Δραστική μείωση των heap accesses κατά τη διάρκεια της αναζήτησης.
- Αποτελεσματικότερη χρήση του cache line, καθώς περισσότερα keys χωρούν σε έναν κόμβο.
- Δυνατότητα χρήσης SIMD οδηγιών για ταχύτερες συγκρίσεις.
Ασύγχρονη απόκρυψη λανθανόντος χρόνου (latency hiding)
Μια από τις πιο ενδιαφέρουσες αρχιτεκτονικές επιλογές του bbtree είναι η χρήση των async state machines της Rust για την επεξεργασία batch αιτημάτων. Αντιμετωπίζοντας κάθε cache miss ως ένα Future, το σύστημα μπορεί να εκτελεί πολλαπλές αναζητήσεις παράλληλα. Όταν μια αναζήτηση περιμένει δεδομένα από τη μνήμη, ο επεξεργαστής μεταβαίνει σε άλλη εργασία, μεγιστοποιώντας το throughput χωρίς την ανάγκη για ένα βαρύ runtime όπως το tokio, χρησιμοποιώντας έναν εξαιρετικά ελαφρύ, custom executor.
Συμπεράσματα για συστήματα παραγωγής
Το bbtree δεν αποτελεί απλώς μια ταχύτερη δομή δεδομένων, αλλά μια ολοκληρωμένη λύση για συστήματα που απαιτούν χαμηλό latency και υψηλή προβλεψιμότητα. Η ικανότητά του να αντικαθιστά υπάρχουσες δομές (όπως τα skiplists) χωρίς αλλαγές στο API, σε συνδυασμό με την προσεκτική διαχείριση μνήμης, το καθιστά ιδανικό για βάσεις δεδομένων, συστήματα RAG και εφαρμογές LLM.