ProHoster > Blog > administración > Bloqueo distribuido usando Redis

Bloqueo distribuido usando Redis

¡Hola, Habr!

Hoy llamamos su atención sobre la traducción de un artículo complejo sobre la implementación del bloqueo distribuido usando Redis y lo invitamos a hablar sobre las perspectivas de Redis como tema. Análisis del algoritmo Redlock en cuestión de Martin Kleppmann, autor del libro "Aplicaciones de carga alta", dado aquí.

El bloqueo distribuido es una primitiva muy útil que se utiliza en muchos entornos donde diferentes procesos deben trabajar en recursos compartidos de manera mutuamente excluyente.

Hay varias bibliotecas y publicaciones que describen cómo implementar DLM (Distributed Lock Manager) usando Redis, pero cada biblioteca adopta un enfoque diferente y las garantías que brindan son bastante débiles en comparación con lo que se puede lograr con un diseño un poco más sofisticado.

En este artículo intentaremos describir un algoritmo canónico condicional que demuestra cómo implementar el bloqueo distribuido usando Redis. Hablaremos de un algoritmo llamado Bloqueo rojo, implementa un administrador de bloqueo distribuido y, en nuestra opinión, este algoritmo es más seguro que el enfoque habitual de instancia única. Esperamos que la comunidad lo analice, proporcione comentarios y lo utilice como punto de partida para proyectos más complejos o alternativos.

Implementación

Antes de pasar a la descripción del algoritmo, proporcionamos varios enlaces a implementaciones listas para usar. Se pueden utilizar como referencia.

Garantías de seguridad y disponibilidad

Vamos a modelar nuestro diseño con solo tres propiedades que creemos que brindan las garantías mínimas necesarias para utilizar eficazmente el bloqueo distribuido.

  1. Bienes de garantía: Exclusión mutua. En un momento dado, sólo un cliente puede mantener el candado.
  2. Disponibilidad Propiedad A: Sin puntos muertos. Siempre es posible adquirir un bloqueo, incluso si el cliente que bloqueó el recurso falla o aterriza en un segmento de disco diferente.
  3. Propiedad de disponibilidad B: Tolerancia a fallos. Mientras la mayoría de los nodos de Redis estén en ejecución, los clientes podrán adquirir y liberar bloqueos.

Por qué la implementación basada en la recuperación de fallos no es suficiente en este caso
Para comprender qué vamos a mejorar, analicemos la situación actual con la mayoría de las bibliotecas de bloqueo distribuidas basadas en Redis.

La forma más sencilla de bloquear un recurso usando Redis es crear una clave en la instancia. Normalmente, se crea una clave 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 publica (propiedad 2 en nuestra lista). Cuando el cliente necesita liberar el recurso, elimina la clave.

A primera vista, esta solución funciona bastante bien, pero hay un problema: nuestra arquitectura crea un único punto de falla. ¿Qué sucede si falla la instancia del host Redis? ¡Entonces agreguemos un esclavo! Y lo usaremos si el presentador no está disponible. Lamentablemente, 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 asíncrona.

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

  1. El cliente A adquiere un bloqueo sobre el maestro.
  2. El maestro falla antes de que la entrada de clave se transfiera al esclavo.
  3. El seguidor asciende a líder.
  4. El cliente B adquiere un bloqueo en el mismo recurso que A ya ha bloqueado. ¡VIOLACIÓN DE SEGURIDAD!

En ocasiones es completamente normal que en circunstancias especiales, como por ejemplo un fallo, muchos clientes puedan sujetar el candado al mismo tiempo. En tales casos, se puede aplicar una solución basada en replicación. De lo contrario, recomendamos la solución descrita en este artículo.

Implementación correcta con una sola instancia.

Antes de intentar superar las deficiencias de la configuración de instancia única descrita anteriormente, comprendamos cómo manejar adecuadamente este caso simple, ya que esta solución es realmente válida en aplicaciones donde una condición de carrera es aceptable de vez en cuando, y también porque el bloqueo en un La instancia única sirve como base que se utiliza en el algoritmo distribuido que se describe aquí.

