ProHoster > Blog > Administración > Bloqueo distribuído mediante Redis

Bloqueo distribuído mediante Redis

Ola Habr!

Hoxe traemos á túa atención a tradución dun artigo complexo sobre a implementación do bloqueo distribuído mediante Redis e invitámosche a falar sobre as perspectivas de Redis como tema. Análise do algoritmo Redlock en cuestión de Martin Kleppmann, autor do libro "Aplicacións de alta carga", dado aquí.

O bloqueo distribuído é unha primitiva moi útil que se usa en moitos ambientes nos que diferentes procesos deben traballar en recursos compartidos de forma mutuamente excluínte.

Hai unha serie de bibliotecas e publicacións que describen como implementar DLM (Xestor de bloqueo distribuído) usando Redis, pero cada biblioteca adopta un enfoque diferente e as garantías que ofrecen son bastante débiles en comparación co que se pode conseguir cun deseño un pouco máis sofisticado.

Neste artigo, tentaremos describir un algoritmo canónico condicional que demostra como implementar o bloqueo distribuído usando Redis. Falaremos dun algoritmo chamado Redlock, implementa un xestor de bloqueo distribuído e, na nosa opinión, este algoritmo é máis seguro que o enfoque habitual dunha única instancia. Agardamos que a comunidade o analice, proporcione comentarios e o utilice como punto de partida para proxectos máis complexos ou alternativos.

Implementación

Antes de pasar á descrición do algoritmo, fornecemos varias ligazóns a implementacións preparadas. Pódense usar como referencia.

Garantías de seguridade e dispoñibilidade

Imos modelar o noso deseño con só tres propiedades que pensamos que proporcionan as garantías mínimas necesarias para utilizar eficazmente o bloqueo distribuído.

  1. Bens de seguridade: exclusión mutua. En calquera momento, só un cliente pode manter o bloqueo.
  2. Dispoñibilidade Propiedade A: sen bloqueos. Sempre é posible eventualmente adquirir un bloqueo, aínda que o cliente que bloqueou o recurso falle ou aterrice nun segmento de disco diferente.
  3. Dispoñibilidade Propiedade B: Tolerancia a fallos. Mentres a maioría dos nós de Redis estean en execución, os clientes poden adquirir e liberar bloqueos.

Por que a implementación baseada na recuperación do fallo non é suficiente neste caso
Para comprender o que imos mellorar, analicemos o estado actual da maioría das bibliotecas de bloqueo distribuídas baseadas en Redis.

A forma máis sinxela de bloquear un recurso usando Redis é crear unha chave na instancia. Normalmente, unha chave créase cunha vida útil limitada, isto conséguese mediante a función de caducidade proporcionada en Redis, polo que tarde ou cedo esta chave é liberada (propiedade 2 da nosa lista). Cando o cliente necesita liberar o recurso, elimina a chave.

A primeira vista, esta solución funciona bastante ben, pero hai un problema: a nosa arquitectura crea un único punto de falla. Que ocorre se a instancia de Redis do host falla? Engadimos un escravo entón! E utilizarémolo se o presentador non está dispoñible. Desafortunadamente, esta opción non é viable. Ao facelo, non poderemos implementar correctamente a propiedade de exclusión mutua que necesitamos para garantir a seguridade, porque a replicación en Redis é asíncrona.

Obviamente, nun modelo deste tipo ocorre unha condición de carreira:

  1. O cliente A adquire un bloqueo no mestre.
  2. O mestre falla antes de que a entrada da chave sexa transferida ao escravo.
  3. O seguidor é ascendido a líder.
  4. O cliente B adquire un bloqueo no mesmo recurso que A xa bloqueou. VIOLACIÓN DA SEGURIDADE!

Ás veces é completamente normal que en circunstancias especiais, como un fallo, moitos clientes poidan manter o bloqueo ao mesmo tempo. Nestes casos, pódese aplicar unha solución baseada na replicación. En caso contrario, recomendamos a solución descrita neste artigo.

Implementación correcta cunha única instancia

Antes de tentar superar as deficiencias da configuración de instancia única descrita anteriormente, imos entender como xestionar correctamente este caso sinxelo, xa que esta solución é realmente válida en aplicacións onde unha condición de carreira é aceptable de cando en vez, e tamén porque o bloqueo nun instancia única serve como base que se usa no algoritmo distribuído descrito aquí.

Para adquirir un bloqueo, fai isto:

SET resource_name my_random_value NX PX 30000

