Το φθινόπωρο του 2019, πραγματοποιήθηκε μια πολυαναμενόμενη εκδήλωση στην ομάδα του Mail.ru Cloud iOS. Η κύρια βάση δεδομένων για την επίμονη αποθήκευση της κατάστασης της εφαρμογής έχει γίνει αρκετά εξωτική για τον κόσμο των κινητών Βάση δεδομένων με αντιστοίχιση μνήμης Lightning (LMDB). Κάτω από την περικοπή, η προσοχή σας καλείται στη λεπτομερή ανασκόπησή του σε τέσσερα μέρη. Αρχικά, ας μιλήσουμε για τους λόγους μιας τόσο μη τετριμμένης και δύσκολης επιλογής. Στη συνέχεια, ας προχωρήσουμε στην εξέταση τριών φαλαινών στην καρδιά της αρχιτεκτονικής LMDB: αρχεία με χαρτογράφηση μνήμης, δέντρο B +, προσέγγιση αντιγραφής σε εγγραφή για την υλοποίηση συναλλαγών και πολλαπλών εκδόσεων. Τέλος, για επιδόρπιο - το πρακτικό μέρος. Σε αυτό, θα δούμε πώς να σχεδιάσουμε και να εφαρμόσουμε ένα βασικό σχήμα με πολλούς πίνακες, συμπεριλαμβανομένου ενός ευρετηρίου, πάνω από το χαμηλού επιπέδου API κλειδιού-τιμής.

περιεχόμενο

Κίνητρα Υλοποίησης
Τοποθέτηση LMDB
Τρεις φάλαινες LMDB
3.1. Φάλαινα #1. Αρχεία με χαρτογράφηση μνήμης
3.2. Φάλαινα #2. Β+-δέντρο
3.3. Φάλαινα #3. αντιγραφή σε εγγραφή
Σχεδιασμός σχήματος δεδομένων πάνω από το API κλειδιού-τιμής
4.1. Βασικές αφαιρέσεις
4.2. Μοντελοποίηση πίνακα
4.3. Μοντελοποίηση σχέσεων μεταξύ πινάκων

1. Κίνητρα υλοποίησης

Μια φορά το χρόνο, το 2015, φροντίσαμε να κάνουμε μια μέτρηση, πόσο συχνά καθυστερεί η διεπαφή της εφαρμογής μας. Δεν κάναμε μόνο αυτό. Έχουμε όλο και περισσότερα παράπονα για το γεγονός ότι μερικές φορές η εφαρμογή σταματά να ανταποκρίνεται στις ενέργειες των χρηστών: τα κουμπιά δεν πατούνται, οι λίστες δεν κάνουν κύλιση κ.λπ. Σχετικά με τη μηχανική των μετρήσεων είπα στην AvitoTech, οπότε εδώ δίνω μόνο τη σειρά των αριθμών.

Τα αποτελέσματα των μετρήσεων έγιναν ένα κρύο ντους για εμάς. Αποδείχθηκε ότι τα προβλήματα που προκαλούνται από τα παγώματα είναι πολύ περισσότερα από κάθε άλλο. Εάν, πριν συνειδητοποιήσουμε αυτό το γεγονός, ο κύριος τεχνικός δείκτης ποιότητας ήταν χωρίς σύγκρουση, τότε μετά την εστίαση μετατοπίστηκε σε ελεύθερη κατάψυξη.

Έχοντας χτίσει ταμπλό με παγώματα και έχοντας ξοδέψει ποσοτικός и ποιότητα ανάλυση των αιτιών τους, ο κύριος εχθρός έγινε σαφής - η βαριά επιχειρηματική λογική εκτελείται στο κύριο νήμα της εφαρμογής. Μια φυσική αντίδραση σε αυτό το αίσχος ήταν μια διακαής επιθυμία να το σπρώξω σε ρεύματα εργασίας. Για μια συστηματική λύση αυτού του προβλήματος, καταφύγαμε σε μια αρχιτεκτονική πολλαπλών νημάτων που βασίζεται σε ελαφριούς ηθοποιούς. Αφιέρωσα τις προσαρμογές της για τον κόσμο του iOS δύο κλωστές στο συλλογικό twitter και άρθρο για το Habré. Ως μέρος της τρέχουσας ιστορίας, θέλω να τονίσω εκείνες τις πτυχές της απόφασης που επηρέασαν την επιλογή της βάσης δεδομένων.

Το μοντέλο δρών της οργάνωσης του συστήματος υποθέτει ότι το multithreading γίνεται η δεύτερη ουσία του. Τα αντικείμενα του μοντέλου σε αυτό αρέσει να διασχίζουν τα όρια νημάτων. Και αυτό το κάνουν όχι μερικές φορές και σε ορισμένα μέρη, αλλά σχεδόν συνεχώς και παντού.

Η βάση δεδομένων είναι ένα από τα στοιχεία ακρογωνιαίο λίθο στο παρουσιαζόμενο διάγραμμα. Το κύριο καθήκον του είναι να εφαρμόσει ένα μοτίβο μακροεντολών Κοινόχρηστη βάση δεδομένων. Εάν στον κόσμο των επιχειρήσεων χρησιμοποιείται για την οργάνωση του συγχρονισμού δεδομένων μεταξύ των υπηρεσιών, τότε στην περίπτωση μιας αρχιτεκτονικής ηθοποιών, δεδομένα μεταξύ νημάτων. Έτσι, χρειαζόμασταν μια τέτοια βάση δεδομένων, η συνεργασία με την οποία σε ένα περιβάλλον πολλαπλών νημάτων δεν προκαλεί ούτε ελάχιστες δυσκολίες. Συγκεκριμένα, αυτό σημαίνει ότι τα αντικείμενα που προέρχονται από αυτό πρέπει να είναι τουλάχιστον ασφαλή για νήματα και ιδανικά να μην είναι καθόλου μεταβλητά. Όπως γνωρίζετε, το τελευταίο μπορεί να χρησιμοποιηθεί ταυτόχρονα από πολλά νήματα χωρίς να καταφύγετε σε οποιοδήποτε είδος κλειδαριάς, γεγονός που έχει ευεργετική επίδραση στην απόδοση.

Ο δεύτερος σημαντικός παράγοντας που επηρέασε την επιλογή της βάσης δεδομένων ήταν το cloud API μας. Εμπνεύστηκε από την προσέγγιση git στο συγχρονισμό. Σαν αυτόν στοχεύαμε πρώτο API εκτός σύνδεσης, το οποίο φαίνεται περισσότερο από κατάλληλο για πελάτες cloud. Θεωρήθηκε ότι θα αντλούσαν μόνο μία φορά την πλήρη κατάσταση του νέφους και στη συνέχεια ο συγχρονισμός στη συντριπτική πλειονότητα των περιπτώσεων θα γινόταν μέσω κυλιόμενων αλλαγών. Δυστυχώς, αυτή η δυνατότητα εξακολουθεί να είναι μόνο στη θεωρητική ζώνη και στην πράξη, οι πελάτες δεν έχουν μάθει πώς να εργάζονται με patches. Υπάρχουν αρκετοί αντικειμενικοί λόγοι για αυτό, τους οποίους, για να μην καθυστερήσουμε την εισαγωγή, θα τους αφήσουμε εκτός παρενθέσεων. Τώρα, πολύ πιο ενδιαφέροντα είναι τα διδακτικά αποτελέσματα του μαθήματος σχετικά με το τι συμβαίνει όταν το API είπε "A" και ο καταναλωτής του δεν είπε "B".

Έτσι, αν φανταστείτε το git, το οποίο, κατά την εκτέλεση μιας εντολής pull, αντί να εφαρμόζει ενημερώσεις κώδικα σε ένα τοπικό στιγμιότυπο, συγκρίνει την πλήρη κατάστασή του με τον πλήρη διακομιστή, τότε θα έχετε μια αρκετά ακριβή ιδέα για το πώς γίνεται ο συγχρονισμός εμφανίζεται σε υπολογιστές-πελάτες cloud. Είναι εύκολο να μαντέψει κανείς ότι για την υλοποίησή του είναι απαραίτητο να εκχωρηθούν δύο δέντρα DOM στη μνήμη με μετα-πληροφορίες για όλους τους διακομιστή και τα τοπικά αρχεία. Αποδεικνύεται ότι εάν ένας χρήστης αποθηκεύει 500 χιλιάδες αρχεία στο σύννεφο, τότε για να το συγχρονίσει, είναι απαραίτητο να αναδημιουργήσει και να καταστρέψει δύο δέντρα με 1 εκατομμύριο κόμβους. Αλλά κάθε κόμβος είναι ένα άθροισμα που περιέχει ένα γράφημα υποαντικειμένων. Υπό αυτό το πρίσμα, τα αποτελέσματα του προφίλ ήταν αναμενόμενα. Αποδείχθηκε ότι ακόμη και χωρίς να ληφθεί υπόψη ο αλγόριθμος συγχώνευσης, η ίδια η διαδικασία δημιουργίας και στη συνέχεια καταστροφής ενός τεράστιου αριθμού μικρών αντικειμένων κοστίζει μια αρκετά δεκάρα. Η κατάσταση επιδεινώνεται από το γεγονός ότι η βασική λειτουργία συγχρονισμού περιλαμβάνεται σε μεγάλο αριθμό των σεναρίων χρήστη. Ως αποτέλεσμα, διορθώνουμε το δεύτερο σημαντικό κριτήριο για την επιλογή μιας βάσης δεδομένων - τη δυνατότητα υλοποίησης λειτουργιών CRUD χωρίς δυναμική κατανομή αντικειμένων.

Άλλες απαιτήσεις είναι πιο παραδοσιακές και η πλήρης λίστα τους είναι η εξής.

Ασφάλεια νήματος.
Πολυεπεξεργασία. Υπαγορεύεται από την επιθυμία χρήσης της ίδιας παρουσίας βάσης δεδομένων για τον συγχρονισμό της κατάστασης όχι μόνο μεταξύ των νημάτων, αλλά και μεταξύ της κύριας εφαρμογής και των επεκτάσεων iOS.
Η δυνατότητα αναπαράστασης αποθηκευμένων οντοτήτων ως μη μεταβλητών αντικειμένων.
Έλλειψη δυναμικών κατανομών εντός των λειτουργιών CRUD.
Υποστήριξη συναλλαγών για βασικές ιδιότητες ΟΞΥΛέξεις κλειδιά: ατομικότητα, συνέπεια, απομόνωση και αξιοπιστία.
Ταχύτητα στις πιο δημοφιλείς περιπτώσεις.

Με αυτό το σύνολο απαιτήσεων, το SQLite ήταν και εξακολουθεί να είναι μια καλή επιλογή. Ωστόσο, ως μέρος της μελέτης των εναλλακτικών, έπεσα πάνω σε ένα βιβλίο "Ξεκινώντας με το LevelDB". Υπό την ηγεσία της, γράφτηκε ένα σημείο αναφοράς που συγκρίνει την ταχύτητα εργασίας με διαφορετικές βάσεις δεδομένων σε πραγματικά σενάρια cloud. Το αποτέλεσμα ξεπέρασε τις πιο τρελές προσδοκίες. Στις πιο δημοφιλείς περιπτώσεις - λήψη ενός δρομέα σε μια ταξινομημένη λίστα όλων των αρχείων και μια ταξινομημένη λίστα όλων των αρχείων για έναν δεδομένο κατάλογο - το LMDB αποδείχθηκε ότι ήταν 10 φορές ταχύτερο από το SQLite. Η επιλογή έγινε προφανής.

2. Τοποθέτηση LMDB

Το LMDB είναι μια βιβλιοθήκη, πολύ μικρή (μόνο 10 γραμμές), η οποία υλοποιεί το χαμηλότερο θεμελιώδες επίπεδο βάσεων δεδομένων - αποθήκευση.

Το παραπάνω διάγραμμα δείχνει ότι η σύγκριση του LMDB με το SQLite, το οποίο υλοποιεί ακόμη υψηλότερα επίπεδα, δεν είναι γενικά πιο σωστή από το SQLite με Core Data. Θα ήταν πιο δίκαιο να αναφέρουμε τις ίδιες μηχανές αποθήκευσης ως ισότιμους ανταγωνιστές - BerkeleyDB, LevelDB, Sophia, RocksDB, κ.λπ. Υπάρχουν ακόμη εξελίξεις όπου το LMDB λειτουργεί ως στοιχείο μηχανής αποθήκευσης για το SQLite. Το πρώτο τέτοιο πείραμα το 2012 Πέρασα συγγραφέας LMDB Χάουαρντ Τσου. Ευρήματα αποδείχτηκε τόσο ενδιαφέρουσα που η πρωτοβουλία του έγινε αποδεκτή από τους λάτρεις της OSS και βρήκε τη συνέχειά της στο πρόσωπο του LumoSQL. Τον Ιανουάριο του 2020 ο συγγραφέας αυτού του έργου είναι ο Den Shearer παρουσιάζονται το στο LinuxConfAu.

