Scaling State Machine Replication

Decanato - Facoltà di scienze informatiche

Data: 23 Luglio 2020 / 14:30 - 17:00


You are cordially invited to attend the PhD Dissertation Defense of Long Hoang Le on Thursday July 23rd, 2020 at 14:30 on Zoom.

Today's online services must meet strict availability and performance requirements. State machine replication (SMR), one of the most fundamental approaches to increasing the availability of services without sacrificing strong consistency, provides configurable availability but limited performance scalability. The lacking of scalability of SMR due to the fact that every replica has to execute all commands, which limits the overall performance by the throughput of a single replica, so adding servers does not increase the maximum throughput. Scalable State Machine Replication (S-SMR) achieves scalable performance by partitioning the service state and coordinating the ordering and execution of commands. While S-SMR scales the performance of single-partition commands with the number of deployed partitions, replica coordination needed by multi-partition commands introduces an overhead in the execution of multi-partition commands. In this thesis, we propose and implement the following ideas: (i) Dynamic scalable state machine replication (DS-SMR), (ii) Dynastar: Optimized partitioning for SMR. DS-SMR addresses the problem of S-SMR by allowing repartitioning the service state dynamically, based on the workload. Variables that are usually accessed together are moved to the same partition, which significantly improves scalability. To provide better partitioning for DS-SMR, we develop Dynastar, a novel approach to scaling SMR. Dynastar also uses dynamically repartitioning state technique, combined with a centralized oracle, to maintain a global view of workload and inform heuristics about data placement. Using this oracle, Dynastar is able to adapt to workload changes over time, while also minimizing the number of state changes. The performance evaluation using two benchmarks, a social network based on real data and TPC-C, shows that Dynastar is a practical technique that achieves excellent throughput.

Dissertation Committee:
- Prof. Fernando Pedone, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Marc Langheinrich, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Robert Soulé, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Miguel Correia, Universidade de Lisboa, Portugal (External Member)
- Prof. Rachid Guerraoui, EPFL, Switzerland (External Member)
- Prof. Pawel Wojciechowski, Poznan University of Technology, Poland (External Member)