Οι επιστήμονες βρίσκουν τη βέλτιστη ισορροπία αποθήκευσης δεδομένων και χρόνου | Περιοδικό Quanta

Πριν από περίπου 70 χρόνια, ένας μηχανικός της IBM ονόματι Hans Peter Luhn άλλαξε αθόρυβα την πορεία της επιστήμης των υπολογιστών. Ο Luhn κατείχε ήδη αρκετές πατέντες, συμπεριλαμβανομένης μιας για μια συσκευή που μπορούσε να μετρήσει τον αριθμό των νημάτων ενός υφάσματος και μια άλλη για έναν οδηγό που καθόριζε τι μικτά ποτά θα μπορούσατε να φτιάξετε από τα συστατικά της κουζίνας σας. Αλλά σε ένα εσωτερικό έγγραφο της IBM το 1953, πρότεινε μια νέα τεχνική για την αποθήκευση και την ανάκτηση πληροφοριών που είναι πλέον ενσωματωμένη σχεδόν σε όλα τα υπολογιστικά συστήματα: τον πίνακα κατακερματισμού.

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

Σε μια 1957 χαρτί δημοσιευμένο στο IBM Journal of Research and Development, W. Wesley Peterson προσδιόρισε την κύρια τεχνική πρόκληση που θέτουν οι πίνακες κατακερματισμού: Πρέπει να είναι γρήγοροι, που σημαίνει ότι μπορούν να ανακτήσουν γρήγορα τις απαραίτητες πληροφορίες. Αλλά πρέπει επίσης να είναι συμπαγείς, χρησιμοποιώντας όσο το δυνατόν λιγότερη μνήμη. Αυτοί οι δίδυμοι στόχοι είναι ουσιαστικά σε αντίθεση. Η πρόσβαση και η τροποποίηση μιας βάσης δεδομένων μπορεί να γίνει πιο γρήγορα όταν ο πίνακας κατακερματισμού έχει περισσότερη μνήμη. και οι λειτουργίες γίνονται πιο αργές σε πίνακες κατακερματισμού που χρησιμοποιούν λιγότερο χώρο. Από τότε που ο Peterson έθεσε αυτή την πρόκληση, οι ερευνητές προσπάθησαν να βρουν την καλύτερη ισορροπία μεταξύ χρόνου και χώρου.

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

«Σίγουρα θα έλεγα ότι είναι μεγάλη υπόθεση», πρόσθεσε Rasmus Pagh, επιστήμονας υπολογιστών στο Πανεπιστήμιο της Κοπεγχάγης. «Πολλοί άνθρωποι έχουν δουλέψει πάνω σε αυτό το πρόβλημα, προσπαθώντας να δουν πόσο μπορείτε να πιέσετε χώρο, ενώ παράλληλα έχετε λειτουργίες αποδοτικές από άποψη χρόνου. Αυτό θα ήθελα να λύσω».

Κάνοντας ένα Hash από αυτό

Οι πίνακες κατακερματισμού είναι από τις παλαιότερες, απλούστερες, ταχύτερες και πιο ευρέως χρησιμοποιούμενες δομές δεδομένων σήμερα. Έχουν σχεδιαστεί για να εκτελούν τρεις βασικές λειτουργίες: εισαγωγές, οι οποίες προσθέτουν νέα στοιχεία στη βάση δεδομένων. ερωτήματα, τα οποία έχουν πρόσβαση σε ένα στοιχείο ή ελέγχουν αν υπάρχει. και διαγραφές. Ένας πίνακας κατακερματισμού μπορεί να είναι εφήμερος — υπάρχει μόνο όσο εκτελείται ένα συγκεκριμένο πρόγραμμα — ή μπορεί να είναι μόνιμο μέρος του λειτουργικού συστήματος του υπολογιστή σας. Ένα πρόγραμμα περιήγησης ιστού όπως το Chrome ή το Safari μπορεί να έχει πολλούς ενσωματωμένους πίνακες κατακερματισμού που προορίζονται να παρακολουθούν διαφορετικά είδη δεδομένων.

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

