Chaque appel récursif était en position terminale

Nos flux d’automatisation sont des graphes. Un déclencheur s’active, le parcours visite des nœuds, chaque nœud fait quelque chose, et à un moment le parcours n’a plus de fil à suivre et l’exécution est terminée. Jusqu’à cette semaine, ce parcours était une fonction récursive qui s’appelait elle-même une fois par fil sortant, et cela convenait tant qu’une exécution se terminait à l’intérieur de la requête qui l’avait lancée.

Un nœud d’approbation brise complètement cette hypothèse. L’exécution doit s’arrêter, être consignée, et reprendre demain lorsque quelqu’un cliquera sur un bouton. Une demi-pile d’appels JavaScript n’est pas une chose que l’on sérialise dans une colonne de base de données.

Le parcours est donc devenu une machine à pile. Ce qui est intéressant n’est pas qu’il le soit devenu ; c’est que la réécriture est démontrablement le même parcours, et non un nouveau parcours dont on espère qu’il se comporte pareil.

Pourquoi la réécriture est exacte et non approximative

Chaque appel récursif de l’ancien parcours se trouvait en position terminale. La forme était littéralement await follow(node, port); return;. Rien ne se produisait jamais après le retour de l’appel : pas d’accumulation, pas de nettoyage, pas de seconde moitié de fonction attendant que son enfant ait fini.

Cette seule propriété est ce qui rend la conversion mécanique. Un parcours en profondeur dont la récursion est en position terminale est par construction identique à une pile explicite sur laquelle on empile les cibles dans l’ordre inverse. Il n’y a là aucune décision de conception à rater, aucune question sur l’ordre de visite des nœuds frères, aucun risque qu’un nœud autrefois visité après son sous-arbre le soit désormais avant lui.

La conséquence qui nous importait est que l’ordre de visite est inchangé. Les tests de parcours existants, quarante-trois, n’ont pas été touchés et sont restés verts. C’est tout l’argument : ces tests décrivent l’ancien comportement, ils ont été écrits avant que quiconque sache que cette réécriture arrivait, et ils n’ont pas eu besoin d’une seule modification.

Si la récursion n’avait pas été en position terminale, cela aurait été une réécriture accompagnée d’un argument de compatibilité, et les arguments de compatibilité sont le genre de chose que l’on croit jusqu’au jour où le flux d’un client fait quelque chose d’inattendu un mardi.

Ce que la pile apporte et que la récursion ne pouvait pas

Deux choses, et toutes les deux sont impossibles avec une pile d’appels.

La première est l’interruption. L’état du parcours est le parcours entier exprimé en JSON : la pile, les nœuds visités, les variables accumulées, le compteur et les boucles ouvertes. Il part dans une colonne jsonb de la ligne d’attente et en ressort inchangé. Une exécution en pause est une ligne et non un processus suspendu, si bien qu’un déploiement, un redémarrage ou un conteneur qui tombe ne la perd pas.

La seconde, ce sont les boucles. Un foreach ou un repeat empile un jalon puis suit son corps. Quand la pile redescend jusqu’à ce jalon, un passage est terminé et la boucle décide s’il y en a un autre. Le graphe reste donc un graphe orienté acyclique, aucun fil ne pointe vers l’arrière, et tout ce qui repose sur l’acyclicité continue de fonctionner : l’accessibilité, l’absence de cycles, la vue en liste topologique d’un flux.

Ce dernier point mérite que l’on s’y arrête. La manière évidente d’ajouter des boucles à un éditeur de graphes est de laisser l’utilisateur tracer une arête vers un nœud antérieur. C’est aussi la manière qui détruit en silence toutes les autres garanties de l’éditeur, et on s’en aperçoit le jour où une validation écrite un an plus tôt commence à dépasser son délai.

L’idempotence en trois couches qui font chacune autre chose

Une exécution en pause est réveillée par un ouvrier à travers le réseau. Les ouvriers réessaient. La question qui décide si cette fonctionnalité est sûre est donc de savoir ce qui se passe quand la même exécution est réveillée deux fois.

Il y a trois mécanismes, et ce n’est pas de la redondance. Chacun attrape autre chose.

