Olá, Habr!
Hoje, trazemos para sua atenção a tradução de um artigo complexo sobre a implementação de bloqueios distribuídos usando Redis e discutiremos a viabilidade do Redis como tópico. A análise do algoritmo Redlock de Martin Kleppmann, autor do livro "", é apresentada .
Os bloqueios distribuídos são um primitivo muito útil, utilizado em muitos ambientes onde diferentes processos precisam trabalhar sobre recursos compartilhados com o princípio de exclusão mútua.
Existem várias bibliotecas e publicações descrevendo como implementar o DLM (gerenciador de bloqueios distribuídos) com Redis, mas cada biblioteca usa sua própria abordagem, e as garantias fornecidas são bastante fracas em comparação ao que é alcançável com um pouco mais de design complexo.
Neste artigo, tentaremos descrever um algoritmo que pode ser considerado canônico, demonstrando como implementar bloqueios distribuídos com Redis. Vamos falar sobre o algoritmo chamado Redlock, que implementa um gerenciador de bloqueios distribuídos e, em nossa opinião, é mais seguro do que a abordagem padrão com uma única instância. Esperamos que a comunidade o analise, forneça feedback e o utilize como ponto de partida para a implementação de projetos mais complexos ou alternativos.
Implementações
Antes de prosseguir com a descrição do algoritmo, fornecemos algumas referências a implementações já prontas. Elas podem ser utilizadas como consulta.
- (implementação para Ruby). Também existe o Redlock-rb, que adiciona um pacote (gem) para facilitar a distribuição, e não apenas isso.
- (implementação para Python).
- (implementação para Asyncio Python).
- (implementação para PHP).
- (outra implementação para PHP)
- (biblioteca PHP para bloqueios)
- (implementação para Go).
- (implementação para Java).
- (implementação para Perl).
- (implementação para C++).
- (implementação para C#/.NET).
- (implementação para C#/.NET). Com suporte a extensões assíncronas e de bloqueio.
- (implementação para C# .NET com armazenamento de dados configurável)
- (implementação para C# .NET)
- (implementação para NodeJS). Inclui suporte para extensão de bloqueios.
Garantias de segurança e disponibilidade
Vamos modelar nosso projeto com apenas três propriedades que, em nossa opinião, oferecem as garantias mínimas necessárias para o uso eficaz de bloqueios distribuídos.
- Propriedade de segurança: Exclusão mútua. Em qualquer momento, apenas um cliente pode manter o bloqueio.
- Propriedade de disponibilidade A: Ausência de bloqueios mútuos. No final das contas, sempre é possível obter um bloqueio, mesmo que o cliente que bloqueou o recurso falhe ou entre em outro segmento do disco.
- Propriedade de disponibilidade B: Tolerância a falhas. Enquanto a maioria dos nós Redis estiver funcionando, os clientes podem adquirir e liberar bloqueios.
Por que as implementações baseadas em recuperação de falhas não são suficientes neste caso
Para entender o que vamos melhorar, vamos analisar a situação atual da maioria das bibliotecas de bloqueios distribuídos baseadas em Redis.
A maneira mais simples de bloquear um recurso usando Redis é criar uma chave na instância. Normalmente, a chave é criada com um tempo de vida limitado, isso é alcançado usando o recurso expires do Redis, portanto, mais cedo ou mais tarde essa chave é liberada (propriedade 2 em nossa lista). Quando um cliente precisa liberar o recurso, ele remove a chave.
À primeira vista, essa solução funciona bem, mas existe um problema: em nossa arquitetura, surge um único ponto de falha. O que acontece se a instância principal do Redis falhar? Então vamos adicionar uma secundária! E a usaremos se a principal estiver indisponível. Infelizmente, essa opção é inviável. Ao fazer isso, não conseguiremos implementar corretamente a propriedade de exclusão mútua, que precisamos garantir a segurança, já que a replicação no Redis é assíncrona.
É evidente que, nesse modelo, surge uma condição de corrida:
- O cliente A adquire o bloqueio na primária.
- A primária falha antes que a gravação na chave seja transferida para a secundária.
- A secundária se torna a primária.
- O cliente B adquire o bloqueio do mesmo recurso que já está bloqueado pelo A. VIOLAÇÃO DE SEGURANÇA!
Às vezes, é totalmente normal que, em circunstâncias especiais, como uma falha, vários clientes possam segurar um bloqueio ao mesmo tempo. Nesses casos, pode-se aplicar uma solução baseada em replicação. Em outros casos, recomendamos a solução descrita neste artigo.
Implementação correta com uma única instância
Antes de tentar superar as desvantagens da configuração com uma única instância, descrita acima, vamos entender como agir corretamente neste caso simples, uma vez que tal solução é realmente aceitável em aplicações onde a condição de corrida é, de tempos em tempos, tolerável, e também porque o bloqueio em uma única instância serve como a base que é utilizada no algoritmo distribuído aqui descrito.
Para adquirir o bloqueio, faremos o seguinte:
SET resource_name my_random_value NX PX 30000
Esse comando configura a chave, apenas se ela ainda não existir (opção NX), com um tempo de vida de 30000 milissegundos (opção PX). Para a chave, é definido o valor “myrandomvalue”. Esse valor deve ser único entre todos os clientes e todas as solicitações de bloqueio.
Basicamente, um valor aleatório é usado para liberar o bloqueio de forma segura, utilizando um script que informa ao Redis: exclua a chave, somente se ela existir, e o valor armazenado nela for exatamente o que se esperava. Isso é alcançado através do seguinte script em Lua:
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
endÉ importante não permitir a liberação do bloqueio feito por outro cliente. Por exemplo, um cliente pode adquirir o bloqueio, depois ficar preso durante alguma operação que dura mais do que a validade do primeiro bloqueio (a ponto de o tempo de vida da chave expirar) e depois liberar um bloqueio que foi definido por outro cliente.
Usar um simples DEL não é seguro, pois o cliente pode excluir um bloqueio definido por outro cliente. Em contraste, ao usar o script acima, cada bloqueio é "assinado" por uma string aleatória, portanto, só o cliente que o definiu anteriormente pode excluí-lo.
Qual deve ser essa string aleatória? Suponho que deva ser 20 bytes de /dev/urandom, mas existem maneiras menos custosas de gerar uma string suficientemente única para os fins que você tem em mente. Por exemplo, é aceitável semear RC4 com /dev/urandom e depois gerar um fluxo pseudoaleatório com base nele. Uma solução mais simples está relacionada a uma combinação do tempo Unix em resolução de microssegundos mais o ID do cliente; não é tão segura, mas provavelmente atende ao nível de exigências na maioria dos contextos.
O tempo que usamos como indicador do tempo de vida da chave é chamado de "tempo de expiração do bloqueio". Este valor representa simultaneamente o período após o qual o bloqueio será liberado automaticamente e o tempo que o cliente tem para realizar a operação antes que outro cliente possa, por sua vez, bloquear esse recurso, sem violar efetivamente as garantias de exclusão mútua. Tal garantia é limitada apenas a uma determinada janela de tempo que começa a contar a partir do momento em que o bloqueio é adquirido.
Assim, discutimos uma boa maneira de adquirir e liberar um bloqueio. O sistema (se estamos falando de um sistema não distribuído, composto por uma única instância sempre disponível) é seguro. Vamos expandir esse conceito para um sistema distribuído, no qual não temos tais garantias.
Algoritmo Redlock
Na versão distribuída do algoritmo, supõe-se que temos N instâncias principais do Redis. Esses nós são totalmente independentes uns dos outros, portanto, não usamos replicação ou qualquer outro sistema de coordenação implícita. Já discutimos como adquirir e liberar um bloqueio de forma segura em uma única instância. Aceitamos como dado que o algoritmo ao trabalhar com uma única instância usará exatamente esse método. Em nossos exemplos, definimos N como igual a 5, um valor bastante razoável. Assim, precisaremos usar 5 instâncias principais do Redis em diferentes computadores ou máquinas virtuais para garantir que elas operem principalmente de forma independente umas das outras.
Para adquirir um bloqueio, o cliente realiza as seguintes operações:
- Obtém o tempo atual em milissegundos.
- Tenta obter um bloqueio em todas as N instâncias, usando o mesmo nome de chave e valores aleatórios. Na etapa 2, ao estabelecer o bloqueio para cada instância, o cliente utiliza um atraso que é suficientemente curto em comparação com o tempo após o qual o bloqueio é removido automaticamente. Por exemplo, se a duração do bloqueio for de 10 segundos, o atraso pode variar entre ~5-50 milissegundos. Dessa forma, exclui-se a situação em que o cliente poderia ficar bloqueado por muito tempo, tentando se conectar a um nó Redis com falha: se uma instância não estiver disponível, tentamos nos conectar a outra instância o mais rápido possível.
- Para obter o bloqueio, o cliente calcula quanto tempo se passou; para isso, ele subtrai do valor atual de tempo o timestamp que foi obtido na etapa 1. Somente quando o cliente conseguiu obter bloqueio na maioria das instâncias (pelo menos 3) e o tempo total necessário para conseguir o bloqueio é menor do que o tempo de validade do bloqueio, considera-se que o bloqueio foi obtido.
- Se o bloqueio foi obtido, a duração do bloqueio é considerada como o valor inicial do tempo de bloqueio menos o tempo decorrido, calculado na etapa 3.
- Se o cliente não conseguiu obter o bloqueio por algum motivo (seja porque não conseguiu bloquear N/2+1 instâncias ou o tempo de validade do bloqueio foi negativo), ele tentará desbloquear todas as instâncias (mesmo aquelas que achou que não poderia bloquear).
O algoritmo é assíncrono?
Este algoritmo baseia-se na suposição de que, embora não haja relógios sincronizados com os quais todos os processos trabalham, o tempo local em cada processo ainda flui aproximadamente na mesma velocidade, e a discrepância é pequena em comparação ao tempo total após o qual o bloqueio é removido automaticamente. Essa suposição é muito semelhante à situação típica em computadores normais: em cada computador, existem relógios locais, e normalmente podemos contar que a variação de tempo em diferentes computadores é pequena.
Neste estágio, devemos formular com mais rigor nossa regra de exclusão mútua: a exclusão mútua é garantida apenas se o cliente, que mantém o bloqueio, concluir sua operação dentro do período durante o qual o bloqueio é válido (esse valor foi obtido na etapa 3), menos um certo tempo (apenas alguns milissegundos, para compensar a discrepância de tempo entre os processos).
Mais detalhes sobre sistemas como esses, que requerem coordenação de discrepâncias de tempo, são discutidos no seguinte artigo interessante: .
Nova tentativa em caso de falha
Quando o cliente falha em obter um bloqueio, ele deve tentar novamente, aguardando um atraso aleatório; isso é feito com o objetivo de dessincronizar múltiplos clientes tentando simultaneamente obter o bloqueio do mesmo recurso (o que pode levar a uma situação de 'cérebro dividido', onde não há vencedores). Além disso, quanto mais rápido o cliente tenta adquirir o bloqueio da maioria das instâncias Redis, menor o intervalo em que pode ocorrer a situação de cérebro dividido (e menor a necessidade de novas tentativas). Portanto, idealmente, o cliente deve tentar enviar comandos SET simultaneamente a N instâncias usando multiplexação.
Aqui, é importante enfatizar quão crucial é que clientes que não conseguiram obter a maioria dos bloqueios liberem (parcialmente) os bloqueios adquiridos, para que não seja necessário esperar que o prazo de validade da chave expire antes que o bloqueio do recurso possa ser adquirido novamente (no entanto, se houver fragmentação de rede e o cliente perder a conexão com as instâncias Redis, será necessário pagar o preço da violação de disponibilidade enquanto se aguarda a expiração do prazo da chave).
Liberação do bloqueio
A liberação do bloqueio é uma operação simples, que requer apenas desbloquear todas as instâncias, independentemente de o cliente acreditar que conseguiu bloquear com sucesso uma instância específica.
Considerações de segurança
O algoritmo é seguro? Vamos tentar imaginar o que acontece em diferentes cenários.
Para começar, vamos supor que o cliente conseguiu obter o bloqueio sobre a maioria das instâncias. Cada uma das instâncias conterá uma chave com o mesmo tempo de validade. No entanto, cada uma dessas chaves foi estabelecida em momentos diferentes, portanto, a expiração delas ocorrerá em tempos distintos. Mas, se a primeira chave foi estabelecida em um momento não pior do que T1 (tempo que escolhemos antes de contatar o primeiro servidor), e a última chave foi estabelecida em um momento não pior do que T2 (tempo em que recebemos a resposta do último servidor), então estamos seguros de que a primeira chave no conjunto cuja validade vai expirar existirá por pelo menos MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Todas as outras chaves expirarão depois, portanto, podemos ter certeza de que todas as chaves serão válidas simultaneamente por, no mínimo, esse tempo.
Durante o tempo em que a maioria das chaves permanece válida, outro cliente não poderá adquirir o bloqueio, pois N/2+1 operações SET NX não podem ser bem-sucedidas se já existem N/2+1 chaves. Portanto, se o bloqueio foi adquirido, não é possível adquiri-lo novamente no mesmo momento (isso violaria a propriedade da exclusão mútua).
Na verdade, queremos ter certeza de que um conjunto de clientes que tenta adquirir o bloqueio ao mesmo tempo não conseguirá ter sucesso simultaneamente.
Se um cliente bloqueou a maioria das instâncias, gastando um tempo igual ou maior que o tempo máximo de duração do bloqueio, então considerará o bloqueio inválido e desbloqueará as instâncias. Portanto, devemos levar em conta apenas o caso em que o cliente conseguiu bloquear a maioria das instâncias em um tempo inferior ao período de validade. Neste caso, em relação ao argumento acima exposto, ao longo do tempo MIN_VALIDITY nenhum cliente deve ser capaz de recuperar o bloqueio novamente. Assim, um conjunto de clientes poderá bloquear N/2+1 instâncias ao mesmo tempo (que expira no momento em que a fase 2 termina) apenas quando o tempo para bloquear a maioria foi maior que o tempo TTL, tornando o bloqueio inválido.
Você pode apresentar uma prova formal de segurança, indicar algoritmos semelhantes que existem ou encontrar um bug na exposição?
Considerações sobre acessibilidade
A acessibilidade do sistema depende de três características principais:
- Desbloqueio automático (uma vez que os prazos de validade das chaves expiram): no final, as chaves estarão disponíveis novamente para serem usadas em bloqueios.
- O fato de que os clientes normalmente ajudam uns aos outros removendo bloqueios quando o bloqueio necessário não foi adquirido, ou foi adquirido, mas o trabalho foi concluído; portanto, é bastante provável que não precisemos esperar até que as chaves expirem para readquirir o bloqueio.
- O fato de que, quando um cliente precisa tentar novamente obter um bloqueio, ele espera por um período relativamente mais longo do que o necessário para adquirir a maioria dos bloqueios. Isso reduz a probabilidade de uma situação de cérebro dividido na competição por recursos.
No entanto, existe uma penalidade pelo tempo de acessibilidade reduzida, equivalente ao tempo de TTL em segmentos de rede, portanto, se houver segmentos contínuos, essa penalidade pode assumir um tamanho indefinido. Isso acontece toda vez que um cliente adquire um bloqueio e, em seguida, se desconecta em outro segmento antes de conseguir liberá-lo.
Em princípio, com segmentos contínuos e infinitos de rede, o sistema pode permanecer inacessível por um período infinito de tempo.
Desempenho, recuperação de falhas e fsync
Muitos utilizam Redis, pois é necessário garantir alto desempenho do servidor de bloqueios, no nível de latências necessárias para aquisição e liberação de bloqueios, assim como o número de operações de aquisição/liberação que conseguimos executar por segundo. Para atender a essa exigência, existe uma estratégia de comunicação com N servidores Redis, para reduzir a latência. Essa é uma estratégia de multiplexação (ou 'multiplexação de pobre', onde o socket é colocado em modo não bloqueante, envia todos os comandos e lê os comandos mais tarde, presumindo que o tempo de resposta entre o cliente e cada uma das instâncias é similar).
Na verdade, devemos considerar também a questão do armazenamento a longo prazo dos dados, se desejamos criar um modelo com recuperação confiável de falhas.
Basicamente, para esclarecer a questão, vamos supor que estamos configurando o Redis sem armazenamento de dados persistente. O cliente consegue bloquear 3 dos 5 instâncias. Uma das instâncias que o cliente conseguiu bloquear é reiniciada, e nesse momento surgem novamente 3 instâncias para o mesmo recurso que podemos bloquear, e outro cliente pode, por sua vez, bloquear a instância reiniciada, violando a propriedade de segurança que pressupõe a exclusividade dos bloqueios.
Se ativarmos a gravação antecipada de dados (AOF), a situação melhora um pouco. Por exemplo, podemos elevar o servidor enviando o comando SHUTDOWN e reiniciando-o. Como as operações de expiração no Redis são semanticamente implementadas de forma que o tempo continua a correr mesmo quando o servidor está desligado, todas as nossas requisições estão em ordem. Em teoria, isso funciona bem, desde que o desligamento seja feito de forma prudente. E o que fazer em caso de quedas de energia? Se o Redis estiver configurado por padrão, com a sincronização fsync no disco a cada segundo, é possível que, após a reinicialização, não consigamos encontrar nossa chave. Teoricamente, se quisermos garantir a segurança dos bloqueios em qualquer reinicialização da instância, devemos ativar fsync=always nas configurações de armazenamento de dados persistente. Isso vai acabar com a performance, reduzindo-a ao nível de sistemas CP que são tradicionalmente usados para implementações seguras de bloqueios distribuídos.
Mas a situação é melhor do que parece à primeira vista. Basicamente, a segurança do algoritmo é mantida, uma vez que, quando a instância é reiniciada após uma falha, ela não participa mais de nenhum bloqueio que esteja ativo no momento.
Para garantir isso, basta assegurar que, após uma falha, a instância permaneça indisponível por um período ligeiramente superior ao máximo TTL que estamos usando. Assim, aguardaremos a expiração e a liberação automática de todas as chaves que estavam ativas no momento da falha.
Usar reinicializações adiadas é, em princípio, uma forma de alcançar segurança mesmo na ausência de qualquer persistência a longo prazo no Redis. Vale ressaltar, no entanto, que isso pode resultar em penalidades por violação de disponibilidade. Por exemplo, com a falha da maioria das instâncias, o sistema se tornará globalmente inacessível durante o tempo de TTL (e nenhum recurso poderá ser bloqueado durante esse período).
Aumentando a disponibilidade do algoritmo: estendendo o bloqueio
Se o trabalho realizado pelos clientes consiste em pequenas etapas, é possível reduzir o tempo de expiração do bloqueio definido como padrão e implementar um mecanismo de extensão dos bloqueios. Basicamente, se o cliente estiver ocupado com cálculos e o valor do tempo de expiração do bloqueio estiver perigosamente diminuindo, pode-se enviar a todos as instâncias um script em Lua que estende o TTL da chave, caso a chave ainda exista e seu valor continue sendo aleatório, obtido quando o bloqueio foi adquirido.
O cliente deve considerar o bloqueio como re-adquirido apenas quando conseguir bloquear a maioria das instâncias durante o tempo de validade.
Entretanto, tecnicamente o algoritmo não muda, portanto o número máximo de tentativas de reaquisição de bloqueios deve ser limitado, caso contrário, as propriedades de disponibilidade serão comprometidas.
Fonte: habr.com
