Redução do custo da durabilidade em Replicação Máquina de Estados através de checkpoints particionados

Abstract

Replicação é uma técnica comumente utilizada para implementação de serviços tolerantes a falhas. Ao ser replicado, o serviço se mantém operando corretamente apesar da falha de uma quantidade limitada de réplicas. Para aumentar a disponibilidade, estratégias de recuperação se fazem necessárias, desta forma réplicas extras podem ser adicionadas durante a execução do serviço. Replicação Máquina de Estados (RME) é um tipo de replicação bastante difundido para implementação de sistemas tolerantes a falhas. Em RME, todas as réplicas partem de um mesmo estado inicial e executam a mesma sequência determinística de comandos. Desta forma, as réplicas transitam pela mesma sequência de estados e produzem exatamente as mesmas respostas para cada requisição. Para garantir que réplicas faltosas recuperem-se ou novas réplicas sejam adicionadas ao sistema, estratégias de durabilidade como logging, checkpointing e transferência de estados devem ser implementadas nas réplicas do serviço. Enquanto processam as requisições, as réplicas registram os comandos executados em um log em armazenamento persistente, permitindo que réplicas faltosas obtenham uma sequência de comandos já executada. Para evitar que o log cresça indefinidamente, réplicas salvam periodicamente seus estados em armazenamento persistente (checkpoint) e removem do log os comandos cujas alterações estão refletidas no checkpoint. Apesar de melhorarem a disponibilidade, estratégias de durabilidade degradam a performance do serviço. Técnicas tradicionais de checkpointing exigem que a execução de novas requisições seja interrompida enquanto o estado é salvo. Esta sincronização é necessária para garantir consistência, porém a vazão do serviço é reduzida e a latência de resposta aumenta. Neste trabalho é proposta uma estratégia que reduz a degradação do desempenho causada por checkpointing com base no particionamento do estado da aplicação. É apresentado um algoritmo onde diferentes threads de execução realizam checkpointing de determinadas partições em diferentes instantes de tempo. Desta maneira, durante o salvamento de estado, são impedidos de executar somente os comandos que operam sobre a partição que encontra-se em checkpointing. Requisições sobre as demais partições podem ser executadas normalmente. Através desta abordagem foi possível obter melhor desempenho durante a execução do serviço. A nova estratégia apresentou melhores resultados na vazão do serviço. Ainda, foi possível observar que a latência de resposta para as requisições realizadas durante a realização de checkpoints foi consideravelmente menor. A nova abordagem apresentou menor tempo necessário para recuperação do sistema.

Replication is a technique commonly adopted on the development of faulttolerant systems. By replicating a service, it remains accessible by clients despite the occurrence of faults in a bounded number of replicas. To increase availability, recovery strategies are required, so that extra replicas can be added to the system at run time. State Machine Replication (SMR) is a well-known replication technique for implementing strong consistency across replicas. In SMR, every replica starts in the same state and executes a totally ordered sequence of deterministic commands. Thus, each replica evolves through the same sequence of state changes and produce exactly the same outputs for every request. In order to support recovery of faulty replicas or addition of new ones, replicas must implement durability strategies, such as logging, checkpointing and state transfer. While processing commands, replicas log these commands in a persistent storage, allowing new replicas retrieve a sequence of commands already executed. To avoid the continuos growth of logs, replicas periodically save their states and truncates their logs, removing those commands represented by the checkpoints. Althought durability approaches benefits overall availability, they hurt systems performance. Traditional checkpointing approaches interrupt the execution of incoming commands while service state is being saved. This synchronization is necessary to ensure consistence, but it causes a reduction in the throughput and latency increase. This work proposes a strategy based on state partition to aleviate the performance degradation caused by checkpointing. The work presents a new algorithm that save states at different times. This way, during a checkpointing, new commands are blocked only if they access a partition being saved. Requests addressed to other partitions can be normally executed. By employing this new approach one can observe better performance during normal service execution. The new approach presented higher throughput. Moreover, it was noticed that the latency for those requests issued during the checkpointing execution where considerable low. The new approach presented lower time for systems recovery.