Extending state machine replication through composition

Abstract

A Replicação Máquina de Estados (RME) é uma abordagem bem estabelecida para implementar serviços altamente disponíveis e tolerantes a falhas. No modelo tradicional de RME, todas as réplicas executam as mesmas requisições de forma determinística e na mesma ordem, garantindo um modelo de consistência forte. Nas últimas décadas, a RME ganhou popularidade, levando a uma extensa pesquisa que aprimorou sua resiliência, desempenho e escalabilidade. No entanto, um aspecto ainda não abordado na RME é a composição de serviços. Neste trabalho, damos os primeiros passos nessa direção, apresentando uma definição formal de replicação de máquina de estados e composicionalidade. Ao combinar RMEs por meio de composição, permitimos a reutilização de serviços existentes para construir sistemas mais complexos e confiáveis. Esta abordagem modular proporciona soluções flexíveis e fracamente acopladas, avançando a base teórica de RME e alinhando-se com o desenvolvimento de aplicações em larga escala baseadas em computação em nuvem e microsserviços. Demonstramos que o uso da composição em RME permite adicionar novas funcionalidades às especificações existentes de RME e estende a semântica da operação do serviço, permitindo que diferentes réplicas de máquinas de estados executem etapas complementares para a mesma operação. O sharding e a partição de estados também são facilitados pela composição de RME, pois variáveis de estado disjuntas podem ser atribuídas a RMEs separadas. Além disso, esse trabalho apresenta exemplos ilustrativos de composição em SMR e introduzimos uma arquitetura a alto nível, mostrando os componentes essenciais, e suas interações para suportar o processo de composição. Para demonstrar sua praticabilidade, apresentamos uma API para construir um SMR com composição que combina comunicação baseada em RPC com configuração declarativa em formato YAML.

Abstract: State Machine Replication (SMR) is a well-established approach for implementing highly available and fault-tolerant services. In the traditional SMR model, all replicas execute the same requests deterministically and in the same order, ensuring strong consistency. Over the past decades, SMR has gained popularity, leading to extensive research that has enhanced its resilience, performance, and scalability. However, one aspect not yet addressed in SMR is service composition. In this work, we take the first steps in this direction, presenting a formal definition of state machine replication and compositionality. By combining SMRs through composition, we enable the reuse of existing services to build more complex and reliable systems. This modular approach provides loosely coupled and flexible solutions, advancing the theoretical background of SMR and aligning with large-scale application development based on cloud computing and microservices. We demonstrate that using composition in SMR allows adding new features to existing SMR specifications and extends the service operation's semantics by enabling different state machine replicas to perform complementary steps for the same operation. Sharding and state partitioning are also facilitated by SMR composition, as disjoint state variables can be assigned to separate SMRs. Furthermore, this work presents illustrative examples of composing SMR and introduces a high-level architecture, detailing its essential components and their interactions to support the composition process. To demonstrate its practicality, we present an API for constructing SMR with composition that combines RPC-based communication with a declarative YAML configuration format.