Robinhood, el servicio interno de balanceo de carga de Dropbox

• Robinhood es el servicio interno de balanceo de carga de Dropbox, implementado en 2020
• Enruta el tráfico interno entre servidores para distribuir de manera equilibrada la carga de los servicios
• Antes de Robinhood, la mayoría de los servicios de Dropbox sufrían por una distribución desigual de la carga entre backends
• Las diferencias de hardware y las limitaciones de los algoritmos de balanceo de carga anteriores provocaban problemas de confiabilidad debido a instancias sobrecargadas
• Para resolver esto, era necesario sobreaprovisionar en exceso las flotas de servicios, lo que aumentaba los costos de hardware

Nuevas funciones de Robinhood

• Al aprovechar un controlador PID (Proportional-Integral-Derivative), ahora puede gestionar el desequilibrio de carga de forma más rápida y efectiva
• Esto ha llevado a mejoras en la confiabilidad de la infraestructura y a una reducción significativa en los costos de hardware
• Con el aumento de las cargas de trabajo de IA que impulsan funciones inteligentes modernas, administrar eficazmente la demanda de recursos de GPU es más importante que nunca

Desafíos del balanceo de carga en Dropbox

• El sistema de descubrimiento de servicios de Dropbox puede escalar a cientos de miles de hosts distribuidos en varios centros de datos en todo el mundo
• Algunos servicios de Dropbox tienen millones de clientes, pero no es posible permitir que cada cliente se conecte a todas las instancias de servidor
  • Esto ejercerá demasiada presión sobre la memoria de los servidores y, cuando un servidor se reinicie, los handshakes TLS pueden sobrecargarlo
• En su lugar, se usa el sistema de descubrimiento de servicios para proporcionar a cada cliente un subconjunto de servidores a los que conectarse
• La mejor estrategia de balanceo de carga disponible para el cliente es hacer round robin con la lista de direcciones proporcionada por el sistema de descubrimiento de servicios
  • Sin embargo, con este método la carga de cada instancia de servidor puede quedar bastante desequilibrada
  • Aumentar el tamaño del subconjunto es una mitigación sencilla, pero no elimina por completo el desequilibrio y solo agrega otro parámetro para el propietario del servicio
• Un problema más profundo es que, incluso si se envía el mismo número de solicitudes a cada servidor, el hardware subyacente puede ser distinto entre ellos
  • Es decir, una solicitud consume diferentes cantidades de recursos según la clase de hardware
• El punto clave es que los clientes no tienen visibilidad de la carga del servidor
• En el pasado, se intentó resolver este problema haciendo que los servidores adjuntaran la carga en los headers de respuesta
  • Los clientes podían realizar el balanceo de carga por su cuenta seleccionando el endpoint menos cargado dentro del subconjunto de direcciones
  • Los resultados fueron prometedores, pero todavía había varias desventajas
    • Como se requerían cambios de código tanto en servidores como en clientes para esos headers especiales de carga, era difícil adoptarlo a escala global
    • Los resultados fueron buenos, pero no lo suficientemente buenos

Decisión de construir Robinhood

• En 2019 se tomó la decisión oficial de construir Robinhood
• Este nuevo servicio se construyó sobre el sistema interno existente de descubrimiento de servicios, recopilando información de carga de los servidores y adjuntándola a la información de enrutamiento
• Robinhood aprovecha el Endpoint Discovery Service de Envoy para integrar la información de carga en los pesos de los endpoints, permitiendo que los clientes hagan round robin basado en pesos
• Como la comunidad de gRPC está adoptando el protocolo xDS de Envoy, Robinhood es compatible tanto con Envoy como con clientes gRPC
• Se decidió construir un nuevo servicio porque no existía una solución de balanceo de carga disponible que cumpliera con los requisitos de Dropbox en ese momento

Resultados de Robinhood

• Tras varios años de uso en producción, ha mostrado resultados prometedores
• Se logró reducir en 25% el tamaño de la flota de algunos servicios grandes, lo que generó ahorros significativos en costos de hardware cada año
• La confiabilidad también mejoró al disminuir la cantidad de procesos sobreutilizados

Arquitectura de Robinhood

• En cada centro de datos se implementan instancias de Robinhood, compuestas por tres partes: servicio de balanceo de carga, proxy y base de datos de enrutamiento

Servicio de balanceo de carga (LBS)

• El núcleo de Robinhood
• Se encarga de recopilar información de carga y generar información de enrutamiento con pesos de endpoint
• Como varias instancias actualizan simultáneamente la información de enrutamiento de un servicio, se utiliza un shard manager interno para asignar un worker principal a cada servicio
• Dado que cada servicio es independiente, el LBS puede particionarse por servicio y escalar horizontalmente

Proxy

• Se encarga de enrutar la información de carga de los servicios hacia la partición LBS correspondiente dentro del centro de datos
• El uso de proxies también reduce la cantidad de conexiones directas a los procesos LBS
  • Sin el proxy, todos los procesos LBS tendrían que conectarse a todos los nodos de la infraestructura
  • En cambio, los procesos LBS solo se conectan a los proxies, lo que reduce significativamente la presión de memoria sobre LBS
• Los proxies solo se conectan a nodos dentro del mismo centro de datos, por lo que pueden escalar horizontalmente
• Este patrón se usa en muchas partes de la infraestructura para proteger los servicios de recibir demasiadas conexiones TLS

Base de datos de enrutamiento

• Una base de datos basada en ZooKeeper/etcd que almacena información de enrutamiento de los servicios, como nombres de host, direcciones IP y pesos generados por el LBS
• ZooKeeper y etcd pueden notificar en tiempo real a todos los watchers sobre cambios en nodos/keys, lo que los hace muy adecuados para el caso de uso de descubrimiento de servicios centrado en lectura de Dropbox
• La consistencia eventual garantizada por ZooKeeper/etcd también es suficiente para el descubrimiento de servicios

Un vistazo más de cerca al servicio de balanceo de carga

• El objetivo del balanceo de carga es hacer que la utilización de todos los nodos sea igual a la utilización promedio
• Se usa un controlador PID para mantener la utilización de cada nodo casi igual a la utilización promedio
• El LBS crea un controlador PID para cada nodo y usa la utilización promedio como setpoint
• El LBS usa la salida del controlador PID como delta para los pesos de los endpoints y normaliza los pesos entre todos los endpoints del servicio
• Aunque un nodo nuevo necesita varios ajustes para converger hacia la utilización promedio, el controlador PID es muy efectivo para el balanceo de carga

Escenarios de operación del LBS

• El LBS está diseñado para manejar diversos escenarios que pueden afectar el balanceo de carga, desde reinicios de nodos hasta reportes de carga faltantes
• Para mantener un rendimiento óptimo, el LBS implementa varias estrategias para manejar estos casos excepcionales

Inicio del LBS

• El LBS mantiene en memoria la información de carga y el estado del controlador PID
• Durante un reinicio del LBS, no comienza a actualizar pesos de inmediato, sino que espera un momento hasta que lleguen los reportes de carga
• En cuanto a los pesos del controlador PID, el LBS restaura los pesos de endpoints leyendo la base de datos de enrutamiento

Nodos con Cold Start

• Como nuevos nodos se incorporan con frecuencia a la flota de servicios, es importante evitar el problema de Thundering Herd
• Dado que la utilización inicial de un nodo nuevo normalmente es 0, el LBS establece el peso del nodo nuevo en un peso de endpoint bajo y deja que el controlador PID lo lleve hasta la utilización promedio

Reportes de carga faltantes

• En entornos de sistemas distribuidos, las fallas son comunes
• Debido a congestión de red o fallas de hardware, los reportes de carga de algunos nodos pueden retrasarse o no llegar
• El LBS omite esos nodos durante la actualización de pesos, por lo que sus pesos de endpoint no cambian
• Sin embargo, si faltan muchos reportes de carga, el cálculo de la utilización promedio puede volverse inexacto
• Por seguridad, en ese caso el LBS omite por completo la etapa de actualización de pesos

Métricas de utilización

• La utilización de CPU es la métrica de balanceo de carga más usada en Dropbox
• Para servicios que no tienen cuello de botella en CPU, la cantidad de solicitudes en curso es una buena métrica alternativa
• El LBS está implementado para admitir balanceo de carga basado en CPU y/o solicitudes en curso

Limitaciones

• El controlador PID forma un bucle de retroalimentación para mantener la utilización del nodo cerca del valor objetivo (la utilización promedio)
• En casos con muy poca retroalimentación, como servicios con muy poco tráfico o solicitudes de latencia muy alta medidas en minutos, el balanceo de carga no resulta efectivo
• Los servicios con solicitudes de alta latencia deben ser asíncronos

Enrutamiento entre centros de datos

• Las instancias de LBS manejan el balanceo de carga dentro de un centro de datos
• El enrutamiento entre centros de datos implica otras consideraciones
  • Por ejemplo, se busca enrutar las solicitudes al centro de datos más cercano para reducir el tiempo de ida y vuelta de las solicitudes
• Para ello, se introduce una configuración de localidad que define la división del tráfico entre centros de datos de destino

Evaluación del rendimiento del balanceador de carga

• El rendimiento del balanceo de carga se mide con la relación max/avg
  • Si el propietario del servicio elige el balanceo de carga basado en CPU, se usa maxCPU/avgCPU como métrica de rendimiento
  • Los propietarios de servicios normalmente aprovisionan sus servicios según la utilización máxima entre nodos, porque el objetivo principal del balanceo de carga es reducir el tamaño de la flota
• La estrategia de balanceo de carga con controlador PID puede mantener la relación max/avg cerca de 1

Gráficas de evaluación del rendimiento del balanceo de carga

• Gráfica que muestra max/avg CPU y p95/avg CPU del clúster más grande entre los clústeres de proxy Envoy
  • Después de habilitar el balanceo de carga basado en controlador PID, ambas métricas bajan hasta acercarse a 1
  • La relación max/avg bajó de 1.26 a 1.01, lo que muestra una mejora del 20%
• Gráfica que muestra un análisis de percentiles de la utilización de CPU por nodo
  • Después de habilitar el balanceo de carga basado en controlador PID, max, p95, avg y p5 casi se unifican en una sola línea
• Otra gráfica que muestra max/avg CPU y p95/avg CPU del clúster más grande entre los clústeres frontend de base de datos
  • Después de habilitar el balanceo de carga basado en controlador PID, ambas métricas bajan hasta acercarse a 1
  • La relación max/avg bajó de 1.4 a 1.05, lo que muestra una mejora del 25%
• Otra gráfica que muestra un análisis de percentiles de la utilización de CPU por nodo
  • Después de habilitar el balanceo de carga basado en controlador PID, max, p95, avg y p5 vuelven a unificarse casi en una sola línea

Razón para construir Config Aggregator

• Robinhood ofrece varias opciones que los propietarios de servicios pueden elegir, y también puede aplicar cambios de forma dinámica
• Los propietarios de servicios crean y actualizan la configuración de Robinhood para su servicio en el directorio del servicio dentro del codebase
• Estas configuraciones se almacenan en un servicio de gestión de configuración, que es una biblioteca conveniente para recibir en tiempo real cambios en la configuración de Robinhood
• Sin embargo, por varios problemas no era posible construir y publicar periódicamente desde el codebase la megaconfiguración de Robinhood
  • Si un cambio introducido por un push de configuración causa problemas, presionar el botón de rollback es riesgoso
    • porque no se sabe cuántos otros servicios cambiaron desde el último push
  • El equipo responsable de Robinhood también es responsable de cada push de la megaconfiguración
    • Esto significa que el equipo de Robinhood debe participar en todos los pushes de configuración modificada, lo cual es una pérdida de tiempo de ingeniería
    • porque la mayoría de los incidentes pueden ser resueltos por los propietarios del servicio
  • Para minimizar el riesgo potencial, cada push tarda horas en desplegarse en varios centros de datos
• Para resolver estos problemas, construyeron otro pequeño servicio llamado Config Aggregator

Config Aggregator

• Config Aggregator recopila todas las configuraciones específicas por servicio y construye la megaconfiguración que usará LBS
• Config Aggregator observa las configuraciones específicas por servicio y propaga los cambios a la megaconfiguración en tiempo real
• Config Aggregator también ofrece una función de tombstone para evitar que la configuración de Robinhood de un servicio se elimine por accidente
  • Si el propietario del servicio hace push de un cambio que elimina el servicio de la configuración de Robinhood, Config Aggregator marca la entrada del servicio con un tombstone en lugar de eliminarla de inmediato
  • La eliminación real ocurre varios días después
  • Esta función también resuelve condiciones de carrera que pueden surgir por los distintos ciclos de push entre la configuración de Robinhood y otras configuraciones de enrutamiento, como la configuración de Envoy
• Una desventaja del servicio de gestión de configuración es que actualmente no tiene control de versiones
• La megaconfiguración se respalda periódicamente en caso de que sea necesario revertir la configuración de LBS a un estado conocido como bueno

Estrategia de migración

• Cambiar la estrategia de balanceo de carga de una sola vez puede ser riesgoso
• Esa es la razón por la que Robinhood permite configurar múltiples estrategias de balanceo de carga para un servicio
• Dropbox cuenta con feature gates basados en porcentajes, así que implementaron una estrategia híbrida donde el cliente usa como peso del endpoint una suma ponderada de los pesos generados por dos estrategias de balanceo de carga
• Esto permite migrar gradualmente a la nueva estrategia de balanceo de carga mientras todos los clientes siguen viendo la misma asignación de pesos para los endpoints

Lecciones aprendidas

• Durante el diseño e implementación de Robinhood obtuvieron varias lecciones clave sobre qué funcionó y qué no
• Al priorizar la simplicidad, minimizar los cambios en el cliente y planear la migración desde el principio, pudieron simplificar el desarrollo y despliegue de LBS y evitar errores costosos

La configuración debe ser lo más simple posible

• Robinhood introdujo muchas opciones que los propietarios de servicios pueden configurar
• Sin embargo, en la mayoría de los casos lo que necesitan es la configuración predeterminada proporcionada
• Una configuración predeterminada buena y simple, o mejor aún, ninguna configuración, puede ahorrar una enorme cantidad de tiempo de ingeniería

Mantener simples también los cambios del cliente

• Hacer rollout de cambios a clientes internos puede tomar meses
  • La mayoría de los despliegues se hacen semanalmente, pero muchos se hacen una vez al mes o incluso no se despliegan en años
• Cuantos más cambios puedan moverse a LBS, mejor
  • Por ejemplo, al principio decidieron usar weighted round robin en el diseño del cliente, y no lo han cambiado desde entonces
  • Esto aceleró enormemente el avance
• Limitar la mayoría de los cambios a LBS también reduce el riesgo para la estabilidad
  • porque, si es necesario, los cambios en LBS pueden revertirse en cuestión de minutos

La migración debe planearse en la etapa de diseño del proyecto

• La migración consume una enorme cantidad de tiempo de ingeniería
• También hay riesgos de estabilidad que deben considerarse
• No es un trabajo divertido, pero sí importante
• Al diseñar un nuevo servicio, hay que pensar lo antes posible cómo migrar sin fricción los casos de uso existentes al nuevo servicio
• Cuantas más exigencias se le hagan al propietario del servicio, más pesadilla se vuelve la migración
  • especialmente en el caso de componentes básicos de infraestructura
• Como el proceso de migración de Robinhood no estuvo bien diseñado desde el principio, terminaron invirtiendo mucho más tiempo del esperado en reimplementar el proceso y rediseñar la configuración
• El tiempo de ingeniería necesario para la migración debería ser una métrica clave del éxito

Efecto de Robinhood

• Después de alrededor de un año en producción, se puede decir que la iteración más reciente de Robinhood resolvió de manera efectiva los problemas históricos de balanceo de carga de Dropbox
• El algoritmo central de controlador PID mostró resultados prometedores y mejoras de rendimiento significativas en los servicios más grandes
• Obtuvieron perspectivas valiosas sobre el diseño y la operación de un servicio de balanceo de carga a la escala de Dropbox

Notas

1. Sean N, M y s el número de servidores, el número de clientes y el tamaño del subconjunto de direcciones, respectivamente. El número de clientes a los que se conecta un servidor sigue una muestra de la distribución binomial B(M, s/n). Como se mencionó antes, los clientes realizan round robin simple sobre el conjunto de direcciones provisto por el descubrimiento de servicios. Por lo tanto, si cada cliente envía aproximadamente la misma cantidad de solicitudes, la distribución de carga del lado del servidor se parece a una distribución binomial.

2. Se extendió el sistema existente de descubrimiento de servicios para soportar el protocolo gRPC xDS (A27). A la fecha de redacción de este blog, los clientes de gRPC no soportaban weighted round robin para los pesos de endpoint del control plane, por lo que implementaron un selector personalizado de weighted round robin basado en shortest deadline first scheduling.

3. Surgió un caso interesante en el que un servicio a veces se atascaba por I/O degradado. En esta situación, la CPU de ese nodo se mantenía baja y LBS empezaba a aumentar el peso del nodo para llevar su CPU al promedio, lo que llevaba a una espiral de muerte. Como solución, se pasó a usar el máximo entre CPU y solicitudes en curso como medida de carga para equilibrar el servicio.

Opinión de GN⁺

• Robinhood parece ser un excelente servicio que resolvió de forma efectiva los desafíos de balanceo de carga de Dropbox. Resulta especialmente impresionante el uso de un controlador PID
• Este es un buen caso que muestra lo difícil que puede ser el balanceo de carga en una infraestructura global de gran escala. Hay muchos factores que considerar, como diferencias de hardware, distribución desigual de la carga y congestión de red
• Parece importante diseñar el sistema para que todos los componentes funcionen de manera orgánica y conectada. Aunque LBS, el proxy y la base de datos de enrutamiento están separados, interactúan estrechamente en tiempo real
• Son llamativas las gráficas que evalúan cuantitativamente el rendimiento del balanceo de carga y visualizan las mejoras. En especial, muestran bien que mantener la proporción max/avg cerca de 1 es importante para optimizar el tamaño de la flota
• También parece una buena idea haber introducido Config Aggregator para separar la configuración por servicio. Esto permite que los responsables de cada servicio gestionen sus propios cambios de forma independiente
• También es un detalle cuidadoso haber incorporado mecanismos de seguridad como tombstone. Es importante evitar que una configuración se elimine por error
• Las lecciones sobre la estrategia de migración también parecen útiles. Si no se considera la migración desde el principio, más adelante puede consumir mucho tiempo
• En general, Robinhood parece una solución sistemática y sofisticada para el balanceo de carga a la escala de Dropbox. Es un caso que otras empresas con infraestructura de gran tamaño también podrían tomar como referencia

Soluciones similares:

• Elastic Load Balancing (ELB) de AWS y Cloud Load Balancing de Google Cloud también ofrecen servicios administrados para balanceo de carga a gran escala
• En el caso de Kubernetes, cuenta con su propio balanceador de carga (kube-proxy), pero si se usan soluciones de service mesh como Istio o Linkerd, se puede acceder a funciones más potentes de balanceo de carga y gestión de tráfico
• Zuul de Netflix y Envoy de Lyft también ofrecen funciones de balanceo de carga basadas en proxy

Aspectos a considerar al adoptarlo:

• Es necesario verificar la compatibilidad con la infraestructura y los servicios existentes. Si se requiere una migración, hay que definir una estrategia
• Se debe probar y monitorear suficientemente el impacto en el rendimiento y la estabilidad. Un bug en la lógica de balanceo de carga puede ser crítico
• Hay que decidir el alcance y la velocidad de adopción considerando la capacidad del equipo. En lugar de aplicarlo de golpe a todo, parece mejor una adopción gradual
• A largo plazo, será necesario seguir optimizando y mejorando continuamente. Actividades como ajustar el algoritmo de balanceo de carga según la situación y eliminar cuellos de botella pueden ayudar bastante

[kbumsik]

Es curioso ver que mencionen un controlador PID en el lado del software jaja