Padrão de eleição de líderLeader Election pattern

Coordene as ações executadas por uma coleção de instâncias de colaboração em um aplicativo distribuído elegendo uma instância como o líder que assume a responsabilidade de gerenciar as demais.Coordinate the actions performed by a collection of collaborating instances in a distributed application by electing one instance as the leader that assumes responsibility for managing the others. Isso pode ajudar a garantir que as instâncias não entrem em conflito com outras, causar contenção de recursos compartilhados ou interferir inadvertidamente no trabalho que outras instâncias estão executando.This can help to ensure that instances don't conflict with each other, cause contention for shared resources, or inadvertently interfere with the work that other instances are performing.

Contexto e problemaContext and problem

Um aplicativo de nuvem típico tem muitas tarefas que funcionam de maneira coordenada.A typical cloud application has many tasks acting in a coordinated manner. Essas tarefas poderiam ser instâncias que executam o mesmo código e precisam de acessar aos mesmos recursos ou podem estar trabalhando juntas em paralelo para executar as partes individuais de um cálculo complexo.These tasks could all be instances running the same code and requiring access to the same resources, or they might be working together in parallel to perform the individual parts of a complex calculation.

As instâncias de tarefa poderão ser executadas separadamente pela maior parte do tempo, mas também pode ser necessário coordenar as ações de cada instância para garantir que eles não entrem em conflito, causem contenção dos recursos compartilhados ou interfiram acidentalmente no trabalho que outras instâncias de tarefa estão executando.The task instances might run separately for much of the time, but it might also be necessary to coordinate the actions of each instance to ensure that they don’t conflict, cause contention for shared resources, or accidentally interfere with the work that other task instances are performing.

Por exemplo:For example:

  • Em um sistema baseado em nuvem que implementa o dimensionamento horizontal, várias instâncias da mesma tarefa podem estar em execução ao mesmo tempo com cada instância atendendo a um usuário diferente.In a cloud-based system that implements horizontal scaling, multiple instances of the same task could be running at the same time with each instance serving a different user. Se essas instâncias gravarem em um recurso compartilhado, será necessário coordenar suas ações para impedir que cada instância substitua as alterações feitas por outras.If these instances write to a shared resource, it's necessary to coordinate their actions to prevent each instance from overwriting the changes made by the others.
  • Se as tarefas estão executando elementos individuais de um cálculo complexo em paralelo, os resultados precisam ser agregados quando todos forem concluídos.If the tasks are performing individual elements of a complex calculation in parallel, the results need to be aggregated when they all complete.

Todas as instâncias de tarefa são pares, portanto não há um líder natural que possa atuar como o coordenador ou agregador.The task instances are all peers, so there isn't a natural leader that can act as the coordinator or aggregator.

SoluçãoSolution

Uma única instância de tarefa deve ser eleita para atuar como líder e essa instância deve coordenar as ações de outras instâncias de tarefa subordinada.A single task instance should be elected to act as the leader, and this instance should coordinate the actions of the other subordinate task instances. Se todas as instâncias de tarefa executarem o mesmo código, qualquer uma delas poderá atuar como o líder.If all of the task instances are running the same code, they are each capable of acting as the leader. Portanto, o processo de eleição deve ser gerenciado com cuidado para evitar que duas ou mais instâncias assumam a função de líder ao mesmo tempo.Therefore, the election process must be managed carefully to prevent two or more instances taking over the leader role at the same time.

O sistema deve fornecer um mecanismo robusto para selecionar o líder.The system must provide a robust mechanism for selecting the leader. Esse método precisa lidar com eventos como interrupções da rede ou falhas de processo.This method has to cope with events such as network outages or process failures. Em muitas soluções, as instâncias de tarefa subordinadas monitoram o líder por meio de algum tipo de método de pulsação ou por meio de sondagem.In many solutions, the subordinate task instances monitor the leader through some type of heartbeat method, or by polling. Se o líder designado terminar inesperadamente ou se uma falha de rede deixar o líder indisponível para as instâncias de tarefa subordinadas, será necessário eleger um novo líder.If the designated leader terminates unexpectedly, or a network failure makes the leader unavailable to the subordinate task instances, it's necessary for them to elect a new leader.