Para adquirir un candado, haga 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 un período de validez de 30000 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, se utiliza un valor aleatorio para liberar el bloqueo de forma segura, con un script que le dice a Redis: solo elimine la clave si existe y el valor almacenado en ella es exactamente el esperado. Esto se logra usando el siguiente script 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 se elimine un candado retenido por otro cliente. Por ejemplo, un cliente puede adquirir un candado, luego quedar bloqueado en alguna operación que dure más que el primer candado (para que la clave tenga tiempo de caducar) y luego quitar el candado que otro cliente había colocado.
Usar un DEL simple no es seguro porque un cliente puede eliminar un bloqueo que tiene otro cliente. Por el contrario, cuando se utiliza el script anterior, cada candado está "firmado" con una cadena aleatoria, por lo que sólo el cliente que lo colocó previamente puede eliminarlo.

¿Cuál debería ser esta cadena aleatoria? Supongo que debería tener 20 bytes de /dev/urandom, pero puedes encontrar formas menos costosas de hacer que la cadena sea lo suficientemente única para tus propósitos. Por ejemplo, estaría bien inicializar RC4 con /dev/urandom y luego generar una secuencia pseudoaleatoria a partir de él. Una solución más sencilla implica una combinación de tiempo Unix en resolución de microsegundos más el ID del cliente; No es tan seguro, pero probablemente esté a la altura de la tarea en la mayoría de los contextos.

El tiempo que utilizamos como medida de la vida útil de la clave se denomina "vida útil de la cerradura". Este valor es tanto la cantidad de tiempo antes de que el bloqueo se libere automáticamente como la cantidad de tiempo que tiene un cliente para completar una operación antes de que otro cliente pueda, a su vez, bloquear ese recurso, sin violar realmente las garantías de exclusión mutua. Esta garantía está limitada únicamente a un período de tiempo determinado, que comienza desde el momento en que se compra la cerradura.

Por eso, hemos analizado una buena forma de adquirir y liberar un candado. El sistema (si hablamos de un sistema no distribuido 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 de bloqueo rojo

La versión distribuida del algoritmo supone que tenemos N maestros de Redis. Estos nodos son completamente independientes entre sí, por lo que no utilizamos replicación ni ningún otro sistema de coordinación implícito. Ya hemos cubierto cómo adquirir y liberar de forma segura un bloqueo en una sola instancia. Damos por sentado que el algoritmo, cuando trabaje con una sola instancia, utilizará exactamente este método. En nuestros ejemplos establecemos N en 5, que es un valor razonable. Por lo tanto, necesitaremos utilizar 5 maestros de Redis en diferentes computadoras o máquinas virtuales para asegurarnos de que actúen 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. Intenta secuencialmente obtener un bloqueo en todas las N instancias, utilizando el mismo nombre de clave y valores aleatorios en todos los casos. En la etapa 2, cuando el cliente configura un bloqueo por instancia, el cliente utiliza un retraso para adquirirlo que es lo suficientemente corto en comparación con el tiempo después del cual el bloqueo se libera automáticamente. Por ejemplo, si la duración del bloqueo es de 10 segundos, entonces el retraso podría estar en el rango de ~5 a 50 milisegundos. Esto elimina la situación en la que el cliente podría permanecer bloqueado durante mucho tiempo intentando llegar a un nodo de Redis fallido: si la instancia no está disponible, intentamos conectarnos a otra instancia lo antes posible.
  3. Para tomar un candado, el cliente calcula cuánto tiempo ha transcurrido; Para hacer esto, resta del valor de tiempo real la marca de tiempo que se obtuvo en el paso 1. Si y solo si el cliente pudo obtener el bloqueo en la mayoría de las instancias (al menos 3), y el tiempo total que tomó Para obtener el bloqueo, es menor que la duración del bloqueo y se considera que se ha obtenido el bloqueo.
  4. Si se ha adquirido un bloqueo, la duración del bloqueo se considera la duración del bloqueo original menos el tiempo transcurrido calculado en el paso 3.
  5. Si el cliente no puede obtener el bloqueo por algún motivo (ya sea que no pudo bloquear N/2+1 instancias o que la duración del bloqueo fue negativa), intentará desbloquear todas las instancias (incluso aquellas que pensó que no podía bloquear). ).

¿El algoritmo es asíncrono?

Este algoritmo se basa en la suposición de que, aunque no existe un reloj sincronizado en el que funcionen todos los procesos, la hora local en cada proceso sigue fluyendo aproximadamente al mismo ritmo y el error es pequeño en comparación con el tiempo total después del cual se activa el bloqueo. liberado automáticamente. Esta suposición es muy similar a la situación típica de las computadoras comunes: cada computadora tiene un reloj local y generalmente podemos contar con el hecho de que la diferencia horaria entre diferentes computadoras es pequeña.

En este punto, debemos formular con más cuidado nuestra regla de exclusión mutua: la exclusión mutua está garantizada sólo si el cliente que mantiene el candado sale durante el tiempo que el candado es válido (este valor se obtiene en el paso 3), menos un poco más de tiempo (en total unos cuantos). milisegundos para compensar la diferencia de tiempo entre procesos).

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

Reintentar en caso de error

Cuando un cliente no logra adquirir un bloqueo, debe intentarlo nuevamente después de un retraso aleatorio; esto se hace para desincronizar varios clientes que intentan adquirir un bloqueo en el mismo recurso al mismo tiempo (lo que puede llevar a una situación de "cerebro dividido" en la que no hay ganadores). Además, cuanto más rápido un cliente intente 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 menor será la necesidad de reintentos). Por lo tanto, idealmente, el cliente debería intentar enviar comandos SET a N instancias simultáneamente mediante multiplexación.

Vale la pena enfatizar aquí lo importante que es para los clientes que no logran adquirir la mayoría de los bloqueos liberar los bloqueos (parcialmente) adquiridos, para que no tengan que esperar a que la clave caduque antes de poder adquirir nuevamente el bloqueo del recurso. (aunque si se produce una fragmentación de la red y el cliente pierde el contacto con las instancias de Redis, deberá pagar una penalización de disponibilidad mientras espera que caduque la clave).

Liberar el bloqueo

Liberar un bloqueo es una operación simple que simplemente requiere desbloquear todas las instancias, independientemente de si el cliente parece haber bloqueado exitosamente una instancia en particular.

Consideraciones de Seguridad

¿Es seguro el algoritmo? Intentemos imaginar qué sucede en diferentes escenarios.

Para empezar, supongamos que el cliente pudo obtener un bloqueo en la mayoría de los casos. Cada instancia contendrá una clave con la misma duración para todas. Sin embargo, cada una de estas claves se instaló en un momento diferente, por lo que caducarán en momentos diferentes. Pero, si la primera clave se instaló en un momento no peor que T1 (el momento que elegimos antes de contactar al primer servidor), y la última clave se instaló en un momento no peor que T2 (el momento en que se recibió la respuesta del último servidor), entonces estamos seguros de que la primera clave del conjunto que caduque sobrevivirá al menos MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Todas las demás claves caducan más tarde, por lo que podemos estar seguros de que todas las claves serán válidas simultáneamente al menos durante este tiempo.

Durante el tiempo que la mayoría de las claves sigan siendo válidas, otro cliente no podrá adquirir el bloqueo, ya que las operaciones N/2+1 SET NX no pueden tener éxito si ya existen N/2+1 claves. Por tanto, una vez adquirido un candado, es imposible volver a adquirirlo en el mismo momento (esto violaría la propiedad de exclusión mutua).
Sin embargo, queremos asegurarnos de que varios clientes que intenten adquirir un candado al mismo tiempo no puedan tener éxito al mismo tiempo.

Si el cliente ha bloqueado la mayoría de las instancias durante aproximadamente o más de la duración máxima del bloqueo, considerará que el bloqueo no es válido y desbloqueará las instancias. Por tanto, sólo hay que tener en cuenta el caso en el que el cliente logró bloquear la mayoría de instancias en un tiempo inferior a la fecha de vencimiento. En este caso, respecto del argumento anterior, durante el tiempo MIN_VALIDITY ningún cliente debería poder recuperar el candado. Por lo tanto, muchos clientes podrán bloquear N/2+1 instancias al mismo tiempo (que finaliza al final de la etapa 2) solo cuando el tiempo para bloquear la mayoría sea mayor que el tiempo TTL, lo que invalida el bloqueo.

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

Consideraciones de accesibilidad

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

  1. Liberar candados automáticamente (a medida que las llaves caducan): las llaves eventualmente volverán a estar disponibles para usarse en candados.
  2. El hecho de que los clientes suelen ayudarse unos a otros quitando cerraduras cuando la cerradura deseada no ha sido adquirida, o ha sido adquirida y el trabajo ha finalizado; por lo que es probable que no tengamos que esperar a que caduquen las llaves para volver a adquirir el candado.
  3. El hecho de que cuando un cliente necesita volver a intentar adquirir un candado, espera un tiempo comparativamente más largo que el requerido para adquirir la mayoría de los candados. Esto reduce la probabilidad de que surja una situación de división del cerebro al competir por recursos.

Sin embargo, existe una penalización de disponibilidad igual al TTL de los segmentos de la red, por lo que si hay segmentos contiguos la penalización puede ser indefinida. Esto ocurre cada vez que un cliente adquiere un candado y luego lo arranca a otro segmento antes de poder liberarlo.

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

Rendimiento, conmutación por error y fsync

Muchas personas usan Redis porque necesitan un alto rendimiento del servidor de bloqueo en términos de la latencia requerida para adquirir y liberar bloqueos, y la cantidad de adquisiciones/liberaciones que se pueden completar por segundo. Para cumplir con este requisito, existe una estrategia para comunicarse con los servidores N Redis para reducir la latencia. Esta es una estrategia de multiplexación (o "multiplexación del pobre", donde el socket se pone 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) .

Sin embargo, también debemos tener en cuenta las consideraciones asociadas con el almacenamiento de datos a largo plazo si nos esforzamos por crear un modelo con recuperación confiable de fallas.

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

Si habilita los datos por delante (AOF), la situación mejorará ligeramente. Por ejemplo, puede promocionar un servidor enviando el comando SHUTDOWN y reiniciándolo. Dado que las operaciones de caducidad en Redis se implementan semánticamente de tal manera que el tiempo continúa fluyendo incluso cuando el servidor está apagado, todos nuestros requisitos están bien. Esto es normal siempre que se garantice un apagado normal. ¿Qué hacer en caso de cortes de energía? Si Redis está configurado de forma predeterminada, con fsync sincronizándose en el disco cada segundo, entonces es posible que después de reiniciar no tengamos nuestra clave. Teóricamente, si queremos garantizar la seguridad del bloqueo durante el reinicio de cualquier instancia, deberíamos habilitar fsync=always en la configuración para el almacenamiento de datos a largo plazo. Esto acabará por completo con el rendimiento, hasta el nivel de los sistemas CP que se utilizan tradicionalmente para implementar bloqueos distribuidos de forma segura.

Pero la situación es mejor de lo que parece a primera vista. En principio, la seguridad del algoritmo se preserva porque cuando la instancia se reinicia después de un error, ya no participa en ningún bloqueo que esté activo actualmente.

Para garantizar esto, solo debemos asegurarnos de que después de un error la instancia permanezca no disponible durante un período de tiempo que supere ligeramente el TTL máximo que utilizamos. De esta forma esperaremos hasta la fecha de vencimiento y liberación automática de todas las claves que estaban activas en el momento del fallo.

Al utilizar reinicios retrasados, en principio es posible lograr seguridad incluso en ausencia de persistencia a largo plazo en Redis. Sin embargo, tenga en cuenta que esto puede resultar en una multa por violar la accesibilidad. Por ejemplo, si la mayoría de las instancias fallan, el sistema dejará de estar disponible globalmente para el TTL (y no se podrá bloquear ningún recurso durante este tiempo).

Aumentamos la disponibilidad del algoritmo: ampliamos el bloqueo

Si el trabajo realizado por los clientes consta de pequeños pasos, es posible reducir la duración del bloqueo predeterminado e implementar un mecanismo para extender los bloqueos. En principio, si el cliente está ocupado computando y el valor de vencimiento del bloqueo es peligrosamente bajo, puede enviar un script Lua a todas las instancias que extienda el TTL de la clave si la clave aún existe y su valor sigue siendo un valor aleatorio obtenido cuando la Se adquirió el candado.

Un cliente sólo debe considerar que se vuelve a adquirir un bloqueo si ha logrado bloquear la mayoría de las instancias dentro del período de validez.

Es cierto que técnicamente el algoritmo no cambia, por lo que se debe limitar el número máximo de intentos repetidos de adquirir bloqueos; de lo contrario, se violarán las propiedades de accesibilidad.

Fuente: habr.com

Añadir un comentario