Bloqueio distribuído usando Redis

Oi, Habr!

Hoje chamamos sua atenção para a tradução de um artigo complexo sobre a implementação de bloqueio distribuído usando Redis e convidamos você a falar sobre as perspectivas do Redis como tema. Análise do algoritmo Redlock em questão de Martin Kleppmann, autor do livro "Aplicações de alta carga", dado aqui.

O bloqueio distribuído é uma primitiva muito útil usada em muitos ambientes onde diferentes processos devem trabalhar em recursos compartilhados de maneira mutuamente exclusiva.

Existem várias bibliotecas e postagens que descrevem como implementar DLM (Distributed Lock Manager) usando Redis, mas cada biblioteca adota uma abordagem diferente e as garantias que elas fornecem são bastante fracas em comparação com o que é possível com um design um pouco mais sofisticado.

Neste artigo tentaremos descrever um algoritmo canônico condicional que demonstra como implementar o bloqueio distribuído usando Redis. Falaremos 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 usual de instância única. Esperamos que a comunidade o analise, forneça feedback e o utilize como ponto de partida para projetos mais complexos ou alternativos.

Implementação

Antes de passarmos à descrição do algoritmo, fornecemos vários links para implementações prontas. Eles podem ser usados ​​como referência.

• Redlock-rb (implementação para Ruby). Há também garfo Redlock-rb, que adiciona um pacote (gem) para facilitar a distribuição, e não só para isso.
• Redlock-py (Implementação Python).
• Aioredlock (implementação para Asyncio Python).
• Redlock-php (implementação para PHP).
• PHPRedisMutex (outra implementação para PHP)
• cheprasov/php-redis-lock (Biblioteca PHP para bloqueios)
• Redsync (implementação para Go).
• Redisson (implementação para Java).
• Redis::DistLock (implementação para Perl).
• Redlock-cpp (implementação para C++).
• Redlock-cs (implementação para C#/.NET).
• RedLock.net (implementação para C#/.NET). Com suporte para extensões assíncronas e de bloqueio.
• ScarletLock (implementação para C# .NET com armazenamento de dados configurável)
• Redlock4Net (implementação para C# .NET)
• nó-redlock (implementação para NodeJS). Inclui suporte para extensão de fechaduras.

Garantias de segurança e disponibilidade

Vamos modelar nosso projeto com apenas três propriedades que acreditamos fornecerem as garantias mínimas necessárias para usar efetivamente o bloqueio distribuído.

1. Propriedade de segurança: Exclusão mútua. A qualquer momento, apenas um cliente pode manter o bloqueio.
2. Propriedade de disponibilidade A: Sem conflitos. Sempre é possível adquirir um bloqueio, mesmo que o cliente que bloqueou o recurso falhe ou caia em um segmento de disco diferente.
3. Propriedade de disponibilidade B: tolerância a falhas. Enquanto a maioria dos nós Redis estiver em execução, os clientes poderão adquirir e liberar bloqueios.

Por que a implementação baseada na recuperação de falhas não é suficiente neste caso
Para entender o que vamos melhorar, vamos analisar o estado atual da maioria das bibliotecas de bloqueio distribuídas baseadas em Redis.

A maneira mais simples de bloquear um recurso usando Redis é criar uma chave na instância. Normalmente, uma chave é criada com vida útil limitada, isso é conseguido 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 exclui a chave.

À primeira vista, esta solução funciona muito bem, mas há um problema: a nossa arquitetura cria um ponto único de falha. O que acontece se a instância do host Redis falhar? Vamos adicionar um escravo então! E vamos usá-lo se o apresentador não estiver disponível. Infelizmente, esta opção não é viável. Ao fazer isso, não seremos capazes de implementar adequadamente a propriedade de exclusão mútua necessária para garantir a segurança, porque a replicação no Redis é assíncrona.

Obviamente, em tal modelo ocorre uma condição de corrida:

1. O cliente A adquire um bloqueio no mestre.
2. O mestre falha antes que a entrada da chave seja transferida para o escravo.
3. O seguidor é promovido a líder.
4. O cliente B adquire um bloqueio no mesmo recurso que A já bloqueou. VIOLAÇÃO DE SEGURANÇA!

Às vezes é completamente normal que em circunstâncias especiais, como uma falha, muitos clientes consigam manter o bloqueio ao mesmo tempo. Nesses casos, uma solução baseada em replicação pode ser aplicada. Caso contrário, recomendamos a solução descrita neste artigo.

Implementação correta com uma única instância

Antes de tentar superar as deficiências da configuração de instância única descrita acima, vamos entender como lidar adequadamente com este caso simples, uma vez que esta solução é realmente válida em aplicações onde uma condição de corrida é aceitável de tempos em tempos, e também porque o bloqueio em um uma única instância serve como base usada no algoritmo distribuído descrito aqui.

Para adquirir um bloqueio, faça o seguinte:

SET resource_name my_random_value NX PX 30000

Este comando instala uma chave somente se ela ainda não existir (opção NX), com prazo de validade de 30000 milissegundos (opção PX). A chave está definida como “myrandomvalue" Esse valor deve ser exclusivo em todos os clientes e em todas as solicitações de bloqueio.
Basicamente, um valor aleatório é usado para liberar o bloqueio com segurança, com um script informando ao Redis: remova a chave apenas se ela existir e o valor armazenado nela for exatamente o esperado. Isso é conseguido usando o seguinte script Lua:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

Isto é importante para evitar que um bloqueio mantido por outro cliente seja removido. Por exemplo, um cliente pode adquirir um bloqueio e, em seguida, ficar bloqueado em alguma operação que dure mais que o primeiro bloqueio (para que a chave tenha tempo de expirar) e, posteriormente, remover o bloqueio que algum outro cliente colocou.
Usar um DEL simples não é seguro porque um cliente pode remover um bloqueio mantido por outro cliente. Em contrapartida, ao utilizar o script acima, cada bloqueio é “assinado” com uma string aleatória, portanto somente o cliente que o colocou anteriormente pode removê-lo.

Qual deveria ser essa string aleatória? Suponho que deva ter 20 bytes de /dev/urandom, mas você pode encontrar maneiras menos dispendiosas de tornar a string única o suficiente para seus propósitos. Por exemplo, seria bom semear RC4 com /dev/urandom e então gerar um fluxo pseudo-aleatório a partir dele. Uma solução mais simples envolve uma combinação de tempo unix em resolução de microssegundos mais o ID do cliente; não é tão seguro, mas provavelmente está à altura da tarefa na maioria dos contextos.

O tempo que usamos como medida da vida útil da chave é chamado de “vida útil da fechadura”. Esse valor é a quantidade de tempo antes que o bloqueio seja liberado automaticamente e a quantidade de tempo que um cliente tem para concluir uma operação antes que outro cliente possa, por sua vez, bloquear esse recurso, sem realmente violar as garantias de exclusão mútua. Esta garantia está limitada apenas a um determinado período de tempo, que começa a partir do momento da compra da fechadura.

Portanto, 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 instância única e sempre disponível) é seguro. Vamos estender esse conceito para um sistema distribuído, onde não temos tais garantias.

Algoritmo Redlock

A versão distribuída do algoritmo assume que temos N mestres Redis. Esses nós são completamente independentes entre si, portanto não utilizamos replicação ou qualquer outro sistema de coordenação implícito. Já abordamos como adquirir e liberar com segurança um bloqueio em uma única instância. Assumimos que o algoritmo, ao trabalhar com uma única instância, usará exatamente este método. Nos nossos exemplos definimos N como 5, que é um valor razoável. Assim, precisaremos usar 5 mestres Redis em diferentes computadores ou máquinas virtuais para garantir que eles atuem de forma bastante independente um do outro.

Para adquirir um bloqueio, o cliente realiza as seguintes operações:

1. Obtém a hora atual em milissegundos.
2. Tenta sequencialmente obter um bloqueio em todas as N instâncias, usando o mesmo nome de chave e valores aleatórios em todos os casos. No Estágio 2, quando o cliente configura um bloqueio por instância, o cliente usa um atraso para adquiri-lo que é curto o suficiente em comparação com o tempo após o qual o bloqueio é liberado automaticamente. Por exemplo, se a duração do bloqueio for de 10 segundos, o atraso poderá estar na faixa de aproximadamente 5 a 50 milissegundos. Isso elimina a situação em que o cliente poderia permanecer bloqueado por um longo tempo tentando acessar um nó Redis com falha: se a instância estiver indisponível, tentamos conectar-se a outra instância o mais rápido possível.
3. Para realizar o bloqueio, o cliente calcula quanto tempo passou; Para fazer isso, ele subtrai do valor do tempo real o carimbo de data/hora obtido na etapa 1. Se e somente se o cliente conseguiu obter o bloqueio na maioria das instâncias (pelo menos 3) e o tempo total que levou para obter o bloqueio, menor que a duração do bloqueio, o bloqueio é considerado obtido.
4. Se um bloqueio tiver sido adquirido, a duração do bloqueio será considerada a duração do bloqueio original menos o tempo decorrido calculado na etapa 3.
5. Se o cliente não conseguir obter o bloqueio por algum motivo (não foi possível bloquear instâncias N/2+1 ou a duração do bloqueio foi negativa), ele tentará desbloquear todas as instâncias (mesmo aquelas que ele pensou que não poderia bloquear). ).

O algoritmo é assíncrono?

Este algoritmo é baseado na suposição de que, embora não exista um relógio sincronizado no qual todos os processos funcionem, a hora local em cada processo ainda flui aproximadamente no mesmo ritmo, e o erro é pequeno comparado ao tempo total após o qual o bloqueio é liberado automaticamente. Essa suposição é muito semelhante à situação típica dos computadores comuns: cada computador possui um relógio local e geralmente podemos contar com o fato de que a diferença horária entre os diferentes computadores é pequena.

Neste ponto, devemos formular com mais cuidado a nossa regra de exclusão mútua: a exclusão mútua é garantida apenas se o cliente detentor do bloqueio sair durante o tempo em que o bloqueio é válido (este valor obtido no passo 3), menos algum tempo a mais (total de alguns milissegundos para compensar a diferença de tempo entre os processos).

O artigo interessante a seguir fala mais sobre sistemas que requerem coordenação de intervalos de tempo: Locações: um mecanismo eficiente de tolerância a falhas para consistência de cache de arquivos distribuídos.

Tentar novamente em caso de falha

Quando um cliente não consegue adquirir um bloqueio, ele deve tentar novamente após um atraso aleatório; isso é feito para dessincronizar vários clientes que tentam adquirir um bloqueio no mesmo recurso ao mesmo tempo (o que pode levar a uma situação de "cérebro dividido" na qual não há vencedores). Além disso, quanto mais rápido um cliente tentar adquirir um bloqueio na maioria das instâncias do Redis, mais estreita será a janela na qual uma situação de cérebro dividido pode ocorrer (e menor será a necessidade de novas tentativas). Portanto, idealmente, o cliente deve tentar enviar comandos SET para N instâncias simultaneamente usando multiplexação.

Vale ressaltar aqui a importância de que os clientes que não conseguem adquirir a maioria dos bloqueios liberem os bloqueios (parcialmente) adquiridos, para que não tenham que esperar a chave expirar para que o bloqueio do recurso possa ser adquirido novamente (embora se ocorrer fragmentação da rede e o cliente perder contato com as instâncias do Redis, você terá que pagar uma penalidade de disponibilidade enquanto espera a chave expirar).

Solte o bloqueio

Liberar um bloqueio é uma operação simples que requer simplesmente o desbloqueio de todas as instâncias, independentemente de o cliente parecer ter bloqueado com êxito 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 um bloqueio na maioria das instâncias. Cada instância conterá uma chave com o mesmo tempo de vida para todas. No entanto, cada uma dessas chaves foi instalada em um momento diferente e, portanto, expirarão em momentos diferentes. Mas, se a primeira chave foi instalada num momento não pior que T1 (o momento que escolhemos antes de contactar o primeiro servidor), e a última chave foi instalada num momento não pior que T2 (o momento em que a resposta foi recebida do último servidor), então estamos confiantes de que a primeira chave do conjunto que expira sobreviverá pelo menos MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Todas as outras chaves expirarão mais tarde, portanto podemos ter certeza de que todas as chaves serão válidas simultaneamente pelo menos desta vez.

Durante o tempo em que a maioria das chaves permanecer válida, outro cliente não poderá adquirir o bloqueio, uma vez que as operações N/2+1 SET NX não poderão ter sucesso se já existirem chaves N/2+1. Portanto, uma vez adquirido um bloqueio, é impossível adquiri-lo novamente no mesmo momento (isso violaria a propriedade de exclusão mútua).
No entanto, queremos ter certeza de que vários clientes que tentam adquirir um bloqueio ao mesmo tempo não terão sucesso ao mesmo tempo.

Se o cliente tiver bloqueado a maioria das instâncias por aproximadamente ou mais que a duração máxima do bloqueio, ele considerará o bloqueio inválido e desbloqueará as instâncias. Portanto, basta levar em consideração o caso em que o cliente conseguiu bloquear a maioria das instâncias em tempo inferior ao prazo de validade. Neste caso, em relação ao argumento acima, durante o tempo MIN_VALIDITY nenhum cliente deve ser capaz de readquirir o bloqueio. Portanto, muitos clientes poderão bloquear instâncias N/2+1 no mesmo tempo (que termina no final do estágio 2) somente quando o tempo para bloquear a maioria for maior que o tempo TTL, o que torna o bloqueio inválido.

Você pode fornecer uma prova formal de segurança, indicar algoritmos semelhantes existentes ou encontrar um bug nos itens acima?

Considerações de acessibilidade

A disponibilidade do sistema depende de três características principais:

1. Liberar bloqueios automaticamente (conforme as chaves expiram): As chaves eventualmente estarão disponíveis novamente para serem usadas em bloqueios.
2. O fato de os clientes geralmente se ajudarem removendo bloqueios quando o bloqueio desejado não foi adquirido, ou foi adquirido e o trabalho foi concluído; portanto, é provável que não tenhamos que esperar que as chaves expirem para readquirir o bloqueio.
3. O fato de que quando um cliente precisa tentar novamente adquirir um bloqueio, ele espera um tempo comparativamente mais longo do que o período necessário para adquirir a maioria dos bloqueios. Isto reduz a probabilidade de surgir uma situação de divisão cerebral ao competir por recursos.

Porém, existe uma penalidade de disponibilidade igual ao TTL dos segmentos da rede, portanto, se houver segmentos contíguos, a penalidade poderá ser indefinida. Isso ocorre sempre que um cliente adquire um bloqueio e depois o transfere para outro segmento antes de poder liberá-lo.

Em princípio, dados infinitos segmentos de rede contíguos, um sistema pode permanecer indisponível por um período infinito de tempo.

Desempenho, failover e fsync

Muitas pessoas usam o Redis porque precisam de alto desempenho do servidor de bloqueio em termos da latência necessária para adquirir e liberar bloqueios e do número de aquisições/liberações que podem ser concluídas por segundo. Para atender a esse requisito, existe uma estratégia de comunicação com servidores N Redis para reduzir a latência. Esta é uma estratégia de multiplexação (ou "multiplexação do pobre homem", onde o soquete é colocado 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) .

No entanto, também temos de ter em conta a consideração associada ao armazenamento de dados a longo prazo se nos esforçarmos para criar um modelo com recuperação fiável de falhas.

Basicamente, para esclarecer o problema, vamos supor que configuramos o Redis sem nenhum 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 existem 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 assume exclusividade de fechaduras.

Se você habilitar os dados antecipados (AOF), a situação melhorará um pouco. Por exemplo, você pode promover um servidor enviando o comando SHUTDOWN e reiniciando-o. Como as operações de expiração no Redis são implementadas semanticamente de forma que o tempo continue a fluir mesmo quando o servidor está desligado, todos os nossos requisitos estão corretos. Isso é normal, desde que seja garantido um desligamento normal. O que fazer em caso de queda de energia? Se o Redis estiver configurado por padrão, com fsync sincronizando no disco a cada segundo, então é possível que após uma reinicialização não tenhamos nossa chave. Teoricamente, se quisermos garantir a segurança do bloqueio durante qualquer reinicialização da instância, deveríamos habilitar fsync=always nas configurações para armazenamento de dados de longo prazo. Isso eliminará completamente o desempenho, até o nível dos sistemas CP que são tradicionalmente usados ​​para implementar bloqueios distribuídos com segurança.

Mas a situação é melhor do que parece à primeira vista. A princípio, a segurança do algoritmo é preservada porque 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, 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 usamos. Desta forma aguardaremos até a data de vencimento e liberação automática de todas as chaves que estavam ativas no momento da falha.

Usando reinicializações atrasadas, é, em princípio, possível obter segurança mesmo na ausência de qualquer persistência de longo prazo no Redis. Observe, entretanto, que isso pode resultar em multa por violação de acessibilidade. Por exemplo, se a maioria das instâncias falhar, o sistema ficará globalmente indisponível para o TTL (e nenhum recurso poderá ser bloqueado durante esse período).

Aumentamos a disponibilidade do algoritmo: estendemos o bloqueio

Se o trabalho realizado pelos clientes consistir em pequenas etapas, é possível reduzir a duração padrão do bloqueio e implementar um mecanismo para estender os bloqueios. Em princípio, se o cliente estiver ocupado computando e o valor de expiração do bloqueio estiver perigosamente baixo, você poderá enviar um script Lua para todas as instâncias que estenda o TTL da chave se a chave ainda existir e seu valor ainda for um valor aleatório obtido quando o o bloqueio foi adquirido.

Um cliente só deve considerar a readquirição de um bloqueio se tiver conseguido bloquear a maioria das instâncias dentro do período de validade.

É verdade que tecnicamente o algoritmo não muda, portanto o número máximo de tentativas repetidas de aquisição de bloqueios deve ser limitado, caso contrário as propriedades de acessibilidade serão violadas.

Fonte: habr.com