Padrão de Eleição de Coordenador

Coordene as ações executadas por uma coleção de instâncias de colaboração numa aplicação distribuída, ao eleger uma instância como o coordenador que assume a responsabilidade de gerir as outras. Poderá assim evitar que as instâncias entrem em conflito entre si, provoquem contenção devido aos recursos partilhados ou interfiram inadvertidamente com o trabalho que as outras instâncias estão a realizar.

Contexto e problema

Uma aplicação na cloud típica tem muitas tarefas a funcionar de forma coordenada. Estas tarefas podem ser todas instâncias a executar o mesmo código e precisam de acesso aos mesmos recursos ou podem estar a trabalhar em conjunto de forma paralela para realizar partes individuais de um cálculo complexo.

As instâncias de tarefa podem ser executadas separadamente durante a maior parte do tempo, mas também pode ser necessário coordenar as ações de cada instância para garantir que elas não entrem em conflito, causem contenção de recursos compartilhados ou interfiram acidentalmente no trabalho que outras instâncias de tarefa estão executando.

Por exemplo:

• Num sistema baseado na cloud que implementa o dimensionamento horizontal, várias instâncias da mesma tarefa podem estar em execução em simultâneo com cada uma a servir um utilizador diferente. Se estas instâncias estiverem a escrever num recurso partilhado, será necessário coordenar as ações delas para impedir que cada instância substitua as alterações realizadas pelas outras.
• Se as tarefas estiverem a executar elementos individuais de um cálculo complexo em paralelo, será necessário agregar os resultados quando estiverem concluídos.

As instâncias de tarefa são todas elementos da rede, pelo que não há um líder natural que possa agir como o coordenador ou agregador.

Solução

Eleja uma instância de tarefa única para funcionar como coordenador. Por sua vez, esta instância deve coordenar as ações das outras instâncias de tarefa subordinadas. Se todas as instâncias de tarefas estiverem a executar o mesmo código, terão todas a capacidade de agir como coordenadores. Por conseguinte, o processo eleitoral deve ser gerido com cuidado para evitar que duas ou mais instâncias assumam a posição de líder ao mesmo tempo.

O sistema tem de fornecer um mecanismo robusto para selecionar o coordenador. Este método tem de lidar com eventos como interrupções de rede ou falhas de processos. Em muitas soluções, as instâncias de tarefa subordinadas monitorizam o coordenador através de algum tipo de método de heartbeat ou por consulta. Se o coordenador designado terminar inesperadamente ou uma falha de rede a tornar indisponível para as instâncias de tarefa subordinadas, será necessário que elejam um novo coordenador.

Existem várias estratégias para eleger um coordenador num conjunto de tarefas num ambiente distribuído, incluindo:

• Selecionar a instância de tarefa com a instância ou o ID de processo com a classificação mais baixa.
• Competir para adquirir uma exclusão mútua distribuída e partilhada. A primeira instância de tarefa que adquire a exclusão mútua é o coordenador. No entanto, o sistema tem de garantir que, se o coordenador terminar ou ficar desligado do resto do sistema, a exclusão mútua é libertada para permitir que outra instância de tarefa se torne no coordenador.
• Implementar um dos algoritmos comuns de eleição de coordenador, tal como o Algoritmo Bully ou Algoritmo Ring. Estes algoritmos partem do princípio de que cada candidato na eleição tem um ID exclusivo e que consegue comunicar com os outros candidatos de forma fiável.

Problemas e considerações

Na altura de decidir como implementar este padrão, considere os seguintes pontos:

• O processo de eleição de um coordenador deve ser resiliente face a falhas transitórias e persistentes.
• Tem de ser possível detetar quando o coordenador falhou ou ficou, de alguma forma, indisponível (por exemplo, devido a uma falha de comunicações). A exigência de rapidez de deteção depende do sistema. Alguns sistemas podem conseguir funcionar sem um coordenador durante um curto período de tempo, durante o qual uma falha transitória poderá ser corrigida. Noutros casos, poderá ser necessário detetar a falha do coordenador de forma imediata e acionar uma nova eleição.
• Num sistema que implementa o dimensionamento automático horizontal, o coordenador poderá ser terminado se o sistema for reduzido e desligar alguns dos recursos informáticos.
• A utilização de uma exclusão mútua distribuída e partilhada cria relativamente ao serviço externo que fornece a exclusão mútua. O serviço constitui um ponto único de falha. Se ficar indisponível por qualquer motivo, o sistema não conseguirá eleger um coordenador.
• A utilização de um processo dedicado único como coordenador é uma abordagem simples. No entanto, se o processo falhar, poderá verificar-se um atraso significativo para ser reiniciado. A latência resultante pode afetar os tempos de resposta e o desempenho dos outros processos caso estejam a aguardar que o coordenador coordene uma operação.
• A implementação manual de um dos algoritmos de eleição fornece a maior flexibilidade para o ajuste e a otimização do código.
• Evite tornar o coordenador num estrangulamento do sistema. O objetivo 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 fazê-lo se a tarefa não for eleita como líder.

