Amazon Dynamo – Parte I

Amazon-DynamoDB

Vamos iniciar com este post uma sequência sobre NoSql, inicialmente querendo cobrir Dynamo, MongoDB, Cassandra e Neo4j.

Sobre o Dynamo

O Dynamo é um banco NoSql do tipo key-value store eventualmente consistente, criado para atender a necessidades de vários produtos da Amazon. Sua proposta é ser um repositório altamente disponível, especialmente para escrita. Para atingir tamanha disponibilidade, ele sacrifica um pouco de consistência em cenários de falha. Ele faz uso extensivo de versionamento de objetos e resolução de conflitos do lado da aplicação para oferecer uma interface simples e altamente disponível.

É bem interessante conhecer o Dynamo e sua arquitetura, pois ele foi um dos primeiros bancos NoSql e serviu de inspiração para muitos outros. Este post teve como ponto de partida um paper sobre o Dynamo que foi recomendado pelo NoSql Summer Reading List.

Motivação

Os BDs relacionais foram concebidos e desenvolvidos em um contexto no qual as características ACID (Atomicidade, Consistência, Isolamento e Durabilidade) eram muito importantes. Como leitura complementar neste tema, na edição de Novembro/2012 da Communications of the ACM há um artigo interessante de Michael Stonebraker (criador do Postgres e do Ingres) sobre como a web mudou os requisitos de persistência das aplicações, e que o paradigma relacional não é mais adequado para muitos dos cenários atuais.

Uma reflexão interessante da Amazon é que confiabilidade e escalabilidade dependem muito de como o estado das aplicações é gerenciado. Segundo o CAP Theorem, é impossível para um web service oferecer ao mesmo tempo os 3 itens:

    Consistência, Disponibilidade e Tolerância a particionamento.

Os BDs relacionais sempre foram muito focados em consistência, mas com isso fica difícil atingir níveis críticos de disponibilidade quando o volume de dados e acessos cresce muito. Os bancos NoSql abordam essas questões de forma diferente, e cada implementação é mais direcionada para um cenário/problema específico.

Background e premissas

  • Cada serviço que usa o Dynamo mantém suas próprias instâncias do mesmo. Não há compartilhamento de instâncias Dynamo entre diferentes produtos
  • Operações simples de leitura e escrita sobre um item de dados identificado por um ID. Não há definição de schema e nem operações envolvendo múltiplos itens.
  • Dynamo se concentra em aplicações que precisem guardar objetos razoavelmente pequenos (maioria até 1 MB)
  • Foco em prover alta disponibilidade, relaxando requisitos de consistência. Sem garantias de isolamento e permitindo atualizações de uma única chave por vez.
  • Requisitos não-funcionais e SLA buscam atender bem a 99,9% dos acessos, em vez de se concentrar em tempos médios de resposta.
  • O ambiente operacional do Dynamo assume “não-hostilidade”, somente com acessos “confiáveis”. Assim, ele não foi construído com requisitos de segurança como autenticação e autorização.

Considerações de Design

A Amazon possui uma ampla gama de serviços e usa uma infraestrutura bem descentralizada. A idéia é definir bem as responsabilidades de cada serviço e permitir que cada um escale horizontalmente com facilidade. Além disso, a infraestrutura lida bem com falhas em componentes individuais, pois isto sempre vai ocorrer.

Para que esta topologia funcione bem na prática, é fundamental manter as latências e tempos de resposta baixos, e definir SLAs para cada um. Assim é possível atingir tempos de resposta mais previsíveis e maior disponibilidade. Problemas de rede são muito comuns, e indisponibilidade não quer dizer que o serviço em questão está offline, mas quer dizer que não respondeu abaixo de X ms.

Outras considerações importantes são:

  • Foco em sempre aceitar escritas, como por exemplo adição de produtos ao carrinho. Complexidade da resolução de conflitos fica para a a leitura, para permitir que nunca sejam perdidas escritas.
  • Escalabilidade incremental: deve ser sempre possível adicionar ou remover nós, com mínimo impacto sobre os operadores e sobre o sistema como um todo.
  • Simetria: cada nó deve ter as mesmas responsabilidades que seus companheiros, para facilitar a administração e manutenção.
  • Descentralização: uso de técnicas peer-to-peer descentralizadas em vez de controle centralizado. Isso facilita o tratamento de falhas em nós individuais e aumenta a disponibilidade.
  • Heterogeneidade: devem ser suportados nós com capacidades diferentes, com distribuição de carga de acordo com a capacidade de cada nó. Isto permite a introdução de novos nós com capacidades diferentes sem ter que modificar todos os nós de uma vez.