Η κύρια χρήση του LMDB είναι ως μηχανή για βάσεις δεδομένων εφαρμογών. Η βιβλιοθήκη οφείλει την εμφάνισή της στους προγραμματιστές OpenLDAP, οι οποίοι ήταν έντονα δυσαρεστημένοι με το BerkeleyDB ως βάση του έργου τους. Σπρώχνοντας μακριά από την ταπεινή βιβλιοθήκη btree, ο Howard Chu κατάφερε να δημιουργήσει μια από τις πιο δημοφιλείς εναλλακτικές της εποχής μας. Αφιέρωσε την πολύ ωραία αναφορά του σε αυτή την ιστορία, καθώς και στην εσωτερική δομή του LMDB. "The Lightning Memory-Mapped Database". Λεονίντ Γιούριεφ (γνωστός και ως yleo) από την Positive Technologies στην ομιλία του στο Highload 2015 "Ο κινητήρας LMDB είναι ένας ειδικός πρωταθλητής". Σε αυτό, μιλά για το LMDB στο πλαίσιο ενός παρόμοιου έργου εφαρμογής του ReOpenLDAP και το LevelDB έχει ήδη υποβληθεί σε συγκριτική κριτική. Ως αποτέλεσμα της υλοποίησης, η Positive Technologies απέκτησε ακόμη και μια ενεργά αναπτυσσόμενη διχάλα MDBX με πολύ νόστιμα χαρακτηριστικά, βελτιστοποιήσεις και διορθώσεις σφαλμάτων.

Το LMDB χρησιμοποιείται συχνά και ως αποθήκευση. Για παράδειγμα, το πρόγραμμα περιήγησης Mozilla Firefox επέλεξε για μια σειρά από ανάγκες και, ξεκινώντας από την έκδοση 9, Xcode προνομιούχος Το SQLite του για αποθήκευση ευρετηρίων.

Ο κινητήρας μπήκε επίσης στον κόσμο της ανάπτυξης κινητής τηλεφωνίας. Ίχνη χρήσης του μπορεί να είναι βρίσκω στο πρόγραμμα-πελάτη iOS για το Telegram. Το LinkedIn προχώρησε ένα βήμα παραπέρα και επέλεξε το LMDB ως προεπιλεγμένο αποθηκευτικό χώρο για το εγχώριο πλαίσιο προσωρινής αποθήκευσης δεδομένων, το Rocket Data, για το οποίο είπε σε άρθρο του 2016.

Η LMDB παλεύει με επιτυχία για μια θέση στον ήλιο στη θέση που άφησε η BerkeleyDB μετά τη μετάβαση υπό τον έλεγχο της Oracle. Η βιβλιοθήκη είναι αγαπητή για την ταχύτητα και την αξιοπιστία της, ακόμη και σε σύγκριση με το είδος της. Όπως γνωρίζετε, δεν υπάρχουν δωρεάν γεύματα και θα ήθελα να τονίσω τον συμβιβασμό που θα πρέπει να αντιμετωπίσετε όταν επιλέγετε μεταξύ LMDB και SQLite. Το παραπάνω διάγραμμα δείχνει ξεκάθαρα πώς επιτυγχάνεται η αυξημένη ταχύτητα. Πρώτον, δεν πληρώνουμε για πρόσθετα επίπεδα αφαίρεσης πάνω από την αποθήκευση δίσκου. Φυσικά, σε μια καλή αρχιτεκτονική, δεν μπορείτε ακόμα να κάνετε χωρίς αυτά και αναπόφευκτα θα εμφανιστούν στον κώδικα της εφαρμογής, αλλά θα είναι πολύ πιο λεπτές. Δεν θα έχουν δυνατότητες που δεν απαιτούνται από μια συγκεκριμένη εφαρμογή, για παράδειγμα, υποστήριξη για ερωτήματα στη γλώσσα SQL. Δεύτερον, καθίσταται δυνατή η βέλτιστη εφαρμογή της αντιστοίχισης των λειτουργιών της εφαρμογής σε αιτήματα για αποθήκευση δίσκου. Εάν το SQLite στη δουλειά μου προέρχεται από τις μέσες ανάγκες μιας μέσης εφαρμογής, τότε εσείς, ως προγραμματιστής εφαρμογών, γνωρίζετε καλά τα κύρια σενάρια φόρτωσης. Για μια πιο παραγωγική λύση, θα πρέπει να πληρώσετε ένα αυξημένο τίμημα τόσο για την ανάπτυξη της αρχικής λύσης όσο και για την επακόλουθη υποστήριξή της.

3. Τρεις φάλαινες LMDB

Αφού κοιτάξετε το LMDB από την οπτική γωνία, ήρθε η ώρα να πάμε βαθύτερα. Οι επόμενες τρεις ενότητες θα αφιερωθούν στην ανάλυση των κύριων φαλαινών στις οποίες βασίζεται η αρχιτεκτονική αποθήκευσης:

Αρχεία με αντιστοίχιση μνήμης ως μηχανισμός εργασίας με δίσκο και συγχρονισμού εσωτερικών δομών δεδομένων.
B+-δέντρο ως οργάνωση της αποθηκευμένης δομής δεδομένων.
Αντιγραφή σε εγγραφή ως προσέγγιση για την παροχή συναλλακτικών ιδιοτήτων ACID και πολλαπλών εκδόσεων.

3.1. Φάλαινα #1. Αρχεία με χαρτογράφηση μνήμης

Τα αρχεία με χαρτογράφηση μνήμης είναι ένα τόσο σημαντικό αρχιτεκτονικό στοιχείο που εμφανίζονται ακόμη και στο όνομα του αποθετηρίου. Τα ζητήματα της προσωρινής αποθήκευσης και του συγχρονισμού της πρόσβασης σε αποθηκευμένες πληροφορίες είναι αποκλειστικά στο έλεος του λειτουργικού συστήματος. Το LMDB δεν περιέχει κρυφές μνήμες μέσα του. Αυτή είναι μια συνειδητή απόφαση του συγγραφέα, καθώς η απευθείας ανάγνωση δεδομένων από χαρτογραφημένα αρχεία σάς επιτρέπει να κόψετε πολλές γωνίες στην υλοποίηση του κινητήρα. Παρακάτω είναι μια μακριά από την πλήρη λίστα ορισμένων από αυτές.

Η διατήρηση της συνέπειας των δεδομένων στην αποθήκευση κατά την εργασία με αυτά από διάφορες διεργασίες γίνεται ευθύνη του λειτουργικού συστήματος. Στην επόμενη ενότητα, αυτός ο μηχανικός συζητείται λεπτομερώς και με εικόνες.
Η απουσία κρυφής μνήμης απαλλάσσει πλήρως το LMDB από τα γενικά έξοδα που σχετίζονται με τις δυναμικές εκχωρήσεις. Η ανάγνωση δεδομένων στην πράξη είναι η ρύθμιση του δείκτη στη σωστή διεύθυνση στην εικονική μνήμη και τίποτα περισσότερο. Ακούγεται σαν φαντασία, αλλά στην πηγή του αποθετηρίου, όλες οι κλήσεις calloc συγκεντρώνονται στη λειτουργία διαμόρφωσης αποθετηρίου.
Η απουσία κρυφής μνήμης σημαίνει επίσης την απουσία κλειδαριών που σχετίζονται με το συγχρονισμό για πρόσβαση σε αυτές. Οι αναγνώστες, των οποίων ένας αυθαίρετος αριθμός μπορεί να υπάρχει ταυτόχρονα, δεν συναντούν ούτε ένα mutex στο δρόμο τους προς τα δεδομένα. Λόγω αυτού, η ταχύτητα ανάγνωσης έχει ιδανική γραμμική επεκτασιμότητα όσον αφορά τον αριθμό των CPU. Στο LMDB, μόνο οι λειτουργίες τροποποίησης συγχρονίζονται. Μπορεί να υπάρχει μόνο ένας συγγραφέας τη φορά.
Η ελάχιστη λογική αποθήκευσης στην κρυφή μνήμη και συγχρονισμός σώζει τον κώδικα από έναν εξαιρετικά περίπλοκο τύπο σφαλμάτων που σχετίζονται με την εργασία σε περιβάλλον πολλαπλών νημάτων. Υπήρχαν δύο ενδιαφέρουσες μελέτες βάσεων δεδομένων στο συνέδριο Usenix OSDI 2014: "Όλα τα συστήματα αρχείων δεν δημιουργούνται ίσα: σχετικά με την πολυπλοκότητα της δημιουργίας εφαρμογών που συνεπάγονται σφάλματα" и Βασανιστικές βάσεις δεδομένων για διασκέδαση και κέρδος. Από αυτά μπορείτε να λάβετε πληροφορίες τόσο για την άνευ προηγουμένου αξιοπιστία του LMDB, όσο και για την σχεδόν άψογη υλοποίηση των ιδιοτήτων ACID των συναλλαγών, που την ξεπερνά στο ίδιο SQLite.
Ο μινιμαλισμός του LMDB επιτρέπει στη μηχανή αναπαράστασης του κώδικά του να τοποθετηθεί πλήρως στην κρυφή μνήμη L1 του επεξεργαστή με τα χαρακτηριστικά ταχύτητας που προκύπτουν.

Δυστυχώς, στο iOS, τα αρχεία με χαρτογράφηση μνήμης δεν είναι τόσο ρόδινα όσο θα θέλαμε. Για να μιλήσουμε για τα μειονεκτήματα που σχετίζονται με αυτά πιο συνειδητά, είναι απαραίτητο να υπενθυμίσουμε τις γενικές αρχές για την εφαρμογή αυτού του μηχανισμού στα λειτουργικά συστήματα.

Γενικές πληροφορίες σχετικά με αρχεία με χαρτογράφηση μνήμης

Με κάθε εκτελέσιμη εφαρμογή, το λειτουργικό σύστημα συσχετίζει μια οντότητα που ονομάζεται διεργασία. Σε κάθε διαδικασία εκχωρείται ένα συνεχόμενο εύρος διευθύνσεων στις οποίες τοποθετεί όλα όσα χρειάζεται για να λειτουργήσει. Οι χαμηλότερες διευθύνσεις περιέχουν ενότητες με κώδικα και σκληρά κωδικοποιημένα δεδομένα και πόρους. Ακολουθεί το ανοδικά αναπτυσσόμενο μπλοκ του δυναμικού χώρου διευθύνσεων, γνωστό σε εμάς ως σωρό. Περιέχει τις διευθύνσεις των οντοτήτων που εμφανίζονται κατά τη λειτουργία του προγράμματος. Στην κορυφή βρίσκεται η περιοχή της μνήμης που χρησιμοποιείται από τη στοίβα εφαρμογών. Είτε μεγαλώνει είτε συρρικνώνεται, με άλλα λόγια το μέγεθός του έχει και δυναμικό χαρακτήρα. Προκειμένου η στοίβα και ο σωρός να μην πιέζουν και να παρεμβαίνουν μεταξύ τους, χωρίζονται σε διαφορετικά άκρα του χώρου διευθύνσεων. Υπάρχει μια τρύπα μεταξύ των δύο δυναμικών τμημάτων στο επάνω και στο κάτω μέρος. Οι διευθύνσεις σε αυτό το μεσαίο τμήμα χρησιμοποιούνται από το λειτουργικό σύστημα για να συσχετιστούν με μια διαδικασία διαφόρων οντοτήτων. Συγκεκριμένα, μπορεί να αντιστοιχίσει ένα συγκεκριμένο συνεχές σύνολο διευθύνσεων σε ένα αρχείο στο δίσκο. Ένα τέτοιο αρχείο ονομάζεται αρχείο με αντιστοίχιση μνήμης.

Ο χώρος διευθύνσεων που εκχωρείται σε μια διαδικασία είναι τεράστιος. Θεωρητικά, ο αριθμός των διευθύνσεων περιορίζεται μόνο από το μέγεθος του δείκτη, το οποίο καθορίζεται από το bit του συστήματος. Εάν η φυσική μνήμη της είχε εκχωρηθεί 1-σε-1, τότε η πρώτη διαδικασία θα καταβρόχθιζε ολόκληρη τη μνήμη RAM και δεν θα υπήρχε θέμα πολλαπλών εργασιών.

Ωστόσο, γνωρίζουμε εκ πείρας ότι τα σύγχρονα λειτουργικά συστήματα μπορούν να εκτελέσουν όσες διαδικασίες θέλετε ταυτόχρονα. Αυτό είναι δυνατό λόγω του γεγονότος ότι εκχωρούν πολλή μνήμη σε διαδικασίες μόνο σε χαρτί, αλλά στην πραγματικότητα φορτώνουν στην κύρια φυσική μνήμη μόνο εκείνο το μέρος που είναι σε ζήτηση εδώ και τώρα. Επομένως, η μνήμη που σχετίζεται με τη διαδικασία ονομάζεται εικονική.

