Concevoir une file de capacité multidimensionnelle

Résumé

Ce mois-ci, j'ai dû ajouter des dimensions supplémentaires à un mécanisme de file de capacité. L'appli de commande de repas que j'ai créée devait pouvoir limiter la capacité selon le nombre de commandes, le contenu de chaque commande et le mode de remise (à emporter ou livraison). Lis la suite pour savoir comment j'ai utilisé une architecture Lambda pour y arriver.

Texte intégral

Limiter la capacité

Tu ne t'en rends peut-être pas compte, mais l'une des fonctions les plus puissantes de l'appli de commande de repas que j'ai créée est justement de pouvoir limiter le nombre de commandes. Ça paraît contre-intuitif, mais en limitant le nombre de commandes passées, mes clients (les restaurateurs et commerçants qui utilisent mon appli) s'assurent que les commandes soient préparées et livrées correctement.

La complexité de trois pizzas

Disons que tu veux commander trois pizzas. L'appli doit alors savoir :

• Veux-tu les retirer sur place ou te les faire livrer ?
• À quelle heure ? Quand devront-elles passer au four ?
• Y a-t-il assez de place pour trois pizzas dans le four à ce moment-là ?
• Si tu as choisi le retrait : peut-on t'accueillir en toute sécurité à cette heure-là ?
• Si tu as choisi la livraison : un livreur ou une livreuse est-il disponible pour t'apporter tes pizzas ?
• Oui à tout ? Alors merci de payer pendant que nous gardons tes pizzas planifiées au four et pour la livraison ou le retrait. Paiement échoué ? Un doute ? Alors on « annule » toute la planification et on attend que quelqu'un d'autre commande des pizzas !

Trois dimensions de capacité

Surtout autour de l'« heure du dîner », il y a un risque que trop de gens commandent à manger en même temps. Même si l'appli encaisse le surcroît de trafic grâce à son architecture hautement évolutive, les contraintes physiques demeurent, comme :

• capacité de la cuisine : le nombre de plats qu'on peut préparer en même temps
• capacité de retrait : le nombre de personnes qu'on peut accueillir en toute sécurité en même temps, compte tenu des restrictions COVID-19
• capacité de livraison : le nombre de commandes qu'on peut livrer, en tenant compte de la circulation, de la distance et de l'itinéraire

Distinctes mais interdépendantes

Ces trois types de contraintes sont interdépendants. Par exemple, une grosse commande à emporter peut absorber toute la capacité de la cuisine, ce qui rend la livraison indisponible aussi. De plus petites commandes pourraient encore être acceptées pour remplir la capacité de la cuisine, alors qu'il n'y aurait peut-être plus assez de capacité pour de grosses commandes. Il faut donc un mécanisme qui examine toutes les mesures ensemble pour déterminer la disponibilité pour de nouvelles commandes, y compris le contenu d'une commande non encore passée (par exemple ce qu'il y a dans ton panier).

Différences de granularité temporelle

Il est courant de définir une contrainte physique par une durée, par exemple « la cuisine peut produire 10 plats par tranche de 15 minutes ». Ça se corse quand d'autres contraintes physiques sont définies avec des durées différentes. Alors que la cuisine pourrait être limitée par tranche de 15 minutes, la capacité de livraison pourrait utiliser une durée plus longue (par exemple 3 livraisons par tranche de 30 minutes). Le mécanisme doit pouvoir gérer ces différences de granularité temporelle.

Commander à l'avance

L'option de commander à l'avance ajoute au défi. Les gens peuvent choisir un créneau futur et faire réserver la capacité nécessaire. Parfois, je vois des gens passer commande des jours à l'avance pour être sûrs d'être livrés un jour et à une heure précis. Il y a donc (au moins) deux heures associées à chaque commande : l'heure de commande et l'heure de livraison.

Réserver et libérer de la capacité

La plupart des commerçants exigent un paiement en ligne pour les commandes en ligne, afin que toutes les commandes soient légitimes et qu'aucune capacité (ni nourriture) ne soit gaspillée en cas de défection ou de commandes fantômes. Le problème des paiements en ligne, c'est que toutes les transactions ne réussissent pas. Parfois un paiement par carte de crédit ou de débit est refusé (par exemple faute de fonds). Parfois les gens ferment simplement l'appli avant de terminer la commande. Le système doit réserver la capacité requise pour une commande donnée pendant que la personne effectue le paiement en ligne, et libérer cette capacité si la commande est abandonnée ou si le paiement échoue.

Gros volume, grande vitesse

