Algoritmi di Load Balancing: Modelli Matematici di Distribuzione del Traffico nelle Reti di Grandi Dimensioni

Principio Fondamentale del Bilanciamento del Carico

Il bilanciamento del carico (load balancing) è un meccanismo infrastrutturale che distribuisce il traffico di rete in ingresso tra un insieme di server backend, con l'obiettivo di massimizzare l'utilizzo delle risorse computazionali disponibili, minimizzare il tempo di risposta verso il client e garantire la continuità del servizio in caso di guasto parziale dell'infrastruttura. Dal punto di vista matematico, il problema del bilanciamento del carico appartiene alla categoria dei problemi di ottimizzazione combinatoria, e i diversi algoritmi rappresentano differenti approcci euristici alla sua risoluzione in tempo reale.

Un bilanciatore di carico opera tipicamente al livello 4 (trasporto) o al livello 7 (applicazione) del modello OSI. I bilanciatori L4 effettuano il routing basandosi sugli indirizzi IP e le porte TCP/UDP, senza ispezionare il contenuto del payload applicativo. I bilanciatori L7, detti anche application delivery controller (ADC), possono ispezionare le intestazioni HTTP, i cookie di sessione e il contenuto della richiesta per implementare logiche di routing più sofisticate.

Algoritmo Round Robin

L'algoritmo Round Robin rappresenta l'approccio più elementare al bilanciamento del carico. Le richieste vengono distribuite sequenzialmente tra i server disponibili in modo circolare: la prima richiesta va al server S1, la seconda al server S2, la terza al server S3 e così via, ritornando al server S1 al completamento del ciclo.

Formalmente, dato un insieme di server S = {S1, S2, ..., Sn} e un contatore di richieste i, la funzione di selezione del Round Robin è: f(i) = S[(i mod n) + 1]. L'algoritmo assume implicitamente che tutti i server abbiano capacità computazionale equivalente e che tutte le richieste abbiano costo di elaborazione omogeneo.

Round Robin Ponderato (Weighted Round Robin)

La variante ponderata del Round Robin introduce un coefficiente di peso w(Si) per ciascun server, proporzionale alla sua capacità di elaborazione. Un server con peso 3 riceve tre volte il numero di richieste di un server con peso 1 nel medesimo ciclo. Questa variante è appropriata in ambienti eterogenei dove i server backend hanno specifiche hardware differenti e quindi capacità di throughput diverse.

L'implementazione pratica del Weighted Round Robin utilizza tipicamente un vettore pre-calcolato in cui ogni server appare un numero di volte pari al proprio peso, e la selezione avviene mediante scorrimento circolare di questo vettore. La generazione del vettore di pesi ha complessità O(Σw) e viene ricalcolata solo in caso di modifica della configurazione.

Algoritmo Least Connections

L'algoritmo Least Connections (o Minimum Connections) adotta un approccio dinamico: ogni nuova richiesta viene instradata al server che al momento dell'arrivo ha il minor numero di connessioni attive aperte. A differenza del Round Robin, questo algoritmo si adatta automaticamente alla variabilità del tempo di elaborazione delle richieste individuali.

La funzione di selezione è: f(richiesta) = argmin_i c(Si), dove c(Si) è il numero corrente di connessioni attive sul server Si. Il bilanciatore mantiene una tabella di stato con il contatore di connessioni per ciascun server backend, aggiornata ad ogni apertura e chiusura di connessione.

Least Connections Ponderato

Analogamente al Round Robin ponderato, la variante ponderata del Least Connections normalizza il numero di connessioni attive rispetto al peso del server: il server selezionato è quello con il valore minimo del rapporto c(Si) / w(Si). Questo garantisce che server con capacità maggiore gestiscano un numero proporzionalmente superiore di connessioni concorrenti.

Algoritmi Basati su Hash

Gli algoritmi di routing basati su funzioni hash determinano il server destinatario applicando una funzione hash a uno o più attributi della richiesta — tipicamente l'indirizzo IP sorgente, la combinazione IP:porta, o un identificativo di sessione HTTP. Il risultato dell'hash viene mappato su uno specifico server backend tramite un'operazione modulo.

Il vantaggio principale di questo approccio è la persistenza di sessione: richieste provenienti dallo stesso client vengono sistematicamente indirizzate allo stesso server backend, eliminando la necessità di condividere lo stato di sessione tra i server. Questo è particolarmente rilevante per applicazioni stateful che mantengono la sessione utente in memoria locale.

Consistent Hashing

L'algoritmo di consistent hashing, introdotto da Karger et al. nel 1997, risolve un problema fondamentale degli algoritmi hash tradizionali: la riorganizzazione massiva delle mappature quando il numero di server cambia. In un hash tradizionale con modulo, l'aggiunta o rimozione di un singolo server invalida la mappatura della maggior parte delle chiavi. Il consistent hashing dispone server e chiavi su un "anello" circolare: ogni chiave è assegnata al server immediatamente successivo in senso orario. Aggiungere o rimuovere un server richiede solo il riassegnamento delle chiavi adiacenti a quel server, lasciando invariate tutte le altre mappature.

Algoritmo Random

L'algoritmo di selezione casuale (Random) seleziona un server backend tramite un generatore di numeri pseudo-casuali ad ogni richiesta. Nonostante la sua semplicità, nelle grandi distribuzioni statisticamente offre risultati comparabili al Round Robin per workload uniformi. La variante "Power of Two Choices" migliora questo approccio selezionando casualmente due server e scegliendo il meno carico tra i due, ottenendo una distribuzione significativamente più uniforme con un costo computazionale marginale.

Algoritmo Least Response Time

L'algoritmo Least Response Time estende il Least Connections incorporando anche la misurazione del tempo medio di risposta di ciascun server backend. La funzione di selezione considera sia le connessioni attive sia la latenza di elaborazione osservata: il server selezionato è quello con il minimo prodotto tra connessioni attive e tempo di risposta medio. Questo algoritmo richiede che il bilanciatore effettui misurazioni attive (health check) di latenza verso i backend e mantenga una media mobile esponenziale dei tempi di risposta osservati.

Architetture Multi-Tier e Global Load Balancing

In infrastrutture di scala globale, il bilanciamento del carico opera su livelli gerarchici. Il Global Server Load Balancing (GSLB) opera a livello DNS: le query DNS per il nome del servizio restituiscono indirizzi IP diversi a seconda della posizione geografica del client e della disponibilità dei data center. Il bilanciamento locale (cluster load balancing) opera poi all'interno di ciascun data center. Questa architettura gerarchica consente di ottimizzare sia la latenza geografica (routing verso il data center più vicino) sia il bilanciamento delle risorse all'interno di ogni singolo data center.

Considerazioni sull'Alta Disponibilità del Bilanciatore

Il bilanciatore di carico stesso rappresenta un potenziale single point of failure nell'architettura. Le implementazioni production-grade adottano configurazioni in coppia attivo-passivo o attivo-attivo con meccanismi di failover automatico, tipicamente basati su protocolli come VRRP (Virtual Router Redundancy Protocol) o CARP (Common Address Redundancy Protocol). Alcune architetture cloud-native eliminano completamente il bilanciatore centralizzato adottando un approccio di client-side load balancing, in cui ogni istanza client è responsabile della selezione del server backend attraverso un processo di service discovery distribuito.