Το λειτουργικό σύστημα οργανώνει την εικονική και φυσική μνήμη σε σελίδες συγκεκριμένου μεγέθους. Μόλις μια συγκεκριμένη σελίδα εικονικής μνήμης είναι σε ζήτηση, το λειτουργικό σύστημα τη φορτώνει στη φυσική μνήμη και τοποθετεί μια αντιστοιχία μεταξύ τους σε έναν ειδικό πίνακα. Εάν δεν υπάρχουν δωρεάν κουλοχέρηδες, τότε μία από τις σελίδες που έχουν φορτωθεί προηγουμένως αντιγράφεται στο δίσκο και τη θέση της παίρνει η ζητούμενη. Αυτή η διαδικασία, στην οποία θα επανέλθουμε σύντομα, ονομάζεται swapping. Το παρακάτω σχήμα απεικονίζει τη διαδικασία που περιγράφεται. Σε αυτό, φορτώθηκε η σελίδα Α με διεύθυνση 0 και τοποθετήθηκε στην κύρια σελίδα μνήμης με τη διεύθυνση 4. Αυτό το γεγονός αντικατοπτρίστηκε στον πίνακα αντιστοιχίας στον αριθμό κελιού 0.

Με τα αρχεία με χαρτογράφηση μνήμης, η ιστορία είναι ακριβώς η ίδια. Λογικά, υποτίθεται ότι τοποθετούνται συνεχώς και εξ ολοκλήρου στον εικονικό χώρο διευθύνσεων. Ωστόσο, μπαίνουν στη φυσική μνήμη σελίδα προς σελίδα και μόνο κατόπιν ζήτησης. Η τροποποίηση τέτοιων σελίδων συγχρονίζεται με το αρχείο στο δίσκο. Έτσι, μπορείτε να εκτελέσετε I/O αρχείου, απλά δουλεύοντας με byte στη μνήμη - όλες οι αλλαγές θα μεταφερθούν αυτόματα από τον πυρήνα του λειτουργικού συστήματος στο αρχικό αρχείο.

Η παρακάτω εικόνα δείχνει πώς το LMDB συγχρονίζει την κατάστασή του όταν εργάζεται με τη βάση δεδομένων από διαφορετικές διεργασίες. Αντιστοιχίζοντας την εικονική μνήμη διαφορετικών διεργασιών στο ίδιο αρχείο, υποχρεώνουμε εκ των πραγμάτων το λειτουργικό σύστημα να συγχρονίζει μεταβατικά ορισμένα μπλοκ των χώρων διευθύνσεών τους μεταξύ τους, όπου φαίνεται το LMDB.

Μια σημαντική απόχρωση είναι ότι το LMDB τροποποιεί το αρχείο δεδομένων από προεπιλογή μέσω του μηχανισμού κλήσης συστήματος εγγραφής και το ίδιο το αρχείο εμφανίζεται σε λειτουργία μόνο για ανάγνωση. Αυτή η προσέγγιση έχει δύο σημαντικές επιπτώσεις.

Η πρώτη συνέπεια είναι κοινή σε όλα τα λειτουργικά συστήματα. Η ουσία του είναι να προσθέσει προστασία από ακούσια βλάβη στη βάση δεδομένων από λανθασμένο κώδικα. Όπως γνωρίζετε, οι εκτελέσιμες οδηγίες μιας διεργασίας είναι ελεύθερες να έχουν πρόσβαση σε δεδομένα από οπουδήποτε στον χώρο διευθύνσεών της. Ταυτόχρονα, όπως μόλις θυμηθήκαμε, η εμφάνιση ενός αρχείου σε λειτουργία ανάγνωσης-εγγραφής σημαίνει ότι οποιαδήποτε εντολή μπορεί επίσης να το τροποποιήσει επιπλέον. Εάν το κάνει αυτό κατά λάθος, προσπαθώντας, για παράδειγμα, να αντικαταστήσει πραγματικά ένα στοιχείο πίνακα σε ένα ανύπαρκτο ευρετήριο, τότε με αυτόν τον τρόπο μπορεί κατά λάθος να αλλάξει το αρχείο που έχει αντιστοιχιστεί σε αυτήν τη διεύθυνση, κάτι που θα οδηγήσει σε καταστροφή της βάσης δεδομένων. Εάν το αρχείο εμφανίζεται σε λειτουργία μόνο για ανάγνωση, τότε μια προσπάθεια αλλαγής του χώρου διευθύνσεων που αντιστοιχεί σε αυτό θα οδηγήσει σε συντριβή του προγράμματος με το σήμα SIGSEGV, και το αρχείο θα παραμείνει άθικτο.

Η δεύτερη συνέπεια είναι ήδη συγκεκριμένη για το iOS. Ούτε ο συγγραφέας ούτε άλλες πηγές το αναφέρουν ρητά, αλλά χωρίς αυτό, το LMDB θα ήταν ακατάλληλο για εκτέλεση σε αυτό το λειτουργικό σύστημα για κινητά. Η επόμενη ενότητα είναι αφιερωμένη στην εξέτασή της.

Τεχνικά χαρακτηριστικά των αρχείων με αντιστοίχιση μνήμης στο iOS

Το 2018, υπήρξε μια υπέροχη αναφορά στο WWDC Βαθιά κατάδυση μνήμης iOS. Λέει ότι στο iOS όλες οι σελίδες που βρίσκονται στη φυσική μνήμη ανήκουν σε έναν από τους 3 τύπους: βρώμικες, συμπιεσμένες και καθαρές.

Η καθαρή μνήμη είναι μια συλλογή σελίδων που μπορούν να αντικατασταθούν με ασφάλεια από τη φυσική μνήμη. Τα δεδομένα που περιέχουν μπορούν να φορτωθούν εκ νέου από τις αρχικές πηγές τους, όπως απαιτείται. Τα αρχεία που αντιστοιχίζονται με μνήμη μόνο για ανάγνωση ανήκουν σε αυτήν την κατηγορία. Το iOS δεν φοβάται να ξεφορτώσει τις σελίδες που έχουν αντιστοιχιστεί σε ένα αρχείο από τη μνήμη ανά πάσα στιγμή, καθώς είναι εγγυημένο ότι θα συγχρονιστούν με το αρχείο στο δίσκο.

Όλες οι τροποποιημένες σελίδες μπαίνουν σε βρώμικη μνήμη, ανεξάρτητα από το πού βρίσκονται αρχικά. Συγκεκριμένα, τα αρχεία που έχουν αντιστοιχιστεί με μνήμη και τροποποιούνται με εγγραφή στην εικονική μνήμη που σχετίζεται με αυτά θα ταξινομούνται επίσης με αυτόν τον τρόπο. Άνοιγμα LMDB με σημαία MDB_WRITEMAP, αφού κάνετε αλλαγές σε αυτό, μπορείτε να δείτε μόνοι σας.

Μόλις μια εφαρμογή αρχίσει να καταλαμβάνει υπερβολική φυσική μνήμη, το iOS συμπιέζει τις βρώμικες σελίδες της. Η συλλογή της μνήμης που καταλαμβάνεται από βρώμικες και συμπιεσμένες σελίδες είναι το λεγόμενο αποτύπωμα μνήμης της εφαρμογής. Όταν φτάσει σε μια ορισμένη τιμή κατωφλίου, ο δαίμονας του συστήματος δολοφονίας OOM έρχεται μετά τη διαδικασία και την τερματίζει αναγκαστικά. Αυτή είναι η ιδιαιτερότητα του iOS σε σύγκριση με τα λειτουργικά συστήματα για επιτραπέζιους υπολογιστές. Αντίθετα, η μείωση του αποτυπώματος μνήμης με την εναλλαγή σελίδων από φυσική μνήμη σε δίσκο δεν παρέχεται στο iOS. Μπορεί κανείς μόνο να μαντέψει τους λόγους. Ίσως η διαδικασία για την εντατική μετακίνηση σελίδων στο δίσκο και πίσω είναι πολύ ενεργοβόρα για κινητές συσκευές, ή το iOS εξοικονομεί τον πόρο επανεγγραφής κελιών σε μονάδες SSD ή ίσως οι σχεδιαστές δεν ήταν ικανοποιημένοι με τη συνολική απόδοση του συστήματος, όπου όλα είναι ανταλλάσσονται συνεχώς. Όπως και να έχει, το γεγονός παραμένει.

Τα καλά νέα, που αναφέρθηκαν ήδη νωρίτερα, είναι ότι το LMDB δεν χρησιμοποιεί τον μηχανισμό mmap για την ενημέρωση αρχείων από προεπιλογή. Ως εκ τούτου, τα δεδομένα που αποδίδονται ταξινομούνται ως καθαρή μνήμη από το iOS και δεν συμβάλλουν στο αποτύπωμα της μνήμης. Αυτό μπορεί να επαληθευτεί χρησιμοποιώντας το εργαλείο Xcode που ονομάζεται VM Tracker. Το παρακάτω στιγμιότυπο οθόνης δείχνει την κατάσταση εικονικής μνήμης της εφαρμογής iOS Cloud κατά τη λειτουργία. Στην αρχή, 2 στιγμιότυπα LMDB αρχικοποιήθηκαν σε αυτό. Το πρώτο είχε τη δυνατότητα να αντιστοιχίσει το αρχείο του σε 1GiB εικονικής μνήμης, το δεύτερο - 512 MiB. Παρά το γεγονός ότι και οι δύο αποθηκευτικοί χώροι καταλαμβάνουν μια ορισμένη ποσότητα μόνιμης μνήμης, κανένας από τους δύο δεν συμβάλλει στο βρώμικο μέγεθος.

Τώρα ήρθε η ώρα για τα άσχημα νέα. Χάρη στον μηχανισμό swap στα λειτουργικά συστήματα επιτραπέζιου υπολογιστή 64-bit, κάθε διεργασία μπορεί να καταλαμβάνει τόσο χώρο εικονικών διευθύνσεων όσο ο ελεύθερος χώρος στον σκληρό δίσκο επιτρέπει την πιθανή εναλλαγή της. Η αντικατάσταση του swap με τη συμπίεση στο iOS μειώνει δραστικά το θεωρητικό μέγιστο. Τώρα όλες οι ζωντανές διεργασίες πρέπει να χωρούν στην κύρια μνήμη (ανάγνωση RAM) και όλες αυτές που δεν χωρούν υπόκεινται σε αναγκαστικό τερματισμό. Αναφέρεται όπως στα παραπάνω κανω ΑΝΑΦΟΡΑ, και στο επίσημη τεκμηρίωση. Κατά συνέπεια, το iOS περιορίζει σοβαρά την ποσότητα της διαθέσιμης μνήμης για εκχώρηση μέσω mmap. Εδώ εδώ μπορείτε να δείτε τα εμπειρικά όρια της ποσότητας μνήμης που θα μπορούσε να εκχωρηθεί σε διαφορετικές συσκευές χρησιμοποιώντας αυτήν την κλήση συστήματος. Στα πιο σύγχρονα μοντέλα smartphone, το iOS έχει γίνει γενναιόδωρο κατά 2 gigabyte και στις κορυφαίες εκδόσεις του iPad - κατά 4. Στην πράξη, φυσικά, πρέπει να εστιάσετε στα νεότερα υποστηριζόμενα μοντέλα συσκευών, όπου όλα είναι πολύ λυπηρά. Ακόμη χειρότερα, κοιτάζοντας την κατάσταση μνήμης της εφαρμογής στο VM Tracker, θα διαπιστώσετε ότι το LMDB απέχει πολύ από το μόνο που ισχυρίζεται ότι έχει αντιστοιχιστεί μνήμη. Τα καλά κομμάτια καταναλώνονται από τους κατανεμητές συστήματος, τα αρχεία πόρων, τα πλαίσια εικόνων και άλλα μικρότερα αρπακτικά.

Ως αποτέλεσμα πειραμάτων στο Cloud, καταλήξαμε στις ακόλουθες συμβιβαστικές τιμές μνήμης που εκχωρήθηκαν από το LMDB: 384 megabyte για συσκευές 32 bit και 768 για συσκευές 64 bit. Αφού εξαντληθεί αυτός ο τόμος, οποιεσδήποτε τροποποιητικές λειτουργίες αρχίζουν να ολοκληρώνονται με τον κωδικό MDB_MAP_FULL. Παρατηρούμε τέτοια σφάλματα στην παρακολούθησή μας, αλλά είναι αρκετά μικρά ώστε να παραμεληθούν σε αυτό το στάδιο.

Ένας μη προφανής λόγος για την υπερβολική κατανάλωση μνήμης από την αποθήκευση μπορεί να είναι οι μακροχρόνιες συναλλαγές. Για να κατανοήσουμε πώς σχετίζονται αυτά τα δύο φαινόμενα, θα μας βοηθήσει να εξετάσουμε τις υπόλοιπες δύο φάλαινες LMDB.

3.2. Φάλαινα #2. Β+-δέντρο

Για την εξομοίωση πινάκων πάνω από έναν χώρο αποθήκευσης κλειδιού-τιμής, πρέπει να υπάρχουν οι ακόλουθες λειτουργίες στο API του:

Εισαγωγή νέου στοιχείου.
Αναζήτηση για ένα στοιχείο με ένα δεδομένο κλειδί.
Διαγραφή στοιχείου.
Επαναλάβετε τα βασικά διαστήματα με τη σειρά ταξινόμησης τους.

Η απλούστερη δομή δεδομένων που μπορεί εύκολα να εφαρμόσει και τις τέσσερις λειτουργίες είναι ένα δυαδικό δέντρο αναζήτησης. Κάθε κόμβος του είναι ένα κλειδί που χωρίζει ολόκληρο το υποσύνολο των θυγατρικών κλειδιών σε δύο υποδέντρα. Στα αριστερά είναι εκείνα που είναι μικρότερα από τον γονέα, και στα δεξιά - αυτά που είναι μεγαλύτερα. Η απόκτηση ενός παραγγελθέντος σετ κλειδιών επιτυγχάνεται μέσω μιας από τις κλασικές διασχίσεις δέντρων.

Τα δυαδικά δέντρα έχουν δύο βασικά μειονεκτήματα που τα εμποδίζουν να είναι αποτελεσματικά ως δομή δεδομένων δίσκου. Πρώτον, ο βαθμός της ισορροπίας τους είναι απρόβλεπτος. Υπάρχει σημαντικός κίνδυνος απόκτησης δέντρων στα οποία το ύψος διαφορετικών κλαδιών μπορεί να ποικίλλει πολύ, γεγονός που επιδεινώνει σημαντικά την αλγοριθμική πολυπλοκότητα της αναζήτησης σε σύγκριση με την αναμενόμενη. Δεύτερον, η αφθονία των διασταυρούμενων συνδέσεων μεταξύ των κόμβων στερεί από τα δυαδικά δέντρα την εντοπιότητα στη μνήμη.Οι κλειστοί κόμβοι (από την άποψη των συνδέσεων μεταξύ τους) μπορούν να βρίσκονται σε εντελώς διαφορετικές σελίδες στην εικονική μνήμη. Κατά συνέπεια, ακόμη και μια απλή διέλευση πολλών γειτονικών κόμβων σε ένα δέντρο μπορεί να απαιτεί την επίσκεψη συγκρίσιμου αριθμού σελίδων. Αυτό είναι ένα πρόβλημα ακόμα και όταν μιλάμε για την αποτελεσματικότητα των δυαδικών δέντρων ως δομή δεδομένων στη μνήμη, καθώς η συνεχής περιστροφή σελίδων στη μνήμη cache του επεξεργαστή δεν είναι φθηνή. Όταν πρόκειται για τη συχνή ανύψωση σελίδων που σχετίζονται με κόμβους από το δίσκο, τα πράγματα γίνονται πολύ άσχημα. αξιοθρήνητος.

Τα Β-δέντρα, όντας μια εξέλιξη δυαδικών δέντρων, λύνουν τα προβλήματα που εντοπίστηκαν στην προηγούμενη παράγραφο. Πρώτον, εξισορροπούνται. Δεύτερον, κάθε κόμβος τους χωρίζει το σύνολο των θυγατρικών κλειδιών όχι σε 2, αλλά σε υποσύνολα διατεταγμένα σε M, και ο αριθμός M μπορεί να είναι αρκετά μεγάλος, της τάξης πολλών εκατοντάδων ή και χιλιάδων.

Εκ τούτου:

Κάθε κόμβος έχει μεγάλο αριθμό ήδη παραγγελθέντων κλειδιών και τα δέντρα είναι πολύ χαμηλά.
Το δέντρο αποκτά την ιδιότητα της εντοπιότητας στη μνήμη, αφού τα κλειδιά που έχουν κοντινή αξία βρίσκονται φυσικά το ένα δίπλα στο άλλο σε έναν ή γειτονικούς κόμβους.
Μειώνει τον αριθμό των κόμβων διέλευσης κατά την κάθοδο του δέντρου κατά τη διάρκεια μιας επιχείρησης αναζήτησης.
Μειώνει τον αριθμό των κόμβων-στόχων που διαβάζονται για ερωτήματα εύρους, καθώς καθένας από αυτούς περιέχει ήδη μεγάλο αριθμό διατεταγμένων κλειδιών.

Το LMDB χρησιμοποιεί μια παραλλαγή του Β-δέντρου που ονομάζεται δέντρο B+ για την αποθήκευση δεδομένων. Το παραπάνω διάγραμμα δείχνει τους τρεις τύπους κόμβων που περιέχει:

Στην κορυφή βρίσκεται η ρίζα. Δεν υλοποιείται τίποτα περισσότερο από την έννοια της βάσης δεδομένων μέσα σε ένα αποθετήριο. Μέσα σε μία μόνο παρουσία LMDB, μπορείτε να δημιουργήσετε πολλές βάσεις δεδομένων που μοιράζονται τον αντιστοιχισμένο χώρο εικονικών διευθύνσεων. Κάθε ένα από αυτά ξεκινά από τη δική του ρίζα.
Στο χαμηλότερο επίπεδο βρίσκονται τα φύλλα (φύλλο). Είναι αυτοί και μόνο αυτοί που περιέχουν τα ζεύγη κλειδιών-τιμών που είναι αποθηκευμένα στη βάση δεδομένων. Παρεμπιπτόντως, αυτή είναι η ιδιαιτερότητα των Β+-δέντρων. Εάν ένα κανονικό δέντρο Β αποθηκεύει τα μέρη-τιμές στους κόμβους όλων των επιπέδων, τότε η παραλλαγή Β+ είναι μόνο στο χαμηλότερο. Έχοντας διορθώσει αυτό το γεγονός, σε αυτό που ακολουθεί θα ονομάσουμε τον υποτύπο του δέντρου που χρησιμοποιείται στο LMDB απλά B-tree.
Μεταξύ της ρίζας και των φύλλων, υπάρχουν 0 ή περισσότερα τεχνικά επίπεδα με κόμβους πλοήγησης (κλαδιά). Το καθήκον τους είναι να μοιράσουν το ταξινομημένο σύνολο κλειδιών μεταξύ των φύλλων.

Φυσικά, οι κόμβοι είναι μπλοκ μνήμης προκαθορισμένου μήκους. Το μέγεθός τους είναι πολλαπλάσιο του μεγέθους των σελίδων μνήμης στο λειτουργικό σύστημα, για το οποίο μιλήσαμε παραπάνω. Η δομή του κόμβου φαίνεται παρακάτω. Η κεφαλίδα περιέχει μετα-πληροφορίες, η πιο προφανής από τις οποίες, για παράδειγμα, είναι το άθροισμα ελέγχου. Στη συνέχεια έρχονται πληροφορίες σχετικά με τις μετατοπίσεις, κατά μήκος των οποίων βρίσκονται τα κελιά με δεδομένα. Ο ρόλος των δεδομένων μπορεί να είναι είτε πλήκτρα, αν μιλάμε για κόμβους πλοήγησης, είτε ολόκληρα ζεύγη κλειδιών-τιμών στην περίπτωση των φύλλων. Μπορείτε να διαβάσετε περισσότερα για τη δομή των σελίδων στο έργο "Αξιολόγηση καταστημάτων υψηλής απόδοσης βασικής αξίας".

Έχοντας ασχοληθεί με το εσωτερικό περιεχόμενο των κόμβων σελίδας, θα αναπαραστήσουμε περαιτέρω το LMDB B-tree με απλοποιημένο τρόπο στην ακόλουθη μορφή.

Οι σελίδες με κόμβους διατάσσονται διαδοχικά στο δίσκο. Οι σελίδες με μεγαλύτερο αριθμό βρίσκονται στο τέλος του αρχείου. Η λεγόμενη μετα-σελίδα (μετασελίδα) περιέχει πληροφορίες σχετικά με τις μετατοπίσεις, οι οποίες μπορούν να χρησιμοποιηθούν για την εύρεση των ριζών όλων των δέντρων. Όταν ανοίγει ένα αρχείο, το LMDB σαρώνει το αρχείο σελίδα προς σελίδα από το τέλος προς την αρχή αναζητώντας μια έγκυρη μετα-σελίδα και βρίσκει τις υπάρχουσες βάσεις δεδομένων μέσω αυτής.

Τώρα, έχοντας μια ιδέα της λογικής και φυσικής δομής της οργάνωσης δεδομένων, μπορούμε να προχωρήσουμε στην εξέταση της τρίτης φάλαινας του LMDB. Με τη βοήθειά του γίνονται όλες οι τροποποιήσεις αποθήκευσης συναλλακτικά και μεμονωμένα μεταξύ τους, δίνοντας στη βάση δεδομένων στο σύνολό της επίσης την ιδιότητα πολλαπλών εκδόσεων.

3.3. Φάλαινα #3. αντιγραφή σε εγγραφή

Ορισμένες λειτουργίες B-tree περιλαμβάνουν την πραγματοποίηση μιας ολόκληρης σειράς αλλαγών στους κόμβους του. Ένα παράδειγμα είναι η προσθήκη ενός νέου κλειδιού σε έναν κόμβο που έχει ήδη φτάσει τη μέγιστη χωρητικότητά του. Σε αυτήν την περίπτωση, είναι απαραίτητο, πρώτον, να χωριστεί ο κόμβος στα δύο και, δεύτερον, να προστεθεί ένας σύνδεσμος στον νέο αποσπασμένο θυγατρικό κόμβο στον γονέα του. Αυτή η διαδικασία είναι δυνητικά πολύ επικίνδυνη. Εάν για κάποιο λόγο (σύγκρουση, διακοπή ρεύματος, κ.λπ.) συμβεί μόνο ένα μέρος των αλλαγών από τη σειρά, τότε το δέντρο θα παραμείνει σε ασυνεπή κατάσταση.

Μια παραδοσιακή λύση για να κάνετε μια βάση δεδομένων ανεκτική σε σφάλματα είναι να προσθέσετε μια πρόσθετη δομή δεδομένων που βασίζεται σε δίσκο, το αρχείο καταγραφής συναλλαγών, γνωστό και ως καταγραφή προκαταβολών εγγραφής (WAL), δίπλα στο δέντρο B. Είναι ένα αρχείο, στο τέλος του οποίου, αυστηρά πριν από την τροποποίηση του ίδιου του Β-δέντρου, αναγράφεται η προβλεπόμενη λειτουργία. Έτσι, εάν εντοπιστεί καταστροφή δεδομένων κατά τη διάρκεια της αυτοδιάγνωσης, η βάση δεδομένων συμβουλεύεται το αρχείο καταγραφής για να καθαριστεί.

Η LMDB έχει επιλέξει μια διαφορετική μέθοδο ως μηχανισμό ανοχής σφαλμάτων, η οποία ονομάζεται αντιγραφή σε εγγραφή. Η ουσία του είναι ότι αντί να ενημερώνει τα δεδομένα σε μια υπάρχουσα σελίδα, πρώτα τα αντιγράφει πλήρως και κάνει όλες τις τροποποιήσεις ήδη στο αντίγραφο.

Επιπλέον, για να είναι διαθέσιμα τα ενημερωμένα δεδομένα, είναι απαραίτητο να αλλάξετε τη σύνδεση με τον κόμβο που έχει γίνει ενημερωμένος στον γονικό κόμβο σε σχέση με αυτόν. Δεδομένου ότι πρέπει επίσης να τροποποιηθεί για αυτό, έχει επίσης αντιγραφεί εκ των προτέρων. Η διαδικασία συνεχίζεται αναδρομικά μέχρι τη ρίζα. Τα δεδομένα στη μετα-σελίδα είναι τα τελευταία που αλλάζουν.

Εάν ξαφνικά η διεργασία διακοπεί κατά τη διαδικασία ενημέρωσης, τότε είτε δεν θα δημιουργηθεί μια νέα μετα-σελίδα, είτε δεν θα γραφτεί στο δίσκο μέχρι το τέλος και το άθροισμα ελέγχου θα είναι λανθασμένο. Σε οποιαδήποτε από αυτές τις δύο περιπτώσεις, οι νέες σελίδες δεν θα είναι προσβάσιμες και οι παλιές δεν θα επηρεαστούν. Αυτό εξαλείφει την ανάγκη για το LMDB να εγγράφει ημερολόγιο για να διατηρεί τη συνέπεια των δεδομένων. Εκ των πραγμάτων, η δομή της αποθήκευσης δεδομένων στο δίσκο, που περιγράφηκε παραπάνω, αναλαμβάνει ταυτόχρονα τη λειτουργία της. Η απουσία σαφούς αρχείου καταγραφής συναλλαγών είναι ένα από τα χαρακτηριστικά του LMDB, το οποίο παρέχει υψηλή ταχύτητα ανάγνωσης δεδομένων.

