Mathématiques du distribué¶

Les systèmes distribués reposent sur des modèles mathématiques précis — ignorer ces modèles, c'est dimensionner à l'aveugle et déboguer des pannes sans cadre de raisonnement.

Théorie des files d'attente¶

Un système qui reçoit des requêtes et les traite peut toujours être modélisé comme une file d'attente. La théorie des files d'attente fournit des formules exactes pour prédire latence, longueur de file et taux d'utilisation — sans avoir a déployer et mesurer.

La loi de Little¶

La loi de Little (John Little, 1961) est le résultat le plus universel de la théorie des files :

• L : nombre moyen d'éléments dans le système (en attente + en traitement)
• λ (lambda) : taux d'arrivee moyen (éléments par unite de temps)
• W : temps moyen de sejour dans le système (attente + traitement)

Cette loi est remarquable : elle s'applique a tout système en regime stationnaire, quelles que soient les distributions d'arrivee et de service. Pas besoin de supposer des distributions exponentielles.

Exemple concret : un service HTTP reçoit en moyenne 200 requêtes/seconde (\(\lambda = 200\ \text{req/s}\)). Le temps de réponse moyen est 150ms (\(W = 0.15\ \text{s}\)). La loi de Little prédit \(L = 200 \times 0.15 = 30\) requêtes simultanées dans le système — ce qui donne le nombre de threads/connexions nécessaires.

def loi_de_little(lambda_arrivee, W_sejour):
    """
    lambda_arrivee : requetes par seconde
    W_sejour : temps de sejour moyen en secondes
    Retourne : nombre moyen d'elements dans le systeme
    """
    return lambda_arrivee * W_sejour

# Dimensionner un pool de connexions DB
taux = 500       # req/s
temps_db = 0.020 # 20ms par requete DB
L = loi_de_little(taux, temps_db)
print(f"Connexions DB necessaires : {L:.0f}")  # -> 10 connexions

Le modèle M/M/1¶

Le modèle M/M/1 est la file la plus simple avec des propriétés analytiques :

• Arrivees suivant un processus de Poisson de taux \(\lambda\)
• Temps de service exponentiels de taux moyen \(\mu\) (donc durée moyenne \(1/\mu\))
• Un seul serveur

Le taux d'utilisation (fraction du temps ou le serveur est occupe) :

Pour que la file soit stable (ne grossit pas indéfiniment) : \(\rho < 1\).

Formules clés pour M/M/1 :

def mm1(lambda_, mu):
    """
    lambda_ : taux d'arrivee (req/s)
    mu      : taux de service (req/s, = 1 / duree_traitement)
    """
    if lambda_ >= mu:
        raise ValueError("Systeme instable : lambda >= mu")
    rho = lambda_ / mu
    L   = rho / (1 - rho)
    Lq  = rho**2 / (1 - rho)
    W   = 1 / (mu - lambda_)
    Wq  = rho / (mu - lambda_)
    return {
        "utilisation_%": rho * 100,
        "elements_systeme": L,
        "elements_file": Lq,
        "temps_sejour_s": W,
        "temps_attente_s": Wq,
    }

# Service qui traite 100 req/s, recoit 80 req/s
resultats = mm1(lambda_=80, mu=100)
# utilisation   : 80%
# temps_sejour  : 50ms  (vs 10ms sans file)
# temps_attente : 40ms  (attente pure)

Impact non-lineaire de la charge¶

La conséquence la plus importante du modèle M/M/1 : la latence diverge de façon non lineaire quand l'utilisation approche 100%.

Un système a 80% d'utilisation souffre 5 fois plus de latence qu'a utilisation nulle. A 95%, c'est 20 fois. C'est pourquoi les SLO de saturation sonnent l'alarme a 70-80% et non a 100%.

Formule d'Erlang-C (M/M/c)¶

Pour un pool de \(c\) serveurs (workers, threads, instances) — le modèle M/M/c — la formule d'Erlang-C donne la probabilite qu'un client attende :

import math

def erlang_c(c, rho_total):
    """
    c          : nombre de serveurs
    rho_total  : charge totale = lambda / mu
    Retourne : probabilite d'attente
    """
    a = rho_total  # charge totale
    rho = a / c    # charge par serveur

    if rho >= 1:
        return 1.0  # systeme sature

    # Terme de Poisson
    sum_poisson = sum(a**k / math.factorial(k) for k in range(c))
    erlang_b = (a**c / math.factorial(c)) / (sum_poisson + a**c / math.factorial(c))

    return (erlang_b) / (1 - rho * (1 - erlang_b))

def dimensionner_workers(lambda_, mu, prob_attente_max=0.05):
    """
    Trouve le nombre minimal de workers pour respecter
    la contrainte de probabilite d'attente.
    """
    charge = lambda_ / mu
    c = max(1, int(charge) + 1)
    while erlang_c(c, charge) > prob_attente_max:
        c += 1
    return c

# Exemple : 1000 req/s, chaque requete prend 20ms
# mu = 1/0.02 = 50 req/s par worker
workers = dimensionner_workers(lambda_=1000, mu=50, prob_attente_max=0.05)
print(f"Workers necessaires : {workers}")
# -> environ 23 workers (charge = 20, marge pour absorber les pics)

Application : dimensionner et prédire¶

Prédire l'impact d'un pic de trafic¶

Un service traitant 400 req/s (\(\mu = 500\ \text{req/s}\), \(\rho = 80\%\)) présente un temps de réponse de 10ms. Que se passe-t-il si le trafic monte a 450 req/s (+12.5%) ?

avant = mm1(lambda_=400, mu=500)
apres = mm1(lambda_=450, mu=500)

print(f"Avant : {avant['temps_sejour_s']*1000:.1f}ms")
print(f"Apres : {apres['temps_sejour_s']*1000:.1f}ms")
# Avant : 10.0ms
# Apres : 20.0ms   <- doublement de la latence pour +12% de trafic

Dimensionner un pool de workers asynchrones¶

Un pipeline de traitement de messages (Kafka, RabbitMQ) reçoit 2000 messages/minute. Chaque traitement prend en moyenne 1.5 secondes. Combien de workers ?

lambda_msgs = 2000 / 60   # ≈ 33.3 msg/s
mu_worker   = 1 / 1.5     # ≈ 0.67 msg/s par worker

# Charge minimale theorique
charge_min = lambda_msgs / mu_worker  # ≈ 50 workers

# Avec marge de 40% pour les pics et variabilite
workers_recommandes = int(charge_min * 1.4)  # 70 workers

# Verification avec Erlang-C
p_attente = erlang_c(workers_recommandes, charge_min)
print(f"P(attente) avec {workers_recommandes} workers : {p_attente:.1%}")
# -> P(attente) ≈ 0.1% : tres peu de messages attendront

Théorie de l'information¶

Shannon (1948) a pose les fondements mathématiques de la communication : qu'est-ce que l'information ? Quelle est la capacité maximale d'un canal ? Quand peut-on comprimer et jusqu'ou ?

Entropie de Shannon¶

L'entropie mesure l'incertitude (ou la quantite d'information) d'une source aléatoire. Pour une variable aléatoire \(X\) prenant les valeurs \(x_i\) avec probabilites \(p_i\) :

L'unite est le bit. \(H(X)\) est maximal (incertitude maximale) quand toutes les issues sont equiprobables, nul quand une issue est certaine.

import numpy as np

def entropie(probs):
    """Entropie de Shannon en bits."""
    probs = np.array(probs)
    probs = probs[probs > 0]  # eviter log(0)
    return -np.sum(probs * np.log2(probs))

# Pile ou face equitable
entropie([0.5, 0.5])          # 1.0 bit -> incertitude maximale

# De a 6 faces
entropie([1/6] * 6)           # 2.585 bits

# Piece biaisee (90% pile)
entropie([0.9, 0.1])          # 0.469 bits -> peu d'incertitude

# Source deterministe
entropie([1.0, 0.0])          # 0.0 bits -> aucune incertitude

Compression et limite de Shannon¶

Le théorème de codage de source de Shannon affirme qu'on ne peut pas comprimer une source en dessous de son entropie. L'entropie est la longueur minimale de code par symbole atteignable.

Exemple : un texte anglais a environ 1.0-1.5 bits d'entropie par caractère (les humains peuvent prédire la suite avec une bonne probabilite). Un texte aléatoire a 8 bits par caractère (ASCII). C'est pourquoi gzip comprime bien du texte anglais (x5-x10) mais pas des données déjà chiffrees (qui approchent de l'aléatoire).

Capacité d'un canal : théorème de Shannon-Hartley¶

La capacité maximale d'un canal analogique de largeur de bande \(B\) avec un rapport signal/bruit \(S/N\) :

Conséquence : pour doubler le débit, on peut doubler la bande passante OU améliorer le rapport signal/bruit. Mais le gain est logarithmique en S/N — doubler la puissance d'émission ne double pas le débit.

def capacite_canal(bande_passante_hz, snr_lineaire):
    """Capacite de Shannon en bits/s."""
    return bande_passante_hz * np.log2(1 + snr_lineaire)

# Connexion fibre optique : B=1 GHz, SNR=1000 (30 dB)
cap = capacite_canal(1e9, 1000)
print(f"Capacite : {cap/1e9:.1f} Gbps")  # ≈ 10 Gbps

# WiFi 802.11ac : B=80 MHz, SNR varie selon distance
for snr_db in [10, 20, 30, 40]:
    snr = 10**(snr_db/10)
    cap = capacite_canal(80e6, snr)
    print(f"SNR={snr_db}dB : {cap/1e6:.0f} Mbps")

Application : dimensionner la bande passante¶

Un service de streaming video envoie 4K HDR a 25fps. Chaque frame non compressee : \(3840 \times 2160 \times 3\ \text{octets} \times 8\ \text{bits} = 477\ \text{Mbps}\). Avec HEVC (entropie exploitee + redondance temporelle), le débit tombe a 15-25 Mbps. Mais combien de bande passante réserver par utilisateur concurrent ?

La réponse dépend de l'entropie du contenu :

• Film d'animation avec fonds stables : 8-12 Mbps (peu de variabilite temporelle)
• Film d'action avec mouvements rapides : 20-30 Mbps (entropie temporelle élevée)
• Prédiction à la capacité mediane + marge de 20% pour les scenes difficiles

Horloges logiques¶

Dans un système distribué, il n'existe pas d'horloge globale. Chaque nœud a sa propre horloge physique qui dérivé légèrement. Les horloges logiques permettent d'ordonner les événements sans horloge physique partagee.

Relation "happened-before" (Lamport, 1978)¶

La relation \(\rightarrow\) ("happened-before") est définie par Lamport :

1. Si \(a\) et \(b\) sont des événements sur le même processus et \(a\) arrive avant \(b\), alors \(a \rightarrow b\)
2. Si \(a\) est l'envoi d'un message et \(b\) sa reception, alors \(a \rightarrow b\)
3. Transitivite : si \(a \rightarrow b\) et \(b \rightarrow c\), alors \(a \rightarrow c\)

Deux événements sans relation happened-before sont concurrents (notation \(a \| b\)).

Horloge de Lamport¶

Chaque processus maintient un compteur entier (l'horloge de Lamport) :

• Incrementer avant chaque événement local
• À l'envoi d'un message : inclure la valeur courante de l'horloge
• À la reception : \(\text{horloge} = \max(\text{horloge\_locale}, \text{horloge\_message}) + 1\)

class HorlogeLamport:
    def __init__(self, pid):
        self.pid = pid
        self.t = 0

    def evenement_local(self, description):
        self.t += 1
        print(f"P{self.pid} [{self.t}] : {description}")
        return self.t

    def envoyer(self, destination, message):
        self.t += 1
        print(f"P{self.pid} [{self.t}] -> P{destination} : {message}")
        return self.t, message

    def recevoir(self, t_expediteur, message):
        self.t = max(self.t, t_expediteur) + 1
        print(f"P{self.pid} [{self.t}] recu : {message}")
        return self.t

Propriété garantie : si \(a \rightarrow b\), alors \(L(a) < L(b)\). Mais la reciproque n'est pas vraie : \(L(a) < L(b)\) n'implique pas \(a \rightarrow b\). Deux événements concurrents peuvent avoir des horloges quelconques.

Horloges vectorielles¶

Les horloges vectorielles (Fidge & Mattern, 1988) capturent exactement la causalite. Chaque processus \(i\) maintient un vecteur \(V[0..n-1]\) (un compteur par processus).

• Événement local sur \(P_i\) : \(V[i] \mathrel{+}= 1\)
• Envoi depuis \(P_i\) : inclure \(V\) entier, puis \(V[i] \mathrel{+}= 1\)
• Reception par \(P_j\) de \((V_{msg})\) : \(V[j] = \max(V[j], V_{msg})\) composante par composante, puis \(V[j][j] \mathrel{+}= 1\)

Comparaison de deux vecteurs \(V_a\) et \(V_b\) :

• \(V_a < V_b\) (\(a \rightarrow b\)) si toutes composantes de \(V_a \leq V_b\) et au moins une strictement inférieure
• \(V_a \| V_b\) (concurrents) sinon

def compare_vc(Va, Vb):
    """Compare deux horloges vectorielles."""
    leq = all(a <= b for a, b in zip(Va, Vb))
    lt  = any(a < b  for a, b in zip(Va, Vb))
    geq = all(a >= b for a, b in zip(Va, Vb))
    gt  = any(a > b  for a, b in zip(Va, Vb))

    if leq and lt:  return "a -> b (a avant b)"
    if geq and gt:  return "b -> a (b avant a)"
    if Va == Vb:    return "a == b (identiques)"
    return "a || b (concurrents)"

# Exemple
Va = [2, 1, 0]
Vb = [1, 2, 1]
print(compare_vc(Va, Vb))  # a || b (concurrents)

Va = [1, 1, 0]
Vb = [2, 2, 1]
print(compare_vc(Va, Vb))  # a -> b (a avant b)

Diagramme : horloges vectorielles en action¶

sequenceDiagram
    participant P0
    participant P1
    participant P2

    Note over P0: [1,0,0] evenement local
    P0->>P1: message m1 avec [2,0,0]
    Note over P1: [0,1,0] evenement local
    Note over P1: reception m1 : max([0,1,0],[2,0,0])+1 = [2,2,0]
    P1->>P2: message m2 avec [2,3,0]
    Note over P2: [0,0,1] evenement local
    Note over P2: reception m2 : max([0,0,1],[2,3,0])+1 = [2,3,2]
    P0->>P2: message m3 avec [3,0,0]
    Note over P2: reception m3 : max([2,3,2],[3,0,0])+1 = [3,3,3]
    Note over P1,P2: P2 sait que son dernier evenement\na eu lieu APRES m1 et m2

Les horloges vectorielles sont utilisées dans les bases de données distribuées pour détecter les conflits (Riak, DynamoDB utilise des variantes), dans les systèmes de réplication, et dans les outils d'analyse post-mortem de systèmes distribués.

Théorème CAP formalise¶

Énoncé précis (Gilbert & Lynch, 2002)¶

Le théorème CAP, formule par Eric Brewer (2000) et prouve par Gilbert et Lynch (2002), affirme :

Dans un système distribué sujet aux partitions réseau, il est impossible de garantir simultanément la cohérence (Consistency) et la disponibilité (Availability).

Définitions rigoureuses :

• Cohérence (C) : toute lecture retourné la valeur de la dernière écriture (cohérence lineaire). Chaque nœud voit les mêmes données au même moment.
• Disponibilité (A) : chaque requête reçue par un nœud non-defaillant obtient une réponse (pas de timeout, pas d'erreur).
• Tolérance aux partitions (P) : le système continue à fonctionner malgre la perte de messages arbitraires entre nœuds.

La partition réseau n'est pas optionnelle dans un système distribué réel — les réseaux partitionnent. Donc le vrai choix est : C ou A pendant une partition.

Limites du théorème CAP¶

CAP a été critique et affine depuis sa publication :

1. La cohérence de CAP est stricte (linearisabilite) — dans la pratique, on distingue plusieurs niveaux de cohérence : éventuellement cohérent, cohérence causale, lecture de votre propre écriture, cohérence monotone... La plupart des systèmes "AP" garantissent des formes de cohérence plus faibles mais utiles.

2. Les partitions sont rares — en l'absence de partition, on peut avoir cohérence ET disponibilité. CAP ne s'applique qu'en cas de partition effective.

3. Disponibilité graduelle — la disponibilité n'est pas binaire. Un système peut répondre lentement, en mode dégradé, ou avec une probabilite d'échec faible.

PACELC : extension de CAP¶

PACELC (Daniel Abadi, 2012) complète CAP en couvrant le comportement hors partition :

If Partition: C or A
Else (normal operation): L (Latency) or C (Consistency)

En l'absence de partition, le vrai trade-off est entre latence et cohérence : une écriture fortement cohérente doit attendre la confirmation de plusieurs replicas (latence élevée) ; une écriture éventuellement cohérente répond immédiatement (latence faible mais lecture potentiellement perimee).

Exemple pratique : choisir pour son use case¶

Panier e-commerce -> AP (mieux afficher un panier perime que de bloquer)
Compte bancaire   -> CP (mieux refuser la transaction que risquer un double debit)
Session utilisateur -> AP avec TTL (coherence eventuelle acceptable)
Coordination de leader (election) -> CP strict (Raft via etcd)
Catalogue produits -> AP (un prix perime de quelques secondes est acceptable)
Stock en temps reel -> CP (surcommande = probleme metier grave)

Synthèse : les modèles comme outils de décision¶