Dependable data storage with state machine replication

Tese de mestrado em Informática, Universidade de Lisboa, Faculdade de Ciências, 2014State Machine Replication (SMR) is a technique to replicate information across servers, also called replicas, providing fault tolerance to services. Instead of execute in a single server, requests from multiple clients are ordered and executed in a set of replicas. Results are confirmed to the clients once a predefined quorum of replicas replies. Several studies prove possible to tolerate up to f faults using 2f + 1 replicas. Byzantine Fault Tolerant (BFT) SMR configurations, where replicas can behave in an arbitrary mode, require f additional replicas, with the total of 3f + 1 replicas. When a replica is detected faulty, it has to be recovered with an updated state to reduce the vulnerability of the system. This state is generated during the service execution, when write operations are logged. To bind the size of the log and the time to replay it, periodic snapshots of the service state, or checkpoints, are taken and the log reset. During recovery the checkpoint and the log are transferred from other replicas. To provide resilience to co-related faults, information has to be logged in durable storage. Synchronous writes in durable storage and constant checkpoints can affect throughput and latency of the system as replicas have to wait for information to be stored before reply. When a checkpoint is being taken the system cannot make progress because the state cannot be changed. This may cause the service to be interrupted for several seconds during a checkpoint. The state transfer to a recovering replica can also cause perturbations in the system execution, as correct replicas has to read and transfer the state, composed by the checkpoint, log and digests of messages in case of BFT systems. In this dissertation we present three techniques to improve the performance of state storage and transfer in a BFT SMR protocol - BFT-SMART. The first, Parallel Logging stores information in the log in parallel with its execution by the application. The second, Sequential Checkpointing makes only one replica take a checkpoint at a time, in a round-robin fashion, allowing the system to make progress during that period. The last technique, Collaborative State Transfer (CST) reduces the perturbation in a system during state transfer to a recovering replica by having one replica providing the checkpoint and the remaining providing portions of the log. We also present algorithms that address the problem of co-related failures. When several replicas fail at the same time it is possible to start them simultaneously and compare the stored state before having the service available again. After presenting the techniques, we provide a prototype implementation called Dura-SMaRt with an evaluation against BFT-SMART to compare the efficiency of the new techniques. We performed the evaluation with two applications: a consistent key-value store – SCKV-store – and a coordination service that stores information in tuple spaces – DepSpace. Next, we evaluate Dura-SMaRt in a complex use, having a database replication middleware built on top of it. SteelDB, provide fault tolerance for transaction processing in database management systems (DBMS). Transactional databases provide durability for information systems executing operations inside boundaries called transactions. Transactions guarantee several properties, amongst which, atomicity and isolation. Atomicity enforces that all operations executed inside a transaction are confirmed, or none is. Isolation guarantees that operations inside a transaction are only visible for other transactions after it is finished. Concurrency mechanisms implementations allow several transactions, from several clients to be executed at the same time, improving the performance of a DBMS. To provide dependability to DBMS, several DBMS vendors provide replications mechanisms that usually rely on the efficiency of fail detection and recovery. Such replication mechanisms are also attached to the vendor implementation. With SteelDB we provide transparent Byzantine fault tolerance with 3f + 1 replicated databases. SteelDB requires no changes in the client code as it provides a driver implementation of the JDBC specification. Clients have only to switch the current driver provided by the database vendor it is using to the driver provided by SteelDB. After describing the concepts and implementation of SteelDB we present an evaluation performed on SteelDB during the last year of the FP7 TClouds project. We evaluated SteelDB for functional and performance aspects with a real application executing different types of transactions and comparing results with executions on different environments. We compared SteelDB executions in local area networks, private, public and hybrid clouds discussing the differences in performance and efficiency of optimizations present in the middleware. After SteelDB evaluation we discuss the related work to state management in SMR and database replication middlewares. Finally we will conclude the work with a discussion on the results obtained and purposes for future work.Replicação de Máquina de Estados (SMR) é uma técnica para replicar informações entre vários servidores, também chamados de réplicas, provendo tolerância a faltas para aplicações. Ao invés de executar os pedidos dos clientes em um único servidor, pedidos de vários clientes que alteram o estado de uma aplicação passam por um protocolo de ordenação e são entregues na mesma ordem para um conjunto de réplicas. Os resultados somente são confirmados aos clientes após um quórum pré-definido de réplicas responder. Vários estudos provaram ser possível tolerar até f faltas com o uso de 2f + 1 réplicas. Configurações para SMR com Tolerância a Faltas Bizantinas (BFT), onde réplicas podem apresentar comportamento arbitrário, necessitam de f réplicas adicionais, com o total de 3f + 1 réplicas. Quando uma réplica percebe que esta atrasada em relação às demais, ou uma nova réplica é adicionada ao sistema, ela precisa instalar uma a versão atualizada do estado, para poder participar do protocolo de ordenação e processamento dos pedidos, restaurando assim a tolerância do sistema a faltas. Réplicas geram um log das operações executadas para terem uma cópia atualizada do estado, necessária a uma possível recuperação. As operações de escrita são armazenadas de forma sequencial no log. Para limitar seu tamanho e o tempo para reproduzí-lo em uma réplica que está recuperar-se, as réplicas tiram cópias do estado periodicamente em checkpoints e, apagam o log em seguida. Durante a recuperação de uma réplica, o checkpoint e o log são transferidos pelas demais. A réplica que está a recuperar-se instala o checkpoint recebido e executa as operações do log antes de confirmar às demais que está pronta a processar pedidos novamente. Para oferecer tolerância a faltas co-relacionadas, onde várias réplicas podem apresentar falhas ao mesmo tempo, informações precisam ser armazenadas em mídia durável. Escritas síncronas em mídia durável e checkpoints constantes podem diminuir o throughput e aumentar a latência do sistema pois as réplicas precisam esperar até que a escrita seja concluída, antes de confirmar a operação ao cliente. De outra forma, no caso de uma falha antes do fim da escrita, poderíamos ter dados confirmados ao cliente mas não armazenados. Realizamos experimentos que provam que a substituição da mídia por opções mais rápidas, nomeadamente, disco rígido por SSD, apesar de diminuir o tempo de escrita ainda afeta consideravelmente o throughput da aplicação. Enquanto um checkpoint do estado é gerado, a aplicação não pode estar a processar operações de escrita, pois estas podem alterar este estado. Isto faz com que o throughput do sistema seja zero durante este período, que pode demorar vários segundos, dependendo do tamanho do estado. Conforme demonstramos através de gráficos de desempenho da aplicação, a transferência de estado a uma réplica que está a recuperar-se pode também causar perturbações nas réplicas que estão a transferí-lo, pois estas precisam ler dados em mídia durável e transferir o estado pela rede. Em situações onde o tamanho do estado é grande, a transferência pode afectar a comunicação com as demais réplicas e com os clientes. Apresentamos neste trabalho três técnicas puramente algorítmicas que melhoram o desempenho no armazenamento e transferência de estado em um protocolo BFT SMR chamado BFT-SMART. A primeira, Parallel Logging, faz as réplicas armazenarem as operações no log em paralelo com sua execução¸ ao pela aplicação. Em aplicações onde o tempo para se executar uma operação é considerável, pode-se reduzir o tempo total ao executar a operação e o log em threads diferentes. A segunda, Sequential Checkpointing faz somente uma das réplicas tirar um checkpoint por vez, sequencialmente, permitindo ao sistema fazer progresso nesse período. A terceira técnica, Collaborative State Transfer (CST) define uma estratégia para transferência de estado onde uma réplica envia o checkpoint da aplicação e as demais enviam partes do log, reduzindo o efeito da transferência de estado nas réplicas que estão a enviá-lo. Apresentamos também algoritmos para resolver o problema de faltas co-relacionadas. No caso de uma falta onde todas as réplicas vão abaixo, é possível fazê-las retomar o serviço e iniciar a execução¸ ao novamente, após iniciadas. Implementamos as novas técnicas apresentadas em um protótipo chamado Dura-SMaRt para obtermos uma avaliação de seu efeito no desempenho de um sistema replicado. Apresentamos uma avaliação do protótipo e do BFT-SMART com duas aplicações diferentes construídas sobre estes, uma consistent key-value store chamada SCKV-Store e um serviço de coordenação que utiliza um espaço de tuplos para armazenamento de dados chamado DepSpace. Comparamos os resultados de diversos experimentos para demonstrar que as novas técnicas reduzem o impacto da escrita de operações em mídia durável. Apresentamos resultados que mostram que a execução das operações de escrita em paralelo com seu armazenamento no log não afectam o throughput em para aplicações onde o tempo de execução de mensagens é considerável. As novas técnicas também reduzem o impacto que a geração de um checkpoint tem no throughput do sistema. Por fim demonstramos que a transferência de estado tem menor impacto no throughput do sistema com as novas técnicas quando comparadas ao modelo anterior onde uma réplica era responsável por enviar o checkpoint e o log das operações. De seguida, avaliamos o Dura-SMaRt em um caso de uso complexo: um middleware para replicação de bases de dados chamado SteelDB. Este middleware utilizou o Dura-SMaRt para replicação de dados, oferecendo tolerˆancia a faltas para transações em sistemas de gerenciamento de bases de dados (DBMS). Bases de dados transacionais fornecem durabilidade para sistemas de informação ao executar operações dentro de barreiras chamadas transações. Uma transação garante algumas propriedades, entre as quais atomicidade e isolamento. Atomicidade implica que todas as operações executadas são confirmadas, ou nenhuma é. Isolamento garante que alterações presentes dentro de uma transação só serão visíveis às demais após o fim desta. Estas propriedades permitem a utilização da base de dados simultaneamente por vários clientes, aumentando a concorrência na execução de operações. Para aumentar a disponibilidade e recuperação a faltas, vários desenvolvedores de DBMS fornecem mecanismos de replicação de dados. Estes mecanismos geralmente estão ligados a eficiência dos sistemas de deteccão de falha e recuperação. Eles também estão intrinsecamente ligados ao fabricante da base de dados escolhido. Com o SteelDB n´os oferecemos tolerância transparente a faltas Byzantinas, com o uso de 3f + 1 bases de dados. O SteelDB fornece aos clientes uma implementação da especificação JDBC, portanto, clientes que já utilizam um driver JDBC para aceder a uma base de dados, somente precisam trocá-lo pelo driver fornecido pelo SteelDB. Depois de descrever os conceitos e implementação do middleware SteelDB, apresentamos uma avaliação deste, realizada no último ano do projeto FP7 TClouds. Esta avaliação testou diversos aspectos de desempenho e funcionalidade em uma aplicação real com diversos tipos de transações, fornecida por um dos parceiros do projeto. Descrevemos a configuração e execução do SteelDB em diversos ambientes como redes locais, clouds privadas, públicas e híbridas. Comparamos de seguida os resultados da execução nestes diferentes ambientes para avaliar a eficiência de optimizações incluídas no middleware. Apesar da utilização de bases locais ter desempenho consideravelmente melhor com relação à replicação com o SteelDB, bases locais não fornecem tolerância a faltas. Também demonstramos que quando o tamanho das transações aumenta, a diferença entre os tempos de execução diminui, evidenciando o custo da troca de mensagens entre redes remotas. Otimizações incluídas no SteelDB, entretanto, diminuem o número de mensagens necessárias por operação, reduzindo também o seu tempo de execução total. Avaliamos também o desempenho do SteelDB em simulações com diferentes tipos de faltas. Nos casos de teste que avaliamos, as faltas não afectam consideravelmente o desempenho do SteelDB, uma vez que o protocolo de replicação Dura-SMaRt não precisa esperar por respostas de todas as réplicas antes de confirmar as operaçõees aos clientes. Após apresentarmos a avaliação do SteelDB, discutimos os trabalhos relacionados com o gerenciamento de estado em sistemas SMR e também estudos e alternativas para replicação de bases de dados com o uso de SMR. Concluímos com uma discussão dos resulados obtidos e propostas de trabalhos futuros