Patrón Leader ElectionLeader Election pattern

Coordina las acciones realizadas por una colección de instancias de colaboración de una aplicación distribuida mediante la elección de una instancia como líder que asume la responsabilidad de administrar las otras.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. Esto puede ayudar a garantizar que las instancias no entren en conflicto, provoquen la contención de recursos compartidos o interfieran por accidente con el trabajo que realizan otras instancias.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 y problemaContext and problem

Una aplicación en la nube típica tiene muchas tareas que actúan de manera coordinada.A typical cloud application has many tasks acting in a coordinated manner. Estas instancias podrían ser todas instancias que ejecutan el mismo código y que requieren acceso a los mismos recursos, o podría estar funcionando juntas en paralelo para realizar las partes individuales de un cálculo complejo.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.

Las instancias de tarea podrían ejecutarse por separado la mayor parte del tiempo, pero también podría ser necesario coordinar las acciones de cada una para garantizar que no entren en conflicto, provoquen la contención de recursos compartidos o interfieran por accidente con el trabajo que realizan otras instancias de tarea.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 ejemplo:For example:

  • En un sistema basado en la nube que implementa escalado horizontal, varias instancias de la misma tarea podrían estar ejecutándose al mismo tiempo y cada instancia atender a un usuario 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. Si estas instancias escriben en un recurso compartido, es necesario coordinar sus acciones para evitar que cada instancia sobrescriba los cambios realizados por las demás.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.
  • Si las tareas ejecutan elementos individuales de un cálculo complejo en paralelo, los resultados deben agregarse cuando dichos cálculos finalicen.If the tasks are performing individual elements of a complex calculation in parallel, the results need to be aggregated when they all complete.

Las instancia de tarea son todas del mismo nivel, por lo que no hay un líder natural que actúe como coordinador o agregador.The task instances are all peers, so there isn't a natural leader that can act as the coordinator or aggregator.

SoluciónSolution

Se debe elegir una única instancia de tarea para que actúe como líder, y esta instancia debe coordinar las acciones de las demás instancias de tarea subordinadas.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. Si todas las instancias de tarea ejecutan el mismo código, cada una de ellas tiene la capacidad para actuar como líder.If all of the task instances are running the same code, they are each capable of acting as the leader. Por lo tanto, el proceso de elección debe administrarse con cuidado para evitar que dos o más instancias asuman el rol de líder al mismo tiempo.Therefore, the election process must be managed carefully to prevent two or more instances taking over the leader role at the same time.

El sistema debe proporcionar un mecanismo eficaz para seleccionar el líder.The system must provide a robust mechanism for selecting the leader. Este método tiene que hacer frente a eventos, como interrupciones de red o errores de proceso.This method has to cope with events such as network outages or process failures. En muchas de las soluciones, las instancias de tarea subordinadas supervisan el líder a través de algún tipo de método de latido o mediante sondeo.In many solutions, the subordinate task instances monitor the leader through some type of heartbeat method, or by polling. Si el líder designado termina de forma inesperada, o un error de red hace que el líder no esté disponible para las instancias de tarea subordinadas, será necesario elegir un nuevo 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.

Existen varias estrategias para elegir un líder entre un conjunto de tareas en un entorno distribuido, como son:There are several strategies for electing a leader among a set of tasks in a distributed environment, including:

  • Seleccionar la instancia de tarea con el identificador de proceso o de instancia peor clasificados.Selecting the task instance with the lowest-ranked instance or process ID.
  • Competir para adquirir una exclusión mutua compartida y distribuida.Racing to acquire a shared, distributed mutex. La primera instancia de tarea que adquiere la exclusión mutua es el líder.The first task instance that acquires the mutex is the leader. Sin embargo, el sistema debe asegurarse de que, si el líder finaliza o se desconecta del resto del sistema, se libere la exclusión mutua para permitir que otra instancia de tarea se convierta en el 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.
  • Implementar uno de los algoritmos de Leader Electrion comunes como el algoritmo Bully o el algoritmo Ring.Implementing one of the common leader election algorithms such as the Bully Algorithm or the Ring Algorithm. Estos algoritmos dan por supuesto que cada candidato de la elección tiene un identificador único y que puede comunicarse con los otros candidatos de manera confiable.These algorithms assume that each candidate in the election has a unique ID, and that it can communicate with the other candidates reliably.

