Google Chubby e Apache ZooKeeper: coordenação e locks

01 · CONTEXTO

Quem manda agora? O problema da coordenação

Todo sistema que roda várias cópias de um servidor precisa responder a uma pergunta simples: quem manda agora? A resposta precisa valer para todos ao mesmo tempo, mesmo com máquinas e redes falhando.

Os autores do Chubby, serviço de lock do Google, esperavam que ele ajudasse na sincronização de grão grosso e, em especial, na eleição de um líder entre servidores equivalentes. O GFS usa um lock do Chubby para designar o seu master, e o Bigtable o usa para eleger o master, para o master descobrir os servidores que controla e para os clientes encontrarem o master.

Antes do Chubby, a maioria dos sistemas distribuídos do Google usava métodos ad hoc para eleger o primário, quando o trabalho podia ser duplicado sem dano, ou exigia intervenção do operador, quando a correção era essencial. No segundo caso, o paper relata uma melhora significativa de disponibilidade em sistemas que deixaram de precisar de intervenção humana na falha.

O serviço oferece uma interface parecida com a de um sistema de arquivos distribuído, com locks consultivos, e o desenho prioriza disponibilidade e confiabilidade em vez de alto desempenho. O paper observa que quem conhece computação distribuída reconhecerá a eleição de um primário entre pares como uma instância do problema de consenso distribuído.

Por que um serviço de lock e não uma biblioteca de consenso? Um motivo é que sistemas costumam começar como protótipos, com pouca carga e garantias frouxas de disponibilidade, e um servidor de lock facilita manter a estrutura do programa e os padrões de comunicação existentes. Para eleger um master que escreve em um servidor de arquivos já existente, bastam duas instruções e um parâmetro de RPC a mais. Outro motivo é que, com um serviço de lock, até um único cliente consegue obter o lock e progredir com segurança.

A segunda decisão central foi servir pequenos arquivos, para que o primário eleito anuncie a si mesmo e seus parâmetros sem exigir um segundo serviço. Outra escolha, que o paper diz poder surpreender, é esperar uso de grão grosso, e não locks de grão fino mantidos por segundos ou menos. Locks de grão grosso impõem muito menos carga ao servidor, e um exemplo é a eleição de um primário que depois trata todo o acesso a um dado por um tempo considerável, talvez horas ou dias.

02 · A CÉLULA CHUBBY

Réplicas, um mestre e um master lease

Uma célula Chubby é um pequeno conjunto de servidores, tipicamente cinco, chamados réplicas e colocados de modo a reduzir a chance de falha correlacionada, por exemplo em racks diferentes. Como algoritmos de consenso decidem por quórum, o Chubby costuma ter cinco réplicas por célula, das quais três precisam estar rodando para a célula funcionar.

As réplicas usam um protocolo de consenso para eleger um mestre. O mestre precisa de votos da maioria das réplicas e de promessas de que elas não elegerão outro mestre durante alguns segundos, o master lease. Só o mestre inicia leituras e escritas no banco; as demais réplicas apenas copiam as atualizações.

1. As réplicas da célula estão listadas no DNS, e é a elas que o cliente envia o pedido de localização do mestre.

2. O cliente pergunta a uma réplica onde está o mestre, e uma réplica que não é o mestre responde com a identidade dele.

3. Localizado o mestre, o cliente envia todos os pedidos a ele até que pare de responder ou diga que deixou de ser o mestre.

4. Uma escrita é propagada às réplicas pelo protocolo de consenso e só é confirmada quando chega à maioria.

5. Leituras são atendidas só pelo mestre, o que é seguro enquanto o master lease não expirou.

6. A cada poucas horas o mestre grava um snapshot do banco em um servidor GFS de outro prédio.

Escritas são propagadas a todas as réplicas pelo protocolo de consenso e confirmadas quando chegam à maioria. Leituras são atendidas só pelo mestre, o que é seguro enquanto o master lease não expirou, porque nenhum outro mestre pode existir. Se o mestre falha, as outras réplicas rodam a eleição quando seus master leases expiram, e um novo mestre costuma ser eleito em alguns segundos; o paper cita duas eleições recentes que levaram 6 s e 4 s, e valores de até 30 s.

O cliente enxerga uma árvore estrita de arquivos e diretórios, numa interface parecida com a do UNIX, porém mais simples, e qualquer nó pode funcionar como lock consultivo de leitura e escrita. Arquivos efêmeros servem como arquivos temporários e como indicadores aos demais de que um cliente está vivo.

O backup funciona assim: a cada poucas horas o mestre de cada célula grava um snapshot do banco em um servidor GFS em outro prédio. Isso garante que o backup sobreviva a danos no prédio e evita dependência cíclica, já que um GFS no mesmo prédio poderia depender do Chubby para eleger seu master.

03 · LOCKS, SEQUENCERS E SESSÕES

Locks consultivos e a mensagem atrasada

Os locks do Chubby são consultivos: conflitam apenas com outras tentativas de adquirir o mesmo lock. Os autores rejeitaram locks obrigatórios, que tornam objetos travados inacessíveis a clientes que não seguram o lock, e um dos motivos é que os locks do Chubby costumam proteger recursos implementados por outros serviços, não só o arquivo associado ao lock.

Em sistemas distribuídos o lock é complexo porque a comunicação é incerta e os processos falham de forma independente. Um processo que segura o lock L pode emitir um pedido R e falhar; outro processo pode adquirir L e agir antes de R chegar ao destino. Se R chegar depois, pode ser executado sem a proteção de L e sobre dados potencialmente inconsistentes.

O Chubby oferece o sequencer: o dono do lock pode pedir uma sequência opaca de bytes que descreve o estado do lock logo após a aquisição, com o nome do lock, o modo de aquisição e o número de geração do lock. O cliente a passa aos servidores cujas operações quer proteger, e o servidor receptor deve testar se o sequencer ainda é válido e, se não for, rejeitar o pedido. O paper também descreve, na justificativa do desenho, passar a contagem de aquisição do lock na RPC de escrita, e o servidor de arquivos rejeita a escrita se a contagem for menor que o valor atual.

Para servidores que não suportam sequencers, o paper descreve um mecanismo imperfeito, porém mais fácil, para reduzir o risco de pedidos atrasados ou reordenados. Se o lock fica livre porque o dono falhou ou ficou inacessível, o servidor impede outros clientes de pegá-lo durante um período chamado lock-delay. O cliente pode escolher qualquer valor até um limite, na época de um minuto.

A relação entre cliente e célula é a sessão, mantida por handshakes periódicos chamados KeepAlives. Cada sessão tem um lease: um intervalo futuro em que o mestre garante não encerrar a sessão unilateralmente. A extensão padrão é de 12 s, e um mestre sobrecarregado pode usar valores maiores para reduzir o número de KeepAlives. O mestre normalmente bloqueia o KeepAlive até que o lease anterior do cliente esteja perto de expirar, e o cliente inicia um novo logo após receber a resposta, de modo que quase sempre há um KeepAlive bloqueado no mestre.

O cache do cliente também depende da sessão. Os clientes mantêm em memória um cache consistente, write-through, de dados de arquivos e metadados, inclusive a ausência de arquivos. Para mudar um dado, o mestre bloqueia a modificação enquanto envia invalidações a todo cliente que possa tê-lo em cache, e ela só prossegue depois que cada cliente confirmou a invalidação ou deixou o lease de seu cache expirar. As invalidações viajam nas respostas de KeepAlive, o que impede o cliente de manter a sessão sem confirmá-las.

1. Em operação normal, o cliente mantém quase sempre um KeepAlive bloqueado no mestre, e a resposta informa o novo prazo do lease.

2. O mestre morre antes de responder ao KeepAlive seguinte, e as outras réplicas rodam a eleição quando seus master leases expiram.

3. O lease local do cliente expira: ele esvazia e desabilita o cache, bloqueia as chamadas da aplicação e espera o período de graça.

4. O novo mestre escolhe um novo número de época, que os clientes devem apresentar em cada chamada, e rejeita chamadas com época antiga.

5. O primeiro KeepAlive ao novo mestre é rejeitado por trazer a época errada; a resposta ao pedido reenviado permite ao cliente estender o lease.