Η προκύπτουσα κατασκευή, που ονομάζεται B-tree μόνο με προσθήκη, παρέχει φυσικά απομόνωση συναλλαγών και πολλαπλές εκδόσεις. Στο LMDB, κάθε ανοιχτή συναλλαγή έχει μια ενημερωμένη ρίζα δέντρου που σχετίζεται με αυτήν. Εφόσον η συναλλαγή δεν έχει ολοκληρωθεί, οι σελίδες του δέντρου που συσχετίζονται με αυτό δεν θα αλλάξουν ποτέ ή δεν θα επαναχρησιμοποιηθούν για νέες εκδόσεις δεδομένων. Έτσι, μπορείτε να εργαστείτε για όσο διάστημα θέλετε ακριβώς με το σύνολο δεδομένων που ήταν σχετικό στο τη στιγμή που άνοιξε η συναλλαγή, ακόμα κι αν ο χώρος αποθήκευσης συνεχίζει να ενημερώνεται ενεργά αυτήν τη στιγμή. Αυτή είναι η ουσία της πολλαπλής έκδοσης, καθιστώντας το LMDB ιδανική πηγή δεδομένων για την αγαπημένη μας UICollectionView. Αφού ανοίξετε μια συναλλαγή, δεν χρειάζεται να αυξήσετε το αποτύπωμα μνήμης της εφαρμογής, αντλώντας βιαστικά τα τρέχοντα δεδομένα σε κάποια δομή στη μνήμη, φοβούμενοι να μην μείνετε χωρίς τίποτα. Αυτό το χαρακτηριστικό ξεχωρίζει το LMDB από το ίδιο SQLite, το οποίο δεν μπορεί να καυχηθεί για τέτοια πλήρη απομόνωση. Αφού ανοίξετε δύο συναλλαγές στην τελευταία και διαγράψετε μια συγκεκριμένη εγγραφή σε μία από αυτές, η ίδια εγγραφή δεν μπορεί πλέον να αποκτηθεί στη δεύτερη εναπομείνασα.

Η άλλη όψη του νομίσματος είναι η δυνητικά σημαντικά υψηλότερη κατανάλωση εικονικής μνήμης. Η διαφάνεια δείχνει πώς θα μοιάζει η δομή της βάσης δεδομένων εάν τροποποιηθεί ταυτόχρονα με 3 ανοιχτές συναλλαγές ανάγνωσης που εξετάζουν διαφορετικές εκδόσεις της βάσης δεδομένων. Εφόσον το LMDB δεν μπορεί να επαναχρησιμοποιήσει κόμβους που είναι προσβάσιμοι από τις ρίζες που σχετίζονται με τις πραγματικές συναλλαγές, η αποθήκευση δεν έχει άλλη επιλογή από το να εκχωρήσει μια άλλη τέταρτη ρίζα στη μνήμη και να κλωνοποιήσει ξανά τις τροποποιημένες σελίδες κάτω από αυτήν.

Εδώ δεν θα είναι περιττό να ανακαλέσετε την ενότητα για αρχεία που έχουν αντιστοιχιστεί με μνήμη. Φαίνεται ότι η επιπλέον κατανάλωση εικονικής μνήμης δεν πρέπει να μας ενοχλεί ιδιαίτερα, αφού δεν συμβάλλει στο αποτύπωμα μνήμης της εφαρμογής. Ωστόσο, την ίδια στιγμή, σημειώθηκε ότι το iOS είναι πολύ τσιγκούνικο στην εκχώρηση του και δεν μπορούμε να παρέχουμε μια περιοχή LMDB 1 terabyte σε διακομιστή ή επιφάνεια εργασίας από τον ώμο του πλοιάρχου και να μην σκεφτόμαστε καθόλου αυτό το χαρακτηριστικό. Όταν είναι δυνατόν, θα πρέπει να προσπαθείτε να διατηρείτε τη διάρκεια ζωής των συναλλαγών όσο το δυνατόν μικρότερη.

4. Σχεδιασμός σχήματος δεδομένων πάνω από το API κλειδιού-τιμής

Ας ξεκινήσουμε την ανάλυση του API εξετάζοντας τις βασικές αφαιρέσεις που παρέχονται από το LMDB: περιβάλλον και βάσεις δεδομένων, κλειδιά και τιμές, συναλλαγές και δρομείς.

Σημείωση σχετικά με τις καταχωρίσεις κωδικών

Όλες οι συναρτήσεις στο δημόσιο API LMDB επιστρέφουν το αποτέλεσμα της εργασίας τους με τη μορφή κωδικού σφάλματος, αλλά σε όλες τις επόμενες καταχωρίσεις ο έλεγχος του παραλείπεται για λόγους συνοπτικής. Στην πράξη, χρησιμοποιήσαμε τον δικό μας κώδικα για να αλληλεπιδράσουμε με το αποθετήριο. πιρούνι Περιτυλίγματα C++ lmdbxx, στο οποίο τα σφάλματα υλοποιούνται ως εξαιρέσεις C++.

Ως ο ταχύτερος τρόπος σύνδεσης LMDB σε έργο iOS ή macOS, προσφέρω το CocoaPod μου POSLMDB.

4.1. Βασικές αφαιρέσεις

περιβάλλον

Δομή MDB_env is είναι το αποθετήριο της εσωτερικής κατάστασης του LMDB. Οικογένεια προκαθορισμένων συναρτήσεων mdb_env σας επιτρέπει να διαμορφώσετε ορισμένες από τις ιδιότητές του. Στην απλούστερη περίπτωση, η προετοιμασία του κινητήρα μοιάζει με αυτό.

mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512)
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);

Στην εφαρμογή Mail.ru Cloud, αλλάξαμε τις προεπιλεγμένες τιμές μόνο για δύο παραμέτρους.

Το πρώτο είναι το μέγεθος του χώρου εικονικών διευθύνσεων στον οποίο αντιστοιχίζεται το αρχείο αποθήκευσης. Δυστυχώς, ακόμη και στην ίδια συσκευή, η συγκεκριμένη τιμή μπορεί να διαφέρει σημαντικά από εκτέλεση σε εκτέλεση. Για να λάβουμε υπόψη αυτή τη δυνατότητα του iOS, επιλέγουμε δυναμικά το μέγιστο αποθηκευτικό χώρο. Ξεκινώντας από μια συγκεκριμένη τιμή, μειώνεται διαδοχικά στο μισό μέχρι τη συνάρτηση mdb_env_open δεν θα επιστρέψει αποτέλεσμα άλλο από ENOMEM. Θεωρητικά, υπάρχει ο αντίθετος τρόπος - πρώτα εκχωρήστε μια ελάχιστη μνήμη στον κινητήρα και, στη συνέχεια, όταν ληφθούν σφάλματα MDB_MAP_FULL, αυξήστε το. Ωστόσο, είναι πολύ πιο ακανθώδες. Ο λόγος είναι ότι η διαδικασία επαναχαρτογράφησης μνήμης με χρήση της συνάρτησης mdb_env_set_map_size ακυρώνει όλες τις οντότητες (δρομείς, συναλλαγές, κλειδιά και τιμές) που ελήφθησαν νωρίτερα από τον κινητήρα. Η καταγραφή μιας τέτοιας εξέλιξης γεγονότων στον κώδικα θα οδηγήσει σε σημαντική περιπλοκή του. Εάν, ωστόσο, η εικονική μνήμη σας είναι πολύ αγαπητή, τότε αυτός μπορεί να είναι ένας λόγος για να δείτε το πιρούνι που έχει πάει πολύ μπροστά. MDBX, όπου μεταξύ των δηλωμένων χαρακτηριστικών υπάρχει "αυτόματη προσαρμογή μεγέθους βάσης δεδομένων on the fly".

Η δεύτερη παράμετρος, η προεπιλεγμένη τιμή της οποίας δεν μας ταίριαζε, ρυθμίζει τη μηχανική διασφάλισης της ασφάλειας του νήματος. Δυστυχώς, τουλάχιστον στο iOS 10, υπάρχουν προβλήματα με την υποστήριξη τοπικής αποθήκευσης νημάτων. Για το λόγο αυτό, στο παραπάνω παράδειγμα, το αποθετήριο ανοίγει με τη σημαία MDB_NOTLS. Επιπλέον, απαιτούσε επίσης πιρούνι Περιτύλιγμα C++ lmdbxxγια να κόψετε μεταβλητές με και σε αυτό το χαρακτηριστικό.

Βάση δεδομένων

Η βάση δεδομένων είναι ένα ξεχωριστό παράδειγμα του Β-δέντρου για το οποίο μιλήσαμε παραπάνω. Το άνοιγμά του γίνεται μέσα σε μια συναλλαγή, κάτι που στην αρχή μπορεί να φαίνεται λίγο περίεργο.

MDB_txn *txn;
MDB_dbi dbi;
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);
mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);
mdb_txn_abort(txn);

Πράγματι, μια συναλλαγή στο LMDB είναι μια οντότητα αποθήκευσης, όχι μια συγκεκριμένη βάση δεδομένων. Αυτή η ιδέα σάς επιτρέπει να εκτελείτε ατομικές λειτουργίες σε οντότητες που βρίσκονται σε διαφορετικές βάσεις δεδομένων. Θεωρητικά, αυτό ανοίγει τη δυνατότητα μοντελοποίησης πινάκων με τη μορφή διαφορετικών βάσεων δεδομένων, αλλά κάποια στιγμή πήγα στον άλλο δρόμο, που περιγράφεται λεπτομερώς παρακάτω.

Κλειδιά και αξίες

Δομή MDB_val μοντελοποιεί την έννοια τόσο του κλειδιού όσο και μιας τιμής. Το αποθετήριο δεν έχει ιδέα για τη σημασιολογία τους. Για αυτήν, κάτι που είναι διαφορετικό είναι απλώς ένας πίνακας byte ενός δεδομένου μεγέθους. Το μέγιστο μέγεθος κλειδιού είναι 512 byte.

typedef struct MDB_val {
    size_t mv_size;
    void *mv_data;
} MDB_val;

Το κατάστημα χρησιμοποιεί έναν συγκριτικό για να ταξινομήσει τα κλειδιά σε αύξουσα σειρά. Εάν δεν το αντικαταστήσετε με το δικό σας, τότε θα χρησιμοποιηθεί η προεπιλεγμένη, η οποία τα ταξινομεί byte-byte με λεξικογραφική σειρά.

Συναλλαγές

Η συσκευή συναλλαγής περιγράφεται λεπτομερώς στο προηγούμενο κεφάλαιο, οπότε εδώ θα επαναλάβω τις κύριες ιδιότητές τους σε μια σύντομη γραμμή:

Υποστήριξη για όλες τις βασικές ιδιότητες ΟΞΥΛέξεις κλειδιά: ατομικότητα, συνέπεια, απομόνωση και αξιοπιστία. Δεν μπορώ να μην σημειώσω ότι όσον αφορά την αντοχή σε macOS και iOS υπάρχει ένα σφάλμα που διορθώθηκε στο MDBX. Μπορείτε να διαβάσετε περισσότερα σε αυτά README.
Η προσέγγιση της πολυνηματικής σύνδεσης περιγράφεται από το σχήμα «μονός συγγραφέας / πολλαπλοί αναγνώστες». Οι συγγραφείς μπλοκάρουν ο ένας τον άλλον, αλλά δεν μπλοκάρουν τους αναγνώστες. Οι αναγνώστες δεν μπλοκάρουν τους συγγραφείς ή ο ένας τον άλλον.
Υποστήριξη για ένθετες συναλλαγές.
Υποστήριξη πολλαπλών εκδόσεων.

Η πολλαπλή έκδοση στο LMDB είναι τόσο καλή που θέλω να την αποδείξω στην πράξη. Ο παρακάτω κώδικας δείχνει ότι κάθε συναλλαγή λειτουργεί ακριβώς με την έκδοση της βάσης δεδομένων που ήταν σχετική κατά το άνοιγμά της, απομονωμένη πλήρως από όλες τις επόμενες αλλαγές. Η εκκίνηση του αποθετηρίου και η προσθήκη μιας δοκιμαστικής εγγραφής σε αυτό δεν έχει κανένα ενδιαφέρον, επομένως αυτά τα τελετουργικά παραμένουν κάτω από το spoiler.

Προσθήκη δοκιμαστικής καταχώρισης

MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;

mdb_env_create(&env);
mdb_env_open(env, "./testdb", MDB_NOTLS, 0664);

mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);

char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;

int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;

mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);

MDB_txn *txn1, *txn2, *txn3;
MDB_val val;

// Открываем 2 транзакции, каждая из которых смотрит
// на версию базы данных с одной записью.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only

// В рамках первой транзакции удаляем из базы данных существующую в ней запись.
mdb_del(txn1, dbi, &key, NULL);
// Фиксируем удаление.
mdb_txn_commit(txn1);

// Открываем третью транзакцию, которая смотрит на
// актуальную версию базы данных, где записи уже нет.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Убеждаемся, что запись по искомому ключу уже не существует.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Завершаем транзакцию.
mdb_txn_abort(txn3);

// Убеждаемся, что в рамках второй транзакции, открытой на момент
// существования записи в базе данных, её всё ещё можно найти по ключу.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
assert(*(int *)val.mv_data == 997);
// Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
mdb_txn_abort(txn2);

Προαιρετικά, προτείνω να δοκιμάσετε το ίδιο κόλπο με το SQLite και να δείτε τι θα συμβεί.

