Από το double hashing στην αρχιτεκτονική ενός hash

Τα bloom filters αποτελούν θεμελιώδη δομή δεδομένων για την αποφυγή περιττών αναζητήσεων σε δίσκο (disk IO). Ενώ η τεχνική double hashing (Kirsch-Mitzenmacher) μείωσε το κόστος υπολογισμού πολλαπλών hash, η ανάγκη για thread-safety εισήγαγε νέα προβλήματα. Σε συστήματα υψηλής κίνησης, όπως το backend του Bluesky, η χρήση mutexes για την προστασία των bloom filters αποδείχθηκε το κύριο σημείο συμφόρησης (bottleneck), αυξάνοντας τους χρόνους deployment από λεπτά σε ώρες.

Τεχνικές βελτιστοποίησης και cache alignment

Η μετάβαση σε One Hash Bloom Filters (OHBF) δεν προσφέρει μόνο υπολογιστική απλότητα, αλλά επιτρέπει και βαθύτερες βελτιστοποιήσεις σε επίπεδο hardware:

  • Cache-line alignment: Με τον διαχωρισμό του φίλτρου σε blocks των 64 bytes και τη χρήση unsafe για την ευθυγράμμιση στη μνήμη, διασφαλίζεται ότι κάθε lookup απαιτεί το ελάχιστο δυνατό cache miss.
  • Αποφυγή διαίρεσης: Η χρήση της τεχνικής του Daniel Lemire για την επιλογή block μέσω εντολών πολλαπλασιασμού (MUL) αντί για modulo (διαίρεση) επιταχύνει σημαντικά τη διαδικασία.
  • ShardedAtomicFilter: Η διανομή των εγγραφών σε πολλαπλά shards μειώνει το contention μεταξύ των threads, επιτρέποντας την πλήρη αξιοποίηση των bare metal servers χωρίς την ανάγκη για κλειδώματα (locks).

Συμπεράσματα για συστήματα υψηλής απόδοσης

Η εμπειρία από το Bluesky καταδεικνύει ότι, σε επίπεδο υποδομής, η επιλογή της δομής δεδομένων πρέπει να λαμβάνει υπόψη όχι μόνο την πολυπλοκότητα του αλγορίθμου, αλλά και τη συμπεριφορά του σε επίπεδο CPU cache και memory contention. Η υιοθέτηση ατομικών λειτουργιών και η προσεκτική διαχείριση της μνήμης αποτελούν κρίσιμους παράγοντες για την κλιμάκωση υπηρεσιών που διαχειρίζονται εκατομμύρια queries ανά δευτερόλεπτο.