Balanceo de carga (informática)

El conocimiento preciso del tiempo de ejecución de cada tarea permite alcanzar una distribución de carga óptima (véase el algoritmo de suma de prefijos ). ^{[ 1 ]} Desafortunadamente, este es un caso idealizado. Conocer el tiempo de ejecución exacto de cada tarea es una situación extremadamente rara.

Por este motivo, existen diversas técnicas para estimar los diferentes tiempos de ejecución. En primer lugar, cuando las tareas tienen un tamaño relativamente homogéneo, se puede considerar que cada una requerirá aproximadamente el tiempo de ejecución promedio. Si, por el contrario, el tiempo de ejecución es considerablemente irregular, se pueden utilizar otras técnicas. Una de ellas consiste en añadir metadatos a cada tarea. Basándose en el tiempo de ejecución previo para metadatos similares, es posible realizar inferencias para una tarea futura a partir de estadísticas. ^{[ 2 ]}

En algunos casos, las tareas dependen unas de otras. Estas interdependencias pueden ilustrarse mediante un grafo dirigido acíclico . Intuitivamente, algunas tareas no pueden comenzar hasta que otras hayan finalizado.

Suponiendo que se conoce de antemano el tiempo requerido para cada tarea, un orden de ejecución óptimo debe minimizar el tiempo total de ejecución. Sin embargo, este es un problema NP-difícil y, por lo tanto, puede ser difícil de resolver con exactitud. Existen algoritmos, como el planificador de tareas , que calculan distribuciones óptimas de tareas mediante métodos metaheurísticos .

Otra característica fundamental de las tareas para el diseño de un algoritmo de balanceo de carga es su capacidad para dividirse en subtareas durante la ejecución. El algoritmo de cálculo en forma de árbol que se presenta más adelante aprovecha al máximo esta particularidad.

Un algoritmo de balanceo de carga es "estático" cuando no considera el estado del sistema para la distribución de tareas. El estado del sistema incluye parámetros como el nivel de carga (e incluso la sobrecarga) de ciertos procesadores. En cambio, se hacen suposiciones previas sobre el sistema en general, como los tiempos de llegada y los requisitos de recursos de las tareas entrantes. Además, se conoce el número de procesadores, su potencia y sus velocidades de comunicación. Por lo tanto, el balanceo de carga estático busca asociar un conjunto conocido de tareas con los procesadores disponibles para minimizar una función de rendimiento determinada. La función de rendimiento es la clave del diseño.

Las técnicas de balanceo de carga estático suelen estar centralizadas en torno a un enrutador , o maestro , que distribuye las cargas y optimiza la función de rendimiento. Esta minimización puede tener en cuenta información relacionada con las tareas que se van a distribuir y calcular un tiempo de ejecución previsto.

La ventaja de los algoritmos estáticos radica en su facilidad de configuración y su eficiencia en tareas relativamente regulares (como el procesamiento de solicitudes HTTP de un sitio web). Sin embargo, aún existe cierta variabilidad estadística en la asignación de tareas, lo que puede provocar la sobrecarga de algunas unidades de procesamiento.

A diferencia de los algoritmos de distribución de carga estática, los algoritmos dinámicos tienen en cuenta la carga actual de cada una de las unidades de computación (también llamadas nodos) del sistema. Con este enfoque, las tareas se pueden mover dinámicamente de un nodo sobrecargado a uno con menor carga para que se procesen más rápidamente. Si bien el diseño de estos algoritmos es mucho más complejo, pueden mejorar el rendimiento, en particular cuando el tiempo de ejecución varía considerablemente entre las distintas tareas.

La arquitectura de balanceo de carga dinámico puede ser más modular, ya que no es obligatorio tener un nodo específico dedicado a la distribución del trabajo. Cuando las tareas se asignan de forma única a un procesador según su estado en un momento dado, se trata de una asignación única. Si, por otro lado, las tareas pueden redistribuirse permanentemente según el estado del sistema y su evolución, se habla de asignación dinámica. ^{[ 3 ]} Un algoritmo de balanceo de carga que requiere demasiada comunicación para tomar decisiones corre el riesgo de ralentizar la resolución del problema general.

Las infraestructuras de computación paralela suelen estar compuestas por unidades con diferente capacidad de procesamiento , lo que debe tenerse en cuenta para la distribución de la carga.

Por ejemplo, las unidades de menor potencia pueden recibir solicitudes que requieren una menor cantidad de cálculo o, en el caso de solicitudes de tamaño homogéneo o desconocido, recibir menos solicitudes que las unidades más grandes.

Los ordenadores paralelos suelen dividirse en dos grandes categorías: aquellos en los que todos los procesadores comparten una única memoria común en la que leen y escriben en paralelo ( modelo PRAM ), y aquellos en los que cada unidad de cálculo tiene su propia memoria ( modelo de memoria distribuida ), y en los que la información se intercambia mediante mensajes.

En los ordenadores con memoria compartida , la gestión de conflictos de escritura ralentiza considerablemente la ejecución individual de cada unidad de procesamiento. Sin embargo, pueden funcionar perfectamente en paralelo. Por el contrario, en el caso del intercambio de mensajes, cada procesador puede trabajar a máxima velocidad. En cambio, en el intercambio colectivo de mensajes, todos los procesadores se ven obligados a esperar a que los más lentos inicien la comunicación.

En realidad, pocos sistemas se ajustan exactamente a una de las categorías. Por lo general, cada procesador dispone de una memoria interna para almacenar los datos necesarios para los cálculos posteriores y se organiza en clústeres sucesivos . A menudo, estos elementos de procesamiento se coordinan mediante memoria distribuida y paso de mensajes . Por lo tanto, el algoritmo de balanceo de carga debe estar específicamente adaptado a una arquitectura paralela. De lo contrario, existe el riesgo de que la eficiencia de la resolución de problemas en paralelo se vea considerablemente reducida.

Adaptados a las estructuras de hardware descritas anteriormente, existen dos categorías principales de algoritmos de balanceo de carga. Por un lado, está aquel en el que las tareas son asignadas por el "maestro" y ejecutadas por los "trabajadores", quienes mantienen al maestro informado del progreso de su trabajo. En el caso del algoritmo dinámico, el maestro puede entonces encargarse de asignar o reasignar la carga de trabajo. La literatura se refiere a esto como arquitectura maestro-trabajador . Por otro lado, el control puede distribuirse entre los diferentes nodos. El algoritmo de balanceo de carga se ejecuta en cada uno de ellos y la responsabilidad de asignar tareas (así como reasignarlas y dividirlas según corresponda) se comparte. La última categoría asume un algoritmo de balanceo de carga dinámico.

Dado que el diseño de cada algoritmo de balanceo de carga es único, es necesario matizar la distinción anterior. Así, también es posible adoptar una estrategia intermedia, con, por ejemplo, nodos "maestros" para cada subgrupo, los cuales, a su vez, están sujetos a un "maestro" global. Asimismo, existen organizaciones multinivel, con una alternancia entre estrategias maestro-esclavo y de control distribuido. Estas últimas estrategias se vuelven rápidamente complejas y rara vez se utilizan. Los diseñadores prefieren algoritmos más fáciles de controlar.

En el contexto de algoritmos que se ejecutan a muy largo plazo (servidores, nube, etc.), la arquitectura informática evoluciona con el tiempo. Sin embargo, es preferible no tener que diseñar un nuevo algoritmo cada vez.

Por lo tanto, un parámetro de un algoritmo de balanceo de carga es su capacidad de adaptación a una arquitectura de hardware escalable. Esto se conoce como la escalabilidad del algoritmo. Un algoritmo se considera escalable para un parámetro de entrada cuando su rendimiento permanece relativamente independiente del tamaño de dicho parámetro.

Cuando un algoritmo es capaz de adaptarse a un número variable de unidades de cómputo, pero dicho número debe fijarse antes de su ejecución, se denomina moldeable. Si, por el contrario, el algoritmo es capaz de gestionar una cantidad fluctuante de procesadores durante su ejecución, se dice que es maleable. La mayoría de los algoritmos de balanceo de carga son, como mínimo, moldeables. ^{[ 4 ]}

En un algoritmo round-robin, la primera solicitud se envía al primer servidor, la siguiente al segundo, y así sucesivamente hasta el último. Luego, el ciclo se reinicia, asignando la siguiente solicitud al primer servidor, y así sucesivamente.

Este algoritmo puede ponderarse de tal manera que las unidades más potentes reciban el mayor número de solicitudes y las reciban primero.

El balanceo de carga estático aleatorio consiste simplemente en asignar tareas al azar a los distintos servidores. Este método funciona bastante bien. Si, por otro lado, se conoce de antemano el número de tareas, resulta aún más eficiente calcular una permutación aleatoria con antelación. Esto evita los costes de comunicación para cada asignación. Ya no es necesario un maestro de distribución, puesto que cada procesador sabe qué tarea se le ha asignado. Incluso si se desconoce el número de tareas, aún es posible evitar la comunicación mediante una generación de asignación pseudoaleatoria conocida por todos los procesadores.

El rendimiento de esta estrategia (medido en tiempo total de ejecución para un conjunto fijo de tareas) disminuye con el tamaño máximo de las tareas.

También existen otros métodos de asignación:

• Menos conexiones: asigna las nuevas solicitudes al servidor con el menor número de conexiones activas; el método también puede ponderarse. ^{[ 6 ]}
• Hash: asigna las consultas según una tabla hash .
• Poder de dos opciones: elige dos servidores al azar y elige la mejor de las dos opciones. ^{[ 7 ] [ 8 ]}

Inicialmente, muchos procesadores tienen una tarea vacía, excepto uno que trabaja secuencialmente en ella. Los procesadores inactivos emiten solicitudes aleatoriamente a otros procesadores (no necesariamente activos). Si este último puede subdividir la tarea en la que está trabajando, lo hace enviando parte de su trabajo al nodo que realiza la solicitud. De lo contrario, devuelve una tarea vacía. Esto induce una estructura de árbol . Entonces es necesario enviar una señal de terminación al procesador padre cuando la subtarea se completa para que, a su vez, envíe el mensaje a su padre hasta llegar a la raíz del árbol. Cuando el primer procesador, es decir, la raíz, ha terminado, se puede difundir un mensaje de terminación global. Finalmente, es necesario ensamblar los resultados recorriendo el árbol de vuelta hacia arriba.

La eficiencia de dicho algoritmo se aproxima a la suma de prefijos cuando el tiempo de procesamiento y comunicación no es demasiado elevado en comparación con la carga de trabajo. Para evitar costes de comunicación excesivos, se puede imaginar una lista de tareas en memoria compartida . Por lo tanto, una solicitud consiste simplemente en leer desde una posición específica de esta memoria compartida a petición del procesador principal.

El DNS round-robin es un método alternativo de balanceo de carga que no requiere un nodo de software o hardware dedicado. En esta técnica, se asocian varias direcciones IP a un único nombre de dominio ; a los clientes se les asigna una IP de forma rotativa. La IP se asigna a los clientes con una caducidad corta, de modo que es más probable que utilicen una IP diferente la próxima vez que accedan al servicio de Internet solicitado.

Otra técnica más eficaz para el balanceo de carga mediante DNS consiste en delegar www.example.org como un subdominio cuya zona sea gestionada por cada uno de los mismos servidores que alojan el sitio web. Esta técnica funciona especialmente bien cuando los servidores individuales están distribuidos geográficamente en Internet. Por ejemplo:

one.example.org A 192.0.2.1

two.example.org A 203.0.113.2

www.example.org NS one.example.org

www.example.org NS two.example.org

Sin embargo, el archivo de zona para www.example.org en cada servidor es diferente, de modo que cada servidor resuelve su propia dirección IP como el registro A. ^{[ 11 ]} En el servidor uno, el archivo de zona para www.example.org informa:

@ en 192.0.2.1

En el servidor dos, el mismo archivo de zona contiene:

@ en un 203.0.113.2

De esta forma, cuando un servidor falla, su DNS no responde y el servicio web no recibe tráfico. Si la conexión a un servidor está congestionada, la inestabilidad del DNS garantiza que llegue menos tráfico HTTP a ese servidor. Además, la respuesta DNS más rápida al resolvedor casi siempre proviene del servidor más cercano a la red, lo que asegura un equilibrio de carga georreferenciado . Un TTL corto en el registro A ayuda a redirigir rápidamente el tráfico cuando un servidor falla. Es importante considerar la posibilidad de que esta técnica provoque que los clientes cambien de servidor durante la sesión.

Otro enfoque para el balanceo de carga consiste en entregar una lista de direcciones IP de servidores al cliente y, posteriormente, permitir que este seleccione aleatoriamente la IP de la lista en cada conexión. ^{[ 12 ] [ 13 ]} Esto se basa esencialmente en que todos los clientes generen cargas similares y en la ley de los grandes números ^{[ 13 ]} para lograr una distribución de carga razonablemente uniforme entre los servidores. Se ha afirmado que el balanceo de carga aleatorio del lado del cliente tiende a proporcionar una mejor distribución de carga que el DNS round-robin; esto se ha atribuido a problemas de almacenamiento en caché con el DNS round-robin, que, en el caso de grandes servidores de caché DNS, tienden a distorsionar la distribución para el DNS round-robin, mientras que la selección aleatoria del lado del cliente permanece inalterada independientemente del almacenamiento en caché DNS. ^{[ 13 ]}

Con este enfoque, el método de entrega de una lista de direcciones IP al cliente puede variar y puede implementarse como una lista DNS (entregada a todos los clientes sin ningún tipo de distribución equitativa) o mediante su codificación directa en la lista. Si se utiliza un "cliente inteligente" que detecta que un servidor seleccionado aleatoriamente está caído y se conecta de nuevo aleatoriamente, también proporciona tolerancia a fallos .

En los servicios de Internet, un balanceador de carga del lado del servidor suele ser un programa que escucha en el puerto donde los clientes externos se conectan para acceder a los servicios. El balanceador de carga reenvía las solicitudes a uno de los servidores de backend, que normalmente responde al balanceador. Esto permite que el balanceador de carga responda al cliente sin que este tenga conocimiento de la separación interna de funciones. Además, impide que los clientes contacten directamente con los servidores de backend, lo que puede ofrecer ventajas de seguridad al ocultar la estructura de la red interna y prevenir ataques a la pila de red del kernel o a servicios no relacionados que se ejecutan en otros puertos.

Algunos balanceadores de carga ofrecen un mecanismo para realizar acciones especiales en caso de que todos los servidores backend no estén disponibles. Esto podría incluir el reenvío a un balanceador de carga de respaldo o la visualización de un mensaje sobre la interrupción del servicio.

También es importante que el propio balanceador de carga no se convierta en un punto único de fallo . Por lo general, los balanceadores de carga se implementan en pares de alta disponibilidad que también pueden replicar los datos de persistencia de sesión si la aplicación específica lo requiere. ^{[ 14 ]} Ciertas aplicaciones se programan para ser inmunes a este problema, desplazando el punto de balanceo de carga a través de plataformas de compartición diferencial más allá de la red definida. Los algoritmos secuenciales asociados a estas funciones se definen mediante parámetros flexibles únicos para la base de datos específica. ^{[ 15 ]}

TRILL (Interconexión transparente de muchos enlaces) facilita que una Ethernet tenga una topología arbitraria y permite la división de carga por pares de flujo a través del algoritmo de Dijkstra , sin configuración ni intervención del usuario. El catalizador de TRILL fue un evento en el Centro Médico Beth Israel Deaconess que comenzó el 13 de noviembre de 2002. ^{[ 17 ] [ 18 ]} El concepto de Rbridges ^{[ 19 ]} [sic] se propuso por primera vez al Instituto de Ingenieros Eléctricos y Electrónicos en el año 2004, ^{[ 20 ]} quien en 2005 ^{[ 21 ]} rechazó lo que llegó a conocerse como TRILL, y en los años 2006 a 2012 ^{[ 22 ]} ideó una variación incompatible conocida como Shortest Path Bridging .

El IEEE aprobó el estándar IEEE 802.1aq en mayo de 2012, ^{[ 23 ]} también conocido como Shortest Path Bridging (SPB). SPB permite que todos los enlaces estén activos a través de múltiples rutas de igual costo, proporciona tiempos de convergencia más rápidos para reducir el tiempo de inactividad y simplifica el uso del balanceo de carga en topologías de red en malla (parcialmente conectadas y/o totalmente conectadas) al permitir que el tráfico comparta la carga a través de todas las rutas de una red. ^{[ 24 ] [ 25 ]} SPB está diseñado para reducir los errores de configuración y preserva la naturaleza plug-and-play que estableció a Ethernet como el protocolo de facto en la capa 2. ^{[ 26 ]}

Muchas empresas de telecomunicaciones cuentan con múltiples rutas a través de sus redes o hacia redes externas. Utilizan sistemas sofisticados de balanceo de carga para redirigir el tráfico de una ruta a otra, evitando así la congestión de la red en cualquier enlace en particular y, en ocasiones, minimizando el coste de tránsito a través de redes externas o mejorando la fiabilidad de la red .

Otra forma de utilizar el balanceo de carga es en las actividades de monitorización de red . Los balanceadores de carga pueden utilizarse para dividir grandes flujos de datos en varios subflujos y emplear varios analizadores de red, cada uno de los cuales lee una parte de los datos originales. Esto puede utilizarse para monitorizar redes rápidas como 10GbE o STM64, donde el procesamiento complejo de los datos puede no ser posible a la velocidad de la línea . ^{[ 27 ]}