Η πολλαπλή έκδοση φέρνει πολύ ωραία οφέλη στη ζωή ενός προγραμματιστή iOS. Χρησιμοποιώντας αυτήν την ιδιότητα, μπορείτε εύκολα και φυσικά να προσαρμόσετε τον ρυθμό ενημέρωσης της πηγής δεδομένων για φόρμες οθόνης με βάση τις εκτιμήσεις της εμπειρίας χρήστη. Για παράδειγμα, ας πάρουμε μια τέτοια δυνατότητα της εφαρμογής Mail.ru Cloud όπως η αυτόματη φόρτωση περιεχομένου από τη συλλογή πολυμέσων του συστήματος. Με μια καλή σύνδεση, ο πελάτης μπορεί να προσθέσει πολλές φωτογραφίες ανά δευτερόλεπτο στον διακομιστή. Εάν ενημερώνετε μετά από κάθε λήψη UICollectionView Με περιεχόμενο πολυμέσων στο cloud του χρήστη, μπορείτε να ξεχάσετε περίπου 60 fps και να κάνετε ομαλή κύλιση κατά τη διάρκεια αυτής της διαδικασίας. Για να αποτρέψετε συχνές ενημερώσεις οθόνης, πρέπει να περιορίσετε με κάποιο τρόπο τον ρυθμό αλλαγής δεδομένων στη βάση UICollectionViewDataSource.

Εάν η βάση δεδομένων δεν υποστηρίζει πολλαπλές εκδόσεις και σας επιτρέπει να εργάζεστε μόνο με την τρέχουσα κατάσταση, τότε για να δημιουργήσετε ένα στιγμιότυπο δεδομένων σταθερής χρόνου, πρέπει να το αντιγράψετε είτε σε κάποια δομή δεδομένων στη μνήμη είτε σε έναν προσωρινό πίνακα. Οποιαδήποτε από αυτές τις προσεγγίσεις είναι πολύ ακριβή. Στην περίπτωση της αποθήκευσης στη μνήμη, λαμβάνουμε τόσο το κόστος μνήμης που προκαλείται από την αποθήκευση κατασκευασμένων αντικειμένων όσο και το κόστος χρόνου που σχετίζεται με περιττούς μετασχηματισμούς ORM. Όσο για το προσωρινό τραπέζι, αυτό είναι μια ακόμη πιο ακριβή απόλαυση, που έχει νόημα μόνο σε μη ασήμαντες περιπτώσεις.

Το Multiversioning LMDB λύνει το πρόβλημα της διατήρησης μιας σταθερής πηγής δεδομένων με πολύ κομψό τρόπο. Αρκεί απλώς να ανοίξετε μια συναλλαγή και voila - μέχρι να την ολοκληρώσουμε, το σύνολο δεδομένων είναι εγγυημένο ότι θα διορθωθεί. Η λογική του ρυθμού ενημέρωσης είναι πλέον εξ ολοκλήρου στα χέρια του επιπέδου παρουσίασης, χωρίς επιβάρυνση σημαντικών πόρων.

Δρομείς

Οι δρομείς παρέχουν έναν μηχανισμό για τακτική επανάληψη σε ζεύγη κλειδιών-τιμών διασχίζοντας ένα δέντρο Β. Χωρίς αυτούς, θα ήταν αδύνατο να μοντελοποιήσουμε αποτελεσματικά τους πίνακες στη βάση δεδομένων, στους οποίους τώρα στραφούμε.

4.2. Μοντελοποίηση πίνακα

Η ιδιότητα παραγγελίας κλειδιού σάς επιτρέπει να δημιουργήσετε μια αφαίρεση ανώτατου επιπέδου, όπως έναν πίνακα πάνω από βασικές αφαιρέσεις. Ας εξετάσουμε αυτή τη διαδικασία στο παράδειγμα του κύριου πίνακα του προγράμματος-πελάτη cloud, στον οποίο αποθηκεύονται στην προσωρινή μνήμη πληροφορίες για όλα τα αρχεία και τους φακέλους του χρήστη.

Σχήμα πίνακα

Ένα από τα κοινά σενάρια για τα οποία η δομή ενός πίνακα με ένα δέντρο φακέλων θα πρέπει να οξύνεται είναι η επιλογή όλων των στοιχείων που βρίσκονται μέσα σε έναν δεδομένο κατάλογο.Ένα καλό μοντέλο οργάνωσης δεδομένων για αποτελεσματικά ερωτήματα αυτού του είδους είναι Λίστα ικανοτήτων. Για να το εφαρμόσετε πάνω από τον χώρο αποθήκευσης κλειδιού-τιμής, είναι απαραίτητο να ταξινομήσετε τα κλειδιά των αρχείων και των φακέλων με τέτοιο τρόπο ώστε να ομαδοποιούνται με βάση το ότι ανήκουν στον γονικό κατάλογο. Επιπλέον, για να εμφανιστούν τα περιεχόμενα του καταλόγου με τη μορφή που είναι γνωστή σε έναν χρήστη των Windows (πρώτα οι φάκελοι και μετά τα αρχεία, και τα δύο ταξινομούνται αλφαβητικά), είναι απαραίτητο να συμπεριλάβετε τα αντίστοιχα πρόσθετα πεδία στο κλειδί.

Η παρακάτω εικόνα δείχνει πώς, με βάση την εργασία, μπορεί να μοιάζει η αναπαράσταση των κλειδιών ως πίνακας byte. Πρώτα τοποθετούνται τα byte με το αναγνωριστικό γονικού καταλόγου (κόκκινο), μετά με τον τύπο (πράσινο) και ήδη στην ουρά με το όνομα (μπλε). Ταξινομημένα με βάση τον προεπιλεγμένο συγκριτή LMDB με λεξικογραφική σειρά, ταξινομούνται σε τον απαιτούμενο τρόπο. Η διαδοχική διέλευση κλειδιών με το ίδιο κόκκινο πρόθεμα μας δίνει τις τιμές που σχετίζονται με αυτά με τη σειρά με την οποία θα πρέπει να εμφανίζονται στη διεπαφή χρήστη (δεξιά), χωρίς να απαιτείται πρόσθετη μετα-επεξεργασία.

Σειριοποίηση κλειδιών και τιμών

Υπάρχουν πολλές μέθοδοι σειριοποίησης αντικειμένων σε όλο τον κόσμο. Δεδομένου ότι δεν είχαμε άλλη απαίτηση εκτός από την ταχύτητα, επιλέξαμε την ταχύτερη δυνατή για εμάς - μια ένδειξη μνήμης που καταλαμβάνεται από μια παρουσία της δομής της γλώσσας C. Έτσι, το κλειδί ενός στοιχείου καταλόγου μπορεί να μοντελοποιηθεί από την ακόλουθη δομή NodeKey.

typedef struct NodeKey {
    EntityId parentId;
    uint8_t type;
    uint8_t nameBuffer[256];
} NodeKey;

Να σώσω NodeKey σε αποθήκευση ανάγκη σε αντικείμενο MDB_val τοποθετήστε τον δείκτη στα δεδομένα στη διεύθυνση της αρχής της δομής και υπολογίστε το μέγεθός τους με τη συνάρτηση sizeof.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = sizeof(NodeKey),
        .mv_data = (void *)key
    };
}

Στο πρώτο κεφάλαιο για τα κριτήρια επιλογής βάσεων δεδομένων, ανέφερα την ελαχιστοποίηση των δυναμικών εκχωρήσεων ως μέρος των λειτουργιών CRUD ως σημαντικό παράγοντα επιλογής. Κωδικός λειτουργίας serialize δείχνει πώς, στην περίπτωση του LMDB, μπορούν να αποφευχθούν εντελώς όταν εισάγονται νέες εγγραφές στη βάση δεδομένων. Ο εισερχόμενος πίνακας byte από τον διακομιστή μετατρέπεται πρώτα σε δομές στοίβας και στη συνέχεια απορρίπτονται επιπόλαια στον χώρο αποθήκευσης. Δεδομένου ότι δεν υπάρχουν επίσης δυναμικές εκχωρήσεις στο LMDB, μπορείτε να έχετε μια φανταστική κατάσταση σύμφωνα με τα πρότυπα του iOS - χρησιμοποιήστε μόνο στοίβα μνήμη για να εργαστείτε με δεδομένα σε όλη τη διαδρομή από το δίκτυο μέχρι το δίσκο!

Παραγγελία κλειδιών με δυαδικό συγκριτή

Η σχέση σειράς κλειδιών δίνεται από μια ειδική συνάρτηση που ονομάζεται συγκριτής. Δεδομένου ότι ο κινητήρας δεν γνωρίζει τίποτα για τη σημασιολογία των byte που περιέχουν, ο προεπιλεγμένος συγκριτής δεν έχει άλλη επιλογή από το να τακτοποιήσει τα κλειδιά με λεξικογραφική σειρά, καταφεύγοντας στη σύγκρισή τους byte-by-byte. Η χρήση του για τη διευθέτηση δομών είναι παρόμοια με το ξύρισμα με ένα τσεκούρι σκαλίσματος. Ωστόσο, σε απλές περιπτώσεις, βρίσκω αυτή τη μέθοδο αποδεκτή. Η εναλλακτική περιγράφεται παρακάτω, αλλά εδώ θα σημειώσω μερικές ρακές διάσπαρτες στην πορεία.

Το πρώτο πράγμα που πρέπει να θυμάστε είναι η αναπαράσταση μνήμης πρωτόγονων τύπων δεδομένων. Έτσι, σε όλες τις συσκευές Apple, οι ακέραιες μεταβλητές αποθηκεύονται στη μορφή Μικρό Endian. Αυτό σημαίνει ότι το λιγότερο σημαντικό byte θα βρίσκεται στα αριστερά και δεν θα μπορείτε να ταξινομήσετε ακέραιους αριθμούς χρησιμοποιώντας τη σύγκρισή τους byte-by-byte. Για παράδειγμα, εάν προσπαθήσετε να το κάνετε αυτό με ένα σύνολο αριθμών από το 0 έως το 511 θα έχετε το ακόλουθο αποτέλεσμα.

// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)

Για να λυθεί αυτό το πρόβλημα, οι ακέραιοι αριθμοί πρέπει να αποθηκευτούν στο κλειδί σε μια μορφή κατάλληλη για τον συγκριτή byte. Οι λειτουργίες από την οικογένεια θα βοηθήσουν να πραγματοποιηθεί ο απαραίτητος μετασχηματισμός. hton* (συγκεκριμένα htons για αριθμούς διπλού byte από το παράδειγμα).

Η μορφή για την αναπαράσταση συμβολοσειρών στον προγραμματισμό είναι, όπως γνωρίζετε, ένα σύνολο Ιστορία. Εάν η σημασιολογία των συμβολοσειρών, καθώς και η κωδικοποίηση που χρησιμοποιείται για την αναπαράστασή τους στη μνήμη, υποδηλώνουν ότι μπορεί να υπάρχουν περισσότερα από ένα byte ανά χαρακτήρα, τότε είναι καλύτερα να εγκαταλείψετε αμέσως την ιδέα της χρήσης ενός προεπιλεγμένου συγκριτή.

Το δεύτερο πράγμα που πρέπει να έχετε κατά νου είναι αρχές ευθυγράμμισης struct μεταγλωττιστή πεδίου. Εξαιτίας αυτών, τα byte με τιμές σκουπιδιών μπορούν να σχηματιστούν στη μνήμη μεταξύ των πεδίων, κάτι που, φυσικά, διακόπτει την ταξινόμηση byte. Για να εξαλείψετε τα σκουπίδια, πρέπει είτε να δηλώσετε τα πεδία με αυστηρά καθορισμένη σειρά, έχοντας υπόψη τους κανόνες στοίχισης ή να χρησιμοποιήσετε το χαρακτηριστικό στη δήλωση δομής packed.

Παραγγελία κλειδιών από εξωτερικό συγκριτή

Η βασική λογική σύγκρισης μπορεί να αποδειχθεί πολύ περίπλοκη για έναν δυαδικό συγκριτή. Ένας από τους πολλούς λόγους είναι η παρουσία τεχνικών πεδίων μέσα στις κατασκευές. Θα επεξηγήσω την εμφάνισή τους στο παράδειγμα ενός κλειδιού που είναι ήδη γνωστό σε εμάς για ένα στοιχείο καταλόγου.

typedef struct NodeKey {
    EntityId parentId;
    uint8_t type;
    uint8_t nameBuffer[256];
} NodeKey;

Παρά την απλότητά του, στη συντριπτική πλειονότητα των περιπτώσεων καταναλώνει υπερβολική μνήμη. Το buffer τίτλου είναι 256 byte, αν και κατά μέσο όρο τα ονόματα αρχείων και φακέλων σπάνια υπερβαίνουν τους 20-30 χαρακτήρες.

Μία από τις τυπικές τεχνικές για τη βελτιστοποίηση του μεγέθους μιας εγγραφής είναι η περικοπή της ώστε να ταιριάζει στο πραγματικό της μέγεθος. Η ουσία του είναι ότι τα περιεχόμενα όλων των πεδίων μεταβλητού μήκους αποθηκεύονται σε ένα buffer στο τέλος της δομής και τα μήκη τους αποθηκεύονται σε ξεχωριστές μεταβλητές.Σύμφωνα με αυτή την προσέγγιση, το κλειδί NodeKey μετατρέπεται με τον εξής τρόπο.

typedef struct NodeKey {
    EntityId parentId;
    uint8_t type;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeKey;

Επιπλέον, κατά τη σειριοποίηση, δεν προσδιορίζεται ως μέγεθος δεδομένων sizeof ολόκληρη η δομή και το μέγεθος όλων των πεδίων είναι σταθερό μήκος συν το μέγεθος του πραγματικά χρησιμοποιούμενου τμήματος του buffer.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
        .mv_data = (void *)key
    };
}