Este comando instala unha clave só se aínda non existe (opción NX), cun período de validez de 30000 milisegundos (opción PX). A chave está configurada en "myrandomvalue" Este valor debe ser único en todos os clientes e en todas as solicitudes de bloqueo.
Basicamente, úsase un valor aleatorio para liberar o bloqueo con seguridade, cun script que lle indica a Redis: só elimine a chave se existe e o valor almacenado nel é exactamente o que se esperaba. Isto conséguese 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 se elimine un bloqueo mantido por outro cliente. Por exemplo, un cliente pode adquirir un bloqueo, despois quedar bloqueado nalgunha operación que dura máis que o primeiro bloqueo (para que a chave teña tempo de caducar) e despois eliminar o bloqueo que algún outro cliente colocara.
Usar unha DEL simple non é seguro porque un cliente pode eliminar un bloqueo que ten outro cliente. En cambio, cando se utiliza o script anterior, cada bloqueo está "asinado" cunha cadea aleatoria, polo que só o cliente que o colocou anteriormente pode eliminalo.

Cal debe ser esta cadea aleatoria? Supoño que debería estar a 20 bytes de /dev/urandom, pero podes atopar formas menos custosas de facer que a cadea sexa única o suficiente para os teus propósitos. Por exemplo, estaría ben sementar RC4 con /dev/urandom e despois xerar un fluxo pseudoaleatorio a partir del. Unha solución máis sinxela implica unha combinación de tempo Unix en resolución de microsegundos máis o ID do cliente; non é tan seguro, pero probablemente estea á altura da tarefa na maioría dos contextos.

O tempo que usamos como medida da vida útil da chave chámase "vida útil do bloqueo". Este valor é tanto a cantidade de tempo antes de que o bloqueo se libere automaticamente como a cantidade de tempo que ten un cliente para completar unha operación antes de que outro cliente poida bloquear ese recurso, sen que se viole as garantías de exclusión mutua. Esta garantía está limitada só a un período de tempo determinado, que comeza a partir do momento en que se compra o bloqueo.

Así que falamos dunha boa forma de adquirir e liberar un bloqueo. O sistema (se estamos a falar dun sistema non distribuído que consta dunha única instancia e sempre dispoñible) é seguro. Estendamos este concepto a un sistema distribuído, onde non temos tales garantías.

Algoritmo Redlock

A versión distribuída do algoritmo supón que temos N mestres Redis. Estes nodos son completamente independentes entre si, polo que non utilizamos a replicación nin ningún outro sistema de coordinación implícito. Xa explicamos como adquirir e liberar de forma segura un bloqueo nunha única instancia. Damos por feito que o algoritmo, cando traballa cunha única instancia, utilizará exactamente este método. Nos nosos exemplos establecemos N en 5, que é un valor razoable. Así, teremos que empregar 5 mestres Redis en diferentes ordenadores ou máquinas virtuais para asegurarnos de que actúan de forma independente entre si.

Para adquirir un bloqueo, o cliente realiza as seguintes operacións:

  1. Obtén a hora actual en milisegundos.
  2. Intenta obter un bloqueo secuencial en todas as N instancias, utilizando o mesmo nome de chave e valores aleatorios en todos os casos. Na fase 2, cando o cliente configura un bloqueo por instancia, o cliente usa un atraso para adquirilo que é o suficientemente curto en comparación co tempo despois do cal se libera automaticamente o bloqueo. Por exemplo, se a duración do bloqueo é de 10 segundos, o atraso podería estar no intervalo de ~5-50 milisegundos. Isto elimina a situación na que o cliente podería permanecer bloqueado durante moito tempo tentando chegar a un nodo Redis fallido: se a instancia non está dispoñible, tentamos conectarnos a outra instancia canto antes.
  3. Para levar un bloqueo, o cliente calcula canto tempo pasou; Para iso, resta do valor de tempo real a marca de tempo que se obtivo no paso 1. Se e só se o cliente puido obter o bloqueo na maioría das instancias (polo menos 3) e o tempo total que levou obter o bloqueo, menor que a duración do bloqueo, considérase obtido o bloqueo.
  4. Se se adquiriu un bloqueo, a duración do bloqueo considérase como a duración do bloqueo orixinal menos o tempo transcorrido calculado no paso 3.
  5. Se o cliente non consegue o bloqueo por algún motivo (ou non puido bloquear N/2+1 instancias ou a duración do bloqueo foi negativa), tentará desbloquear todas as instancias (incluso aquelas que pensaba que non podía bloquear). ).

O algoritmo é asíncrono?

Este algoritmo baséase na suposición de que, aínda que non hai un reloxo sincronizado no que funcionarían todos os procesos, a hora local de cada proceso segue a fluír aproximadamente ao mesmo ritmo e o erro é pequeno en comparación co tempo total despois do cal o bloqueo se realiza. liberado automaticamente. Esta suposición é moi similar á típica dos ordenadores comúns: cada ordenador ten un reloxo local, e normalmente podemos contar co feito de que a diferenza horaria entre os distintos ordenadores é pequena.

