Selectie van leider-patroon

Gebruik dit patroon om de acties te coördineren die worden uitgevoerd door een verzameling samenwerkende exemplaren in een gedistribueerde toepassing door één exemplaar te selecteren als de leider, die vervolgens de verantwoordelijkheid krijgt voor het beheren van de andere exemplaren. Dit kan ertoe bijdragen dat exemplaren niet met elkaar conflicteren, bijvoorbeeld over gedeelde bronnen, of onbedoeld ingrijpen op het werk dat door andere exemplaren wordt uitgevoerd.

Context en probleem

Een gemiddelde cloudtoepassing heeft veel taken die op een gecoördineerde manier samenwerken. Deze taken kunnen allemaal exemplaren zijn die dezelfde code uitvoeren en die toegang tot dezelfde resources vereisen. Een andere mogelijkheid is dat ze gelijktijdig worden uitgevoerd en de afzonderlijke onderdelen van een complexe berekening voor hun rekening nemen.

De taakexemplaren worden mogelijk gedurende een groot deel van de tijd afzonderlijk uitgevoerd, maar het kan ook nodig zijn om de acties van elk exemplaar te coördineren om ervoor te zorgen dat ze geen conflicten veroorzaken, bijvoorbeeld over gedeelde resources, of per ongeluk ingrijpen op het werk dat door andere taakexemplaren wordt uitgevoerd.

Bijvoorbeeld:

• In een cloudsysteem met ondersteuning voor horizontaal schalen, kunnen meerdere exemplaren van dezelfde taak tegelijkertijd worden uitgevoerd, waarbij elk exemplaar een andere gebruiker bedient. Als deze exemplaren gegevens wegschrijven naar een gedeelde resource, is het nodig om hun acties te coördineren om te voorkomen dat een exemplaar de wijzigingen van andere exemplaren overschrijft.
• Als de taken op hetzelfde moment afzonderlijke elementen van een complexe berekening uitvoeren, moeten de resultaten worden geaggregeerd als alle taken zijn voltooid.

De taakexemplaren zijn allemaal gelijkwaardig, dus er is niet een natuurlijke leider die als coördinator of aggregator kan optreden.

Oplossing

Er moet één taakexemplaar worden geselecteerd dat optreedt als de leider, en dit exemplaar moet de acties van de andere, onderliggende taakexemplaren coördineren. Als alle taakexemplaren dezelfde code uitvoeren, zijn ze allemaal geschikt om als leider te fungeren. Het is dan ook belangrijk dat het selectieproces zorgvuldig wordt beheerd, om te voorkomen dat twee of meer exemplaren op hetzelfde moment de leiderrol overnemen.

Het systeem moet een krachtig mechanisme bieden voor het selecteren van de leider. Deze methode moet omgaan met gebeurtenissen zoals netwerkstoringen of fouten in het proces. In veel oplossingen controleren de onderliggende taakexemplaren de leider via een bepaald type heartbeat-methode, of door polling. Als de aangewezen leider onverwacht uitvalt, of een netwerkstoring tot gevolg heeft dat de leider niet meer beschikbaar is voor de onderliggende taakexemplaren, moeten de andere exemplaren een nieuwe leider selecteren.

Er zijn verschillende strategieën voor het selecteren van een leider uit een set taken in een gedistribueerde omgeving, zoals:

• Het taakexemplaar met de laagst scorende exemplaar- of proces-id selecteren.
• Het exemplaar selecteren dat als eerste een gedeelde, gedistribueerde mutex verkrijgt. Het eerste taakexemplaar dat de mutex verkrijgt, is de nieuwe leider. Als de leider uitvalt of niet meer kan communiceren met de rest van het systeem, moet het systeem ervoor zorgen dat de mutex wordt vrijgegeven zodat een ander taakexemplaar de leider kan worden.
• De implementatie van een van de algemene algoritmen voor het selecteren van een leider, zoals het Bully-algoritme of het Ring-algoritme. Deze algoritmen gaan ervan uit dat elke kandidaat een unieke id heeft en op een stabiele wijze kan communiceren met de andere kandidaten.

Problemen en overwegingen

Beschouw de volgende punten als u besluit hoe u dit patroon wilt implementeren:

• Het proces van het selecteren van een leider moet overweg kunnen met tijdelijke en permanente storingen.
• Het moet mogelijk zijn om te detecteren wanneer de leider is uitgevallen of anderszins niet meer beschikbaar is (zoals vanwege een communicatiestoring). Hoe snel deze detectie moet zijn, verschilt per systeem. Het is mogelijk dat sommige systemen korte tijd zonder een leider kunnen werken, zodat in die periode een eventuele tijdelijke fout kan worden opgelost. In andere gevallen kan het nodig zijn dat de uitval van de leider direct wordt gedetecteerd en dat er meteen een nieuwe leider wordt geselecteerd.
• In een systeem met ondersteuning voor automatisch horizontaal schalen, kan de leider wegvallen als het systeem terugschaalt en enkele rekenbronnen worden afgesloten.
• De keuze voor een gedeelde, gedistribueerde mutex betekent dat er sprake is van een afhankelijkheid van de externe service die de mutex levert. De service vormt een Single Point of Failure. Als de service om wat voor reden dan ook niet beschikbaar is, kan er geen leider worden geselecteerd.
• De keuze van een speciaal toegewezen proces als de leider is een ongecompliceerde benadering. Als het proces echter uitvalt, kan er een aanzienlijke vertraging optreden terwijl het proces opnieuw wordt opgestart. De resulterende latentie kan gevolgen hebben voor de prestaties en reactietijden van andere processen als deze wachten op het coördineren van een bewerking door de leider.
• Het handmatig implementeren van een van de algoritmen voor het selecteren van een leider biedt de grootste flexibiliteit bij het afstemmen en optimaliseren van de code.

Wanneer dit patroon gebruiken

Gebruik dit patroon wanneer de taken in een gedistribueerde toepassing, zoals een in de cloud gehoste oplossing, zorgvuldige coördinatie vereisen en er geen natuurlijke leider is.

Voorkom dat de leider een knelpunt wordt in het systeem. De leider heeft als doel het werk van de onderliggende taken te coördineren, en hoeft niet per se zelf deel te nemen aan dit werk—de leider moet hiertoe echter wel in staat zijn, voor het geval een ander exemplaar als de leider wordt geselecteerd.

In de volgende gevallen is dit patroon mogelijk niet geschikt:

• Er is een natuurlijke leider of een toegewezen proces dat altijd als de leider kan fungeren. Zo is het bijvoorbeeld mogelijk om een singleton-proces te implementeren dat de taakexemplaren coördineert. Als dit proces uitvalt of slecht functioneert, kan het systeem het proces afsluiten en opnieuw starten.
• De coördinatie tussen taken kan worden bereikt via een minder ingrijpende methode. Als verschillende taakexemplaren bijvoorbeeld alleen maar gecoördineerde toegang tot een gedeelde resource nodig hebben, kunt u beter kiezen voor optimistische of pessimistische vergrendeling om de toegang te regelen.
• Een oplossing van derden is meer geschikt. De Microsoft Azure HDInsight-service (op basis van Apache Hadoop) gebruikt bijvoorbeeld de services van Apache Zookeeper om de toewijzing te coördineren en het aantal taken te verkleinen die gegevens verzamelen en samenvatten.

Voorbeeld

Het project DistributedMutex in de oplossing LeaderElection (een voorbeeldtoepassing met dit patroon die beschikbaar is op GitHub) laat zien hoe u een lease op een Azure Storage-blob kunt gebruiken om een mechanisme te bieden voor het implementeren van een gedeelde, gedistribueerde mutex. Deze mutex kan worden gebruikt om een leider te selecteren uit een groep rolinstanties in een Azure-cloudservice. De eerste rolinstantie die de lease verkrijgt, wordt gekozen als de leider en blijft dit totdat de lease wordt vrijgegeven of niet kan worden vernieuwd. Andere rolinstanties kunnen de blob-lease blijven controleren voor het geval dat de leider niet meer beschikbaar is.

Een blob-lease is een exclusieve schrijfvergrendeling van een blob. Een blob kan altijd maar door één lease worden geclaimd. Een rolinstantie kan een lease aanvragen voor een bepaalde blob en deze lease wordt verleend als er geen andere rolinstantie is die een lease heeft van dezelfde blob. Anders veroorzaakt de aanvraag een uitzondering.

Om te voorkomen dat een rolinstantie die uitvalt de lease voor onbepaalde tijd kan vasthouden, moet u een levensduur voor de lease opgeven. Als deze is verlopen, komt de lease weer beschikbaar. Op het moment dat een rolinstantie echter beschikt over de lease, kan de instantie vragen om een verlenging van de lease, waarna de lease weer voor een nieuwe periode aan de instantie wordt toegekend. De rolinstantie kan dit proces continu herhalen en zo de lease behouden. Zie Lease Blob (REST-API) voor meer informatie over de lease van een blob.

De klasse BlobDistributedMutex in het voorbeeld met C# hieronder bevat de methode RunTaskWhenMutexAcquired waarmee een rolinstantie in staat wordt gesteld om een lease te verkrijgen voor een opgegeven blob. De details van de blob (de naam, de container en het opslagaccount) worden doorgegeven aan de constructor in een BlobSettings-object op het moment dat het BlobDistributedMutex-object wordt gemaakt (dit object is een eenvoudige struct die is opgenomen in de voorbeeldcode). De constructor accepteert ook een Task die verwijst naar de code die moet worden uitgevoerd door de rolinstantie als deze de lease van de blob heeft verkregen en is geselecteerd als de leider. De code die verantwoordelijk is voor het afhandelen van de details van het verkrijgen van de lease is geïmplementeerd in een afzonderlijke helperklasse met de naam BlobLeaseManager.

public class BlobDistributedMutex
{
  ...
  private readonly BlobSettings blobSettings;
  private readonly Func<CancellationToken, Task> taskToRunWhenLeaseAcquired;
  ...

  public BlobDistributedMutex(BlobSettings blobSettings,
           Func<CancellationToken, Task> taskToRunWhenLeaseAcquired)
  {
    this.blobSettings = blobSettings;
    this.taskToRunWhenLeaseAcquired = taskToRunWhenLeaseAcquired;
  }

  public async Task RunTaskWhenMutexAcquired(CancellationToken token)
  {
    var leaseManager = new BlobLeaseManager(blobSettings);
    await this.RunTaskWhenBlobLeaseAcquired(leaseManager, token);
  }
  ...

De methode RunTaskWhenMutexAcquired in het bovenstaande codevoorbeeld roept de methode RunTaskWhenBlobLeaseAcquired aan (zie het volgende codevoorbeeld) om daadwerkelijk in bezit te komen van de lease. De methode RunTaskWhenBlobLeaseAcquired wordt asynchroon uitgevoerd. Zodra de lease is verkregen, wordt de rolinstantie geselecteerd als de leider. Het doel van taskToRunWhenLeaseAcquired is het uitvoeren van het werk dat de andere rolinstanties coördineert. Als de lease niet wordt verkregen, is een andere rolinstantie gekozen als de leider en blijft de huidige rolinstantie een onderliggend exemplaar. De methode TryAcquireLeaseOrWait is een helpermethode die het BlobLeaseManager-object gebruikt voor het verkrijgen van de lease.

  private async Task RunTaskWhenBlobLeaseAcquired(
    BlobLeaseManager leaseManager, CancellationToken token)
  {
    while (!token.IsCancellationRequested)
    {
      // Try to acquire the blob lease.
      // Otherwise wait for a short time before trying again.
      string leaseId = await this.TryAcquireLeaseOrWait(leaseManager, token);

      if (!string.IsNullOrEmpty(leaseId))
      {
        // Create a new linked cancellation token source so that if either the
        // original token is canceled or the lease can't be renewed, the
        // leader task can be canceled.
        using (var leaseCts =
          CancellationTokenSource.CreateLinkedTokenSource(new[] { token }))
        {
          // Run the leader task.
          var leaderTask = this.taskToRunWhenLeaseAcquired.Invoke(leaseCts.Token);
          ...
        }
      }
    }
    ...
  }

De taak die wordt gestart door de leider wordt eveneens asynchroon uitgevoerd. Terwijl deze taak wordt uitgevoerd, probeert de methode RunTaskWhenBlobLeaseAcquired uit het volgende codevoorbeeld de lease periodiek te vernieuwen. Op deze manier wordt ervoor gezorgd dat de rolinstantie de leider blijft. In de voorbeeldoplossing is de vertraging tussen vernieuwingsaanvragen korter dan de tijd die is opgegeven voor de duur van de lease om te voorkomen dat een andere rolinstantie wordt gekozen als de leider. Als de vernieuwing om wat voor reden dan ook mislukt, wordt de taak geannuleerd.

Als het vernieuwen van de lease mislukt of als de taak wordt geannuleerd (mogelijk als gevolg van uitschakeling van de rolinstantie), wordt de lease vrijgegeven. Op dit moment wordt deze of een andere rolinstantie gekozen als de leider. Het codefragment hieronder illustreert een deel van het proces.

  private async Task RunTaskWhenBlobLeaseAcquired(
    BlobLeaseManager leaseManager, CancellationToken token)
  {
    while (...)
    {
      ...
      if (...)
      {
        ...
        using (var leaseCts = ...)
        {
          ...
          // Keep renewing the lease in regular intervals.
          // If the lease can't be renewed, then the task completes.
          var renewLeaseTask =
            this.KeepRenewingLease(leaseManager, leaseId, leaseCts.Token);

          // When any task completes (either the leader task itself or when it
          // couldn't renew the lease) then cancel the other task.
          await CancelAllWhenAnyCompletes(leaderTask, renewLeaseTask, leaseCts);
        }
      }
    }
  }
  ...
}

De methode KeepRenewingLease is een andere helpermethode die het BlobLeaseManager-object gebruikt voor het vernieuwen van de lease. De methode CancelAllWhenAnyCompletes annuleert de taken die zijn opgegeven als de eerste twee parameters. Het volgende diagram laat zien hoe u met behulp van de klasse BlobDistributedMutex een leider selecteert en een taak uitvoert die bewerkingen coördineert.

Het volgende codevoorbeeld toont hoe u de klasse BlobDistributedMutex gebruikt in een werkrol. Met deze code wordt een lease verkregen voor een blob met de naam MyLeaderCoordinatorTask, in de container van de lease in het opslagaccount van de ontwikkelomgeving. De code geeft verder aan dat de code die is gedefinieerd in de methode MyLeaderCoordinatorTask moet worden uitgevoerd als de rolinstantie als de leider wordt geselecteerd.

var settings = new BlobSettings(CloudStorageAccount.DevelopmentStorageAccount,
  "leases", "MyLeaderCoordinatorTask");
var cts = new CancellationTokenSource();
var mutex = new BlobDistributedMutex(settings, MyLeaderCoordinatorTask);
mutex.RunTaskWhenMutexAcquired(this.cts.Token);
...

// Method that runs if the role instance is elected the leader
private static async Task MyLeaderCoordinatorTask(CancellationToken token)
{
  ...
}

Enkele belangrijke aandachtspunten voor de voorbeeldoplossing:

• De blob is een potentieel Single Point of Failure. Als de blob-service niet meer beschikbaar is of niet toegankelijk is, kan de leider de lease niet vernieuwen en kan de lease niet worden overgenomen door een andere rolinstantie. Er is dan geen rolinstantie die kan optreden als de leider. De blob-service is echter ontworpen voor tolerantie, zodat een volledige uitval van de blob-service zeer onwaarschijnlijk is.
• Als de taak die wordt uitgevoerd door de leider vastloopt, kan de leider de lease blijven vernieuwen, waardoor wordt voorkomen dat een andere rolinstantie de lease overneemt en de taken gaat coördineren. In de praktijk moet de status van de leider dan ook regelmatig worden gecontroleerd.
• Het selectieproces is niet-deterministisch. U kunt geen veronderstellingen doen over welke rolinstantie de blob-lease zal verkrijgen en dus de leider wordt.
• De blob die wordt gebruikt als het doel van de blob-lease mag niet voor andere doeleinden worden gebruikt. Als een rolinstantie probeert om gegevens op te slaan in deze blob, zijn deze gegevens pas toegankelijk nadat de rolinstantie de leider is en eigenaar van de blob-lease.

Volgende stappen

De volgende richtlijnen zijn mogelijk ook relevant bij de implementatie van dit patroon:

• Voor dit patroon is een voorbeeldtoepassing beschikbaar die u kunt downloaden.
• Richtlijnen voor automatisch schalen. Het is mogelijk om exemplaren van de taakhosts te starten en stoppen naarmate de belasting van de toepassing varieert. Automatisch schalen kan helpen om de doorvoer en prestaties op peil te houden tijdens piekmomenten.
• Compute Partitioning Guidance (Richtlijnen voor rekenpartities). Hierin wordt beschreven hoe u in een cloudservice taken op zo'n manier taken kunt toewijzen aan hosts dat doorlopende kosten worden geminimaliseerd en tegelijkertijd de schaalbaarheid, prestaties, beschikbaarheid en beveiliging van de service behouden blijven.
• Het op taken gebaseerde Asynchrone patroon.
• Een voorbeeld ter illustratie van het Bully-algoritme.
• Een voorbeeld ter illustratie van het Ring-algoritme.
• Apache Curator, een clientbibliotheek voor Apache ZooKeeper.
• Het artikel Lease Blob (REST-API) op MSDN.