Ως αποτέλεσμα της ανακατασκευής, πετύχαμε σημαντική εξοικονόμηση στον χώρο που καταλαμβάνουν τα κλειδιά. Ωστόσο, λόγω του τεχνικού τομέα nameLength, ο προεπιλεγμένος δυαδικός συγκριτής δεν είναι πλέον κατάλληλος για σύγκριση κλειδιών. Εάν δεν το αντικαταστήσουμε με το δικό μας, τότε το μήκος του ονόματος θα είναι ένας παράγοντας προτεραιότητας στην ταξινόμηση από το ίδιο το όνομα.

Το LMDB επιτρέπει σε κάθε βάση δεδομένων να έχει τη δική της λειτουργία σύγκρισης κλειδιών. Αυτό γίνεται χρησιμοποιώντας τη συνάρτηση mdb_set_compare αυστηρά πριν από το άνοιγμα. Για προφανείς λόγους, μια βάση δεδομένων δεν μπορεί να αλλάξει καθ' όλη τη διάρκεια ζωής της. Στην είσοδο, ο συγκριτής λαμβάνει δύο κλειδιά σε δυαδική μορφή και στην έξοδο επιστρέφει το αποτέλεσμα της σύγκρισης: μικρότερο από (-1), μεγαλύτερο από (1) ή ίσο (0). Ψευκωδικός για NodeKey μοιάζει έτσι.

int compare(MDB_val * const a, MDB_val * const b) {
    NodeKey * const aKey = (NodeKey * const)a->mv_data;
    NodeKey * const bKey = (NodeKey * const)b->mv_data;
    return // ...
}

Εφόσον όλα τα κλειδιά στη βάση δεδομένων είναι του ίδιου τύπου, είναι νόμιμο να μεταφέρεται άνευ όρων η αναπαράσταση byte στον τύπο της δομής εφαρμογής του κλειδιού. Υπάρχει μια απόχρωση εδώ, αλλά θα συζητηθεί λίγο πιο κάτω στην υποενότητα "Ανάγνωση εγγραφών".

Σειριοποίηση τιμών

Με τα κλειδιά των αποθηκευμένων εγγραφών, το LMDB λειτουργεί εξαιρετικά εντατικά. Συγκρίνονται μεταξύ τους στο πλαίσιο οποιασδήποτε λειτουργίας εφαρμογής και η απόδοση ολόκληρης της λύσης εξαρτάται από την ταχύτητα του συγκριτή. Σε έναν ιδανικό κόσμο, ο προεπιλεγμένος δυαδικός συγκριτής θα πρέπει να είναι αρκετός για να συγκρίνετε κλειδιά, αλλά αν έπρεπε πραγματικά να χρησιμοποιήσετε τα δικά σας, τότε η διαδικασία για την αποσειροποίηση κλειδιών σε αυτόν θα πρέπει να είναι όσο το δυνατόν πιο γρήγορη.

Η βάση δεδομένων δεν ενδιαφέρεται ιδιαίτερα για το τμήμα Value της εγγραφής (τιμή). Η μετατροπή του από μια αναπαράσταση byte σε ένα αντικείμενο συμβαίνει μόνο όταν απαιτείται ήδη από τον κώδικα της εφαρμογής, για παράδειγμα, να εμφανιστεί στην οθόνη. Δεδομένου ότι αυτό συμβαίνει σχετικά σπάνια, οι απαιτήσεις για την ταχύτητα αυτής της διαδικασίας δεν είναι τόσο κρίσιμες και κατά την εφαρμογή της είμαστε πολύ πιο ελεύθεροι να επικεντρωθούμε στην ευκολία. Για παράδειγμα, για τη σειριοποίηση μεταδεδομένων σχετικά με αρχεία που δεν έχουν ακόμη ληφθεί, χρησιμοποιούμε NSKeyedArchiver.

NSData *data = serialize(object);
MDB_val value = {
    .mv_size = data.length,
    .mv_data = (void *)data.bytes
};

Ωστόσο, υπάρχουν στιγμές που η απόδοση έχει σημασία. Για παράδειγμα, όταν αποθηκεύουμε μετα-πληροφορίες σχετικά με τη δομή του αρχείου του νέφους χρηστών, χρησιμοποιούμε την ίδια ένδειξη μνήμης αντικειμένων. Το αποκορύφωμα του έργου της δημιουργίας σειριακής αναπαράστασής τους είναι το γεγονός ότι τα στοιχεία ενός καταλόγου μοντελοποιούνται από μια ιεραρχία κλάσεων.

Για την εφαρμογή του στη γλώσσα C, τα συγκεκριμένα πεδία των κληρονόμων εξάγονται σε ξεχωριστές δομές και η σύνδεσή τους με τη βασική προσδιορίζεται μέσω ενός πεδίου τύπου ένωσης. Το πραγματικό περιεχόμενο της ένωσης καθορίζεται μέσω του τεχνικού χαρακτηριστικού τύπου.

typedef struct NodeValue {
    EntityId localId;
    EntityType type;
    union {
        FileInfo file;
        DirectoryInfo directory;
    } info;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeValue;

Προσθήκη και ενημέρωση εγγραφών

Το σειριακό κλειδί και η αξία μπορούν να προστεθούν στο κατάστημα. Για αυτό, χρησιμοποιείται η συνάρτηση mdb_put.

// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);

Στο στάδιο της διαμόρφωσης, μπορεί να επιτραπεί ή να απαγορευτεί η αποθήκευση πολλαπλών εγγραφών με το ίδιο κλειδί στο χώρο αποθήκευσης. Εάν απαγορεύεται η αντιγραφή κλειδιών, τότε κατά την εισαγωγή μιας εγγραφής, μπορείτε να καθορίσετε εάν επιτρέπεται ή όχι η ενημέρωση μιας ήδη υπάρχουσας εγγραφής. Εάν το ξεφτίλισμα μπορεί να συμβεί μόνο ως αποτέλεσμα σφάλματος στον κωδικό, τότε μπορείτε να ασφαλιστείτε για αυτό καθορίζοντας τη σημαία NOOVERWRITE.

Ανάγνωση αρχείων

Η λειτουργία για την ανάγνωση εγγραφών στο LMDB είναι mdb_get. Εάν το ζεύγος κλειδιού-τιμής αντιπροσωπεύεται από δομές που είχαν προηγουμένως απορριφθεί, τότε αυτή η διαδικασία μοιάζει με αυτό.

NodeValue * const readNode(..., NodeKey * const key) {
    MDB_val rawKey = serialize(key);
    MDB_val rawValue;
    mdb_get(..., &rawKey, &rawValue);
    return (NodeValue * const)rawValue.mv_data;
}

Η παρουσιαζόμενη λίστα δείχνει πώς η σειριοποίηση μέσω μιας χωματερής δομών σάς επιτρέπει να απαλλαγείτε από δυναμικές εκχωρήσεις όχι μόνο κατά την εγγραφή, αλλά και κατά την ανάγνωση δεδομένων. Προέρχεται από τη συνάρτηση mdb_get ο δείκτης κοιτάζει ακριβώς τη διεύθυνση εικονικής μνήμης όπου η βάση δεδομένων αποθηκεύει την αναπαράσταση byte του αντικειμένου. Στην πραγματικότητα, παίρνουμε ένα είδος ORM, σχεδόν δωρεάν παρέχοντας πολύ υψηλή ταχύτητα ανάγνωσης δεδομένων. Με όλη την ομορφιά της προσέγγισης, είναι απαραίτητο να θυμάστε πολλά χαρακτηριστικά που σχετίζονται με αυτήν.

Για μια συναλλαγή μόνο για ανάγνωση, ένας δείκτης σε μια δομή αξίας είναι εγγυημένη ότι θα παραμείνει έγκυρος μόνο μέχρι να κλείσει η συναλλαγή. Όπως σημειώθηκε προηγουμένως, οι σελίδες του Β-δέντρου στο οποίο βρίσκεται το αντικείμενο, χάρη στην αρχή της αντιγραφής σε εγγραφή, παραμένουν αμετάβλητες εφόσον τουλάχιστον μία συναλλαγή αναφέρεται σε αυτές. Ταυτόχρονα, μόλις ολοκληρωθεί η τελευταία συναλλαγή που σχετίζεται με αυτές, οι σελίδες μπορούν να επαναχρησιμοποιηθούν για νέα δεδομένα. Εάν είναι απαραίτητο για τα αντικείμενα να επιβιώσουν από τη συναλλαγή που τα δημιούργησε, τότε πρέπει ακόμα να αντιγραφούν.
Για μια συναλλαγή επανεγγραφής, ο δείκτης στην προκύπτουσα δομή-τιμή θα ισχύει μόνο μέχρι την πρώτη διαδικασία τροποποίησης (εγγραφή ή διαγραφή δεδομένων).
Παρόλο που η δομή NodeValue όχι πλήρες, αλλά περικομμένο (βλ. υποενότητα "Παραγγελία κλειδιών από εξωτερικό συγκριτή"), μέσω του δείκτη, μπορείτε εύκολα να αποκτήσετε πρόσβαση στα πεδία του. Το κυριότερο είναι να μην το παραβιάσεις!
Σε καμία περίπτωση δεν μπορείτε να τροποποιήσετε τη δομή μέσω του λαμβανόμενου δείκτη. Όλες οι αλλαγές πρέπει να γίνονται μόνο μέσω της μεθόδου mdb_put. Ωστόσο, με όλη την επιθυμία να γίνει αυτό, δεν θα λειτουργήσει, καθώς η περιοχή μνήμης όπου βρίσκεται αυτή η δομή αντιστοιχίζεται σε λειτουργία μόνο για ανάγνωση.
Αντιστοιχίστε ξανά ένα αρχείο στο χώρο διευθύνσεων μιας διεργασίας προκειμένου, για παράδειγμα, να αυξήσετε το μέγιστο μέγεθος αποθήκευσης χρησιμοποιώντας τη λειτουργία mdb_env_set_map_size ακυρώνει πλήρως όλες τις συναλλαγές και τις σχετικές οντότητες γενικά και τους δείκτες για ανάγνωση αντικειμένων ειδικότερα.

Τέλος, ένα ακόμη χαρακτηριστικό είναι τόσο ύπουλο που η αποκάλυψη της ουσίας του δεν χωράει μόνο σε ένα ακόμη σημείο. Στο κεφάλαιο για το Β-δέντρο, έδωσα ένα διάγραμμα της οργάνωσης των σελίδων του στη μνήμη. Από αυτό προκύπτει ότι η διεύθυνση της αρχής του buffer με σειριακά δεδομένα μπορεί να είναι απολύτως αυθαίρετη. Εξαιτίας αυτού, ο δείκτης προς αυτά, λαμβάνεται στη δομή MDB_val και η μετάδοση σε έναν δείκτη σε μια δομή είναι γενικά μη ευθυγραμμισμένη. Ταυτόχρονα, οι αρχιτεκτονικές ορισμένων τσιπ (στην περίπτωση του iOS, αυτό είναι το armv7) απαιτούν η διεύθυνση οποιωνδήποτε δεδομένων να είναι πολλαπλάσιο του μεγέθους μιας λέξης μηχανής ή, με άλλα λόγια, το bit του συστήματος (για armv7, αυτό είναι 32 bit). Με άλλα λόγια, μια επέμβαση όπως *(int *foo)0x800002 πάνω τους εξισώνεται με τη φυγή και οδηγεί σε εκτέλεση με ετυμηγορία EXC_ARM_DA_ALIGN. Υπάρχουν δύο τρόποι για να αποφύγεις μια τόσο θλιβερή μοίρα.

Το πρώτο είναι να αντιγράψετε τα δεδομένα σε μια γνωστή-στοιχισμένη δομή εκ των προτέρων. Για παράδειγμα, σε έναν προσαρμοσμένο συγκριτή, αυτό θα αντικατοπτρίζεται ως εξής.

int compare(MDB_val * const a, MDB_val * const b) {
    NodeKey aKey, bKey;
    memcpy(&aKey, a->mv_data, a->mv_size);
    memcpy(&bKey, b->mv_data, b->mv_size);
    return // ...
}

Ένας εναλλακτικός τρόπος είναι να ειδοποιήσετε εκ των προτέρων τον μεταγλωττιστή ότι οι δομές με κλειδί και τιμή ενδέχεται να μην ευθυγραμμιστούν χρησιμοποιώντας ένα χαρακτηριστικό aligned(1). Στο ARM μπορεί να είναι το ίδιο αποτέλεσμα φέρνω σε πέρας και χρησιμοποιώντας το χαρακτηριστικό packed. Λαμβάνοντας υπόψη ότι συμβάλλει επίσης στη βελτιστοποίηση του χώρου που καταλαμβάνει η κατασκευή, αυτή η μέθοδος μου φαίνεται προτιμότερη, αν και приводит να αυξήσει το κόστος των λειτουργιών πρόσβασης στα δεδομένα.

typedef struct __attribute__((packed)) NodeKey {
    uint8_t parentId;
    uint8_t type;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeKey;

Ερωτήματα εύρους

Για την επανάληψη σε μια ομάδα εγγραφών, το LMDB παρέχει μια αφαίρεση δρομέα. Ας δούμε πώς να δουλέψουμε με αυτό χρησιμοποιώντας το παράδειγμα ενός πίνακα με μεταδεδομένα cloud χρηστών που είναι ήδη γνωστά σε εμάς.

Ως μέρος της εμφάνισης μιας λίστας αρχείων σε έναν κατάλογο, πρέπει να βρείτε όλα τα κλειδιά με τα οποία συσχετίζονται τα θυγατρικά αρχεία και οι φάκελοί του. Στις προηγούμενες υποενότητες, ταξινομήσαμε τα κλειδιά NodeKey ώστε να ταξινομηθούν πρώτα από το αναγνωριστικό γονικού καταλόγου τους. Έτσι, τεχνικά, το έργο της απόκτησης των περιεχομένων ενός φακέλου περιορίζεται στην τοποθέτηση του δρομέα στο άνω όριο μιας ομάδας πλήκτρων με ένα δεδομένο πρόθεμα, ακολουθούμενη από επανάληψη στο κάτω όριο.

Μπορείτε να βρείτε το άνω φράγμα "στο μέτωπο" με διαδοχική αναζήτηση. Για να γίνει αυτό, ο δρομέας τοποθετείται στην αρχή ολόκληρης της λίστας των κλειδιών στη βάση δεδομένων και στη συνέχεια αυξάνεται μέχρι να εμφανιστεί κάτω από αυτό το κλειδί με το αναγνωριστικό γονικού καταλόγου. Αυτή η προσέγγιση έχει 2 προφανή μειονεκτήματα:

Η γραμμική πολυπλοκότητα της αναζήτησης, αν και, όπως γνωρίζετε, σε δέντρα γενικά και σε ένα δέντρο Β ειδικότερα, μπορεί να γίνει σε λογαριθμικό χρόνο.
Μάταια, όλες οι σελίδες που προηγούνται της επιθυμητής ανεβαίνουν από το αρχείο στην κύρια μνήμη, η οποία είναι εξαιρετικά ακριβή.

Ευτυχώς, το LMDB API παρέχει έναν αποτελεσματικό τρόπο για την αρχική τοποθέτηση του δρομέα. Για να γίνει αυτό, πρέπει να σχηματίσετε ένα κλειδί του οποίου η τιμή είναι γνωστό ότι είναι μικρότερη ή ίση με το κλειδί που βρίσκεται στο άνω όριο του διαστήματος. Για παράδειγμα, σε σχέση με τη λίστα στο παραπάνω σχήμα, μπορούμε να φτιάξουμε ένα κλειδί στο οποίο το πεδίο parentId θα είναι ίσο με 2, και όλα τα υπόλοιπα συμπληρώνονται με μηδενικά. Ένα τέτοιο μερικώς γεμάτο κλειδί τροφοδοτείται στην είσοδο της συνάρτησης mdb_cursor_get που δείχνει τη λειτουργία MDB_SET_RANGE.

NodeKey upperBoundSearchKey = {
    .parentId = 2,
    .type = 0,
    .nameLength = 0
};
MDB_val value, key = serialize(upperBoundSearchKey);
MDB_cursor *cursor;
mdb_cursor_open(..., &cursor);
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);

Εάν βρεθεί το άνω όριο της ομάδας των κλειδιών, τότε επαναλαμβάνουμε πάνω του μέχρι να συναντηθούμε ή το κλειδί με άλλο parentId, διαφορετικά τα κλειδιά δεν θα εξαντληθούν καθόλου.

do {
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);
    // processing...
} while (MDB_NOTFOUND != rc && // check end of table
         IsTargetKey(key));    // check end of keys group