Há várias estratégias para eleger o líder entre um conjunto de tarefas em um ambiente distribuído, incluindo:There are several strategies for electing a leader among a set of tasks in a distributed environment, including:

  • Selecionar a instância da tarefa com a ID de processo ou instância mais baixa.Selecting the task instance with the lowest-ranked instance or process ID.
  • Corrida para adquirir um mutex compartilhado e distribuído.Racing to acquire a shared, distributed mutex. A primeira instância de tarefa que adquirir o mutex é o líder.The first task instance that acquires the mutex is the leader. No entanto, o sistema deve garantir que, se o líder for encerrado ou desconectado do restante do sistema, o mutex será liberado para permitir que outra instância de tarefa torne-se o líder.However, the system must ensure that, if the leader terminates or becomes disconnected from the rest of the system, the mutex is released to allow another task instance to become the leader.
  • Implementação de um dos algoritmos comuns de eleição de líder, como o Algoritmo Bully ou Algoritmo Ring.Implementing one of the common leader election algorithms such as the Bully Algorithm or the Ring Algorithm. Esses algoritmos presumem que cada candidato na eleição tem uma ID exclusiva e que ele pode se comunicar com os outros candidatos de maneira confiável.These algorithms assume that each candidate in the election has a unique ID, and that it can communicate with the other candidates reliably.

Problemas e consideraçõesIssues and considerations

Considere os seguintes pontos ao decidir como implementar esse padrão:Consider the following points when deciding how to implement this pattern:

  • O processo de eleger um líder deve ser resistente a falhas transitórias e persistentes.The process of electing a leader should be resilient to transient and persistent failures.
  • Deve ser possível detectar quando o líder falhou ou ficou indisponível (por exemplo, devido a uma falha de comunicação).It must be possible to detect when the leader has failed or has become otherwise unavailable (such as due to a communications failure). A rapidez de detecção necessária depende do sistema.How quickly detection is needed is system dependent. Alguns sistemas podem funcionar por um curto período sem um líder, durante o qual uma falha temporária pode ser corrigida.Some systems might be able to function for a short time without a leader, during which a transient fault might be fixed. Em outros casos, pode ser necessário detectar a falha do líder imediatamente e disparar uma nova eleição.In other cases, it might be necessary to detect leader failure immediately and trigger a new election.
  • Em um sistema que implementa o dimensionamento automático horizontal, o líder poderia ser terminado se o sistema for reduzido e desligar alguns dos recursos de computação.In a system that implements horizontal autoscaling, the leader could be terminated if the system scales back and shuts down some of the computing resources.
  • Usar um mutex compartilhado e distribuído apresenta uma dependência do serviço externo que fornece o mutex.Using a shared, distributed mutex introduces a dependency on the external service that provides the mutex. O serviço constitui um ponto único de falha.The service constitutes a single point of failure. Se ele ficar indisponível por qualquer motivo, o sistema não poderá eleger um líder.If it becomes unavailable for any reason, the system won't be able to elect a leader.
  • Usar um único processo dedicado como o líder é uma abordagem simples.Using a single dedicated process as the leader is a straightforward approach. No entanto, se o processo falhar, poderá ocorrer um atraso significativo enquanto ele é reiniciado.However, if the process fails there could be a significant delay while it's restarted. A latência resultante pode afetar o desempenho e os tempos de resposta de outros processos se eles estiverem esperando o líder coordenar uma operação.The resulting latency can affect the performance and response times of other processes if they're waiting for the leader to coordinate an operation.
  • Implementar um dos algoritmos de eleição de líder manualmente oferece a maior flexibilidade possível para ajustar e otimizar o código.Implementing one of the leader election algorithms manually provides the greatest flexibility for tuning and optimizing the code.

Quando usar esse padrãoWhen to use this pattern

Use esse padrão quando as tarefas em um aplicativo distribuído, como uma solução hospedada na nuvem, precisarem de coordenação cuidadosa e não houver nenhum líder natural.Use this pattern when the tasks in a distributed application, such as a cloud-hosted solution, need careful coordination and there's no natural leader.

Evite transformar o líder em um gargalo no sistema.Avoid making the leader a bottleneck in the system. É a finalidade do líder coordenar o trabalho das tarefas subordinadas e ele não precisa necessariamente participar desse trabalho em si — embora deva ser capaz de fazer isso se a tarefa não for eleita como o líder.The purpose of the leader is to coordinate the work of the subordinate tasks, and it doesn't necessarily have to participate in this work itself—although it should be able to do so if the task isn't elected as the leader.

Esse padrão pode não ser útil se:This pattern might not be useful if:

  • Há um líder natural ou processo dedicado que sempre pode atuar como o líder.There's a natural leader or dedicated process that can always act as the leader. Por exemplo, seria possível implementar um processo de singleton que coordena as instâncias de tarefa.For example, it might be possible to implement a singleton process that coordinates the task instances. Se esse processo falhar ou se tornar não íntegro, o sistema poderá desligá-lo e reiniciá-lo.If this process fails or becomes unhealthy, the system can shut it down and restart it.
  • A coordenação entre as tarefas pode ser alcançada usando um método mais simples.The coordination between tasks can be achieved using a more lightweight method. Por exemplo, se várias instâncias de tarefa precisam simplesmente de acesso coordenado a um recurso compartilhado, uma solução melhor é usar o bloqueio otimista ou pessimista para controlar o acesso.For example, if several task instances simply need coordinated access to a shared resource, a better solution is to use optimistic or pessimistic locking to control access.
  • Uma solução de terceiros é mais apropriada.A third-party solution is more appropriate. Por exemplo, o serviço do Microsoft Azure HDInsight (baseado em Apache Hadoop) usa os serviços fornecidos pelo Apache Zookeeper para coordenar o mapa e reduzir as tarefas que coletam e resumem os dados.For example, the Microsoft Azure HDInsight service (based on Apache Hadoop) uses the services provided by Apache Zookeeper to coordinate the map and reduce tasks that collect and summarize data.

ExemploExample

O projeto DistributedMutex na solução LeaderElection (um exemplo que demonstra esse padrão está disponível no GitHub) mostra como usar uma concessão em um Azure Storage Blob para fornecer um mecanismo para implementar um mutex compartilhado e distribuído.The DistributedMutex project in the LeaderElection solution (a sample that demonstrates this pattern is available on GitHub) shows how to use a lease on an Azure Storage blob to provide a mechanism for implementing a shared, distributed mutex. O mutex pode ser usado para eleger um líder dentre um grupo de instâncias de função em um serviço de nuvem do Azure.This mutex can be used to elect a leader among a group of role instances in an Azure cloud service. A primeira instância de função a adquirir a concessão é eleita como líder e permanece dessa forma até liberar a concessão ou não for capaz de renová-la.The first role instance to acquire the lease is elected the leader, and remains the leader until it releases the lease or isn't able to renew the lease. Outras instâncias de função podem continuar a monitorar a concessão de blob caso o líder não esteja mais disponível.Other role instances can continue to monitor the blob lease in case the leader is no longer available.

Uma concessão de blob é um bloqueio de gravação exclusivo em um blob.A blob lease is an exclusive write lock over a blob. Um único blob pode estar sujeito a apenas uma concessão ao mesmo tempo.A single blob can be the subject of only one lease at any point in time. Uma instância de função pode solicitar uma concessão em um blob especificado e ele receberá a concessão se nenhuma outra instância de função mantém uma concessão no mesmo blob.A role instance can request a lease over a specified blob, and it'll be granted the lease if no other role instance holds a lease over the same blob. Caso contrário, a solicitação gerará uma exceção.Otherwise the request will throw an exception.