La revendication est la vraie frontière ; les deux autres sont de la structure. La raison est que les effets de bord d’un flux, une commande envoyée à un agent, une notification, une requête HTTP sortante, se produisent pendant le parcours et non après. Le seul endroit correct pour arrêter le second ouvrier est donc avant qu’il ne commence à parcourir, et non au moment où il essaie d’écrire ses résultats. Celui qui reçoit zéro ligne en retour de cette mise à jour ne reprend pas, et l’affaire est close.

Une reprise qui échoue est un problème distinct d’une reprise qui duplique. Il y a un plafond de cinq tentatives avec une temporisation d’une, deux, quatre et huit minutes, car un parcours qui lève une erreur à la reprise, un modèle supprimé, un serveur qui n’existe plus, serait sinon réessayé à chaque battement pour toujours, avec une table de file d’attente qui ne se vide jamais.

Une seule colonne pilote la file d’attente

L’ouvrier pose exactement une question : quelles attentes sont échues. C’est un statut et une heure de réveil, rien d’autre.

Une échéance est une heure de réveil dans le futur. Prendre une décision, c’est mettre cette heure de réveil à maintenant. Il n’y a délibérément pas de seconde voie vers l’exécuteur, pas de dispositif où l’action serveur reprendrait elle-même l’exécution et où l’ouvrier le pourrait aussi. Deux voies seraient une course entre elles, et cette course serait invisible, car les deux chemins produisent une exécution qui a l’air correcte.

Cela a aussi rendu le second type d’attente peu coûteux. Quand un délai durable est arrivé, rien n’a changé dans la file d’attente. C’est une ligne avec une heure de réveil, à laquelle aucun être humain n’est attaché.

Deux tables, parce qu’elles n’ont pas la même vie

La mécanique et le produit sont deux tables distinctes, et la tentation de les fusionner est forte, car au premier jour elles sont en correspondance un à un.

La ligne de mécanique répond à la question « quand cette exécution doit-elle continuer, et avec quoi » : une continuation, une heure de réveil, une revendication, un compteur de tentatives. Elle est interne, elle est générique, et elle est supprimée quand elle a servi.

La ligne de produit répond à la question « ce qui a été demandé, à qui, et ce qui a été décidé » : un intitulé, une explication, une échéance, un décideur, un horodatage. Un client la lit. Un auditeur la relit un an plus tard. Elle survit à l’exécution à laquelle elle appartenait.

Les fusionner donne une table dont la moitié des colonnes sont nulles dès qu’un second type d’attente existe, ce qui est exactement ce qui s’est passé quand le délai durable est arrivé un jour plus tard.

De petites décisions faciles à rater

Le nœud s’appelle approval et non approval.wait. Un point est un séparateur d’espace de noms dans nos catalogues de traduction : un type de nœud qui en contient un produit donc une clé qui se résout en objet imbriqué au lieu d’une chaîne. C’est le genre de contrainte qui vit dans un autre système que celui que l’on est en train de modifier.

L’expiration a trois issues et non quatre : approuver, refuser ou ignorer. Ignorer est celle qui a demandé réflexion, car le quatrième choix évident, « laisser en suspens », n’est pas un choix : c’est l’absence de politique. Une approbation ignorée ne prend aucune des deux branches et le dit dans le registre, ce qui est différent d’être approuvée et différent d’être refusée.

Décider est un droit à part entière plutôt qu’une propriété du module. Sans cela, la personne qui écrit un flux valide elle-même ses propres étapes d’approbation, et le nœud tout entier devient décoratif.

Le corps d’une boucle est une zone fermée. On ne peut pas terminer une exécution depuis l’intérieur, et un fil qui va de l’intérieur du corps vers quelque chose d’extérieur est une erreur de validation plutôt qu’une surprise à l’exécution. L’imbrication s’arrête à trois niveaux, les itérations à cent par boucle et cinq cents visites par exécution, et dépasser l’une de ces limites est une erreur et non une troncature. Tronquer signifie que le flux d’un client a fait la moitié de son travail en silence.

Un repeat ne démarre pas sur un chemin qui n’existe pas encore, car une valeur absente se lit comme faux, y compris pour un test de non-égalité. C’est cette dernière clause qui piège les gens : intuitivement, « ce champ n’est pas égal à done » devrait être vrai quand le champ est absent, et traiter la chose ainsi démarre des boucles sur des données qui ne sont pas arrivées.

Trois lacunes que la ronde a trouvées plutôt que créées

La première est un code de refus pour un nœud d’action sans serveur, présent depuis la ronde qui l’a introduit et absent des neuf catalogues de traduction. Personne ne l’avait rencontré. Il y a désormais un garde-fou qui lit les codes de motif dans les fichiers sources plutôt que dans une liste écrite à la main, et qui exige une phrase pour chacun d’eux dans chacun des neuf catalogues. Il est passé au rouge à sa première exécution, avec 83 constatations.

La seconde est que les fichiers de test de tout ce sous-système n’étaient couverts par aucune configuration de vérification de types. Ils n’étaient compilés dans la construction de personne. Les ajouter a révélé six lacunes de typage, dont un statut de résumé d’exécution typé comme simple chaîne, ce qui veut dire que chaque comparaison portant dessus n’était pas vérifiée.

La troisième est que le comportement du nœud de journalisation n’était décrit nulle part sur la page d’exécution : un client regardant une exécution terminée voyait donc une étape dont le but n’était pas expliqué.

Aucune de ces lacunes n’a été causée par ce travail. Les trois ont été trouvées parce qu’écrire un nouveau type de nœud oblige à lire correctement le code alentour pour la première fois depuis des mois.

Ce que nous noterions

1. 01Vérifiez si votre récursion est en position terminale avant de discuter d’une réécriture. Si elle l’est, la conversion en pile explicite est mécanique et vos tests existants en sont la preuve.
2. 02Les tests que vous n’avez pas eu à modifier sont la preuve la plus forte que vous puissiez obtenir. Quarante-trois tests verts inchangés en disent plus que quarante-trois nouveaux.
3. 03Sérialisez la continuation, pas le processus. Une exécution en pause doit être une ligne qui survit à un déploiement.
4. 04Les boucles dans un éditeur de graphes n’ont pas besoin d’une arête vers l’arrière. Un jalon sur la pile garde le graphe acyclique, et tout ce qui dépend de l’acyclicité continue de fonctionner.
5. 05L’idempotence a sa place avant les effets de bord, pas après. Revendiquez le travail, puis faites-le.
6. 06Une seule colonne doit piloter la file d’attente. Deux voies vers le même exécuteur, c’est une course que vous ne verrez pas en test.
7. 07Mécanique et produit sont deux tables différentes dès qu’il existe un second type de mécanique, ce qui arrivera plus tôt que vous ne le pensez.
8. 08Une politique d’expiration sans valeur par défaut n’est pas une politique. Nommez l’issue, y compris celle qui ne prend aucune des deux branches.
9. 09Approuver est un droit, pas un effet de bord du fait de pouvoir modifier.
10. 10Une limite doit être une erreur, pas une troncature. La moitié d’un flux qui annonce un succès est pire qu’un flux qui s’arrête.

Pour être clair : la vérification de fusion a exécuté 16 étapes sur 16 sans une seule ligne d’échec, l’exécution de bout en bout contre la base de données de développement a donné 83 verts, le test navigateur avec un vrai ouvrier de passerelle a donné 27 verts, où la seule action humaine est un clic et où l’ouvrier journalise qu’il en a réveillé une et repris une, le test de la toile a donné 37 verts et le balayage d’accessibilité n’a rien trouvé sur cinq pages. Non prouvé : une construction de production, les branches d’épuisement des tentatives et de revendication périmée, les nœuds repeat et break en dehors de la suite de tests pure, et les boucles contenant un nœud d’action.

Issu du travail de plateforme sur Provibr. Ce que le même graphe devait garantir avant que tout cela n’existe est dans Un flux est un graphe, et il doit être fini, et l’éditeur dans lequel il se dessine est dans Un fil que l’on tire, et exactement un déclencheur.