Αυτό που είναι ωραίο, ως μέρος της επανάληψης χρησιμοποιώντας mdb_cursor_get, δεν παίρνουμε μόνο το κλειδί, αλλά και την τιμή. Εάν, για να πληρούνται οι προϋποθέσεις επιλογής, είναι απαραίτητο να ελέγξετε, μεταξύ άλλων, τα πεδία από το τμήμα τιμής της εγγραφής, τότε είναι αρκετά προσβάσιμα στον εαυτό τους χωρίς πρόσθετες χειρονομίες.

4.3. Μοντελοποίηση σχέσεων μεταξύ πινάκων

Μέχρι σήμερα, έχουμε καταφέρει να εξετάσουμε όλες τις πτυχές του σχεδιασμού και της εργασίας με μια βάση δεδομένων ενός πίνακα. Μπορούμε να πούμε ότι ένας πίνακας είναι ένα σύνολο ταξινομημένων εγγραφών που αποτελείται από ζεύγη κλειδιών-τιμών του ίδιου τύπου. Εάν εμφανίσετε ένα κλειδί ως ορθογώνιο και τη σχετική τιμή του ως πλαίσιο, λαμβάνετε ένα οπτικό διάγραμμα της βάσης δεδομένων.

Ωστόσο, στην πραγματική ζωή, σπάνια είναι δυνατόν να τα βγάλεις πέρα με τόσο λίγο αίμα. Συχνά σε μια βάση δεδομένων απαιτείται, πρώτον, να υπάρχουν πολλοί πίνακες και, δεύτερον, να πραγματοποιούνται επιλογές σε αυτούς με σειρά διαφορετική από το πρωτεύον κλειδί. Αυτή η τελευταία ενότητα είναι αφιερωμένη στα ζητήματα της δημιουργίας και της διασύνδεσής τους.

Πίνακες ευρετηρίου

Η εφαρμογή cloud έχει μια ενότητα "Γκαλερί". Εμφανίζει περιεχόμενο πολυμέσων από ολόκληρο το cloud, ταξινομημένο κατά ημερομηνία. Για τη βέλτιστη εφαρμογή μιας τέτοιας επιλογής, δίπλα στον κύριο πίνακα, πρέπει να δημιουργήσετε ένα άλλο με έναν νέο τύπο πλήκτρων. Θα περιέχουν ένα πεδίο με την ημερομηνία δημιουργίας του αρχείου, το οποίο θα λειτουργεί ως το κύριο κριτήριο ταξινόμησης. Επειδή τα νέα κλειδιά αναφέρονται στα ίδια δεδομένα με τα κλειδιά στον υποκείμενο πίνακα, ονομάζονται κλειδιά ευρετηρίου. Τονίζονται με πορτοκαλί χρώμα στην παρακάτω εικόνα.

Προκειμένου να διαχωριστούν τα κλειδιά διαφορετικών πινάκων το ένα από το άλλο εντός της ίδιας βάσης δεδομένων, ένα πρόσθετο τεχνικό πεδίο tableId έχει προστεθεί σε όλους. Καθιστώντας την υψηλότερη προτεραιότητα για ταξινόμηση, θα ομαδοποιήσουμε τα κλειδιά πρώτα ανά πίνακες και ήδη μέσα στους πίνακες - σύμφωνα με τους δικούς μας κανόνες.

Το κλειδί ευρετηρίου αναφέρεται στα ίδια δεδομένα με το πρωτεύον κλειδί. Η απλή υλοποίηση αυτής της ιδιότητας συσχετίζοντας μαζί της ένα αντίγραφο του τμήματος τιμής του πρωτεύοντος κλειδιού είναι υποβέλτιστη από πολλές απόψεις ταυτόχρονα:

Από πλευράς καταλαμβανόμενου χώρου, τα μεταδεδομένα μπορεί να είναι αρκετά πλούσια.
Από άποψη απόδοσης, αφού κατά την ενημέρωση των μεταδεδομένων του κόμβου, θα πρέπει να αντικαταστήσετε δύο κλειδιά.
Από την άποψη της υποστήριξης κώδικα, σε τελική ανάλυση, εάν ξεχάσουμε να ενημερώσουμε τα δεδομένα για ένα από τα κλειδιά, θα εμφανιστεί ένα λεπτό σφάλμα ασυνέπειας δεδομένων στην αποθήκευση.

Στη συνέχεια, θα εξετάσουμε πώς να εξαλείψουμε αυτές τις ελλείψεις.

Οργάνωση σχέσεων μεταξύ πινάκων

Το μοτίβο είναι κατάλληλο για τη σύνδεση ενός πίνακα ευρετηρίου με τον κύριο "κλειδί ως αξία". Όπως υποδηλώνει το όνομά του, το τμήμα τιμής της εγγραφής ευρετηρίου είναι αντίγραφο της τιμής του πρωτεύοντος κλειδιού. Αυτή η προσέγγιση εξαλείφει όλα τα μειονεκτήματα που αναφέρονται παραπάνω που σχετίζονται με την αποθήκευση ενός αντιγράφου του τμήματος τιμής της κύριας εγγραφής. Η μόνη χρέωση είναι ότι για να λάβετε την τιμή με το κλειδί ευρετηρίου, πρέπει να κάνετε 2 ερωτήματα στη βάση δεδομένων αντί για ένα. Σχηματικά, το σχήμα της βάσης δεδομένων που προκύπτει έχει ως εξής.

Ένα άλλο μοτίβο για την οργάνωση των σχέσεων μεταξύ των πινάκων είναι "περιττό κλειδί". Η ουσία του είναι να προσθέσει πρόσθετα χαρακτηριστικά στο κλειδί, τα οποία χρειάζονται όχι για την ταξινόμηση, αλλά για την αναδημιουργία του συσχετισμένου κλειδιού. Υπάρχουν όμως πραγματικά παραδείγματα χρήσης του στην εφαρμογή Mail.ru Cloud, προκειμένου να αποφευχθεί η βαθιά κατάδυση στο πλαίσιο συγκεκριμένων πλαισίων iOS, θα δώσω ένα πλασματικό, αλλά πιο κατανοητό παράδειγμα.

Οι πελάτες Cloud για κινητά έχουν μια σελίδα που εμφανίζει όλα τα αρχεία και τους φακέλους που έχει μοιραστεί ο χρήστης με άλλα άτομα. Δεδομένου ότι υπάρχουν σχετικά λίγα τέτοια αρχεία και υπάρχουν πολλές συγκεκριμένες πληροφορίες σχετικά με τη δημοσιότητα που σχετίζονται με αυτά (σε ποιους παρέχεται πρόσβαση, με ποια δικαιώματα κ.λπ.), δεν θα είναι λογικό να επιβαρυνθεί με την αξία του την καταχώρηση στον κεντρικό πίνακα. Ωστόσο, εάν θέλετε να εμφανίσετε τέτοια αρχεία εκτός σύνδεσης, τότε θα πρέπει να τα αποθηκεύσετε κάπου. Μια φυσική λύση είναι να δημιουργήσετε ένα ξεχωριστό τραπέζι για αυτό. Στο παρακάτω διάγραμμα, το κλειδί του έχει το πρόθεμα "P" και το σύμβολο κράτησης θέσης "propname" μπορεί να αντικατασταθεί με την πιο συγκεκριμένη τιμή "δημόσιες πληροφορίες".

Όλα τα μοναδικά μεταδεδομένα, για χάρη των οποίων δημιουργήθηκε ο νέος πίνακας, μετακινούνται στο τμήμα τιμής της εγγραφής. Ταυτόχρονα, δεν θέλω να αντιγράψω τα δεδομένα σχετικά με αρχεία και φακέλους που είναι ήδη αποθηκευμένα στον κύριο πίνακα. Αντίθετα, πλεονάζοντα δεδομένα προστίθενται στο κλειδί "P" με τη μορφή των πεδίων "αναγνωριστικό κόμβου" και "χρονοσήμανση". Χάρη σε αυτά, μπορείτε να κατασκευάσετε ένα κλειδί ευρετηρίου, με το οποίο μπορείτε να λάβετε το πρωτεύον κλειδί, με το οποίο, τέλος, μπορείτε να λάβετε τα μεταδεδομένα του κόμβου.

συμπέρασμα

Αξιολογούμε θετικά τα αποτελέσματα της εφαρμογής LMDB. Μετά από αυτό, ο αριθμός των παγώσεων εφαρμογής μειώθηκε κατά 30%.

Τα αποτελέσματα της δουλειάς που έγινε βρήκαν ανταπόκριση εκτός της ομάδας iOS. Επί του παρόντος, μία από τις κύριες ενότητες "Αρχεία" στην εφαρμογή Android έχει επίσης μεταβεί στη χρήση LMDB και άλλα τμήματα είναι καθ' οδόν. Η γλώσσα C, στην οποία υλοποιείται ο αποθηκευτικός χώρος κλειδιού-τιμής, ήταν μια καλή βοήθεια προκειμένου αρχικά να γίνει η εφαρμογή δεσμευτική γύρω της σε cross-platform στη γλώσσα C ++. Για μια απρόσκοπτη σύνδεση της προκύπτουσας βιβλιοθήκης C ++ με τον κώδικα πλατφόρμας στο Objective-C και στο Kotlin, χρησιμοποιήθηκε μια γεννήτρια κώδικα Ντζίννι από το Dropbox, αλλά αυτό είναι μια άλλη ιστορία.

Πηγή: www.habr.com

Η λαμπρότητα και η φτώχεια της βάσης δεδομένων κλειδιού-τιμής LMDB σε εφαρμογές iOS