Asynchronisme, files d’attente et back pressure

Les files d’attente transforment les pics en arriérés

La charge n’arrive jamais de façon régulière. Les commandes du déjeuner se concentrent à 12:30, les acheteurs de billets appuient tous sur le bouton à 10:00:00, et un traitement par lots déverse un million d’événements à minuit. Un service synchrone doit soit disposer de la capacité nécessaire pour le pic le plus élevé, soit défaillir pendant ce pic. Placer une file d’attente entre le producteur du travail et le service qui l’effectue change le calcul : pendant un pic, le travail excédentaire attend dans la file, et les consommateurs le traitent à leur propre rythme régulier, en rattrapant leur retard une fois le pic passé. Le catalogue de patrons cloud de Microsoft appelle cela le nivellement de charge par file d’attente (queue-based load levelling). La section 2.4 a montré pourquoi des files se forment chaque fois que les arrivées se concentrent ; cette section porte sur leur utilisation délibérée.

L’avantage est réel : les consommateurs peuvent être dimensionnés pour la moyenne plutôt que pour le pic, un consommateur lent ou en cours de redémarrage ne perd pas de travail, et le producteur n’est plus couplé temporellement au consommateur (section 6.5). Le prix à payer est que le travail est désormais effectué plus tard. Une file transforme un pic en arriéré, et un arriéré n’est rien d’autre qu’un délai que subira chaque élément placé derrière lui. C’est acceptable pour envoyer des e-mails de confirmation ou mettre à jour un index de recherche, discutable pour affecter un livreur à une commande, et inacceptable pour un paiement dont le client attend la confirmation. La première question de conception pour toute file est donc : combien de temps un élément peut-il attendre, et qu’advient-il des éléments qui attendraient plus longtemps ?

Files de travail et consommateurs concurrents

L’usage le plus courant est une file de travail avec des consommateurs concurrents (competing consumers) : plusieurs workers identiques lisent une même file, chaque message ne va qu’à l’un d’eux, et le débit augmente quand on ajoute des workers. C’est l’axe X du cube de scalabilité appliqué au travail d’arrière-plan, et il passe naturellement à l’échelle sur le bon signal : l’arriéré par worker, ou l’âge du plus ancien message.

Les mécanismes comptent pour la justesse. Un worker prend un message, le traite, puis en accuse réception ; si le worker plante avant, le courtier rend le message de nouveau visible après un délai (SQS l’appelle le délai de visibilité, ou visibility timeout) et un autre worker le traite. La livraison se fait donc au moins une fois, et les consommateurs doivent être idempotents (section 6.4). Un délai de visibilité plus court que le temps de traitement réel fait traiter le même message deux fois en parallèle. L’ordre est perdu dès qu’il y a plus d’un consommateur, sauf si les messages sont partitionnés par clé, auquel cas le nombre de partitions plafonne le nombre de consommateurs utiles. Enfin, le préchargement (prefetch : un worker qui prend plusieurs messages à la fois pour économiser des allers-retours) doit rester faible pour les tâches lentes, sinon un worker accapare des messages que des workers inactifs auraient pu traiter.

Une file d’attente ne crée pas de capacité

Une file absorbe un excès temporaire ; elle ne peut pas absorber un excès permanent. Si le travail arrive plus vite qu’il n’est accompli pendant assez longtemps, l’arriéré croît sans limite, et la loi de Little (L = λ × W) indique que le temps d’attente croît avec lui. Une file en mémoire non bornée finit par épuiser la mémoire et faire planter le processus, en perdant tout ce qu’elle contient ; une file durable non bornée remplit son disque ou conserve du travail pendant des heures alors que plus personne ne s’en soucie. Pire, la file masque le problème : les producteurs reçoivent des accusés de réception rapides, les taux d’erreur restent à zéro, et le seul symptôme est que les résultats arrivent de plus en plus tard. Des ingénieurs d’Amazon décrivent de tels arriérés comme potentiellement insurmontables, car un service qui prend assez de retard peut consacrer toute sa capacité à traiter du travail que ses clients ont abandonné depuis longtemps.

Deux pratiques en découlent. D’abord, mesurez l’âge du plus ancien message en plus de la longueur de la file : l’âge est ce que vivent les utilisateurs, et il réagit immédiatement quand les consommateurs se bloquent. Ensuite, donnez à chaque file une borne déduite du temps d’attente que vous jugez acceptable, à l’aide de la loi de Little, et décidez à l’avance de ce qui se passe quand la borne est atteinte. Cette décision fait l’objet des trois parties suivantes de cette section.

Back pressure : faire ralentir les producteurs

