NGINX y el algoritmo de balanceo de carga «El poder de dos opciones»

Owen GarrettDirector sénior de Gestión de Producto

Los nuevos casos de uso a veces requieren nuevos algoritmos de balanceo de carga, y en NGINX Plus R16 y NGINX Open Source 1.15.1 añadimos un nuevo método especialmente adecuado para balanceadores de carga distribuidos: una implementación del algoritmo «el poder de dos opciones».

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

Los métodos clásicos de balanceo de carga, como Menor número de conexiones, funcionan muy bien cuando se utiliza un único balanceador de carga activo que mantiene una visión completa del estado de los nodos entre los que se distribuye la carga. El enfoque del «poder de dos opciones» no es tan eficaz con un único balanceador de carga, pero evita hábilmente el «comportamiento de rebaño» que puede darse en el peor de los casos al ampliar el sistema con varios balanceadores de carga independientes.

Este escenario no solo se observa al escalar horizontalmente en entornos de alto rendimiento, sino también en entornos en contenedores, donde varios proxies distribuyen el tráfico entre el mismo conjunto de instancias de servicio.

Un caso habitual de este escenario se da cuando se utiliza NGINX Ingress Controller para Kubernetes, con una instancia de balanceo de carga por cada nodo de Kubernetes.

En la literatura, el algoritmo se conoce como «potencia de dos opciones», ya que se describió por primera vez en la tesis doctoral de Michael Mitzenmacher de 1996, «El poder de dos opciones en el balanceo de carga aleatorio». En NGINX y NGINX Plus, se implementa como una variante del algoritmo de balanceo de carga aleatorio, por lo que también lo denominamos «Aleatorio con dos opciones».

¿Cómo funciona el «poder de dos opciones»?

Empecemos con una situación que quizá te resulte familiar. Acabas de aterrizar tras un largo vuelo internacional y, junto con otros 400 viajeros, has entrado en una concurrida sala de llegadas.

Muchos aeropuertos cuentan con personal de orientación en la sala de llegadas. Su trabajo consiste en indicar a cada viajero a cuál de las distintas colas de los puestos de control de inmigración debe dirigirse. Si consideramos a este personal como balanceadores de carga:

• Usted y los demás viajeros son solicitudes, y todos esperan ser atendidos lo antes posible.
• Los mostradores de inmigración son servidores (de backend), cada uno de los cuales procesa una cola de solicitudes.
• Los guías maximizan la eficiencia seleccionando el mejor servidor para cada solicitud.
• Los métodos de los que disponen las guías para seleccionar el mejor servidor se corresponden con algoritmos de equilibrio de carga.

Veamos qué tal funcionan algunos de los posibles algoritmos en un escenario de equilibrio de carga distribuido como el de la sala de llegadas.

Balanceo de carga por turnos

Round robin es un enfoque sencillo para el balanceo de carga. En este enfoque, el guía selecciona cada cola por turnos: dirige al primer viajero a la cola A, al siguiente a la cola B, y así sucesivamente. Cuando dirige a un viajero a la última cola, el proceso vuelve a comenzar desde la cola A. Round Robin es el algoritmo de balanceo de carga predeterminado de NGINX:

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

La cola deja de avanzar, pero el guía sigue enviando viajeros a ella. La espera se hace cada vez más larga; ¡eso no va a hacer que los viajeros impacientes estén más contentos!

Balanceo de carga por menor número de conexiones

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 balanceo de carga Menos conexiones de NGINX, que asigna cada nueva solicitud al servidor con el menor número de solicitudes pendientes (en cola):

El balanceo de carga por menor número de conexiones gestiona con bastante eficacia a los viajeros que requieren distintos tiempos de procesamiento. Trata de equilibrar la longitud de las colas y evita añadir más solicitudes a una cola que se ha quedado bloqueada.

Balanceo de carga por menor tiempo

Hemos visto que el tiempo necesario para atender a cada pasajero varía; además, algunas colas avanzan más rápido o más despacio que otras. Por ejemplo, un agente de inmigración podría tener problemas informáticos que le hicieran atender a los viajeros más lentamente, mientras que otro podría ser muy meticuloso y someterlos a un interrogatorio exhaustivo. Otros agentes podrían tener mucha experiencia y ser capaces de atender a los viajeros con mayor rapidez.

¿Y si cada puesto de inmigración tuviera encima un contador que indicara cuántos viajeros han sido atendidos, por ejemplo, en los últimos 10 minutos? De este modo, el encargado podría dirigir a los viajeros a una cola en función de su longitud y de la rapidez con la que avanza. Es una forma más eficaz de distribuir la carga, y eso es precisamente lo que hace el algoritmo de balanceo de carga Menor tiempo de NGINX Plus:

Este algoritmo es específico de NGINX Plus porque se basa en datos adicionales recopilados mediante las métricas de Estado ampliado de NGINX Plus. Resulta especialmente eficaz en entornos virtuales o en la nube, donde la latencia de cada servidor puede variar de forma impredecible, por lo que la longitud de la cola por sí sola no basta para estimar el retraso.

Todo se viene abajo con varias guías

Hasta ahora, hemos contado con un único guía (es decir, un balanceador de carga) que tiene una visión completa de las colas y del tiempo de respuesta en la sala de llegadas. Este guía intenta tomar la mejor decisión para cada viajero basándose en la información de la que dispone.

Ahora veamos qué ocurre si tenemos varios guías, cada uno de los cuales dirige a los viajeros de forma independiente. Los guías tienen su propia visión de la longitud de las colas y de los tiempos de espera: solo tienen en cuenta a los viajeros que envían a cada cola.

Este escenario tiende a provocar un comportamiento no deseado: todos los guías observan que una cola es momentáneamente más corta y rápida, y envían a los viajeros a ella. Las simulaciones muestran que este «comportamiento gregario» distribuye a los viajeros de forma desequilibrada e injusta. Del mismo modo, varios balanceadores de carga independientes pueden sobrecargar algunos servidores de origen, independientemente del algoritmo de «mejor opción» que se utilice.

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

La solución reside en el algoritmo de equilibrio de carga conocido como «el poder de dos opciones». En lugar de intentar tomar la mejor decisión posible basándose en datos incompletos, con «el poder de dos opciones» se eligen dos colas al azar y se escoge la mejor de las dos, evitando la peor opción.

El «poder de dos opciones» es fácil de implementar. No es necesario comparar todas las colas para elegir siempre la mejor opción, sino que basta con comparar dos. Y, aunque pueda parecer contradictorio, funciona mejor a gran escala que los algoritmos que eligen la mejor opción. Evita el indeseado comportamiento de rebaño mediante un enfoque sencillo: descartar la peor cola y distribuir el tráfico con cierto grado de aleatoriedad.

Uso del «poder de dos opciones» con NGINX y NGINX Plus

En NGINX y NGINX Plus, el método de balanceo de carga «potencia de dos opciones» se implementa como una variante del algoritmo Random, por lo que lo denominamos Random with Two Choices.

En NGINX Open Source, el algoritmo Aleatorio con dos opciones elige entre dos servidores seleccionados al azar en función de cuál tenga menos conexiones activas en ese momento. Este es el mismo criterio de selección que utiliza el algoritmo de Menos conexiones. (Este también es el algoritmo predeterminado en NGINX Plus y se puede configurar explícitamente añadiendo el parámetro least_conn).

upstream service1 {    zone service1 64k;
    server 192.168.1.11;
    server 192.168.1.12;
    server 192.168.1.13;
    random two; 
}

NGINX Plus también admite el parámetro least_time, que utiliza el mismo criterio de selección que el algoritmo de menor tiempo. Al igual que con dicho algoritmo, también puede elegir entre tener en cuenta:

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

upstream service1 {    zone service1 64k;
    server 192.168.1.11;
    server 192.168.1.12;
    server 192.168.1.13;
    random two least_time=last_byte; # use header or last_byte
}

Conclusión

NGINX y NGINX Plus admit diversos métodos de balanceo de carga; en este artículo, no hemos abordado los métodos deterministas Hash e IP Hash.

Los métodos Menos conexiones (y, en el caso de NGINX Plus, Menor tiempo) son muy eficaces para equilibrar las cargas cuando el balanceador de carga dispone de una visión completa de la carga de trabajo asignada a cada nodo y de su rendimiento anterior. Son menos eficaces cuando varios balanceadores de carga asignan solicitudes y cada uno dispone de una visión incompleta de la carga de trabajo y del rendimiento.

«El poder de dos opciones» utiliza un algoritmo aleatorio sesgado y ha demostrado ser eficaz para equilibrar las cargas cuando cada balanceador de carga tiene una visión incompleta o desactualizada. Evita el «comportamiento de rebaño» que presentan otros algoritmos que intentan tomar la mejor decisión para cada solicitud.

Considere Random with Two Choices, la implementación de NGINX de «power of two choices», para entornos de muy alto rendimiento y escenarios de balanceo de carga distribuido. Un buen caso de uso se da cuando se utilizan varios controladores de Ingress en Kubernetes.

Sobre el autor

Owen GarrettDirector sénior de Gestión de Producto

Más artículos de Owen Garrett