6. Como o período de graça cobriu o intervalo entre o fim do lease antigo e o início do novo, a aplicação percebeu apenas um atraso.

O desfecho depende de uma comparação. Se o período de graça cobre o intervalo entre o fim do lease antigo e o início do novo, o cliente vê apenas um atraso; se fosse menor que esse intervalo, ele teria abandonado a sessão e reportado a falha à aplicação.

04 · APACHE ZOOKEEPER

Um kernel de coordenação sem locks na API

O paper do ZooKeeper descreve o Chubby como um serviço de lock com garantias fortes de sincronização, sobre o qual locks implementam eleição de líder e associação a grupos. O ZooKeeper, por sua vez, busca ser um kernel simples e de alto desempenho para construir primitivas de coordenação mais complexas no cliente.

Ao desenhar a API, os autores se afastaram de primitivas bloqueantes, como locks, porque elas podem fazer clientes lentos ou defeituosos prejudicar o desempenho dos mais rápidos. Olhando só as assinaturas, o ZooKeeper parece ser o Chubby sem os métodos de lock, open e close.

Os dados ficam em znodes organizados em um espaço de nomes hierárquico. Um znode efêmero é removido automaticamente quando a sessão que o criou termina, deliberadamente ou por falha, e a flag sequential acrescenta ao nome do znode um contador monotonicamente crescente. Znodes não foram feitos para armazenamento geral de dados.

As garantias de ordem são duas. A primeira são escritas linearizáveis: todos os pedidos que alteram o estado são serializáveis e respeitam precedência. A segunda é a ordem FIFO por cliente: os pedidos de um cliente executam na ordem em que foram enviados.

O banco replicado é um banco em memória com toda a árvore de dados. Todos os pedidos que atualizam o estado são encaminhados ao líder, que calcula o estado do sistema após a escrita e a transforma em uma transação; ao contrário dos pedidos dos clientes, as transações são idempotentes. O líder difunde a mudança pelo Zab, que usa por padrão quóruns de maioria, e por isso o ZooKeeper só funciona se a maioria dos servidores estiver correta.

1. Cada cliente se conecta a exatamente um servidor do ensemble e envia a ele os pedidos.

2. Uma leitura é respondida pelo banco local do servidor, sem protocolo de acordo, e pode devolver um valor desatualizado.

3. Uma escrita é encaminhada pelo servidor ao líder.

4. O líder transforma a escrita em uma transação idempotente e a difunde pelo Zab, que decide por maioria.

5. O servidor que recebeu o pedido responde ao cliente quando entrega a mudança, e é esse servidor que dispara as notificações de watch daquele cliente.

6. Quem precisa do valor mais recente chama sync antes da leitura.

O preço das leituras locais é a possível defasagem: uma leitura rápida não garante ordem de precedência e pode devolver um valor desatualizado, mesmo que uma atualização mais recente do mesmo znode já tenha sido confirmada. Quando isso importa, o cliente chama sync seguido da leitura para obter o valor mais recente.

A notificação de mudanças segue outro modelo. Watches permitem que clientes recebam notificações sem fazer polling; são gatilhos de uso único associados a uma sessão e indicam que houve uma mudança, mas não a entregam. O paper contrasta isso com o Chubby, que gerencia diretamente o cache dos clientes e bloqueia atualizações para invalidar o cache de todos os que guardam o dado; se algum cliente é lento ou defeituoso, a atualização atrasa. Leases só limitam esse impacto, enquanto os watches do ZooKeeper evitam o problema por completo.

Locks existem, mas como receita no cliente. O serviço não conhece essas primitivas mais poderosas, que são implementadas inteiramente no cliente com a API. No lock mais simples, o cliente tenta criar um znode efêmero e, se a criação der certo, tem o lock; essa versão sofre do herd effect, porque todos os que esperam disputam o lock quando ele é liberado, embora só um possa obtê-lo.

A receita sem herd effect usa a flag sequential para ordenar a tentativa de cada cliente em relação a todas as outras. Se o znode do cliente tem o menor número de sequência, ele tem o lock; senão, o cliente espera a remoção do znode que tem o lock ou o receberá antes dele. Como cada cliente observa só o znode que precede o seu, apenas um processo é acordado quando um lock é liberado ou um pedido é abandonado.

