Salut, Habr !
Aujourd'hui, nous vous proposons une traduction d'un article complexe sur la mise en œuvre des verrous distribués à l'aide de Redis et nous vous invitons à discuter du potentiel de Redis en tant que sujet. L'analyse de l'algorithme Redlock de Martin Kleppmann, auteur du livre "", est fournie .
Les verrous distribués sont un primitive très utile, utilisé dans de nombreux environnements où différents processus doivent travailler sur des ressources partagées selon le principe d'exclusion mutuelle.
Il existe plusieurs bibliothèques et articles décrivant comment mettre en œuvre un DLM (gestionnaire de verrous distribués) avec Redis, mais chaque bibliothèque utilise sa propre approche, et les garanties fournies sont assez faibles par rapport à ce qui est réalisable avec une conception légèrement plus complexe.
Dans cet article, nous allons essayer de décrire un algorithme conditionnellement canonique qui démontre comment mettre en œuvre des verrous distribués à l'aide de Redis. Nous parlerons de l'algorithme appelé Redlock, qui met en œuvre un gestionnaire de verrous distribués et, à notre avis, cet algorithme est plus sûr que l'approche classique avec une seule instance. Nous espérons que la communauté l'analysera, fournira un retour et l'utilisera comme point de départ pour la mise en œuvre de projets plus complexes ou alternatifs.
Implémentations
Avant de passer à la description de l'algorithme, nous fournirons quelques liens vers des implémentations déjà prêtes. Vous pouvez les utiliser comme référence.
- (implémentation pour Ruby). Il existe également Redlock-rb, ajoutant un paquet (gem) pour un partage plus facile, et pas seulement cela.
- (implémentation pour Python).
- (implémentation pour Asyncio Python).
- (implémentation pour PHP).
- (une autre implémentation pour PHP)
- (bibliothèque PHP pour les verrous)
- (implémentation pour Go).
- (implémentation pour Java).
- (implémentation pour Perl).
- (implémentation pour C++).
- (implémentation pour C#/.NET).
- (implémentation pour C#/.NET). Avec le support des extensions async et lock.
- (implémentation pour C# .NET avec un stockage de données configurable)
- (implémentation pour C# .NET)
- (implémentation pour NodeJS). Inclut le support pour le prolongement des verrous.
Garanties de sécurité et de disponibilité
Nous allons modéliser notre projet avec seulement trois propriétés qui, selon nous, offrent les garanties minimales nécessaires pour une utilisation efficace des verrouillages distribués.
- Propriété de sécurité : Exclusion mutuelle. À tout moment, un seul client peut détenir le verrou.
- Propriété d'accessibilité A : Absence de blocages mutuels. Il est toujours possible d'obtenir un verrou, même si le client qui a verrouillé la ressource échoue ou se trouve sur un autre segment de disque.
- Propriété d'accessibilité B : Résilience. Tant que la majorité des nœuds Redis fonctionnent, les clients peuvent acquérir et libérer des verrous.
Pourquoi une mise en œuvre basée sur la reprise après sinistre est-elle insuffisante dans ce cas ?
Pour comprendre ce que nous allons améliorer, analysons l'état actuel des bibliothèques pour verrouillages distribués basées sur Redis.
Le moyen le plus simple de verrouiller une ressource avec Redis consiste à créer une clé dans l'instance. En général, la clé est créée avec une durée de vie limitée, ce qui est réalisé grâce à la fonction expires prévue dans Redis, donc tôt ou tard cette clé sera libérée (propriété 2 dans notre liste). Lorsque le client doit libérer la ressource, il supprime la clé.
À première vue, cette solution fonctionne, mais il y a un problème : dans notre architecture, il y a un point de défaillance unique. Que se passe-t-il si l'instance principale de Redis échoue ? Ajoutons donc une instance secondaire ! Et utilisons-la si la principale n'est pas disponible. Malheureusement, cette option n'est pas viable. En agissant ainsi, nous ne pourrons pas mettre en œuvre correctement la propriété d'exclusion mutuelle, nécessaire pour garantir la sécurité, car la réplication dans Redis est asynchrone.
Il est évident que dans ce modèle, un état de concurrence émerge :
- Le client A acquiert le verrou sur le maître.
- Le maître échoue avant que l'enregistrement de la clé soit transmis à l'esclave.
- L'esclave est promu au rang de maître.
- Le client B acquiert le verrou de la même ressource déjà bloquée par A. VIOLATION DE LA SÉCURITÉ !
Il est parfois tout à fait normal que, dans des circonstances particulières, par exemple en cas de panne, de nombreux clients puissent simultanément détenir un verrou. Dans ces cas, une solution basée sur la réplication peut être appliquée. Dans d'autres situations, nous recommandons la solution décrite dans cet article.
Mise en œuvre correcte avec une seule instance
Avant d'essayer de contourner les inconvénients de la configuration avec une seule instance, comme décrit ci-dessus, examinons comment agir correctement dans ce cas simple, car cette solution est en réalité acceptable dans les applications où l'état de course est parfois tolérable, et aussi parce que le verrouillage d'une seule instance sert de base utilisée dans l'algorithme distribué décrit ici.
Pour acquérir le verrou, procédons comme suit :
SET resource_name my_random_value NX PX 30000
Cette commande définit la clé uniquement si elle n'existe pas encore (option NX), avec une durée de vie de 30000 millisecondes (option PX). Pour la clé, la valeur est définie sur "myrandomvalue". Cette valeur doit être unique parmi tous les clients et toutes les demandes de verrouillage.
En principe, une valeur aléatoire est utilisée pour libérer le verrou en toute sécurité, à l'aide d'un script qui informe Redis : supprime la clé uniquement si elle existe, et la valeur qui y est stockée est bien celle attendue. Cela se fait à l'aide du script Lua suivant :
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
endIl est crucial d'éviter le déverrouillage effectué par un autre client. Par exemple, un client peut acquérir un verrou, puis se bloquer lors d'une opération qui dure plus longtemps que la durée de vie de son premier verrou (de sorte que le délai de la clé expire), et ensuite supprimer le verrou posé par un autre client.
Utiliser un simple DEL n'est pas sûr, car un client peut supprimer un verrou posé par un autre client. En revanche, avec le script ci-dessus, chaque verrou est « signé » par une chaîne aléatoire, donc seul le client qui l'a posé auparavant pourra le supprimer.
Quelle devrait être cette chaîne aléatoire ? Je suppose qu'elle doit faire 20 octets depuis /dev/urandom, mais il existe des méthodes moins coûteuses pour créer une chaîne suffisamment unique pour les objectifs que vous avez. Par exemple, il serait acceptable de semer RC4 avec /dev/urandom, puis de générer à partir de cela un flux pseudo-aléatoire. Une solution plus simple implique une combinaison du temps Unix avec une précision en microsecondes plus l'ID du client ; ce n'est pas aussi sécurisé, mais cela correspond, sinon, à la plupart des tâches dans divers contextes.
Le temps que nous utilisons comme indicateur de la durée de vie de la clé s'appelle « le temps de blocage ». Cette valeur est à la fois la durée après laquelle le blocage sera libéré automatiquement et le temps dont le client dispose pour effectuer son opération avant qu'un autre client ne puisse bloquer cette ressource, sans enfreindre les garanties d'exclusion mutuelle. Cette garantie est limitée à une certaine fenêtre de temps qui commence au moment de l'acquisition du verrou.
Ainsi, nous avons discuté d'un bon moyen d'acquérir et de libérer un verrou. Le système (s'il s'agit d'un système non distribué composé d'une instance unique et toujours disponible) est sécurisé. Élargissons ce concept à un système distribué, où de telles garanties ne s'appliquent pas.
L'algorithme Redlock
Dans la version distribuée de l'algorithme, on suppose que nous avons N masters Redis. Ces nœuds sont totalement indépendants les uns des autres, donc nous n'utilisons pas de réplication ni aucun autre système de coordination implicite. Nous avons déjà expliqué comment acquérir et libérer un verrou en toute sécurité sur une seule instance. Nous prenons pour acquis que l'algorithme en travaillant avec une seule instance utilisera exactement cette méthode. Dans nos exemples, nous fixons N à 5, c'est une valeur tout à fait raisonnable. Ainsi, nous devrons utiliser 5 masters Redis sur différentes machines ou machines virtuelles pour garantir qu'ils fonctionneront principalement de manière indépendante les uns des autres.
Pour acquérir un verrou, le client effectue les opérations suivantes :
- Obtient l'heure actuelle en millisecondes.
- Tente de manière séquentielle d'obtenir un verrou sur toutes les instances N, en utilisant le même nom de clé et des valeurs aléatoires dans tous les cas. À l'étape 2, lors de l'établissement du verrou pour chaque instance, le client utilise un délai suffisamment court par rapport à la durée de laquelle le verrou est automatiquement levé. Par exemple, si la durée du verrou est de 10 secondes, le délai peut être compris entre 5 et 50 millisecondes. Cela évite la situation dans laquelle le client pourrait rester longtemps bloqué en essayant de se connecter à un nœud Redis défaillant : si l'instance est inaccessible, nous tentons de nous connecter au plus tôt à une autre instance.
- Pour prendre le verrou, le client calcule combien de temps s'est écoulé ; pour cela, il soustrait l'horodatage obtenu à l'étape 1 de l'heure actuelle. Ce n'est que lorsque le client a réussi à obtenir le verrou sur la plupart des instances (au moins 3) et que le temps total nécessaire pour obtenir le verrou est inférieur à la durée du verrou, que l'on considère que la prise de verrou a été réussie.
- Si le verrou a été obtenu, la durée de celui-ci est considérée comme la valeur initiale de la durée du verrou moins le temps écoulé, calculé à l'étape 3.
- Si le client n'a pas réussi à obtenir le verrou pour une raison quelconque (soit il n'a pas pu verrouiller N/2+1 instances, soit la durée du verrou s'est révélée négative), il tentera de déverrouiller toutes les instances (même celles qu'il pensait ne pas avoir pu verrouiller).
L'algorithme est-il asynchrone ?
Cet algorithme repose sur l'hypothèse que, bien qu'il n'existe pas d'horloges synchronisées sur lesquelles tous les processus fonctionnent, le temps local dans chaque processus s'écoule tout de même à peu près au même rythme, et que l'erreur est faible par rapport à la durée totale après laquelle le verrou est automatiquement levé. Cette hypothèse ressemble beaucoup à une situation typique sur les ordinateurs ordinaires : chaque ordinateur dispose d'une horloge locale, et en général, nous pouvons compter sur le fait que la divergence horaire entre différents ordinateurs est faible.
À ce stade, nous devons formuler plus précisément notre règle d'exclusion mutuelle : l'exclusion mutuelle est garantie uniquement si le client, retenant le verrou, termine son travail dans le délai de validité du verrou (cette valeur est obtenue à l'étape 3), moins un certain temps (quelques millisecondes, pour compenser le décalage horaire entre les processus).
Pour en savoir plus sur de tels systèmes nécessitant un accord sur le décalage horaire, lisez l'article intéressant suivant : .
Réessayer en cas d'échec
Lorsque le client n'a pas réussi à obtenir le verrou, il doit tenter de le faire à nouveau en respectant un délai aléatoire ; cela est fait pour désynchroniser plusieurs clients essayant en même temps d'acquérir le verrou d'une même ressource (ce qui peut entraîner une situation de « cerveau partagé », où il n'y a pas de gagnants). De plus, plus le client essaie rapidement d'acquérir le verrou sur la majorité des instances Redis, plus la fenêtre pendant laquelle la situation de cerveau partagé peut survenir est étroite (et moins il y a besoin de nouvelles tentatives). Par conséquent, idéalement, le client doit essayer d'envoyer simultanément des commandes SET à N instances par le biais de multiplexage.
Il convient de souligner combien il est important que les clients qui n'ont pas réussi à acquérir la majorité des verrous libèrent (partiellement) les verrous acquis, afin de ne pas avoir à attendre l'expiration de la clé avant que le verrou sur la ressource puisse à nouveau être acquis (bien que si une fragmentation de réseau se produit et que le client perd la connexion avec les instances Redis, il y a une pénalité pour violation de disponibilité tant qu'on attend l'expiration de la clé).
Libération du verrou
La libération du verrou est une opération simple qui consiste simplement à déverrouiller toutes les instances, peu importe si le client pense avoir réussi à verrouiller une instance spécifique.
Considérations de sécurité
L'algorithme est-il sécurisé ? Essayons d'imaginer ce qui se passe dans différents scénarios.
Pour commencer, supposons que le client a réussi à obtenir un verrou sur la plupart des instances. Chacune de ces instances contiendra une clé avec la même durée de vie. Cependant, chacune de ces clés a été établie à des moments différents, donc leurs périodes d'expiration seront variées. Toutefois, si la première clé a été établie à un moment au moins équivalent à T1 (le temps que nous choisissons avant de contacter le premier serveur) et que la dernière clé a été établie à un moment au moins équivalent à T2 (le temps auquel nous avons reçu la réponse du dernier serveur), alors nous sommes sûrs que la première clé dans l'ensemble, qui expirera, existera pendant au moins MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Toutes les autres clés expireront plus tard, donc nous pouvons être certains que toutes les clés seront simultanément valides pendant au moins ce temps.
Pendant la période où la plupart des clés restent valides, un autre client ne pourra pas acquérir de verrou, car N/2+1 opérations SET NX ne peuvent pas réussir s'il existe déjà N/2+1 clés. Par conséquent, si le verrou a été acquis, il est impossible de le ré-acquérir au même moment (cela violerait la propriété d'exclusion mutuelle).
Cependant, nous voulons nous assurer qu'un ensemble de clients tentant simultanément d'acquérir un verrou ne réussira pas à le faire en même temps.
Si un client a verrouillé la plupart des instances, prenant autour ou plus que le temps maximum de durée de verrouillage, il considérera le verrou comme invalide et débloquera les instances. Nous devons donc seulement prendre en compte le cas où le client a réussi à verrouiller la plupart des instances dans un temps inférieur à celui de la durée de validité. Dans ce cas, en ce qui concerne l'argument ci-dessus, pendant le temps MIN_VALIDITY , aucun client ne doit être en mesure de récupérer le verrou à nouveau. Par conséquent, plusieurs clients pourront verrouiller N/2+1 instances au même moment (qui se termine à la fin de l'étape 2), uniquement lorsque le temps pour verrouiller la plupart était supérieur au temps TTL, rendant ainsi le verrou invalide.
Pouvez-vous fournir une preuve formelle de sécurité, indiquer des algorithmes similaires existants, ou trouver un bug dans l'exposé ?
Considérations sur la disponibilité
La disponibilité du système dépend de trois caractéristiques principales :
- Déverrouillage automatique (puisque la durée de vie des clés expire) : en fin de compte, les clés seront de nouveau disponibles pour être utilisées pour des déverrouillages.
- Le fait que les clients s'entraident généralement en supprimant des verrouillages lorsque le verrouillage requis n'a pas été acquis, ou a été acquis mais que le travail est terminé ; il est donc probable que nous n'ayons pas à attendre l'expiration des clés pour réacquérir un verrouillage.
- Le fait que, lorsque le client doit essayer de réacquérir un verrouillage, il attend un temps relativement plus long que la période nécessaire pour acquérir la plupart des verrouillages. Cela réduit la probabilité de situations de concurrence pour les ressources.
Cependant, il faut payer un coût pour la réduction de la disponibilité, équivalent au temps TTL dans les segments de réseau, donc, s'il y a des segments continus, ce coût peut devenir indéfini. Cela se produit chaque fois qu'un client acquiert un verrouillage, puis est isolé dans un autre segment avant d'avoir pu le libérer.
En principe, avec des segments de réseau continus infinis, le système peut rester indisponible pendant une période infinie.
Performance, récupération après sinistre et fsync
Beaucoup utilisent Redis, car il est nécessaire d'assurer une haute performance du serveur de verrouillage, au niveau des latences requises pour acquérir et libérer des verrouillages, ainsi que du nombre d'opérations d'acquisition/libération qui peuvent être effectuées par seconde. Pour répondre à cette exigence, il existe une stratégie de communication avec N serveurs Redis afin de réduire la latence. C'est une stratégie de multiplexage (ou « multiplexage économique », où le socket est mis en mode non-bloquant, envoie toutes les commandes et lit les commandes plus tard, en supposant que le temps de réponse entre le client et chaque instance est similaire).
Cependant, il faut également prendre en compte les considérations concernant le stockage à long terme des données, si nous visons à créer un modèle avec une récupération après sinistre fiable.
Pour clarifier le problème, supposons que nous configurions Redis sans stockage de données persistant. Le client parvient à verrouiller 3 des 5 instances. Une des instances que le client a réussi à verrouiller redémarre, et à ce moment-là, 3 instances du même ressource peuvent de nouveau être verrouillées, et un autre client peut, à son tour, verrouiller l'instance redémarrée, ce qui compromet la propriété de sécurité qui suppose l'exclusivité des verrous.
Si nous activons la sauvegarde anticipée des données (AOF), la situation s'améliore un peu. Par exemple, nous pouvons redémarrer le serveur en envoyant la commande SHUTDOWN puis en le redémarrant. Puisque les opérations d'expiration dans Redis sont sémantiquement réalisées de manière à ce que le temps continue de passer même lorsque le serveur est éteint, tout est en ordre. Tant que l'arrêt se fait correctement. Que faire en cas de panne de courant ? Si Redis est configuré par défaut avec fsync sur le disque chaque seconde, il est possible qu'après un redémarrage, nous ne retrouvions pas notre clé. En théorie, si nous voulons garantir la sécurité des verrous lors de tout redémarrage de l'instance, nous devons activer fsync=always dans les paramètres de stockage de données persistantes. Cela dégradera complètement les performances, jusqu'à atteindre le niveau de systèmes CP traditionnellement utilisés pour la mise en œuvre sûre des verrous distribués.
Cependant, la situation est meilleure qu'elle n'en a l'air. En principe, la sécurité de l'algorithme est maintenue, car lorsque l'instance redémarre après une défaillance, elle ne participe plus à aucun verrou actif à ce moment.
Pour garantir cela, il suffit de s'assurer qu'après une défaillance, l'instance reste inaccessible pendant un temps légèrement supérieur au maximum TTL que nous utilisons. Ainsi, nous attendrons l'expiration et le relâchement automatique de toutes les clés qui étaient actives au moment de la défaillance.
En utilisant des redémarrages différés, il est en principe possible d'atteindre la sécurité même en l'absence de toute persistance à long terme dans Redis. Cependant, il convient de noter que cela peut entraîner une pénalité pour violation de disponibilité. Par exemple, en cas de défaillance de la plupart des instances, le système deviendra globalement inaccessible pendant la durée de TTL (et aucun ressource ne pourra être bloquée pendant ce temps).
Augmentons la disponibilité de l'algorithme : prolongeons le verrouillage
Si le travail effectué par les clients se compose de petites étapes, il est possible de réduire la durée de blocage par défaut et de mettre en place un mécanisme de prolongation des blocages. En principe, si le client est occupé par des calculs et que la valeur de la durée de blocage est dangereusement réduite, il est possible d'envoyer à toutes les instances un script en Lua qui prolonge le TTL de la clé, si la clé existe encore et si sa valeur est toujours aléatoire, obtenue lors de l'acquisition du verrou.
Le client doit considérer le verrou comme ayant été réacquis uniquement s'il a réussi à verrouiller la majorité des instances pendant la durée d'action.
En effet, techniquement, l'algorithme ne change pas, donc le nombre maximum de tentatives de réacquisition de blocs doit être limité, sinon les propriétés de disponibilité seront compromises.
Source : habr.com
