Papers
ZooKeeper: Wait-free Coordination for Internet-scale Systems
Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, Benjamin Reed · USENIX Annual Technical Conference (ATC) 2010, 2010
O problema: toda aplicação distribuída precisa de coordenação, e cada uma a reinventava
Aplicações distribuídas em larga escala precisam de coordenação: configuração compartilhada, eleição de líder, saber quais processos estão vivos (membership), locks e barreiras. Antes do ZooKeeper, a abordagem comum era um serviço específico para cada necessidade, ou um serviço de lock (a referência era o Chubby, do Google), em que o servidor implementa as primitivas prontas. Os autores, do Yahoo!, escolheram outro caminho: em vez de embutir no servidor operações como lock ou eleição, oferecer um 'kernel' simples e de alto desempenho com uma API pequena, para que os próprios clientes construam as primitivas de que precisam. O serviço combina ideias de mensageria em grupo, registradores compartilhados e locks distribuídos num serviço replicado e centralizado. A promessa central, que dá nome ao paper, é o acesso 'wait-free': nenhuma requisição de um cliente fica bloqueada esperando outro cliente (por exemplo, esperando a liberação de um lock dentro do servidor). Os autores consideram essa propriedade importante para o desempenho e para a tolerância a falhas, mas não suficiente para coordenação: por isso ela vem acompanhada de garantias de ordenação bem escolhidas.
O modelo de dados: znodes, nós efêmeros, flag sequencial e watches
O ZooKeeper expõe um espaço de nomes hierárquico parecido com um sistema de arquivos. Cada nó, chamado znode, guarda uma pequena quantidade de dados de coordenação (metadados, não dados de aplicação) e também pode ter filhos. Existem dois tipos de znode. Os regulares são criados e removidos explicitamente pelos clientes. Os efêmeros são removidos automaticamente quando a sessão do cliente que os criou termina, o que os torna ideais para detectar falhas e representar presença de processos. Além disso, na criação de qualquer um dos dois tipos o cliente pode ligar a flag sequencial: o nome do nó ganha um contador crescente anexado, o que dá ordenação e unicidade entre vários clientes criando nós sob o mesmo pai. Atualizações podem ser condicionadas à versão do znode. Para evitar polling, o cliente pode registrar um watch: uma notificação de uso único, disparada quando o znode muda; depois de disparado, o cliente precisa registrá-lo de novo se quiser continuar acompanhando. O cliente mantém uma sessão, cujo estado é distribuído, e por isso pode se reconectar a outro servidor após uma falha. A API é assíncrona, permitindo que um cliente tenha várias operações pendentes ao mesmo tempo.
Garantias e trade-off: escritas linearizáveis, ordem FIFO por cliente e leituras locais
O núcleo do trade-off do paper está em duas garantias: as requisições de um mesmo cliente são executadas em ordem FIFO, e as requisições que alteram o estado são linearizáveis. Os autores argumentam que esse par é suficiente para construir as primitivas de coordenação que as aplicações precisam e permite uma implementação eficiente. Como as escritas passam por um protocolo de difusão atômica baseado em líder, todos os servidores as aplicam na mesma ordem total. Já as leituras são atendidas pela réplica local à qual o cliente está conectado, sem passar pelo protocolo de acordo; por isso não são ordenadas em relação às escritas de outros clientes e podem devolver dados desatualizados. Para quem precisa de um valor atualizado, existe a operação sync. Os watches fecham a lacuna de outra forma: um cliente que registrou um watch nunca enxerga o novo valor antes de receber a notificação da mudança. O custo é claro: leituras são rápidas e escalam com o número de réplicas, enquanto escritas são mais lentas porque exigem acordo entre servidores e gravação durável. O serviço continua disponível enquanto a maioria (quórum) dos servidores estiver funcionando.
Primitivas construídas sobre o kernel: configuração, membership, locks e eleição
A força do design aparece nas receitas que os clientes montam com znodes e watches. Para gerenciar configuração, guarda-se o valor em um znode, lê-se com watch e relê-se quando a notificação chega. Para membership de grupo, cada processo cria um filho efêmero sob o znode do grupo: listar os filhos mostra quem está vivo, e um watch no pai avisa de entradas e saídas, inclusive quando um processo morre, pois sua sessão expira e o nó some. Para locks, cada cliente cria um znode efêmero e sequencial sob o znode do lock. Quem tem o menor número detém o lock; os demais observam apenas o nó imediatamente anterior ao seu. Assim, quando o lock é liberado, só um cliente acorda, evitando o 'efeito manada' (herd effect), em que muitos clientes disputam ao mesmo tempo e saturam o servidor. A documentação de receitas do Apache ZooKeeper descreve a eleição de líder com o mesmo padrão: o menor número vence e cada candidato observa seu predecessor. Barreiras também podem ser montadas com znodes e watches. Nada disso é operação do servidor: o ZooKeeper só oferece os blocos básicos.
Implementação, desempenho e legado
Cada servidor mantém uma cópia do banco de dados (a árvore de znodes) em memória. Antes de aplicar uma atualização, o servidor a registra em log e força a gravação em disco. Para recuperação, são feitos snapshots 'fuzzy': o servidor percorre a árvore sem travar o estado, de modo que o snapshot pode não corresponder a nenhum instante único; isso continua correto porque as mudanças de estado são idempotentes e reaplicadas em ordem. Segundo o paper, o ZooKeeper atinge de dezenas a centenas de milhares de transações por segundo em cargas com proporção de leitura para escrita de 2:1 a 100:1, o que permite uso intensivo e não apenas locks de granularidade grossa. A documentação atual do projeto afirma que ele rende melhor em cargas dominadas por leitura, em torno de 10:1, o que é típico de um serviço de coordenação. O desenho virou o projeto Apache ZooKeeper, usado por sistemas como Hadoop, HBase, Flink, Pulsar, Solr e Spark (e, historicamente, pelo Kafka antes do KRaft) para eleição de líder, detecção de falhas, descoberta de serviços e gerenciamento de configuração.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.