Clever Geek Handbook

Cerraduras distribuidas con Redis

¡Hola, Habr!



Hoy traemos a su atención una traducción de un artículo complejo sobre la implementación de bloqueos distribuidos utilizando Redis y proponemos hablar sobre las perspectivas de Redis como tema. Un análisis del algoritmo Redlock considerado desde Martin Kleppman, autor del libro "alta carga aplicaciones se da", aquí .





Los bloqueos distribuidos son una primitiva muy útil que se utiliza en muchos entornos donde diferentes procesos deben trabajar en recursos compartidos de una manera mutuamente excluyente.



Hay una serie de bibliotecas y publicaciones que describen cómo implementar un DLM (Administrador de bloqueo distribuido) con Redis, pero cada biblioteca adopta un enfoque diferente y las garantías proporcionadas son débiles en comparación con lo que se puede lograr con un diseño un poco más complejo.



En este artículo, intentaremos describir un algoritmo canónico condicional que demuestra cómo implementar bloqueos distribuidos con Redis. Hablaremos de un algoritmo llamado Redlock, implementa un administrador de bloqueo distribuido y, en nuestra opinión, este algoritmo es más seguro que el enfoque convencional de instancia única. Esperamos que la comunidad lo analice, dé su opinión y lo utilice como punto de partida para la implementación de proyectos más complejos o alternativos.



Implementaciones



Antes de continuar con la descripción del algoritmo, aquí hay algunos enlaces a implementaciones listas para usar. Se pueden utilizar como referencia.







Garantías de seguridad y disponibilidad



Vamos a simular nuestro diseño con solo tres propiedades que creemos brindan las garantías mínimas requeridas para utilizar de manera efectiva las cerraduras distribuidas.



  1. Propiedad de seguridad: Exclusión mutua. Solo un cliente puede mantener un candado a la vez.
  2. Propiedad de accesibilidad A: Sin puntos muertos. Al final, siempre puede obtener un bloqueo, incluso si el cliente que bloqueó el recurso falla o termina en otro segmento de disco.
  3. Propiedad de accesibilidad B: tolerancia a fallos. Mientras la mayoría de los nodos de Redis se están ejecutando, los clientes pueden adquirir y liberar bloqueos.




Por qué una implementación basada en failover no es suficiente en este caso

Para comprender qué vamos a mejorar, analicemos el estado actual de la mayoría de las bibliotecas de bloqueo distribuidas basadas en Redis.



La forma más sencilla de bloquear un recurso con Redis es crear una clave en una instancia. Por lo general, una clave se crea con una vida útil limitada, esto se logra utilizando la función de caducidad proporcionada en Redis, por lo que tarde o temprano esta clave se libera (propiedad 2 en nuestra lista). Cuando el cliente necesita liberar el recurso, elimina la clave.



A primera vista, esta solución funciona bien, pero hay un problema: hay un solo punto de falla en nuestra arquitectura. ¿Qué sucede si falla la instancia principal de Redis? ¡Agreguemos un seguidor entonces! Y lo usaremos si el host no está disponible. Desafortunadamente, esta opción no es viable. Al hacer esto, no podremos implementar correctamente la propiedad de exclusión mutua que necesitamos para garantizar la seguridad, porque la replicación en Redis es asincrónica.



Obviamente, se produce una condición de carrera en este modelo:

  1. El cliente A adquiere un candado en el maestro.
  2. El maestro falla antes de que la escritura en la clave se transfiera al esclavo.
  3. El seguidor es ascendido a líder.
  4. El cliente B adquiere un bloqueo en el mismo recurso que ya está bloqueado por A. ¡VIOLACIÓN DE SEGURIDAD!




A veces es perfectamente normal que en circunstancias especiales, como una falla, varios clientes puedan mantener un bloqueo al mismo tiempo. En tales casos, puede aplicar una solución basada en replicación. De lo contrario, recomendamos la solución descrita en este artículo.



Implementación correcta de una sola instancia



Antes de intentar superar las deficiencias de la configuración de una sola instancia descrita anteriormente, descubramos cómo manejar este caso simple, ya que esto es realmente aceptable en aplicaciones donde las condiciones de carrera son ocasionalmente aceptables, y también porque el bloqueo en una sola instancia sirve como base para el algoritmo distribuido que se describe aquí.



Para adquirir un candado, hagamos esto:



SET resource_name my_random_value NX PX 30000