Le back pressure (contre-pression) désigne tout mécanisme par lequel une étape aval plus lente fait ralentir une étape amont plus rapide, au lieu de laisser le travail s’accumuler entre elles. Le terme vient des fluides dans les canalisations, et l’idée a déjà été rencontrée avec les tubes et filtres (section 5.4). Il est intégré à de nombreuses couches de la pile que vous utilisez déjà. Le contrôle de flux de TCP arrête un émetteur quand le tampon du récepteur est plein. Une file bloquante bornée fait attendre le put du producteur jusqu’à ce qu’il y ait de la place. Les consommateurs en mode pull, comme dans Kafka, ne prennent du travail que lorsqu’ils sont prêts, si bien que c’est le journal du courtier, et non la mémoire du consommateur, qui contient l’arriéré, et un producteur Kafka se bloque ou échoue quand son propre tampon d’envoi est plein. La spécification Reactive Streams permet à un abonné de demander un nombre précis d’éléments, de sorte qu’un flux ne livre jamais plus que ce que l’abonné a demandé.

Le back pressure fonctionne bien à l’intérieur d’un processus ou le long d’un pipeline. À travers une frontière requête-réponse avec des utilisateurs humains, il se traduit généralement par un rejet : un service HTTP surchargé ne peut pas faire patienter poliment un téléphone, il répond donc 429 Too Many Requests ou 503 Service Unavailable, idéalement avec un en-tête Retry-After, et compte sur le client pour ralentir. Quand une file bornée est pleine, il n’y a que trois choix : bloquer le producteur, rejeter le nouveau travail, ou abandonner quelque chose de déjà accepté. Chacun est le bon quelque part ; l’erreur est de ne pas choisir.

Délestage de charge et priorisation

Un serveur soumis à plus de charge qu’il ne peut en traiter fait pire que servir sa capacité et refuser le reste. Il accepte tout, chaque requête attend dans ses files internes, les temps de réponse dépassent les délais d’expiration des clients, et il finit par consacrer toute sa capacité à des requêtes dont les clients ont déjà abandonné. Le débit reste élevé tandis que le goodput (débit utile), le rythme des requêtes traitées à temps pour être utiles, s’effondre vers zéro. Le délestage de charge (load shedding) l’empêche en rejetant délibérément certaines requêtes pour que les autres réussissent.

Un bon délestage a trois propriétés. Il est précoce et peu coûteux : rejeter une requête doit coûter bien moins cher que la servir, il a donc lieu à l’entrée, avant tout travail lourd d’authentification ou de base de données, à partir d’un signal peu coûteux comme le nombre de requêtes en cours ou l’âge de la file. Il est priorisé : le livre SRE de Google décrit l’étiquetage de chaque requête avec une criticité (de CRITICAL_PLUS à SHEDDABLE), afin que le trafic de traitement par lots et de préchargement soit abandonné avant le trafic destiné aux utilisateurs. Dans la plateforme de livraison de repas, les validations de commande et les mises à jour de position des livreurs passent avant les recommandations, qui passent elles-mêmes avant les événements analytiques. Enfin, il est conscient du temps : une requête qui a déjà attendu plus longtemps que le délai d’expiration de son appelant doit être abandonnée plutôt que traitée. Les ingénieurs de Facebook ont décrit deux raffinements : une file à délai contrôlé qui n’autorise qu’une courte attente quand une file ne s’est pas vidée récemment, et le passage au mode dernier entré, premier sorti sous charge, afin que les requêtes les plus récentes, dont les utilisateurs attendent encore, soient servies en premier.

Une étape supplémentaire consiste à adapter la limite elle-même. Des limites de concurrence fixes sont soit trop basses un bon jour, soit trop hautes un mauvais jour ; les limiteurs de concurrence adaptatifs augmentent le nombre autorisé de requêtes en cours tant que la latence reste basse et le réduisent quand elle augmente, en empruntant l’idée au contrôle de congestion de TCP. Tout à l’entrée d’un système, le contrôle d’admission peut prendre la forme d’une salle d’attente virtuelle, comme pour l’ouverture de billetterie ci-dessus : les utilisateurs sont retenus dans une file à la périphérie et admis au rythme que le cœur du système peut servir, ce qui revient à du délestage de charge présenté comme de l’équité.

Algorithmes de limitation de débit

La limitation de débit (rate limiting) restreint la quantité de travail qu’un client, une clé d’API, un locataire (tenant) ou une adresse IP donnés peuvent soumettre sur une période. Son objectif diffère de celui du délestage de charge : le délestage protège le serveur contre une surcharge totale, quelle qu’en soit la cause, tandis que la limitation de débit partage équitablement la capacité et protège contre tout client isolé, qu’il soit bogué ou malveillant. Les deux répondent de la même façon, généralement par un HTTP 429. Quatre algorithmes dominent.

Le token bucket (seau à jetons) mérite qu’on s’y attarde, car c’est le choix par défaut habituel. Le seau contient au plus b jetons et en gagne r par seconde. Chaque requête prend un jeton ; s’il n’en reste aucun, elle est rejetée (ou, dans la variante de mise en forme, retardée). Un client resté silencieux peut donc envoyer d’un coup une rafale de b requêtes, ce qui convient aux clients réels, comme une application mobile qui ouvre un écran, alors que sur toute période plus longue il ne peut pas dépasser r en moyenne. Le leaky bucket (seau percé) en est l’image inversée : il lisse la sortie à un rythme constant, ce qui est utile pour protéger un système aval qui ne peut accepter aucune rafale.

import math, time

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate = rate              # tokens added per second
        self.capacity = capacity      # largest burst allowed
        self.tokens = capacity        # start full
        self.updated = time.monotonic()

    def allow(self, cost=1):
        now = time.monotonic()
        elapsed = now - self.updated
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.updated = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True, 0
        wait = (cost - self.tokens) / self.rate   # seconds until enough tokens
        return False, max(1, math.ceil(wait))      # for the Retry-After header

bucket = TokenBucket(rate=5, capacity=20)        # one bucket per API key
allowed, retry_after = bucket.allow()

HTTP 429, Retry-After et où appliquer les limites

HTTP dispose de signaux standard pour les deux situations. 429 Too Many Requests, défini dans la RFC 6585 (2012), indique à un client qu’il a envoyé trop de requêtes en un temps donné. 503 Service Unavailable indique que le serveur dans son ensemble est temporairement surchargé ou en maintenance. L’un comme l’autre peut porter un en-tête Retry-After (RFC 9110), qui donne un nombre de secondes ou une date après laquelle il est judicieux de réessayer. De nombreuses API renvoient aussi des en-têtes qui annoncent la limite, le quota restant et l’heure de remise à zéro, traditionnellement X-RateLimit-* ; un projet de l’IETF est en train de normaliser les champs RateLimit et RateLimit-Policy. Les clients bien conçus respectent Retry-After, ajoutent du jitter pour que les clients rejetés ne reviennent pas tous au même instant, et voient dans des 429 répétés une raison de ralentir plutôt que de réessayer plus fort (section 9.4).

Les limites peuvent être appliquées à plusieurs couches, et les systèmes matures en utilisent plus d’une : à la périphérie ou dans l’API gateway, par adresse IP et par clé d’API, pour arrêter les abus et les clients incontrôlés avant qu’ils ne coûtent quoi que ce soit ; par locataire, pour qu’un gros client ne puisse pas affamer les autres ; et à l’intérieur de chaque service, pour protéger sa propre capacité et ses dépendances. Une limite globale sur de nombreuses instances de gateway nécessite un état partagé, généralement des compteurs atomiques dans Redis, ce qui ajoute un appel réseau par requête ; un compromis courant consiste à donner à chacune des N instances une limite locale d’environ 1 ÷ N du total et à accepter une certaine imprécision. Les limites doivent être fixées à partir de la capacité mesurée et publiées, pour que les partenaires puissent en tenir compte dans leur conception, et le nombre de rejets doit être surveillé, car une hausse soudaine signale soit une attaque, soit un bug chez un client, soit une limite qui ne correspond plus à la réalité.

Files de lettres mortes

Certains messages échouent à chaque fois : un contenu mal formé, une commande pour un restaurant qui n’existe plus, un bug déclenché par une entrée particulière. Réessayé indéfiniment, un tel message empoisonné bloque une partition ou gaspille un worker pour toujours. Une file de lettres mortes (dead-letter queue, présentée à la section 6.4) reçoit les messages qui ont échoué un nombre défini de fois (SQS appelle cela le nombre maximal de réceptions d’une politique de redrive), pour que le reste du travail puisse continuer.

Une file de lettres mortes est un outil pour les défauts, pas pour la surcharge : si des messages y atterrissent parce que les consommateurs sont trop lents, la solution est la capacité ou le back pressure, pas une seconde file. Chaque message dans une DLQ signifie que quelque chose que le métier attendait ne s’est pas produit ; la DLQ a donc besoin d’un responsable, d’une alerte sur sa profondeur ou son âge, d’outils pour inspecter les messages avec leur erreur et leur nombre de tentatives, et d’un moyen de les rejouer une fois la cause corrigée. Décidez à l’avance de ce que signifie un rejeu tardif pour l’ordre des messages et pour les messages dont le moment métier est passé : un remboursement peut être rejoué avec un jour de retard, une affectation de livreur ne le peut pas.