Hoje chamamos sua atenção para a tradução de um artigo complexo sobre a implementação de bloqueios distribuídos usando Redis e propomos falar sobre as perspectivas do Redis como um tópico. Uma análise do algoritmo de Redlock considerado de Martin Kleppman, autor do livro "High Load Applications ", é fornecida aqui .
Os bloqueios distribuídos são um primitivo muito útil usado em muitos ambientes onde diferentes processos devem trabalhar em recursos compartilhados de uma maneira mutuamente exclusiva.
Existem várias bibliotecas e publicações que descrevem como implementar um DLM (Distributed Locking Manager) com o Redis, mas cada biblioteca tem uma abordagem diferente e as garantias fornecidas são bastante fracas em comparação com o que é possível com um design um pouco mais complexo.
Neste artigo, tentaremos descrever um algoritmo condicionalmente canônico demonstrando como implementar bloqueios distribuídos com o Redis. Vamos falar sobre um algoritmo chamado Redlock, ele implementa um gerenciador de bloqueio distribuído e, em nossa opinião, esse algoritmo é mais seguro do que a abordagem convencional de instância única. Esperamos que a comunidade o analise, dê feedback e o use 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, aqui estão alguns links para implementações prontas. Eles podem ser usados como referência.
- Redlock-rb (implementação Ruby). Também existe um fork do Redlock-rb, que adiciona um pacote (gem) para facilitar a distribuição, e não apenas para isso.
- Redlock-py (implementação Python).
- Aioredlock (implementação para Asyncio Python).
- Redlock-php (implementação de PHP ).
- PHPRedisMutex ( PHP)
- cheprasov/php-redis-lock (PHP- )
- Redsync ( Go).
- Redisson ( Java).
- Redis::DistLock ( Perl).
- Redlock-cpp ( C++).
- Redlock-cs ( C#/.NET).
- RedLock.net ( C#/.NET). async lock.
- ScarletLock ( C# .NET )
- Redlock4Net ( C# .NET)
- node-redlock ( NodeJS). .
Garantias de segurança e disponibilidade
Vamos modelar nosso projeto com apenas três propriedades que acreditamos fornecer as garantias mínimas necessárias para o uso eficaz de fechaduras distribuídas.
- Bens de segurança: exclusão mútua. Apenas um cliente pode segurar uma fechadura por vez.
- Propriedade de acessibilidade A: Sem bloqueios. No final, você sempre pode obter um bloqueio, mesmo se o cliente que bloqueou o recurso falhar ou acabar em outro segmento do disco.
- Propriedade B de acessibilidade: tolerância a falhas. Enquanto a maioria dos nós do Redis está em execução, os clientes podem adquirir e liberar bloqueios.
Por que uma implementação baseada em failover não é suficiente neste caso
Para entender o que vamos melhorar, vamos analisar o estado atual das coisas com a maioria das bibliotecas de bloqueio distribuídas baseadas no Redis.
A maneira mais fácil de bloquear um recurso usando o Redis é criar uma chave em uma instância. Normalmente, uma chave é criada com um tempo de vida limitado, isso é feito usando o recurso de expiração fornecido no Redis, então, mais cedo ou mais tarde, essa chave é liberada (propriedade 2 em nossa lista). Quando o cliente precisa liberar o recurso, ele remove a chave.
À primeira vista, essa solução parece funcionar, mas há um problema: há um único ponto de falha em nossa arquitetura. O que acontecerá se a instância mestre do Redis falhar? Vamos adicionar um seguidor então! E vamos usá-lo se o host não estiver disponível. Infelizmente, essa opção não é viável. Fazendo isso, não seremos capazes de implementar corretamente a propriedade de exclusão mútua necessária para garantir a segurança, porque a replicação no Redis é assíncrona.
Obviamente, uma condição de corrida ocorre em tal modelo:
- O cliente A obtém um bloqueio no mestre.
- O mestre falha antes que a gravação na chave seja transferida para o escravo.
- O seguidor é promovido a líder.
- O cliente B obtém um bloqueio no mesmo recurso que já está bloqueado por A. VIOLAÇÃO DE SEGURANÇA!
Às vezes, é perfeitamente normal que em circunstâncias especiais, como uma falha, vários clientes possam segurar uma trava ao mesmo tempo. Nesses casos, você pode aplicar uma solução baseada em replicação. Caso contrário, recomendamos a solução descrita neste artigo.
Implementação correta de instância única
Antes de tentar superar as deficiências da configuração de instância única descrita acima, vamos descobrir como lidar com este caso simples, uma vez que isso é realmente aceitável em aplicativos onde as condições de corrida são ocasionalmente aceitáveis, e também porque o bloqueio em uma única instância serve como base para o algoritmo distribuído descrito aqui.
Para adquirir um bloqueio, vamos fazer o seguinte:
SET resource_name my_random_value NX PX 30000
Este comando instala uma chave apenas se ela ainda não existir (opção NX), com uma data de validade de 30.000 milissegundos (opção PX). A chave está definida para “
myrandomvalue
”. Este valor deve ser exclusivo em todos os clientes e em todas as solicitações de bloqueio.
Basicamente, o valor aleatório é usado para liberar o bloqueio com segurança, com um script dizendo ao Redis para remover a chave apenas se ela existir e o valor armazenado nela for exatamente o que era esperado. Isso é realizado com o seguinte script Lua:
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
end
Isso é importante para evitar a liberação de um bloqueio por outro cliente. Por exemplo, um cliente pode adquirir um cadeado e, em seguida, bloquear em uma operação que dure mais do que o primeiro cadeado (para que a chave tenha tempo de expirar) e, posteriormente, remover o cadeado que algum outro cliente colocou.
Não é seguro usar um DEL simples porque um cliente pode remover um bloqueio mantido por outro cliente. Pelo contrário, ao usar o script acima, cada bloqueio é “assinado” com uma string aleatória, de forma que apenas o cliente que o colocou anteriormente pode removê-lo.
O que deve ser essa string aleatória? Eu acho que deve ter 20 bytes de / dev / urandom, mas você pode encontrar maneiras menos dispendiosas de tornar a string única o suficiente para o propósito que você está tentando realizar. Por exemplo, seria normal semear o RC4 com / dev / urandom e, em seguida, gerar um fluxo pseudo-aleatório com base nele. Uma solução mais simples envolve a combinação de tempo unix de microssegundos mais ID do cliente; não é tão seguro, mas talvez esteja no nível do desafio na maioria dos contextos.
O tempo que usamos como medida do tempo de vida da chave é chamado de "tempo de expiração do bloqueio". Esse valor é o tempo após o qual o bloqueio será automaticamente liberado e o tempo que o cliente tem para concluir a operação antes que outro cliente possa, por sua vez, bloquear o recurso sem realmente violar as garantias mútuas de exclusão. Essa garantia é limitada apenas a uma determinada janela de tempo, que começa a partir do momento da aquisição da fechadura.
Portanto, discutimos uma boa maneira de adquirir e liberar um bloqueio. O sistema (se estamos falando de um sistema não alocado que consiste em uma instância única e sempre disponível) é seguro. Vamos expandir esse conceito para um sistema distribuído no qual não temos essas garantias.
Algoritmo Redlock
A versão distribuída do algoritmo assume que temos N Redis principais. Esses nós são completamente independentes uns dos outros, portanto, não usamos replicação ou qualquer outro sistema de coordenação implícito. Já cobrimos como adquirir e liberar bloqueios com segurança em uma única instância. Presumimos que o algoritmo usará esse método ao trabalhar com uma única instância. Em nossos exemplos, definimos N como 5, que é um valor perfeitamente razoável. Portanto, precisaremos usar 5 mestres Redis em diferentes computadores ou máquinas virtuais para garantir que operem de forma amplamente independente uns dos outros.
Para adquirir um bloqueio, o cliente realiza as seguintes operações:
- Obtém a hora atual em milissegundos.
- N , . 2, , , , , , . , 10 , ~ 5-50 . , , Redis: , .
- , , ; , 1. , ( 3), , , , , , .
- , , 3.
- - ( N/2+1 , ), ( , , , ).
O algoritmo é assíncrono?
Este algoritmo é baseado na suposição de que, embora não haja um relógio sincronizado no qual todos os processos funcionem, a hora local em cada processo ainda flui aproximadamente na mesma taxa e o erro é pequeno em comparação com o tempo total após o qual o bloqueio é liberado automaticamente. Essa suposição é muito semelhante à situação típica de computadores comuns: cada computador tem um relógio local e, geralmente, podemos contar com o fato de que a diferença de fuso horário em computadores diferentes é pequena.
Nesta fase, devemos ser mais cuidadosos ao formular nossa regra de exclusão mútua: a exclusão mútua é garantida apenas se o cliente que está segurando o bloqueio for concluído dentro do tempo durante o qual o bloqueio é válido (este valor foi obtido na etapa 3), menos algum tempo (total vários milissegundos para compensar a diferença de tempo entre os processos).
O seguinte artigo interessante fala mais sobre esses sistemas que requerem um intervalo de tempo: Concessões: um mecanismo tolerante a falhas eficiente para consistência de cache de arquivo distribuído .
Tentar novamente em caso de falha
Quando o cliente não consegue adquirir o bloqueio, ele deve tentar fazê-lo novamente, com um atraso aleatório; isso é feito para sincronizar vários clientes simultaneamente tentando adquirir um bloqueio no mesmo recurso (o que pode levar a uma situação de divisão do cérebro em que não há vencedores). Além disso, quanto mais rápido o cliente tentar obter um bloqueio na maioria das instâncias do Redis, mais estreita será a janela em que uma situação de divisão de cérebro pode ocorrer (e menos tentativas são necessárias). Portanto, o ideal é que o cliente tente enviar comandos SET para N instâncias ao mesmo tempo, usando multiplexação.
É importante enfatizar aqui o quão importante é para os clientes que não foram capazes de adquirir a maioria dos bloqueios liberar bloqueios (parcialmente) adquiridos para que eles não tenham que esperar a data de expiração da chave antes que o bloqueio no recurso possa ser adquirido novamente (embora se ocorrer fragmentação da rede e o cliente perde o contato com as instâncias do Redis, então você tem que pagar uma multa de violação de acesso enquanto a chave expira).
Liberando um bloqueio A
liberação de um bloqueio é uma operação simples que requer que você simplesmente desbloqueie todas as instâncias, independentemente de o cliente achar que conseguiu bloquear uma determinada instância com sucesso.
Considerações de segurança
O algoritmo é seguro? Vamos tentar imaginar o que acontece em diferentes cenários.
Primeiro, vamos supor que o cliente foi capaz de adquirir o bloqueio na maioria das instâncias. Cada uma das instâncias conterá uma chave com o mesmo tempo de vida para todos. No entanto, cada uma dessas chaves foi instalada em seu próprio momento, portanto, elas expirarão em momentos diferentes. Mas, se a primeira chave foi instalada em um momento não pior do que T1 (o horário que escolhemos antes de contatar o primeiro servidor), e a última chave foi instalada em um momento não pior do que T2 (o horário em que uma resposta foi recebida do último servidor), então nós tenha certeza de que a primeira chave do conjunto que expira durará pelo menos
MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT
... Todas as outras chaves irão expirar mais tarde, então podemos ter certeza de que todas as chaves serão válidas simultaneamente por pelo menos este tempo.
Durante o tempo em que a maioria das chaves permanece válida, outro cliente não será capaz de adquirir o bloqueio, uma vez que as operações N / 2 + 1 SET NX não podem ter sucesso se as chaves N / 2 + 1 já existirem. Portanto, se a fechadura foi adquirida, é impossível readquiri-la no mesmo momento (isso violaria a propriedade de exclusão mútua).
No entanto, queremos ter certeza de que muitos clientes tentando adquirir um bloqueio simultaneamente não tenham sucesso ao mesmo tempo.
Se o cliente bloqueou a maioria das instâncias, gastando cerca ou mais do que a duração máxima de bloqueio para este tempo, ele invalidará o bloqueio e desbloqueará as instâncias. Portanto, só temos que considerar o caso em que o cliente conseguiu bloquear a maioria das instâncias em menos do que a data de expiração. Nesse caso, com relação ao argumento acima,
MIN_VALIDITY
nenhum cliente deve ser capaz de readquirir o bloqueio a tempo. Portanto, vários clientes serão capazes de bloquear instâncias N / 2 + 1 na mesma quantidade de tempo (que termina no final do estágio 2) apenas quando o tempo de bloqueio da maioria for maior que o tempo TTL, o que invalida o bloqueio.
Você pode fornecer uma prova formal de segurança, apontar algoritmos semelhantes existentes ou encontrar um bug acima?
Considerações sobre
disponibilidade A disponibilidade do sistema depende de três características principais:
- Liberação automática de fechaduras (conforme as chaves expiram): Eventualmente, as chaves estarão novamente disponíveis para serem utilizadas para fechaduras.
- O fato de que os clientes geralmente ajudam uns aos outros removendo bloqueios quando o bloqueio desejado não foi adquirido, ou foi adquirido, e o trabalho está concluído; portanto, é provável que não tenhamos de esperar que as chaves expirem para readquirir o bloqueio.
- O fato de que quando um cliente precisa tentar adquirir uma fechadura novamente, ele espera por um tempo relativamente mais longo do que o período que leva para adquirir a maioria das fechaduras. Isso reduz a probabilidade de uma situação de divisão do cérebro ao competir por recursos.
No entanto, você tem que pagar uma penalidade pela disponibilidade reduzida igual ao tempo TTL nos segmentos de rede, portanto, se houver segmentos contíguos, essa penalidade pode se tornar de um tamanho indefinido. Isso acontece sempre que um cliente adquire um bloqueio e, em seguida, fixa em outro segmento antes que ele possa liberá-lo.
Em princípio, dados infinitos segmentos de rede contíguos, o sistema pode permanecer indisponível por um período infinito de tempo.
Desempenho, failover e fsync
Muitas pessoas usam o Redis porque precisam fornecer alto desempenho do servidor de bloqueio, no nível de latência necessário para adquirir e liberar bloqueios, bem como o número dessas operações de aquisição / liberação que podem ser executadas por segundo. Para atender a esse requisito, existe uma estratégia de comunicação com servidores N Redis para reduzir a latência. Essa é uma estratégia de multiplexação (ou multiplexação de pobre, que coloca o soquete em modo sem bloqueio, envia todos os comandos e lê os comandos posteriormente, assumindo que o tempo de ida e volta entre o cliente e cada instância é semelhante).
É verdade que também há uma consideração de armazenamento de longo prazo a ser considerada se quisermos criar um modelo com recuperação confiável de falhas.
Basicamente, para esclarecer o problema, vamos supor que estejamos configurando o Redis sem armazenamento de dados de longo prazo. O cliente consegue bloquear 3 de 5 instâncias. Uma das instâncias que o cliente conseguiu bloquear é reiniciada, e neste momento aparecem novamente 3 instâncias para o mesmo recurso, que podemos bloquear, e o outro cliente pode, por sua vez, bloquear a instância reiniciada, violando a propriedade de segurança que implica exclusividade de fechaduras.
Se você habilitar o avanço de dados (AOF), a situação melhorará um pouco. Por exemplo, você pode promover 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 continue fluindo mesmo quando o servidor é desligado, está tudo em conformidade com todos os nossos requisitos. Normal, desde que o desligamento normal seja garantido. O que fazer em caso de queda de energia? Se o Redis estiver configurado por padrão, com o fsync sincronizando no disco a cada segundo, então é possível que após reiniciarmos perderemos nossa chave. Em teoria, se quisermos garantir a segurança dos bloqueios em qualquer reinicialização da instância, devemos habilitar
fsync=always
nas configurações de armazenamento de dados de longo prazo. Isso matará completamente o desempenho, ao nível dos sistemas CP tradicionalmente usados para implementar com segurança bloqueios distribuídos.
Mas a situação é melhor do que aparenta. Em princípio, o algoritmo permanece seguro porque quando uma instância é reiniciada após uma falha, ela não participa mais de nenhum bloqueio ativo no momento.
Para garantir isso, só precisamos garantir que, após uma falha, a instância permaneça indisponível por um período de tempo ligeiramente superior ao TTL máximo que estamos usando. Portanto, aguardaremos o vencimento e liberação automática de todas as chaves que estavam ativas no momento da recusa.
Usando reinicializações adiadas, é, em princípio, possível obter segurança sem qualquer persistência de longo prazo no Redis. Observe, no entanto, que isso pode resultar em uma penalidade de acessibilidade. Por exemplo, se a maioria das instâncias falhar, o sistema ficará globalmente indisponível durante o tempo TTL (e nenhum recurso pode ser bloqueado neste momento).
Aumentando a disponibilidade do algoritmo: estendendo o bloqueio
Se o trabalho realizado pelos clientes consistir em pequenas etapas, é possível reduzir o tempo de expiração do bloqueio padrão e implementar um mecanismo de prolongamento do bloqueio. Basicamente, se o cliente está ocupado com cálculos e o valor de expiração do bloqueio é perigosamente baixo, você pode enviar a todas as instâncias um script em Lua para estender o TTL da chave, se a chave ainda existir e seu valor ainda for aleatório obtido quando o bloqueio foi adquirido.
Um cliente deve considerar um bloqueio como readquirido apenas se tiver bloqueado com êxito a maioria das instâncias dentro do período de validade.
No entanto, tecnicamente, o algoritmo não muda neste caso, então o número máximo de tentativas repetidas de adquirir bloqueios deve ser limitado, caso contrário, as propriedades de acessibilidade serão violadas.