Concurrency techniques for implementing efficient search trees in multicore systems

Abstract

Concurrent search trees are one of the most popular and widely used family of data structures. They are used in applications where it is necessary to store a large volume of sorted data with the ability to efficiently search, insert, remove, as well as more advanced operations, such as range queries. Due to their importance, a large amount of research has led to many different types of search trees with different characteristics such as, for example, the max allowed length of a path of the tree. Each search tree provides different performance guarantees for each tree operation and each tree is chosen based on the needs of the specific application.With the proliferation of multicores, where multiple threads execute concurrently and access shared data, concurrent data structures have become a critical component of parallel applications. In concurrent data structures it is necessary to coordinate the concurrent accesses by multiple threads in a way that guarantees the integrity of the data structure and the correctness of the operations. This coordination is achieved using some kind of synchronization mechanism such as, locks, hardware-provided atomic operations, Read-Copy-Update (RCU) and Transactional Memory (TM).Despite the high amount of prior work, it still remains challenging to implement highly efficient concurrent search trees. This is mainly due to the fact that both traditional synchronization methods (i.e., locks and atomic operations) and more novel ones (i.e., Read-Copy-Update and Transactional Memory) fail to provide solutions that are generic and at the same time able to attain high performance under diverse execution scenarios.Until recently, TM was mainly implemented in software and used through a library. However, recently two of the biggest processor manufacturers, Intel and IBM, have added support for Transactional Memory in the hardware level, allowing TM to be used without the large overheads imposed by the software implementations. In this work, we explore how HTM can be used to implement highly efficient concurrent search trees. More specifically, we present RCU-HTM, a synchronization mechanism that combines RCU and HTM, and: a) supports the implementation of a concurrent version of any type of search tree, and b) achieves high performance across all execution scenarios.In RCU-HTM threads that modify the tree structure in any way work in copies of the affected part of the tree. Once their local copy is ready, they use HTM to validate that the part of the tree that will be replaced has not been modified in the meanwhile and, if this is true, to replace the old part of the tree with their new modified version.To showcase the capabilities of our technique, we implement and evaluate multiple RCU-HTM trees and compare their performance with several state-of-the-art competitors. More specifically, we apply RCU-HTM to 12 different types of binary, B+-trees and (a-b)-trees and compare against several state-of-the-art implementations that use 4 different synchronization mechanisms, namely locks, atomic operations, RCU, and HTM. We evaluate the trees under multiple different execution scenarios by varying the size of the keys stored in the tree, the size of the trees, the operations mix, and the number of threads, for a total of 630 execution scenarios for each implementation. We also evaluate the search trees using two well-known real-life benchmarks, namely TPCC and YCSB, which are widely used for the evaluation of database management systems. Our evaluation shows that in the majority of executions, RCU-HTM trees outperform their state-of-the-art alternatives, and even in the few cases where they do not, their performance is very close to that of the best performing implementation.

