Clever Geek Handbook

Verrous distribués à l'aide de Redis

Bonjour, Habr!



Aujourd'hui, nous portons à votre attention la traduction d'un article complexe sur la mise en œuvre des verrous distribués à l'aide de Redis et proposons de parler des perspectives de Redis en tant que sujet. Une analyse de l'algorithme Redlock considéré de Martin Kleppman, auteur du livre "High Load Applications ", est donnée ici .





Les verrous distribués sont une primitive très utile utilisée dans de nombreux environnements où différents processus doivent travailler sur des ressources partagées de manière mutuellement exclusive.



Il existe un certain nombre de bibliothèques et d'articles décrivant comment implémenter un DLM (Distributed Locking Manager) avec Redis, mais chaque bibliothèque adopte une approche différente et les garanties fournies sont faibles par rapport à ce qui est réalisable avec une conception un peu plus complexe.



Dans cet article, nous allons essayer de décrire un algorithme canonique conditionnel montrant comment implémenter des verrous distribués avec Redis. Nous parlerons d'un algorithme appelé Redlock, il implémente un gestionnaire de verrouillage distribué et, à notre avis, cet algorithme est plus sûr que l'approche classique à instance unique. Nous espérons que la communauté l'analysera, donnera son avis 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, voici quelques liens vers des implémentations toutes faites. Ils peuvent être utilisés pour référence.







Garanties de sécurité et de disponibilité



Nous allons simuler notre conception avec seulement trois propriétés qui, selon nous, fournissent les garanties minimales requises pour utiliser efficacement les verrous distribués.



  1. Propriété de sécurité: exclusion mutuelle. Un seul client peut détenir un verrou à la fois.
  2. Accessibilité Propriété A: Aucune impasse. En fin de compte, vous pouvez toujours obtenir un verrou, même si le client qui a verrouillé la ressource échoue ou se retrouve dans un autre segment de disque.
  3. Propriété d'accessibilité B: tolérance aux pannes. Alors que la plupart des nœuds Redis sont en cours d'exécution, les clients peuvent acquérir et libérer des verrous.




Pourquoi une implémentation basée sur le basculement 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 est de créer une clé sur une instance. Habituellement, une clé est créée avec une durée de vie limitée, cela est réalisé en utilisant la fonctionnalité d'expiration fournie dans Redis, donc tôt ou tard cette clé est libérée (propriété 2 dans notre liste). Lorsque le client a besoin de libérer la ressource, il supprime la clé.



À première vue, cette solution fonctionne bien, mais il y a un problème: il y a un seul point de défaillance dans notre architecture. Que se passe-t-il si l'instance principale de Redis échoue? Ajoutons un suiveur alors! Et nous l'utiliserons si l'hôte n'est pas disponible. Malheureusement, cette option n'est pas viable. En faisant cela, nous ne pourrons pas correctement implémenter la propriété d'exclusion mutuelle dont nous avons besoin pour la sécurité, car la réplication dans Redis est asynchrone.



De toute évidence, une condition de concurrence se produit dans un tel modèle:

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




Parfois, il est tout à fait normal que dans des circonstances spéciales, telles qu'une défaillance, plusieurs clients puissent maintenir un verrou en même temps. Dans de tels cas, vous pouvez appliquer une solution basée sur la réplication. Sinon, nous vous recommandons la solution décrite dans cet article.



Corriger l'implémentation d'instance unique



Avant d'essayer de surmonter les lacunes de la configuration d'instance unique décrite ci-dessus, voyons comment gérer ce cas simple, car cela est en fait acceptable dans les applications où les conditions de concurrence sont parfois acceptables, et aussi parce que le verrouillage sur une seule instance sert de base à l'algorithme distribué décrit ici.



Pour acquérir un verrou, procédons 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 date d'expiration de 30 000 millisecondes (option PX). La clé est réglée sur « myrandomvalue». Cette valeur doit être unique sur tous les clients et sur toutes les demandes de verrouillage.

