Computer Science › Especialização
A teoria de consenso, replicação e consistência de Sistemas Distribuídos I é necessária, mas não suficiente: sistemas reais que atendem bilhões de requisições por dia são construídos combinando essas primitivas em projetos específicos e opinativos, cada um trocando corretude, disponibilidade e desempenho de um jeito diferente para uma carga de trabalho específica.
Uma plataforma de function-as-a-service roda um handler sem estado sob demanda, escalando de zero a milhares de invocações concorrentes e cobrando por invocação: um avanço genuíno para o autoescalonamento, mas que uma crítica no nível de sistemas mostra ser decepcionantemente sem estado e pobre em E/S exatamente onde os estudos de caso desta disciplina (jobs de dados paralelos, armazenamento distribuído) mais precisam de estado e de rede rápida.
Mapear tanto os nós quanto as chaves no mesmo anel de hash, e atribuir cada chave ao próximo nó no sentido horário, significa que adicionar ou remover um nó só redistribui as chaves adjacentes a ele no anel, e não o espaço de chaves inteiro: o truque habilitador por trás de todo armazenamento particionado que precisa aumentar ou diminuir o número de nós sem uma redistribuição completa dos dados.
Um cache que é trivial em pequena escala (consultar uma chave, recorrer ao banco de dados num miss) quebra de várias formas específicas e reais a bilhões de requisições por segundo: manadas estrondosas num miss popular, leituras desatualizadas correndo com uma escrita no banco, e atraso de replicação entre regiões. Cada uma é tratada por um mecanismo distinto e deliberado (leases, um daemon de invalidação que lê o log de commits do banco, e pools regionais), e não por uma correção genérica.
O Dynamo substitui um quórum estrito (que bloqueia escritas sempre que uma réplica designada está fora do ar) por um quórum relaxado (sloppy quorum): uma escrita vai para os primeiros N nós saudáveis ao percorrer o anel, mesmo que isso signifique um substituto temporário, com uma dica, para um nó indisponível, escolhendo a disponibilidade das escritas em vez de sempre acertar o conjunto de réplicas teoricamente correto.
Como os quóruns relaxados permitem que dois clientes escrevam a mesma chave sem que nenhum veja a escrita do outro, o Dynamo marca todo valor com um relógio vetorial e devolve as versões genuinamente concorrentes à aplicação para reconciliação, sendo semanticamente honesto sobre a consistência eventual que está escolhendo, em vez de esconder o conflito e escolher uma versão arbitrariamente.
Um único master que guarda só metadados, muitos chunkservers que guardam chunks de 64MB replicados três vezes, e um projeto que otimiza deliberadamente para leituras sequenciais enormes e escritas só de anexação, em vez dos arquivos pequenos de acesso aleatório para os quais um sistema de arquivos de uma única máquina é construído.
Um mapa esparso, distribuído e ordenado, chaveado por (linha, família de colunas:qualificador, timestamp), dividido em tablets por faixa de linhas e persistido como SSTables imutáveis e ordenadas no GFS, um layout de armazenamento inteiramente diferente de um motor relacional indexado por B+Tree, otimizado para tabelas extremamente largas e esparsas e para escritas sequenciais de alta vazão.
O Bigtable não resolve a coordenação distribuída por conta própria; ele se apoia inteiramente no Chubby, um serviço de locks separado, para eleger um único master vivo, permitir que os servidores de tablets reivindiquem a posse dos tablets que servem, e armazenar metadados de esquema e de controle de acesso, uma separação limpa entre 'servir dados rápido' e 'concordar sobre quem está no comando'.
O ZooKeeper generaliza a ideia do Chubby num serviço de coordenação aberto e reutilizável: uma hierarquia de znodes com watches definidos pelos clientes para notificações, com todas as escritas ordenadas pelo ZAB, um protocolo de broadcast atômico baseado em líder que resolve exatamente o mesmo problema de log replicado que o Raft resolve. Uma biblioteca cliente conecta este conceito diretamente de volta à teoria de consenso já coberta.
Quando uma única transação toca dados particionados em várias máquinas, um coordenador precisa fazer cada participante votar “preparado para confirmar” antes que qualquer um deles de fato confirme. O protocolo é simples, mas tem uma fraqueza real: um participante que está preparado e então perde contato com o coordenador fica preso segurando as suas travas, bloqueado, até que o coordenador volte.
O Spanner compra consistência externa entre data centers espalhados pelo planeta não inventando teoria de consenso nova, mas expondo diretamente a incerteza dos relógios: o TrueTime devolve um intervalo com garantia de conter o tempo real, e uma transação simplesmente espera esse intervalo passar (commit wait) antes de liberar o seu resultado, convertendo um problema difícil de sistemas distribuídos num problema físico e limitado.
Organize as réplicas em linha em vez de em torno de um único primário: as escritas entram pela cabeça e fluem de nó em nó até a cauda, que sozinha responde às leituras. Isso dá a mesma consistência forte da replicação primário-backup, enquanto espalha a vazão de escrita por todos os nós da cadeia em vez de criar um gargalo num único primário.
Dadas três cargas de trabalho realistas (um carrinho de compras que nunca pode perder uma escrita, um livro-razão financeiro global que nunca pode mostrar dois saldos conflitantes, e um job de análise em lote sobre petabytes de logs), escolha e justifique um projeto de sistema real desta disciplina para cada uma, e explique com precisão de qual garantia cada projeto alternativo teria aberto mão.
O programador fornece só uma função map (que transforma um registro de entrada em pares chave/valor intermediários) e uma função reduce (que combina todos os valores de uma chave intermediária); o runtime fornece todo o resto (paralelização, escalonamento, embaralhamento pela rede e tolerância a falhas) sobre dados que já estão num sistema de arquivos distribuído como o GFS.
Um único master reexecuta qualquer tarefa cujo worker pare de enviar heartbeats, escalona as tarefas de map no (ou perto do) chunkserver que já guarda a sua entrada para evitar saturar a rede, e lança execuções de backup redundantes das últimas tarefas retardatárias, para que uma única máquina lenta não consiga segurar um job inteiro.
O GFS expõe deliberadamente uma visão relaxada de um arquivo depois de escritas concorrentes, às vezes indefinida mas consistente, em troca de uma operação especializada de anexação atômica de registros que permite que milhares de produtores escrevam no mesmo arquivo de forma concorrente sem uma trava distribuída, precisamente o trade-off de que a sua carga de trabalho alvo (saída do MapReduce, escritas no estilo log) de fato precisa.
Part of the Computer Science curriculum.
A teoria de consenso, replicação e consistência de Sistemas Distribuídos I é necessária, mas não suficiente: sistemas reais que atendem bilhões de requisições por dia são construídos combinando essas primitivas em projetos específicos e opinativos, cada um trocando corretude, disponibilidade e desempenho de um jeito diferente para uma carga de trabalho específica.
Uma plataforma de function-as-a-service roda um handler sem estado sob demanda, escalando de zero a milhares de invocações concorrentes e cobrando por invocação: um avanço genuíno para o autoescalonamento, mas que uma crítica no nível de sistemas mostra ser decepcionantemente sem estado e pobre em E/S exatamente onde os estudos de caso desta disciplina (jobs de dados paralelos, armazenamento distribuído) mais precisam de estado e de rede rápida.
Mapear tanto os nós quanto as chaves no mesmo anel de hash, e atribuir cada chave ao próximo nó no sentido horário, significa que adicionar ou remover um nó só redistribui as chaves adjacentes a ele no anel, e não o espaço de chaves inteiro: o truque habilitador por trás de todo armazenamento particionado que precisa aumentar ou diminuir o número de nós sem uma redistribuição completa dos dados.
Um cache que é trivial em pequena escala (consultar uma chave, recorrer ao banco de dados num miss) quebra de várias formas específicas e reais a bilhões de requisições por segundo: manadas estrondosas num miss popular, leituras desatualizadas correndo com uma escrita no banco, e atraso de replicação entre regiões. Cada uma é tratada por um mecanismo distinto e deliberado (leases, um daemon de invalidação que lê o log de commits do banco, e pools regionais), e não por uma correção genérica.
O Dynamo substitui um quórum estrito (que bloqueia escritas sempre que uma réplica designada está fora do ar) por um quórum relaxado (sloppy quorum): uma escrita vai para os primeiros N nós saudáveis ao percorrer o anel, mesmo que isso signifique um substituto temporário, com uma dica, para um nó indisponível, escolhendo a disponibilidade das escritas em vez de sempre acertar o conjunto de réplicas teoricamente correto.
Como os quóruns relaxados permitem que dois clientes escrevam a mesma chave sem que nenhum veja a escrita do outro, o Dynamo marca todo valor com um relógio vetorial e devolve as versões genuinamente concorrentes à aplicação para reconciliação, sendo semanticamente honesto sobre a consistência eventual que está escolhendo, em vez de esconder o conflito e escolher uma versão arbitrariamente.
Um único master que guarda só metadados, muitos chunkservers que guardam chunks de 64MB replicados três vezes, e um projeto que otimiza deliberadamente para leituras sequenciais enormes e escritas só de anexação, em vez dos arquivos pequenos de acesso aleatório para os quais um sistema de arquivos de uma única máquina é construído.
Um mapa esparso, distribuído e ordenado, chaveado por (linha, família de colunas:qualificador, timestamp), dividido em tablets por faixa de linhas e persistido como SSTables imutáveis e ordenadas no GFS, um layout de armazenamento inteiramente diferente de um motor relacional indexado por B+Tree, otimizado para tabelas extremamente largas e esparsas e para escritas sequenciais de alta vazão.
O Bigtable não resolve a coordenação distribuída por conta própria; ele se apoia inteiramente no Chubby, um serviço de locks separado, para eleger um único master vivo, permitir que os servidores de tablets reivindiquem a posse dos tablets que servem, e armazenar metadados de esquema e de controle de acesso, uma separação limpa entre 'servir dados rápido' e 'concordar sobre quem está no comando'.
O ZooKeeper generaliza a ideia do Chubby num serviço de coordenação aberto e reutilizável: uma hierarquia de znodes com watches definidos pelos clientes para notificações, com todas as escritas ordenadas pelo ZAB, um protocolo de broadcast atômico baseado em líder que resolve exatamente o mesmo problema de log replicado que o Raft resolve. Uma biblioteca cliente conecta este conceito diretamente de volta à teoria de consenso já coberta.
Quando uma única transação toca dados particionados em várias máquinas, um coordenador precisa fazer cada participante votar “preparado para confirmar” antes que qualquer um deles de fato confirme. O protocolo é simples, mas tem uma fraqueza real: um participante que está preparado e então perde contato com o coordenador fica preso segurando as suas travas, bloqueado, até que o coordenador volte.
O Spanner compra consistência externa entre data centers espalhados pelo planeta não inventando teoria de consenso nova, mas expondo diretamente a incerteza dos relógios: o TrueTime devolve um intervalo com garantia de conter o tempo real, e uma transação simplesmente espera esse intervalo passar (commit wait) antes de liberar o seu resultado, convertendo um problema difícil de sistemas distribuídos num problema físico e limitado.
Organize as réplicas em linha em vez de em torno de um único primário: as escritas entram pela cabeça e fluem de nó em nó até a cauda, que sozinha responde às leituras. Isso dá a mesma consistência forte da replicação primário-backup, enquanto espalha a vazão de escrita por todos os nós da cadeia em vez de criar um gargalo num único primário.
Dadas três cargas de trabalho realistas (um carrinho de compras que nunca pode perder uma escrita, um livro-razão financeiro global que nunca pode mostrar dois saldos conflitantes, e um job de análise em lote sobre petabytes de logs), escolha e justifique um projeto de sistema real desta disciplina para cada uma, e explique com precisão de qual garantia cada projeto alternativo teria aberto mão.
O programador fornece só uma função map (que transforma um registro de entrada em pares chave/valor intermediários) e uma função reduce (que combina todos os valores de uma chave intermediária); o runtime fornece todo o resto (paralelização, escalonamento, embaralhamento pela rede e tolerância a falhas) sobre dados que já estão num sistema de arquivos distribuído como o GFS.
Um único master reexecuta qualquer tarefa cujo worker pare de enviar heartbeats, escalona as tarefas de map no (ou perto do) chunkserver que já guarda a sua entrada para evitar saturar a rede, e lança execuções de backup redundantes das últimas tarefas retardatárias, para que uma única máquina lenta não consiga segurar um job inteiro.
O GFS expõe deliberadamente uma visão relaxada de um arquivo depois de escritas concorrentes, às vezes indefinida mas consistente, em troca de uma operação especializada de anexação atômica de registros que permite que milhares de produtores escrevam no mesmo arquivo de forma concorrente sem uma trava distribuída, precisamente o trade-off de que a sua carga de trabalho alvo (saída do MapReduce, escritas no estilo log) de fato precisa.