Enfin, le mécanisme doit être fiable et performant. La disponibilité pour une commande doit être déterminée en quelques millisecondes, malgré une forte concurrence d'accès, car de nombreux clients sont connectés à l'appli pendant le coup de feu. Quand quelqu'un passe une commande, cela influence la disponibilité de toutes les autres commandes (potentielles). Tout le monde n'est pas connecté de façon fiable : certains utilisent l'appli sur des téléphones avec une mauvaise réception ou en wifi. Le système doit bien fonctionner dans des conditions variées, avec beaucoup de personnes connectées.

Architecture Lambda

L'architecture Lambda est une façon de traiter de grandes quantités de données en combinant traitement de flux et traitement par lots. Une architecture lambda repose sur un modèle de données avec une source de données immuable où l'on ajoute seulement, souvent composée d'événements horodatés.

Données immuables

C'est une fondation très importante du mécanisme : toutes les données sont horodatées et ne changent jamais. Au lieu de modifier des enregistrements existants, on ajoute simplement de nouveaux enregistrements qui écrasent les existants. Cela permet une forte concurrence et des algorithmes distribués, car la synchronisation devient plus simple : il suffit de chercher les nouvelles données (et non les nouvelles et les modifiées !).

Couche temps réel / vitesse

Le traitement de flux, ou couche temps réel/vitesse, d'une architecture lambda est conçu pour fournir des réponses ultra rapides aux besoins de données en temps réel. Il maintient des vues et des mesures fondées sur le traitement en temps réel des événements.

Couche de précalcul

Le traitement par lots, ou couche de précalcul, fournit une base complète et exacte de toutes les données du système. Comme traiter de grandes quantités de données peut prendre du temps, le traitement par lots n'est pas assez rapide pour tout faire instantanément. C'est pourquoi les deux couches travaillent en tandem dans une architecture lambda.

Mise en œuvre

Les serveurs backend qui traitent les commandes de l'appli travaillent avec un flux de données d'événements horodatés. En gros, chaque commande est un événement du système. Chaque commande est stockée avec sa date/heure de commande, sa date/heure de remise (livraison ou retrait planifié), les informations du client et le contenu de la commande (nombre de plats, etc.).

Réserver et libérer de la capacité

Si le paiement échoue ou si une commande est abandonnée, une commande « négative » est ajoutée au flux de données. Ses mesures négatives neutralisent tout effet sur les contraintes de capacité. Par exemple, pour annuler une commande de trois pizzas, on crée dans le flux une commande négative de « moins trois pizzas » avec le même horodatage de remise. C'est une façon élégante de garantir que la capacité soit à la fois réservée et libérée.

Mesures temps réel multidimensionnelles

Au lieu de résumer la capacité en compteurs, le serveur backend utilise les vraies données du flux pour répondre aux requêtes de mesures en temps réel. Cela permet au système de gérer les différences de granularité temporelle.

Quand une requête arrive pour la première fois pour une mesure donnée, le système charge les données historiques par un mécanisme par lots pour initialiser le modèle, qu'il peut ensuite tenir à jour en temps réel. Cette mesure est tenue à jour en examinant toutes les nouvelles commandes qui arrivent dans le système, tant que des requêtes pour cette mesure continuent d'arriver. Quand les données ne sont plus demandées, le modèle est déchargé. S'il est de nouveau nécessaire, le processus se répète.

Le grand avantage de cette approche, c'est que la plupart des requêtes sont traitées en quelques millisecondes, car elles sont lues directement dans la mémoire RAM, sans interaction avec une base de données ni un disque. Cela donne des performances ultra élevées « à la demande ». C'est parfait pour l'appli de commande de repas, car toutes les durées ne sont pas également populaires.

L'appli interroge régulièrement un serveur central de capacité qui tient à jour les mesures de la file. Elle filtre ensuite les créneaux disponibles en regardant ce que la personne sélectionne réellement pour sa commande. Choisir un créneau (probablement) disponible se fait donc côté client, ce qui allège la charge du backend. Une fois la commande passée, le backend réserve la capacité en mettant à jour les mesures centrales de la file, ce qui empêche d'autres personnes de prendre la même place dans la file.

Conclusion

Les mécanismes de file d'attente peuvent être délicats quand plusieurs mesures contrôlent la vitesse. Prends vraiment le temps de bien modéliser, réfléchis aux données dont tu as vraiment besoin pour faire les vérifications liées à la file.

Maintenant tu sais que commander trois pizzas n'est pas si simple ! Garantir qu'elles puissent être servies chaudes et à l'heure est un énorme défi technique, en plus d'être un bon chef. Heureusement pour toi, moi je ne me concentre pas sur ce dernier point, ha !