Replicação máquina de estados paralela com escalonamento híbrido

Abstract

A crescente demanda por aplicações confiáveis e com tempos de resposta cada vez mais baixos vem estimulando as pesquisas sobre o desempenho de serviços tolerantes a falhas há vários anos. Sabemos que projetar aplicações que toleram falhas é fundamental, mas não é suficiente. Uma aplicação confiável cujo tempo de resposta ultrapasse a tolerância (cada vez mais curta) de seus clientes pode ser tão destrutiva para os negócios quanto uma aplicação não confiável. A técnica de Replicação Máquina de Estados (RME), lançada em 1990 e utilizada na implementação de serviços confiáveis, trás consigo um efeito colateral. Em sua forma clássica, ela elimina qualquer tipo de concorrência ou paralelismo no atendimento das requisições dos clientes. Há anos que os principais fabricantes de microprocessadores têm procurado aumentar

o desempenho de seus equipamentos, pelo aumento de sua capacidade de paralelismo, adi- cionando cada vez mais núcleos de processamento em suas arquiteturas multi-core. Por

conseguinte, o comportamento sequencial da RME clássica tornou-se uma séria desvan- tagem. Isso abriu o caminho para um vasto esforço de pesquisa no sentido de aumentar

o desempenho desses serviços replicados, e assim surgiu a Replicação Máquina de Es- tados Paralela (RMEP). A ideia principal desta abordagem é separar os comandos em

conflitantes e não conflitantes, de forma a permitir que comandos não conflitantes sejam executados em paralelo. Dois comandos conflitam quando acessam uma mesma variável e pelo menos um deles altera o seu estado. Nas últimas duas décadas surgiram novas técnicas, algoritmos e estudos no sentido de aperfeiçoar a RMEP. Um aspecto fundamental destas soluções é como escalonar as

requisições dos clientes de modo a permitir que uma parte delas seja executada em pa- ralelo nas réplicas do serviço. Neste contexto, esta dissertação de mestrado propõe uma

abordagem de RMEP que utiliza um método de escalonamento híbrido, com o objetivo de aumentar o desempenho do sistema pelo aumento do seu paralelismo. O método desenvolvido é chamado híbrido pois deriva do aperfeiçoamento de uma combinação de dois proeminentes métodos de escalonamento para RMEP anteriores, o antecipado e o tardio.

vi

O primeiro tem um desempenho excelente com cargas de trabalho com predominância de comandos não conflitantes, porém esse desempenho cai abruptamente na medida que aumentamos a taxa de conflitos. Já o segundo, que supera o primeiro na medida que a taxa de conflitos cresce, tem em seu funcionamento um fator limitante do desempenho quando a taxa de conflitos é reduzida visto que utiliza um paralelizador único para gerenciar as dependências dos comandos. A abordagem híbrida proposta neste trabalho busca agrupar as vantagens de cada uma destas abordagens. Experimentos realizados mostram que a abordagem híbrida apresentou um desempenho superior aos de seus antecessores em diversas cargas de trabalho, além de eliminar as limitações anteriormente elencadas. Também foi realizado um estudo de caso sobre a aplicação de uma RMEP, com o método de escalonamento híbrido, em sistemas de Blockchain.