| Resumo: | A replicação máquina de estados é uma técnica bem estabelecida para desenvolvimento de sistemas tolerantes a faltas. Em parte, isso é explicado pela simplicidade da abordagem e sua garantia de consistência forte. O modelo de replicação máquina de estados tradicional baseia-se na execução sequencial de requisições para garantir consistência forte entre as réplicas. A sequencialidade da execução, no entanto, compromete a escalabilidade. Recentemente, algumas propostas sugeriram paralelizar a execução de algumas requisições visando um aumento na vazão. Apesar do sucesso da replicação máquina de estados paralela em obter alto desempenho, as implicações deste modelo em procedimentos de recuperação são desprezadas. Mesmo para a abordagem de replicação máquina de estados tradicional, poucos estudos têm considerado as questões envolvidas na recuperação de réplicas defeituosas. A motivação desta tese é elucidar os desafios e implicações no desempenho decorrentes de mecanismos de pontos de verificação e recuperação em replicação máquina de estados paralela. A tese também avança no estado-da-arte, propondo novos algoritmos para pontos de verificação e recuperação no contexto de replicação máquina de estados paralela. Criar pontos de verificação de forma eficiente em tais modelos é mais desafiador do que na replicação máquina de estados clássica porque deve-se considerar a execução concorrente de comandos. Nesta tese, nós revisitamos as técnicas para pontos de verificação em abordagens paralelas de replicação máquina de estados e comparamos o impacto destas no desempenho através de simulação. Além disso, nós propomos duas técnicas de ponto de verificação para um destes modelos paralelos.Recuperar uma réplica requer: (a) obter e instalar o estado de um ponto de verificação de uma réplica atualizada, e (b) recuperar e re-executar os comandos não refletidos no ponto de verificação. Técnicas paralelas para replicação máquina de estado tornam a recuperação de réplicas particularmente difícil uma vez que a vazão de processamento durante a execução normal (isto é, na ausência de falhas) é muito alta. Consequentemente, o registo de comandos que precisa ser re-executado é tipicamente grande, o que atrasa a recuperação. Nós apresentamos duas novas técnicas para otimizar a recuperação em replicação máquina de estados paralela. A primeira técnica permite que novos comandos sejam executados em paralelo com a re-execução dos comandos não refletidos no ponto de verificação. Isto ocorre antes da réplica estar completamente atualizada. A segunda técnica introduz recuperação de estado sob-demanda, permitindo que segmentos de um ponto de verificação possam ser recuperados apenas quando necessários, ou ainda, concorrentemente. Nós avaliamos o desempenho de nossas técnicas de recuperação usando um protótipo completo para replicação máquina de estados paralela e comparamos o desempenho destas técnicas com mecanismos tradicionais de recuperação em diferentes cenários.
A well-established technique used to design fault-tolerant systems is state machine replication. In part, this is explained by the simplicity of the approach and its strong consistency guarantees. The traditional state machine replication model builds on the sequential execution of requests to ensure consistency among the replicas. Sequentiality of execution, however, threatens the scalability of replicas. Recently, some proposals have suggested parallelizing the execution of replicas to achieve higher performance. Despite the success of parallel state machine replication in accomplishing high performance, the implication of such models on the recovery is mostly left unaddressed. Even for the traditional state machine replication approach, relatively few studies have considered the issues involved in recovering faulty replicas. The motivation of this thesis is clarifying the challenges and performance implications involved in checkpointing and recovery for parallel state machine replication. The thesis also aims to advance the state-of-the-art by proposing novel algorithms for checkpointing and recovery in the context of parallel state machine replication. Performing checkpoints efficiently in such parallel models is more challenging than in classic state machine replication because the checkpoint operation must account for the execution of concurrent commands. In this thesis, we review checkpointing techniques for parallel approaches to state machine replication and compare their impact on performance through simulation. Furthermore, we propose two checkpoint techniques for one of these parallel models.Recovering a replica requires (a) retrieving and installing an up-to-date replica checkpoint, and (b) restoring and re-executing the log of commands not reflected in the checkpoint. Parallel state machine replication render recovery particularly challenging since throughput under normal execution (i. e. , in the absence of failures) is very high. Consequently, the log of commands that need to be applied until the replica is available is typically large, which delays the recovery. We present two novel techniques to optimize recovery in parallel state machine replication. The first technique allows new commands to execute concurrently with the execution of logged commands, before replicas are completely updated. The second technique introduces ondemand state recovery, which allows segments of a checkpoint to be recovered concurrently. We experimentally assess the performance of our recovery techniques using a full-fledged parallel state machine replication prototype and compare the performance of these techniques to traditional recovery mechanisms under different scenarios. |
