Invalidation-based replication in the datacenter

Abstract

Distributed in-memory datastores underpin cloud applications that run within a datacenter and demand high performance, strong consistency, and availability. A key feature of datastores is data replication. The data are replicated across servers because a single server often cannot handle the request load. Replication is also necessary to guarantee that a server or link failure does not render a portion of the dataset inaccessible. A replication protocol is responsible for ensuring strong consistency between the replicas of a datastore, even when faults occur, by determining the actions necessary to access and manipulate the data. Consequently, a replication protocol also drives the datastore’s performance. Existing strongly consistent replication protocols deliver fault tolerance but fall short in terms of performance. Meanwhile, the opposite occurs in the world of multiprocessors, where data are replicated across the private caches of different cores. The multiprocessor regime uses invalidations to afford strongly consistent replication with high performance but neglects fault tolerance. Although handling failures in the datacenter is critical for data availability, we observe that the common operation is fault-free and far exceeds the operation during faults. In other words, the common operating environment inside a datacenter closely resembles that of a multiprocessor. Based on this insight, we draw inspiration from the multiprocessor for high-performance, strongly consistent replication in the datacenter. The primary contribution of this thesis is in adapting invalidating protocols to the nuances of replicated datastores, which include skewed data accesses, fault tolerance, and distributed transactions.

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