Key-value store distribuído

01 · CONTEXTO

O que um key-value store distribuído precisa decidir

Um key-value store guarda pares chave-valor e responde a duas operações: gravar e ler por chave. Em entrevista, o ponto de partida é levantar requisitos: quanto dado cabe em uma máquina só, quão disponível o serviço precisa ser, e o que é pior para o produto, devolver um valor desatualizado ou recusar a operação? Essa última pergunta define o desenho inteiro.

É a escolha do teorema CAP. Um store orientado a consistência (CP) abre mão de disponibilidade durante uma partição de rede; um store orientado a disponibilidade (AP) abre mão de consistência e continua atendendo, mesmo que isso devolva dados antigos.

O caso estudado aqui segue a linha de sistemas como Dynamo e Cassandra, que adotam consistência eventual: a consistência forte exigiria bloquear novas operações até que todas as réplicas concordem, o que não combina com alta disponibilidade. O desenho é descentralizado, sem ponto único de falha, porque todo nó tem as mesmas responsabilidades.

1. O cliente fala com um coordenador, que atua como intermediário entre ele e os nós de armazenamento.

2. Os nós de armazenamento são pares: nenhum é líder, todos têm as mesmas responsabilidades, então não há um nó único cuja queda derrube o serviço.

02 · DADOS

Particionar e replicar

Um conjunto de dados que não cabe em uma máquina é dividido em partições espalhadas por vários servidores, no espírito do sharding. Há dois desafios: distribuir os dados de modo uniforme e movimentar o mínimo possível quando nós entram ou saem. O hashing consistente é a técnica apontada para os dois. Aqui ele aparece como anel: servidores e chaves são mapeados para posições no mesmo anel, e cada chave pertence ao servidor que encontra ao percorrê-lo.

Para ter alta disponibilidade, cada dado é replicado de forma assíncrona em N servidores, sendo N um parâmetro configurável. Depois que a chave é mapeada para uma posição do anel, caminha-se no sentido horário a partir dela e escolhem-se os primeiros N servidores para guardar as cópias. A replicação traz o problema oposto: as cópias podem divergir, e o restante do desenho existe para administrar isso.

1. O coordenador mapeia a chave para uma posição do anel e identifica o servidor responsável por ela.

2. Caminhando no sentido horário a partir da posição da chave, o coordenador escolhe os primeiros servidores do anel como réplicas; o quarto nó fica fora deste conjunto.

03 · QUÓRUM

Quórum de leitura e escrita

Réplicas permitem escolher quantas delas precisam responder. Com N réplicas, W é o quórum de escrita e R o de leitura: a escrita só é dada como bem-sucedida após W confirmações, e a leitura espera R respostas. Se W somado a R for maior que N, a consistência forte fica garantida, porque sempre existe ao menos um nó em comum entre quem recebeu a escrita e quem responde à leitura, e esse nó tem o dado mais recente. Isso se conecta ao que padrões de consistência e consenso discutem em geral.

A configuração é uma troca entre latência e consistência. Exigir apenas uma resposta na leitura, com a escrita confirmada por todas as réplicas, otimiza a leitura; o inverso otimiza a escrita. Com quórum pequeno a operação retorna rápido, pois o coordenador não espera pela réplica mais lenta, mas a consistência forte deixa de ser garantida quando a soma dos quóruns não passa de N.

04 · CONFLITOS

Versões e vector clocks

Replicar dá disponibilidade, mas causa inconsistência entre réplicas: duas escritas concorrentes podem chegar a nós diferentes e produzir valores em conflito. A solução é tratar cada modificação como uma nova versão imutável do dado e usar um mecanismo capaz de detectar e reconciliar conflitos. O vector clock é a técnica comum: um par servidor-versão associado ao dado, que permite verificar se uma versão precede, sucede ou está em conflito com outra.

05 · FALHAS

Detectar e tolerar falhas

Para saber quem caiu sem depender de um nó central, cada servidor mantém uma lista de membros com contadores de heartbeat e os incrementa periodicamente. Periodicamente também envia seus heartbeats a um conjunto de nós aleatórios, que repassam a outros: é o protocolo de gossip. Se o contador de um membro não aumenta durante um período predefinido, ele é considerado fora do ar.

Detectada a falha, o sistema precisa continuar disponível, o que conversa com os padrões de disponibilidade. No quórum relaxado (sloppy quorum), em vez de exigir as réplicas originais, o sistema usa os primeiros servidores saudáveis do anel e ignora os que estão fora do ar. Outro servidor atende temporariamente pelo que caiu e, quando este volta, as mudanças são devolvidas a ele: é o hinted handoff.

O hinted handoff cobre falhas temporárias. Para uma réplica indisponível de forma permanente, aplica-se um protocolo de anti-entropia que compara os dados das réplicas e atualiza cada uma para a versão mais nova. Uma árvore de Merkle serve para detectar a inconsistência e reduzir o volume de dados transferidos.

1. Um dos nós réplica para de enviar heartbeats; os outros, trocando listas de membros por gossip, passam a considerá-lo fora do ar.

2. O coordenador ignora o nó caído e usa o próximo servidor saudável do anel, que atende temporariamente no lugar dele.

3. Quando o nó volta, o substituto devolve a ele as mudanças que recebeu enquanto ele estava fora.

4. Para uma falha permanente, as réplicas restantes comparam seus dados por árvores de Merkle e sincronizam apenas as partes que divergem.

06 · NÓ

Caminhos de escrita e de leitura dentro de um nó

Dentro de cada nó, o desenho de escrita segue a arquitetura do Cassandra. A requisição é primeiro persistida em um arquivo de commit log; em seguida o dado vai para um cache em memória (veja fundamentos de cache); quando esse cache enche ou atinge um limite predefinido, o dado é descarregado em um SSTable no disco.

Na leitura, o nó consulta primeiro a memória. Se o dado não estiver lá, ele é buscado no disco, e é preciso uma forma eficiente de descobrir qual SSTable contém a chave. O Bloom filter é usado comumente para isso, evitando abrir arquivos que certamente não têm o dado. A escolha do motor de armazenamento é parte de seleção de banco de dados.

1. Na escrita, o nó registra a requisição no commit log e grava o dado no cache em memória.

2. Quando o cache em memória enche ou chega a um limite, o conteúdo é descarregado em arquivos ordenados no disco.

3. Na leitura, o nó olha primeiro a memória; se o dado estiver lá, a resposta sai sem tocar o disco.

4. Sem o dado na memória, o nó vai ao disco e usa um filtro para descobrir quais arquivos podem conter a chave.