O paper também mostra um caso em que locks como os do Chubby não bastam. Quando um novo líder assume, ele precisa mudar muitos parâmetros de configuração, e há dois requisitos: enquanto ele faz as mudanças, os demais processos não devem passar a usar a configuração que está sendo alterada; e, se ele morrer antes de terminar, não devem usar a configuração parcial. Locks como os do Chubby ajudariam no primeiro requisito, mas são insuficientes para o segundo. No ZooKeeper, o novo líder apaga o znode ready, atualiza os znodes de configuração e recria o ready; pelas garantias de ordem, quem vê o ready vê também todas as mudanças.

Em uso real, o Yahoo! Message Broker emprega o ZooKeeper para gerenciar a distribuição de tópicos, tratar falhas de máquinas e controlar a operação do sistema. Para as cargas-alvo, com razão de leitura para escrita de 2:1 a 100:1, o paper mostra que o ZooKeeper trata de dezenas a centenas de milhares de transações por segundo. Sobre disponibilidade, o serviço fica disponível se a maioria dos servidores está ativa e se comunicando, e uma mudança confirmada persiste enquanto um quórum puder se recuperar.

05 · LADO A LADO

Chubby e ZooKeeper nas mesmas perguntas

06 · LIÇÕES DE PRODUÇÃO

O que a operação ensinou ao Chubby

Os clientes do Chubby são processos individuais, então o mestre pode ter muito mais clientes do que se espera: o paper relata ter visto 90 mil clientes falando diretamente com um mestre, muito mais que o número de máquinas. Como há um mestre por célula, em uma máquina igual à dos clientes, eles podem sobrecarregá-lo por uma margem enorme.

O tráfego de RPC é dominado por KeepAlives de sessão, com poucas leituras e pouquíssimas escritas ou aquisições de lock. Os autores concluem que a chave para escalar o Chubby não é o desempenho do servidor, e sim reduzir a comunicação com ele.

O paper também mede o lado da disponibilidade: numa amostra de 61 interrupções ao longo de algumas semanas, somando 700 células-dia, a maioria durou 15 s ou menos e 52 ficaram abaixo de 30 s, e a maioria das aplicações não é afetada de forma significativa por interrupções abaixo de 30 s.

Embora projetado como serviço de lock, o uso mais popular do Chubby foi como servidor de nomes. No DNS, se a troca rápida de serviços falhos é desejada, o TTL pode ficar pequeno o bastante para sobrecarregar os servidores. O paper considera um TTL de 60 s e calcula que manter os caches DNS de um job de 3 mil clientes exigiria 150 mil consultas por segundo. O cache do Chubby usa invalidações explícitas, então uma taxa constante de KeepAlives mantém um número arbitrário de entradas em cache indefinidamente, na ausência de mudanças.

Mesmo assim houve picos. Ao implantar o serviço de nomes, iniciar um job de 3 mil processos, que gera 9 milhões de requisições, podia deixar o mestre de joelhos. A solução foi agrupar as entradas de nomes em lotes, de modo que uma consulta devolva os mapeamentos de um grande número, tipicamente 100, de processos relacionados.

Outra lição veio dos clientes abusivos. Dois outros serviços passaram a usar um mesmo módulo de acompanhamento de uploads para uma população maior de usuários, e um único arquivo de 1,5 MB passou a ser reescrito por inteiro a cada ação do usuário, com o espaço usado pelo serviço superando o de todos os outros clientes somados. O Chubby introduziu um limite de 256 kB por arquivo, mas migrar os dados para outro sistema levou aproximadamente um ano.

A última lição é sobre quem usa o serviço. Os desenvolvedores raramente pensam em probabilidades de falha e tendem a tratar o Chubby como se estivesse sempre disponível. O Chubby fornece um evento para os clientes detectarem que houve fail-over do mestre, com a intenção de que verifiquem possíveis mudanças, mas muitos desenvolvedores optaram por derrubar a aplicação ao recebê-lo, reduzindo bastante a disponibilidade de seus sistemas.