Técnicas utilizadas no Dynamo e suas vantagens

Técnicas Dynamo

O detalhe destas técnicas extrapola o escopo deste post, mas recomendo muito ler as referências que descrevem as técnicas. Há muitas idéias interessantes de engenharia.

Uma observação importante que quero fazer é que a maioria das soluções de detecção e tratamento de falhas em nós, descoberta de novos membros, particionamento e outras técnicas foram inspiradas em soluções criadas em redes peer-to-peer, como a Gnutella e Freenet.

Antigamente estas redes eram vistas de forma negativa e amadora, mas elas trouxeram muitas soluções de engenharia interessantes, e mais inovação do que a maioria dos fornecedores de software proprietários. Muitas inspirações técnicas vieram também de projetos open source, como o Coda, Bayou e Chord.

Arquitetura

  • Interface do sistema: o Dynamo expõe duas operações – get() e put(). A operação put() determina a partir da chave do objeto onde as réplicas devem ser salvas, e grava as réplicas em disco. A operação get() retorna um objeto ou uma lista de objetos com versões conflitantes. Como mencionamos previamente, o Dynamo deixa a resolução de conflitos para a aplicação cliente.
  • Particionamento: os nós do Dynamo se distribuem em um espaço circular, ou anel. Cada nó no sistema recebe um valor aleatório que determina a sua posição no anel. Cada novo objeto é associado a um nó pela aplicação de um hash ao seu ID, e aí percorremos o anel em sentido horário até chegar no primeiro nó com posição maior que a do objeto em questão. Para lidar melhor com as falhas em nós, o Dynamo atribui múltiplas posições para cada nó, em um conceito chamado de “nós virtuais”. Com essa abordagem o Dynamo consegue redistribuir bem os nós quando algum deles falha e a disponibilidade não fica comprometida.

node ring

Estrutura de nós do Dynamo em anel

  • Replicação: para atingir alta disponibilidade e durabilidade, o Dynamo replica os dados em múltiplos nós. Cada item é replicado em N itens, sendo que este valor N é configurável. Além do nó original, o item é gravado nos N-1 nós seguintes, em sentido horário. A lista de nós responsáveis por guardar cada chave é chamada de lista de preferência, e possui mais de N nós, para conseguir lidar com falhas em nós individuais.
  • Versionamento: o Dynamo oferece consistência eventual, na qual as atualizações são propagadas para as réplicas assincronamente. Normalmente há um limite no tempo para as atualizações chegarem às réplicas, mas em cenários de falha este tempo pode ser muito longo. Quando um cliente envia uma atualização de um item, ele especifica qual é a versão que ele está atualizando. Em cenários de falha pode ser necessário fazer um merge de versões conflitantes. Entretanto, isto é feito em tempo de leitura, pois o Dynamo se propõe a sempre aceitar escritas, como mencionamos anteriormente.
  • Execução de operações get() e put(): estas são invocadas usando um framework específico da Amazon, que encapsula HTTP. Há uma lógica de roteamento que considera a distribuição da carga e também a saúde atual dos nós, e aí as requisições são encaminhadas para o nó adequado.
  • Tratamento de falhas – Hinted handoff: o Dynamo tem um mecanismo para que operações de leitura e escrita envolvam N nós saudáveis. É feito um controle de nós saudáveis ao longo do tempo, e com isso o sistema se protege de eventuais falhas de rede e em nós individuais.
  • Tratamento de falhas permanentes – sincronização de réplicas: o Dynamo estrutura a distribuição de itens usando árvores Merkle, pois elas ajudam identificar rapidamente as inconsistências e a minimizar o volume de transferência de dados entre réplicas.
  • Detecção de novos nós e de falhas: o Dynamo usa um protocolo baseado em redes peer-to-peer para que os nós percebam rapidamente as falhas de nós existentes e a entrada de novos nós no anel.
  • Adicionando e removendo nós: o Dynamo possui um mecanismo eficiente que reposiciona os nós no anel quando um novo nó entra, considerando a latência entre os nós para que as comunicações fiquem bastante eficientes.

Com isto finalizamos esta primeira parte, na qual apresentamos muitos aspectos teóricos e de arquitetura do Dynamo, mostrando os cenários em que ele se aplica bem e como ele trata de vários problemas recorrentes de uma implementação deste gênero.

Teremos em breve uma parte 2 bem mais prática, colocando o Dynamo em uso e explicitando uma série de detalhes importantes para utilizá-lo bem em Produção.

21