Para evitar que uma instância de função com falha retenha a concessão indefinidamente, especifique um tempo de vida para a concessão.To avoid a faulted role instance retaining the lease indefinitely, specify a lifetime for the lease. Quando ele expirar, a concessão ficará disponível.When this expires, the lease becomes available. No entanto, enquanto uma instância de função contém a concessão, ela pode solicitar a renovação da concessão e ela será concedida por um período adicional.However, while a role instance holds the lease it can request that the lease is renewed, and it'll be granted the lease for a further period of time. A instância de função pode repetir continuamente esse processo se desejar manter a concessão.The role instance can continually repeat this process if it wants to retain the lease. Para obter mais informações sobre como conceder um blob, consulte Blob de concessão (API REST).For more information on how to lease a blob, see Lease Blob (REST API).

A classe BlobDistributedMutex no exemplo de C# a seguir contém o método RunTaskWhenMutexAcquired que permite que uma instância de função tente adquirir uma concessão em um blob especificado.The BlobDistributedMutex class in the C# example below contains the RunTaskWhenMutexAcquired method that enables a role instance to attempt to acquire a lease over a specified blob. Os detalhes do blob (o nome, contêiner e conta de armazenamento) são passados para o construtor em um objeto BlobSettings quando o objeto BlobDistributedMutex é criado (esse objeto é uma struct simples incluído no código de exemplo).The details of the blob (the name, container, and storage account) are passed to the constructor in a BlobSettings object when the BlobDistributedMutex object is created (this object is a simple struct that is included in the sample code). O construtor também aceita um Task que referencia o código que a instância de função deve executar se adquirir a concessão do blob com êxito e for eleito como líder.The constructor also accepts a Task that references the code that the role instance should run if it successfully acquires the lease over the blob and is elected the leader. Observe que o código que manipula os detalhes de nível baixo da aquisição da concessão é implementado em uma classe auxiliar separada chamada BlobLeaseManager.Note that the code that handles the low-level details of acquiring the lease is implemented in a separate helper class named 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);
  }
  ...

O método RunTaskWhenMutexAcquired no exemplo de código acima invoca o método RunTaskWhenBlobLeaseAcquired mostrado no exemplo de código a seguir para, na verdade, adquirir a concessão.The RunTaskWhenMutexAcquired method in the code sample above invokes the RunTaskWhenBlobLeaseAcquired method shown in the following code sample to actually acquire the lease. O método RunTaskWhenBlobLeaseAcquired é executado de forma assíncrona.The RunTaskWhenBlobLeaseAcquired method runs asynchronously. Se a concessão for adquirida com êxito, a instância de função foi eleita como o líder.If the lease is successfully acquired, the role instance has been elected the leader. A finalidade do delegado taskToRunWhenLeaseAcquired é executar o trabalho que coordena as outras instâncias de função.The purpose of the taskToRunWhenLeaseAcquired delegate is to perform the work that coordinates the other role instances. Se a concessão não for adquirida, outra instância de função foi eleita como o líder e a instância de função atual permanece sendo uma subordinada.If the lease isn't acquired, another role instance has been elected as the leader and the current role instance remains a subordinate. Observe que o TryAcquireLeaseOrWait é um método auxiliar que usa o objeto BlobLeaseManager para adquirir a concessão.Note that the TryAcquireLeaseOrWait method is a helper method that uses the BlobLeaseManager object to acquire the 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);
          ...
        }
      }
    }
    ...
  }

A tarefa iniciada pelo líder também é executada assincronamente.The task started by the leader also runs asynchronously. Enquanto essa tarefa está em execução, o método RunTaskWhenBlobLeaseAcquired mostrado no exemplo de código a seguir tenta periodicamente renovar a concessão.While this task is running, the RunTaskWhenBlobLeaseAcquired method shown in the following code sample periodically attempts to renew the lease. Isso ajuda a garantir que a instância de função permaneça sendo o líder.This helps to ensure that the role instance remains the leader. Na solução de exemplo, o atraso entre as solicitações de renovação é menor que o tempo especificado para a duração da concessão a fim de impedir que outra instância de função seja eleita como o líder.In the sample solution, the delay between renewal requests is less than the time specified for the duration of the lease in order to prevent another role instance from being elected the leader. Se a renovação falhar por algum motivo, a tarefa será cancelada.If the renewal fails for any reason, the task is canceled.