Fondamentalement, la valeur aléatoire est utilisée pour libérer le verrou en toute sécurité, à l'aide d'un script qui indique à Redis de supprimer la clé uniquement si elle existe et que la valeur qui y est stockée correspond exactement à ce qui était attendu. Ceci est accompli avec 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 un autre client de libérer un verrou. Par exemple, un client peut acquérir un verrou, puis bloquer une opération qui dure plus longtemps que le premier verrou (pour que la clé ait le temps d'expirer), puis supprimer le verrou qu'un autre client a placé.

Il n'est pas sûr d'utiliser une simple DEL car un client peut supprimer un verrou détenu par un autre client. Au contraire, 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 précédemment placé peut le supprimer.



Quelle devrait être cette chaîne aléatoire? Je suppose que cela devrait être de 20 octets à partir de / dev / urandom, mais vous pouvez trouver des moyens moins coûteux de rendre la chaîne suffisamment unique pour le but que vous essayez d'accomplir. Par exemple, il serait acceptable d'amorcer RC4 avec / dev / urandom, puis de générer un flux pseudo-aléatoire basé sur celui-ci. Une solution plus simple consiste à combiner une heure unix microseconde plus un ID client; ce n'est pas tout à fait aussi sûr, mais c'est peut-être au niveau du défi dans la plupart des contextes.



Le temps que nous utilisons comme mesure de la durée de vie de la clé est appelé «délai d'expiration du verrou». Cette valeur est à la fois le temps après lequel le verrou sera automatiquement libéré et le temps dont dispose le client pour terminer l'opération avant qu'un autre client puisse à son tour verrouiller la ressource sans enfreindre réellement les garanties d'exclusion mutuelle. Une telle garantie est limitée uniquement à une certaine fenêtre de temps, qui commence à partir du moment de l'acquisition de la serrure.



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



Algorithme Redlock



La version distribuée de l'algorithme suppose que nous avons N Redis en tête. 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 débloquer en toute sécurité des verrous sur une seule instance. Nous tenons pour acquis que l'algorithme utilisera cette méthode lorsqu'il travaillera avec une seule instance. Dans nos exemples, nous mettons N à 5, ce qui est une valeur parfaitement raisonnable. Ainsi, nous devrons utiliser 5 maîtres Redis sur différents ordinateurs ou machines virtuelles pour nous assurer qu'ils fonctionnent 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. N , . 2, , , , , , . , 10 , ~ 5-50 . , , Redis: , .
  3. , , ; , 1. , ( 3), , , , , , .
  4. , , 3.
  5. - ( N/2+1 , ), ( , , , ).




L'algorithme est-il asynchrone?



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



A ce stade, nous devrions être plus prudents dans la formulation de notre règle d'exclusion mutuelle: l'exclusion mutuelle n'est garantie que si le client détenant le verrou termine dans le temps pendant lequel le verrou est valide (cette valeur a été obtenue à l'étape 3), moins un peu plus de temps (total plusieurs millisecondes pour compenser la différence de temps entre les processus).



L'article intéressant suivant en dit plus sur ces systèmes qui nécessitent un décalage temporel: Baux: un mécanisme efficace de tolérance aux pannes pour la cohérence du cache de fichiers distribué .



Réessayer en cas d'échec



Lorsque le client ne parvient pas à acquérir le verrou, il doit essayer de le faire à nouveau, avec un délai aléatoire; ceci est fait pour désynchroniser plusieurs clients simultanément essayant d'acquérir un verrou sur la même ressource (ce qui peut conduire à une situation de split-brain dans laquelle il n'y a pas de gagnants). De plus, plus un client essaie d'acquérir un verrou rapidement sur la plupart des instances Redis, plus la fenêtre dans laquelle une situation de split-brain peut se produire est étroite (et moins de nouvelles tentatives sont nécessaires). 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 à quel point il est important pour les clients qui n'ont pas été en mesure d'acquérir la plupart des verrous de libérer (partiellement) les verrous acquis afin qu'ils n'aient pas à attendre la date d'expiration de la clé avant que le verrou sur la ressource puisse être acquis à nouveau (même si la fragmentation du réseau se produit et le client perd le contact avec les instances Redis, vous devez payer une pénalité de violation d'accès pendant que la clé est censée expirer).



Libération d'un verrou La



libération d'un verrou est une opération simple qui vous oblige à déverrouiller simplement toutes les instances, que le client pense ou non avoir réussi à verrouiller une instance particulière.



Considérations de sécurité



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



Tout d'abord, supposons que le client ait pu acquérir le verrou sur la plupart des instances. Chacune des instances contiendra une clé avec la même durée de vie pour tout le monde. Cependant, chacune de ces clés a été installée à son propre moment, 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 une réponse a été reçue du dernier serveur), alors nous sont sûrs que la première clé de l'ensemble qui expirera durera au moinsMIN_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 fois.



Pendant le temps où 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, si le verrou a été acquis, il est alors impossible de le réacquérir au même moment (cela violerait la propriété d'exclusion mutuelle).

Cependant, nous voulons nous assurer que de nombreux clients essayant simultanément d'acquérir un verrou ne peuvent pas réussir en même temps.



Si le client a verrouillé la plupart des instances, dépensant environ ou plus que la durée de verrouillage maximale pendant cette période, il invalidera le verrou et débloquera les instances. Par conséquent, nous n'avons qu'à considérer le cas dans lequel le client a pu bloquer la plupart des instances en moins de la date d'expiration. Dans ce cas, en ce qui concerne l'argument ci-dessus, MIN_VALIDITYaucun client ne doit être en mesure de réacquérir le verrou à temps. Par conséquent, plusieurs clients pourront verrouiller N / 2 + 1 instances dans le même laps de temps (qui se termine à la fin de l'étape 2) uniquement lorsque le temps de verrouillage de la majorité est supérieur au temps TTL, ce qui invalide le verrouillage.



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



Considérations



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



  1. Libération automatique des verrous (lorsque les clés expirent): Finalement, les clés seront à nouveau disponibles pour être utilisées pour les verrous.
  2. Le fait que les clients s'entraident généralement en supprimant les verrous lorsque le verrou souhaité n'a pas été acquis ou a été acquis et que le travail est terminé; par conséquent, il est probable que nous n'ayons pas à attendre l'expiration des clés pour réacquérir le verrou.
  3. Le fait que lorsqu'un client doit réessayer pour acquérir un verrou, il attend un temps relativement plus long que le temps nécessaire pour acquérir la plupart des verrous. Cela réduit la probabilité d'une situation de fractionnement du cerveau lors de la compétition pour les ressources.




Cependant, vous devez payer une pénalité pour disponibilité réduite égale au temps TTL dans les segments de réseau, donc s'il y a des segments contigus, cette pénalité peut devenir d'une taille indéfinie. Cela se produit chaque fois qu'un client acquiert un verrou, puis se fixe à un autre segment avant de pouvoir le libérer.



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



Performances, basculement et fsync



De nombreuses personnes utilisent Redis car elles doivent fournir des performances élevées du serveur de verrouillage, au niveau de latence requis pour acquérir et libérer des verrous, ainsi que le nombre d'opérations d'acquisition / de libération pouvant être effectuées par seconde. Pour répondre à cette exigence, il existe une stratégie de communication avec N serveurs Redis pour réduire la latence. Il s'agit d'une stratégie de multiplexage (ou multiplexage du pauvre, qui met la socket 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).



Certes, il faut également prendre en compte le stockage des données à long terme si nous voulons créer un modèle avec une récupération fiable après des pannes.



Fondamentalement, pour clarifier le problème, supposons que nous configurons Redis sans 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, 3 instances apparaissent à nouveau pour la même ressource, que nous pouvons bloquer, et l'autre client peut, à son tour, bloquer l'instance redémarrée, violant la propriété de sécurité qui implique exclusivité des serrures.



Si vous activez l'avance des données (AOF), la situation s'améliorera légèrement. Par exemple, vous pouvez promouvoir le serveur en envoyant la commande SHUTDOWN, puis en le redémarrant. Étant donné que les opérations d'expiration dans Redis sont implémentées sémantiquement de telle sorte que le temps continue à s'écouler même lorsque le serveur est éteint, tout va bien avec toutes nos exigences. Normal tant que l'arrêt normal est assuré. Que faire en cas de coupure de courant? Si Redis est configuré par défaut, avec fsync se synchronisant sur le disque toutes les secondes, il est possible qu'après le redémarrage, nous manquions notre clé. En théorie, si l'on veut garantir la sécurité des verrous à tout redémarrage de l'instance, il faut activerfsync=alwaysdans les paramètres de stockage de données à long terme. Cela va complètement tuer les performances, au niveau des systèmes CP traditionnellement utilisés pour implémenter en toute sécurité les verrous distribués.



Mais la situation est meilleure qu'il n'y paraît. En principe, l'algorithme reste sécurisé car lorsqu'une instance est redémarrée après un échec, 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. Nous attendrons donc l'expiration et la libération automatique de toutes les clés qui étaient actives au moment du refus.



En utilisant des redémarrages différés, il est en principe possible d'obtenir la sécurité sans aucune persistance à long terme dans Redis. Notez, cependant, que cela peut entraîner une pénalité d'accessibilité. Par exemple, si la plupart des instances échouent, le système deviendra globalement indisponible pendant la durée TTL (et aucune ressource ne pourra être bloquée pour le moment).



Augmenter la disponibilité de l'algorithme: étendre le verrou



Si le travail effectué par les clients consiste en de petites étapes, il est possible de raccourcir le délai d'expiration du verrou par défaut et de mettre en œuvre un mécanisme de prolongation du verrou. Fondamentalement, si le client est occupé avec des calculs et que la valeur d'expiration du verrou est dangereusement basse, vous pouvez envoyer à toutes les instances un script dans Lua pour étendre le TTL de la clé, si la clé existe toujours, et sa valeur est toujours aléatoire obtenue lorsque le verrou a été acquis.



Un client doit considérer un verrou comme réacquis uniquement s'il a réussi à verrouiller la plupart des instances au cours de la période de validité.



Cependant, techniquement, l'algorithme ne change pas dans ce cas, donc le nombre maximum de tentatives répétées pour acquérir des verrous doit être limité, sinon les propriétés d'accessibilité seront violées.


More articles:


All Articles