Για να πάρουμε ένα εξαιρετικά απλοποιημένο παράδειγμα, σκεφτείτε το Αγγλικό Λεξικό της Οξφόρδης, το οποίο έχει ορισμούς για περισσότερες από 600,000 λέξεις. Εάν μια ψηφιακή έκδοση βασίζεται σε έναν πίνακα κατακερματισμού, μπορείτε απλώς να χρησιμοποιήσετε μια δεδομένη λέξη ως κλειδί και να προχωρήσετε κατευθείαν στον ορισμό. Χωρίς έναν πίνακα κατακερματισμού, το λεξικό πιθανότατα θα βασιζόταν σε έναν πολύ πιο αργό μηχανισμό αναζήτησης, χρησιμοποιώντας μια διαδικασία εξάλειψης για να συγκλίνει τελικά στον ζητούμενο ορισμό. Και ενώ ένας πίνακας κατακερματισμού μπορεί να βρει οποιαδήποτε λέξη σε σταθερό χρονικό διάστημα (συνήθως ένα μικροσκοπικό κλάσμα του δευτερολέπτου), ο χρόνος αναζήτησης για άλλες μεθόδους μπορεί να αυξάνεται καθώς αυξάνεται ο αριθμός των λέξεων στο λεξικό. Ένας πίνακας κατακερματισμού προσφέρει επίσης ένα άλλο πλεονέκτημα: Μπορεί να διατηρήσει το λεξικό δυναμικό, καθιστώντας εύκολη την εισαγωγή νέων λέξεων και τη διαγραφή παλαιών.

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

Ανακάτεμα δεδομένων

Το πρώτο σημαντικό βήμα προς αυτόν τον στόχο έγινε το 2022 μεγάλο συνέδριο επιστήμης υπολογιστών στη Ρώμη. Εκεί, μια ομάδα πρότεινε έναν πίνακα κατακερματισμού με νέα χαρακτηριστικά που θα μπορούσαν να προσφέρουν τον καλύτερο συνδυασμό απόδοσης χρόνου και χώρου που έχει ακόμα σχεδιαστεί. Ο πρώτος συγγραφέας της εργασίας (που παρατίθεται αλφαβητικά) ήταν ο Michael Bender του Πανεπιστημίου Stony Brook, επομένως αναφέρεται συνήθως ως Bender et al. πίνακας κατακερματισμού. Αν και η ομάδα δεν προσπάθησε να δημιουργήσει έναν λειτουργικό πίνακα κατακερματισμού, απέδειξαν ότι θα μπορούσε, καταρχήν, να κατασκευαστεί με τα χαρακτηριστικά που περιέγραψαν.

Για να αξιολογήσει τον πίνακα κατακερματισμού που δημιούργησε, η ομάδα δημιούργησε μια καμπύλη αντιστάθμισης - ένα γράφημα που απεικονίζει το χρόνο ανά λειτουργία (εισαγωγή ή διαγραφή) στον έναν άξονα και τον χώρο που καταλαμβάνει η μνήμη στον άλλο. Αλλά αυτό το γράφημα ορίζει το χώρο με έναν ειδικό τρόπο: Λόγω του τρόπου κατασκευής τους, οι πίνακες κατακερματισμού χρειάζονται περισσότερη μνήμη από το ελάχιστο που απαιτείται για την αποθήκευση ενός δεδομένου συνόλου στοιχείων. Οι επιστήμονες υπολογιστών αποκαλούν αυτόν τον επιπλέον χώρο «χαμένα κομμάτια», παρόλο που δεν σπαταλούνται πραγματικά και είναι, σε κάποιο βαθμό, απαραίτητα. Ο άξονας διαστήματος σε μια καμπύλη αντιστάθμισης μετρά τον αριθμό των χαμένων bit ανά κλειδί.

Αναλύοντας μια καμπύλη ανταλλαγής, οι ερευνητές μπορούν να καταλάβουν τον ταχύτερο δυνατό χρόνο για έναν πίνακα κατακερματισμού που χρησιμοποιεί δεδομένο χώρο. Μπορούν επίσης να αναστρέψουν την ερώτηση για να καταλάβουν τον μικρότερο δυνατό χώρο για έναν δεδομένο χρόνο λειτουργίας. Συνήθως, μια μικρή αλλαγή σε μια μεταβλητή θα οδηγήσει σε μια μικρή αλλαγή στην άλλη, είπε William Kuszmaul, θεωρητικός επιστήμονας υπολογιστών στο Χάρβαρντ και συν-συγγραφέας της εργασίας του 2022. "Εάν διπλασιάσετε το χρόνο, ίσως μειώσετε στο μισό τον αριθμό των χαμένων bits ανά κλειδί."

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

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

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