Este comando instala una clave solo si aún no existe (opción NX), con una fecha de caducidad de 30.000 milisegundos (opción PX). La clave está configurada en “ myrandomvalue”. Este valor debe ser único en todos los clientes y en todas las solicitudes de bloqueo.

Básicamente, el valor aleatorio se usa para liberar el bloqueo de manera segura, con un script que le dice a Redis que solo elimine la clave si existe y el valor almacenado en ella es exactamente lo que se esperaba. Esto se logra con el siguiente script de Lua: 



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




Esto es importante para evitar que otro cliente libere un bloqueo. Por ejemplo, un cliente puede adquirir un candado, luego bloquear una operación que dura más que el primer candado (para que la llave tenga tiempo de caducar) y luego quitar el candado que otro cliente ha colocado.

No es seguro utilizar un DEL simple porque un cliente puede eliminar un bloqueo retenido por otro cliente. Por el contrario, cuando se utiliza el script anterior, cada candado se "firma" con una cadena aleatoria, por lo que solo el cliente que lo colocó anteriormente puede eliminarlo.



¿Cuál debería ser esta cadena aleatoria? Supongo que debería ser de 20 bytes de / dev / urandom, pero puede encontrar formas menos costosas de hacer que la cadena sea lo suficientemente única para el propósito que está tratando de lograr. Por ejemplo, estaría bien sembrar RC4 con / dev / urandom y luego generar un flujo pseudoaleatorio basado en él. Una solución más simple implica combinar microsegundos de tiempo Unix más ID de cliente; no es tan seguro, pero quizás esté al nivel del desafío en la mayoría de los contextos.



El tiempo que usamos como medida de la vida útil de la clave se denomina "tiempo de caducidad del bloqueo". Este valor es tanto el tiempo después del cual el bloqueo se liberará automáticamente como el tiempo que el cliente tiene para completar la operación antes de que otro cliente pueda, a su vez, bloquear el recurso sin violar realmente las garantías de exclusión mutua. Dicha garantía se limita solo a una cierta ventana de tiempo, que comienza desde el momento de adquirir la cerradura.



Así que discutimos una buena forma de adquirir y liberar un candado. El sistema (si estamos hablando de un sistema no asignado que consta de una instancia única y siempre disponible) es seguro. Extendamos este concepto a un sistema distribuido donde no tenemos tales garantías.



Algoritmo Redlock



La versión distribuida del algoritmo asume que tenemos N Redis líder. Estos nodos son completamente independientes entre sí, por lo que no usamos replicación ni ningún otro sistema de coordinación implícito. Ya hemos cubierto cómo adquirir y liberar bloqueos de forma segura en una sola instancia. Damos por sentado que el algoritmo utilizará este método cuando trabaje con una sola instancia. En nuestros ejemplos, establecemos N en 5, que es un valor perfectamente razonable. Por lo tanto, necesitaremos ejecutar 5 maestros de Redis en diferentes computadoras o máquinas virtuales para asegurarnos de que funcionen en gran medida de forma independiente entre sí.



Para adquirir un candado, el cliente realiza las siguientes operaciones:



  1. Obtiene la hora actual en milisegundos.
  2. N , . 2, , , , , , . , 10 , ~ 5-50 . , , Redis: , .
  3. , , ; , 1. , ( 3), , , , , , .
  4. , , 3.
  5. - ( N/2+1 , ), ( , , , ).




¿Es el algoritmo asincrónico?



Este algoritmo se basa en el supuesto de que, aunque no hay un reloj sincronizado en el que funcionen todos los procesos, la hora local en cada proceso sigue fluyendo aproximadamente a la misma velocidad y el error es pequeño en comparación con el tiempo total después del cual el bloqueo se libera automáticamente. Esta suposición es muy similar a la situación típica de las computadoras ordinarias: cada computadora tiene un reloj local y, por lo general, podemos contar con el hecho de que la diferencia horaria en diferentes computadoras es pequeña.



En esta etapa, debemos formular cuidadosamente nuestra regla de exclusión mutua: la exclusión mutua está garantizada solo si el cliente que tiene el bloqueo se completa dentro del tiempo durante el cual el bloqueo es válido (este valor se obtuvo en el paso 3), menos un poco más de tiempo (total varios milisegundos para compensar la diferencia de tiempo entre procesos).



El siguiente artículo interesante brinda más información sobre los sistemas que requieren un intervalo de tiempo: Arrendamientos: un mecanismo eficiente tolerante a fallas para la coherencia de la caché de archivos distribuidos .



Reintentar si falla



Cuando el cliente no logra adquirir el candado, debe intentar hacerlo nuevamente, con un retraso ocasional; esto se hace para sincronizar varios clientes simultáneamente que intentan adquirir un bloqueo en el mismo recurso (lo que puede llevar a una situación de cerebro dividido en la que no hay ganadores). Además, cuanto más rápido intente el cliente adquirir un bloqueo en la mayoría de las instancias de Redis, más estrecha será la ventana en la que puede ocurrir una situación de cerebro dividido (y se requieren menos reintentos). Por lo tanto, idealmente, el cliente debería intentar enviar comandos SET a N instancias al mismo tiempo utilizando multiplexación.



Vale la pena enfatizar aquí lo importante que es para los clientes que no han podido adquirir la mayoría de los bloqueos liberar (parcialmente) los bloqueos adquiridos para que no tengan que esperar la fecha de vencimiento de la clave antes de que el bloqueo en el recurso pueda adquirirse nuevamente (aunque si se produce la fragmentación de la red). y el cliente pierde contacto con las instancias de Redis, entonces debe pagar una multa por infracción de acceso mientras la clave expira).



Liberar un bloqueo



Liberar un bloqueo es una operación simple que simplemente requiere desbloquear todas las instancias, independientemente de si el cliente cree que pudo bloquear con éxito una instancia en particular.



Consideraciones de seguridad



¿Es seguro el algoritmo? Intentemos imaginar lo que sucede en diferentes escenarios.



Primero, supongamos que el cliente pudo adquirir el bloqueo en la mayoría de las instancias. Cada una de las instancias contendrá una clave con la misma duración para todos. Sin embargo, cada una de estas claves se instaló en su propio momento, por lo que caducarán en diferentes momentos. Pero, si la primera clave se instaló en un momento no peor que T1 (el momento que elegimos antes de contactar con el primer servidor), y la última clave se instaló en un momento no peor que T2 (el momento en que se recibió una respuesta del último servidor), entonces están seguros de que la primera clave del conjunto que caduca durará al menosMIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT... Todas las demás claves caducarán más tarde, por lo que podemos estar seguros de que todas las claves serán válidas simultáneamente durante al menos este tiempo.



Durante el tiempo en que la mayoría de las claves permanezcan válidas, otro cliente no podrá adquirir la cerradura, ya que las operaciones N / 2 + 1 SET NX no pueden tener éxito si las claves N / 2 + 1 ya existen. Por lo tanto, si se adquirió el bloqueo, entonces es imposible volver a adquirirlo en el mismo momento (esto violaría la propiedad de exclusión mutua).

Sin embargo, queremos asegurarnos de que muchos clientes que intentan adquirir un candado simultáneamente no puedan tener éxito al mismo tiempo.



Si el cliente ha bloqueado la mayoría de las instancias, gastando aproximadamente o más que la duración máxima del bloqueo para este tiempo, invalidará el bloqueo y desbloqueará las instancias. Por lo tanto, solo tenemos que considerar el caso en el que el cliente pudo bloquear la mayoría de las instancias en menos de la fecha de vencimiento. En este caso, con respecto al argumento anterior, MIN_VALIDITYningún cliente debería poder volver a adquirir el bloqueo a tiempo. Por lo tanto, varios clientes podrán bloquear instancias N / 2 + 1 en la misma cantidad de tiempo (que finaliza al final de la etapa 2) solo cuando el tiempo para bloquear la mayoría fue mayor que el tiempo TTL, lo que invalida el bloqueo.



¿Puede proporcionar una prueba formal de seguridad, señalar algoritmos similares existentes o encontrar un error en lo anterior?



Consideraciones de



disponibilidad La disponibilidad del sistema depende de tres características principales:



  1. Liberación automática de cerraduras (a medida que caducan las llaves): Con el tiempo, las llaves estarán disponibles nuevamente para ser utilizadas como cerraduras.
  2. El hecho de que los clientes usualmente se ayudan entre sí quitando candados cuando el candado deseado no fue adquirido o fue adquirido y el trabajo está terminado; por lo tanto, es probable que no tengamos que esperar a que caduquen las llaves para volver a adquirir la cerradura.
  3. El hecho de que cuando un cliente necesita volver a intentar adquirir una cerradura, espera un tiempo relativamente más largo que el que tarda en adquirir la mayoría de las cerraduras. Esto reduce la probabilidad de una situación de cerebro dividido cuando se compite por recursos.




