Candado rojo de Redis
En la versión distribuida de este algoritmo, asumimos que hay N nodos maestros de Redis. Los nodos son completamente independientes, por lo que no utilizamos replicación ni ningún otro sistema de coordinación implícito. Hemos cubierto cómo adquirir y liberar bloqueos de forma segura en una sola instancia. Lógicamente podemos suponer que el algoritmo utilizará este método para adquirir y liberar bloqueos en una sola instancia. En nuestro ejemplo, configuramos N=5, que es un valor razonable, por lo que necesitamos ejecutar 5 nodos maestros de Redis en diferentes máquinas o máquinas virtuales para asegurarnos de que fallen de una manera en gran medida independiente.
Para adquirir el bloqueo, el cliente realiza las siguientes operaciones:
Este algoritmo se basa en el supuesto de que, aunque los relojes no están sincronizados entre procesos, la hora local de cada proceso es aproximadamente La La misma tasa de actualización, el margen de error es muy pequeño en comparación con el tiempo que lleva liberar automáticamente el bloqueo. Esta suposición es muy similar a la de las computadoras del mundo real: cada computadora tiene un reloj local y, por lo general, podemos confiar en una desviación de reloj muy pequeña entre diferentes computadoras.
En este punto, necesitamos especificar mejor las reglas de exclusión mutua: siempre que el cliente que posee el candado finalice su trabajo dentro del tiempo de validez del candado (obtenido en el paso 3) y reduzca el tiempo dado. (sólo unos pocos milisegundos para compensar la desviación del reloj entre procesos), la regla de exclusión mutua está garantizada.
Este artículo contiene más información sobre sistemas similares que requieren una deriva de reloj limitada: Arrendamiento: Tolerancia eficiente a fallos para la coherencia de la caché de archivos distribuidos.
Cuando un cliente no logra adquirir un bloqueo, debe volver a intentarlo después de un retraso aleatorio para intentar desincronizar varios clientes que intentan adquirir un bloqueo en el mismo recurso al mismo tiempo (esto puede llevar a una situación de lluvia de ideas). es decir, nadie gana). Además, cuanto más rápido un cliente intenta adquirir un bloqueo en la mayoría de las instancias de Redis, más pequeña es la ventana para que ocurra una situación de cerebro dividido (y la necesidad de volver a intentarlo), por lo que idealmente los clientes deberían intentar usar la multiplexación para enviar simultáneamente comandos SET a N instancias.
Vale la pena enfatizar que para un cliente que no logra adquirir la mayoría de los candados, es muy importante liberar (parte de) los candados adquiridos lo antes posible para que no tenga que esperar. la clave secreta antes de volver a adquirir la clave de bloqueo caduca (sin embargo, si se produce una partición de red y el cliente ya no puede comunicarse con la instancia de Redis, tendrá que pagar una penalización de disponibilidad mientras espera que caduque la clave).
Liberar un bloqueo es muy simple y se puede realizar independientemente de si el cliente cree que puede bloquear con éxito una instancia determinada.
¿Es seguro este algoritmo? Veamos qué sucede en diferentes escenarios de aplicación.
Primero, asumimos que el cliente puede adquirir el candado en la mayoría de los casos. Todas las instancias contendrán una clave válida por el mismo tiempo. Sin embargo, las claves se configuran en momentos diferentes, por lo que caducan en momentos diferentes. Sin embargo, si la primera clave está configurada en el peor momento T1 (el tiempo de muestreo antes de que contactemos al primer servidor antes del muestreo), y la última clave está configurada en el peor momento T2 (el momento en que recibimos una respuesta del último servidor) está configurado en el peor, entonces podemos estar seguros de que la primera clave caducada del conjunto de claves caducará al menos en . Todas las demás claves caducarán más tarde, por lo que podemos estar seguros de que al menos esta vez todas caducarán al mismo tiempo. está configurado. MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT
Durante el tiempo que la mayoría de las claves estén configuradas, otros clientes no podrán adquirir el candado porque si ya existen N/2 1 claves, N/2 1 La operación SET NX no tendrá éxito. Por lo tanto, si se adquiere un candado, es imposible volver a adquirirlo al mismo tiempo (violando la propiedad de exclusión mutua).
Sin embargo, también queremos asegurarnos de que varios clientes que intentan adquirir el candado al mismo tiempo no lo consigan al mismo tiempo.
Si el cliente bloquea la mayoría de las instancias por un tiempo cercano o mayor que el tiempo máximo de validez del bloqueo (que básicamente usamos para el TTL de SET), el cliente considerará que el bloqueo no es válido y lo desbloqueará. esas instancias, por lo que solo necesitamos considerar el caso en el que el cliente puede bloquear la mayoría de las instancias por menos del tiempo efectivo. En este caso, ningún cliente podrá volver a adquirir el candado según los parámetros anteriores. Por lo tanto, varios clientes pueden bloquear N/2 1 instancias al mismo tiempo solo si el tiempo que la mayoría de las instancias están bloqueadas es mayor que el tiempo TTL ("tiempo" se refiere a la hora de finalización del paso 2), lo que hace que el bloqueo deje de ser válido. MIN_VALIDITY
La actividad del sistema se basa en tres funciones principales:
Sin embargo, pagamos una pérdida de disponibilidad igual al tiempo TTL de la partición de red, por lo que si hay particiones consecutivas, podemos continuar indefinidamente. Paga este precio. Esto sucede cada vez que un cliente adquiere un bloqueo y particiona antes de poder eliminar el bloqueo.
Básicamente, si hay infinitas particiones de red contiguas, el sistema no estará disponible durante un período de tiempo infinito.
Muchos usuarios de Redis como servidor de bloqueo necesitan un alto rendimiento en términos de latencia para adquirir y liberar bloqueos y la cantidad de operaciones de adquisición/liberación que se pueden realizar por segundo. Para cumplir con este requisito, la estrategia para hablar con los servidores N Redis para reducir la latencia es, sin duda, la multiplexación (ponga el socket en modo sin bloqueo, envíe todos los comandos y luego lea todos los comandos, asumiendo que el cliente y cada El RTT entre instancias es similar ).
Sin embargo, si deseamos adoptar un modelo de sistema de recuperación de fallos, hay otra consideración en términos de durabilidad.
Básicamente, para entender el problema aquí, supongamos que Redis está configurado sin persistencia alguna. El cliente adquirió el candado en 3 de cada 5 casos. Una de las instancias en las que el cliente pudo adquirir el bloqueo se reinició, momento en el cual podríamos tener 3 instancias bloqueadas para el mismo recurso y otro cliente podría bloquearlo nuevamente, violando la propiedad de seguridad de la exclusividad del bloqueo.
La situación mejorará si habilitamos la persistencia de AOF. Por ejemplo, podemos actualizar un servidor enviando un comando SHUTDOWN al servidor y reiniciándolo. Dado que la caducidad de Redis se implementa semánticamente, cuando el servidor está inactivo, el tiempo todavía pasa, por lo que todos nuestros requisitos están bien. Sin embargo, siempre que apagues el servidor limpiamente, todo estará bien. ¿Qué hacer si hay un corte de energía? Si Redis está configurado para sincronizarse en el disco una vez por segundo (de forma predeterminada), es posible que nuestras claves se pierdan al reiniciar. En teoría, si queremos que el bloqueo sea seguro en cualquier tipo de reinicio de instancia, debemos habilitar esta función en la configuración de persistencia. fsync=always
Sin embargo, la situación es mucho mejor de lo que parece a primera vista. Básicamente, siempre que la instancia se reinicie después de un fallo, ya no participa en ningún bloqueo actualmente activo y se preserva la seguridad del algoritmo. Esto significa que cuando se reinicia una instancia, el conjunto de bloqueos actualmente activo se obtiene bloqueando instancias distintas de la instancia que se reincorporó al sistema.
Para garantizar esto, simplemente hacemos que la instancia no esté disponible después de que falla, al menos un poco más que el TTL máximo que utilizamos. Este es el tiempo necesario para que todas las claves de la cerradura que estaban presentes cuando la instancia falló caduquen y se liberen automáticamente.
Al retrasar los reinicios, es más seguro usar Redis incluso cuando no hay persistencia de Redis disponible, pero tenga en cuenta que esto puede resultar en una pérdida de disponibilidad. Por ejemplo, si la mayoría de las instancias fallan, el sistema no estará disponible globalmente en TTL (global significa que no se puede bloquear ningún recurso durante este período).
Si el trabajo realizado por el cliente consta de pasos más pequeños, puede utilizar un período de validez de bloqueo más pequeño de forma predeterminada y ampliar el algoritmo que implementa el mecanismo de extensión de bloqueo.
Básicamente, si la validez del bloqueo del cliente se acerca a un valor más bajo durante el cálculo, el bloqueo se puede extender enviando un script Lua a todas las instancias, extendiendo así el TTL de la clave (si la clave existe y su valor sigue siendo cliente. Un valor aleatorio asignado al adquirir la cerradura).
Solo se debe considerar volver a adquirir el candado si el cliente es capaz de extender el candado a la mayoría de las instancias durante un período de tiempo (esencialmente usando un algoritmo muy similar al utilizado para adquirir el candado). ).
Sin embargo, técnicamente esto no cambia el algoritmo, por lo que debe haber un límite en el número máximo de intentos para volver a adquirir el bloqueo; de lo contrario, se violará una propiedad de actividad.