EphèseLe catalogue de la bibliothèque de l'ECAM

Hybrid ordering protocol for partially-replicated state machine / Charles Vandevoorde 

Public ISBD Titre : Hybrid ordering protocol for partially-replicated state machine Type de document : Travail de fin d'études Auteurs : Charles Vandevoorde, Auteur ; Peter Van Roy, ; Sébastien Combefis, Editeur : ECAM Année de publication : 2018 Note générale : UCL Langues : Anglais (eng) Index. décimale : TFE - Informatique (ECAM) Résumé : State machine replication (SMR) is a technique used to provide fault-tolerant services but SMR are inherently not scalable because every replica executes all commands and stores the full state. Recent works introduce the concept of partially replicated state machine (PSMR) which shards the state into multiple partitions and replicates each partition for fault-tolerance. For multi-partitions replications, the PSMR's ordering protocol needs to orchestrate the ordering across multiple partitions to ensure the global ordering. Currently, no work on PSMR has been done on optimizing data skewness and dynamic workload. In most realistic workloads, partitioning the global state introduces data skewness meaning that the workload is not evenly split between partitions. Unfortunately, skewness induce more load and more latency on some partitions. Multi-partitions operations received by a partition may require more communication to some partitions while others need to communicate rarely. On top of that, real workload is dynamic meaning that data access pattern may change. When the workload characteristic changes, the chosen protocol could deliver a worse latency than expected. This master thesis provides a new adaptive protocol to strive providing optimal ordering latency by combining two communication patterns. One pattern provides an optimal latency with periodic communication while the other is slower but optimized for rare communication patterns. By following the workload characteristics, the proposed protocol can adjust the communication pattern to provide optimal latency. The proposed protocol has been implemented and tested as the ordering layer of a research database named Calvin. Calvin is an implementation of a PSMR which provides a scalable transactional datastore with full ACID-compliance. Hybrid ordering protocol for partially-replicated state machine [Travail de fin d'études] / Charles Vandevoorde, Auteur ; Peter Van Roy, ; Sébastien Combefis,  . - ECAM, 2018. UCL Langues : Anglais (eng) Index. décimale : TFE - Informatique (ECAM) Résumé : State machine replication (SMR) is a technique used to provide fault-tolerant services but SMR are inherently not scalable because every replica executes all commands and stores the full state. Recent works introduce the concept of partially replicated state machine (PSMR) which shards the state into multiple partitions and replicates each partition for fault-tolerance. For multi-partitions replications, the PSMR's ordering protocol needs to orchestrate the ordering across multiple partitions to ensure the global ordering. Currently, no work on PSMR has been done on optimizing data skewness and dynamic workload. In most realistic workloads, partitioning the global state introduces data skewness meaning that the workload is not evenly split between partitions. Unfortunately, skewness induce more load and more latency on some partitions. Multi-partitions operations received by a partition may require more communication to some partitions while others need to communicate rarely. On top of that, real workload is dynamic meaning that data access pattern may change. When the workload characteristic changes, the chosen protocol could deliver a worse latency than expected. This master thesis provides a new adaptive protocol to strive providing optimal ordering latency by combining two communication patterns. One pattern provides an optimal latency with periodic communication while the other is slower but optimized for rare communication patterns. By following the workload characteristics, the proposed protocol can adjust the communication pattern to provide optimal latency. The proposed protocol has been implemented and tested as the ordering layer of a research database named Calvin. Calvin is an implementation of a PSMR which provides a scalable transactional datastore with full ACID-compliance.

Exemplaires

Code-barres	Cote	Support	Localisation	Section	Disponibilité
aucun exemplaire

Documents numériques

Ce document n'est visible qu'après identification thesis-ilovepdf-compressed.pdf Adobe Acrobat PDF

---

1 (1 - 1 / 1) Par page : 25 50 100 200