Computer Science › Sistemas
Uma única máquina que cai, cai inteira e para; um sistema distribuído pode ter algumas máquinas funcionando bem enquanto outras falharam, e as sobreviventes geralmente não conseguem distinguir “aquela máquina está morta” de “aquela máquina (ou a rede até ela) está só lenta”. Este conceito nomeia a falha parcial, a ausência de memória compartilhada e a ausência de um relógio compartilhado como as três propriedades que tornam os sistemas distribuídos um problema genuinamente diferente e mais difícil do que a programação concorrente numa máquina, e não apenas programação concorrente com latência extra.
O RPC faz uma chamada a outra máquina parecer sintaticamente uma chamada de função comum, mas o projeto original de Birrell & Nelson já precisou enfrentar tudo o que a distingue de uma: os argumentos precisam ser serializados em bytes e enviados por um socket, o chamado pode não existir ou cair no meio da chamada, e a rede entre chamador e chamado pode descartar, atrasar ou reordenar mensagens de formas que uma chamada local nunca pode. A abstração é genuinamente útil, mas só depois que as suas rachaduras são entendidas.
Quando um chamador de RPC atinge o timeout esperando uma resposta, ele enfrenta uma situação genuinamente ambígua (a requisição pode nunca ter chegado, o servidor pode tê-la executado e a resposta ter se perdido, ou o servidor pode ainda estar executando-a), e este conceito percorre os três contratos precisos e comumente confundidos que um sistema pode oferecer em resposta (at-least-once via reenvio cego, at-most-once via deduplicação e o muito mais difícil exactly-once), mostrando por que a própria entrega confiável de fluxo de bytes do TCP, uma camada abaixo, resolve um problema relacionado mas diferente e não dá, por si só, semântica exactly-once de graça a uma biblioteca de RPC.
O relógio local de toda máquina é um oscilador físico que deriva na sua própria taxa ligeiramente diferente, então os relógios de duas máquinas discordam cada vez mais quanto mais tempo ficam sem sincronização. Este conceito trabalha por que sincronizar relógios físicos por uma rede é fundamentalmente limitado pelo atraso de mensagens incerto e assimétrico (dá para medir o tempo de ida e volta, mas não como esse tempo se divide entre a perna de ida e a de volta), que é exatamente o problema prático que o artigo de Lamport de 1978 trata na sua segunda metade, e exatamente por que um sistema distribuído que precisa ordenar eventos de forma confiável não pode simplesmente carimbá-los com o horário de relógio e confiar na ordem.
O artigo de Lamport de 1978 contorna os relógios físicos inteiramente: ele define “happens-before” (→) diretamente a partir do que um sistema distribuído consegue de fato observar (a ordem do programa dentro de um processo, e o envio de uma mensagem sempre acontecendo antes do recebimento correspondente), produzindo exatamente uma ordem parcial (irreflexiva e transitiva, mas não total: dois eventos em processos diferentes sem nenhuma cadeia de mensagens entre eles são simplesmente incomparáveis, ou seja, concorrentes). Em seguida, ele dá um algoritmo simples de contador inteiro que satisfaz a Condição do Relógio (a→b implica C(a)<C(b)) e mostra como desempatar com IDs de processo estende essa ordem parcial numa ordem total sempre que uma é necessária.
A definição de Herlihy & Wing de 1990 é precisa onde a intuição popular (“parece que só existe uma cópia dos dados”) é vaga: um histórico concorrente é linearizável se a cada operação puder ser atribuído um único ponto no tempo real, estritamente entre a sua invocação e a sua resposta, de modo que os valores de retorno das operações batam com o que uma execução sequencial legal nesses pontos produziria. A exigência de que o ponto caia dentro do intervalo real, de relógio, entre invocação e resposta (e não apenas “alguma ordem consistente”) é exatamente o que torna a linearizabilidade o modelo de consistência comum mais forte, e exatamente aquilo de que o modelo mais fraco do próximo conceito abre mão.
A consistência sequencial mantém a parte da linearizabilidade que preserva a própria ordem de programa de cada processo e exige que todos os processos concordem com uma única intercalação global de todas as operações, mas descarta inteiramente a restrição de tempo real: uma intercalação é legal mesmo que reordene duas operações não sobrepostas de processos diferentes na ordem de tempo real “errada”, desde que as operações de cada processo fiquem na sua própria ordem de programa. Isso faz todo histórico linearizável ser também sequencialmente consistente, mas não o contrário, com um contraexemplo concreto trabalhado à mão para mostrar exatamente onde os dois modelos divergem.
A consistência eventual faz uma promessa muito mais fraca, puramente no estilo de vivacidade: se nenhuma escrita nova chegar, todas as réplicas vão eventualmente convergir para o mesmo valor, sem limite para quanto tempo “eventualmente” leva e sem garantia sobre o que qualquer leitura isolada retorna nesse meio-tempo, que é exatamente a troca que sistemas reais fazem deliberadamente em favor da disponibilidade durante partições de rede. Os protocolos de gossip / anti-entropy que espalham atualizações entre réplicas para alcançar essa convergência eventual são um paralelo estrutural genuíno (e não uma metáfora) da propagação com informação local e convergência eventual do próprio roteamento por vetor de distâncias, incluindo um risco análogo de informação temporariamente desatualizada ou contraditória no meio da convergência.
A prova de Gilbert & Lynch de 2002 dá à conjectura de Brewer um enunciado preciso e uma prova real por contradição: suponha que um sistema fornece Consistência linearizável e Disponibilidade total, depois construa uma partição de rede e mostre que dois nós em lados opostos precisam ou discordar (violando a Consistência) ou se recusar a responder (violando a Disponibilidade). Este conceito também traz a nuance da retrospectiva do próprio Brewer de 2012 de que a tolerância a partições não é uma terceira opção simétrica ao lado de C e A: redes reais de fato se particionam, então a única escolha genuína, momento a momento, que um sistema faz é entre C e A durante uma partição real, com o slogan popular “escolha dois dos três” sinalizado explicitamente como a simplificação excessiva que ele é.
O tutorial de Schneider de 1990 nomeia a arquitetura que todo protocolo do restante desta disciplina implementa: se toda réplica começa no mesmo estado, é determinística e aplica exatamente a mesma sequência de comandos, então toda réplica termina exatamente no mesmo estado. Isso reduz “manter as réplicas consistentes apesar de falhas” a exatamente duas propriedades, Acordo (toda réplica aplica o mesmo conjunto de comandos) e Ordem (toda réplica os aplica na mesma sequência), a segunda das quais é precisamente o problema do consenso ao qual esta disciplina chega a seguir.
A replicação primário-backup designa uma réplica como o primário, que ordena toda escrita e a encaminha aos backups: simples e barata, mas o sistema inteiro trava (ou precisa de um mecanismo separado, e igualmente difícil, de detecção de falhas e promoção) no momento em que o primário fica inalcançável. A replicação baseada em quórum, em vez disso, exige que apenas uma maioria (ou, num esquema de registrador R+W>N, um quórum de leitura/escrita sobreposto) de algum conjunto de réplicas participe de cada operação, tolerando falhas de nós individuais sem que um único líder designado trave tudo, ao custo real de precisar de um protocolo de acordo por maioria de fato (exatamente o que o Paxos e o Raft, a seguir, fornecem) em vez da palavra de um único primário. Quando esse conjunto de réplicas é escolhido dinamicamente em escala, ele é tipicamente o mesmo conjunto de N nós que um anel de hashing consistente já atribui a uma dada chave.
Fischer, Lynch & Paterson dão ao consenso a sua forma formal antes de provar qualquer coisa difícil sobre ele: todo processo não defeituoso propõe um valor, e um protocolo correto precisa garantir Acordo (nenhum par de processos não defeituosos decide de forma diferente), Validade (o valor decidido foi de fato proposto por alguém, descartando um protocolo trivial de sempre decidir 0) e Terminação (todo processo não defeituoso eventualmente decide). Serviços de coordenação reais como ZooKeeper e etcd existem justamente porque as aplicações precisam exatamente desta garantia (acordo sobre um líder, um detentor de lock ou um valor de configuração) como um bloco de construção reutilizável, em vez de resolvê-la de novo por conta própria.
O teorema FLP de 1985 é um limite real e honesto, e não uma popularização: num sistema completamente assíncrono (sem limite algum para o atraso de mensagens ou para a velocidade relativa de processamento) em que até um único processo pode cair, nenhum protocolo determinístico consegue garantir as três propriedades de Acordo, Validade e Terminação. A prova não é por contradição simples, mas por um argumento de adversário mais sutil, mostrando que a partir de qualquer configuração inicial “bivalente” (uma em que tanto 0 quanto 1 ainda poderiam ser decididos) um adversário que controla o agendamento das mensagens sempre consegue encontrar algum próximo passo que mantém o sistema bivalente para sempre, então a terminação sempre pode ser adiada. Todo protocolo de consenso real (Paxos e Raft incluídos) sobrevive a este resultado apenas abrindo mão da assincronia estrita na prática, via timeouts e randomização que tornam a terminação meramente provável, e não refutando o teorema.
O Paxos, a solução original de Lamport para o consenso de 1989 (publicada como “The Part-Time Parliament” em 1998, e depois reexplicada no muito mais legível “Paxos Made Simple” em 2001), atribui três papéis (proponentes, aceitadores e aprendizes) e roda duas fases por tentativa (Prepare/Promise, depois Accept/Accepted), construídas inteiramente sobre o fato de que quaisquer duas maiorias de aceitadores precisam se sobrepor em pelo menos um membro. Essa sobreposição é exatamente o que prova a propriedade de segurança central do Paxos, de que, uma vez escolhido qualquer valor, nenhum valor diferente pode jamais ser escolhido depois. Este conceito cobre o Paxos exatamente neste nível (papéis reais, fases reais, o argumento de segurança real pelo nome) sem rederivar cada detalhe de vivacidade e reconfiguração, deixando o tratamento trabalhado mais completo para o Raft, que os próximos três conceitos constroem do zero justamente porque o próprio algoritmo de Lamport era, por amplo consenso, incluindo o título do seu próprio artigo, incomumente difícil de ensinar.
O Raft decompõe o consenso em eleição de líder, replicação de log e segurança especificamente para ser mais compreensível que o Paxos, começando aqui pela eleição: o tempo é dividido em termos (inteiros monotonicamente crescentes, no máximo um líder por termo), cada servidor é um Seguidor, Candidato ou Líder, e um Seguidor que não ouve nenhum heartbeat antes que o seu timeout de eleição randomizado expire se torna um Candidato, incrementa o seu termo e envia RPCs RequestVote a todo outro servidor. A randomização é o mecanismo de fato que torna os votos divididos (dois candidatos dando timeout simultaneamente) raros, e não impossíveis, e um candidato só se torna líder ao coletar votos de uma maioria do cluster completo, a mesma propriedade de sobreposição de maiorias na qual o Paxos se apoia.
Uma vez eleito, um líder Raft é o único servidor que aceita requisições de clientes: ele anexa cada novo comando ao seu próprio log como uma entrada não confirmada, depois a replica para os seguidores via RPCs AppendEntries (que também servem de heartbeats), e só avança o seu índice de commit (marcando aquela entrada, e por construção toda entrada anterior a ela, como confirmada com segurança) quando uma maioria do cluster (líder incluído) a armazenou. A Propriedade de Correspondência de Logs (Log Matching Property), segundo a qual dois logs que concordam sobre o termo de uma entrada num dado índice têm garantia de serem idênticos em toda entrada até aquele índice, inclusive, é o que permite à checagem de consistência do AppendEntries (comparando apenas um par índice/termo anterior) substituir a comparação do histórico inteiro do log.
Todo o argumento de segurança do Raft depende de uma restrição imposta durante a votação: o RequestVote é recusado a menos que o log do candidato seja pelo menos tão atualizado quanto o do próprio eleitor (comparado pelo termo da última entrada, depois pelo tamanho). Isso força o log de todo líder futuro a já conter toda entrada que qualquer líder passado já confirmou, a Propriedade de Completude do Líder. O artigo prova isso por contradição: suponha que algum líder com o maior termo confirmado NÃO tem uma entrada já confirmada, note que o líder que originalmente confirmou essa entrada precisou que uma maioria a tivesse, note que o novo líder também precisou de uma maioria de eleitores e, como quaisquer duas maiorias se sobrepõem, algum servidor isolado precisa ter tanto votado no novo líder QUANTO já armazenado a entrada confirmada. Mas a restrição de eleição então teria recusado esse voto a menos que o log do novo líder já estivesse pelo menos tão atualizado, uma contradição direta.
Todo protocolo que esta disciplina cobriu (FLP, Paxos, Raft) assume o modelo de falha por queda (fail-stop): um processo defeituoso simplesmente para, e nunca envia uma mensagem corrompida, contraditória ou ativamente enganosa; o modelo de falha bizantina é estritamente mais difícil e assume exatamente o oposto, que um processo defeituoso pode se comportar arbitrariamente, incluindo mentir de forma diferente a diferentes pares, que é precisamente por que os argumentos simples de voto por maioria e sobreposição de quórum do Raft não se transferem sem modificação e os protocolos reais tolerantes a falhas bizantinas precisam de um quórum maior e de um argumento de segurança diferente, nomeado honestamente aqui como um problema real e distinto que esta disciplina não re-deriva, já que o tratamento aplicado em nível de protocolo (o Problema dos Generais Bizantinos, PBFT) já existe em `system-design-concepts`.
Este capstone rastreia uma escrita de cliente concreta de ponta a ponta através de um cluster Raft de 3 nós: um RPC chega ao líder atual, o líder o anexa ao seu log como não confirmado, AppendEntries o replica para ambos os seguidores, o líder avança seu índice de commit no instante em que uma maioria (ele próprio mais um seguidor) o armazenou, a entrada é aplicada à máquina de estados replicada, e só então o cliente recebe sua resposta, nomeando o conceito exato responsável por cada passo, rastreando o que muda quando um seguidor está lento, quando o líder cai no meio da replicação, e encerrando com um relato honesto de onde o rigor desta disciplina termina e os serviços de coordenação aplicados e em escala de produção (ZooKeeper, etcd) construídos sobre exatamente este mecanismo começam.
Part of the Computer Science curriculum.
Uma única máquina que cai, cai inteira e para; um sistema distribuído pode ter algumas máquinas funcionando bem enquanto outras falharam, e as sobreviventes geralmente não conseguem distinguir “aquela máquina está morta” de “aquela máquina (ou a rede até ela) está só lenta”. Este conceito nomeia a falha parcial, a ausência de memória compartilhada e a ausência de um relógio compartilhado como as três propriedades que tornam os sistemas distribuídos um problema genuinamente diferente e mais difícil do que a programação concorrente numa máquina, e não apenas programação concorrente com latência extra.
O RPC faz uma chamada a outra máquina parecer sintaticamente uma chamada de função comum, mas o projeto original de Birrell & Nelson já precisou enfrentar tudo o que a distingue de uma: os argumentos precisam ser serializados em bytes e enviados por um socket, o chamado pode não existir ou cair no meio da chamada, e a rede entre chamador e chamado pode descartar, atrasar ou reordenar mensagens de formas que uma chamada local nunca pode. A abstração é genuinamente útil, mas só depois que as suas rachaduras são entendidas.
Quando um chamador de RPC atinge o timeout esperando uma resposta, ele enfrenta uma situação genuinamente ambígua (a requisição pode nunca ter chegado, o servidor pode tê-la executado e a resposta ter se perdido, ou o servidor pode ainda estar executando-a), e este conceito percorre os três contratos precisos e comumente confundidos que um sistema pode oferecer em resposta (at-least-once via reenvio cego, at-most-once via deduplicação e o muito mais difícil exactly-once), mostrando por que a própria entrega confiável de fluxo de bytes do TCP, uma camada abaixo, resolve um problema relacionado mas diferente e não dá, por si só, semântica exactly-once de graça a uma biblioteca de RPC.
O relógio local de toda máquina é um oscilador físico que deriva na sua própria taxa ligeiramente diferente, então os relógios de duas máquinas discordam cada vez mais quanto mais tempo ficam sem sincronização. Este conceito trabalha por que sincronizar relógios físicos por uma rede é fundamentalmente limitado pelo atraso de mensagens incerto e assimétrico (dá para medir o tempo de ida e volta, mas não como esse tempo se divide entre a perna de ida e a de volta), que é exatamente o problema prático que o artigo de Lamport de 1978 trata na sua segunda metade, e exatamente por que um sistema distribuído que precisa ordenar eventos de forma confiável não pode simplesmente carimbá-los com o horário de relógio e confiar na ordem.
O artigo de Lamport de 1978 contorna os relógios físicos inteiramente: ele define “happens-before” (→) diretamente a partir do que um sistema distribuído consegue de fato observar (a ordem do programa dentro de um processo, e o envio de uma mensagem sempre acontecendo antes do recebimento correspondente), produzindo exatamente uma ordem parcial (irreflexiva e transitiva, mas não total: dois eventos em processos diferentes sem nenhuma cadeia de mensagens entre eles são simplesmente incomparáveis, ou seja, concorrentes). Em seguida, ele dá um algoritmo simples de contador inteiro que satisfaz a Condição do Relógio (a→b implica C(a)<C(b)) e mostra como desempatar com IDs de processo estende essa ordem parcial numa ordem total sempre que uma é necessária.
A definição de Herlihy & Wing de 1990 é precisa onde a intuição popular (“parece que só existe uma cópia dos dados”) é vaga: um histórico concorrente é linearizável se a cada operação puder ser atribuído um único ponto no tempo real, estritamente entre a sua invocação e a sua resposta, de modo que os valores de retorno das operações batam com o que uma execução sequencial legal nesses pontos produziria. A exigência de que o ponto caia dentro do intervalo real, de relógio, entre invocação e resposta (e não apenas “alguma ordem consistente”) é exatamente o que torna a linearizabilidade o modelo de consistência comum mais forte, e exatamente aquilo de que o modelo mais fraco do próximo conceito abre mão.
A consistência sequencial mantém a parte da linearizabilidade que preserva a própria ordem de programa de cada processo e exige que todos os processos concordem com uma única intercalação global de todas as operações, mas descarta inteiramente a restrição de tempo real: uma intercalação é legal mesmo que reordene duas operações não sobrepostas de processos diferentes na ordem de tempo real “errada”, desde que as operações de cada processo fiquem na sua própria ordem de programa. Isso faz todo histórico linearizável ser também sequencialmente consistente, mas não o contrário, com um contraexemplo concreto trabalhado à mão para mostrar exatamente onde os dois modelos divergem.
A consistência eventual faz uma promessa muito mais fraca, puramente no estilo de vivacidade: se nenhuma escrita nova chegar, todas as réplicas vão eventualmente convergir para o mesmo valor, sem limite para quanto tempo “eventualmente” leva e sem garantia sobre o que qualquer leitura isolada retorna nesse meio-tempo, que é exatamente a troca que sistemas reais fazem deliberadamente em favor da disponibilidade durante partições de rede. Os protocolos de gossip / anti-entropy que espalham atualizações entre réplicas para alcançar essa convergência eventual são um paralelo estrutural genuíno (e não uma metáfora) da propagação com informação local e convergência eventual do próprio roteamento por vetor de distâncias, incluindo um risco análogo de informação temporariamente desatualizada ou contraditória no meio da convergência.
A prova de Gilbert & Lynch de 2002 dá à conjectura de Brewer um enunciado preciso e uma prova real por contradição: suponha que um sistema fornece Consistência linearizável e Disponibilidade total, depois construa uma partição de rede e mostre que dois nós em lados opostos precisam ou discordar (violando a Consistência) ou se recusar a responder (violando a Disponibilidade). Este conceito também traz a nuance da retrospectiva do próprio Brewer de 2012 de que a tolerância a partições não é uma terceira opção simétrica ao lado de C e A: redes reais de fato se particionam, então a única escolha genuína, momento a momento, que um sistema faz é entre C e A durante uma partição real, com o slogan popular “escolha dois dos três” sinalizado explicitamente como a simplificação excessiva que ele é.
O tutorial de Schneider de 1990 nomeia a arquitetura que todo protocolo do restante desta disciplina implementa: se toda réplica começa no mesmo estado, é determinística e aplica exatamente a mesma sequência de comandos, então toda réplica termina exatamente no mesmo estado. Isso reduz “manter as réplicas consistentes apesar de falhas” a exatamente duas propriedades, Acordo (toda réplica aplica o mesmo conjunto de comandos) e Ordem (toda réplica os aplica na mesma sequência), a segunda das quais é precisamente o problema do consenso ao qual esta disciplina chega a seguir.
A replicação primário-backup designa uma réplica como o primário, que ordena toda escrita e a encaminha aos backups: simples e barata, mas o sistema inteiro trava (ou precisa de um mecanismo separado, e igualmente difícil, de detecção de falhas e promoção) no momento em que o primário fica inalcançável. A replicação baseada em quórum, em vez disso, exige que apenas uma maioria (ou, num esquema de registrador R+W>N, um quórum de leitura/escrita sobreposto) de algum conjunto de réplicas participe de cada operação, tolerando falhas de nós individuais sem que um único líder designado trave tudo, ao custo real de precisar de um protocolo de acordo por maioria de fato (exatamente o que o Paxos e o Raft, a seguir, fornecem) em vez da palavra de um único primário. Quando esse conjunto de réplicas é escolhido dinamicamente em escala, ele é tipicamente o mesmo conjunto de N nós que um anel de hashing consistente já atribui a uma dada chave.
Fischer, Lynch & Paterson dão ao consenso a sua forma formal antes de provar qualquer coisa difícil sobre ele: todo processo não defeituoso propõe um valor, e um protocolo correto precisa garantir Acordo (nenhum par de processos não defeituosos decide de forma diferente), Validade (o valor decidido foi de fato proposto por alguém, descartando um protocolo trivial de sempre decidir 0) e Terminação (todo processo não defeituoso eventualmente decide). Serviços de coordenação reais como ZooKeeper e etcd existem justamente porque as aplicações precisam exatamente desta garantia (acordo sobre um líder, um detentor de lock ou um valor de configuração) como um bloco de construção reutilizável, em vez de resolvê-la de novo por conta própria.
O teorema FLP de 1985 é um limite real e honesto, e não uma popularização: num sistema completamente assíncrono (sem limite algum para o atraso de mensagens ou para a velocidade relativa de processamento) em que até um único processo pode cair, nenhum protocolo determinístico consegue garantir as três propriedades de Acordo, Validade e Terminação. A prova não é por contradição simples, mas por um argumento de adversário mais sutil, mostrando que a partir de qualquer configuração inicial “bivalente” (uma em que tanto 0 quanto 1 ainda poderiam ser decididos) um adversário que controla o agendamento das mensagens sempre consegue encontrar algum próximo passo que mantém o sistema bivalente para sempre, então a terminação sempre pode ser adiada. Todo protocolo de consenso real (Paxos e Raft incluídos) sobrevive a este resultado apenas abrindo mão da assincronia estrita na prática, via timeouts e randomização que tornam a terminação meramente provável, e não refutando o teorema.
O Paxos, a solução original de Lamport para o consenso de 1989 (publicada como “The Part-Time Parliament” em 1998, e depois reexplicada no muito mais legível “Paxos Made Simple” em 2001), atribui três papéis (proponentes, aceitadores e aprendizes) e roda duas fases por tentativa (Prepare/Promise, depois Accept/Accepted), construídas inteiramente sobre o fato de que quaisquer duas maiorias de aceitadores precisam se sobrepor em pelo menos um membro. Essa sobreposição é exatamente o que prova a propriedade de segurança central do Paxos, de que, uma vez escolhido qualquer valor, nenhum valor diferente pode jamais ser escolhido depois. Este conceito cobre o Paxos exatamente neste nível (papéis reais, fases reais, o argumento de segurança real pelo nome) sem rederivar cada detalhe de vivacidade e reconfiguração, deixando o tratamento trabalhado mais completo para o Raft, que os próximos três conceitos constroem do zero justamente porque o próprio algoritmo de Lamport era, por amplo consenso, incluindo o título do seu próprio artigo, incomumente difícil de ensinar.
O Raft decompõe o consenso em eleição de líder, replicação de log e segurança especificamente para ser mais compreensível que o Paxos, começando aqui pela eleição: o tempo é dividido em termos (inteiros monotonicamente crescentes, no máximo um líder por termo), cada servidor é um Seguidor, Candidato ou Líder, e um Seguidor que não ouve nenhum heartbeat antes que o seu timeout de eleição randomizado expire se torna um Candidato, incrementa o seu termo e envia RPCs RequestVote a todo outro servidor. A randomização é o mecanismo de fato que torna os votos divididos (dois candidatos dando timeout simultaneamente) raros, e não impossíveis, e um candidato só se torna líder ao coletar votos de uma maioria do cluster completo, a mesma propriedade de sobreposição de maiorias na qual o Paxos se apoia.
Uma vez eleito, um líder Raft é o único servidor que aceita requisições de clientes: ele anexa cada novo comando ao seu próprio log como uma entrada não confirmada, depois a replica para os seguidores via RPCs AppendEntries (que também servem de heartbeats), e só avança o seu índice de commit (marcando aquela entrada, e por construção toda entrada anterior a ela, como confirmada com segurança) quando uma maioria do cluster (líder incluído) a armazenou. A Propriedade de Correspondência de Logs (Log Matching Property), segundo a qual dois logs que concordam sobre o termo de uma entrada num dado índice têm garantia de serem idênticos em toda entrada até aquele índice, inclusive, é o que permite à checagem de consistência do AppendEntries (comparando apenas um par índice/termo anterior) substituir a comparação do histórico inteiro do log.
Todo o argumento de segurança do Raft depende de uma restrição imposta durante a votação: o RequestVote é recusado a menos que o log do candidato seja pelo menos tão atualizado quanto o do próprio eleitor (comparado pelo termo da última entrada, depois pelo tamanho). Isso força o log de todo líder futuro a já conter toda entrada que qualquer líder passado já confirmou, a Propriedade de Completude do Líder. O artigo prova isso por contradição: suponha que algum líder com o maior termo confirmado NÃO tem uma entrada já confirmada, note que o líder que originalmente confirmou essa entrada precisou que uma maioria a tivesse, note que o novo líder também precisou de uma maioria de eleitores e, como quaisquer duas maiorias se sobrepõem, algum servidor isolado precisa ter tanto votado no novo líder QUANTO já armazenado a entrada confirmada. Mas a restrição de eleição então teria recusado esse voto a menos que o log do novo líder já estivesse pelo menos tão atualizado, uma contradição direta.
Todo protocolo que esta disciplina cobriu (FLP, Paxos, Raft) assume o modelo de falha por queda (fail-stop): um processo defeituoso simplesmente para, e nunca envia uma mensagem corrompida, contraditória ou ativamente enganosa; o modelo de falha bizantina é estritamente mais difícil e assume exatamente o oposto, que um processo defeituoso pode se comportar arbitrariamente, incluindo mentir de forma diferente a diferentes pares, que é precisamente por que os argumentos simples de voto por maioria e sobreposição de quórum do Raft não se transferem sem modificação e os protocolos reais tolerantes a falhas bizantinas precisam de um quórum maior e de um argumento de segurança diferente, nomeado honestamente aqui como um problema real e distinto que esta disciplina não re-deriva, já que o tratamento aplicado em nível de protocolo (o Problema dos Generais Bizantinos, PBFT) já existe em `system-design-concepts`.
Este capstone rastreia uma escrita de cliente concreta de ponta a ponta através de um cluster Raft de 3 nós: um RPC chega ao líder atual, o líder o anexa ao seu log como não confirmado, AppendEntries o replica para ambos os seguidores, o líder avança seu índice de commit no instante em que uma maioria (ele próprio mais um seguidor) o armazenou, a entrada é aplicada à máquina de estados replicada, e só então o cliente recebe sua resposta, nomeando o conceito exato responsável por cada passo, rastreando o que muda quando um seguidor está lento, quando o líder cai no meio da replicação, e encerrando com um relato honesto de onde o rigor desta disciplina termina e os serviços de coordenação aplicados e em escala de produção (ZooKeeper, etcd) construídos sobre exatamente este mecanismo começam.