ProHoster > Blog > administration > Verrouillage distribué à l'aide de Redis

Verrouillage distribué à l'aide de Redis

Hé Habr !

Aujourd'hui, nous attirons votre attention sur la traduction d'un article complexe sur la mise en œuvre du verrouillage distribué à l'aide de Redis et vous invitons à parler des perspectives de Redis en tant que sujet. Analyse de l'algorithme Redlock en question de Martin Kleppmann, auteur du livre "Applications à charge élevée", donné ici.

Le verrouillage distribué est une primitive très utile utilisée dans de nombreux environnements où différents processus doivent fonctionner sur des ressources partagées de manière mutuellement exclusive.

Il existe un certain nombre de bibliothèques et d'articles qui décrivent comment implémenter DLM (Distributed Lock Manager) à l'aide de Redis, mais chaque bibliothèque adopte une approche différente et les garanties qu'elles offrent sont assez faibles par rapport à ce qui est réalisable avec une conception légèrement plus sophistiquée.

Dans cet article, nous allons essayer de décrire un algorithme canonique conditionnel qui montre comment implémenter le verrouillage distribué à l'aide de Redis. Nous parlerons d'un algorithme appelé Verrouillage rouge, il implémente un gestionnaire de verrous distribués et, à notre avis, cet algorithme est plus sûr que l'approche habituelle à instance unique. Nous espérons que la communauté l'analysera, fournira des commentaires et l'utilisera comme point de départ pour des projets plus complexes ou alternatifs.

Mise en œuvre

Avant de passer à la description de l’algorithme, nous fournissons plusieurs liens vers des implémentations prêtes à l’emploi. Ils peuvent être utilisés à titre de référence.

Garanties de sécurité et de disponibilité

Nous allons modéliser notre conception avec seulement trois propriétés qui, selon nous, fournissent les garanties minimales nécessaires pour utiliser efficacement le verrouillage distribué.

  1. Propriété de sécurité : Exclusion mutuelle. À tout moment, un seul client peut détenir le verrou.
  2. Propriété de disponibilité A : aucun blocage. Il est toujours possible d'acquérir éventuellement un verrou, même si le client qui a verrouillé la ressource échoue ou atterrit sur un segment de disque différent.
  3. Propriété de disponibilité B : tolérance aux pannes. Tant que la majorité des nœuds Redis sont en cours d'exécution, les clients peuvent acquérir et libérer des verrous.

Pourquoi la mise en œuvre basée sur la reprise après échec n'est pas suffisante dans ce cas
Pour comprendre ce que nous allons améliorer, analysons l'état actuel des choses avec la plupart des bibliothèques de verrouillage distribuées basées sur Redis.

Le moyen le plus simple de verrouiller une ressource à l'aide de Redis consiste à créer une clé dans l'instance. En règle générale, une clé est créée avec une durée de vie limitée, ceci est réalisé à l'aide de la fonctionnalité d'expiration fournie dans Redis, donc tôt ou tard cette clé est publié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 plutôt bien, mais il y a un problème : notre architecture crée un point de défaillance unique. Que se passe-t-il si l'instance Redis hôte échoue ? Ajoutons un esclave alors ! Et nous l'utiliserons si le présentateur n'est pas disponible. Malheureusement, cette option n'est pas viable. En faisant cela, nous ne pourrons pas implémenter correctement la propriété d'exclusion mutuelle dont nous avons besoin pour garantir la sécurité, car la réplication dans Redis est asynchrone.

Évidemment, dans un tel modèle, une condition de concurrence critique se produit :

  1. Le client A acquiert un verrou sur le maître.
  2. Le maître échoue avant que l'entrée de clé ne soit transférée à l'esclave.
  3. Le suiveur est promu leader.
  4. Le client B acquiert un verrou sur la même ressource que A a déjà verrouillée. VIOLATION DE LA SÉCURITÉ!

