¡Hola, Habr!
Hoy les presentamos la traducción de un artículo complejo sobre la implementación de bloqueos distribuidos utilizando Redis y discutiremos la viabilidad de Redis como tema. Se analiza el algoritmo Redlock de Martin Kleppmann, autor del libro "", y se presenta .
Los bloqueos distribuidos son un primitivo muy útil que se utiliza en muchos entornos donde diferentes procesos deben trabajar en recursos compartidos bajo el principio de exclusión mutua.
Existen varias bibliotecas y publicaciones que describen cómo implementar DLM (gestor de bloqueos distribuidos) utilizando Redis, pero cada biblioteca utiliza un enfoque propio y las garantías que se ofrecen son bastante débiles en comparación con lo que se puede lograr mediante un diseño un poco más complejo.
En este artículo, intentaremos describir un algoritmo que se puede considerar canónico, el cual demuestra cómo implementar bloqueos distribuidos utilizando Redis. Hablaremos del algoritmo llamado Redlock, que implementa un gestor de bloqueos distribuidos y, en nuestra opinión, este algoritmo es más seguro que el enfoque habitual con una única instancia. Esperamos que la comunidad lo analice, brinde retroalimentación y lo utilice como punto de partida para implementar proyectos más complejos o alternativos.
Implementaciones
Antes de pasar a la descripción del algoritmo, brindemos algunos enlaces a implementaciones ya disponibles. Se pueden utilizar como referencia.
- (implementación para Ruby). También existe Redlock-rb, que agrega un paquete (gem) para facilitar la distribución, y no solo para eso.
- (implementación para Python).
- (implementación para Asyncio Python).
- (implementación para PHP).
- (otra implementación para PHP)
- (biblioteca PHP para bloqueos)
- (implementación para Go).
- (implementación para Java).
- (implementación para Perl).
- (implementación para C++).
- (implementación para C#/.NET).
- (implementación para C#/.NET). Con soporte para extensiones asíncronas y bloqueo.
- (implementación para C# .NET con almacenamiento de datos configurable)
- (implementación para C# .NET)
- (implementación para NodeJS). Incluye soporte para la extensión de bloqueos.
Garantías de seguridad y disponibilidad
Vamos a modelar nuestro proyecto con solo tres propiedades que, en nuestra opinión, brindan las garantías mínimas necesarias para el uso efectivo de bloqueos distribuidos.
- Propiedad de seguridad: Exclusión mutua. En cualquier momento, solo un cliente puede mantener un bloqueo.
- Propiedad de disponibilidad A: Ausencia de bloqueos mutuos. Siempre se puede obtener un bloqueo, incluso si el cliente que bloqueó el recurso falla o queda en otro segmento del disco.
- Propiedad de disponibilidad B: Resiliencia. Mientras la mayoría de los nodos de Redis estén funcionando, los clientes podrán adquirir y liberar bloqueos.
Por qué las implementaciones que se basan en la recuperación ante fallos son insuficientes en este caso.
Para entender qué vamos a mejorar, analicemos la situación actual de la mayoría de las bibliotecas para bloqueos distribuidos basadas en Redis.
La forma más sencilla de bloquear un recurso con Redis es crear una clave en la instancia. Normalmente, la clave se crea con un tiempo de vida limitado, esto se logra mediante la opción de expiración que ofrece Redis, por lo que tarde o temprano esta clave se libera (propiedad 2 en nuestra lista). Cuando un cliente necesita liberar el recurso, elimina la clave.
A primera vista, esta solución funciona bastante bien, pero hay un problema: en nuestra arquitectura se genera un único punto de fallo. ¿Qué pasará si la instancia principal de Redis falla? ¡Entonces agreguemos una secundaria! Y la utilizaremos si la principal no está disponible. Desafortunadamente, esa opción no es viable. Al hacer esto, no podremos implementar correctamente la propiedad de exclusión mutua que necesitamos para garantizar la seguridad, ya que la replicación en Redis es asíncrona.
Es evidente que en este modelo se produce una condición de carrera:
- El cliente A adquiere el bloqueo en la instancia principal.
- La instancia principal falla antes de que la escritura en la clave sea transferida a la secundaria.
- La secundaria se convierte en la principal.
- El cliente B adquiere el bloqueo del mismo recurso que ya está bloqueado por A. ¡VIOLACIÓN DE SEGURIDAD!
A veces es completamente normal que, en circunstancias especiales, por ejemplo durante una falla, muchos clientes puedan mantener un bloqueo al mismo tiempo. En tales casos, se puede aplicar una solución basada en replicación. En otros casos, recomendamos la solución descrita en este artículo.
Implementación correcta con una única instancia
Antes de intentar superar las desventajas de la configuración de una única instancia descrita anteriormente, analicemos cómo proceder correctamente en este caso simple, ya que tal solución es aceptable en aquellas aplicaciones donde una condición de carrera sea ocasionalmente permisible, además de que el bloqueo en una única instancia sirve como base para el algoritmo distribuido descrito aquí.
Para adquirir el bloqueo, haremos lo siguiente:
SET resource_name my_random_value NX PX 30000
Este comando establece la clave solo si aún no existe (opción NX), con una duración de 30000 milisegundos (opción PX). Para la clave se establece el valor “myrandomvalue”. Este valor debe ser único entre todos los clientes y todas las solicitudes de bloqueo.
En principio, se utiliza un valor aleatorio para liberar de manera segura el bloqueo, mediante un script que le indica a Redis: elimina la clave solo si existe, y el valor almacenado en ella es exactamente lo que se esperaba. Esto se logra mediante el siguiente script en Lua:
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
endEs importante no permitir que se libere un bloqueo realizado por otro cliente. Por ejemplo, un cliente puede adquirir el bloqueo, luego quedar bloqueado durante alguna operación que dure más que el tiempo de vida del primer bloqueo (de modo que el tiempo de vida de la clave expire), y después liberar un bloqueo que fue establecido por otro cliente.
Usar un simple DEL no es seguro, ya que un cliente podría eliminar un bloqueo establecido por otro cliente. Por el contrario, al utilizar el script anterior, cada bloqueo está 'firmado' con una cadena aleatoria, por lo que solo el cliente que lo estableció inicialmente puede eliminarlo.
¿Cuál debería ser esta cadena aleatoria? Supongo que debería ser de 20 bytes de /dev/urandom, pero hay formas menos costosas de hacer una cadena suficientemente única para los propósitos que tienes. Por ejemplo, estaría bien sembrar RC4 con /dev/urandom y luego generar un flujo pseudoaleatorio basado en eso. Una solución más simple está relacionada con la combinación del tiempo unix en resolución de microsegundos más el ID del cliente; no es tan seguro, pero posiblemente se ajuste al nivel de tareas en la mayoría de contextos.
El tiempo que usamos como indicador de la vida útil de la clave se llama 'tiempo de validez del bloqueo'. Este valor es al mismo tiempo el período después del cual el bloqueo se liberará automáticamente y el tiempo que tiene el cliente para realizar la operación antes de que otro cliente pueda, a su vez, bloquear este recurso, sin violar realmente las garantías de exclusión mutua. Esta garantía está limitada solo a una ventana de tiempo específica, que comienza desde el momento en que se adquiere el bloqueo.
Así que hemos discutido una buena manera de adquirir y liberar un bloqueo. El sistema (si se trata de un sistema no distribuido, compuesto por una única instancia siempre disponible) es seguro. Ampliemos este concepto a un sistema distribuido, en el que no tenemos esas garantías.
Algoritmo Redlock
En la versión distribuida del algoritmo, se supone que tenemos N instancias maestras de Redis. 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 explicado cómo adquirir y liberar un bloqueo de manera segura en una única instancia. Damos por sentado que el algoritmo, al trabajar con una única instancia, utilizará este método. En nuestros ejemplos, establecemos N en 5, que es un valor bastante razonable. Así que necesitaremos usar 5 instancias maestras de Redis en diferentes computadoras o máquinas virtuales para garantizar que actúen principalmente de forma independiente entre sí.
Para adquirir un bloqueo, el cliente realiza las siguientes operaciones:
- Obtiene la hora actual en milisegundos.
- Intenta conseguir el bloqueo de manera secuencial en todas las N instancias, utilizando el mismo nombre de clave y valores aleatorios en todos los casos. En la etapa 2, al establecer el bloqueo para cada instancia, el cliente, para obtenerlo, utiliza un retraso que es bastante 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, el retraso puede estar en el rango de ~ 5-50 milisegundos. De esta manera, se evita la situación en la que el cliente podría estar bloqueado por mucho tiempo tratando de acceder a un nodo Redis que falló: si la instancia no está disponible, intentamos conectarnos con otra instancia lo antes posible.
- Para tomar el bloqueo, el cliente calcula cuánto tiempo ha pasado; para esto, resta del valor actual del tiempo la marca de tiempo obtenida en el paso 1. Entonces, y solo entonces, cuando el cliente ha podido obtener el bloqueo en la mayoría de las instancias (al menos 3), y el tiempo total que tomó obtener el bloqueo es menor que la duración del bloqueo, se considera que la obtención del bloqueo ha tenido éxito.
- Si se ha obtenido el bloqueo, la duración del mismo se considera el valor original de la duración del bloqueo menos el tiempo transcurrido, calculado en el paso 3.
- Si el cliente no ha podido obtener el bloqueo por alguna razón (ya sea porque no pudo bloquear N/2+1 instancias o porque la duración del bloqueo resultó ser negativa), intentará desbloquear todas las instancias (incluso aquellas que creía no poder bloquear).
¿Es el algoritmo asincrónico?
Este algoritmo se basa en la suposición de que, aunque no hay relojes sincronizados que hagan funcionar todos los procesos, el tiempo local en cada proceso todavía avanza aproximadamente al mismo ritmo, y el margen de 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 parecida a la situación común en las computadoras normales: cada computadora tiene su propio reloj local, y generalmente podemos confiar en que la diferencia de tiempo entre diferentes computadoras es pequeña.
En esta etapa, debemos formular más cuidadosamente nuestra regla de exclusión mutua: la exclusión mutua está garantizada solo si el cliente que mantiene el bloqueo completa su tarea dentro del tiempo durante el cual el bloqueo es válido (este valor se obtuvo en el paso 3), menos un tiempo adicional (solo unos milisegundos, para compensar la desviación temporal entre los procesos).
Más información sobre sistemas similares que requieren la conciliación de la desviación temporal se encuentra en el siguiente artículo interesante: .
Reintento en caso de falla
Cuando un cliente no logra obtener un bloqueo, debe intentar nuevamente, esperando un retraso aleatorio; esto se hace con el objetivo de desincronizar a varios clientes que intentan adquirir el bloqueo del mismo recurso al mismo tiempo (lo que puede conducir a una situación de "cerebro dividido", donde no hay ganadores). Además, cuanto más rápido intente el cliente adquirir el bloqueo de la mayoría de las instancias de Redis, más pequeño será el intervalo en el que puede surgir la situación de cerebro dividido (y menor será la necesidad de reintentos). Por lo tanto, idealmente, el cliente debe intentar simultáneamente enviar comandos SET a N instancias mediante multiplexión.
Aquí es importante subrayar cuán esencial es que los clientes que no pudieron adquirir la mayoría de los bloqueos liberen (parcialmente) los bloqueos adquiridos, para que no haya que esperar a que expire la clave antes de que el bloqueo sobre el recurso pueda ser adquirido nuevamente (aunque, si ocurre una fragmentación de red y el cliente pierde la conexión con las instancias de Redis, se incurre en una penalización por violar la disponibilidad, mientras se espera la expiración de la clave).
Liberación del bloqueo
La liberación del bloqueo es una operación simple, que solo requiere desbloquear todas las instancias, independientemente de si el cliente cree haber bloqueado con éxito una instancia específica.
Consideraciones de seguridad
¿Es seguro el algoritmo? Vamos a intentar imaginar qué ocurre en varios escenarios.
Para empezar, supongamos que un cliente ha logrado obtener el bloqueo sobre la mayoría de las instancias. Cada una de las instancias contendrá una clave con el mismo tiempo de vida para todas. Sin embargo, cada una de estas claves fue establecida en su momento, por lo que su tiempo de validez expirará en momentos diferentes. Pero, si la primera clave se estableció en un momento no peor que T1 (el tiempo que elegimos antes de contactar con el primer servidor), y la última clave se estableció en un momento no peor que T2 (el tiempo en que se recibió la respuesta del último servidor), entonces estamos seguros de que la primera clave en el conjunto que expirará, existirá al menos MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Todas las demás claves expirará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 el bloqueo, ya que las operaciones de N/2+1 SET NX no pueden tener éxito si ya existen N/2+1 claves. Por lo tanto, si se adquirió el bloqueo, no se puede volver a obtener en el mismo momento (esto violaría la propiedad de exclusión mutua).
Sin embargo, queremos asegurarnos de que un conjunto de clientes que intentan obtener el bloqueo al mismo tiempo no puedan tener éxito simultáneamente.
Si un cliente bloqueó la mayoría de las instancias, tomando para ello un tiempo igual o mayor que el tiempo máximo de duración del bloqueo, considerará el bloqueo inválido y desbloqueará las instancias. Por lo tanto, solo necesitamos considerar el caso en el que el cliente logró bloquear la mayoría de las instancias en un tiempo menor que la duración. En este caso, en relación con el argumento anterior, durante el tiempo MIN_VALIDITY ningún cliente debería poder volver a obtener el bloqueo. Por lo tanto, un conjunto de clientes podrá bloquear N/2+1 instancias al mismo tiempo (que finaliza en el momento de completar la etapa 2), solo cuando el tiempo para bloquear la mayoría haya sido mayor que el tiempo TTL, lo que convierte el bloqueo en inválido.
¿Podrías proporcionar una prueba formal de seguridad, indicar algoritmos similares existentes o encontrar un error en lo expuesto?
Consideraciones sobre la disponibilidad
La disponibilidad del sistema depende de tres características principales:
- Desbloqueo automático (ya que la validez de las claves expira): al final, las claves estarán disponibles nuevamente para ser utilizadas para desbloqueos.
- El hecho de que los clientes normalmente se ayudan entre sí al desbloquear, cuando no se adquirió el bloqueo necesario, o fue adquirido pero la tarea se completó; por lo tanto, es muy probable que no tengamos que esperar a que las claves expiren para volver a adquirir el bloqueo.
- El hecho de que, cuando un cliente necesita intentar obtener el bloqueo nuevamente, espera un período de tiempo relativamente más largo que el tiempo requerido para adquirir la mayoría de los bloqueos. Esto reduce la probabilidad de que se produzca una situación de cerebro dividido en la competencia por los recursos.
Sin embargo, se debe pagar una penalización por la reducción de la disponibilidad, equivalente al tiempo TTL en los segmentos de red, por lo que si hay segmentos continuos, esta penalización puede adquirir un tamaño indefinido. Esto sucede cada vez que un cliente adquiere un bloqueo y luego se desconecta en otro segmento antes de poder liberarlo.
En principio, con segmentos de red continuos infinitos, el sistema puede permanecer inaccesible durante un período de tiempo infinito.
Rendimiento, recuperación ante fallos y fsync
Muchos utilizan Redis, ya que se requiere asegurar un alto rendimiento del servidor de bloqueos, al nivel de las latencias necesarias 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 N servidores Redis para reducir la latencia. Esta es una estrategia de multiplexión (o 'multiplexión de pobres', donde el socket se pone en modo no bloqueante, envía todos los comandos y lee los comandos más tarde, asumiendo que el tiempo de vuelta entre el cliente y cada una de las instancias es similar).
Sin embargo, también debemos considerar lo relacionado con el almacenamiento a largo plazo de datos, si buscamos crear un modelo con recuperación ante fallos confiable.
En principio, para aclarar el problema, supongamos que configuramos Redis sin almacenamiento persistente de datos. El cliente consigue bloquear 3 de 5 instancias. Una de las instancias que el cliente logró bloquear se reinicia, y en ese momento surgen nuevamente 3 instancias para el mismo recurso que podemos bloquear, y otro cliente podría, a su vez, bloquear la instancia reiniciada, violando la propiedad de seguridad que implica la exclusividad de los bloqueos.
Si habilitamos la persistencia anticipada de datos (AOF), la situación mejora un poco. Por ejemplo, se puede reiniciar el servidor enviando el comando SHUTDOWN y luego reiniciándolo. Dado que las operaciones de expiración en Redis se implementan semánticamente de tal manera que el tiempo sigue avanzando, incluso cuando el servidor está apagado, todo está bien con nuestras solicitudes. Bien, siempre que haya un apagado controlado. ¿Pero qué hacer en caso de cortes de energía? Si Redis está configurado por defecto, sincronizando fsync en el disco cada segundo, es posible que después del reinicio no contemos con nuestra clave. Teóricamente, si queremos garantizar la seguridad de los bloqueos ante cualquier reinicio de instancia, debemos activar fsync=always en la configuración de la persistencia de datos. Esto afectará significativamente el rendimiento, al nivel de esos sistemas CP que tradicionalmente se utilizan 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 mantiene, ya que cuando una instancia se reinicia tras una falla, ya no participa en ningún bloqueo activo en ese momento.
Para garantizar esto, solo es necesario asegurar que tras una falla, la instancia permanezca inaccesible durante un tiempo que exceda ligeramente el máximo TTL que utilizamos. Así esperaremos a que expire el plazo y se liberen automáticamente todas las claves que estaban activas en el momento de la falla.
Usando reinicios diferidos, en principio es posible lograr seguridad incluso sin ninguna persistencia a largo plazo en Redis. Cabe señalar, sin embargo, que esto puede resultar en una penalización por violación de disponibilidad. Por ejemplo, en caso de fallo de la mayoría de las instancias, el sistema se volverá globalmente inaccesible durante el tiempo de TTL (y ningún recurso podrá ser bloqueado en ese tiempo).
Aumentando la disponibilidad del algoritmo: extendemos el bloqueo
Si el trabajo realizado por los clientes consiste en etapas pequeñas, es posible reducir el tiempo de vigencia del bloqueo definido por defecto y activar un mecanismo de extensión de bloqueos. En principio, si el cliente está ocupado en cálculos y el valor de la vigencia del bloqueo disminuye peligrosamente, se puede enviar un script en Lua a todas las instancias 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.
El cliente debe considerar el bloqueo como nuevamente adquirido solo en el caso de que haya logrado bloquear la mayoría de las instancias durante el tiempo de vigencia.
Sin embargo, técnicamente el algoritmo no cambia, por lo que el número máximo de intentos de re-adquisición de bloqueos debe ser limitado, de lo contrario, se violarán las propiedades de disponibilidad.
Fuente: habr.com
