Computer Science › Software + Computação Distribuída
Todo lab nesta disciplina roda os seus sistemas replicados sobre uma rede simulada, não uma real, e este primeiro lab constrói esse simulador do zero: uma camada de RPC básica mais um transporte que pode ser mandado, sob comando, a atrasar uma mensagem, descartá-la silenciosamente, reordená-la, ou cortar um par específico de nós um do outro inteiramente, a mesma abordagem de simular-primeiro-depois-quebrá-lo que o próprio curso 6.5840 do MIT fornece pronto para os seus estudantes, construído aqui deliberadamente à mão em vez disso para que a sua mecânica de fato, não só a sua API, seja entendida antes de todo lab posterior nesta disciplina depender dele.
Este lab implementa o primeiro quarto do Raft, correspondendo ao próprio Lab 3A do MIT 6.5840 exatamente: RPCs RequestVote, timeouts de eleição aleatorizados, e a lógica baseada em termo que garante no máximo um líder por termo, rodada contra o simulador do Lab 1 com cenários de falha reais e repetíveis (um líder isolado, um líder morto, uma rede não confiável demais para eleger qualquer um) em vez de uma descrição só em diagrama de como a eleição deveria funcionar.
O timeout de eleição aleatorizado do Raft é uma resposta direta e prática a um problema específico de relógio físico que este lab torna concreto em vez de teórico: os relógios de máquina reais derivam uns em relação aos outros, então um timeout fixo e idêntico em todo nó deixaria dois seguidores darem timeout e começarem uma eleição no mesmo instante com frequência demais, dividindo votos e estagnando o progresso. Este lab instrumenta a implementação do Lab 3 para injetar deslize de relógio artificial e varrer a janela de aleatorização do timeout de eleição para baixo rumo a zero, medindo, empiricamente, o ponto em que eleições espúrias e desnecessárias começam a dominar e a estabilidade do líder colapsa, transformando os próprios requisitos de timing enunciados do artigo do Raft num número de fato medido, não só lido.
Este lab estende o líder eleito do lab anterior num log replicado real, implementando RPCs AppendEntries, a contabilidade de nextIndex por seguidor do líder, e a regra de maioria que avança o índice de commit, correspondendo ao Lab 3B do MIT 6.5840, e especificamente força o caminho de reparo de inconsistência de log que só a teoria raramente torna concreto: matar e reiniciar seguidores no meio do fluxo até o log de um seguidor ter genuinamente divergido do log do líder, depois verificar que a implementação de fato o traz de volta ao acordo em vez de só funcionar no caminho fácil, sem falha.
Um servidor Raft que perde o seu termo, voto e log no instante em que falha pode votar duas vezes no mesmo termo após reiniciar, violando silenciosamente a propriedade de segurança de um-voto-por-termo da qual todo este protocolo depende; este lab implementa a persistência de exatamente o estado que o próprio argumento de segurança do Raft exige que seja durável, e o seu teste real é um ciclo deliberado e repetido de matar todo servidor do cluster simultaneamente (uma falha de energia total, não só o crash de um nó) e confirmar que o sistema inteiro retoma corretamente a partir do disco, correspondendo ao Lab 3C do MIT 6.5840.
Um log Raft sempre crescente e nunca truncado é uma falha real e prática esperando para acontecer, não só uma ineficiência, já que um seguidor que fica suficientemente para trás eventualmente não consegue se atualizar reproduzindo um log grande demais para segurar em memória ou reproduzir em tempo razoável; este lab implementa snapshotting periódico e o RPC InstallSnapshot que deixa um seguidor muito atrasado saltar direto para um estado recente em vez disso, correspondendo ao Lab 3D do MIT 6.5840, testado privando deliberadamente um seguidor de AppendEntries por tempo suficiente para que só um snapshot, não a replicação de log comum, consiga trazê-lo em dia de novo.
Antes de a replicação sequer entrar em cena, este lab constrói um servidor chave-valor Put/Get/Append de nó único sobre o próprio transporte não confiável do Lab 1, e imediatamente confronta o problema concreto que esse transporte cria: um cliente cuja resposta de RPC foi perdida não consegue dizer se a sua requisição nunca chegou ou chegou e teve sucesso, então ele tenta de novo, e um servidor ingênuo executa essa escrita retentada duas vezes. Implementar detecção de duplicatas (um ID de cliente e de requisição carimbado em todo RPC, uma tabela do lado do servidor lembrando quais IDs já foram aplicados) é o que de fato transforma \"entrega at-least-once de uma rede não confiável\" na garantia de execução at-most-once na qual o código do cliente pode confiar com segurança.
Este lab é onde \"o banco replicado\" para o qual esta disciplina é nomeada de fato é construído: o serviço chave-valor Put/Get/Append do Lab 2 reconstruído sobre a implementação completa de Raft dos Labs 3-6, de modo que toda escrita passa por commit no log antes de ser aplicada e toda leitura reflete o último estado com commit, correspondendo ao Lab 4 do MIT 6.5840 por completo, incluindo a sua barra de correção de fato, a linearizabilidade verificada sob clientes concorrentes aleatorizados, crashes de servidor e partições tudo na mesma execução de teste, não meramente a correção sob o caso fácil de nenhuma concorrência e nenhuma falha.
Este capstone roda a store KV-sobre-Raft linearizável concluída do Lab 7 por um único cenário de caos combinado, uma partição de rede dividindo o cluster num lado majoritário e um minoritário, crashes e reinícios concorrentes sobre essa partição, um transporte não confiável que descarta pacotes por toda parte, e deslize de relógio injetado do Lab 8 tudo de uma vez, correspondendo às condições de teste reais e combinadas sob as quais os próprios testes mais difíceis do Lab 4 do MIT 6.5840 rodam, e exige escrever o que foi de fato observado: a partição minoritária corretamente estagna em vez de servir escritas obsoletas, exatamente a troca de disponibilidade-por-consistência que a teoria de CAP e PACELC de todo este currículo já previu, agora confirmada contra um sistema construído à mão em vez de aceito com base na fé.
Part of the Computer Science curriculum.
Todo lab nesta disciplina roda os seus sistemas replicados sobre uma rede simulada, não uma real, e este primeiro lab constrói esse simulador do zero: uma camada de RPC básica mais um transporte que pode ser mandado, sob comando, a atrasar uma mensagem, descartá-la silenciosamente, reordená-la, ou cortar um par específico de nós um do outro inteiramente, a mesma abordagem de simular-primeiro-depois-quebrá-lo que o próprio curso 6.5840 do MIT fornece pronto para os seus estudantes, construído aqui deliberadamente à mão em vez disso para que a sua mecânica de fato, não só a sua API, seja entendida antes de todo lab posterior nesta disciplina depender dele.
Este lab implementa o primeiro quarto do Raft, correspondendo ao próprio Lab 3A do MIT 6.5840 exatamente: RPCs RequestVote, timeouts de eleição aleatorizados, e a lógica baseada em termo que garante no máximo um líder por termo, rodada contra o simulador do Lab 1 com cenários de falha reais e repetíveis (um líder isolado, um líder morto, uma rede não confiável demais para eleger qualquer um) em vez de uma descrição só em diagrama de como a eleição deveria funcionar.
O timeout de eleição aleatorizado do Raft é uma resposta direta e prática a um problema específico de relógio físico que este lab torna concreto em vez de teórico: os relógios de máquina reais derivam uns em relação aos outros, então um timeout fixo e idêntico em todo nó deixaria dois seguidores darem timeout e começarem uma eleição no mesmo instante com frequência demais, dividindo votos e estagnando o progresso. Este lab instrumenta a implementação do Lab 3 para injetar deslize de relógio artificial e varrer a janela de aleatorização do timeout de eleição para baixo rumo a zero, medindo, empiricamente, o ponto em que eleições espúrias e desnecessárias começam a dominar e a estabilidade do líder colapsa, transformando os próprios requisitos de timing enunciados do artigo do Raft num número de fato medido, não só lido.
Este lab estende o líder eleito do lab anterior num log replicado real, implementando RPCs AppendEntries, a contabilidade de nextIndex por seguidor do líder, e a regra de maioria que avança o índice de commit, correspondendo ao Lab 3B do MIT 6.5840, e especificamente força o caminho de reparo de inconsistência de log que só a teoria raramente torna concreto: matar e reiniciar seguidores no meio do fluxo até o log de um seguidor ter genuinamente divergido do log do líder, depois verificar que a implementação de fato o traz de volta ao acordo em vez de só funcionar no caminho fácil, sem falha.
Um servidor Raft que perde o seu termo, voto e log no instante em que falha pode votar duas vezes no mesmo termo após reiniciar, violando silenciosamente a propriedade de segurança de um-voto-por-termo da qual todo este protocolo depende; este lab implementa a persistência de exatamente o estado que o próprio argumento de segurança do Raft exige que seja durável, e o seu teste real é um ciclo deliberado e repetido de matar todo servidor do cluster simultaneamente (uma falha de energia total, não só o crash de um nó) e confirmar que o sistema inteiro retoma corretamente a partir do disco, correspondendo ao Lab 3C do MIT 6.5840.
Um log Raft sempre crescente e nunca truncado é uma falha real e prática esperando para acontecer, não só uma ineficiência, já que um seguidor que fica suficientemente para trás eventualmente não consegue se atualizar reproduzindo um log grande demais para segurar em memória ou reproduzir em tempo razoável; este lab implementa snapshotting periódico e o RPC InstallSnapshot que deixa um seguidor muito atrasado saltar direto para um estado recente em vez disso, correspondendo ao Lab 3D do MIT 6.5840, testado privando deliberadamente um seguidor de AppendEntries por tempo suficiente para que só um snapshot, não a replicação de log comum, consiga trazê-lo em dia de novo.
Antes de a replicação sequer entrar em cena, este lab constrói um servidor chave-valor Put/Get/Append de nó único sobre o próprio transporte não confiável do Lab 1, e imediatamente confronta o problema concreto que esse transporte cria: um cliente cuja resposta de RPC foi perdida não consegue dizer se a sua requisição nunca chegou ou chegou e teve sucesso, então ele tenta de novo, e um servidor ingênuo executa essa escrita retentada duas vezes. Implementar detecção de duplicatas (um ID de cliente e de requisição carimbado em todo RPC, uma tabela do lado do servidor lembrando quais IDs já foram aplicados) é o que de fato transforma \"entrega at-least-once de uma rede não confiável\" na garantia de execução at-most-once na qual o código do cliente pode confiar com segurança.
Este lab é onde \"o banco replicado\" para o qual esta disciplina é nomeada de fato é construído: o serviço chave-valor Put/Get/Append do Lab 2 reconstruído sobre a implementação completa de Raft dos Labs 3-6, de modo que toda escrita passa por commit no log antes de ser aplicada e toda leitura reflete o último estado com commit, correspondendo ao Lab 4 do MIT 6.5840 por completo, incluindo a sua barra de correção de fato, a linearizabilidade verificada sob clientes concorrentes aleatorizados, crashes de servidor e partições tudo na mesma execução de teste, não meramente a correção sob o caso fácil de nenhuma concorrência e nenhuma falha.
Este capstone roda a store KV-sobre-Raft linearizável concluída do Lab 7 por um único cenário de caos combinado, uma partição de rede dividindo o cluster num lado majoritário e um minoritário, crashes e reinícios concorrentes sobre essa partição, um transporte não confiável que descarta pacotes por toda parte, e deslize de relógio injetado do Lab 8 tudo de uma vez, correspondendo às condições de teste reais e combinadas sob as quais os próprios testes mais difíceis do Lab 4 do MIT 6.5840 rodam, e exige escrever o que foi de fato observado: a partição minoritária corretamente estagna em vez de servir escritas obsoletas, exatamente a troca de disponibilidade-por-consistência que a teoria de CAP e PACELC de todo este currículo já previu, agora confirmada contra um sistema construído à mão em vez de aceito com base na fé.