Il est parfois tout à fait normal que dans des circonstances particulières, comme une panne, plusieurs clients puissent détenir la serrure en même temps. Dans de tels cas, une solution basée sur la réplication peut être appliquée. Sinon, nous recommandons la solution décrite dans cet article.

Implémentation correcte avec une seule instance

Avant de tenter de pallier les défauts de la configuration mono-instance décrite ci-dessus, comprenons comment gérer correctement ce cas simple, puisque cette solution est en réalité valable dans des applications où une situation de concurrence critique est acceptable de temps en temps, et aussi parce que le blocage sur un une seule instance sert de base utilisée dans l'algorithme distribué décrit ici.

Pour acquérir un verrou, procédez comme suit :

SET resource_name my_random_value NX PX 30000

Cette commande installe une clé uniquement si elle n'existe pas déjà (option NX), avec une durée de validité de 30000 XNUMX millisecondes (option PX). La clé est réglée sur «myrandomvalue" Cette valeur doit être unique pour tous les clients et toutes les demandes de verrouillage.
Fondamentalement, une valeur aléatoire est utilisée pour libérer le verrou en toute sécurité, avec un script indiquant à Redis : ne supprimez la clé que si elle existe et si la valeur qui y est stockée correspond exactement à celle attendue. Ceci est réalisé en utilisant le script Lua suivant :

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

Ceci est important pour empêcher la suppression d’un verrou détenu par un autre client. Par exemple, un client peut acquérir un verrou, puis être verrouillé lors d'une opération qui dure plus longtemps que le premier verrou (de sorte que la clé ait le temps d'expirer), puis retirer le verrou placé par un autre client.
L'utilisation d'un simple DEL n'est pas sûre car un client peut supprimer un verrou détenu par un autre client. En revanche, lors de l'utilisation du script ci-dessus, chaque verrou est « signé » avec une chaîne aléatoire, de sorte que seul le client qui l'a placé précédemment peut le supprimer.

Quelle devrait être cette chaîne aléatoire ? Je suppose qu'il devrait s'agir de 20 octets de /dev/urandom, mais vous pouvez trouver des moyens moins coûteux de rendre la chaîne suffisamment unique pour vos besoins. Par exemple, ce serait bien d'amorcer RC4 avec /dev/urandom puis d'en générer un flux pseudo-aléatoire. Une solution plus simple implique une combinaison du temps Unix en résolution en microsecondes et de l'ID client ; ce n'est pas aussi sécurisé, mais c'est probablement à la hauteur dans la plupart des contextes.

Le temps que nous utilisons comme mesure de la durée de vie de la clé est appelé « durée de vie de la serrure ». Cette valeur correspond à la fois au temps écoulé avant que le verrou soit automatiquement libéré et au temps dont dispose un client pour terminer une opération avant qu'un autre client puisse à son tour verrouiller cette ressource, sans réellement violer les garanties d'exclusion mutuelle. Cette garantie est limitée uniquement à une certaine fenêtre de temps, qui commence à partir du moment où la serrure est achetée.

Nous avons donc discuté d'un bon moyen d'acquérir et de déverrouiller un verrou. Le système (si nous parlons d'un système non distribué constitué d'une instance unique et toujours disponible) est sécurisé. Étendons ce concept à un système distribué, où nous n'avons aucune telle garantie.

Algorithme Redlock

La version distribuée de l'algorithme suppose que nous disposons de N maîtres Redis. Ces nœuds sont complètement indépendants les uns des autres, nous n'utilisons donc pas de réplication ou tout autre système de coordination implicite. Nous avons déjà expliqué comment acquérir et libérer en toute sécurité un verrou sur une seule instance. Nous tenons pour acquis que l'algorithme, lorsqu'il travaille avec une seule instance, utilisera exactement cette méthode. Dans nos exemples, nous fixons N à 5, ce qui est une valeur raisonnable. Ainsi, nous devrons utiliser 5 maîtres Redis sur différents ordinateurs ou machines virtuelles pour nous assurer qu'ils agissent largement indépendamment les uns des autres.

Pour acquérir un verrou, le client effectue les opérations suivantes :

  1. Obtient l'heure actuelle en millisecondes.
  2. Tente séquentiellement d'obtenir un verrou sur toutes les N instances, en utilisant le même nom de clé et les mêmes valeurs aléatoires dans tous les cas. À l'étape 2, lorsque le client configure un verrou instance par instance, il utilise un délai pour l'acquérir suffisamment court par rapport au temps après lequel le verrou est automatiquement libéré. Par exemple, si la durée du blocage est de 10 secondes, le délai peut être compris entre environ 5 et 50 millisecondes. Cela élimine la situation dans laquelle le client pourrait rester bloqué pendant une longue période en essayant d'atteindre un nœud Redis défaillant : si l'instance n'est pas disponible, alors nous essayons de nous connecter à une autre instance dès que possible.
  3. Pour prendre un verrou, le client calcule le temps écoulé ; Pour ce faire, il soustrait de la valeur temporelle réelle l'horodatage obtenu à l'étape 1. Si et seulement si le client a pu obtenir le verrou sur la majorité des instances (au moins 3), et le temps total qu'il a fallu pour obtenir le verrou, inférieure à la durée du verrou, le verrou est considéré comme obtenu.
  4. Si un verrou a été acquis, la durée du verrouillage est considérée comme étant la durée de verrouillage d'origine moins le temps écoulé calculé à l'étape 3.
  5. Si le client ne parvient pas à obtenir le verrou pour une raison quelconque (soit il n'a pas pu verrouiller N/2+1 instances, soit la durée du verrouillage était négative), alors il tentera de déverrouiller toutes les instances (même celles qu'il pensait ne pas pouvoir bloquer). ).

L'algorithme est-il asynchrone ?

Cet algorithme est basé sur l'hypothèse que, même s'il n'existe pas d'horloge synchronisée sur laquelle tous les processus fonctionneraient, l'heure locale de chaque processus s'écoule toujours à peu près au même rythme et l'erreur est faible par rapport au temps total après lequel le verrou est verrouillé. automatiquement libéré. Cette hypothèse est très similaire à la situation typique des ordinateurs ordinaires : chaque ordinateur possède une horloge locale, et nous pouvons généralement compter sur le fait que la différence de temps entre les différents ordinateurs est faible.

À ce stade, nous devons formuler plus soigneusement notre règle d'exclusion mutuelle : l'exclusion mutuelle n'est garantie que si le client détenant le verrou sort pendant la durée de validité du verrou (cette valeur obtenue à l'étape 3), moins un certain temps supplémentaire (au total quelques millisecondes pour compenser la différence de temps entre les processus).

L'article intéressant suivant en dit plus sur les systèmes qui nécessitent une coordination des intervalles de temps : Baux : un mécanisme efficace de tolérance aux pannes pour la cohérence du cache de fichiers distribués.

Réessayer en cas d'échec

Lorsqu'un client ne parvient pas à acquérir un verrou, il doit réessayer après un délai aléatoire ; ceci est fait pour désynchroniser plusieurs clients essayant d'acquérir un verrou sur la même ressource en même temps (ce qui peut conduire à une situation de « cerveau divisé » dans laquelle il n'y a pas de gagnants). De plus, plus rapidement un client tente d'acquérir un verrou sur la majorité des instances Redis, plus la fenêtre dans laquelle une situation de split-brain peut se produire est étroite (et moins il est nécessaire de réessayer). Par conséquent, idéalement, le client devrait essayer d’envoyer des commandes SET à N instances simultanément en utilisant le multiplexage.

Il convient de souligner ici combien il est important que les clients qui ne parviennent pas à acquérir la majorité des verrous libèrent les verrous (partiellement) acquis, afin de ne pas avoir à attendre l'expiration de la clé avant de pouvoir acquérir à nouveau le verrou sur la ressource. (cependant, si une fragmentation du réseau se produit et que le client perd le contact avec les instances Redis, vous devez alors payer une pénalité de disponibilité en attendant l'expiration de la clé).

Libérez le verrou

La libération d'un verrou est une opération simple qui nécessite simplement de déverrouiller toutes les instances, que le client semble avoir ou non verrouillé avec succès une instance particulière.

Considérations de sécurité

L'algorithme est-il sûr ? Essayons d'imaginer ce qui se passe dans différents scénarios.

Pour commencer, supposons que le client ait pu obtenir un verrou sur la majorité des instances. Chaque instance contiendra une clé avec la même durée de vie pour tous. Cependant, chacune de ces clés a été installée à un moment différent, elles expireront donc à des moments différents. Mais, si la première clé a été installée à un moment pas pire que T1 (l'heure que nous choisissons avant de contacter le premier serveur), et que la dernière clé a été installée à un moment pas pire que T2 (l'heure à laquelle la réponse a été reçue du dernier serveur), alors nous sommes sûrs que la première clé de l'ensemble qui expire survivra au moins MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Toutes les autres clés expireront plus tard, nous pouvons donc être sûrs que toutes les clés seront valides simultanément pendant au moins cette période.

Pendant que la plupart des clés restent valides, un autre client ne pourra pas acquérir le verrou, car les opérations N/2+1 SET NX ne peuvent pas réussir si N/2+1 clés existent déjà. Par conséquent, une fois qu’un verrou a été acquis, il est impossible de l’acquérir à nouveau au même moment (cela violerait la propriété d’exclusion mutuelle).
Cependant, nous voulons nous assurer que plusieurs clients essayant d'acquérir un verrou en même temps ne puissent pas réussir en même temps.

Si le client a verrouillé la majorité des instances pendant une durée égale ou supérieure à la durée de verrouillage maximale, il considérera le verrouillage comme invalide et déverrouillera les instances. Il suffit donc de prendre en compte le cas dans lequel le client a réussi à bloquer la majorité des instances dans un délai inférieur à la date d'expiration. Dans ce cas, concernant l'argument ci-dessus, pendant le temps MIN_VALIDITY aucun client ne devrait pouvoir réacquérir le verrou. Par conséquent, de nombreux clients pourront verrouiller N/2+1 instances dans le même temps (qui se termine à la fin de l'étape 2) uniquement lorsque le temps de verrouillage de la majorité sera supérieur au temps TTL, ce qui rendra le verrouillage invalide.

Pouvez-vous fournir une preuve formelle de sécurité, indiquer des algorithmes similaires existants ou trouver un bug dans ce qui précède ?

Considérations relatives à l'accessibilité

La disponibilité du système dépend de trois caractéristiques principales :

  1. Libérer automatiquement les verrous (à mesure que les clés expirent) : les clés seront éventuellement à nouveau disponibles pour être utilisées pour les verrous.
  2. Le fait que les clients s'entraident généralement en retirant les verrous lorsque le verrou souhaité n'a pas été acquis, ou a été acquis et le travail est terminé ; il est donc probable que nous n'aurons pas à attendre l'expiration des clés pour réacquérir la serrure.
  3. Le fait que lorsqu'un client doit réessayer d'acquérir un verrou, il attend comparativement plus longtemps que la période requise pour acquérir la plupart des verrous. Cela réduit la probabilité qu’une situation de division du cerveau se produise lors d’une compétition pour les ressources.

Cependant, il existe une pénalité de disponibilité égale à la durée de vie des segments de réseau, donc s'il existe des segments contigus, la pénalité peut être indéfinie. Cela se produit chaque fois qu'un client acquiert un verrou, puis le pirate sur un autre segment avant de pouvoir le libérer.

En principe, étant donné une infinité de segments de réseau contigus, un système peut rester indisponible pendant une période de temps infinie.

Performances, basculement et fsync

De nombreuses personnes utilisent Redis car elles ont besoin de performances élevées du serveur de verrouillage en termes de latence requise pour acquérir et libérer les verrous, et de nombre d'acquisitions/libérations pouvant être effectuées par seconde. Pour répondre à cette exigence, il existe une stratégie de communication avec les serveurs N Redis afin de réduire la latence. Il s'agit d'une stratégie de multiplexage (ou "multiplexage du pauvre", où le socket est mis en mode non bloquant, envoie toutes les commandes et lit les commandes plus tard, en supposant que le temps d'aller-retour entre le client et chaque instance est similaire) .

Cependant, nous devons également prendre en compte les considérations associées au stockage des données à long terme si nous nous efforçons de créer un modèle avec une récupération fiable après une panne.

Fondamentalement, pour clarifier le problème, supposons que nous configurons Redis sans aucun stockage de données à long terme. Le client parvient à bloquer 3 instances sur 5. L'une des instances que le client a réussi à bloquer est redémarrée, et à ce moment il y a à nouveau 3 instances pour la même ressource, que nous pouvons bloquer, et un autre client peut, à son tour, bloquer l'instance redémarrée, violant la propriété de sécurité qui assume l'exclusivité des serrures.

Si vous activez les données anticipées (AOF), la situation s'améliorera légèrement. Par exemple, vous pouvez promouvoir un serveur en envoyant la commande SHUTDOWN et en le redémarrant. Étant donné que les opérations d'expiration dans Redis sont sémantiquement implémentées de telle manière que le temps continue de s'écouler même lorsque le serveur est éteint, toutes nos exigences sont bonnes. Ceci est normal tant qu'un arrêt normal est assuré. Que faire en cas de coupure de courant ? Si Redis est configuré par défaut, avec une synchronisation fsync sur le disque toutes les secondes, alors il est possible qu'après un redémarrage nous n'ayons pas notre clé. Théoriquement, si nous voulons garantir la sécurité du verrouillage lors d'un redémarrage d'une instance, nous devrions activer fsync=always dans les paramètres de stockage de données à long terme. Cela tuera complètement les performances, jusqu'au niveau des systèmes CP traditionnellement utilisés pour implémenter en toute sécurité des verrous distribués.

Mais la situation est meilleure qu’il n’y paraît à première vue. En principe, la sécurité de l'algorithme est préservée car lorsque l'instance est redémarrée après une panne, elle ne participe plus à aucun verrou actuellement actif.

Pour garantir cela, nous devons simplement nous assurer qu'après une panne, l'instance reste indisponible pendant une période dépassant légèrement le TTL maximum que nous utilisons. De cette façon, nous attendrons la date d'expiration et la libération automatique de toutes les clés qui étaient actives au moment de l'échec.

Grâce aux redémarrages différés, il est en principe possible d'assurer la sécurité même en l'absence de persistance à long terme dans Redis. Notez cependant que cela peut entraîner une amende en cas de violation de l'accessibilité. Par exemple, si la majorité des instances échouent, le système deviendra globalement indisponible pour le TTL (et aucune ressource ne pourra être bloquée pendant ce temps).

On augmente la disponibilité de l'algorithme : on étend le blocage

Si le travail effectué par les clients consiste en de petites étapes, il est possible de réduire la durée de verrouillage par défaut et de mettre en place un mécanisme d'extension des verrouillages. En principe, si le client est occupé à calculer et que la valeur d'expiration du verrou est dangereusement basse, vous pouvez envoyer un script Lua à toutes les instances qui étend la durée de vie de la clé si la clé existe toujours et que sa valeur est toujours une valeur aléatoire obtenue lorsque le client est en train de calculer. la serrure a été acquise.

Un client ne doit envisager de réacquérir un verrou que s'il a réussi à verrouiller la majorité des instances pendant la période de validité.

Certes, techniquement, l'algorithme ne change pas, donc le nombre maximum de tentatives répétées d'acquisition de verrous doit être limité, sinon les propriétés d'accessibilité seront violées.

Source: habr.com

Ajouter un commentaire