Transactional Replication: Algorithms and Properties
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
PL Replikacja transakcyjna: algorytmy i własności
polish
- service replication
- transactional systems
- correctness properties
- replikacja usług
- systemy transakcyjne
- własności poprawności
PL Replication is an established method to increase service availability and dependability. It means deployment of a service on multiple machines and coordination of their actions so that a consistent state is maintained across all the service replicas. In case of a (partial) system failure operational replicas continue to provide the service. In this dissertation, we revisit State Machine Replication (SMR) and Deferred Update Replication (DUR), two basic strongly consistent replication schemes. We compare the schemes side-by-side and uncover their strong and weak sides. We study the guarantees provided by SMR and DUR using our new correctness criteria, which we grouped into two families: ♢-opacity and ♢-linearizability. Our properties are not bound to SMR and DUR only. They allow us to formalize the behaviour of a wide variety of replicated schemes that do or do not support transactional semantics, respectively. By establishing a formal relationship between ♢-opacity and ♢-linearizability we can directly compare guarantees provided by SMR and DUR, even though only the latter provides true transactional support. We also compare SMR and DUR experimentally across a wide range of workloads. Our results show that performance-wise, neither scheme is superior. Such a conclusion may come as a surprise since only the latter scheme is potentially scalable with an increasing number of processors. We discuss the characteristics of workloads that are favourable or troublesome for either scheme. Finally, we combine SMR and DUR into a single, versatile replication scheme called Hybrid Transactional Replication (HTR). This way we bring together the best features of SMR and DUR. Not only HTR offers powerful transactional semantics (similarly to DUR) and is free of some limitations regarding the code of the replicated service itself (unlike both SMR and DUR), but it also works well across various workloads, often providing much better performance than either SMR or DUR. All these benefits are provided while maintaining strong correctness guarantees similar to those provided by DUR. By relying on a machine-learning-based approach, HTR can dynamically adopt to changing conditions.
EN Replikacja jest typowym sposobem pozwalającym na zwiększenie dostępności i niezawodności usług pracujących w Internecie. Polega ona na uruchomieniu usługi na wielu maszynach i koordynacji ich działań, tak by repliki usługi utrzymywały spójny stan. W przypadku (częściowej) awarii systemu, działające repliki kontynuują przetwarzanie nieprzerwanie obsługując żądania kierowane przez klientów usługi. W tej rozprawie skupiamy się na dwóch podstawowych silnie spójnych schematach replikacji: replikacji maszyny stanowej (ang. State Machine Replication, SMR) i replikacji z opóźnioną aktualizacją (ang. Deferred Update Replication, DUR). Porównujemy oba podejścia i wskazujemy na ich silne i słabe strony. Badamy gwarancje oferowane przez SMR i DUR korzystając z nowych własności poprawności tworzących dwie rodziny własności: ♢-opacity i ♢-linearizability. Wprowadzone własności pozwalają sformalizować nie tylko gwarancje oferowane przez SMR i DUR, ale także gwarancje oferowane przez wiele innych, transakcyjnych i nietransakcyjnych schematów replikacji. Dzięki formalnemu określeniu związku pomiędzy ♢-opacity i ♢-linearizability, możemy bezpośrednio porównać gwarancje oferowane przez SMR i DUR pomimo tego, że spośród tych dwóch podejść do replikacji, tylko DUR oferuje wsparcie dla semantyki transakcyjnej. SMR i DUR porównujemy również eksperymentalnie badając ich wydajność w kontekście różnego rodzaju obciążeń (różnych typach żądań kierowanych przez klientów do usługi). Wyniki naszych badań pokazują, że pod względem wydajności, żadne z podejść nie jest ściśle lepsze od drugiego. Taki wniosek może wydawać się zaskakujący biorąc pod uwagę to, że tylko w przypadku DUR wydajność systemu może rosnąć wraz ze zwiększającą się liczbą procesorów wykorzystywanych do przetwarzania żądań. Wskazujemy, z jakimi rodzajami obciążeń dobrze radzi sobie każde z podejść, a także jakie rodzaje obciążeń są dla nich problematyczne. W rozprawie przedstawiamy także hybrydową replikacją transakcyjną (ang. Hybrid Transactional Replication, HTR), nowe, wszechstronne podejście do replikacji, które łączy najlepsze cechy SMR i DUR. HTR nie tylko oferuje bogatą semantykę transakcyjną (tak jak DUR), jest wolne od pewnych ograniczeń dotyczących kodu replikowanej usługi (w przeciwieństwie do SMR i DUR), ale także działa dobrze dla różnego rodzaju obciążeń, często oferując znacznie lepszą wydajność niż SMR czy DUR. HTR zachowuje silne gwarancje poprawności, które są analogiczne do tych oferowanych przez DUR. Dzięki mechanizmom wykorzystującym techniki uczenia maszynowego, HTR dynamicznie dostosowuje się do zmieniających się warunków (w tym rodzaju obciążenia).
182
computer sciences and computer science
computer science
DrOIN 1819
public
Tomasz Jurdziński
Wrocław, Polska
15.03.2017
polish
public
Fernando Pedone
Lugano, Szwajcaria
14.02.2017
english
public
dissertation
Poznań, Polska
07.04.2017
Rada Wydziału Informatyki Politechniki Poznańskiej
doktor nauk technicznych w dyscyplinie: informatyka, w specjalności przetwarzanie rozproszone