NGINX y el algoritmo de equilibrio de carga "El poder de dos opciones"

Los nuevos casos de uso a veces requieren nuevos algoritmos de equilibrio de carga, y en NGINX Plus R16 y NGINX Open Source 1.15.1 agregamos un nuevo método que es particularmente adecuado para balanceadores de carga distribuidos: una implementación del algoritmo de “poder de dos opciones”.

¿Por qué necesitamos un nuevo algoritmo de equilibrio de carga?

Los métodos clásicos de equilibrio de carga, como el de Mínimas Conexiones, funcionan muy bien cuando se opera un único equilibrador de carga activo que mantiene una vista completa del estado de los nodos equilibrados de carga. El enfoque del "poder de dos opciones" no es tan efectivo en un solo balanceador de carga, pero evita hábilmente el "comportamiento de manada" que puede ocurrir cuando se escala a varios balanceadores de carga independientes.

Este escenario no solo se observa cuando se escala horizontalmente en entornos de alto rendimiento; también se observa en entornos en contenedores donde varios servidores proxy equilibran la carga del tráfico hacia el mismo conjunto de instancias de servicio.

Una instancia común de este escenario ocurre cuando se utiliza NGINX Ingress Controller para Kubernetes, con una instancia de equilibrio de carga por nodo de Kubernetes.

El algoritmo se conoce en la literatura como “poder de dos opciones”, porque se describió por primera vez en la disertación de Michael Mitzenmacher de 1996, El poder de dos opciones en el equilibrio de carga aleatorio . En NGINX y NGINX Plus, se implementa como una variación del algoritmo de equilibrio de carga aleatorio, por lo que también lo llamamos aleatorio con dos opciones .

¿Cómo funciona el “poder de dos decisiones”?

Comencemos con lo que podría ser una situación familiar. Acaba de aterrizar después de un largo vuelo internacional y, junto con otros 400 viajeros, ha entrado en una concurrida sala de llegadas.

Muchos aeropuertos emplean guías en la sala de llegadas. Su trabajo es dirigir a cada viajero a una de las varias colas para cada mostrador de inmigración. Si pensamos en las guías como balanceadores de carga:

• Usted y sus compañeros de viaje son solicitudes que esperan ser procesadas lo más rápidamente posible.
• Los mostradores de inmigración son servidores (backend), cada uno de los cuales procesa una serie de solicitudes pendientes.
• Los guías maximizan la eficiencia al seleccionar el mejor servidor para cada solicitud.
• Los métodos disponibles en las guías para seleccionar el mejor servidor corresponden a algoritmos de equilibrio de carga.

Consideremos qué tan bien funcionan algunos de los posibles algoritmos en un escenario de equilibrio de carga distribuido como la sala de llegadas.

Balanceo de carga round-robin

El método round robin es un enfoque ingenuo para equilibrar la carga. En este enfoque, el guía selecciona cada cola en rotación: el primer viajero se dirige a la cola A, el siguiente a la cola B, y así sucesivamente. Una vez que un viajero es dirigido a la última cola, el proceso se repite desde la cola A. Round Robin es el algoritmo de equilibrio de carga predeterminado utilizado por NGINX:

Este enfoque funciona adecuadamente hasta que se produce un retraso en una de las colas. Quizás algún viajero haya extraviado su documentación o despierte sospechas en el oficial de inmigración:

La cola deja de moverse, pero el guía continúa asignando viajeros a esa cola. El retraso es cada vez mayor, ¡y eso no hará más felices a los impacientes viajeros!

Equilibrio de carga de conexiones mínimas

Hay un enfoque mucho mejor. El guía observa cada cola y cada vez que llega un viajero, lo envía a la cola más corta. Este método es análogo al método de equilibrio de carga de Menos Conexiones en NGINX, que asigna cada nueva solicitud al servidor con la menor cantidad de solicitudes pendientes (en cola):

El equilibrio de carga de Least Connections se ocupa de manera bastante efectiva de los viajeros que tardan distintos tiempos en procesarse. Busca equilibrar las longitudes de las colas y evitar agregar más solicitudes a una cola que se ha estancado.

Equilibrio de carga en el menor tiempo posible

Hemos visto que el tiempo de procesamiento varía según el pasajero; además, algunas colas se procesan más rápido o más lento que otras. Por ejemplo, un funcionario de inmigración puede tener problemas informáticos, lo que significa que procesa a los viajeros más lentamente; otro funcionario puede ser más estricto con los detalles e interrogar a los viajeros muy minuciosamente. Es posible que otros oficiales tengan mucha experiencia y puedan procesar a los viajeros más rápidamente.

¿Qué pasaría si cada cabina de inmigración tuviera un contador encima que indicara cuántos viajeros han sido procesados en, por ejemplo, los últimos 10 minutos? Luego, el guía puede dirigir a los viajeros a una cola en función de su longitud y de la rapidez con la que se procesa. Esa es una forma más efectiva de distribuir la carga, y es lo que hace el algoritmo de equilibrio de carga de menor tiempo en NGINX Plus:

Este algoritmo es específico de NGINX Plus porque se basa en datos adicionales recopilados con las métricas de estado extendido de NGINX Plus. Es particularmente efectivo en entornos virtuales o de nube donde la latencia de cada servidor puede variar de manera impredecible, por lo que la longitud de la cola por sí sola no es suficiente para estimar el retraso.

Todo se desmorona con múltiples guías

Hasta ahora, teníamos una guía (es decir, un balanceador de carga) con una visión completa de las colas y el tiempo de respuesta en la sala de llegadas. Ese guía intenta hacer la mejor elección para cada viajero basándose en la información que conoce.

Ahora pensemos en lo que ocurre si tenemos varios guías, cada uno de ellos dirigiendo a los viajeros de forma independiente. Los guías tienen vistas independientes de la longitud de las colas y los tiempos de espera: solo consideran a los viajeros que envían a cada cola.

Este escenario es propenso a un comportamiento indeseable, donde todos los guías notan que una cola es momentáneamente más corta y más rápida, y todos envían viajeros a esa cola. Las simulaciones muestran que este “comportamiento de manada” distribuye a los viajeros de una manera desequilibrada e injusta. De la misma manera, varios balanceadores de carga independientes pueden sobrecargar algunos servidores ascendentes, sin importar qué algoritmo de “mejor opción” utilice.

El algoritmo de equilibrio de carga «El poder de dos opciones»

La solución está en el algoritmo de equilibrio de carga “poder de dos opciones”. En lugar de tomar la mejor decisión posible usando datos incompletos, con “elección de poder de dos” se eligen dos colas al azar y se elige la mejor opción de las dos, evitando la peor opción .

Es eficiente implementar el “poder de dos opciones”. No es necesario comparar todas las colas para elegir la mejor opción cada vez; solo es necesario comparar dos. Y, aunque quizá no lo parezca, funciona mejor a gran escala que los algoritmos de mejor elección. Evita el comportamiento gregario no deseado mediante el simple enfoque de evitar la peor cola y distribuir el tráfico con un grado de aleatoriedad.

Usando el “Poder de Dos Opciones” con NGINX y NGINX Plus

En NGINX y NGINX Plus, el método de equilibrio de carga de “poder de dos opciones” se implementa como una variante del algoritmo aleatorio, por eso lo llamamos aleatorio con dos opciones.

En NGINX Open Source, Random with Two Choices elige entre dos servidores seleccionados aleatoriamente en función de cuál tiene actualmente menos conexiones activas. Este es el mismo criterio de selección que se utiliza para el algoritmo de menores conexiones. (Este también es el algoritmo predeterminado en NGINX Plus y se puede configurar explícitamente agregando el parámetro less_conn ).

servicio ascendente1 { zona servicio1 64k; servidor 192.168.1.11; servidor 192.168.1.12; servidor 192.168.1.13; dos aleatorios ; }

NGINX Plus también admite el parámetro least_time , que utiliza el mismo criterio de selección que el algoritmo Least Time. Al igual que con ese algoritmo, también puede elegir entre considerar:

• El tiempo para recibir el encabezado de respuesta ( least_time=header )
• El tiempo para recibir la respuesta completa ( less_time=last_byte ), como en el siguiente fragmento. El criterio de menor tiempo es ideal para situaciones donde la latencia de cada servidor ascendente puede variar.

servicio ascendente1 { zona servicio1 64k; servidor 192.168.1.11; servidor 192.168.1.12; servidor 192.168.1.13; dos aleatorios tiempo_menor=último_byte ; # usar encabezado o último_byte}

CONCLUSIÓN

NGINX y NGINX Plus admiten una variedad de métodos de equilibrio de carga; en este artículo, no consideramos los métodos deterministas Hash y IP Hash .

Los métodos de menor conexión (y para NGINX Plus, menor tiempo) son muy efectivos para equilibrar cargas cuando el balanceador de carga tiene una vista completa de la carga de trabajo asignada a cada nodo y su rendimiento pasado. Son menos efectivos cuando varios balanceadores de carga asignan solicitudes y cada uno tiene una visión incompleta de la carga de trabajo y el rendimiento.

“El poder de dos opciones” utiliza un algoritmo aleatorio sesgado y se ha demostrado que es eficaz para equilibrar cargas cuando cada equilibrador de carga tiene una vista incompleta o retrasada. Evita el “comportamiento de manada” que exhiben otros algoritmos que buscan tomar la mejor decisión en cada solicitud.

Considere Random with Two Choices, la implementación de NGINX del “poder de dos opciones”, para entornos de muy alto rendimiento y para escenarios de equilibrio de carga distribuido. Un buen caso de uso surge cuando se utilizan múltiples controladores de Ingress en Kubernetes.