Computer Science › Software + Computação Distribuída
Consenso quando os atrasos de mensagem são limitados: escolha de líder por rodadas, o que um crash custa, o limite inferior de f+1 rodadas e por que este mundo simples é a referência contra a qual os protocolos assíncronos são medidos.
O broadcast de ordem total como a abstração de que sistemas replicados realmente precisam, como ele se reduz a uma sequência de instâncias de consenso, e por que os dois problemas são equivalentes.
Do Paxos de decisão única a um log replicado: um líder estável, pular a fase 1 nos slots seguintes, preencher lacunas, e o que a lição existente de Paxos deixou de fora sobre vivacidade.
O Fast Paxos e o seu caminho rápido que pula o líder, com os quóruns maiores que ele paga, e depois o Flexible Paxos, que mostra que só os quóruns da fase 1 e da fase 2 precisam se intersectar.
Como trocar o conjunto de réplicas sem perder segurança: entradas de configuração no log, o joint consensus e as mudanças de um servidor por vez do Raft, e a falha de maiorias disjuntas que eles evitam.
Detectores de falha não confiáveis como definidos por Chandra e Toueg, suas classes de completude e precisão, o detector mais fraco para consenso, e detectores por heartbeat e phi-accrual na prática.
Group membership como uma sequência de views acordadas, a comunicação view-synchronous e como o modelo de virtual synchrony se relaciona com a replicação baseada em consenso.
A consistência causal exige que cada processo veja alguma serialização das próprias operações e de todas as escritas que respeite o fecho transitivo da ordem de programa com a ordem writes-into. O modelo fica entre a consistência sequencial e a PRAM, é rastreado com vector clocks ou metadados explícitos de dependência, e o teorema costumeiro sobre ele trata, na verdade, da consistência causal em tempo real: sob falhas de omissão, nada mais forte que ela é alcançável com armazenamento sempre disponível e one-way convergent.
Leituras de uma chave por vez não dão visão consistente de várias chaves, nem com causalidade. O COPS-GT acrescenta transações só de leitura em até duas rodadas, e o Cure define a Consistência Causal Transacional: transações interativas sobre snapshots causalmente consistentes, com visibilidade atômica e convergência por CRDTs. O modelo abre mão de invariantes entre transações concorrentes, de parte do frescor e de escritas recentes de um datacenter perdido.
O espaço clássico de projeto da replicação de bancos de dados: quando as atualizações se propagam, quem pode originá-las, as cinco fases de Wiesmann e o modelo de Gray, em que deadlocks e reconciliações crescem com o cubo do número de nós. A certificação sobre atomic broadcast executa localmente, difunde read set e write set e deixa um teste determinístico decidir o mesmo em todo site, com one-copy serializability e sem atomic commit.
Algoritmos epidêmicos do trabalho da Xerox PARC: gossip em push, pull e push-pull, a velocidade com que um rumor se espalha, e a diferença entre anti-entropy e rumor mongering.
Overlays não estruturados: flooding e seu custo, super-peers como meio-termo, e como o tit-for-tat e o rarest-first do BitTorrent trocam o problema de busca por um de disseminação.
O anel de identificadores do Chord, successors e finger tables, por que um lookup leva um número logarítmico de hops, e como a stabilization lida com nós que entram e falham.
Duas DHTs que roteiam por dígitos compartilhados do identificador ou por distância XOR: os k-buckets do Kademlia, a tabela de roteamento do Pastry, e por que lookups paralelos e localidade importam na prática.
Como construir publish-subscribe sobre um overlay estruturado: árvores de disseminação por tópico, como no Scribe, e como esse desenho se compara a um broker centralizado.
O shared log como primitiva: o sequenciador e a replicação conduzida pelo cliente do CORFU sobre flash, as estruturas de dados replicadas do Tango construídas em cima dele e os streams materializados do vCorfu.
Dois caminhos para além de um sequenciador único: o FuzzyLog relaxa a ordem total em uma ordem parcial entre cores, e o Scalog replica os registros primeiro e os ordena depois.
Um shared log como substrato de estado para funções serverless: as abstrações do Boki baseadas em log para workflows e transações, e a abordagem do FlexLog para o mesmo problema.
Como reduzir o custo de ordenação de um shared log sem abrir mão da ordem total: o LazyLog confirma o append antes de existir posição e fixa a ordem em segundo plano, antes que ela possa ser lida, e o SpecLog entrega registros numa ordem prevista para o consumidor computar enquanto a coordenação acontece, com a confirmação ainda limitando o que pode sair para fora.
A inversão do Calvin: as máquinas concordam com uma sequência global de transações antes de pegar qualquer lock, e cada réplica executa essa sequência de forma determinística, o que tira o two-phase commit do caminho e encurta o tempo em que locks ficam presos, ao custo de conjuntos de leitura e escrita declarados, de bloqueios que não podem ser contornados e de latência no sequenciamento.
Levar a ordenação para a rede e deixar a entrega confiável na aplicação: o multicast ordenado e não confiável do NOPaxos, os multi-stamps do Eris para transações entre shards e o Hydra, que combina relógios e números de sequência para dispensar um ponto único de serialização.
O Saturn separa dados de metadados causais: uma árvore de serializadores propaga um label pequeno e de tamanho constante, cada datacenter recebe a própria serialização, e a troca entre latência de visibilidade e vazão encolhe e se muda para a configuração da árvore.
Dada uma carga de trabalho concreta, cinco perguntas levam a uma escolha entre consenso, certificação, réplicas causais, shared logs, projetos determinísticos e ordenação na rede, com o custo calculado e cada decisão defendida contra seus modos de falha.
Part of the Computer Science curriculum.
Consenso quando os atrasos de mensagem são limitados: escolha de líder por rodadas, o que um crash custa, o limite inferior de f+1 rodadas e por que este mundo simples é a referência contra a qual os protocolos assíncronos são medidos.
O broadcast de ordem total como a abstração de que sistemas replicados realmente precisam, como ele se reduz a uma sequência de instâncias de consenso, e por que os dois problemas são equivalentes.
Do Paxos de decisão única a um log replicado: um líder estável, pular a fase 1 nos slots seguintes, preencher lacunas, e o que a lição existente de Paxos deixou de fora sobre vivacidade.
O Fast Paxos e o seu caminho rápido que pula o líder, com os quóruns maiores que ele paga, e depois o Flexible Paxos, que mostra que só os quóruns da fase 1 e da fase 2 precisam se intersectar.
Como trocar o conjunto de réplicas sem perder segurança: entradas de configuração no log, o joint consensus e as mudanças de um servidor por vez do Raft, e a falha de maiorias disjuntas que eles evitam.
Detectores de falha não confiáveis como definidos por Chandra e Toueg, suas classes de completude e precisão, o detector mais fraco para consenso, e detectores por heartbeat e phi-accrual na prática.
Group membership como uma sequência de views acordadas, a comunicação view-synchronous e como o modelo de virtual synchrony se relaciona com a replicação baseada em consenso.
A consistência causal exige que cada processo veja alguma serialização das próprias operações e de todas as escritas que respeite o fecho transitivo da ordem de programa com a ordem writes-into. O modelo fica entre a consistência sequencial e a PRAM, é rastreado com vector clocks ou metadados explícitos de dependência, e o teorema costumeiro sobre ele trata, na verdade, da consistência causal em tempo real: sob falhas de omissão, nada mais forte que ela é alcançável com armazenamento sempre disponível e one-way convergent.
Leituras de uma chave por vez não dão visão consistente de várias chaves, nem com causalidade. O COPS-GT acrescenta transações só de leitura em até duas rodadas, e o Cure define a Consistência Causal Transacional: transações interativas sobre snapshots causalmente consistentes, com visibilidade atômica e convergência por CRDTs. O modelo abre mão de invariantes entre transações concorrentes, de parte do frescor e de escritas recentes de um datacenter perdido.
O espaço clássico de projeto da replicação de bancos de dados: quando as atualizações se propagam, quem pode originá-las, as cinco fases de Wiesmann e o modelo de Gray, em que deadlocks e reconciliações crescem com o cubo do número de nós. A certificação sobre atomic broadcast executa localmente, difunde read set e write set e deixa um teste determinístico decidir o mesmo em todo site, com one-copy serializability e sem atomic commit.
Algoritmos epidêmicos do trabalho da Xerox PARC: gossip em push, pull e push-pull, a velocidade com que um rumor se espalha, e a diferença entre anti-entropy e rumor mongering.
Overlays não estruturados: flooding e seu custo, super-peers como meio-termo, e como o tit-for-tat e o rarest-first do BitTorrent trocam o problema de busca por um de disseminação.
O anel de identificadores do Chord, successors e finger tables, por que um lookup leva um número logarítmico de hops, e como a stabilization lida com nós que entram e falham.
Duas DHTs que roteiam por dígitos compartilhados do identificador ou por distância XOR: os k-buckets do Kademlia, a tabela de roteamento do Pastry, e por que lookups paralelos e localidade importam na prática.
Como construir publish-subscribe sobre um overlay estruturado: árvores de disseminação por tópico, como no Scribe, e como esse desenho se compara a um broker centralizado.
O shared log como primitiva: o sequenciador e a replicação conduzida pelo cliente do CORFU sobre flash, as estruturas de dados replicadas do Tango construídas em cima dele e os streams materializados do vCorfu.
Dois caminhos para além de um sequenciador único: o FuzzyLog relaxa a ordem total em uma ordem parcial entre cores, e o Scalog replica os registros primeiro e os ordena depois.
Um shared log como substrato de estado para funções serverless: as abstrações do Boki baseadas em log para workflows e transações, e a abordagem do FlexLog para o mesmo problema.
Como reduzir o custo de ordenação de um shared log sem abrir mão da ordem total: o LazyLog confirma o append antes de existir posição e fixa a ordem em segundo plano, antes que ela possa ser lida, e o SpecLog entrega registros numa ordem prevista para o consumidor computar enquanto a coordenação acontece, com a confirmação ainda limitando o que pode sair para fora.
A inversão do Calvin: as máquinas concordam com uma sequência global de transações antes de pegar qualquer lock, e cada réplica executa essa sequência de forma determinística, o que tira o two-phase commit do caminho e encurta o tempo em que locks ficam presos, ao custo de conjuntos de leitura e escrita declarados, de bloqueios que não podem ser contornados e de latência no sequenciamento.
Levar a ordenação para a rede e deixar a entrega confiável na aplicação: o multicast ordenado e não confiável do NOPaxos, os multi-stamps do Eris para transações entre shards e o Hydra, que combina relógios e números de sequência para dispensar um ponto único de serialização.
O Saturn separa dados de metadados causais: uma árvore de serializadores propaga um label pequeno e de tamanho constante, cada datacenter recebe a própria serialização, e a troca entre latência de visibilidade e vazão encolhe e se muda para a configuração da árvore.
Dada uma carga de trabalho concreta, cinco perguntas levam a uma escolha entre consenso, certificação, réplicas causais, shared logs, projetos determinísticos e ordenação na rede, com o custo calculado e cada decisão defendida contra seus modos de falha.