Conceitos
Gossip, associação ao cluster (membership) e detecção de falhas
Intuição
Imagine um grande escritório sem recepcionista e sem uma lista mestra de funcionários. De tempos em tempos, cada pessoa conversa com um colega escolhido ao acaso e os dois trocam notícias sobre quem entrou ou saiu da equipe e o que mudou, de modo que a informação se espalha por todo o escritório sem ninguém no comando. Para decidir se alguém realmente se foi, alguns escritórios simplesmente deixam de contar com o colega que ignora suas mensagens (e voltam a checar de vez em quando), enquanto outros aprendem com que frequência costumam ouvir de cada pessoa, de modo que, quanto maior o silêncio em comparação com esse ritmo, mais desconfiados ficam, agindo apenas quando a desconfiança é alta o bastante.
Como funciona
No Dynamo não existe um registro central de quais nós estão vivos nem de quais posições do anel cada um possui: cada nó periodicamente propaga (gossip) sua visão do anel e da membership para um par escolhido ao acaso, e os dois mesclam suas visões. A membership do Cassandra também é baseada em gossip, construída sobre o Scuttlebutt, que o paper do Cassandra descreve como um mecanismo de gossip anti-entropia muito eficiente, valorizado pelo baixo uso de CPU; o mesmo gossip também transporta outros estados de controle do sistema, não apenas a membership. Na detecção de falhas, o projeto final do Dynamo não depende de uma visão global propagada por gossip (os primeiros projetos dependiam, mas as entradas e saídas explícitas a tornaram desnecessária); a detecção de falhas dele é puramente local: o nó A trata B como falho quando B não responde às mensagens de A, mesmo que B responda a outros, e A tenta B de novo periodicamente para ver se ele se recuperou. O Cassandra, em vez disso, usa uma versão modificada do Phi Accrual Failure Detector, que produz um nível de suspeita, Phi, em vez de uma resposta sim ou não, numa escala que se ajusta dinamicamente às condições de rede e de carga, e o paper atribui aos detectores accrual uma qualidade muito boa tanto em precisão quanto em velocidade. Cada nó mantém uma janela deslizante dos intervalos entre chegadas das mensagens de gossip dos outros nós e calcula o Phi a partir da distribuição resultante; os autores do Cassandra constataram que uma distribuição exponencial se ajustava melhor do que a aproximação gaussiana sugerida pelo paper original do accrual, por causa de como o canal de gossip afeta a latência. Se um nó é suspeito quando o Phi chega a 1, a chance de erro (uma mensagem atrasada que depois contradiz a decisão) é de cerca de 10 por cento, caindo para cerca de 1 por cento em Phi 2 e cerca de 0,1 por cento em Phi 3. As mudanças de membership se espalham por gossip até que a lista de todos os nós concorde, enquanto cada nó julga as falhas por conta própria; nenhum dos dois papers afirma coordenação zero: o Dynamo depende de entradas e saídas emitidas por administradores e de nós semente (seed nodes), e as políticas do Cassandra que consideram rack e datacenter usam um líder eleito pelo Zookeeper que informa aos nós quais faixas eles replicam.
Na prática
A membership e as posições no anel se espalham de par a par por gossip, de modo que nenhum serviço central precisa ser consultado a cada requisição, embora o Cassandra ainda use o Zookeeper para alguma coordenação, como um líder que atribui as faixas de réplicas nas suas políticas que consideram rack e datacenter. O paper do Cassandra relata um experimento com 100 nós em que os outros detectores levaram cerca de dois minutos para detectar um nó falho, enquanto o detector accrual com Phi igual a 5 reduziu a média para cerca de 15 segundos. Você escolheria essa abordagem quando quer um detector ao mesmo tempo preciso e rápido (a medição do paper foi um único experimento com 100 nós), aceitando que o limiar de Phi é um ajuste que você calibra contra o risco de falsas suspeitas.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.