εισαγωγή
Έδωσα αυτή την έκθεση στα αγγλικά στο συνέδριο Gophercon Russia 2019 στη Μόσχα και στα ρωσικά σε μια συνάντηση στο Nizhny Novgorod. Μιλάμε για έναν δείκτη Bitmap - λιγότερο κοινό από το B -Tree, αλλά όχι λιγότερο ενδιαφέρον. Μοιρασιά ομιλίες στο συνέδριο στα αγγλικά και μεταγραφές κειμένων στα ρωσικά.
Θα εξετάσουμε πώς λειτουργεί ένα ευρετήριο bitmap, πότε είναι καλύτερο, πότε είναι χειρότερο από άλλα ευρετήρια και σε ποιες περιπτώσεις είναι σημαντικά ταχύτερο από αυτούς. Ας δούμε ποια δημοφιλή DBMS έχουν ήδη ευρετήρια bitmap. Ας προσπαθήσουμε να γράψουμε το δικό μας στο Go. Και «για επιδόρπιο» θα χρησιμοποιήσουμε έτοιμες βιβλιοθήκες για να δημιουργήσουμε τη δική μας εξαιρετικά γρήγορη εξειδικευμένη βάση δεδομένων.
Ελπίζω πραγματικά ότι τα έργα μου θα είναι χρήσιμα και ενδιαφέροντα για εσάς. Πηγαίνω!
Εισαγωγή
Γεια σε όλους! Η ώρα είναι έξι το βράδυ και είμαστε όλοι πολύ κουρασμένοι. Καλή στιγμή να μιλήσουμε για τη βαρετή θεωρία ευρετηρίου βάσης δεδομένων, σωστά; Μην ανησυχείτε, θα έχω μερικές γραμμές πηγαίου κώδικα εδώ κι εκεί. 🙂
Πέρα από όλα τα αστεία, η αναφορά είναι γεμάτη πληροφορίες και δεν έχουμε πολύ χρόνο. Ας ξεκινήσουμε λοιπόν.
Σήμερα θα μιλήσω για τα εξής:
- τι είναι τα ευρετήρια?
- τι είναι ένας δείκτης bitmap;
- που χρησιμοποιείται και που ΔΕΝ χρησιμοποιείται και γιατί?
- Απλή υλοποίηση στο Go και λίγο αγώνα με τον μεταγλωττιστή.
- ελαφρώς λιγότερο απλή, αλλά πολύ πιο παραγωγική εφαρμογή στο Go assembler.
- "Προβλήματα" των ευρετηρίων bitmap.
- υπάρχουσες υλοποιήσεις.
Τι είναι λοιπόν οι δείκτες;
Το ευρετήριο είναι μια ξεχωριστή δομή δεδομένων που διατηρούμε και ενημερώνουμε εκτός από τα κύρια δεδομένα. Χρησιμοποιείται για την επιτάχυνση της αναζήτησης. Χωρίς ευρετήρια, η αναζήτηση θα απαιτούσε την πλήρη διέλευση των δεδομένων (μια διαδικασία που ονομάζεται πλήρης σάρωση) και αυτή η διαδικασία έχει γραμμική αλγοριθμική πολυπλοκότητα. Αλλά οι βάσεις δεδομένων συνήθως περιέχουν τεράστιες ποσότητες δεδομένων και η γραμμική πολυπλοκότητα είναι πολύ αργή. Στην ιδανική περίπτωση, θα παίρναμε λογαριθμικό ή σταθερό.
Αυτό είναι ένα εξαιρετικά περίπλοκο θέμα, γεμάτο με λεπτές αποχρώσεις και συμβιβασμούς, αλλά μετά από δεκαετίες ανάπτυξης και έρευνας βάσεων δεδομένων, είμαι πρόθυμος να πω ότι υπάρχουν μόνο μερικές ευρέως χρησιμοποιούμενες προσεγγίσεις για τη δημιουργία ευρετηρίων βάσεων δεδομένων.
Η πρώτη προσέγγιση είναι η ιεραρχική μείωση του χώρου αναζήτησης, διαιρώντας τον χώρο αναζήτησης σε μικρότερα μέρη.
Συνήθως το κάνουμε αυτό χρησιμοποιώντας διαφορετικούς τύπους δέντρων. Ένα παράδειγμα θα ήταν ένα μεγάλο κουτί με υλικά στην ντουλάπα σας που περιέχει μικρότερα κουτιά με υλικά χωρισμένα σε διαφορετικά θέματα. Αν χρειάζεστε υλικά, πιθανότατα θα τα ψάξετε σε ένα κουτί που γράφει "Υλικά" αντί για "Cookies", σωστά;
Η δεύτερη προσέγγιση είναι να επιλέξετε αμέσως το επιθυμητό στοιχείο ή ομάδα στοιχείων. Αυτό το κάνουμε σε χάρτες κατακερματισμού ή αντίστροφα ευρετήρια. Η χρήση χαρτών κατακερματισμού μοιάζει πολύ με το προηγούμενο παράδειγμα, αλλά αντί για ένα κουτί κουτιών, έχετε ένα σωρό μικρά κουτιά με τελικά αντικείμενα στην ντουλάπα σας.
Η τρίτη προσέγγιση είναι η εξάλειψη της ανάγκης για αναζήτηση. Το κάνουμε αυτό χρησιμοποιώντας φίλτρα άνθισης ή φίλτρα κούκου. Οι πρώτοι δίνουν μια απάντηση αμέσως, εξοικονομώντας σας από την ανάγκη αναζήτησης.
Η τελευταία προσέγγιση είναι να αξιοποιήσουμε πλήρως όλη τη δύναμη που μας δίνει το σύγχρονο υλικό. Αυτό ακριβώς κάνουμε στα ευρετήρια bitmap. Ναι, όταν τα χρησιμοποιούμε, μερικές φορές χρειάζεται να εξετάσουμε ολόκληρο το ευρετήριο, αλλά το κάνουμε εξαιρετικά αποτελεσματικά.
Όπως είπα, το θέμα των ευρετηρίων βάσεων δεδομένων είναι τεράστιο και γεμάτο συμβιβασμούς. Αυτό σημαίνει ότι μερικές φορές μπορούμε να χρησιμοποιήσουμε πολλές προσεγγίσεις ταυτόχρονα: εάν πρέπει να επιταχύνουμε ακόμη περισσότερο την αναζήτηση ή εάν πρέπει να καλύψουμε όλους τους πιθανούς τύπους αναζήτησης.
Σήμερα θα μιλήσω για την λιγότερο γνωστή προσέγγιση αυτών - τα ευρετήρια bitmap.
Ποιος είμαι εγώ για να μιλήσω για αυτό το θέμα;
Εργάζομαι ως επικεφαλής ομάδας στο Badoo (ίσως είστε πιο εξοικειωμένοι με το άλλο προϊόν μας, το Bumble). Έχουμε ήδη περισσότερους από 400 εκατομμύρια χρήστες σε όλο τον κόσμο και πολλές λειτουργίες που επιλέγουν την καλύτερη αντιστοιχία για αυτούς. Αυτό το κάνουμε χρησιμοποιώντας προσαρμοσμένες υπηρεσίες, συμπεριλαμβανομένων ευρετηρίων bitmap.
Τι είναι λοιπόν ένας δείκτης bitmap;
Τα ευρετήρια bitmap, όπως υποδηλώνει το όνομα, χρησιμοποιούν bitmaps ή bitset για την υλοποίηση ενός ευρετηρίου αναζήτησης. Από την οπτική γωνία, αυτό το ευρετήριο αποτελείται από έναν ή περισσότερους τέτοιους bitmaps που αντιπροσωπεύουν τυχόν οντότητες (όπως άτομα) και τις ιδιότητες ή τις παραμέτρους τους (ηλικία, χρώμα ματιών, κ.λπ.) και έναν αλγόριθμο που χρησιμοποιεί πράξεις bit (AND, OR, NOT ) για να απαντήσετε στο ερώτημα αναζήτησης.
Μας είπαν ότι τα ευρετήρια bitmap ταιριάζουν καλύτερα και έχουν πολύ καλή απόδοση για περιπτώσεις όπου υπάρχουν αναζητήσεις που συνδυάζουν ερωτήματα σε πολλές στήλες χαμηλής καρδιναικότητας (σκεφτείτε "χρώμα ματιών" ή "οικογενειακή κατάσταση" έναντι κάτι σαν "απόσταση από το κέντρο της πόλης" ). Αλλά θα δείξω αργότερα ότι λειτουργούν μια χαρά και για στήλες υψηλής καρδιναικότητας.
Ας δούμε το απλούστερο παράδειγμα ενός ευρετηρίου bitmap.
Φανταστείτε ότι έχουμε μια λίστα με εστιατόρια της Μόσχας με δυαδικές ιδιότητες όπως αυτές:
- κοντά στο μετρό?
- Υπάρχει ιδιωτικός χώρος στάθμευσης.
- υπάρχει βεράντα (έχει βεράντα).
- μπορείτε να κάνετε κράτηση τραπεζιού (δέχεται κρατήσεις).
- κατάλληλο για χορτοφάγους (φιλικό προς τους vegan).
- ακριβό (ακριβό).
Ας δώσουμε σε κάθε εστιατόριο έναν αριθμό σειράς που ξεκινά από το 0 και ας εκχωρήσουμε μνήμη για 6 bitmaps (ένα για κάθε χαρακτηριστικό). Στη συνέχεια, θα συμπληρώσουμε αυτούς τους bitmaps ανάλογα με το αν το εστιατόριο έχει αυτήν την ιδιοκτησία ή όχι. Εάν το εστιατόριο 4 έχει βεράντα, τότε το bit No. 4 στο bitmap "έχει βεράντα" θα οριστεί σε 1 (αν δεν υπάρχει βεράντα, τότε στο 0).
Τώρα έχουμε το απλούστερο δυνατό ευρετήριο bitmap και μπορούμε να το χρησιμοποιήσουμε για να απαντήσουμε σε ερωτήματα όπως:
- «Δείξε μου εστιατόρια φιλικά για χορτοφάγους»
- «Δείξε μου φθηνά εστιατόρια με βεράντα όπου μπορείς να κλείσεις τραπέζι».
Πως? Ας ρίξουμε μια ματιά. Το πρώτο αίτημα είναι πολύ απλό. Το μόνο που πρέπει να κάνουμε είναι να πάρουμε το "φιλικό για χορτοφάγους" bitmap και να το μετατρέψουμε σε μια λίστα με εστιατόρια των οποίων τα κομμάτια εκτίθενται.
Το δεύτερο αίτημα είναι λίγο πιο περίπλοκο. Πρέπει να χρησιμοποιήσουμε το NOT bitmap στο "ακριβό" bitmap για να λάβουμε μια λίστα με φθηνά εστιατόρια, στη συνέχεια ΚΑΙ με το bitmap "μπορώ να κλείσω τραπέζι" και ΚΑΙ το αποτέλεσμα με το bitmap "υπάρχει βεράντα". Το bitmap που προκύπτει θα περιέχει μια λίστα με εγκαταστάσεις που πληρούν όλα τα κριτήριά μας. Σε αυτό το παράδειγμα, αυτό είναι μόνο το εστιατόριο Yunost.
Υπάρχει πολλή θεωρία, αλλά μην ανησυχείτε, θα δούμε τον κωδικό πολύ σύντομα.
Πού χρησιμοποιούνται τα ευρετήρια bitmap;
Εάν κάνετε ευρετήρια bitmap στο Google, το 90% των απαντήσεων θα σχετίζεται με το Oracle DB με τον ένα ή τον άλλο τρόπο. Αλλά και άλλα DBMS πιθανώς υποστηρίζουν κάτι τέτοιο, σωστά; Όχι πραγματικά.
Ας δούμε τη λίστα των βασικών υπόπτων.
Η MySQL δεν υποστηρίζει ακόμη ευρετήρια bitmap, αλλά υπάρχει μια πρόταση που προτείνει την προσθήκη αυτής της επιλογής ().
Η PostgreSQL δεν υποστηρίζει ευρετήρια bitmap, αλλά χρησιμοποιεί απλά bitmaps και λειτουργίες bit για να συνδυάσει τα αποτελέσματα αναζήτησης σε πολλά άλλα ευρετήρια.
Το Tarantool έχει ευρετήρια bitset και υποστηρίζει απλές αναζητήσεις σε αυτά.
Το Redis έχει απλά bitfields) χωρίς τη δυνατότητα αναζήτησης τους.
Το MongoDB δεν υποστηρίζει ακόμη δείκτες bitmap, αλλά υπάρχει επίσης μια πρόταση που υποδηλώνει ότι αυτή η επιλογή θα προστεθεί
Το Elasticsearch χρησιμοποιεί εσωτερικά bitmaps).
- Αλλά ένας νέος γείτονας εμφανίστηκε στο σπίτι μας: ο Pilosa. Αυτή είναι μια νέα μη σχεσιακή βάση δεδομένων γραμμένη στο Go. Περιέχει μόνο ευρετήρια bitmap και βασίζει τα πάντα σε αυτούς. Θα το συζητήσουμε λίγο αργότερα.
Υλοποίηση στο Go
Αλλά γιατί τα ευρετήρια bitmap χρησιμοποιούνται τόσο σπάνια; Πριν απαντήσω σε αυτήν την ερώτηση, θα ήθελα να σας δείξω πώς να εφαρμόσετε ένα πολύ απλό ευρετήριο bitmap στο Go.
Τα bitmaps είναι ουσιαστικά απλώς κομμάτια δεδομένων. Στο Go, ας χρησιμοποιήσουμε κομμάτια byte για αυτό.
Έχουμε ένα bitmap για ένα χαρακτηριστικό εστιατορίου και κάθε bit στο bitmap υποδεικνύει εάν ένα συγκεκριμένο εστιατόριο έχει αυτήν την ιδιότητα ή όχι.
Θα χρειαστούμε δύο βοηθητικές λειτουργίες. Ένα θα χρησιμοποιηθεί για να γεμίσει τα bitmaps μας με τυχαία δεδομένα. Τυχαίο, αλλά με μια συγκεκριμένη πιθανότητα το εστιατόριο να έχει κάθε ακίνητο. Για παράδειγμα, πιστεύω ότι υπάρχουν πολύ λίγα εστιατόρια στη Μόσχα όπου δεν μπορείτε να κάνετε κράτηση για τραπέζι και μου φαίνεται ότι περίπου το 20% των εγκαταστάσεων είναι κατάλληλα για χορτοφάγους.
Η δεύτερη λειτουργία θα μετατρέψει το bitmap σε μια λίστα εστιατορίων.
Για να απαντήσουμε στο ερώτημα «Δείξε μου φθηνά εστιατόρια που έχουν αίθριο και μπορούν να κάνουν κρατήσεις», χρειαζόμαστε λειτουργίες δύο bit: ΟΧΙ και ΚΑΙ.
Μπορούμε να απλοποιήσουμε λίγο τον κώδικά μας χρησιμοποιώντας τον πιο περίπλοκο τελεστή ΚΑΙ ΟΧΙ.
Έχουμε λειτουργίες για κάθε μία από αυτές τις λειτουργίες. Και τα δύο περνούν από τις φέτες, παίρνουν τα αντίστοιχα στοιχεία από το καθένα, τα συνδυάζουν με μια λειτουργία bit και βάζουν το αποτέλεσμα στη φέτα που προκύπτει.
Και τώρα μπορούμε να χρησιμοποιήσουμε τα bitmaps και τις συναρτήσεις μας για να απαντήσουμε στο ερώτημα αναζήτησης.
Η απόδοση δεν είναι τόσο υψηλή, παρόλο που οι λειτουργίες είναι πολύ απλές και εξοικονομήσαμε πολλά χρήματα με το να μην επιστρέφουμε ένα νέο προκύπτον κομμάτι κάθε φορά που καλούνταν η συνάρτηση.
Αφού έκανα λίγο προφίλ με το pprof, παρατήρησα ότι από τον μεταγλωττιστή Go έλειπε μια πολύ απλή αλλά πολύ σημαντική βελτιστοποίηση: η λειτουργία inlining.
Το γεγονός είναι ότι ο μεταγλωττιστής Go φοβάται τρομερά τους βρόχους που περνούν από φέτες και αρνείται κατηγορηματικά να ενσωματώσει συναρτήσεις που περιέχουν τέτοιους βρόχους.
Αλλά δεν φοβάμαι και μπορώ να ξεγελάω τον μεταγλωττιστή χρησιμοποιώντας goto αντί για βρόχο, όπως στις παλιές καλές μέρες.
Και, όπως μπορείτε να δείτε, τώρα ο μεταγλωττιστής θα ενσωματώσει ευχαρίστως τη λειτουργία μας! Ως αποτέλεσμα, καταφέρνουμε να εξοικονομήσουμε περίπου 2 μικροδευτερόλεπτα. Καθόλου άσχημα!
Η δεύτερη συμφόρηση είναι εύκολο να δει αν κοιτάξετε προσεκτικά την έξοδο της συναρμολόγησης. Ο μεταγλωττιστής πρόσθεσε έναν έλεγχο ορίων φέτας δεξιά μέσα στο πιο καυτό βρόχο μας. Το γεγονός είναι ότι το GO είναι μια ασφαλής γλώσσα, ο μεταγλωττιστής φοβάται ότι τα τρία μου επιχειρήματα (τρεις φέτες) έχουν διαφορετικά μεγέθη. Μετά από όλα, τότε θα υπάρξει μια θεωρητική πιθανότητα της εμφάνισης μιας λεγόμενης υπερχείλισης buffer.
Ας καθησυχάσουμε τον μεταγλωττιστή δείχνοντας ότι όλες οι φέτες έχουν το ίδιο μέγεθος. Μπορούμε να το κάνουμε αυτό προσθέτοντας έναν απλό έλεγχο στην αρχή της λειτουργίας μας.
Βλέποντας αυτό, ο μεταγλωττιστής παραλείπει ευτυχώς τον έλεγχο και καταλήγουμε να εξοικονομούμε άλλα 500 νανοδευτερόλεπτα.
Big Butches
Εντάξει, καταφέραμε να αποσπάσουμε κάποια απόδοση από την απλή μας υλοποίηση, αλλά αυτό το αποτέλεσμα είναι στην πραγματικότητα πολύ χειρότερο από ό,τι είναι δυνατό με το τρέχον υλικό.
Το μόνο που κάνουμε είναι βασικές λειτουργίες bit και οι επεξεργαστές μας τις εκτελούν πολύ αποτελεσματικά. Όμως, δυστυχώς, «τροφοδοτούμε» τον επεξεργαστή μας με πολύ μικρά κομμάτια εργασίας. Οι συναρτήσεις μας εκτελούν λειτουργίες ανά byte. Μπορούμε πολύ εύκολα να τροποποιήσουμε τον κώδικά μας ώστε να λειτουργεί με κομμάτια 8 byte χρησιμοποιώντας slices UInt64.
Όπως μπορείτε να δείτε, αυτή η μικρή αλλαγή επιτάχυνε το πρόγραμμά μας οκτώ φορές αυξάνοντας το μέγεθος της παρτίδας κατά οκτώ φορές. Το κέρδος μπορούμε να πούμε ότι είναι γραμμικό.
Εφαρμογή σε assembler
Αυτό όμως δεν είναι το τέλος. Οι επεξεργαστές μας μπορούν να συνεργαστούν με κομμάτια 16, 32 και ακόμη και 64 bytes. Τέτοιες «ευρείς» λειτουργίες ονομάζονται πολλαπλά δεδομένα μιας εντολής (SIMD, μία εντολή, πολλά δεδομένα) και η διαδικασία μετασχηματισμού κώδικα ώστε να χρησιμοποιεί τέτοιες λειτουργίες ονομάζεται διανυσματική.
Δυστυχώς, ο μεταγλωττιστής Go απέχει πολύ από το να είναι εξαιρετικός στη διανυσματοποίηση. Επί του παρόντος, ο μόνος τρόπος για να διανυσματοποιήσετε τον κώδικα Go είναι να λάβετε και να πραγματοποιήσετε αυτές τις λειτουργίες με μη αυτόματο τρόπο χρησιμοποιώντας το assembler Go.
Ο Go assembler είναι ένα περίεργο θηρίο. Πιθανότατα γνωρίζετε ότι η γλώσσα assembly είναι κάτι που συνδέεται σε μεγάλο βαθμό με την αρχιτεκτονική του υπολογιστή για τον οποίο γράφετε, αλλά αυτό δεν συμβαίνει στο Go. Το Go assembler μοιάζει περισσότερο με IRL (ενδιάμεση γλώσσα αναπαράστασης) ή ενδιάμεση γλώσσα: είναι πρακτικά ανεξάρτητο από πλατφόρμα. Εξαιρετική εμφάνιση έδωσε ο Ρομπ Πάικ σχετικά με αυτό το θέμα πριν από αρκετά χρόνια στο GopherCon στο Ντένβερ.
Επιπλέον, το Go χρησιμοποιεί μια ασυνήθιστη μορφή Plan 9, η οποία διαφέρει από τις γενικά αποδεκτές μορφές AT&T και Intel.
Είναι ασφαλές να πούμε ότι το να γράφεις το Go assembler με το χέρι δεν είναι ό,τι πιο διασκεδαστικό.
Αλλά, ευτυχώς, υπάρχουν ήδη δύο εργαλεία υψηλού επιπέδου που μας βοηθούν να γράψουμε το Go assembler: το PeachPy και το avo. Και οι δύο επιχειρήσεις κοινής ωφέλειας δημιουργούν συναρμολογητή GO από κώδικα υψηλότερου επιπέδου γραμμένο στο Python και Go, αντίστοιχα.
Αυτά τα βοηθητικά προγράμματα απλοποιούν πράγματα όπως η κατανομή καταχωρήσεων, οι βρόχοι γραφής και γενικά απλοποιούν τη διαδικασία εισόδου στον κόσμο του προγραμματισμού συναρμολόγησης στο Go.
Θα χρησιμοποιήσουμε το avo, επομένως τα προγράμματά μας θα είναι σχεδόν κανονικά προγράμματα Go.
Αυτό είναι το απλούστερο παράδειγμα ενός προγράμματος avo. Έχουμε μια συνάρτηση main(), η οποία ορίζει μέσα της τη συνάρτηση Add(), η έννοια της οποίας είναι να προσθέτουμε δύο αριθμούς. Υπάρχουν βοηθητικές συναρτήσεις εδώ για να λάβετε τις παραμέτρους με το όνομα και να αποκτήσετε έναν από τους δωρεάν και κατάλληλους καταχωρητές επεξεργαστή. Κάθε λειτουργία επεξεργαστή έχει μια αντίστοιχη λειτουργία on avo, όπως φαίνεται στο ADDQ. Τέλος, βλέπουμε μια βοηθητική συνάρτηση για την αποθήκευση της τιμής που προκύπτει.
Καλώντας το go generate, θα εκτελέσουμε το πρόγραμμα στο avo και ως αποτέλεσμα θα δημιουργηθούν δύο αρχεία:
- add.s με τον κώδικα που προκύπτει στο Go assembler.
- Stub.go με κεφαλίδες λειτουργίας για να συνδέσετε τους δύο κόσμους: GO και Assembler.
Τώρα που είδαμε τι κάνει και πώς η avo, ας δούμε τις λειτουργίες μας. Εφάρμοσα τόσο βαθμωτές όσο και διανυσματικές (SIMD) εκδόσεις των συναρτήσεων.
Ας δούμε πρώτα τις βαθμωτές εκδόσεις.
Όπως στο προηγούμενο παράδειγμα, ζητάμε έναν δωρεάν και έγκυρο καταχωρητή γενικού σκοπού, δεν χρειάζεται να υπολογίσουμε μετατοπίσεις και μεγέθη για τα ορίσματα. Ο avo τα κάνει όλα αυτά για εμάς.
Χρησιμοποιούσαμε ετικέτες και goto (ή άλματα) για να βελτιώσουμε την απόδοση και να ξεγελάσουμε τον μεταγλωττιστή Go, αλλά τώρα το κάνουμε από την αρχή. Το θέμα είναι ότι οι κύκλοι είναι μια έννοια υψηλότερου επιπέδου. Στο assembler, έχουμε μόνο ετικέτες και άλματα.
Ο κωδικός που απομένει θα πρέπει να είναι ήδη γνωστός και κατανοητός. Μιμούμε έναν βρόχο με ετικέτες και πηδήματα, παίρνουμε ένα μικρό κομμάτι δεδομένων από τις δύο φέτες μας, τις συνδυάζουμε με μια λειτουργία bit (ΚΑΙ ΟΧΙ σε αυτήν την περίπτωση) και μετά βάζουμε το αποτέλεσμα στη φέτα που προκύπτει. Ολα.
Έτσι φαίνεται ο τελικός κώδικας assembler. Δεν χρειάστηκε να υπολογίσουμε μετατοπίσεις και μεγέθη (επισημασμένα με πράσινο χρώμα) ή να παρακολουθούμε τους καταχωρητές που χρησιμοποιήθηκαν (επισημασμένοι με κόκκινο).
Αν συγκρίνουμε την απόδοση της υλοποίησης της γλώσσας assembly με την απόδοση της καλύτερης υλοποίησης στο Go, θα δούμε ότι είναι η ίδια. Και αυτό είναι αναμενόμενο. Εξάλλου, δεν κάναμε τίποτα ιδιαίτερο - απλώς αναπαράγαμε αυτό που θα έκανε ένας μεταγλωττιστής Go.
Δυστυχώς, δεν μπορούμε να αναγκάσουμε τον μεταγλωττιστή να ενσωματώσει τις λειτουργίες μας γραμμένες σε γλώσσα assembly. Ο μεταγλωττιστής Go προς το παρόν δεν διαθέτει τέτοια δυνατότητα, αν και υπάρχει αίτημα για προσθήκη εδώ και αρκετό καιρό.
Αυτός είναι ο λόγος για τον οποίο είναι αδύνατο να επωφεληθείτε από μικρές λειτουργίες στη γλώσσα assembly. Πρέπει είτε να γράψουμε μεγάλες συναρτήσεις, είτε να χρησιμοποιήσουμε το νέο πακέτο μαθηματικών/bit, είτε να παρακάμψουμε τη γλώσσα assembler.
Ας δούμε τώρα τις διανυσματικές εκδόσεις των συναρτήσεών μας.
Για αυτό το παράδειγμα, αποφάσισα να χρησιμοποιήσω το AVX2, επομένως θα χρησιμοποιήσουμε λειτουργίες που λειτουργούν σε κομμάτια 32 byte. Η δομή του κώδικα μοιάζει πολύ με τη βαθμωτή έκδοση: φόρτωση παραμέτρων, αίτημα για δωρεάν κοινόχρηστο μητρώο κ.λπ.
Μια καινοτομία είναι ότι οι ευρύτερες διανυσματικές πράξεις χρησιμοποιούν ειδικούς ευρείες καταχωρητές. Στην περίπτωση των κομματιών 32 byte, αυτοί είναι καταχωρητές με πρόθεμα Y. Αυτός είναι ο λόγος για τον οποίο βλέπετε τη συνάρτηση YMM() στον κώδικα. Αν χρησιμοποιούσα το AVX-512 με κομμάτια 64-bit, το πρόθεμα θα ήταν Z.
Η δεύτερη καινοτομία είναι ότι αποφάσισα να χρησιμοποιήσω μια βελτιστοποίηση που ονομάζεται ξεκύλιση βρόχου, που σημαίνει να κάνω οκτώ λειτουργίες βρόχου με μη αυτόματο τρόπο πριν μεταβώ στην αρχή του βρόχου. Αυτή η βελτιστοποίηση μειώνει τον αριθμό των διακλαδώσεων στον κώδικα και περιορίζεται από τον αριθμό των διαθέσιμων δωρεάν καταχωρίσεων.
Λοιπόν, τι γίνεται με την απόδοση; Είναι όμορφη! Πετύχαμε επιτάχυνση περίπου επτά φορές σε σύγκριση με την καλύτερη λύση Go. Εντυπωσιακό, σωστά;
Αλλά ακόμη και αυτή η υλοποίηση θα μπορούσε ενδεχομένως να επιταχυνθεί με τη χρήση του AVX-512, της προαναφοράς ή ενός JIT (μεταγλωττιστή ακριβώς στην ώρα) για τον προγραμματιστή ερωτημάτων. Αλλά αυτό είναι σίγουρα ένα θέμα για ξεχωριστή έκθεση.
Προβλήματα με ευρετήρια bitmap
Τώρα που έχουμε ήδη εξετάσει μια απλή υλοποίηση ενός ευρετηρίου bitmap στο Go και ενός πολύ πιο παραγωγικού στη γλώσσα assembly, ας μιλήσουμε επιτέλους γιατί τα ευρετήρια bitmap χρησιμοποιούνται τόσο σπάνια.
Παλαιότερα έγγραφα αναφέρουν τρία προβλήματα με ευρετήρια bitmap, αλλά τα νεότερα έγγραφα και υποστηρίζω ότι δεν είναι πλέον σχετικά. Δεν θα βουτήξουμε βαθιά σε καθένα από αυτά τα προβλήματα, αλλά θα τα δούμε επιφανειακά.
Το πρόβλημα της υψηλής καρδινικότητας
Έτσι, μας λένε ότι τα ευρετήρια bitmap είναι κατάλληλα μόνο για πεδία με χαμηλή καρδινάτητα, δηλαδή εκείνα που έχουν λίγες τιμές (για παράδειγμα, φύλο ή χρώμα ματιών) και ο λόγος είναι ότι η συνήθης αναπαράσταση τέτοιων πεδίων (ένα bit ανά τιμή) σε περίπτωση υψηλής καρδιναικότητας, θα καταλαμβάνει πολύ χώρο και, επιπλέον, αυτοί οι δείκτες bitmap θα πληρωθούν ελάχιστα (σπάνια).
Μερικές φορές μπορούμε να χρησιμοποιήσουμε μια διαφορετική αναπαράσταση, όπως η τυπική που χρησιμοποιούμε για να αντιπροσωπεύουμε αριθμούς. Αλλά ήταν η έλευση των αλγορίθμων συμπίεσης που άλλαξαν τα πάντα. Τις τελευταίες δεκαετίες, οι επιστήμονες και οι ερευνητές έχουν καταλήξει σε μεγάλο αριθμό αλγορίθμων συμπίεσης για bitmaps. Το κύριο πλεονέκτημά τους είναι ότι δεν υπάρχει ανάγκη αποσυμπίεσης bitmaps για την εκτέλεση λειτουργιών bit - μπορούμε να εκτελέσουμε λειτουργίες bit απευθείας σε συμπιεσμένα bitmaps.
Πρόσφατα, οι υβριδικές προσεγγίσεις έχουν αρχίσει να εμφανίζονται, όπως τα βρυχηθμό bitmaps. Χρησιμοποιούν ταυτόχρονα τρεις διαφορετικές αναπαραστάσεις για bitmaps - bitmaps οι ίδιοι, πίνακες και τα λεγόμενα bit runs - και ισορροπούν μεταξύ τους για να μεγιστοποιήσουν την απόδοση και να ελαχιστοποιήσουν την κατανάλωση μνήμης.
Μπορείτε να βρείτε βρυχηθμό bitmaps στις πιο δημοφιλείς εφαρμογές. Υπάρχει ήδη ένας τεράστιος αριθμός υλοποιήσεων για μια μεγάλη ποικιλία γλωσσών προγραμματισμού, συμπεριλαμβανομένων περισσότερων από τρεις υλοποιήσεις για το Go.
Μια άλλη προσέγγιση που μπορεί να μας βοηθήσει να αντιμετωπίσουμε την υψηλή πρωτοτυπία ονομάζεται binning. Φανταστείτε ότι έχετε ένα πεδίο που αντιπροσωπεύει το ύψος ενός ατόμου. Το ύψος είναι ένας αριθμός κινητής υποδιαστολής, αλλά εμείς οι άνθρωποι δεν το σκεφτόμαστε έτσι. Για εμάς δεν υπάρχει διαφορά μεταξύ ύψους 185,2 cm και 185,3 cm.
Αποδεικνύεται ότι μπορούμε να ομαδοποιήσουμε παρόμοιες τιμές σε ομάδες εντός 1 cm.
Και αν γνωρίζουμε επίσης ότι πολύ λίγοι άνθρωποι είναι μικρότεροι από 50 εκατοστά και ψηλότεροι από 250 εκατοστά, τότε μπορούμε ουσιαστικά να μετατρέψουμε ένα πεδίο με άπειρο καρδινάλιο σε ένα πεδίο με καρδινικότητα περίπου 200 τιμών.
Φυσικά, εάν είναι απαραίτητο, μπορούμε να κάνουμε επιπλέον φιλτράρισμα μετά.
Πρόβλημα υψηλού εύρους ζώνης
Το επόμενο πρόβλημα με τους δείκτες Bitmap είναι ότι η ενημέρωση τους μπορεί να είναι πολύ ακριβό.
Οι βάσεις δεδομένων πρέπει να είναι σε θέση να ενημερώνουν δεδομένα ενώ δυνητικά εκατοντάδες άλλα ερωτήματα αναζητούν τα δεδομένα. Χρειαζόμαστε κλειδαριές για να αποφύγουμε προβλήματα με ταυτόχρονη πρόσβαση στα δεδομένα ή άλλα προβλήματα κοινής χρήσης. Και όπου υπάρχει μια μεγάλη κλειδαριά, υπάρχει ένα πρόβλημα - διαμάχη κλειδώματος, όταν αυτή η κλειδαριά γίνεται εμπόδιο.
Αυτό το πρόβλημα μπορεί να λυθεί ή να παρακαμφθεί με τη χρήση διαμοιρασμού ή χρησιμοποιώντας ευρετήρια με έκδοση.
Το Sharding είναι απλό και γνωστό πράγμα. Μπορείτε να μοιράζετε ένα ευρετήριο bitmap όπως θα κάνατε με οποιαδήποτε άλλα δεδομένα. Αντί για μια μεγάλη κλειδαριά, θα πάρετε ένα σωρό μικρές κλειδαριές και έτσι θα απαλλαγείτε από τη διαμάχη κλειδαριάς.
Ο δεύτερος τρόπος επίλυσης του προβλήματος είναι η χρήση ευρετηρίων με έκδοση. Μπορείτε να έχετε ένα αντίγραφο του ευρετηρίου που χρησιμοποιείτε για αναζήτηση ή ανάγνωση και ένα αντίγραφο που χρησιμοποιείτε για σύνταξη ή ενημέρωση. Και μία φορά σε μια συγκεκριμένη χρονική περίοδο (για παράδειγμα, μία φορά κάθε 100 ms ή 500 ms) τα αντιγράφετε και τα αλλάζετε. Φυσικά, αυτή η προσέγγιση είναι εφαρμόσιμη μόνο σε περιπτώσεις όπου η εφαρμογή σας μπορεί να χειριστεί έναν ελαφρώς καθυστερημένο δείκτη αναζήτησης.
Αυτές οι δύο προσεγγίσεις μπορούν να χρησιμοποιηθούν ταυτόχρονα: μπορείτε να έχετε ένα μοιρασμένο ευρετήριο.
Πιο σύνθετα ερωτήματα
Το τελευταίο πρόβλημα με τα ευρετήρια bitmap είναι ότι μας λένε ότι δεν είναι κατάλληλα για πιο σύνθετους τύπους ερωτημάτων, όπως τα ερωτήματα εμβέλειας.
Πράγματι, αν το καλοσκεφτείτε, λειτουργίες bit όπως AND, OR, κ.λπ. δεν είναι πολύ κατάλληλες για ερωτήματα a la "Δείξε μου ξενοδοχεία με τιμές δωματίων από 200 έως 300 δολάρια ανά διανυκτέρευση."
Μια αφελής και πολύ ασυνήθιστη λύση θα ήταν να λάβετε τα αποτελέσματα για κάθε αξία του δολαρίου και να τα συνδυάσετε με ένα bitwise ή λειτουργία.
Μια ελαφρώς καλύτερη λύση θα ήταν η χρήση ομαδοποίησης. Για παράδειγμα, σε ομάδες των 50 δολαρίων. Αυτό θα επιτάχυνε τη διαδικασία μας κατά 50 φορές.
Αλλά το πρόβλημα επιλύεται επίσης εύκολα χρησιμοποιώντας μια προβολή που δημιουργήθηκε ειδικά για αυτόν τον τύπο αιτήματος. Στις επιστημονικές εργασίες λέγεται bitmaps με κωδικοποίηση εύρους.
Σε αυτήν την αναπαράσταση, δεν ορίζουμε απλώς ένα bit για κάποια τιμή (για παράδειγμα, 200), αλλά ορίζουμε αυτήν την τιμή και όλα υψηλότερα. 200 και άνω. Το ίδιο για 300: 300 και πάνω. Και ούτω καθεξής.
Χρησιμοποιώντας αυτήν την αναπαράσταση, μπορούμε να απαντήσουμε σε αυτό το είδος ερωτήματος αναζήτησης διασχίζοντας το ευρετήριο μόνο δύο φορές. Αρχικά, θα λάβουμε μια λίστα με ξενοδοχεία όπου το δωμάτιο κοστίζει λιγότερο ή 300 $ και, στη συνέχεια, θα αφαιρέσουμε από αυτήν εκείνα όπου το κόστος του δωματίου είναι μικρότερο ή 199 $. Ετοιμος.
Θα εκπλαγείτε, αλλά ακόμη και γεωγραφικά ερωτήματα είναι δυνατά χρησιμοποιώντας ευρετήρια bitmap. Το κόλπο είναι να χρησιμοποιήσετε μια γεωμετρική αναπαράσταση που περιβάλλει τη συντεταγμένη σας με ένα γεωμετρικό σχήμα. Για παράδειγμα, το S2 από την Google. Το σχήμα θα πρέπει να μπορεί να αναπαρασταθεί με τη μορφή τριών ή περισσότερων τεμνόμενων γραμμών που μπορούν να αριθμηθούν. Με αυτόν τον τρόπο μπορούμε να μετατρέψουμε το geoquery μας σε πολλά ερωτήματα "κατά μήκος του κενού" (κατά μήκος αυτών των αριθμημένων γραμμών).
Έτοιμες λύσεις
Ελπίζω να σας ενδιαφέρομαι λίγο και τώρα έχετε ένα άλλο χρήσιμο εργαλείο στο οπλοστάσιό σας. Εάν πρέπει ποτέ να κάνετε κάτι τέτοιο, θα ξέρετε ποιος τρόπος να κοιτάξετε.
Ωστόσο, δεν έχουν ο καθένας το χρόνο, την υπομονή ή τους πόρους για να δημιουργήσει δείκτες bitmap από το μηδέν. Ειδικά πιο προηγμένα, χρησιμοποιώντας το SIMD, για παράδειγμα.
Ευτυχώς, υπάρχουν αρκετές έτοιμες λύσεις που θα σας βοηθήσουν.
Βρυχηθμό bitmaps
Πρώτον, υπάρχει η ίδια βρυχηθμένη βιβλιοθήκη bitmaps για την οποία μίλησα ήδη. Περιέχει όλα τα απαραίτητα κοντέινερ και τις λειτουργίες bit που θα χρειαστείτε για να δημιουργήσετε ένα πλήρες ευρετήριο bitmap.
Δυστυχώς, αυτή τη στιγμή, καμία από τις υλοποιήσεις Go δεν χρησιμοποιεί SIMD, πράγμα που σημαίνει ότι οι υλοποιήσεις Go έχουν μικρότερη απόδοση από τις υλοποιήσεις C, για παράδειγμα.
Πιλόζα
Ένα άλλο προϊόν που μπορεί να σας βοηθήσει είναι το Pilosa DBMS, το οποίο, στην πραγματικότητα, έχει μόνο ευρετήρια bitmap. Αυτή είναι μια σχετικά νέα λύση, αλλά κερδίζει καρδιές με μεγάλη ταχύτητα.
Το Pilosa χρησιμοποιεί εσωτερικά βρυχηθέντα bitmaps και σας δίνει τη δυνατότητα να τα χρησιμοποιήσετε, απλοποιεί και εξηγεί όλα τα πράγματα για τα οποία μίλησα παραπάνω: ομαδοποίηση, bitmaps με κωδικοποίηση περιοχής, την έννοια ενός πεδίου κ.λπ.
Ας ρίξουμε μια γρήγορη ματιά σε ένα παράδειγμα χρήσης του Pilosa για να απαντήσετε σε μια ερώτηση που γνωρίζετε ήδη.
Το παράδειγμα μοιάζει πολύ με αυτό που είδατε πριν. Δημιουργούμε έναν πελάτη στον διακομιστή Pilosa, δημιουργούμε ένα ευρετήριο και τα απαραίτητα πεδία, στη συνέχεια συμπληρώνουμε τα πεδία μας με τυχαία δεδομένα με πιθανότητες και, τέλος, εκτελούμε το γνωστό ερώτημα.
Μετά από αυτό, χρησιμοποιούμε το ΟΧΙ στο πεδίο "ακριβό", μετά τέμνουμε το αποτέλεσμα (ή ΚΑΙ αυτό) με το πεδίο "ταράτσα" και με το πεδίο "κρατήσεις". Και τελικά, έχουμε το τελικό αποτέλεσμα.
Ελπίζω πραγματικά ότι στο άμεσο μέλλον αυτός ο νέος τύπος ευρετηρίου θα εμφανιστεί επίσης σε DBMS όπως τα ευρετήρια MySQL και PostgreSQL - bitmap.
Συμπέρασμα
Αν δεν σας έχει πάρει ο ύπνος ακόμα, σας ευχαριστώ. Έπρεπε να θίξω εν συντομία πολλά θέματα λόγω περιορισμένου χρόνου, αλλά ελπίζω ότι η ομιλία ήταν χρήσιμη και ίσως ακόμη και ενθαρρυντική.
Είναι καλό να γνωρίζετε τα ευρετήρια bitmap, ακόμα κι αν δεν τα χρειάζεστε αυτήν τη στιγμή. Αφήστε τα να είναι ένα άλλο εργαλείο στην εργαλειοθήκη σας.
Έχουμε εξετάσει διάφορα κόλπα απόδοσης για το GO και τα πράγματα που ο μεταγλωττιστής GO δεν χειρίζεται πολύ καλά. Αλλά αυτό είναι απολύτως χρήσιμο για κάθε προγραμματιστή Go να γνωρίζει.
Μόνο αυτό ήθελα να σου πω. Ευχαριστώ!
Πηγή: www.habr.com