DevoxxFR – Basses latences, hauts débits : les secrets de la finance pour avoir des systèmes réactifs

Cyrille DUPUYDAUBY et Thomas PIERRAIN nous ont fait un excellent retour à Devoxx France sur la mise en place d’un système réactif afin de répondre aux besoins métiers de la finance de marché, précisément un algorithme de pricing.

Après nous avoir introduit aux concepts et problématiques liés à l’activité de marché (exercice mené avec brio face à une horde de néophytes), ils nous ont présenté 3 approches d’architectures incapables de répondre correctement à leur besoin, nous guidant dans la réflexion vers l’architecture qu’ils utilisent en production pour paralléliser les calculs et gérer les pics de charge. Enfin, ils ont ouvert le débat vers quelques réflexions d’ordre général pour aborder des problématiques d’algorithmes réactifs, soumis à de fortes charges.

Pitch

Présentation du métier

Pour passer des ordres d’achat et de vente sur des produits financiers, les investisseurs peuvent soit se connecter directement à un marché, soit passer par un intermédiaire que l’on appelle « broker ». En plus de sa capacité à offrir ce type de service pour ses clients, la SG CIB –en sa qualité de « Market Maker » – a également l’obligation de fournir régulièrement de la « liquidité » sur les différents marchés (c.ad d’animer ceux-ci en fournissant des prix d’achat et de vente sur de nombreux produits).
Acheter au meilleur prix, et vendre au meilleur prix, sachant que les combinatoires sont très variées suivant que l’on achète à la hausse, à la baisse, des prix dans le futur etc…
La SGCIB publie des ordres pour ses clients en se basant sur les événements du marché indiquant les variations des prix des devises, produits financiers, etc…Au final, cela 5 millions d’ordres par jour, et une moyenne de 250 000 updates par seconde sur la journée. Suite à la publication d’un événement de marché, il faut mettre à jour tous les prix des produits financiers concernés, et publier les ordres correspondants, tout ceci dans l’espace d’une milliseconde (voire plusieurs, en fonction du type de produit concerné).
De toute façon, plus on est rapide, mieux c’est. Pour les algorithmes de haute fréquence, on descend autours de quelques dizaines de microsecondes voire de quelques centaines de nanosecondes. Ce ne sera pas l’objet de la présentation : ce ne sont pas les mêmes natures de transactions, pas les mêmes algorithmes, pas les mêmes infrastructures techniques pour les calculs ni les mêmes coûts associés.

Pour simplifier la présentation des algorithmes, Cyrille nous a exposé le problème sous la forme d’un super marché, dans lequel notre but est de mettre à jour le prix des pâtes (différentes formes, couleurs, avec ou sans oeufs, avec des produits en plus), en fonction des prix des ingrédients de base. Une combinatoire de 2400 pâtes différentes au final.
Nous nous sommes donc intéressés à résoudre deux problèmes avec Thomas cette fois : la rapidité du calcul et les pics de charge afin d’assurer aussi bien les basses latences que les hauts débits.

Différentes approches

1ère approche: Algorithme mono-thread
Cette approche est intéressante lorsque de très basses latences sont nécessaires, pour le trading de haute fréquence par exemple. Dans ce cas, on se trouve sur des architectures techniques plus adaptées (pour plus d’informations, n’hésitez pas à aller voir les conférences de Martin Thompson). Cependant, dans notre cas, on veut tirer parti efficacement des 16 coeurs du CPU du serveur.

2éme approche: Algorithme multi (worker) threads
On crée un thread par type de pâte qui sera en charge de calculer les nouveaux prix pour ce type de pâte. L’inconvénient, c’est que l’on va créer 2400 threads. La machine passe plus de temps à faire du contexte switching qu’à calculer vraiment les prix des pâtes. Impossible de penser une telle approche avec des millions de prix.

On en vient donc rapidement à la 3éme approche: Algorithme avec pool de thread
Un ensemble de thread calculent des prix, en piochant dans la liste d’évènements, indifféremment de la nature des produits concernés. Cette approche est assez difficile à mettre en oeuvre, il faut faire attention au locking des threads. On arrive à s’en sortir tout de même. Malheureusement, comme chaque thread pioche dans la liste d’événement et que l’on a aucune maîtrise sur l’exécution des thread en eux-mêmes, on peut se retrouver dans des cas où un thread met du temps à calculer un prix alors qu’un autre thread vient de produire une nouvelle valeur pour ce prix sur la base d’événements plus récents. Ces incohérences peuvent se répercuter sur les carnets d’ordres et en particulier lorsque l’on travaille sur des produits composites.

