Ordonnancement de la file d'attente


Objectif de ce document

Ceci est le début de la documentation de l'algorithme du gestionnaire des files d'attente de Patrik Rak. Depuis longtemps, ce code était disponible sous le nom "nqmgr(8)" (nouveau gestionnaire des files d'attente), comme module optionnel. Depuis Postfix 2.1, il est le gestionnaire des files d'attente par défaut, qui est toujours appelé "qmgr(8)". L'ancien gestionnaire des files d'attente restera disponible un certain temps sous le nom "oqmgr(8)".

Pourquoi avoir remplacé l'ancien gestionnaire des files d'attente

L'ancien ordonnaceur avait des limitations sévères dues à de mauvais choix dans sa conception.

  1. Selection Round-robin par destination pour le courrier délivré via le même transporteur de messages. La stratégie round-robin avait été choisie avec l'intention d'éviter à un simple site (destination) d'utiliser trop de ressources de livraison de messages. Toutefois, cette strategie pénalise le courrier entrant sur des passerelles bi-directionelles. Ces destinations étant sélectionnées seulement 1 fois par nombre de destinations, même s'il elles ont plus de courrier que les autres destinations, et ainsi le courrier peut prendre du retard.

    Victor Duchovni a trouvé un contournement : utiliser différents transporteurs de messages, et ainsi éviter le problème. L'ordonnaceur de Patrik Rak résout ce problème en utilisant une sélection FIFO (premier entré - premier sorti).

  2. Une seconde limitation de l'ancien ordonnaceur était que la livraison des messages en bloc pouvait bloquer les autres livraisons, causant de fort retards. L'ordonnanceur de Patrik Rak's autorise les messages avec peu de destinataires de dépasser les messages en bloc de manière élégante.

Comment fonctionne le gestionnaire des files d'attente

Le texte suivant a été écrit par Patrik Rak et doit être lu en parallèle de la page de manuel postconf(5) qui décrit chaque paramètre de configuration en détail.

Du point de vue de l'utilisateur, oqmgr(8) et qmgr(8) sont les mêmes, si ce n'est que le message suivant est choisit lorsque l'agent de livraison devient disponible. Vous savez déjà que oqmgr(8) utilise un round-robin par destination alors que qmgr(8) utilise un simple FIFO, à l'exception de certaines priorités magiques. La page de manuel postconf(5) documente toutes les ficelles que l'utilisateur peut utiliser pour contrôler cette préemption magique - il n'y a que les simples conditions décrites ci-dessous pour la préemption.

Comme une documentation niveau programmeur, elle a été extraite de tous les messages que nous avons échangé avec Wietse [Arg ! J'espérais que Patrik fasse le travail pour moi -- Wietse] mais je pense que peu de choses manquent de ce que nous avons mentionné dans nos conversations.

Toutefois, même su point de vue du programmeur, il n'y a rien à ajouter à l'idée de l'ordonnancement des messages elle-même. Quelques éléments peuvent la faire paraître plus compliquée qu'elle n'est, l'algorithme est le même que celui perçu par les utilisateurs. En résumé, les différences entre les points de vue utilisateur et programmeur sont :

  1. Simplification des termes pour les utilisateurs : l'utilisateur n'a connaissance que des messages et des destinataires. Le programme lui-même travaille avec des jobs (un message est coupé en plusieurs jobs, un par transporteur utilisé pour livrer le message) et les entrées de la file d'attente (chaque entrée peut regrouper plusieurs destinataires pour la même destination). Ensuite il y a la structure introduite par qmgr(8) qui est simplement analogue aux jobs de la structure de la file d'attente.

  2. Traitement des limites de simultanéïté : l'implémentation actuelle est compliquée par le fait que les messages (resp. jobs) peuvent ne pas être livrés exactement dans le même ordre en raison des limites de concurrence. Il est nécessaire d'ignorer certains jobs "bloquant" lorsque la limite de concurrence est atteinte et de les relancer lorsque les limites le permette.

  3. Traitement des limites de ressources : l'implémentation actuelle est compliquée par le fait que tous les destinataires du corps peuvent ne pas être traités en même temps. Ainsi chaque message a des destinataires dans le corps et d'autres pouvant résulter de fichiers. Ceci signifie que a) l'algorithme préemptif doit travailler avec une estimation du nombre de destinataires au lieu du nombre exact, b) il y a du code supplémentaire qui nécessite de manipuler les groupes de destinataires par transporteur qui peuvent être lus dans le corps au même moment, et c) il y a du code supplémentaire qui nécessite d'être apte à lire les destinataires dans le corps en arrière-plan et qui est déclenché au moment approprié.

  4. Faire les choses efficacement : toutes les choses importantes sont faites dans le temps le plus court possible (soit directement soit après pour les traitements complexes), mais choisir le job meilleur candidat pour la préemption requiert une recherche linéaire dans tous les jobs du transporteur (le pire cas théorique - la réalité est meilleure). Comme ceci est fait chaque fois que l'entrée suivante dans la file doit être livré, il semble raisonnable d'ajouter un cahce qui minimise les délais. La maintenance de ce cache obscurcit les choses.

Les points 2 et 3 sont ceux qui rendent (l'apparence de) l'implémentation compliquée, mais j'espére que la compréhension de l'algorithme d'ordonnancement lui-même (qui demeure le travail réel) reste aisée.

Note du traducteur : je ne suis pas très fier de la traduction de cette page, une petite aide serait la bienvenue.

Valid HTML 4.01! traduction par Xavier Guimard - Retour au menu