Sélection d'un leader dans les systèmes distribués

La sélection d'un leader est simplement l'idée de donner quelques pouvoirs spéciaux à un élément (un processus, un hôte, un thread, un objet ou un humain) faisant partie d'un système distribué. Il peut s'agir, par exemple, de la capacité d'affecter du travail, de la capacité de modifier des données, voire de la responsabilité de la gestion de toutes les requêtes du système.

La sélection d'un leader est un outil puissant permettant d'améliorer l'efficacité, de réduire la coordination, de simplifier les architectures et de réduire les opérations. En revanche, la sélection d'un leader peut introduire de nouveaux modes de défaillance et goulots d'étranglement en matière de mise à l'échelle. Elle peut également vous compliquer la tâche d'évaluation de l'exactitude d'un système.

Il convient, en raison de ces complications, d'étudier attentivement d'autres options avant d'implémenter la sélection d'un leader. En ce qui concerne le traitement des données et les flux de travail, les services de flux de travail comme AWS Step Functions apportent de nombreux avantages similaires à ceux de la sélection d'un leader tout en évitant les risques qu'elle implique. Pour d'autres systèmes, pensez à implémenter des API idempotentes, le verrouillage optimiste et d'autres modèles qui ne nécessitent pas un seul leader.

Dans cet article, nous allons voir quelques-uns des pour et des contre de la sélection d'un leader en général et les approches d'Amazon concernant la sélection d'un leader dans ses systèmes distribués, avec des analyses détaillées des défaillances liées aux leaders.

Il existe de nombreuses façons de sélectionner un leader : les algorithmes comme Paxos, les logiciels comme Apache ZooKeeper, le matériel personnalisé ou encore les locations. Les locations représentent le mécanisme de sélection d'un leader le plus utilisé au sein d'Amazon. Les locations sont relativement simples à comprendre et à implémenter et offrent souvent une tolérance aux pannes intégrée. Elles fonctionnent avec une base de données unique qui stocke le leader actuel. Ensuite, la location requière une pulsion régulière du leader pour s'assurer qu'il est toujours le leader. Si la pulsion du leader existant disparait après un certain temps, d'autres leaders candidats peuvent essayer de prendre le relais.

Nous évitons la dépendance au temps dans les systèmes distribués, malgré l'excellente fonction de synchronisation du temps dans Amazon Elastic Compute Cloud(Amazon EC2). Il est difficile de s'assurer que les horloges d'un système de cluster sont assez synchronisées pour déprendre de cette synchronisation pour la commande ou la coordination des opérations distribuées. Chez Amazon, les systèmes distribués utilisent le temps uniquement pour la consommation humaine. Les locations dépendent du temps. Cependant, elles dépendent seulement d'une certaine durée locale, plutôt que d'un temps de calcul synchronisé qui doit être convenu plusieurs serveurs.

Le code source de client de verrou DynamoDB fournit des exemples et des informations détaillées sur la sélection d'un leader. Néanmoins, nous avons découvert que même si les locations et les verrous sont simples sur le plan conceptuel, les implémenter correctement peut s'avérer délicat. En effet, il faut comprendre comment un serveur mesure la durée locale pour les implémenter. Par exemple, si un serveur ou une bibliothèque qui mesure le temps pensait que le temps revenait en arrière ponctuellement, il contredirait l'hypothèse selon laquelle les durées sont intégrées à des locations. Les durées contournent les problèmes avec la synchronisation d'horloge globale qui empêchent les serveurs de se mettre d'accord sur l'heure qu'il est, des secondes intercalaires au décalage d'horloge locale au fil du temps en raison d'une utilisation constamment soutenue du processeur.

Un problème plus grave des locations et de tous les types de verrous distribués est qu'il faut s'assurer que le leader effectue le travail uniquement lorsqu'il détient le verrou. S'assurer que le leader détient le verrou se révèle être assez difficile. Nous avons découvert qu'il est important de s'assurer qu'un leader sur un réseau lent ou à pertes ne croit pas qu'il détient des verrous pour une durée plus longue qu'en réalité. De même, les pauses de nettoyage de mémoire entre un verrou en cours de vérification et un travail en cours de réalisation peuvent entraîner un comportement incorrect. Dans la pratique, résoudre ces problèmes constitue souvent la principale difficulté.

DynamoDB et ZooKeeper fournissent des clients de verrouillage simples basés sur des locations qui procurent une sélection du leader tolérante aux pannes. Sauf en cas de besoins particuliers, nous préférons ces clients, car nous pensons qu'ils sont le moyen le plus facile et le plus testé d'implémenter une sélection de leader. Les équipes d'Amazon préfèrent éviter de créer une implémentation de sélection de leader personnalisée. Nous favorisons plutôt les clients existants éprouvés et aguerris.

La sélection de leader est un modèle largement déployé au sein d'Amazon. Par exemple :

• Presque tous les systèmes utilisant des systèmes de gestion de base de données relationnelle (SGBDR) classiques reposent sur la sélection de leader pour choisir une base de données de leaders qui gère toutes les écritures et parfois toutes les lectures. Dans ces systèmes, la sélection peut être automatisée, mais elle est souvent effectuée manuellement par un opérateur humain.
• Amazon EBS distribue des lectures et des écritures pour un volume sur de nombreux serveurs de stockage. Par souci d'uniformité, il a recours à la sélection d’un leader pour élire des primaires pour chaque partie du volume, qui en ordonne la lecture et l'écriture. Si cette primaire échoue, le suiveur copie les étapes en utilisant le même mécanisme de sélection du leader. Dans Amazon EBS, la sélection du leader assure la cohérence et améliore les performances en évitant la coordination sur le plan de données. DynamoDB, Amazon Quantum Ledger Database (Amazon QLDB) et Amazon Kinesis (Kinesis) utilisent des approches similaires pour les mêmes raisons.
• La Kinesis Client Library (KCL) utilise les locations pour s'assurer que chaque partition est traitée par un seul propriétaire, ce qui facilite le traitement évolutif des flux Kinesis.

Il est également important de réfléchir sérieusement à ce qu'il arrive au travail d'un leader lorsque ce dernier tombe en panne. Si un leader tombe en panne pendant une tâche, comment le nouveau leader termine-t-il la tâche ? Si un leader tombe en panne avant de rendre son travail durable, le système est-il toujours correct ? Les étapes « rendre le travail durable » et « informer qu'il est terminé » sont distinctes dans de nombreux types de systèmes. Chez Amazon, nos systèmes effectuent la première étape, puis la deuxième (ou tolèrent la perte de données). Une fois de plus, l'idempotence est utile. Elle permet au nouveau leader de rediriger en toute confiance le travail que le leader sortant a partiellement ou totalement effectué sans en informer les autres.

Pour tolérer les pannes, les systèmes distribués d'Amazon n'ont pas de leader unique. À la place, le leadership est une propriété qui passe de serveur à serveur ou de processus à processus. Dans les systèmes distribués, il n'est pas possible de garantir que le système comporte précisément un leader. La plupart du temps, il comporte un leader, mais il peut également en comporter aucun ou deux en cas de pannes.

Le choix de comportement du système en cas de défaillance du leader dépend de ce qu'il se passe dans un système lorsqu'il comporte deux leaders. Les systèmes qui effectuent des tâches idempotentes peuvent souvent tolérer deux leaders avec une perte minimale d'efficacité. Avec deux leaders, les systèmes peuvent avoir davantage de disponibilité et choisir des approches de sélection du leader plus faibles.

Les systèmes qui doivent impérativement avoir un seul leader sont plus difficiles à construire que les systèmes à leaders multiples. Le système de sélection du leader doit toujours être correct et cohérent. Il doit également garantir que le leader sortant est destitué avant que le nouveau leader soit sélectionné, ce qui est plus difficile qu'on ne le pense. Dans les systèmes distribués, il est souvent difficile de savoir si un système est en panne ou s'il poursuit simplement son travail dans une autre partition de réseau. Chez Amazon, nous nous assurons que tous les systèmes à leaders sélectionnés gèrent ce genre de cas limites.

Chez Amazon, nous suivons les bonnes pratiques suivantes pour la sélection du leader :

• Nous vérifions souvent le temps de location restant (ou le statut du verrou en général), en particulier avant de démarrer n'importe quelle opération ayant des effets secondaires au-delà du leader lui-même.
• Nous prenons en compte le fait que les réseaux lents, les délais d'expiration, les nouvelles tentatives et les pauses de nettoyage de mémoire peuvent entraîner une expiration du temps de location restant avant l'expiration prévue par le code.
• Nous évitons les locations de pulsions dans les threads en arrière-plan, qui peuvent entraîner des problèmes d'exactitude si le thread ne peut pas interrompre le code lorsque la location expire ou le thread de pulsion meurt. Des problèmes de disponibilité peuvent se produire si le thread de travail meurt ou s'arrête alors que le thread de pulsion se cramponne à la location.
• Nous avons des métriques fiables qui montrent la quantité de travail qu'un leader peut effectuer par rapport à celle qu'il effectue actuellement. Il convient de revoir souvent ces métriques et de s'assurer de la présence de plans pour la mise à l'échelle avant de manquer de capacité.
• Nous facilitons la recherche de l'hôte dans lequel le leader actuel se trouve et de l'hôte dans lequel le leader se trouvait à un moment donné. Il convient de conserver un suivi ou un journal d'audit des changements de leadership.
• Nous modélisons et nous vérifions formellement l'exactitude des algorithmes distribués à l'aide d'outils tes que TLA+. Ce dernier met en cache les bogues rares, subtiles et difficiles à observer qui peuvent survenir lorsqu'une application émet trop de suppositions sur les garanties fournies par le protocole de la sélection du leader.

La sélection du leader est un outil puissant utilisé dans les systèmes au sein d'Amazon pour que nos systèmes soient plus tolérants aux pannes et faciles à utiliser. Cependant, lorsque nous utilisons la sélection de leader, nous prenons soin d'examiner les garanties que chaque protocole de sélection du leader fournit, et plus important encore, qu'il ne fournit pas.

Les systèmes Amazon utilisent souvent la sélection du leader pour garantir une tolérance aux pannes intégrée. Lorsque les systèmes utilisent la sélection du leader pour garantir qu'au moins un serveur traite une tâche, ils utilisent des mécanismes distincts pour maintenir l'exactitude face aux nombreux leaders concurrents. Par exemple, ils peuvent utiliser une base de données sous-jacente pour s'assurer que si deux leaders pensent qu'ils détiennent tous deux une location, ils n'interfèrent pas entre eux. Plutôt que d'émettre des suppositions sur les garanties fournies par l'implémentation d'une location, nous nous concentrons sur l'exactitude de ces systèmes, souvent à l'aide de la modélisation avec des techniques comme TLA+.

Malgré ses subtilités, la sélection du leader reste un outil utile dans notre boîte à outils de systèmes distribués chez Amazon, parallèlement aux modèles tels que l'idempotence et le verrouillage optimiste.

Pour plus d'informations sur le fonctionnement de ces locations, consultez la documentation suivante :

• How to do distributed locking (Comment réaliser le verrouillage distribué)
• Burrows, The Chubby lock service for loosely-coupled distributed systems (Le service de verrouillage Chubby pour les systèmes distribués à couplage lâche)
• Gray and Cheriton, Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency (Locations : un mécanisme tolérant aux pannes et efficace pour la cohérence de mise en cache de fichiers distribuée)