Se a concessão não puder ser renovada ou a tarefa for cancelada (provavelmente devido ao desligamento da instância de função), a concessão será liberada.If the lease fails to be renewed or the task is canceled (possibly as a result of the role instance shutting down), the lease is released. Neste ponto, essa ou outra instância de função pode ser eleita como líder.At this point, this or another role instance might be elected as the leader. A extração de código abaixo mostra essa parte do processo.The code extract below shows this part of the process.

  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);
        }
      }
    }
  }
  ...
}

O KeepRenewingLease é outro método auxiliar que usa o objeto BlobLeaseManager para renovar a concessão.The KeepRenewingLease method is another helper method that uses the BlobLeaseManager object to renew the lease. O método CancelAllWhenAnyCompletes cancela as tarefas especificadas como os dois primeiros parâmetros.The CancelAllWhenAnyCompletes method cancels the tasks specified as the first two parameters. O diagrama a seguir ilustra o uso da classe BlobDistributedMutex para eleger o líder e executar uma tarefa que coordena as operações.The following diagram illustrates using the BlobDistributedMutex class to elect a leader and run a task that coordinates operations.

A Figura 1 ilustra as funções da classe BlobDistributedMutex

O exemplo de código a seguir mostra como usar a classe BlobDistributedMutex em uma função de trabalho.The following code example shows how to use the BlobDistributedMutex class in a worker role. Esse código adquire uma concessão em um blob denominado MyLeaderCoordinatorTask no contêiner de concessão no armazenamento de desenvolvimento e especifica que o código definido no método MyLeaderCoordinatorTask deve ser executado se a instância de função for eleita como líder.This code acquires a lease over a blob named MyLeaderCoordinatorTask in the lease's container in development storage, and specifies that the code defined in the MyLeaderCoordinatorTask method should run if the role instance is elected the leader.

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)
{
  ...
}

Observe os pontos a seguir sobre a solução de exemplo:Note the following points about the sample solution:

  • O blob é um ponto único de falha em potencial.The blob is a potential single point of failure. Se o serviço Blob ficar indisponível ou estiver inacessível, o líder não poderá renovar a concessão e nenhuma outra instância de função poderá adquiri-la.If the blob service becomes unavailable, or is inaccessible, the leader won't be able to renew the lease and no other role instance will be able to acquire the lease. Nesse caso, nenhuma instância de função será capaz de atuar como o líder.In this case, no role instance will be able to act as the leader. No entanto, o serviço Blob é projetado para ser resiliente, por isso uma falha completa do serviço Blob é considerada extremamente improvável.However, the blob service is designed to be resilient, so complete failure of the blob service is considered to be extremely unlikely.
  • Se a tarefa que está sendo executada pelo líder parar, ele poderá continuar a renovar a concessão, impedindo que qualquer outra instância de função adquira a concessão e assuma a função de líder para coordenar tarefas.If the task being performed by the leader stalls, the leader might continue to renew the lease, preventing any other role instance from acquiring the lease and taking over the leader role in order to coordinate tasks. No mundo real, a integridade do líder deve ser verificada em intervalos frequentes.In the real world, the health of the leader should be checked at frequent intervals.
  • O processo de eleição é não determinístico.The election process is nondeterministic. Você não pode fazer suposições sobre qual instância de função obterá a concessão de blob e se tornará o líder.You can't make any assumptions about which role instance will acquire the blob lease and become the leader.
  • O blob usado como o destino da concessão de blob não deve ser usado para nenhuma outra finalidade.The blob used as the target of the blob lease shouldn't be used for any other purpose. Se uma instância de função tentar armazenar dados nesse blob, tais dados não poderão ser acessados, a menos que a instância de função seja o líder e possua a concessão de blob.If a role instance attempts to store data in this blob, this data won't be accessible unless the role instance is the leader and holds the blob lease.

As diretrizes a seguir também podem ser relevantes ao implementar esse padrão:The following guidance might also be relevant when implementing this pattern: