απαιτήσεις: Πρόσφατα, είδα ένα βίντεο του αλγορίθμου Redis Bloom στο Bilibili για να λύσω το πρόβλημα της διείσδυσης της κρυφής μνήμης, με απλά λόγια, να προσθέσω ένα επίπεδο λογικής κρίσης πριν αποκτήσω πρόσβαση στη βάση δεδομένων για να προσδιορίσω εάν υπάρχουν τα δεδομένα και, εάν ναι, πρόσβαση στη βάση δεδομένων. Για παράδειγμα, εάν ένας ιστότοπος είναι ένα σύστημα ειδήσεων, οι διευθύνσεις URL των άρθρων δημιουργούνται από αυτο-αυξανόμενα αναγνωριστικά πρωτεύοντος κλειδιού (μορφή URL example:/news-1.html), ο ιστότοπος μπορεί να έχει μόνο δεκάδες χιλιάδες άρθρα και κρυφές μνήμες.
Αρχικά:
Αίτηση πόρου ειδήσεων -> Προσδιορίστε εάν υπάρχει το cache -> Παρουσία -> Το cache επιστρέφει δεδομένα.
Αίτηση πόρων ειδήσεων -> Προσδιορίστε εάν υπάρχει το cache -> δεν υπάρχει -> Ερώτημα από τη βάση δεδομένων -> Παρουσίαση -> Προσωρινή αποθήκευση και επιστροφή δεδομένων.
Αίτηση πόρου ειδήσεων -> Προσδιορίστε εάν υπάρχει το cache -> δεν υπάρχει -> Ερώτημα από τη βάση δεδομένων -> Δεν υπάρχει -> Επιστρέφει σφάλμα 404.
Αυτή τη στιγμή:
Ζητήστε πηγή ειδήσεων -> αλγόριθμος του Bloom -> Ύπαρξη -> Ακολουθήστε την αρχική λογική.
Αίτημα πόρου ειδήσεων -> Ο αλγόριθμος του Bloom -> δεν υπάρχει -> επιστρέφει απευθείας ένα σφάλμα 404.
Φίλτρο άνθισης
Ο αλγόριθμος BloomFilter είναι ένας αλγόριθμος προγραμματισμού μεγάλων δεδομένων. Σε ένα σύνολο με μεγάλο όγκο δεδομένων, μπορεί να προσδιοριστεί με ακρίβεια ότι ένα αντικείμενο δεν βρίσκεται στο σύνολο. Είναι δυνατό να κρίνετε ένα αντικείμενο σε ένα σετ και να πιάνετε λίγο χώρο. αυτόΔεν είναι κατάλληλο για καταστάσεις που απαιτούν υψηλή ακρίβεια και μηδενικά σφάλματα。 Η αποτελεσματική χρήση του χώρου επιτυγχάνεται θυσιάζοντας τη μερική ακρίβεια.
Ο αλγόριθμος του Bloom είναι μια μέθοδος που βασίζεται σεΘυσιάστε μια συγκεκριμένη ακρίβεια με αντάλλαγμα έναν αλγόριθμο φιλτραρίσματος με χαμηλή κατανάλωση μνήμης, το οποίο μπορεί να πραγματοποιήσει το φιλτράρισμα, την αφαίρεση διπλότυπων και άλλες λειτουργίες μεγάλου όγκου δεδομένων.
Ο αλγόριθμος Bloom είναι απλώς μια αφηρημένη έννοια και μπορεί να εφαρμοστεί με πολλούς τρόπους, και η χρήση του BitMap στο Redis στο άρθρο είναι απλώς μια απλή υλοποίηση.
Αναφορά:Η σύνδεση με υπερσύνδεσμο είναι ορατή.
Εισαγωγή BitMap
Το BitMap είναι ένα bitmap, το οποίο είναι στην πραγματικότητα ένας πίνακας byte, που αναπαρίσταται σε δυαδικό.Υπάρχουν μόνο δύο αριθμοί, το 0 και το 1, bitmap είναι να χρησιμοποιήσετε κάθε δυαδικό bit για να αποθηκεύσετε ή να επισημάνετε την τιμή που αντιστοιχεί σε ένα στοιχείο. Συνήθως χρησιμοποιείται για να προσδιοριστεί εάν υπάρχουν συγκεκριμένα δεδομένα ή όχι, επειδή αποθηκεύονται σε bit, επομένως το ίδιο το Bitmap θα εξοικονομήσει σημαντικά χώρο αποθήκευσης.
Όπως φαίνεται στο παρακάτω σχήμα, η συμβολοσειρά αποθηκεύεται σε δυαδική μορφή στον υπολογιστή.
Τύποι δεδομένων BitMap στο Redis
Ο τύπος δεδομένων που παρέχεται από το Redis είναι BitMap και κάθε bit αντιστοιχεί σε δύο καταστάσεις: 0 και 1. Αν και ο εσωτερικός χώρος αποθήκευσης εξακολουθεί να είναι τύπου String, το Redis παρέχει ορισμένες οδηγίες για τον άμεσο χειρισμό του BitMap, το οποίο μπορεί να θεωρηθεί ως πίνακας bit και ο δείκτης του πίνακα είναι η μετατόπιση.
Τα πλεονεκτήματά του είναι:Χαμηλή επιβάρυνση μνήμης και υψηλή απόδοσηΚαι η λειτουργία είναι απλή.
Εξοικονόμηση χώρου: Ένα bit χρησιμοποιείται για να αναπαραστήσει την τιμή ή την κατάσταση ενός στοιχείου, όπου κλειδί είναι η τιμή του αντίστοιχου στοιχείου. Στην πραγματικότητα, 8 bit μπορούν να αποτελέσουν ένα byte, επομένως εξοικονομεί χώρο.
Υψηλή απόδοση: Η χρονική πολυπλοκότητα του setbit και του getbit είναι O(1) και η απόδοση άλλων bit είναι επίσης υψηλή.
Ακολουθεί ένα παράδειγμα χρήσης της συλλογής συνόλων και του χώρου αποθήκευσης BitMap:
| τύπος δεδομένων | Κάθε userid καταλαμβάνει χώρο | Ο αριθμός των χρηστών που πρέπει να αποθηκευτούν | Όλα απασχολούν τη μνήμη | | βάζω | Τα 32 bit είναι 4 byte (υποθέτοντας ότι το Userid χρησιμοποιεί ακέραιους αριθμούς, πολλοί ιστότοποι χρησιμοποιούν στην πραγματικότητα μεγάλους ακέραιους αριθμούς) | 50,000,000 | 32 bit * 50.000.000 = 200 MB | | Δυφιοαπεικόνιση | 1 κομμάτι | 100,000,000 | 1 bit * 100.000.000 = 12,5 MB |
Ο χρόνος τεντώνεται λίγο
| | Μια μέρα | Ένας μήνας | Ένα έτος | | βάζω | 200Λ | 6Ζ | 72ΓΡ | | Δυφιοαπεικόνιση | 12,5 εκατ. | 375Λ | 4,5 γρ |
Μετά τον υπολογισμό, διαπιστώθηκε ότι όσο αυξανόταν ο χρόνος, ο όγκος των δεδομένων που έπρεπε να καταγραφούν αυξανόταν και η αντίθεση γινόταν πιο εμφανής και το BitMap καταλάμβανε λιγότερο χώρο από ό,τι είχε οριστεί.
Το Redis παρέχει τις ακόλουθες οδηγίες για τη λειτουργία του BitMap:
Τεκμηρίωση εντολών:Η σύνδεση με υπερσύνδεσμο είναι ορατή.
Τώρα που έχετε μια σύντομη κατανόηση του αλγορίθμου και των χαρακτηριστικών και της σύνταξης Bitmap του Redis, ας χρησιμοποιήσουμε το redis για να κάνουμε μια απλή λειτουργία.
Σύνταξη SETBIT:Τιμή μετατόπισης κλειδιού SETBIT
Ορίστε το άρθρο id:9, 10, 156 σε 1 και η εντολή είναι η εξής:
Σύνταξη GETBIT: Μετατόπιση κλειδιού GETBIT
Για να προσδιορίσετε εάν υπάρχει το id: 10 ή το 11, η εντολή είναι η εξής:
Το .NET/C# χειρίζεται τον τύπο BitMap του Redis
Μάθαμε για πολλές εντολές BitMap στο redis και πώς να τις χειριζόμαστε μέσω προγραμματισμού. Δημιουργήστε ένα νέο έργο κονσόλας .NET 3.1, ανατρέξτε στο πακέτο StackExchange.Redis και χρησιμοποιήστε την ακόλουθη εντολή:
Ο πηγαίος κώδικας έχει ως εξής:
Υπάρχουν πολλά άλλα σενάρια εφαρμογής bitmap για το Redis, ως εξής:
- Μπορεί να χρησιμοποιηθεί ως ένα απλό φίλτρο Bloom για να προσδιοριστεί εάν ένας χρήστης έχει εκτελέσει ορισμένες ενέργειες.
- Στατιστικά στοιχεία της καθημερινής δραστηριότητας των χρηστών, της μηνιαίας δραστηριότητας και του ποσοστού διατήρησης
- Συνειδητοποιήστε τα στατιστικά στοιχεία του αριθμού των εκκινήσεων χρηστών
- Στατιστικά στοιχεία διαδικτυακής παρουσίας χρηστών και ατόμων
(Τέλος)
|
Δημοσιεύτηκε στις 2/1/2023 5:37:01 μ.μ.
|
|
|
|
Σπιτονοικοκύρης|
Δημοσιεύτηκε στις 2/1/2023 5:41:56 μ.μ.
|
Δημοσιεύτηκε στις 2/1/2023 8:42:47 μ.μ.
|
