Assine a nossa newsletter | Receba insights sobre Transformação Digital

Problema dos dois generais e chave de idempotência

Kubernetes

Imagine-se fazendo uma compra em alguma loja virtual. Ao finalizar, a página de pagamento informa que ocorreu um erro durante o processo.

Você, desconfiado, verifica no aplicativo correspondente ao cartão utilizado se houve alguma cobrança, e de fato houve.

O dinheiro foi transferido para a loja, porém a confirmação que o servidor recebeu a transação corretamente não foi recebida.

Você espera para ter certeza de que na realidade não ocorreu erro no pedido e, após alguns minutos, recebe a informação que o pagamento foi registrado e o pedido está a caminho.

User's Computer X Application's Server

Esta situação, apesar de hipotética, é muito comum e provavelmente já aconteceu com qualquer um de nós — um erro na confirmação de recebimento de dados. Isso pode ocorrer em diversas ocasiões em que há a comunicação entre dois computadores enviando dados. A pergunta que cabe agora é: como resolver este problema?

Para responder, vou antes apresentar um problema clássico da Ciência da Computação chamado “Problema dos Dois Generais” (ou “Two General’s Problem”).

Problema dos dois generais

O problema consiste em dois exércitos, cada um liderado por um general, e um castelo. Os generais querem atacar o castelo, mas, para conseguirem destruí-lo, ambos os exércitos devem atacar ao mesmo momento.

Se apenas um deles atacar, a defesa do castelo será mais forte e o exército será derrotado. Os generais devem mandar mensageiros para definirem uma hora exata de ataque.

Contudo, os mensageiros passam por uma rota perigosa próxima ao castelo, e podem ser impedidos de entregar a mensagem.

Como um general pode ter certeza de que o outro recebeu a mensagem e que estejam de acordo com um horário de ataque?

Problema dos dois generais

Para fins de organização, sejam os generais A e B. O general A pode começar enviando uma mensagem “Ataque às 09:00 em 30 de agosto”.

No entanto, uma vez enviada, o general A não tem ideia se o mensageiro passou. Essa incerteza pode levar o general A a hesitar em atacar devido ao risco de ir sem a ajuda do outro exército.

Assim, o general B pode enviar uma confirmação de volta para o outro: “Recebi sua mensagem e atacarei às 09:00 em 30 de agosto”. Neste caso o mensageiro que carrega a confirmação pode ser capturado e o general B pode hesitar, sabendo que o A não irá sem a confirmação.

Novas confirmações podem parecer uma solução — deixe o general A enviar uma segunda confirmação: “Recebi sua confirmação do ataque planejado às 09:00 em 30 de agosto”. No entanto, este novo mensageiro do general A também pode ser capturado.

Assim, torna-se rapidamente evidente que não importa quantas rodadas de confirmação sejam feitas, não há como garantir a exigência de que cada general tenha certeza de que o outro concordou com o plano de ataque.

Este problema, por incrível que pareça, não tem solução. É impossível fazer com que os dois generais estejam de acordo com um horário sob as circunstâncias dadas.

O “Problema dos Dois Generais”, juntamente com a prova da não existência de uma solução, foi primeiro apresentado por E. A. Akkoyunlu, K. Ekanadham, e R. V. Huber em 1975² e é fundamental no estudo de redes.

Em computação, este problema se traduz em um cliente enviando dados à um servidor, que por sua vez manda de volta uma confirmação. Os dois nunca conseguem ter certeza de que o envio dos dados e a confirmação de recebimento ocorreu.

É claro que, na prática, uma solução é enviar os dados e a confirmação muitas vezes, mitigando a incerteza ao máximo.

Surge, assim, outro problema: imagine-se na situação apresentada inicialmente, e que você ou o aplicativo mande mais de uma vez os dados da compra para ter certeza de que o pedido foi registrado.

Nesta situação, se o servidor não estiver preparado, poderão ser registrados pedidos idênticos, além da possibilidade de ter seu dinheiro debitado mais de uma vez. Como fazer para solucionar este outro problema e a situação de uma vez por todas?

Problema Server

A seguir, vou introduzir o conceito de idempotência e depois explicar o que é uma chave de idempotência — o segredo para responder à pergunta acima.

Idempotência e sua chave

Idempotência é a propriedade que algumas operações têm de poderem ser aplicadas várias vezes sem que o valor do resultado se altere após a primeira aplicação. Alguns exemplos de operações idempotentes são:

  • Chamar o elevador: não importa quantas vezes se aperta o botão, o elevador sempre levará um tempo constante para chegar ao andar destino;
  • Arredondar um número real qualquer para o inteiro mais próximo: o resultado de arredondar 4.9 para o inteiro mais próximo é 5. O resultado de arredondar 5 para o inteiro mais próximo também é, trivialmente, 5.

Agora que sabemos o que é idempotência, é fácil perceber que a operação de enviar os dados da compra para um servidor não é, a priori, idempotente.

Enviar mais de uma vez os dados pode implicar em mais de uma debitação na conta do cliente e mais de uma compra registrada nos sistemas da loja. Sendo assim, se for possível tornar tal operação idempotente, o problema será resolvido.

Dessa motivação é que surge a Chave de Idempotência, entidade que consegue tornar requisições em idempotentes.

Uma Chave de Idempotência é um valor único gerado pelo cliente que o servidor usa para distinguir envios. Se dois conjuntos de dados tem o mesmo valor de idempotency-key, isso quer dizer que na verdade estamos tratando de dados iguais, porém enviados mais de uma vez.

Dito isso, é importante perceber que, da mesma maneira que dados iguais têm o mesmo valor da chave, se tivermos duas chaves iguais, os dados dos envios devem ser suficientemente iguais para garantir consistência.

Aplique isso, por exemplo, em uma operação de compra online. Se um cliente fizer duas requisições de um mesmo produto, utilizando o mesmo cartão e com pouco tempo de diferença entre tais requisições, muito provavelmente estamos tratando de um mesmo pedido que, por algum motivo, ocorreu duas vezes.

O servidor irá verificar se as chaves de idempotência de cada uma das requisições são iguais e processar apenas uma.

Semanticamente todo esse processo se traduz em “se você receber uma requisição com essa chave de mim, considere a mesma que qualquer outra requisição minha também com essa chave”.

A aplicação destes conceitos é em APIs, presente na maioria das comunicações envolvendo mais de uma máquina. Para garantir idempotência de uma HTTP API por exemplo, pode ser utilizada a chave de idempotência em requests não idempotentes como HTTP POST ou PATCH requests (outros como GET, READ, PUT e DELETE já são idempotentes).

Este texto foi motivado por um vídeo disponível no YouTube chamado “The Two General’s Problem” de Tom Scott¹. Se você se interessou pelo assunto, não hesite em assisti-lo nem em verificar as outras referências.

Referências

https://youtu.be/IP-rGJKSZ3s, acesso em 24/08/2021.

Akkoyunlu, Eralp A., Kattamuri Ekanadham, and Richard V. Huber. “Some constraints and tradeoffs in the design of network communications.” Proceedings of the fifth ACM symposium on Operating systems principles. 1975.

https://en.wikipedia.org/wiki/Two_Generals%27_Problem, acesso em 26/08/2021.