Problemas y consideracionesIssues and considerations

Tenga en cuenta los puntos siguientes al decidir cómo implementar este patrón:Consider the following points when deciding how to implement this pattern:

  • El proceso de elegir un líder debería ser resistente a errores transitorios y persistentes.The process of electing a leader should be resilient to transient and persistent failures.
  • Tiene que ser posible detectar cuándo el líder ha generado un error o ha dejado de estar disponible (por ejemplo, debido a un error de comunicación).It must be possible to detect when the leader has failed or has become otherwise unavailable (such as due to a communications failure). La rapidez con que se necesite la detección depende del sistema.How quickly detection is needed is system dependent. Algunos sistemas podrían funcionar durante un corto espacio de tiempo sin un líder, en cuyo transcurso un error transitorio podría corregirse.Some systems might be able to function for a short time without a leader, during which a transient fault might be fixed. En otros casos, podría ser necesario detectar el error del líder inmediatamente y desencadenar una nueva elección.In other cases, it might be necessary to detect leader failure immediately and trigger a new election.
  • En un sistema que implementa el escalado automático horizontal, el líder podría finalizarse si el sistema se reduce y cierra algunos de los recursos de computación.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.
  • El uso de una exclusión mutua compartida distribuida introduce una dependencia en el servicio externo que proporciona la exclusión mutua.Using a shared, distributed mutex introduces a dependency on the external service that provides the mutex. El servicio constituye un punto único de error.The service constitutes a single point of failure. Si por algún motivo deja de estar disponible, el sistema no podrá elegir un líder.If it becomes unavailable for any reason, the system won't be able to elect a leader.
  • El uso de un único proceso dedicado como líder es un enfoque sencillo.Using a single dedicated process as the leader is a straightforward approach. Sin embargo, si el proceso produce un error, podría haber un considerable retraso mientras se reinicia.However, if the process fails there could be a significant delay while it's restarted. La latencia resultante puede afectar al rendimiento y a los tiempos de respuesta de otros procesos si están a la espera de que el líder coordine una operación.The resulting latency can affect the performance and response times of other processes if they're waiting for the leader to coordinate an operation.
  • La implementación de uno de los algoritmos de Leader Election proporciona manualmente la máxima flexibilidad para optimizar y ajustar el código.Implementing one of the leader election algorithms manually provides the greatest flexibility for tuning and optimizing the code.

Cuándo usar este patrónWhen to use this pattern

Use este patrón cuando las tareas de una aplicación distribuida, como una solución hospedada en las nube, necesiten una cuidadosa coordinación y no haya un 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 convertir el líder en un cuello de botella en el sistema.Avoid making the leader a bottleneck in the system. La finalidad del líder es coordinar el trabajo de las tareas subordinadas, y no tiene que participar necesariamente en este trabajo—aunque debería poder hacerlo si la tarea no se elige como 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.

Este patrón puede ser útil en los siguientes casos:This pattern might not be useful if:

  • Hay un líder natural o un proceso dedicado que puede actuar siempre como líder.There's a natural leader or dedicated process that can always act as the leader. Por ejemplo, podría implementarse un proceso de singleton que coordine las instancias de tarea.For example, it might be possible to implement a singleton process that coordinates the task instances. Si se produce un error en este proceso o su estado no es correcto, el sistema puede cerrarlo y reiniciarlo.If this process fails or becomes unhealthy, the system can shut it down and restart it.
  • La coordinación entre las tareas se puede lograr con un método más ligero.The coordination between tasks can be achieved using a more lightweight method. Por ejemplo, si varias instancias de tarea solo necesitan acceso coordinado a un recurso compartido, una solución mejor es usar bloqueo optimista o pesimista para controlar el acceso.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.
  • Una solución de terceros es más adecuada.A third-party solution is more appropriate. Por ejemplo, el servicio Microsoft Azure HDInsight (basado en Apache Hadoop) usa los servicios que proporciona Apache Zookeeper para coordinar las tareas de asignación y reducción que recopilan y resumen los datos.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.

EjemploExample

El proyecto DistributedMutex de la solución LeaderElection (se puede encontrar un ejemplo que demuestra este patrón en GitHub) muestra cómo usar una concesión en un blob de Azure Storage para proporcionar un mecanismo a fin de implementar una exclusión mutua distribuida compartida.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. Esta exclusión mutua puede usarse para elegir un líder entre un grupo de instancias de rol de un servicio en la nube de Azure.This mutex can be used to elect a leader among a group of role instances in an Azure cloud service. La primera instancia de rol en adquirir la concesión se elige como líder y lo sigue siendo hasta que libera la concesión o es incapaz de renovarla.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. Otras instancias de rol pueden continuar con la supervisión de la concesión del blob en caso de que el líder ya no esté disponible.Other role instances can continue to monitor the blob lease in case the leader is no longer available.

Una concesión de blob es un bloqueo exclusivo de escritura sobre un blob.A blob lease is an exclusive write lock over a blob. Un único blob solo puede ser el sujeto de una concesión en cualquier momento en el tiempo.A single blob can be the subject of only one lease at any point in time. Una instancia de rol puede solicitar una concesión sobre un blob especificado y se le concederá la concesión si ninguna otra instancia de rol mantiene una concesión sobre el mismo 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. En caso contrario, la solicitud inicia una excepción.Otherwise the request will throw an exception.

Para evitar que una instancia de rol con errores conserve la concesión de forma indefinida, especifique una duración para la concesión.To avoid a faulted role instance retaining the lease indefinitely, specify a lifetime for the lease. Cuando expire, la concesión estará disponible.When this expires, the lease becomes available. Sin embargo, mientras una instancia de rol mantenga la concesión puede solicitar que ésta se renueve, así que se le otorgará durante un periodo de tiempo 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. La instancia de rol puede repetir continuamente este proceso si desea conservar la concesión.The role instance can continually repeat this process if it wants to retain the lease. Para más información sobre cómo conceder un blob, consulte Lease Blob (API de REST).For more information on how to lease a blob, see Lease Blob (REST API).

La clase BlobDistributedMutex del ejemplo de C# contiene el método RunTaskWhenMutexAcquired que permite que una instancia de rol intente adquirir una concesión sobre un 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. Los detalles del blog (el nombre, el contenedor y la cuenta de almacenamiento) se pasan al constructor en un objeto BlobSettings cuando se crea el objeto BlobDistributedMutex (este objeto es una estructura sencilla que se incluye el código de ejemplo).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). El constructor también acepta un elemento Task que hace referencia al código que debe ejecutar la instancia de rol si adquiere correctamente la concesión sobre el blob y se elige 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. Tenga en cuenta que el código que administra los detalles de bajo nivel de adquisición de la concesión se implementa en una clase auxiliar independiente llamada 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);
  }
  ...

El método RunTaskWhenMutexAcquired del código de ejemplo anterior invoca el método RunTaskWhenBlobLeaseAcquired mostrado en el código de ejemplo siguiente para adquirir realmente la concesión.The RunTaskWhenMutexAcquired method in the code sample above invokes the RunTaskWhenBlobLeaseAcquired method shown in the following code sample to actually acquire the lease. El método RunTaskWhenBlobLeaseAcquired se ejecuta de forma asincrónica.The RunTaskWhenBlobLeaseAcquired method runs asynchronously. Si la concesión se adquirió correctamente, la instancia de rol se elige como líder.If the lease is successfully acquired, the role instance has been elected the leader. El propósito del delegado taskToRunWhenLeaseAcquired es realizar el trabajo que coordina las otras instancias de rol.The purpose of the taskToRunWhenLeaseAcquired delegate is to perform the work that coordinates the other role instances. Si la concesión no se adquiere, otra instancia de rol se elije como líder y la instancia de rol actual queda como la subordinada.If the lease isn't acquired, another role instance has been elected as the leader and the current role instance remains a subordinate. Tenga en cuenta que el método TryAcquireLeaseOrWait es un método auxiliar que utiliza el objeto BlobLeaseManager para adquirir la concesión.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);
          ...
        }
      }
    }
    ...
  }

La tarea iniciada por el líder también se ejecuta de manera asincrónica.The task started by the leader also runs asynchronously. Mientras se ejecuta esta tarea, el método RunTaskWhenBlobLeaseAcquired mostrado en el siguiente código de ejemplo intenta periódicamente renovar la concesión.While this task is running, the RunTaskWhenBlobLeaseAcquired method shown in the following code sample periodically attempts to renew the lease. Esto ayuda a garantizar que la instancia de rol sigue siendo el líder.This helps to ensure that the role instance remains the leader. En la solución de ejemplo, el retraso entre solicitudes de renovación es menor que el tiempo especificado para la duración de la concesión a fin de evitar que otra instancia de rol se elija como 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. Si se produce un error en la renovación por cualquier motivo, se cancela la tarea.If the renewal fails for any reason, the task is canceled.

Si no se renueva la concesión o se cancela la tarea (probablemente debido al cierre de la instancia de rol), se libera la concesión.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. En este momento, esta u otra instancia de rol podrían elegirse como líder.At this point, this or another role instance might be elected as the leader. El extracto de código siguiente muestra esta parte del proceso.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);
        }
      }
    }
  }
  ...
}

El método KeepRenewingLease es otro método auxiliar que usa el objeto BlobLeaseManager para renovar la concesión.The KeepRenewingLease method is another helper method that uses the BlobLeaseManager object to renew the lease. El método CancelAllWhenAnyCompletes cancela las tareas especificadas como los dos primeros parámetros.The CancelAllWhenAnyCompletes method cancels the tasks specified as the first two parameters. En el diagrama siguiente se ilustra el uso de la clase BlobDistributedMutex para elegir un líder y ejecutar una tarea que coordina las operaciones.The following diagram illustrates using the BlobDistributedMutex class to elect a leader and run a task that coordinates operations.

La figura 1 muestra las funciones de la clase BlobDistributedMutex.

En el código de ejemplo siguiente se muestra cómo usar la clase BlobDistributedMutex en un rol de trabajo.The following code example shows how to use the BlobDistributedMutex class in a worker role. Este código adquiere una concesión sobre un blob denominado MyLeaderCoordinatorTask en el contenedor de la concesión en el almacenamiento de desarrollo y especifica que el código definido en el método MyLeaderCoordinatorTask debe ejecutarse si la instancia de rol se elige 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)
{
  ...
}

Tenga en cuenta los siguientes puntos acerca de la solución de ejemplo:Note the following points about the sample solution:

  • El blob es un posible único punto de error.The blob is a potential single point of failure. Si el servicio de blob deja de estar disponible, o no es accesible, el líder no podrá renovar la concesión y ninguna otra instancia de rol podrá adquirirla.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. En este caso, ninguna instancia de rol podrá funcionar como líder.In this case, no role instance will be able to act as the leader. Sin embargo, el servicio de blob está diseñado para ser resistente, por lo que se considera improbable el error completo de dicho servicio.However, the blob service is designed to be resilient, so complete failure of the blob service is considered to be extremely unlikely.
  • Si la tarea que realiza el líder se detiene, el líder puede continuar y renovar la concesión, lo que impide que cualquier otra instancia de rol pueda adquirirla y asuma el rol de líder para coordinar las tareas.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. En el mundo real, se debe comprobar el mantenimiento del líder a intervalos frecuentes.In the real world, the health of the leader should be checked at frequent intervals.
  • El proceso de elección es no determinista.The election process is nondeterministic. No se puede realizar ninguna suposición acerca de qué instancia de rol adquirirá la concesión del blob y se convertirá en líder.You can't make any assumptions about which role instance will acquire the blob lease and become the leader.
  • El blob que se usa como el destino de la concesión no debe usarse para otros fines.The blob used as the target of the blob lease shouldn't be used for any other purpose. Si una instancia de rol intenta almacenar datos en este blob, estos datos no podrán estar accesibles a menos que la instancia de rol sea el líder y mantenga la concesión del 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.

Las directrices siguientes también pueden ser importantes a la hora de implementar este patrón:The following guidance might also be relevant when implementing this pattern: