Aplicação do framework ISS ao protocolo Paxos

Abstract

Protocolos de consenso são um bloco fundamental para a construção de sistemas distribuídos que garantem a consistência das decisões tomadas por um grupo de processos distribuídos, mesmo em casos de múltiplas falhas. Eles se mostram essenciais para a construção de serviços distribuídos com alta disponibilidade e vazão, como eleição de líderes, replicação de máquinas de estado e bases de dados distribuídas. As variadas necessidades que estes sistemas possuem levaram a criação de diversas variantes de protocolos de consenso, com características que melhor sirvam a cada serviço e situação. Uma grande parte destas variantes, podem traçar sua origem para o Paxos, um dos primeiros protocolos de consenso distribuído e que serviu como base para a criação de novos algoritmos como o Multi-paxos, Fast Paxos, Egalitarian Paxos e WPaxos. Uma destas classes de variantes, os algoritmos multi-líder, são comumente utilizados de forma a atender as demandas crescentes por maior escalabilidade e vazão em sistemas distribuídos. Neste contexto, a presente monografia aplicou o framework ISS, capaz de aumentar a escalabilidade e vazão de um protocolo de consenso por meio de uma estratégia multi-líder, ao Paxos, avaliando seu desempenho quanto a vazão, latência e escalabilidade quando comparado a outros protocolos multi-líder. O framework ISS, implementado em Go com a ajuda da biblioteca Paxos, apresentou melhor vazão que outros protocolos multi-líder avaliados, no entanto também apresentou elevada latência e potencialmente pior escalabilidade.

Distributed consensus protocols are one of the fundamental construction blocks of distributed systems. They guarantee the consistency of decisions made by a group of processes, even in cases of multiple failures, being essential to the construction of services with high availability and throughput, such as leader election, state machine replication and distributed databases. The varying needs of these systems has led to the creation of a diverse array of consensus protocol variants, with characteristics that better suit each service and situation. Many of these variants can trace their origins back to Paxos, one of the firsts distributed consensus protocols and base for the creation of new algorithms such as Multi-Paxos, Fast Paxos, Egalitarian Paxos and WPaxos. Some of these variants, classified as multi-leader algorithms, are commonly utilized in order to better meet growing demands for scalability and throughput in distributed systems. As such, this thesis applied the ISS framework, capable of increasing scalability and throughput of consensus protocols by utilizing a multi-leader strategy, to the Paxos protocol, evaluating its performance pertaining to throughput, latency and scalability when compared to other multi-leader protocols. The ISS framework, implemented in Go with the Paxi library, presented a better throughput than other multi-leader protocols that were evaluated, but also presented an elevated latency and potentially worse scalability.