Driftwood: decentralized Raft consensus

Abstract

The Raft consensus algorithm allows multiple state machine replicas to behave as a single and robust system, capable of tolerating various faults, offering more resilience when compared to a monolithic system. Raft is known for its ease of understanding and practical implementation, due to its utilization of strong leadership and division into three relatively independent sub-problems: log replication, leader election and safety. The combination of its simplicity, strong consistency, and fault tolerance guarantees in data replication has solidified Raft as one of the most popular algorithms since its creation a decade ago. It has been widely adopted in production by various systems, including Etcd, CockroachDB, MongoDB, and Neo4j. The leader in a Raft cluster has the active role of replicating its log entries on a process-by-process basis. In contrast, the other processes play a passive role, waiting for the leader’s requests and responding accordingly. This approach limits Raft in terms of scalability and performance: the larger number of processes in the system, the higher the leader’s replication workload, causing the leader to become the system bottleneck. Therefore, the overall performance of a Raft cluster is heavily dependent on the efficiency of the leader process. In terms of fault tolerance, a Raft cluster with 2f+1 processes can tolerate f processes to crash, requiring only a majority of correct processes to ensure availability. Furthermore, Raft allows for messages to be delayed or lost and can tolerate total network partitions. However, it assumes that messages are eventually delivered, as the leader needs to maintain constant communication with all processes to retain its leadership status. If a process does not receive any communication from the leader within a specified timeout period, it will assume that the leader failed and initiate an election. Therefore, Raft needs a transitive network to operate efficiently. If there are processes that do not receive messages from the leader, it increases the likelihood of elections being triggered constantly, leading to a loss of system performance. A consequence of such an occurrence was the outage experienced by Cloudflare on November 2, 2020, which lasted for six and a half hours [30]. In this thesis, we present Driftwood, a novel algorithm that expands Raft by incorporating gossip mechanisms to decentralize the leader replication effort. Gossip protocols allow a process to deliver a message to all processes, even in non-transitive networks, with a high probability. The Driftwood’s leader, instead of sending its log entries one-by-one, will initiate gossip rounds with a message containing uncommitted entries so that the processes propagate these entries among themselves and replicate the leader’s log. Furthermore, this message serves as the leader’s heartbeat when first received, avoiding unnecessary elections in non-transitive networks. However, the leader still has to receive replication confirmations from the processes in order to commit entries. So, we also propose new replicated data structures, shared in the gossip rounds, to discover new committed log entries. Driftwood is experimentally evaluated and compared with Raft. To this end, we implemented three algorithms in the Paxi framework: Raft, which serves as the baseline comparison, and two versions of Driftwood, one that uses the new replicated data structures while the other doesn’t. Through our evaluation, we determine the differences in performance, scalability, and distributed resource usage between Raft and Driftwood. We also analyse the behaviour of these algorithms in simulated non-transitive network scenarios.

O algoritmo de acordo Raft permite que múltiplas réplicas de uma máquina de estado se comportem como um único sistema robusto, capaz de tolerar diversas faltas, oferecendo mais resiliência comparado a um sistema monolítico. Raft é reconhecido pela sua facilidade de compreensão e implementação prática, devido ao uso de liderança forte e divisão em três sub-problemas relativamente independentes: replicação do registo, eleição do líder e segurança. A combinação de simplicidade, e garantias de coerência forte e tolerância a faltas na replicação de dados solidificou o Raft como um dos algoritmos mais populares desde a sua criação há uma década, sendo adotado em produção por diversos sistemas, incluindo Etcd, CockroachDB, MongoDB e Neo4j. O líder dum sistema de Raft tem o papel ativo de replicar as entradas do seu registo processo a pro cesso. Em contrapartida, os outros processos têm um papel passivo no sistema, esperando apenas pelos pedidos do líder e respondendo de acordo. Esta abordagem limita o Raft em termos de escalabilidade e desempenho. Com um maior número de processos no sistema, maior será a carga de trabalho de replicação para o líder, fazendo com que o líder se torne o gargalo do sistema. Assim, o desempenho dum sistema de Raft é dependente da eficiência do processo líder. Em termos de tolerância a faltas, um sistema de Raft com 2f+1 processos consegue tolerar f crashes de processos, necessitando apenas uma maioria de processos corretos para assegurar disponibilidade. Além disto, Raft permite perda ou atraso de entrega de mensagens e tolera partições totais de rede. Contudo, é assumido que mensagens são entregues inevitavelmente, uma vez que o líder tem que manter constante comunicação com todos os processos para manter a liderança. Se um processo não recebe nenhuma comunicação do líder até um tempo limite, este assume que o líder falhou e inicia uma eleição. Desta forma, Raft necessita de uma rede transitiva para operar eficientemente. Caso o líder não consiga comunicar com alguns processos, maior será a possibilidade que eleições aconteçam constantemente, resultando na perda de desempenho do sistema. Uma consequência desta ocorrência foi uma interrupção de serviços da Cloudfare a 2 de novembro de 2020 que durou seis horas e meia [30]. Nesta tese apresentamos Driftwood, um novo algoritmo que expande o Raft com a incorporação de mecanismos de propagação epidémica para descentralizar o esforço da replicação pelo líder. Protocolos de propagação epidémica permitem que um processo entregue uma mensagem a todos os processos, mesmo em redes não transitivas, com elevada probabilidade. O líder, no Driftwood, em vez de enviar as entradas do seu registo um-a-um, vai iniciar rondas de propagação epidémica com uma mensagem contendo entradas não confirmadas para que os processos propagarem estas entradas entre si e replicarem o registo do líder. Além disso, esta mensagem serve como heartbeat do líder quando recebida pela primeira vez, evitando eleições desnecessárias em redes não transitivas. Contudo, o líder continua a ter que receber as confirmações de replicação dos processos para descobrir que entradas estão confirmadas. Assim, propomos novas estruturas de dados partilhadas na propagação epidémica que permitirão aos processos descobrir as entradas do seu registo que são confirmadas. Driftwood é avaliado experimentalmente e comparado com Raft. Para tal, implementamos três algo ritmos na framework Paxi: Raft que serve de base e duas versões de Driftwood, que diferem no uso de novas estruturas de dados para avanço das entradas confirmadas. Através da nossa avaliação pretendemos determinar a diferença de desempenho, escalabilidade e no uso de recursos distribuídos entre Raft e Driftwood. Analisamos também o comportamento destes algoritmos em cenários de rede não transitiva simulada.