|
|
| Κωδικός Πόρου |
000441652 |
| Τίτλος |
Balancing Garbage Collection vs I/O Amplification using hybrid Key-Value Placement in LSM-based Key-Value Stores |
| Άλλος τίτλος |
Ισορροπώντας το κόστος της ανάκτησης χώρου και του αυξημένου I/O σε συστήματα κλειδιού-τιμής βασισμένα στο LSM δέντρο με την υβριδική τοποθέτηση ζευγαριών κλειδιού-τιμής |
|
Συγγραφέας
|
Ξανθάκης, Γιώργος Ι.
|
|
Σύμβουλος διατριβής
|
Μπίλας, Άγγελος
|
|
Μέλος κριτικής επιτροπής
|
Μαγκούτης, Κωνσταντίνος
Πρατικάκης, Πολύβιος
|
| Περίληψη |
Η τεχνική της διαχώρισης κλειδιού-τιμής εισάγει τυχαιότητα στα μοτίβα πρόσβασης
ώστε να μειώσει τo επιπλέον Ι/Ο στα συστήματα κλειδιού-τιμής που είναι βασισμένα
στο LSM δέντρο και στοχεύουν τις γρήγορες συσκευές αποθήκευσης (NVMe). Η τεχνική
της διαχώρισης κλειδιού-τιμής αποθηκεύει τα ζευγάρια σε ένα log και αποθηκεύει
κάποια μεταπληροφορία για την ανάκτηση των δεδομένων στο ευρετήριο του
συστήματος. Παρ' όλα αυτά η τεχνική της διαχώρισης κλειδιού-τιμής έχει ένα σημαντικό
μειονέκτημα που τη κάνει λιγότερο ελκυστική. Για τις λειτουργίες διαγραφής και
ενημέρωσης που είναι σημαντικές για τα workloads που εμφανίζονται στη βιομηχανία
προκαλούν συχνά την ακριβή λειτουργία ανάκτησης χώρου (Garbage Collection) στo log
του συστήματος και καθιστά τα συστήματα που χρησιμοποιούν αυτή τη τεχνική να μην
είναι πρακτικά.
Σε αυτή την εργασία, σχεδιάζουμε και υλοποιούμε το Parallax, το οποίο προτείνει μια
υβριδική τοποθέτηση των ζευγαριών κλειδιού-τιμής που μειώνει το κόστος της
ανάκτησης χώρου σημαντικά και μεγιστοποιεί το κέρδος όταν αποθηκεύουμε τις τιμές
σε ένα log. Πρώτα μοντελοποιούμε τα κέρδη της τεχνικής διαχώρισης κλειδιού-τιμής για
διάφορα μεγέθη. Χρησιμοποιούμε το μοντέλο για να κατηγοριοποιήσουμε τα ζευγάρια
κλειδιού-τιμής σε τρεις κατηγορίες στη μικρή, τη μεσαία, και τη μεγάλη.
Στη συνέχεια, το Parallax χρησιμοποιεί διαφορετικές προσεγγίσεις για τη κάθε
κατηγορία: Τοποθετεί τα μεγάλα ζευγάρια πάντα σε ένα log και τα μικρά ζευγάρια πάντα
στο ευρετήριο. Για την μεσαία κατηγορία χρησιμοποιεί μια μεικτή στρατηγική που
συνδυάζει τα κέρδη του log για όλα εκτός από τα τελευταία επίπεδα (συνήθως το
τελευταίο ή προτελευταίο) στην LSM δομή, όπου πραγματοποιεί μια πλήρη σάρωση στο
log και τοποθετεί τις τιμές μέσα στο ευρετήριο. Μετά τη σάρωση ανακτά το χώρο του
μεσαίου log χωρίς να χρειάζεται η λειτουργία της ανάκτησης χώρου (Garbage Collection).
Στην πειραματική μας ανάλυση συγκρίνουμε το Parallax με τη RocksDB που τοποθετεί
όλες τις τιμές μέσα στο ευρετήριο της και τη BlobDB που τοποθετεί όλες τις τιμές σε ένα
log. Καταλήγουμε ότι το Parallax αυξάνει την απόδοση από 12.4 μέχρι 17.83x, μειώνει το
επιπλέον I/O από 26 μέχρι 27.1x και αυξάνει την αποτελεσματικότητα του επεξεργαστή
από 18.7 μέχρι 28x αντίστοιχα για όλα τα workloads του YCSB εκτός από αυτά που
βασίζονται σε scans.
|
| Φυσική περιγραφή |
vi, 37 σ. : σχεδ., πιν., εικ. ; 30 εκ. |
| Γλώσσα |
Αγγλικά |
| Θέμα |
Fast storage devices |
|
KV separation |
|
LSM tree |
| Ημερομηνία έκδοσης |
2021-07-30 |
| Συλλογή
|
Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
|
|
|
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
|
| Εμφανίσεις |
355 |
Balancing Garbage Collection vs I/O Amplification using hybrid Key-Value Placement in LSM-based Key-Value Stores
