Compromissos de consistência no projeto de sistemas de banco de dados distribuídos modernos: o CAP é apenas parte da história
Título original: Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story
PublicadoComputer
Saiu em uma revista, congresso ou livro, que normalmente avaliam o trabalho antes de aceitar. Mesmo assim, um único estudo nunca é a palavra final.
Resumo
O impacto do teorema CAP no projeto de sistemas de banco de dados distribuídos modernos é mais limitado do que se costuma perceber. Outro compromisso, entre consistência e latência, teve influência mais direta sobre vários DDBSs conhecidos. Uma nova formulação proposta, o PACELC, unifica esse compromisso com o CAP.
Tradução nossa do resumo original dos autores, em inglês.
Análise de pesquisa
Escrita pelo Kurz, não pelos autores do paper. O resumo acima é dos próprios autores.
- Última revisão
- Versão
- 1.0
Visão geral
Daniel J. Abadi (Universidade de Yale) publicou este texto na IEEE Computer, volume 45, número 2, em fevereiro de 2012, páginas 37 a 42, como artigo de capa. É um texto curto para profissionais, não um artigo de pesquisa: não traz experimentos próprios e se apoia em dois estudos de outros autores. O cenário é a década seguinte à prova da conjectura de Brewer, quando sistemas como o Dynamo e o Cassandra abriam mão da consistência por padrão e o CAP era a explicação habitual.
Abadi diz que a explicação está errada ou, no mínimo, incompleta. A consistência de que ele trata é a atômica, ou linearizável, usada por Gilbert e Lynch na prova (veja Linearizability). Entradas relacionadas do catálogo: Eventually Consistent, pelos parâmetros N, W e R de quórum em que o artigo se apoia, e o Bigtable, que o artigo lista junto com o HBase.
Vale saber antes: o que é uma partição de rede, o significado de consistência, disponibilidade e tolerância a partições no CAP, e leituras e escritas por quórum com R + W > N.
Contribuição
- Uma leitura do CAP. O CAP impõe limitações apenas diante de certos tipos de falha. Não é a tolerância a partições sozinha, e sim ela combinada com uma partição real que força a escolha entre disponibilidade e consistência. No caso-base, o CAP permite o conjunto completo de garantias ACID junto com alta disponibilidade.
- Um segundo compromisso, sempre presente. Todo sistema que replica dados (o que a alta disponibilidade exige) precisa trocar consistência por latência, com ou sem partições. O artigo trata disponibilidade e latência como, em boa medida, a mesma coisa: um sistema indisponível tem, na prática, latência extremamente alta.
- PACELC. Se há partição (P), como o sistema troca disponibilidade por consistência (A e C); senão (E), na operação normal sem partições, como troca latência por consistência (L e C).
- Uma classificação. O artigo rotula sistemas conhecidos com o código de quatro letras e argumenta, a partir do PNUTS, que a escolha de reduzir consistência no caso-base não se deve ao CAP.
Metodologia
Não há medição. O método é um argumento por enumeração. O artigo primeiro lista os contextos em que os sistemas foram construídos (o carrinho de compras da Amazon para o Dynamo, a busca na caixa de entrada do Facebook para o Cassandra, os recursos com muita escrita do LinkedIn para o Voldemort, os dados de cada visualização de página do Yahoo para o PNUTS, usos parecidos com os da Amazon para o Riak) e cita um estudo do Google segundo o qual 100 ms a mais podem reduzir drasticamente a probabilidade de o cliente continuar interagindo ou voltar. Depois afirma que há só três jeitos de replicar: enviar as atualizações a todas as réplicas ao mesmo tempo, a um nó mestre combinado primeiro, ou a um nó arbitrário primeiro. Cada um é cruzado com replicação síncrona, assíncrona ou mista e com o ponto onde as leituras são servidas, e para cada combinação o artigo nomeia o custo de latência ou a perda de consistência. Dois estudos externos, sobre o Cassandra e sobre o SimpleDB, servem de evidência. Os sistemas são então colocados no PACELC a partir do projeto padrão, e o artigo diz que seu foco é o projeto original, não os ajustes que se tornaram possíveis depois das primeiras versões.
Resultados
- Por que consistência custa latência. Enviar a todas as réplicas ao mesmo tempo exige um protocolo de acordo ou uma camada de pré-processamento para evitar divergência, e ambos somam latência. Um nó mestre com replicação síncrona espera pela réplica mais lenta, principalmente numa WAN. Com replicação assíncrona, ler só do mestre mantém a consistência, mas perde a réplica próxima e o balanceamento de carga, enquanto ler de qualquer nó é rápido, mas pode devolver versões diferentes. Enviar a atualização a um nó arbitrário primeiro soma o custo de resolver atualizações simultâneas do mesmo item. Com quórum, R + W > N mantém a consistência e R + W <= N permite leituras inconsistentes.
- Evidência de terceiros. Rao, Shekita e Tata constataram no Cassandra que leituras por quórum e leituras fracas podem diferir em latência por um fator de quatro ou mais. Wada e colegas não encontraram aumento significativo de latência nas leituras consistentes do SimpleDB, mas só dentro de uma região, e o artigo suspeita de replicação mestre-escravo a curta distância.
- O PNUTS como caso mais claro. Ele atribui um mestre a cada item, replica de forma assíncrona numa WAN e serve leituras de qualquer réplica, ou seja, a opção (2)(b)(ii). Numa partição que isola o mestre, o padrão é tornar o item indisponível para atualizações, então por padrão ele é CP.
- Posição no PACELC.
| Sistema | Classe |
|---|---|
| Dynamo, Cassandra, Riak | PA/EL |
| VoltDB/H-Store, Megastore | PC/EC |
| BigTable, HBase | PC/EC |
| MongoDB | PA/EC |
| PNUTS | PC/EL |
Dynamo, Cassandra e Riak usam uma combinação das opções (2)(c) e (3) e, segundo o artigo, passam mais plenamente à (3) durante uma partição, com código de reconciliação. Voldemort e SimpleDB são discutidos, mas não recebem classe na seção do PACELC. PC/EL não significa totalmente consistente: PC quer dizer que o sistema não reduz a consistência além do nível-base durante uma partição.
Análise crítica
- Opinião, não evidência. O artigo não apresenta medição própria. Seu principal apoio empírico são dois estudos de terceiros, que segundo ele parecem se contradizer até que se considere o cenário do SimpleDB. Que o compromisso consistência/latência seja discutivelmente mais influente que o CAP é a leitura do autor, assim como a ideia de que sistemas no estilo Dynamo reaproveitaram o código de tratamento de partições para a escolha do caso-base.
- A classificação é interpretação. Os rótulos vêm da configuração padrão da época, e o texto observa que a consistência de alguns sistemas se tornou ajustável depois das primeiras versões. Não verifiquei como esses produtos se comportam hoje, então a tabela deve ser lida como retrato de 2012. O próprio artigo chama o PC/EL de confuso e classifica o MongoDB como PA/EC ao notar que, tecnicamente, ele não é disponível pela definição do CAP.
- O que não é afirmado. O artigo não diz que o CAP está errado, que partições nunca importam, nem que a latência é o único motivo para relaxar a consistência. Também não dá números para o custo ou a frequência das partições, só diz que são "um tanto raras" e muitas vezes menos frequentes que outras falhas, citando um post de blog.
- Sistemas posteriores no catálogo (comparação feita aqui, não no artigo). Highly Available Transactions (2013) mede a diferença de latência entre projetos sem coordenação e com coordenação, e o COPS (2011) busca consistência causal com baixa latência. O Spanner (2012) surgiu depois deste artigo e não é classificado nele.
Literatura posterior, que não faz parte do artigo. O texto de Brewer "CAP twelve years later: How the rules have changed" aparece no Crossref na mesma edição da Computer (volume 45, número 2, páginas 23 a 29, DOI 10.1109/mc.2012.37). Li apenas esses metadados, não o texto, e não sei o que ele diz sobre o PACELC.
Pesquisas futuras
- Medir o compromisso consistência/latência entre regiões para o mesmo sistema e a mesma carga, o que o artigo só defende a partir de dois estudos.
- Quantificar quão raras são as partições em diferentes implantações, já que a premissa do artigo se apoia numa afirmação geral.
- Classificar os sistemas pelas opções de configuração atuais, não só pelo projeto original.
- Relacionar o PACELC a modelos de consistência mais fracos que dispensam coordenação síncrona, como a consistência causal.
Texto completo
Discussão · 0
Entre para participar da discussãoNenhum post ainda. Seja o primeiro a iniciar a discussão.