Uber Schemaless: datastore sobre MySQL

01 · CONTEXTO

Por que construir um datastore próprio

No início de 2014, o Uber estava ficando sem espaço de banco de dados por causa do crescimento das viagens, e o time concluiu que não conseguia mais armazenar dados de viagem suficientes no Postgres. A missão passou a ser implementar a próxima geração de tecnologia de banco de dados da empresa.

O novo armazenamento de viagens tinha cinco requisitos principais. O primeiro era adicionar capacidade de forma linear com mais servidores, algo que o Postgres do time não oferecia. Os outros eram disponibilidade de escrita, notificação de sistemas dependentes quando os dados mudam, índices secundários e confiança operacional.

O requisito de escrita tinha um precedente: o Uber já usava um buffer em Redis para repetir gravações que falhavam no Postgres. O problema é que, enquanto a viagem estava no Redis, ela não podia ser lida do Postgres e funções como a cobrança eram perdidas. O Schemaless precisava de um mecanismo parecido, favorecendo a disponibilidade de escrita sobre a semântica de ler a própria escrita.

Para o requisito de notificação, o processamento antigo tratava vários componentes da viagem ao mesmo tempo, o que era propenso a erro: se uma etapa falhava, era preciso repetir tudo. O time queria separar esses passos em etapas isoladas, iniciadas por mudanças nos dados.

O time analisou alternativas comuns, como Cassandra, Riak e MongoDB, entre outras, e a decisão final veio da confiança operacional no sistema que guardaria dados críticos de viagem. Nos sistemas comparados pelo time, índices sobre muitos valores ficam lentos porque usam scatter-gather em todos os nós.

O resultado foi um key-value store que guarda JSON sem validação rígida de esquema, daí o nome. Ele combina MySQL particionado só com acréscimo, buffered writes para suportar masters MySQL com falha, triggers para notificação de mudanças e índices globais. O desenho se inspira no FriendFeed e o foco operacional no Pinterest.

02 · MODELO DE DADOS

Células imutáveis em um mapa esparso

O Schemaless é descrito como um mapa hash persistente, esparso, de três dimensões e só com acréscimo, parecido com o Bigtable do Google. A menor entidade é a célula, imutável: depois de escrita, não pode ser sobrescrita nem apagada.

A célula é um blob JSON referenciado por uma row key, um nome de coluna e uma ref key. A row key é um UUID, a coluna é uma string e a ref key é um inteiro. Para atualizar uma célula, grava-se uma nova com ref key maior, e a mais recente é a de maior ref key.

Não há esquema predefinido nem imposto: as linhas não precisam compartilhar nomes de coluna, e esses nomes são definidos inteiramente pela aplicação. Tipicamente, a aplicação agrupa dados relacionados na mesma coluna, o que reúne dados que mudam juntos e permite mudar o esquema no lado dela sem parada no banco.

No serviço Mezzanine, que guarda as viagens, cada coluna tem um papel. A BASE guarda dados básicos, como o UUID do motorista e a hora do dia. A STATUS guarda o estado de pagamento, com uma célula para cada tentativa de cobrança. A NOTES guarda anotações do motorista ou de um funcionário de operações, e a FARE ADJUSTMENTS guarda células quando a tarifa é ajustada. A divisão em colunas evita corridas de dados e reduz o volume escrito nas atualizações.

03 · ARQUITETURA

Workers, storage nodes e shards

O Schemaless tem dois tipos de nó: workers e storage nodes. Os clientes falam com os workers por endpoints HTTP, e os workers roteiam os pedidos aos storage nodes, agregam os resultados e cuidam de jobs em segundo plano. Os dois tipos são separados para escalar cada parte de forma independente.

Os dados são divididos em um número fixo de shards, tipicamente 4096, mapeados para storage nodes. Uma célula vai para um shard pela row key. Os storage nodes de um shard formam um cluster com um master e dois minions, e os minions ficam distribuídos por vários datacenters, para redundância em caso de queda catastrófica de um datacenter.

1. O serviço cliente envia o pedido por HTTP a um worker, que o roteia aos storage nodes.

2. O worker usa a row key para achar o shard da célula e envia a escrita ao master do cluster.

3. Depois de atualizar o master, o storage node replica a mudança de forma assíncrona para os minions.

4. Na leitura, o padrão é o master, e assim o cliente vê o resultado da própria escrita; ler de um minion é opção por requisição.

Em entrevista, vale dizer qual origem de leitura você usaria em cada caso e qual consistência isso entrega ao cliente.

04 · FALHAS

Leituras, escritas e buffered writes

Quando um worker é lento ou falha, uma biblioteca no cliente tenta outros hosts e repete os pedidos. Isso é seguro porque as escritas no Schemaless são idempotentes, e todo pedido pode ser repetido.

Na leitura, o cluster atende pedidos enquanto um nó estiver disponível. Com o master disponível, o Schemaless sempre devolve o dado mais recente. Sem ele, parte dos dados pode não ter chegado ao minion e o resultado pode estar defasado, embora em produção a latência de replicação costume ser inferior a um segundo. Os workers usam circuit breaker nas conexões com os storage nodes para detectar um nó com problema, e a leitura faz failover para outro nó.

Na escrita, a queda de um minion não afeta nada, porque as escritas vão para o master. Se o master está fora, o Schemaless ainda aceita a escrita e a persiste em disco em outro master escolhido ao acaso, o que é parecido com o hinted handoff de Dynamo e Cassandra. O custo é que leituras seguintes não enxergam essas escritas antes de o master voltar ou de um minion ser promovido.

Ter um único master por shard tem vantagens e desvantagens. A vantagem é a ordem total das escritas em cada shard, importante para os triggers, que podem ler os dados de um shard de qualquer nó e manter a mesma ordem de processamento. A desvantagem é que, com o master fora, as escritas vão para outro lugar onde não podem ser lidas; em compensação, o Schemaless avisa o cliente de que a célula não está imediatamente disponível para leitura.

Há ainda o risco da replicação assíncrona do MySQL: a escrita se perde se o master a persiste e falha antes de replicar para os minions. Buffered writes reduzem essa chance ao escrever o dado em mais de um cluster. O worker grava a requisição em dois clusters, primeiro o secundário e depois o primário, e o cliente só é avisado do sucesso se as duas gravações tiverem sucesso.

1. O worker recebe a escrita e a grava primeiro no cluster secundário e depois no primário.

2. O master secundário é escolhido ao acaso e a escrita vai para uma tabela de buffer especial.

3. O master primário persiste a célula, e o cliente só é avisado do sucesso se as duas gravações tiverem sucesso.

4. Se o master primário cair antes de a replicação alcançar os minions, o master secundário serve de backup temporário do dado.

5. Um job em segundo plano monitora os minions primários e só apaga a célula da tabela de buffer quando ela aparece lá.

Com o cluster secundário, todo dado fica escrito em pelo menos dois hosts, e o número de masters secundários é configurável. Buffered writes usam idempotência: se já existe uma célula com a mesma row key, coluna e ref key, a escrita é rejeitada. Se várias escritas iguais forem bufferizadas, só uma tem sucesso e as demais são rejeitadas quando o cluster primário volta.

05 · ARMAZENAMENTO

MySQL como motor de cada shard

O Schemaless é uma camada relativamente fina sobre o MySQL, que roteia os pedidos ao banco certo. Os índices do MySQL e o cache do InnoDB dão desempenho rápido de consulta para células e índices secundários.

Cada shard é um banco MySQL separado. Cada banco tem uma tabela para as células, a entity table, e uma tabela para cada índice secundário, além de tabelas auxiliares.

A entity table tem uma coluna added_id, um inteiro auto-incremento que é a chave primária. Com ela como chave primária, o MySQL grava as células de forma linear no disco, e os triggers a usam como ponteiro único para extrair células na ordem de inserção. Um índice composto sobre row key, coluna e ref key permite achar células com eficiência.

O corpo da célula é o objeto JSON guardado como um blob MySQL comprimido. Depois de experimentar várias codificações e algoritmos de compressão, o time ficou com MessagePack e ZLib pela velocidade e pelo tamanho da compressão.

06 · TRIGGERS E ÍNDICES

Do log de mudanças ao índice por shard

Como as células são imutáveis e novas versões são acrescentadas, cada célula representa uma mudança, e os valores de uma instância formam um log de mudanças. É possível escutar essas mudanças e disparar funções a partir delas, como num barramento de eventos do tipo Kafka. Esse recurso são os triggers.

O exemplo do Uber é a cobrança: um trigger dispara quando a coluna BASE é escrita na instância Mezzanine.

1. Quando a viagem termina, a coluna BASE é escrita na instância de viagens.

2. O serviço de cobrança, que dispara na coluna BASE, pega a célula e tenta cobrar a viagem no cartão.

3. O resultado da cobrança, sucesso ou falha, é gravado de volta na coluna STATUS.

4. Assim a cobrança fica desacoplada da criação da viagem, e o Schemaless atua como barramento de eventos assíncrono.

Os índices são definidos sobre campos dos blobs JSON. A consulta é eficiente porque só precisa ir a um único shard, e o Schemaless permite desnormalizar dados da célula direto no índice, trocando armazenamento por consulta rápida. No Mezzanine, um índice secundário permite achar as viagens de um motorista, com a hora de criação e a cidade desnormalizadas.

O único requisito de um índice é ter um campo designado como shard field, que determina em qual shard a entrada é escrita ou lida e que precisa ser informado ao consultar. No momento do artigo, esse campo precisava ser imutável. Ele deve ter boa distribuição.

Os índices são eventualmente consistentes: a atualização do índice não ocorre na mesma transação da escrita da célula, e célula e entradas de índice normalmente não ficam no mesmo shard. Índices consistentes exigiriam 2PC nas escritas, com sobrecarga significativa. Evita-se esse custo, mas usuários podem ver dados defasados, embora na maior parte do tempo a defasagem fique bem abaixo de 20ms.