Εάν το στοιχείο βρίσκεται στην 100η καλύτερη θέση του, η δευτερεύουσα δομή δεδομένων επισυνάπτει τον αριθμό 100. Και επειδή το σύστημα χρησιμοποιεί δυαδικό, αντιπροσωπεύει τον αριθμό 100 ως 1100100. Χρειάζεται, φυσικά, περισσότερη μνήμη για την αποθήκευση του αριθμού 1100100 από το 1 — ο αριθμός που εκχωρείται σε ένα αντικείμενο όταν βρίσκεται στο καλύτερο σημείο. Τέτοιες διαφορές γίνονται σημαντικές αν αποθηκεύετε, ας πούμε, ένα εκατομμύριο αντικείμενα.

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

«Πριν από αυτή την εργασία, κανείς δεν είχε συνειδητοποιήσει ότι μπορούσατε να συμπιέσετε περαιτέρω τη δομή δεδομένων μεταφέροντας πληροφορίες», είπε ο Pagh. «Αυτή ήταν η μεγάλη εικόνα του χαρτιού Bender».

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

Δεσμευμένος να πετύχει

Την επόμενη χρονιά, μια ομάδα με επικεφαλής Χουατσένγκ Γιου, ένας επιστήμονας υπολογιστών στο Πανεπιστήμιο του Πρίνστον, προσπάθησε να βελτιώσει τον πίνακα κατακερματισμού της ομάδας Bender. «Δουλέψαμε πολύ σκληρά και δεν τα καταφέραμε», είπε Ρενφέι Ζου, φοιτητής στο Πανεπιστήμιο Tsinghua στο Πεκίνο και μέλος της ομάδας του Yu. «Τότε υποψιαζόμασταν ότι το άνω όριο τους ήταν [επίσης] ένα κάτω όριο» — το καλύτερο που μπορεί να επιτευχθεί. "Όταν το άνω όριο ισούται με το κάτω όριο, το παιχνίδι τελείωσε και έχετε την απάντησή σας." Ανεξάρτητα από το πόσο έξυπνοι είστε, κανένας πίνακας κατακερματισμού δεν μπορεί να κάνει κάτι καλύτερο.

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

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

Αυτό ήταν το βασικό τους επίτευγμα. Στη συνέχεια, μπόρεσαν να καθορίσουν ένα χαμηλότερο όριο στο χρόνο εκτέλεσης για οποιονδήποτε πίνακα κατακερματισμού με απόδοση χώρου. Και είδαν ότι ταίριαζε ακριβώς με τον πίνακα κατακερματισμού Bender. «Σκεφτήκαμε [στην αρχή] ότι θα μπορούσε να βελτιωθεί», είπε ο Zhou. «Αποδείχθηκε ότι κάναμε λάθος». Αυτό, με τη σειρά του, σήμαινε ότι το πρόβλημα του Peterson είχε επιτέλους λυθεί.

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

Hashing στο μέλλον

Παρά την άνευ προηγουμένου αποτελεσματικότητα του νέου πίνακα κατακερματισμού, κανείς δεν είναι πιθανό να προσπαθήσει να τον δημιουργήσει σύντομα. Είναι πολύ περίπλοκο να το κατασκευάσετε. «Ένας αλγόριθμος που είναι γρήγορος στη θεωρία δεν είναι απαραίτητα γρήγορος στην πράξη», είπε ο Zhou.

Δεν είναι ασυνήθιστο τέτοια κενά μεταξύ θεωρίας και πράξης να επιμένουν για μεγάλο χρονικό διάστημα, είπε ο Kuszmaul, επειδή οι θεωρητικοί τείνουν να αγνοούν σταθερούς παράγοντες. Ο χρόνος που χρειάζεται για την εκτέλεση μιας πράξης τυπικά πολλαπλασιάζεται με έναν αριθμό, κάποια σταθερά της οποίας η ακριβής τιμή μπορεί να είναι ασήμαντη από θεωρητική άποψη. «Αλλά στην πράξη, οι σταθερές έχουν πραγματικά σημασία», είπε. «Στον πραγματικό κόσμο, ο συντελεστής 10 είναι το τέλος του παιχνιδιού».

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

Ο Mitzenmacher ελπίζει ότι το αποτέλεσμα του 2023 μπορεί να αποφέρει σύντομα άλλου είδους όφελος: «Όποτε λαμβάνετε ένα νέο κατώτερο όριο - ειδικά αυτό που περιλαμβάνει κάποιες νέες τεχνικές - υπάρχει πάντα ελπίδα ότι θα μπορούσατε να τα χρησιμοποιήσετε ... για σχετικά προβλήματα».

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