Elección de líder en los sistemas distribuidos

La elección de líder es simplemente la noción de darle a un elemento (un proceso, un alojamiento, un subproceso, un objeto o un humano) algunas atribuciones especiales en un sistema distribuido. Esas atribuciones podrían incluir la capacidad de asignar trabajo y de modificar datos, o incluso la responsabilidad de administrar todas las solicitudes en el sistema.

La elección de líder es una herramienta muy eficaz que mejora la eficiencia, reduce la coordinación, simplifica las arquitecturas y reduce las operaciones. Por otro parte, la elección de líder puede introducir nuevos modos de error y cuellos de botella de escalado. Además, esta herramienta puede complicar más su tarea de evaluación de la exactitud de un sistema.

Debido a estas complicaciones, consideramos cuidadosamente otras opciones antes de implementar la elección de líder. Para los flujos de trabajo y el procesamiento de datos, los servicios de flujos de trabajo, como AWS Step Functions, pueden lograr muchos de los mismos beneficios que la elección de líder y, a la vez, evitar muchos de sus riesgos. Para otros sistemas, solemos implementar API idempotentes, bloqueos optimistas y otros patrones que eliminan la necesidad de un único líder.

En este artículo, analizo algunos de los beneficios y los perjuicios de la elección de líder en general, y la manera en que Amazon aborda la elección de líder en los sistemas distribuidos, incluida la información acerca de los errores del líder.

Hay muchas formas de elegir a un líder, ya sea algoritmos como Paxos, software como Apache ZooKeeper, hardware personalizado, o concesiones. Las concesiones son el mecanismo de elección de líder más utilizado en Amazon. Son relativamente fáciles de entender e implementar, y ofrecen tolerancia a errores integrada. También funcionan con una base de datos única que almacena al líder actual. Luego, la concesión necesita que el líder se muestre activo de forma periódica para indicar que todavía es el líder. Si no se muestra activo después de un tiempo, otros candidatos a líderes pueden tratar de quedar a cargo.

Evitamos depender del tiempo en sistemas distribuidos, incluso con la gran función de sincronización de tiempo en Amazon Elastic Compute Cloud (Amazon EC2). Es difícil asegurarse de que los relojes del sistema en un clúster estén sincronizados lo suficiente como para depender de esa sincronización para ordenar o coordinar las operaciones distribuidas. En Amazon, los sistemas distribuidos solo utilizan el tiempo para el consumo humano. Las concesiones dependen del tiempo. Sin embargo, dependen solo de la duración del tiempo transcurrido localmente, en lugar del tiempo de un reloj en tiempo real que está sincronizado y que necesita de un acuerdo de varios servidores.

El código fuente del cliente de bloqueo de DynamoDB ofrece ejemplos y detalles relacionados con la elección de líder. Sin embargo, descubrimos que, a pesar de que las concesiones y los bloqueos son teóricamente sencillos, la correcta implementación puede ser sutil. Las implementaciones requieren de un conocimiento acerca de cómo un servidor mide la duración del tiempo local. Por ejemplo, si un servidor o una biblioteca que mide el tiempo pensara que el tiempo retrocede ocasionalmente, esto terminaría las suposiciones sobre la duración del tiempo que se incluyen en las concesiones. Las duraciones evitan los problemas con la sincronización global del reloj que hacen que los servidores dejen de ponerse de acuerdo sobre la hora que es, desde los segundos intercalares hasta la deriva del reloj local a lo largo del tiempo debido a la alta utilización sostenida de la CPU.

Un problema mayor para las concesiones y cualquier tipo de bloqueo distribuido es asegurarse de que el líder solo esté trabajando mientras mantiene el bloqueo. Asegurarse de que el líder mantiene el bloqueo en realidad es bastante difícil. Nos parece que es importante garantizar que un líder en una red lenta o con pérdidas no crea que mantiene bloqueos durante más tiempo de lo que realmente lo hace. De manera similar, las pausas de la recolección de basura entre la comprobación de un bloqueo y la realización de un trabajo pueden llevar a un comportamiento incorrecto. En la práctica, la protección frente a estos problemas suele ser el mayor problema.

DynamoDB y ZooKeeper ofrecen clientes de bloqueo simples que se basan en concesiones, lo que ofrece una elección de líder tolerante a errores. A menos que haya necesidades particulares, preferimos estos clientes, ya que creemos que ofrecen la forma más fácil y más comprobada para implementar la elección de líder. Los equipos de Amazon prefieren evitar la creación de una implementación de elección de líder personalizada. En cambio, nosotros apoyamos a los clientes existentes que están bien probado y fortalecidos.

La elección de líder es un patrón ampliamente implementado en Amazon. Por ejemplo:

• Casi todos los sistemas que utilizan los sistemas de administración de bases de datos relacionales (RDBMS) dependen de la elección de líder para elegir una base de datos de líder que administra todas las escrituras y, a veces, las lecturas. En estos sistemas, se puede automatizar la elección, pero es un operador humano quien suele realizarla de forma manual.
• Amazon EBS distribuye lecturas y escrituras para un volumen a través de muchos servidores de almacenamiento. Con el fin de asegurar la consistencia, utiliza la elección del líder para determinar los principales de cada área del volumen, que se encargan de ordenar las lecturas y las escrituras. Si el líder principal falla, las copias del seguidor pasan a ser el líder mediante el mismo mecanismo de elección. En Amazon EBS, la elección de líder garantiza la consistencia y, a su vez, mejora el rendimiento, ya que evita la coordinación en el plano de los datos. DynamoDB, Amazon Quantum Ledger Database (Amazon QLDB) y Amazon Kinesis (Kinesis) utilizan enfoques similares por la misma razón.
• Kinesis Client Library (KCL) utiliza concesiones para asegurarse de que cada partición de Kinesis la procese un propietario, lo que facilita el procesamiento de escalado ascendente de las transmisiones de Kinesis.

Otra cosa que hay que considerar detenidamente es qué sucede con el trabajo de un líder cuando este falla. Si un líder falla durante una tarea, ¿de qué manera completa la tarea el líder nuevo? Si un líder falla antes de lograr que su trabajo sea duradero, ¿el sistema sigue siendo correcto? Muchos tipos de sistemas tienen pasos separados para “hacer que el trabajo sea duradero” y “decir a otros que está completo”. En Amazon, nuestros sistemas siempre hacen lo primero antes que lo segundo (o toleran la pérdida de datos). De nuevo, la idempotencia es útil aquí. Le permite al nuevo líder redireccionar con confianza el trabajo que el líder saliente pudo haber completado de forma total o parcial, pero que no le informó a otros.

Para tolerar los errores, los sistemas distribuidos de Amazon no tienen un líder único. En cambio, el liderazgo es una propiedad que pasa de un servidor a otro o de un proceso a otro. En los sistemas distribuidos, no es posible asegurar que haya exactamente un líder en el sistema. Por el contrario, generalmente puede haber un líder y, durante los errores, se llega a tener dos o ninguno.

La forma en la que elegimos el comportamiento del sistema frente al error del líder depende de lo que suceda en un sistema cuando hay dos líderes. Los sistemas que realizan un trabajo idempotente a menudo pueden tolerar dos líderes con una pérdida mínima de la eficiencia. Con dos líderes, los sistemas pueden lograr una mayor disponibilidad y elegir enfoques de elección de líder más débiles.

Los sistemas que necesitan como mucho un líder son más difíciles de crear que los sistemas de varios líderes. El sistema de elección de líder siempre debe ser correcto y coherente. Además, debe garantizar que el líder saliente sea destituido antes de que se elija un líder nuevo, lo cual es más difícil de lo que parece. En los sistemas distribuidos, suele ser difícil saber si un sistema ha fallado o si simplemente continúa trabajando en alguna otra partición de red. En Amazon, nos aseguramos de que cualquier sistema elegido por un líder se encargue de este caso extremo.

En Amazon, seguimos las prácticas recomendadas para la elección de líder:

• Verificar el tiempo de concesión restante (o el estado de bloqueo en general) con frecuencia, y especialmente antes de iniciar cualquier operación que tenga efectos secundarios más allá del propio líder.
• Tener en cuenta que las redes lentas, los tiempos de espera, los reintentos y las pausas de recolección de basura pueden hacer que expire el tiempo de concesión restante antes de que el código espere que suceda.
• Evitar concesiones de latidos en un subproceso de fondo. Esto puede causar problemas de exactitud si el subproceso no puede interrumpir el código cuando expira la concesión o finaliza el latido del subproceso. Pueden ocurrir problemas de disponibilidad si el trabajo del subproceso finaliza o se detiene mientras que el latido del mismo espera a la concesión.
• Tener métricas confiables que muestren cuánto trabajo puede realizar un líder frente a la cantidad que está realizando en la actualidad. Revise esas métricas con frecuencia y asegúrese de que haya planes para el escalado antes de quedarse sin capacidad.
• Hacer que sea fácil encontrar qué alojamiento es el líder actual y qué alojamiento era el líder en determinado momento. Mantenga un registro o un seguimiento de auditoría de los cambios de liderazgo.
• Modelar y verificar formalmente la exactitud de los algoritmos distribuidos mediante herramientas como TLA+. Esto detecta errores sutiles, difíciles de observar y poco comunes que pueden aparecer cuando una aplicación asume demasiadas cosas sobre las garantías proporcionadas por el protocolo de elección de líder.

La elección de líder es una herramienta muy eficaz que se utiliza en los sistemas de Amazon para que nuestros sistemas sean tolerantes a errores y fáciles de operar. Sin embargo, cuando utilizamos la elección de líder, consideramos cuidadosamente las garantías que proporciona cada protocolo de elección de líder y, lo que es más importante, las que no proporciona.

Los sistemas de Amazon a menudo utilizan la elección de líder para garantizar que haya tolerancia a errores integrada. Cuando los sistemas utilizan la elección de líder para garantizar que al menos un servidor esté procesando una tarea, utilizan mecanismos separados para mantener la exactitud frente a varios líderes simultáneos. Por ejemplo, podrían utilizar una base de datos subyacente para asegurarse de que si dos líderes piensan que ambos tienen una concesión, no interfieran entre sí. En lugar de hacer suposiciones sobre las garantías que ofrece la implementación de una concesión, nos enfocamos en la exactitud de estos sistemas, por lo general con el modelado con técnicas como TLA+.

A pesar de sus matices, la elección de líder sigue siendo una herramienta útil en nuestro conjunto de herramientas de sistemas distribuidos en Amazon, junto con patrones como la idempotencia y el bloqueo optimista.

Para obtener más información acerca de cómo funcionan las concesiones, consulte lo siguiente:

• How to do distributed locking
• Burrows, The Chubby lock service for loosely-coupled distributed systems
• Gray and Cheriton, Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency