Papers
The Chubby lock service for loosely-coupled distributed systems
Mike Burrows · 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI) 2006, 2006
O problema: coordenação grossa entre servidores equivalentes e por que um serviço de locks
O Chubby é um serviço interno do Google pensado para sistemas distribuídos fracamente acoplados, formados por muitas máquinas pequenas ligadas por uma rede rápida. Ele oferece lock de granularidade grossa e armazenamento confiável, porém de baixo volume, por meio de uma interface parecida com a de um sistema de arquivos distribuído com locks consultivos. A ênfase do projeto está em disponibilidade e confiabilidade, não em alto desempenho. O caso de uso típico é a eleição de um primário entre servidores equivalentes: o GFS usa um lock do Chubby para designar seu servidor master, e o Bigtable o usa para eleger o master, descobrir os servidores que controla e como local conhecido e disponível para guardar pequenos metadados. Antes do Chubby, muitos sistemas elegiam o primário por métodos ad hoc ou exigiam intervenção de um operador quando a correção era essencial. O autor explica por que não bastaria uma biblioteca de Paxos: desenvolvedores costumam começar com protótipos sem pensar em alta disponibilidade e só depois acrescentam replicação, e um serviço de locks é mais fácil de encaixar em programas existentes. Além disso, programadores conhecem locks, e com um serviço de locks mesmo um único cliente consegue progredir com segurança, reduzindo o número de servidores que o sistema do cliente precisa ter. O autor ressalta que o trabalho foi de engenharia, sem novos algoritmos.
Arquitetura: células, réplicas, master com lease e interface de arquivos
Uma instância do Chubby, chamada célula, tem tipicamente cinco servidores réplicas, posicionados de modo a reduzir falhas correlacionadas (por exemplo, em racks diferentes). As réplicas usam um protocolo de consenso para eleger um master, que precisa de votos da maioria e de promessas de que as demais não elegerão outro master durante alguns segundos, o chamado master lease. Esse lease é renovado periodicamente enquanto o master continuar vencendo a votação. Apenas o master inicia leituras e escritas no banco de dados replicado; as outras réplicas só copiam as atualizações. Uma escrita é confirmada quando atinge a maioria das réplicas, enquanto leituras são atendidas só pelo master, o que é seguro porque, enquanto o lease não expira, nenhum outro master pode existir. Os clientes localizam o master consultando as réplicas listadas no DNS. Se o master falha, as outras réplicas rodam a eleição quando o lease dele expira; o paper cita eleições recentes de 6 s e 4 s, com valores de até 30 s. Os clientes enxergam uma árvore de arquivos e diretórios com nomes como /ls/foo/wombat/pouch, em que ls significa lock service. Cada arquivo guarda bytes não interpretados, lidos e escritos de forma atômica e por inteiro, e os nós podem ser permanentes ou efêmeros; estes são apagados quando nenhum cliente os mantém abertos.
Locks consultivos, sequencers e lock-delay
Cada arquivo ou diretório do Chubby pode atuar como lock de leitor e escritor: ou um único handle o segura em modo exclusivo, ou vários o seguram em modo compartilhado. Os locks são consultivos (advisory): conflitam apenas com outras tentativas de adquirir o mesmo lock, e segurar o lock F não é necessário para acessar o arquivo F nem impede que outros o acessem. O autor rejeitou locks obrigatórios por três razões principais: eles protegem recursos implementados por outros serviços, o que exigiria modificá-los; não se queria obrigar o encerramento de aplicações para depuração ou administração; e os desenvolvedores já verificam erros com asserções do tipo o lock X está seguro. O problema difícil é que mensagens atrasadas ou fora de ordem podem fazer um processo que já perdeu o lock agir indevidamente. Como a solução de números de sequência em todo o sistema é cara, o Chubby oferece o sequencer: uma cadeia opaca de bytes que descreve o estado do lock logo após a aquisição, com nome do lock, modo e número de geração. O cliente o repassa aos servidores, que verificam se ainda é válido. Para servidores que não suportam sequencers há um mecanismo imperfeito, o lock-delay: se o lock é liberado porque o dono falhou ou ficou inacessível, o servidor impede outros de pegá-lo por um período, limitado a, no máximo, um minuto (valor da época). O limite existe para impedir que um cliente defeituoso deixe um lock, e portanto o recurso que ele protege, indisponível por tempo arbitrariamente longo.
Cache consistente, sessões, KeepAlive e período de graça
Para reduzir o tráfego de leitura, os clientes mantêm um cache write-through em memória de dados e metadados dos arquivos, mantido consistente por invalidações enviadas pelo master. Quando um dado vai mudar, a modificação fica bloqueada enquanto o master envia invalidações a todos os clientes que podem tê-lo em cache; só prossegue depois que cada um confirmou ou deixou seu lease de cache expirar. O protocolo invalida em vez de atualizar, e o autor escolheu essa consistência estrita porque modelos mais fracos seriam mais difíceis para os programadores. A relação entre cliente e célula é uma sessão, mantida por handshakes periódicos chamados KeepAlives. O master bloqueia a chamada KeepAlive até perto de o lease atual expirar e então a responde estendendo o prazo; a extensão padrão é de 12 s. Eventos e invalidações vão junto nas respostas. Se o lease local do cliente expira, a sessão entra em jeopardy: o cliente esvazia e desabilita o cache e espera um período de graça, de 45 s por padrão. Se um KeepAlive tiver sucesso nesse intervalo, o cliente recebe o evento safe e segue; senão, a sessão é considerada expirada. Assim, falhas curtas de master não derrubam sessões, e a aplicação vê no máximo um atraso.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.