Quando utilizar este padrão

Utilize este padrão quando as tarefas numa aplicação distribuída, tal como uma solução alojado na cloud, precisam de uma coordenação cuidada e não existe nenhum coordenador natural.

Este padrão pode não ser prático se:

• Existir um coordenador natural ou um processo dedicado que sempre pode agir como o coordenador. Por exemplo, pode ser possível implementar um processo singleton que coordena as instâncias de tarefas. Se este processo falhar ou apresentar um estado de funcionamento incorreto, o sistema poderá encerrá-lo e reiniciá-lo.
• A coordenação entre as tarefas puder ser obtida com um método mais simples. Por exemplo, se várias instâncias de tarefa precisarem apenas de um acesso coordenado a um recurso partilhado, a melhor solução passará por utilizar um bloqueio otimista ou pessimista para controlar o acesso.
• Uma solução de terceiros for mais adequada. Por exemplo, o serviço do Microsoft Azure HDInsight (com base no Apache Hadoop) utiliza os serviços disponibilizados pelo Apache Zookeeper para coordenar o mapa e reduzir as tarefas que recolhem e resumem os dados.

Design da carga de trabalho

Um arquiteto deve avaliar como o padrão de Eleição de Líder pode ser usado no design de sua carga de trabalho para abordar as metas e os princípios abordados nos pilares do Azure Well-Architected Framework. Por exemplo:

Como em qualquer decisão de design, considere quaisquer compensações em relação aos objetivos dos outros pilares que possam ser introduzidos com esse padrão.

Exemplo

O exemplo de Eleição de Líder no GitHub) mostra como usar uma concessão em um blob de Armazenamento do Azure para fornecer um mecanismo para implementar um mutex compartilhado e distribuído. Este mutex pode ser usado para eleger um líder entre um grupo de instâncias de trabalhadores disponíveis. A primeira instância para adquirir o contrato de arrendamento é eleita o líder e permanece como líder até que libere o contrato ou não consiga renovar o contrato. Outras instâncias de trabalho podem continuar monitorando a concessão de blob caso o líder não esteja mais disponível.

Uma concessão de blob é um bloqueio de escrita exclusivo sobre um blob. Um blob único pode ser o objeto de apenas uma concessão em dado momento. Uma instância de trabalho pode solicitar uma concessão sobre um blob especificado e será concedida a concessão se nenhuma outra instância de trabalho tiver uma concessão sobre o mesmo blob. Caso contrário, a solicitação lançará uma exceção.

Para evitar que uma instância de líder com defeito mantenha a locação indefinidamente, especifique um tempo de vida para a locação. Quando esta expirar, a concessão ficará disponível. No entanto, enquanto uma instância detém o arrendamento, pode solicitar que o contrato seja renovado, e ser-lhe-á concedido o arrendamento por um período de tempo adicional. A instância líder pode repetir continuamente esse processo se quiser manter a locação. Para obter mais informações sobre como concessionar um blob, veja Lease Blob (REST API) (Blob de Concessão (API REST)).

A BlobDistributedMutex classe no exemplo de C# abaixo contém o RunTaskWhenMutexAcquired método que permite que uma instância de trabalho tente adquirir uma concessão sobre um blob especificado. Os detalhes do blob (o nome, o contentor e a conta de armazenamento) são transmitidos ao construtor num objeto BlobSettings, quando o objeto BlobDistributedMutex é criado (este objeto é uma estrutura simples incluída no código de exemplo). O construtor também aceita um Task que faz referência ao código que a instância de trabalho deve executar se ele adquirir com êxito a concessão sobre o blob e for eleito o líder. Tenha em atenção que o código que processa os detalhes de baixo nível da aquisição da concessão está implementado numa classe de programa auxiliar separada denominada 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 código de exemplo acima, invoca o método RunTaskWhenBlobLeaseAcquired, mostrado no exemplo de código seguinte, para adquirir realmente a concessão. O método RunTaskWhenBlobLeaseAcquired é executado de forma assíncrona. Se o contrato de arrendamento for adquirido com sucesso, a instância do trabalhador foi eleita o líder. O objetivo do delegado é executar o trabalho que coordena as outras instâncias de taskToRunWhenLeaseAcquired trabalho. Se a locação não for adquirida, outra instância de trabalhador foi eleita como líder e a instância de trabalhador atual permanece subordinada. Tenha em atenção que o método TryAcquireLeaseOrWait é um método de programa auxiliar que utiliza o objeto BlobLeaseManager para adquirir a concessão.

  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 coordenador também é executa de forma assíncrona. Durante a execução desta tarefa, o método RunTaskWhenBlobLeaseAcquired, mostrado no exemplo de código seguinte, tenta periodicamente renovar a concessão. Isso ajuda a garantir que a instância do trabalhador permaneça a líder. Na solução de exemplo, o atraso entre as solicitações de renovação é menor do que o tempo especificado para a duração da locação, a fim de evitar que outra instância de trabalhador seja eleita líder. Se a renovação falhar por qualquer motivo, a tarefa específica do líder é cancelada.

Se a concessão não for renovada ou a tarefa for cancelada (possivelmente como resultado do desligamento da instância de trabalho), a concessão será liberada. Neste ponto, esta ou outra instância do trabalhador pode ser eleita como líder. O extrato de código abaixo mostra esta parte do processo.

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

KeepRenewingLease é outro método de programa auxiliar que utiliza o objeto BlobLeaseManager para renovar a concessão. O método CancelAllWhenAnyCompletes cancela as tarefas especificadas como sendo os primeiro dois parâmetros. O diagrama seguinte ilustra a utilização da classe BlobDistributedMutex para eleger um coordenador e executar uma tarefa que coordena as operações.

O exemplo de código a seguir mostra como usar a classe dentro de BlobDistributedMutex uma instância de trabalho. Esse código adquire uma concessão sobre um blob nomeado MyLeaderCoordinatorTask no contêiner da concessão Armazenamento de Blobs do Azure e especifica que o código definido no MyLeaderCoordinatorTask método deve ser executado se a instância de trabalho for eleita como líder.

// Create a BlobSettings object with the connection string or managed identity and the name of the blob to use for the lease
BlobSettings blobSettings = new BlobSettings(storageConnStr, "leases", "MyLeaderCoordinatorTask");

// Create a new BlobDistributedMutex object with the BlobSettings object and a task to run when the lease is acquired
var distributedMutex = new BlobDistributedMutex(
    blobSettings, MyLeaderCoordinatorTask);

// Wait for completion of the DistributedMutex and the UI task before exiting
await distributedMutex.RunTaskWhenMutexAcquired(cancellationToken);

...

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

Tenha em atenção os seguintes pontos relativamente à solução de exemplo:

• O blob é um potencial ponto único de falha. Se o serviço de blob ficar indisponível ou estiver inacessível, o líder não poderá renovar a locação e nenhuma outra instância de trabalhador poderá adquirir a locação. Neste caso, nenhuma instância de trabalhador será capaz de atuar como líder. No entanto, o serviço blob foi concebido para ser resiliente, pelo que a falha total do serviço blob é considerado como algo extremamente improvável.
• Se a tarefa que está a ser executada pelo líder parar, o líder pode continuar a renovar o contrato, impedindo que qualquer outra instância de trabalhador adquira o contrato de arrendamento e assuma a posição de líder para coordenar tarefas. No mundo real, o estado de funcionamento do coordenador deve ser verificado regularmente.
• O processo de eleição não é determinístico. Você não pode fazer suposições sobre qual instância de trabalhador adquirirá o contrato de arrendamento de blob e se tornará o líder.
• O blob utilizado como destino da concessão do blob não deve ser utilizado para qualquer outra finalidade. Se uma instância de trabalho tentar armazenar dados nesse blob, esses dados não estarão acessíveis a menos que a instância de trabalho seja o líder e mantenha a concessão de blob.

Próximos passos

As seguintes orientações também podem ser relevantes ao implementar este padrão:

• Este padrão possui uma aplicação de exemplo transferível.
• Orientações de Dimensionamento Automático. É possível iniciar e parar as instâncias dos anfitriões de tarefas à medida que a carga na aplicação varia. O dimensionamento automático pode ajudar a manter o débito e o desempenho durante os períodos de pico de processamento.
• O padrão assíncrono baseado em tarefas.
• Um exemplo que ilustra o Algoritmo Bully.
• Um exemplo que ilustra o Algoritmo Ring.
• O Apache Curator é uma biblioteca de cliente do Apache ZooKeeper.
• O artigo Lease Blob (REST API) (Blob de Concessão (API REST)) no MSDN.