Planet-scale leaderless consensus

As aplicações de web modernas replicam os seus dados à escala planetária e exigem fortes garantias na coerência dos seus dados mais críticos. Essas garantias são geralmente fornecidas por meio de replicação de máquina de estados (RME). Avanços recentes em RME concentraram-se em protocolos sem líder, pois estes melhoram o desempenho e a disponibilidade das soluções tradicionais baseadas em Paxos. Embora os protocolos sem líder se tenham mostrado muito promissores, estes são ainda pouco adequados para sistemas de escala planetária, pois utilizam grandes quóruns, oferecem um desempenho imprevisível e têm mecanismos de recuperação complexos. Nesta tese propomos dois protocolos sem líder, Atlas e Tempo, adaptados para sistemas de escala planetária. O Atlas minimiza o tamanho dos seus quóruns fazendo uso da observação de que falhas simultâneas em centros de dados são raras. Também processa uma percentagem elevada de comandos da aplicação em uma única round trip, mesmo quando estes comandos conflituam. O Atlas consegue isto com um mecanismo de recuperação que é significativamente mais simples do que os protocolos sem líder que o precederam. O Tempo baseia-se no Atlas, mas atinge um rendimento superior e oferece um desempenho previsível mesmo em cargas de trabalho com elevado nível de conflitos. Para obter estes benefícios, o Tempo marca cada comando da aplicação com uma timestamp e executa-o somente após esta timestamp se tornar estável, ou seja, quando todos os comandos com uma timestamp menor são conhecidos. Ambos os mecanismos para gerar uma timestamp e detetar quando esta fica estável são totalmente descentralizados, evitando assim a necessidade de um líder. Avaliámos o Atlas e o Tempo em ambientes geo-distribuídos reais e simulados e demonstramos que eles superam as alternativas oferecidas pelo estado da arte.

Name thesis:degree_name

Programa de Doutoramento em Informática das Universidades do Minho, de Aveiro e do Porto

Grantor

Universidade do Minho

Year dc:date.issued

2022

Author dc:creator

• Duarte, Vitor Manuel Enes

Advisors dc:contributor.advisor

• Gotsman, Alexey
• Baquero, Carlos

• Consenso distribuído
• Geo-replicação
• Tolerância a falhas
• Consensus
• Fault tolerance
• Geo-replication

Statement dc:rights

• openAccess

Licence dc:rights.uri

• http://creativecommons.org/licenses/by/4.0/

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1822/81307

OAI record oai:identifier

http://repositorium.sdum.uminho.pt/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Arepositorium.uminho.pt%3A1822%2F81307