Equilibrio de carga en servidores (algoritmo aleatorio)

Considere un sitio web de alto tráfico que recibe millones de requests (de diferentes tipos) cada cinco minutos, el sitio tiene k (por ejemplo, n = 1000) servidores para procesar las requests. ¿Cómo se debe equilibrar la carga entre los servidores?

Las soluciones en las que generalmente pensamos son
a) Round Robin
b) Asignar una nueva solicitud a un servidor que tenga una carga mínima.

Los dos enfoques anteriores se ven bien, pero requieren que se mantenga información de estado adicional para equilibrar la carga. El siguiente es un enfoque simple que funciona mejor que los enfoques anteriores.

Do following whenever a new request comes in, 
        Pick a random server and assign the request to a random server

El enfoque anterior es más simple, liviano y sorprendentemente efectivo. Este enfoque no calcula la carga existente en el servidor y no necesita gestión del tiempo.

Análisis del enfoque aleatorio anterior
Analicemos la carga promedio en un servidor cuando se utiliza el enfoque anterior de selección aleatoria del servidor.

Que haya k solicitud (o trabajos) J ₁ , J ₂ , … J _k

Sean n servidores S ₁ , S ₂ , … S _k .

Deje que el tiempo tomado por i’th trabajo sea T _i

Sea R _ij cargado en el servidor S _i desde Job J _j .

R _ij es T _j si el trabajo j’th (o J _j ) se asigna a S _i , de lo contrario 0. Por lo tanto, el valor de R _ij es T _j con probabilidad 1/n y el valor es 0 con probabilidad (1-1/n )

Deje que R _se cargue en el i’ésimo servidor

Average Load on i'th server 'Ex(Ri)' 
                            [Applying Linearity of Expectation]
                          =  
                          = 
                          = (Total Load)/n  

Entonces, la carga promedio en un servidor es la carga total dividida por n, que es un resultado perfecto.

¿Cuál es la posibilidad de desviación del promedio (un servidor en particular recibe demasiada carga)?
La carga promedio del enfoque de asignación aleatoria anterior se ve bien, pero puede existir la posibilidad de que un servidor en particular se cargue demasiado (incluso si el promedio está bien).
Resulta que la probabilidad de desviación del promedio también es muy baja (se puede probar usando el límite de Chernoff ). Los lectores pueden consultar los enlaces de referencia a continuación para probar las desviaciones. Por ejemplo, en una videoconferencia del MIT , se muestra que si hay 2500 requests por unidad de tiempo y hay 10 servidores, entonces la probabilidad de que cualquier servidor en particular obtenga un 10% más de carga es como máximo 1/16000. También se muestran resultados similares al final de la segunda referencia.

Entonces, el esquema de equilibrio de carga simple anterior funciona perfectamente. De hecho, este esquema se usa en balanceadores de carga.

Referencias:
http://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/probabilityandcomputing.pdf

Video conferencia del MIT

Este artículo es una contribución de Shivam . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.