Je travaille actuellement sur un système distribué où nous devons mettre en œuvre une sorte de Election Leader . Le problème est que nous aimerions éviter que tous les ordinateurs se connaissent - mais seulement le leader. Y a-t-il un moyen rapide où nous pouvons utiliser par exemple diffuser pour atteindre ce que nous voulons?
ou est-ce que nous devons simplement en savoir au moins un, pour effectuer une bonne élection de leader?
Il est assuré que tous les ordinateurs sont sur le même sous-réseau.
Merci pour votre aide.
5 Réponses :
Comme l'une des solutions intéressantes de la mécanique distribuée que j'ai voir la dernière fois que je recommanderais Apache Projet ZookePer . Ceci est une solution open source, donc au moins, vous devriez pouvoir obtenir quelques idées à partir de là. En outre, il se développe de manière intensive afin que vous puissiez probablement la réutiliser comme faisant partie de votre solution.
ZOOEPER est un service centralisé pour maintenir la configuration informations, nommage, fournissant une synchronisation distribuée et fournir des services de groupe. Tous ces types de services sont utilisés dans une forme ou une autre par des applications distribuées. Chaque fois qu'ils sont mis en œuvre il y a beaucoup de travail qui consiste à réparer les bugs et conditions de course inévitables. À cause de la difficulté de Mise en œuvre de ces types de services, des applications initialement habituellement lésinant sur eux, qui les rendent fragiles en présence de changement et difficile à gérer. Même lorsque cela est fait correctement, différent les implémentations de ces services conduisent à la complexité de la gestion lorsque Les applications sont déployées.
Je recommanderais des jgroups pour résoudre ce problème - en supposant que vous construisez un système au-dessus de la JVM.
Utilisez le verrouillage pour vous assurer que seul 1 noeud dans le cluster est le leader. Les jGroups peuvent être configurés pour utiliser un verrou à pair ou un verrou central - soit fonctionner dans votre cas.
voir http://withmeta.blogspot.com /2014/01/leader-élections-problem-in-élastique.html pour une implémentation de clojure ou http://javabender.blogspot.com.au/2012/01/jgroups-lockservice-example.html pour un Java One.
La question n'implique pas Java ou une langue en particulier.
Le problème est que nous aimerions éviter que tous les ordinateurs doivent se connaître - mais seul le leader.
L'élection du leader est le problème de la sélection d'un seul chef de file d'un ensemble de candidats de leader potentiels. Regardez-le comme ayant deux propriétés requises: véridique et sécurité . Ici, véridique signifierait "la plupart du temps, il y a un leader", tandis que la sécurité signifierait "il y a zéro ou un leaders". Considérons comment nous résolvons cette propriété de sécurité dans votre exemple, en utilisant la diffusion.
Choisissons un algorithme simple (cassé), en supposant que chaque nœud a une carte d'identité unique. Chaque nœud diffuse son identifiant et écoute. Lors de la réception d'un ID plus élevé que le sien, il cesse de participer. S'il reçoit un identifiant inférieur à celui de celui-ci, il envoie la diffusion saople à nouveau. En supposant un réseau synchrone, la dernière identification reçoit que tout le monde est l'ID du leader. Maintenant, introduisez une partition réseau. Le protocole continuera volontiers de chaque côté de la partition et deux dirigeants seront élus.
C'est vrai de ce protocole brisé, mais il est également vrai de tous les protocoles possibles. Comment indiquez-vous la différence entre les nœuds que vous ne pouvez pas communiquer avec et les nœuds qui n'existent pas si vous ne connaissez pas (au moins) combien de nœuds existent? Il y a donc un premier la sécurité : vous devez savoir combien de nœuds existent, ou vous ne pouvez pas vous assurer qu'il n'y a qu'un seul chef.
Maintenant, relaxons notre Safety la contrainte pour être un problème probabiliste: "Il peut y avoir zéro ou plusieurs dirigeants, mais la plupart du temps, il y en a un". Cela rend le problème difficile et une solution largement utilisée est des potages (protocoles d'épidémie). Par exemple, voir Un service de détection de défaillance de style potins qui discute d'une variante de ce problème exact. Le document concerne principalement la détection et l'énumération de défaillance correcte probabilitues, mais si vous pouvez le faire, vous pouvez également faire une élection de leader correcte probabiliste.
Autant que je puisse dire, vous ne pouvez pas avoir une élection de leader non probabiliste en toute sécurité dans les réseaux généraux sans au moins énumérer les participants.
En fait, il y a un moyen d'éviter de connaître tous les dirigeants. Tout ce qu'il faut est un point de rencontre fiable. Pensez à "place de stationnement". Nous ne connaissons pas tous les pilotes possibles. Néanmoins, il y a au plus une voiture garée.
Une solution pratique consiste à utiliser dB comme "réunion".
Cette solution est très pratique spécialement si vous utilisez déjà SQL DB, tout ce qu'il faut est une nouvelle table. Si vous utilisez un cluster de DB, vous pouvez profiter de sa haute disponibilité. P>
Voici le tableau Mes utilisations de la mise en œuvre: P>
class SqlLease {
private ISqlLeaseDal _dal;
private string _resourceId;
private string _myId;
public SqlLease(ISqlLeaseDal dal, string resourceId) {
_dal = dal;
_resourceId = resourceId;
_myId = Guid.NewGuid().ToString();
}
class LeaseRow {
public string ResourceId {get; set;}
public string OwnerId {get; set;}
public Datetime Expiration {get; set;}
public byte[] RowVersion {get; set;}
}
public bool TryAcquire(Datetime expiration) {
expiration = expiration.ToUniversalTime();
if (expiration < DateTime.UtcNow) return false;
try {
var row = _dal.FindRow(_resourceId);
if (row != null) {
if (row.Expiration >= DateTime.UtcNow && row.OwnerId != _myId) {
return false;
}
row.OwnerId = _myId;
row.Expiration = expiration;
_dal.Update(row);
return true;
}
_dal.Insert(new LeaseRow {
ResourceId = _resourceId,
OwnerId = _myId,
Expiration = expiration,
});
return true;
} catch (SqlException e) {
if (e.Number == 2601 || e.Number == 2627) return false;
throw e;
} catch (DBConcurrencyException) {
return false;
}
}
}
Le problème avec cette approche est qu'il n'a pas échoué. Si vous continuez à utiliser la DB pour chaque chef des élections que vous tombez sur une plate-forme plus grande, suffisamment, le DB est étrangeté en manipulant des serrures et ne peut pas servir des données. J'ai vu cela arriver dans la vie réelle malheureusement
@marc l'a décrit très bien. Je voudrais ajouter quelques points dessus.
Si tous les systèmes participants ne doivent pas se connaître les uns des autres, l'ID de radiodiffusion (ou dire TimeStamp) ne révèle pas son état à moins qu'il ne soit élu en tant que chef. Une fois élu en tant que dirigeant, il peut maintenant diffuser l'état de la machine pour tous les autres nœuds du cluster pour se connecter.
Si les systèmes participants ne doivent pas du tout révéler leur présence, il doit y avoir un système pour communiquer par ex. un dB (comme mentionné par Igor), un système basé sur TCP ou un emplacement monté (la manière dont ZooKePer élit) Lorsque toutes les machines l'état sont stockées, mais le moindre (ou le premier est disponible avec une autorisation de lecture) et le responsable continue de mettre à jour son état de ce système. Si le responsable tombe, le système choisit le nœud suivant comme leader en le permettant de lire à d'autres nœuds nettoient la dernière entrée de leader.
Zookeeper crée un nœud éphémère disponible pour lire tous les nœuds. Ce comportement peut être remplacé par uniquement le nœud supérieur disponible pour lire chaque fois qu'il y a une modification de l'état du cluster.
La concurrence ne peut être un problème que si un grand nombre de nœuds commencent en même temps (en millisecondes) et le système intermédiaire prend trop de temps pour renvoyer un résultat minuscule.
Avec la description du problème que vous donnez, il est difficile de faire autre chose que de vous référer à l'article Wikipedia que vous avez déjà donné. Pouvez-vous donner plus de détails, peut-être dire pourquoi les algorithmes énumérés dans la page Wikipedia ne fournissaient pas ce dont vous avez besoin?
Salut Blubb. Autant que je puisse voir les algorithmes de la page Wikipedia exigent que tous les ordinateurs connaissent tous les autres ordinateurs. Mais j'aimerais trouver une solution qui fonctionne quand ils ne se connaissent pas. Pouvez-vous me suivre? Quel est le coût d'utilisation de multidiffusion / diffusion. Est-il linéaire au nombre d'ordinateurs du groupe ou dépend-il seulement de la quantité de données que vous voulez envoyer?
Pas vraiment. Par exemple, je ne vois pas comment le algorithme intimidateur compterait sur des ordinateurs se sachant mutuellement. En fait, il repose sur la radiodiffusion. Pourriez-vous donner une description précise de ce que vous «connaissez-vous» des termes techniques ou théoriques?
De plus, vous devez spécifier quel modèle d'échec vous supposez. Supposez-vous que tous les ordinateurs sont opérationnels (correctement) tout le temps? Supposez-vous que les ordinateurs peuvent mourir soudainement? Ou même devenir fou et agir malicieusement?
Salut Blubb. Ce que je veux dire par, ne nous connaissant pas, est que nous avons un graphique non connecté (aucun bord contenu). Nous devons gérer des ordinateurs qui meurent soudainement. Comment fonctionner l'algorithme de balle, s'ils ne se connaissent pas. Nous ne pouvons pas comparer les identifiants uniques si nous ne les connaissons pas?