Sin embargo, debe pagar una penalización por disponibilidad reducida igual al tiempo TTL en los segmentos de red, por lo que si hay segmentos contiguos, esta penalización puede llegar a ser de un tamaño indefinido. Esto sucede siempre que un cliente adquiere un candado y luego se sujeta a otro segmento antes de que pueda liberarlo.



En principio, dados infinitos segmentos de red contiguos, el sistema puede permanecer indisponible durante un período de tiempo infinito.



Rendimiento, conmutación por error y fsync



Muchas personas usan Redis porque necesitan proporcionar un alto rendimiento del servidor de bloqueo, en el nivel de latencia requerido para adquirir y liberar bloqueos, así como el número de operaciones de adquisición / liberación que se pueden realizar por segundo. Para cumplir con este requisito, existe una estrategia de comunicación con los servidores N Redis para reducir la latencia. Esta es una estrategia de multiplexación (o multiplexación del pobre, que pone el socket en modo sin bloqueo, envía todos los comandos y lee los comandos más tarde, asumiendo que el tiempo de ida y vuelta entre el cliente y cada instancia es similar).



Es cierto que también hay que considerar el almacenamiento a largo plazo si queremos crear un modelo con recuperación confiable de fallas.



Básicamente, para aclarar el problema, supongamos que estamos configurando Redis sin ningún almacenamiento de datos a largo plazo. El cliente logra bloquear 3 de cada 5 instancias. Se reinicia una de las instancias que el cliente logró bloquear, y en este momento vuelven a aparecer 3 instancias para el mismo recurso, que podemos bloquear, y el otro cliente puede, a su vez, bloquear la instancia reiniciada, violando la propiedad de seguridad que implica exclusividad de cerraduras.



Si habilita la conservación de datos (AOF), la situación mejorará ligeramente. Por ejemplo, puede promover el servidor enviando el comando APAGAR y luego reiniciarlo. Dado que las operaciones de expiración en Redis se implementan semánticamente de tal manera que el tiempo continúa fluyendo incluso cuando el servidor está apagado, todo está bien con todos nuestros requisitos. Normal siempre que se asegure el apagado normal. ¿Qué hacer en caso de cortes de energía? Si Redis está configurado por defecto, con fsync sincronizándose en disco cada segundo, entonces es posible que luego de reiniciar perdamos nuestra clave. En teoría, si queremos garantizar la seguridad de los bloqueos en cualquier reinicio de la instancia, debemos habilitarfsync=alwaysen la configuración para el almacenamiento de datos a largo plazo. Esto acabará por completo con el rendimiento, al nivel de los sistemas CP que se utilizan tradicionalmente para implementar de forma segura bloqueos distribuidos.



Pero la situación es mejor de lo que parece. En principio, el algoritmo permanece seguro porque cuando una instancia se reinicia después de una falla, ya no participa en ningún bloqueo activo actualmente.



Para garantizar esto, solo necesitamos asegurarnos de que después de una falla, la instancia no esté disponible por un período de tiempo que exceda ligeramente el TTL máximo que estamos usando. Por lo que esperaremos el vencimiento y liberación automática de todas las claves que estaban activas en el momento del rechazo.



Al usar reinicios diferidos, en principio es posible lograr seguridad sin ninguna persistencia a largo plazo en Redis. Sin embargo, tenga en cuenta que esto puede resultar en una penalización de accesibilidad. Por ejemplo, si la mayoría de las instancias fallan, el sistema dejará de estar disponible globalmente durante el tiempo de TTL (y no se puede bloquear ningún recurso en este momento).



Incrementar la disponibilidad del algoritmo: extender el bloqueo



Si el trabajo realizado por los clientes consta de pequeños pasos, entonces es posible acortar la duración del bloqueo predeterminado e implementar un mecanismo para extender los bloqueos. Básicamente, si el cliente está ocupado con los cálculos y el valor de vencimiento del bloqueo es peligrosamente bajo, puede enviar a todas las instancias un script en Lua para extender el TTL de la clave, si la clave aún existe, y su valor sigue siendo aleatorio obtenido cuando se adquirió el bloqueo.



Un cliente debe considerar un candado como readquirido solo si ha bloqueado exitosamente la mayoría de las instancias durante el período de validez.



Sin embargo, técnicamente, el algoritmo no cambia en este caso, por lo que el número máximo de intentos repetidos para adquirir bloqueos debe ser limitado, de lo contrario se violarán las propiedades de accesibilidad.


More articles:


All Articles