Neste punto, debemos formular máis coidadosamente a nosa regra de exclusión mutua: a exclusión mutua está garantida só se o cliente que ten o bloqueo sae durante o tempo que o bloqueo é válido (este valor obtido no paso 3), menos un tempo máis (en total uns poucos). milisegundos para compensar a diferenza de tempo entre procesos).

O seguinte artigo interesante explica máis sobre estes sistemas que requiren coordinación de intervalos de tempo: Arrendamentos: un mecanismo eficiente de tolerancia a fallos para a coherencia da caché de ficheiros distribuídos.

Inténtalo de novo en caso de fallo

Cando un cliente non logra adquirir un bloqueo, debe tentalo de novo despois dun atraso aleatorio; isto faise para desincronizar varios clientes que tentan adquirir un bloqueo no mesmo recurso ao mesmo tempo (o que pode levar a unha situación de "cerebro dividido" na que non hai gañadores). Ademais, canto máis rápido intente un cliente adquirir un bloqueo na maioría das instancias de Redis, máis estreita será a xanela na que se pode producir unha situación de división do cerebro (e menor será a necesidade de reintentos). Polo tanto, idealmente, o cliente debería tentar enviar comandos SET a N instancias simultaneamente mediante multiplexación.

Convén enfatizar aquí o importante que é para os clientes que non adquiren a maioría das pechaduras liberar as pechaduras (parcialmente) adquiridas, para que non teñan que esperar a que caduque a chave antes de poder volver a adquirir o bloqueo do recurso. (aínda que se se produce a fragmentación da rede e o cliente perde o contacto coas instancias de Redis, entón tes que pagar unha penalización de dispoñibilidade mentres esperas a que caduque a chave).

Liberando o bloqueo

Liberar un bloqueo é unha operación sinxela que simplemente require desbloquear todas as instancias, independentemente de que o cliente pareza bloquear con éxito unha instancia en particular.

Consideracións de seguridade

É seguro o algoritmo? Intentemos imaxinar o que acontece en diferentes escenarios.

Para comezar, supoñamos que o cliente puido obter un bloqueo na maioría das instancias. Cada instancia conterá unha clave coa mesma vida útil para todas. Non obstante, cada unha destas chaves instalouse nun momento diferente, polo que caducarán en momentos diferentes. Pero, se a primeira chave instalouse nun momento non peor que o T1 (o momento que escollemos antes de contactar co primeiro servidor) e a última chave instalouse nun momento non peor que o T2 (o momento no que se recibiu a resposta). desde o último servidor), entón estamos seguros de que a primeira clave do conxunto que caduca sobrevivirá polo menos MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Todas as demais chaves caducarán máis tarde, polo que podemos estar seguros de que todas as claves serán válidas simultáneamente polo menos durante este tempo.

Durante o tempo que a maioría das chaves permanecen válidas, outro cliente non poderá adquirir o bloqueo, xa que as operacións N/2+1 SET NX non poden ter éxito se xa existen chaves N/2+1. Polo tanto, unha vez adquirido un bloqueo, é imposible adquirilo de novo no mesmo momento (isto vulneraría a propiedade de exclusión mutua).
Non obstante, queremos asegurarnos de que varios clientes que intenten adquirir un bloqueo ao mesmo tempo non poidan ter éxito ao mesmo tempo.

Se o cliente bloqueou a maioría das instancias durante aproximadamente ou máis que a duración máxima do bloqueo, considerará que o bloqueo non é válido e desbloqueará as instancias. Polo tanto, só temos que ter en conta o caso no que o cliente conseguiu bloquear a maioría das instancias nun tempo inferior á data de caducidade. Neste caso, respecto do argumento anterior, durante o tempo MIN_VALIDITY ningún cliente debería poder volver a adquirir o bloqueo. Polo tanto, moitos clientes poderán bloquear N/2+1 instancias ao mesmo tempo (que remata ao final da etapa 2) só cando o tempo para bloquear a maioría fose superior ao tempo TTL, o que fai que o bloqueo non sexa válido.

Podes proporcionar unha proba formal de seguridade, indicar algoritmos similares existentes ou atopar un erro no anterior?

Consideracións de accesibilidade

A dispoñibilidade do sistema depende de tres características principais:

  1. Liberar os bloqueos automaticamente (a medida que caducan as chaves): as chaves estarán dispoñibles de novo para ser usadas para as pechaduras.
  2. O feito de que os clientes adoitan axudarse uns a outros eliminando os bloqueos cando non se adquiriu o bloqueo desexado, ou foi adquirido e o traballo completou; polo que é probable que non teñamos que esperar a que caduquen as chaves para volver adquirir o bloqueo.
  3. O feito de que cando un cliente necesita volver tentar adquirir un bloqueo, espera un tempo comparativamente máis longo que o período necesario para adquirir a maioría dos bloqueos. Isto reduce a probabilidade de que se produza unha situación de división cerebral ao competir polos recursos.

Non obstante, existe unha penalización de dispoñibilidade igual ao TTL dos segmentos de rede, polo que se hai segmentos contiguos, a penalización pode ser indefinida. Isto ocorre sempre que un cliente adquire un bloqueo e despois arrinca outro segmento antes de que poida liberalo.

En principio, dados infinitos segmentos de rede contiguos, un sistema pode permanecer non dispoñible durante un período de tempo infinito.

Rendemento, failover e fsync

Moitas persoas usan Redis porque necesitan un alto rendemento do servidor de bloqueo en canto á latencia necesaria para adquirir e liberar bloqueos e ao número de adquisicións/lanzamentos que se poden completar por segundo. Para cumprir este requisito, hai unha estratexia para comunicarse cos servidores N Redis para reducir a latencia. Esta é unha estratexia de multiplexación (ou "multiplexación do pobre", onde o socket ponse en modo non bloqueador, envía todos os comandos e le os comandos máis tarde, asumindo que o tempo de ida e volta entre o cliente e cada instancia é similar) .

Non obstante, tamén temos que ter en conta a consideración asociada ao almacenamento de datos a longo prazo se nos esforzos por crear un modelo con recuperación fiable de fallos.

Basicamente, para aclarar o problema, supoñamos que configuramos Redis sen almacenamento de datos a longo prazo. O cliente consegue bloquear 3 de cada 5 instancias. Reiniciase unha das instancias que o cliente conseguiu bloquear, e neste momento hai de novo 3 instancias para o mesmo recurso, que podemos bloquear, e outro cliente pode, á súa vez, bloquear a instancia reiniciada, violando a propiedade de seguridade que asume a exclusividade das pechaduras.

Se activas datos adiante (AOF), a situación mellorará lixeiramente. Por exemplo, pode promocionar un servidor enviando o comando SHUTDOWN e reiniciándoo. Dado que as operacións de caducidade en Redis están implementadas semanticamente de forma que o tempo segue fluíndo mesmo cando o servidor está apagado, todos os nosos requisitos están ben. Isto é normal sempre que se garanta unha parada normal. Que facer en caso de corte de luz? Se Redis está configurado por defecto, con fsync sincronizando no disco cada segundo, entón é posible que despois dun reinicio non teñamos a nosa chave. Teoricamente, se queremos garantir a seguridade do bloqueo durante o reinicio de calquera instancia, deberíamos activalo fsync=always na configuración de almacenamento de datos a longo prazo. Isto matará completamente o rendemento, ata o nivel dos sistemas CP que se usan tradicionalmente para implementar de forma segura bloqueos distribuídos.

Pero a situación é mellor do que parece a primeira vista. En principio, a seguridade do algoritmo presérvase porque cando a instancia se reinicia despois dun fallo, xa non participa en ningún bloqueo que estea activo actualmente.

Para garantir isto, só necesitamos asegurarnos de que despois dun fallo a instancia non estea dispoñible durante un período de tempo que supere lixeiramente o TTL máximo que utilizamos. Deste xeito agardaremos ata a data de caducidade e liberación automática de todas as claves que estaban activas no momento do fallo.

Usando reinicios atrasados, en principio é posible conseguir a seguridade mesmo en ausencia de calquera persistencia a longo prazo en Redis. Teña en conta, non obstante, que isto pode resultar nunha multa por violar a accesibilidade. Por exemplo, se a maioría das instancias fallan, o sistema non estará dispoñible globalmente para o TTL (e non se pode bloquear ningún recurso durante este tempo).

Aumentamos a dispoñibilidade do algoritmo: ampliamos o bloqueo

Se o traballo realizado polos clientes consiste en pequenos pasos, é posible reducir a duración predeterminada do bloqueo e implementar un mecanismo para estender os bloqueos. En principio, se o cliente está ocupado computando e o valor de caducidade do bloqueo é perigosamente baixo, pode enviar un script Lua a todas as instancias que estenda o TTL da chave se a chave aínda existe e o seu valor aínda é un valor aleatorio obtido cando se adquiriuse o bloqueo.

Un cliente só debería considerar que se volva adquirir un bloqueo se conseguiu bloquear a maioría das instancias dentro do período de validez.

É certo que tecnicamente o algoritmo non cambia, polo que debe limitarse o número máximo de intentos repetidos de adquirir bloqueos, se non, violaranse as propiedades de accesibilidade.

Fonte: www.habr.com

Engadir un comentario