On the feasibility of multi-leader replication in the early tiers

dc.contributor.advisorKao, Odej
dc.contributor.authorJungnickel, Tim
dc.contributor.grantorTechnische Universität Berlinen
dc.contributor.refereeMĂĽhl, Gero
dc.contributor.refereeNestmann, Uwe
dc.contributor.refereeKao, Odej
dc.date.accepted2018-05-30
dc.date.accessioned2018-06-18T09:30:07Z
dc.date.available2018-06-18T09:30:07Z
dc.date.issued2018
dc.descriptionPublished in print by Universitätsverlag der TU Berlin, ISBN 978-3-7983-3001-6 (ISSN 2199-5249)en
dc.description.abstractIn traditional service architectures that follow the service statelessness principle, the state is primarily held in the data tier. Here, service operators utilize tailored storage solutions to guarantee the required availability; even though failures can occur at any time. This centralized approach to store and process an application’s state in the data tier implies that outages of the entire tier cannot be tolerated. An alternative approach, which is in focus of this thesis, is to decentralize the processing of state information and to use more stateful components in the early tiers. The possibility to tolerate a temporary outage of an entire tier implies that the application’s state can be manipulated by the remaining tiers without waiting for approval from the unavailable tier. This setup requires multi-leader replication, where every replica can accept writes and forwards the resulting changes to the other replicas. This thesis explores the feasibility of using multi-leader replication to store and process state in a decentralized manner across multiple tiers. To this end, two replication mechanisms, namely Conflict-free Replicated Data Types and Operational Transformation, are under particular investigation. We use and extend both mechanisms to demonstrate that the aforementioned decentralization is worth considering when designing a service architecture. The challenges that arise when following our approach go back to fundamental impossibility results in distributed systems research, i.e. the impossibility to achieve a fault-tolerant consensus mechanism in asynchronous systems and the inevitable trade-off between availability and consistency in the presence of failures. With this thesis, we contribute to close the exposed gaps of both results by providing usable alternatives for standard IT services. We exemplify the feasibility of our alternatives with a fully distributed IMAP service and a programming library that provides the necessary extension to utilize our approach in a variety of web-based applications. All contributions of this thesis are based on both theory and practice. In particular, all extensions to the existing multi-leader replication mechanisms were proven to satisfy the necessary properties. Moreover, those extensions were also implemented as prototypical applications and evaluated against the corresponding de facto standard software from the industry.en
dc.description.abstractBasierend auf dem “service statelessness principle” ist es üblich, Softwaredienste so zu entwerfen, dass der Zustand des Dienstes primär in einer gekapselten Datenschicht verarbeitet wird. Innerhalb der Datenschicht werden spezielle Lösungen verwendet, um die Verfügbarkeit der Daten sicherzustellen. Dieser zentralisierte Ansatz hat zur Folge, dass ein Ausfall oder eine temporäre Nichtverfügbarkeit der gesamten Datenschicht zwangsweise zur Nichtverfügbarkeit des gesamten Dienstes führt. Ein alternativer Ansatz, welcher in dieser Arbeit erforscht wird, ist die dezentralisierte Speicherung und Verarbeitung der Daten in den darüberliegenden Softwareschichten. Um in diesem Ansatz einen Ausfall der gesamten Datenschicht zu kompensieren, ist es zwingend notwendig, dass die verbleibenden Schichten die eingehenden Anfragen ohne die Bestätigung durch die Datenschicht beantworten können. Hierfür wird eine Replikationsarchitektur benötigt, in der jedes Replikat die Anfragen direkt beantworten kann; die so genannte “multi-leader replication”. In dieser Arbeit werden diese Replikationsarchitekturen verwendet, um den Zustand und die Daten eines Dienstes zu dezentralisieren und über mehrere Schichten zu replizieren. Hierbei werden zwei Mechanismen detaillierter betrachtet: “Conflict-free Replicated Data Types” und “Operational Transformation”. Anschließend werden beide Mechanismen erweitert und hinsichtlich der Verwendbarkeit für den beschriebenen Ansatz geprüft. Als Ergebnis dieser Arbeit wird gezeigt, dass ein dezentralisierter Ansatz mit den vorgestellten Mechanismen in Betracht gezogen werden kann. Die Herausforderungen, die bei der Anwendung dieses Ansatzes entstehen, basieren auf nachweislich unlösbaren Problemen aus der Forschung von Verteilten Systemen. Dazu gehört die Unlösbarkeit von Konsensus und die unausweichliche Abwägung zwischen Verfügbarkeit und Konsistenz in einem verteilten System mit Ausfällen. Diese Arbeit trägt dazu bei, die entstehenden Lücken, welche aus diesen fundamentalen Ergebnissen resultieren, zu schließen und die vorgeschlagenen Lösungen für reale IT Dienste anwendbar zu machen. Dieses wird anhand eines dezentralen IMAP Dienstes und einer Programmierbibliothek für Webanwendungen verdeutlicht. Alle Bestandteile dieser Doktorarbeit verbinden Theorie und Praxis. Alle vorgeschlagenen Erweiterungen für bestehende Replikationssysteme werden in formalen Modellen verifiziert und prototypisch implementiert. Die Implementierungen werden außerdem mit vergleichbarer Standardsoftware, welche dem heutigen Stand der Technik entspricht, in praktischen Experimenten evaluiert.de
dc.identifier.eissn2199-5257
dc.identifier.isbn978-3-7983-3002-3
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/7947
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-7109
dc.language.isoenen
dc.publisher.nameUniversitätsverlag der TU Berlinen
dc.publisher.placeBerlinen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subject.ddc000 Informatik, Informationswissenschaft, allgemeine Werkede
dc.subject.otherverteilte Systemede
dc.subject.otherReplikationde
dc.subject.otherZuverlässigkeitde
dc.subject.otherFehlertoleranzde
dc.subject.otherdistributed systemsen
dc.subject.otherreplicationen
dc.subject.otherreliabilityen
dc.subject.otherfault toleranceen
dc.titleOn the feasibility of multi-leader replication in the early tiersen
dc.title.translatedĂśber die Realisierbarkeit von Multi-Leader Replikation in den frĂĽhen Softwareschichtende
dc.typeDoctoral Thesisen
dc.type.versionpublishedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 4 Elektrotechnik und Informatik::Inst. Telekommunikationssysteme::FG Komplexe und Verteilte IT-Systemede
tub.affiliation.facultyFak. 4 Elektrotechnik und Informatikde
tub.affiliation.groupFG Komplexe und Verteilte IT-Systemede
tub.affiliation.instituteInst. Telekommunikationssystemede
tub.publisher.universityorinstitutionUniversitätsverlag der TU Berlinen
tub.series.issuenumber11en
tub.series.nameFoundations of computingen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
jungnickel_tim.pdf
Size:
2.2 MB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.9 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections