Go : Ordonnanceur distribué, affinité, scoring et anti-famine

Cette semaine, j'ai dû résoudre un problème d'ordonnancement. Des jobs à distribuer vers des workers. "Facile", me suis-je dit, "une queue, des consommateurs, un SELECT, et on passe à autre chose."

Sauf que les workers ne sont pas interchangeables. Certains ne savent traiter que du PDF, d'autres que de l'Excel, et quelques-uns sont polyvalents. Et il y a des utilisateurs qui attendent une réponse en temps réel pendant que des jobs de batch s'accumulent dans la queue. Et plusieurs instances de l'ordonnanceur (nommé scheduler dans la suite du texte) tournent en parallèle.

Et puis il y a le petit dernier. Un job de faible priorité, sur une ressource rare, car il n'y a qu'un seul worker compatible. Les jobs plus prioritaires passent devant, encore et encore. Ça fait trois heures qu'il attend. Il ne s'est jamais lancé. Et c'est là qu'un worker crash.

Le "facile" a duré environ 15 minutes. Ensuite, ça a été trois pathologies classiques de l'ordonnancement, un peu de maths, et quelques pièges de concurrence distribuée. Voici le résultat.

Le problème : ce n'est pas une simple queue

Imaginez un système où des jobs de nature différente doivent être exécutés par des workers spécialisés. Chaque worker ne peut traiter que certains types de jobs :

Contrairement à une queue classique FIFO où le premier arrivé est le premier servi, ici le scheduler doit résoudre un problème d'affectation sous contraintes :

Affinité job/worker : un job de type X ne peut s'exécuter que sur un worker qui supporte X
Ressources limitées : nombre fixe de slots d'exécution
Distribution : plusieurs instances du scheduler tournent en parallèle
Deux modes de consommation : des jobs en queue (le scheduler choisit quand les exécuter) et des requêtes on-demand (un utilisateur attend activement une réponse)

C'est la combinaison de ces contraintes qui rend le problème intéressant. Prises individuellement, elles sont simples. Ensemble, elles créent trois pathologies qu'il faut traiter simultanément.

Trois pathologies à comprendre

1. La famine (starvation)

Un job dont le type est supporté par peu de workers risque d'attendre indéfiniment si des jobs "populaires" arrivent en continu :

C'est un problème classique en ordonnancement. Si on choisit toujours le job le plus prioritaire statiquement, un job de faible priorité sur un worker rare peut attendre indéfiniment. En théorie de l'ordonnancement, c'est le problème du starvation : l'absence de garantie de progression.

2. Le gaspillage de polyvalence

Un worker polyvalent (supportant plusieurs types) ne devrait pas prendre un job qu'un worker spécialisé pourrait faire. Si le worker polyvalent prend un job de type A alors qu'un worker spécialisé en A est libre, le worker polyvalent est gaspillé. Quand un job de type C arrive (que seul le polyvalent peut traiter), personne ne peut le prendre.

Mauvais choix:
  Worker polyvalent [A,B,C] prend un job de type A
  → Worker spécialisé [A] reste inactif
  → Job de type C arrive, personne ne peut le traiter

Bon choix:
  Worker spécialisé [A] prend le job de type A
  → Worker polyvalent [A,B,C] reste disponible pour B ou C

C'est l'équivalent d'envoyer le chirurgien cardiaque poser un pansement alors qu'un infirmier est libre. Le chirurgien peut techniquement le faire, mais c'est un gaspillage de compétence rare.

3. L'urgence utilisateur vs l'équité

Un utilisateur qui fait une requête on-demand attend activement. Il doit passer devant les jobs queue, mais pas de manière absolue : sinon un flux continu de requêtes on-demand créerait de la famine sur les jobs queue, et on retomberait sur le problème n°1.

Architecture : l'Actor Model

Avant d'attaquer le scoring, un mot sur l'architecture de synchronisation. Le scheduler maintient un état mutable partagé : le pool de slots libres, les index par type, les compteurs. Comment synchroniser tout ça ?

La réponse classique serait les mutex. Mais quiconque a passé des nuits à traquer un deadlock sait que les mutex sont une source intarissable de bugs subtils. Ici, le choix est un Actor Model : une goroutine unique possède tout l'état mutable, et les autres composants communiquent avec elle via des channels.

La goroutine unique écoute sur plusieurs channels : enregistrement de worker, désenregistrement (stop ou crash), libération de slot, requête on-demand, notification de nouveau job en base, et heartbeat périodique. Tout passe par un select Go.

Zéro mutex dans notre code. Les channels en sont bourrés en interne, quiconque a lu le runtime Go le sait. Mais la différence est dans les garanties : avec des mutex explicites, c'est le développeur qui doit verrouiller, déverrouiller, et ne pas se planter dans l'ordre. Le compilateur ne vérifie rien. Avec des channels et un select, le compilateur cadre l'usage. L'état mutable est confiné dans une seule goroutine, les messages arrivent séquentiellement, et toute une classe de bugs (double-lock, inversion de priorité, verrou oublié) disparaît par construction.

L'avantage est que tout le raisonnement sur l'état est séquentiel au sein de cette goroutine. Pas de race condition possible sur les structures internes. La complexité de la concurrence est confinée aux channels, qui sont thread-safe par construction.

Le pool de slots : index inversé par type

Le cœur de la structure de données est le pool de slots. La question fondamentale à laquelle le scheduler doit répondre en permanence est : "pour un type de job donné, quels slots sont disponibles ?". Si on parcourt tous les slots à chaque décision, on obtient une complexité O(s) où s est le nombre total de slots. C'est acceptable pour 10 slots, beaucoup moins pour 1000.

La solution est un index inversé par type. Chaque type de job est identifié par un entier, et chaque slot également. Comme montré dans l'article sur les maps Go, les maps sont très performantes en Go, surtout avec des clés entières. C'est exactement notre cas.

On maintient trois maps : une pour tous les slots indexés par leur ID, une pour les slots libres indexés par type de job, et une pour le compteur de capacité par type.

C'est le même principe qu'un index dans une base de données. Au lieu de scanner la table, on maintient une structure auxiliaire qui permet de répondre en $O(1)$ à la question "y a-t-il des slots pour le type X ?" et en O(n) à "donne-moi le meilleur slot pour le type X" où n est le nombre de slots compatibles (pas le nombre total).

Le coût est la maintenance de l'index : à chaque passage dans la boucle de scheduling, on modifie l'index (acquisition d'un slot, libération, mise à jour des compteurs). Mais grâce aux maps, ajouter, supprimer et mettre à jour l'accounting est en O(1). Le surcoût est négligeable comparé au gain sur les lookups.

Le système de scoring

Passons au cœur du sujet : comment choisir le prochain job à exécuter parmi tous les candidats éligibles ?

D'où viennent les candidats ?

Les jobs candidats arrivent de deux sources. Les requêtes on-demand sont transmises directement au scheduler via un channel et sont déjà en mémoire locale. Les jobs queue sont récupérés depuis la base de données par une requête qui ne ramène que les jobs dont le type correspond à un slot libre. On se limite à quelques résultats : le nombre de jobs demandés à la base correspond au nombre de slots disponibles × 2. Ça donne de la marge pour les claims ratés (on y vient) sans charger inutilement des jobs qu'on ne pourra pas exécuter. Le scoring s'applique ensuite sur cette liste combinée.

Pour prendre une décision de distribution, le scheduler dispose donc de :

La liste des jobs éligibles en attente : pour chacun, son type, sa priorité métier (un entier de 0 à 10), sa date de création, et s'il est en mode queue ou on-demand
La liste des slots libres : pour chacun, les types de jobs qu'il supporte

C'est à partir de ces données qu'on calcule un score pour chaque job. Le job avec le score le plus élevé sera exécuté en premier.

La formule

Pour chaque job candidat, on calcule un score :

\begin{aligned} \text{score}(job) =\ & \text{base\_priority} \times 1024 \\ +\ & \text{age} \times 16 \\ +\ & \text{rarity\_bonus} \\ +\ & \text{on\_demand\_bonus} \end{aligned}

Où :

$\text{base\_priority}$ : priorité métier du job, entier de 0 à 10 (10 étant le plus prioritaire)
$\text{age}$ : temps d'attente du job en secondes
$\text{rarity\_bonus}$ : bonus inversement proportionnel au nombre de slots compatibles
$\text{on\_demand\_bonus}$ : bonus appliqué uniquement aux jobs en mode on-demand

C'est une combinaison linéaire pondérée de quatre facteurs : chacun capture un aspect différent de l'urgence du job. Les constantes sont choisies en puissances de 2 pour que le compilateur les optimise en décalages de bits. Détaillons-les.

Composante 1 : Priorité de base (0-10k points)

C'est la priorité métier assignée au job. Simple multiplication :

\text{score} \mathrel{+}= \text{priority} \times 1024

Le facteur 1024 sert à donner de l'espace aux autres composantes. Un job de priorité 5 commence avec 5120 points, un job de priorité 0 avec 0 points. Cet écart devra être comblé par les autres composantes pour qu'un job de faible priorité passe devant un job de haute priorité. C'est volontaire : la priorité métier doit peser lourd.

Composante 2 : Anti-starvation par vieillissement (16 points/seconde)

C'est la composante qui garantit qu'aucun job n'attendra indéfiniment. Le score d'un job croît linéairement avec son temps d'attente :

\text{score} \mathrel{+}= \text{age} \times 16

Propriété fondamentale : deux droites de pentes identiques mais d'ordonnées à l'origine différentes ne se croisent jamais. Mais ici, toutes les composantes "âge" ont la même pente. C'est le score initial (priorité de base) qui diffère. Donc deux jobs de priorités différentes finiront toujours par se croiser si on ajoute un facteur discriminant (le bonus on-demand a une pente différente, on y vient).

On peut calculer exactement quand un job de faible priorité rattrapera un job de haute priorité. L'écart de score initial entre deux jobs est leur différence de priorité × 1024. Le vieillissement comble cet écart à raison de 16 points par seconde :

\text{Temps de croisement} = \frac{\text{écart de priorité} \times 1024}{16} = \text{écart de priorité} \times 64 \text{ secondes}

Concrètement : un job de priorité 0 rattrapera un job de priorité 5 après 320 secondes, soit environ 5 minutes. C'est un paramètre métier : si 5 minutes est trop long, on augmente le coefficient de vieillissement. Si c'est trop court, on le diminue. Le rapport $\frac{1024}{16} = 64$ secondes par unité de priorité est le bouton de réglage.

Composante 3 : Bonus de rareté

Un job dont peu de slots sont compatibles reçoit un bonus. C'est une fonction hyperbolique (inverse) :

\text{rarity\_bonus} = \frac{500}{\text{compatible\_slots}}

Où :

$\text{compatible\_slots}$ : nombre de slots libres pouvant exécuter ce job

Slots compatibles	Bonus	Décroissance
1	500	n/a
2	250	-50%
4	125	-75%
8	62	-88%

C'est une fonction à utilité marginale décroissante : la première option disponible a énormément de valeur, les suivantes de moins en moins. Un job qui n'a qu'un seul slot compatible doit le saisir. Un job avec 10 options peut se permettre d'attendre.

Le choix de l'hyperbolique n'est pas anodin. On aurait pu utiliser une exponentielle décroissante ou une fonction logarithmique. L'hyperbolique a l'avantage d'être simple à calculer (une division), d'avoir un effet très fort pour $n=1$ (500 points, soit une demi-unité de priorité de base), et de converger rapidement vers zéro. Ici, pas d'optimisation en puissance de 2 possible : c'est le diviseur qu'il faudrait en $2^x$ pour que le compilateur remplace par un shift, et le diviseur est une variable runtime.

En pratique : pour $n \geq 4$ , le bonus devient négligeable (125 points = 8 secondes de vieillissement). La rareté ne joue un rôle significatif que pour les jobs vraiment contraints.

Composante 4 : Bonus on-demand

Un utilisateur attend activement → forte priorité, mais pas absolue :

\text{score} \mathrel{+}= 4096 \mathrel{+} \text{age} \times 32

Le bonus initial de 4096 points est l'équivalent de 4 unités de priorité de base. Un job on-demand passe devant presque tout le monde immédiatement. Mais un job queue de haute priorité qui attend depuis longtemps peut quand même passer devant.

Le vieillissement accéléré (pente totale de 48/s : 16 de base + 32 de bonus) assure que les jobs on-demand qui attendent sont traités de plus en plus rapidement par rapport aux jobs queue.

Visualisation : les droites de score

On lit directement sur ce graphique que les deux droites se croisent à 256 secondes, soit environ 4 minutes. Un job queue de priorité 0 qui attend depuis plus de 4 minutes passera devant un job on-demand fraîchement arrivé. C'est voulu : la patience finit par être récompensée, même face à l'urgence.

Sélection du slot : préférer les spécialistes

Une fois le meilleur job choisi par le scoring, il reste à décider sur quel slot l'exécuter. C'est le problème du matching slot/job, et il est plus subtil qu'il n'y paraît.

L'objectif est de préserver les slots polyvalents pour les jobs rares. L'algorithme est simple : parmi les slots compatibles avec le type du job, on parcourt la liste et on garde celui qui supporte le moins de types différents.

Exemple concret :

Job de type "PDF" arrive
Slots disponibles:
  - Slot A: [PDF]               ← 1 type  → CHOISI
  - Slot B: [PDF, Excel]        ← 2 types
  - Slot C: [PDF, Excel, Index] ← 3 types

Résultat: Slot A est utilisé, B et C restent disponibles pour Excel/Index

C'est une heuristique gloutonne. Elle n'est pas optimale au sens global (on pourrait imaginer des cas où garder le spécialiste libre pour un futur job serait meilleur), mais elle est O(n) et donne de bons résultats en pratique. L'optimalité globale nécessiterait de prédire les futurs jobs, ce qui est un problème bien plus complexe.

Concurrence distribuée : le double-claim

Plusieurs instances du scheduler peuvent tourner en parallèle. Deux pourraient vouloir le même job. C'est le problème classique du double-claim.

Solution : claim optimiste

La solution est le claim optimiste. Plutôt que de poser un verrou avant de lire les jobs candidats (coûteux et source de contention), on laisse chaque instance travailler indépendamment et on gère les conflits au moment du claim :

UPDATE jobs
SET status = 'running', worker_id = $1
WHERE id = $2 AND status = 'pending'
RETURNING id

La clause WHERE status = 'pending' est la clé. Un UPDATE en SQL est une opération atomique : si deux schedulers tentent de claimer le même job, le premier modifie le status en 'running' et la condition WHERE status = 'pending' du second ne matche plus. Le perdant voit 0 lignes affectées. Pas d'erreur, pas de deadlock, juste un résultat vide.

Algorithme de retry

Quand un claim échoue, on passe au candidat suivant dans la liste triée par score. Si plus de 5 claims échouent d'affilée (valeur à ajuster selon la contention observée), c'est que notre liste est périmée : on refetch les candidats depuis la base et on recommence.

Gestion des pannes : le crash d'un worker

Un worker peut crasher à tout moment. Il faut gérer deux cas : les slots qui étaient libres (facile, on les retire) et les slots qui exécutaient un job (plus délicat).

Entre le moment du crash et sa détection par le scheduler, un FD invalide peut être utilisé. Ce n'est pas le scheduler qui protège contre ça, c'est le kernel : écrire sur un FD fermé retourne EPIPE ou EBADF, le job échoue proprement.

Edge case assumé : si deux workers crashent et redémarrent dans l'ordre inverse, le kernel peut redistribuer les file descriptors de manière croisée. Le scheduler, pas encore notifié des crashs, envoie alors un job à un worker qui n'est potentiellement pas fait pour. Trois issues possibles : le worker sait le faire et c'est tant mieux, il ne sait pas et le job échoue, ou pire il le fait mal. Ce cas est accepté : la probabilité est faible et le coût d'une protection (handshake synchrone à chaque écriture) ne justifie pas la complexité.

Quand le scheduler détecte le crash, il fait un unregister : on retire tous les slots du worker de l'index, qu'ils soient libres ou occupés.

Pour les slots occupés, le job en cours tentera d'écrire sur un file descriptor invalide et obtiendra un EPIPE (broken pipe), ou de lire et obtiendra 0. Dans les deux cas, le job sera marqué comme failed, et le release trouvera que le slot n'existe plus et sera ignoré silencieusement. L'absence du slot dans la map principale sert de garde-fou : toute opération sur un slot inexistant est un `no-op.

Quand le worker redémarre, il s'enregistre avec de nouveaux slots et de nouveaux file descriptors. L'état est propre.

Complexité algorithmique

Récapitulons les complexités :

Opération	Complexité
Vérifier la capacité par type	$O(1)$ - lookup dans `capacity`
Acquérir un slot	$O(s)$ - s = slots compatibles avec le type
Calculer le score d'un job	$O(1)$ - quelques opérations arithmétiques
Trier les candidats	$O(n \log n)$ - tri standard Go, n = jobs éligibles

La complexité totale d'un cycle de scheduling est dominée par le tri : $O(n \log n)$ . En pratique, n est borné par le nombre de slots disponibles × 2 (la limite du fetch). Pour des valeurs raisonnables (quelques dizaines de jobs), c'est négligeable. Il faut relativiser : pendant un seul aller-retour réseau vers la base de données, on aurait le temps de trier un million d'entrées. C'est toutefois toujours bien d'économiser du CPU, surtout quand ça ne coûte rien à la lisibilité.

Résumé des garanties

Le système combine six mécanismes qui adressent chacun une pathologie spécifique :

Index inversé par type : accès O(1) aux slots compatibles, pas de scan linéaire
Scoring multi-critères : combinaison linéaire pondérée, paramétrable par les coefficients
Vieillissement linéaire : garantie mathématique qu'aucun job n'attend indéfiniment (anti-famine)
Bonus de rareté hyperbolique : les jobs contraints ne sont pas défavorisés
Sélection du slot le plus spécialisé : préservation de la polyvalence
Claim optimiste SQL : concurrence distribuée sans verrou distribué

Le tout tourne dans un Actor Model single-writer qui élimine les race conditions sur l'état interne.

Est-ce optimal ? Non. Un scheduler omniscient qui connaîtrait les futurs jobs pourrait faire mieux. Mais entre l'optimal théorique et le praticable en production, il y a un gouffre que les heuristiques bien calibrées comblent très correctement.