Τα δένδρα αναζήτησης αποτελούν μία από τις πιο κλασσικές και ευρέως διαδεδομένες δομές δεδομένων. Χρησιμοποιούνται σε εφαρμογές όπου απαιτείται η διατήρηση μεγάλου ταξινομημένου όγκου δεδομένων με δυνατότητα γρήγορης αναζήτησης, εισαγωγής, διαγραφής και επιπλέον λειτουργιών, όπως είναι η αναζήτηση εύρους τιμών. Λόγω της σημασίας τους, ένα μεγάλο πλήθος ερευνητικών εργασιών έχει προτείνει πολλούς διαφορετικούς τύπους δένδρων με διαφορετικά χαρακτηριστικά όπως είναι, για παράδειγμα, το μέγιστο μήκος που μπορεί να έχει ένα μονοπάτι μέσα στο δένδρο. Κάθε τύπος δένδρου προσφέρει και διαφορετικές εγγυήσεις επίδοσης για την κάθε λειτουργία και κάθε δένδρο επιλέγεται με βάση τις ανάγκες της εκάστοτε εφαρμογής στην οποία θα ενσωματωθεί.Με την επικράτηση των πολυπύρηνων επεξεργαστών, όπου πολλαπλά νήματα εκτελούνται ταυτόχρονα και πιθανώς προσπελαύνουν κοινά δεδομένα, οι ταυτόχρονες δομές δεδομένων έχουν γίνει σημαντικό μέρος των εφαρμογών αυτών. Στις ταυτόχρονες δομές δεδομένων είναι αναγκαίος ο συντονισμός των ταυτόχρονων προσπελάσεων από διαφορετικά νήματα με τρόπο που να διατηρείται η ακεραιότητα της δομής και να εξασφαλίζεται η ορθή εκτέλεση όλων των επιμέρους λειτουργιών. Ο συντονισμός αυτός επιτυγχάνεται με τη χρήση κάποιου μηχανισμού συγχρονισμού όπως για παράδειγμα τα κλειδώματα, οι εντολές ατομικής προσπέλασης μνήμης που παρέχονται απο τους σύγχρονους επεξεργαστές, η τεχνική Διάβασε-Αντίγραψε-Ανανέωσε (Read-Copy-Update) και η μνήμη δοσοληψιών (Transactional Memory).Τα ταυτόχρονα δένδρα αναζήτησης είναι μία από τις πιο ευρέως χρησιμοποιούμενες δομές δεδομένων για την αποθήκευση και ανάκτηση δεδομένων σε σύγχρονες πολυνηματικές εφαρμογές. Παρά τον πολύ μεγάλο όγκο σχετικής δουλειάς, παραμένει ακόμα σημαντική πρόκληση η υλοποίηση ταυτόχρονων δένδρων αναζήτησης υψηλών επιδόσεων. Αυτό οφείλεται κυρίως στο γεγονός πως τόσο οι κλασσικές μέθοδοι συγχρονισμού (δηλαδή η χρήση κλειδωμάτων και η χρήση ατομικών λειτουργιών) όσο και οι πιο πρόσφατες (δηλαδή η τεχνική Read-Copy-Update και η Transactional Memory) δεν είναι αρκετές από μόνες τους ώστε να προσφέρουν λύσεις που θα είναι γενικές και εύκολα υλοποιήσιμες αλλά και την ίδια στιγμή θα προσφέρουν υψηλές επιδόσεις σε διαφορετικά σενάρια εκτέλεσης και επίπεδα συμφόρησης στη δομή.Μέχρι πρόσφατα, η Transactional Memory χρησιμοποιούταν κυρίως μέσω κάποιας βιβλιοθήκης που την υλοποιούσε σε επίπεδο λογισμικού. Ωστόσο, τα τελευταία χρόνια δύο απο τις μεγαλύτερες εταιρείες παραγωγής επεξεργαστών, η Intel και η IBM, έχουν προσθέσει υποστήριξη για Transactional Memory σε επίπεδο υλικού, αφαιρώντας με αυτό τον τρόπο τις μεγάλες καθυστερήσεις που εισάγονταν από τις υλοποιήσεις σε επίπεδου λογισμικού. Σε αυτή την εργασία εξετάζουμε τους τρόπους με τους οποίους μπορεί να χρησιμοποιηθεί η Transactional Memory για την υλοποίηση ταυτόχρονων δένδρων αναζήτησης υψηλής επίδοσης. Πιο συγκεκριμένα, παρουσιάζουμε την RCU-HTM, μία τεχνική συγχρονισμού που συνδυάζει τις τεχνικές Read-Copy-Update (RCU) και Hardware Transactional Memory (HTM) και: α) υποστηρίζει την υλοποίηση ταυτόχρονης έκδοσης οποιουδήποτε τύπου δένδρου αναζήτησης, και β) επιτυγχάνει πολύ υψηλές επιδόσεις για ένα μεγάλο εύρος σεναρίων εκτέλεσης.Στην RCU-HTM τα νήματα που τροποποιούν τη δομή του δένδρου με οποιοδήποτε τρόπο δουλεύουν σε αντίγραφα του τμήματος του δένδρου που επηρεάζουν. Μόλις το τοπικό τους αντίγραφο είναι έτοιμο, χρησιμοποιούν την HTM ώστε να επιβεβαιώσουν πως το μέρος του δένδρου που θα αντικατασταθεί δεν έχει στο μεταξύ τροποποιηθεί από κάποιο άλλο νήμα εκτέλεσης και, αν αυτό ισχύει, να αντικαταστήσουν το παλιό αντίγραφο με το τοπικό τους, το οποίο περιλαμβάνει τις κατάλληλες τροποποιήσεις.Για να δείξουμε τις δυνατότητες της τεχνικής μας, υλοποιούμε και αξιολογούμε ένα σημαντικό αριθμό δένδρων αναζήτησης με χρήση του RCU-HTM και συγκρίνουμε την επίδοσή τους με ένα πλήθος ανταγωνιστικών ταυτόχρονων δένδρων. Πιο συγκεκριμένα, εφαρμόζουμε την τεχνική RCU-HTM σε 12 διαφορετικούς τύπους δυαδικών δένδρων, Β+ δένδρων και (a-b)-δένδρων και συγκρίνουμε με πλήθος άλλων υλοποιήσεων που χρησιμοποιούν 4 διαφορετικούς μηχανισμούς συγχρονισμού, τα κλειδώματα, τις ατομικές λειτουργίες, το RCU και το HTM.Αξιολογούμε τα δένδρα αναζήτησης κάτω από πολλά διαφορετικά σενάρια εκτέλεσης μεταβάλλοντας το μέγεθος του κλειδιού που αποθηκεύεται στο δένδρο, τον αριθμό των κλειδιών που αποθηκεύονται στο δένδρο, το μείγμα από λειτουργίες που εκτελούνται καθώς και τον αριθμό των νημάτων που εκτελούν ταυτόχρονα λειτουργίες. Όλοι οι διαφορετικοί συνδυασμοί αυτών των παραμέτρων μας δίνουν 630 διαφορετικά σενάρια εκτέλεσης για κάθε δένδρο αναζήτησης. Επίσης, αξιολογούμε τα δένδρα χρησιμοποιώντας δύο μετροπρογράμματα που χρησιμοποιούνται κατα κόρον για την αξιολόγηση συστημάτων βάσεων δεδομένων, τα TPC-C και YCSB. Η αξιολόγηση μας δείχνει πως στην πλειονότητα των πειραμάτων τα δένδρα που χρησιμοποιούν το RCU-HTM έχουν υψηλότερες επιδόσεις από τους ανταγωνιστές τους, και ακόμα και στις ελάχιστες περιπτώσεις που δεν είναι τα καλύτερα, η επίδοσή τους είναι πολύ κοντά στην καλύτερη υλοποίηση. Αυτό, σε συνδυασμό με την ευκολία προγραμματισμού που προσφέρει η τεχνική RCU-HTM την καθιστούν την πρώτη τεχνική συγχρονισμού που μπορεί σχετικά εύκολα να εφαρμοστεί σε κάθε τύπου δένδρου αναζήτησης χωρίς να επηρεάζεται σε μεγάλο βαθμό η επίδοση τους.