Il s’agit en quelque sorte de « race conditions fonctionnelles » à l’échelle du système entier. Ces erreurs font la part belle à l’arbitrage.

On sent qu’il va falloir ajouter de l’intelligence dans notre pool de thread pour gérer efficacement cet ordre, et la complexité apportée par cette tâche doit être transparente pour les développeurs (qui ne doivent surtout pas utiliser de lock dans leur code applicatif au passage. Car comme le dit l’expert : « qui dit lock … dit deadlock »). Et puis on ne peut pas penser systématiquement à la problématique d’interlocking de thread et être productif sur du code métier.

C’est là qu’intervient la 4éme approche: Mise en oeuvre du pattern « sequencer »
Le pattern « sequencer », c’est « simplement » gérer notre pool de thread en amont et masquer la complexité du multithreading. Les « sequencer » sont en charge d’ordonner les événements par nature de produit et de répartir les calculs sur des threads différents.

Un « sequencer » implémente l’interface :

interface Sequencer {
    void dispatch(Task function);
}

On peut donc se concentrer sur la « Task », sans se poser la question de la concurrence. En effet : toutes les tâches traitées par le même Sequencer (en mode asynchrone et sans affinité de threading), seront exécutées dans le même ordre que celui dans lequel il les aura reçues.  L’implémentation du sequencer peut par contre se baser sur des locks (ou pas !). L’important c’est d’avoir encapsulé cette complexité.

Gérer les pics de charge

Sans se limiter au dimensionnement de leur architecture en fonction du pic de charge maximal auquel ils peuvent être confronté, Cyrille et Thomas nous ont présenté une approche intéressante pour limiter l’empilement des messages dans la file d’entrée : la « conflation ».
Derrière ce mot se cache une idée simple : plutôt que d’empiler les messages, essayons de consolider l’information. Ainsi on pense tout de suite à deux approches pour la « conflation » :

• Le balking : un nouveau prix est arrivé, le prix que j’ai dans ma file d’attente est donc périmé, je peux ainsi le remplacer par le nouveau prix (une sorte d’annule et remplace).
• Le merge : un nouvel évènement peut enrichir un événement déjà présent dans ma file. La stratégie de merge dépend alors de votre métier.

Attention cependant : la conflation sur une file ne s’activant qu’à partir du moment où le système est déjà occupé (à calculer des prix de pâtes par exemple), il est primordial de ne pas bypasser celle-ci en déversant rapidement les événements de cette file conflatée vers une autre file intermédiaire dans notre système (qui n’aurait -elle- pas de conflation). Notre système pourrait alors prendre du retard « par le milieu », en s’engorgeant dans cette file intermédiaire (difficile à diagnostiquer).

Et l’option d’annuler une tâche en cours qui vient juste de commencer pour pouvoir la refaire avec un input plus récent ? Très mauvaise idée d’après les speakers, car notre système pourrait se retrouver alors à ne jamais rien finir de ce qu’il entreprend. Il est important de calculer et de publier des prix ; même s’ils pourraient être plus « frais », ceux-ci seront déjà bien plus frais que le dernier déjà publié pour cette pâte quelques millisecondes plus tôt.

Conclusion

Finalement, on ne nous aura pas décrit les implémentations du « sequencer » ou de la « conflation », probablement faute de temps, cela reste néanmoins notre seule frustration concernant cette excellente présentation qui nous aura apporté quelques idées à ne jamais oublier dans les situations de performances et parallélisation des traitements :

• Réfléchir à la modélisation pour choisir les zones à paralléliser
• Encapsuler la complexité
• D’éviter le fléau des deadlocks en proscrivant l’utilisation de lock ou de wait sans timeout dans le code applicatif
• Ne pas « deviner » la performance mais mesurer, mesurer, mesurer
• Il n’y a pas de solution toute faite (même les systèmes « réactifs ») et chaque solution est adaptée à un métier et un traitement particulier.