Il y a 3 années · 8 minutes · Back

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

Comment concevoir des systèmes capables d’encaisser des dizaines de milliers d’updates par seconde sans s’engorger, ni dépasser la milli-seconde de traitement ? Comment écrire du code scalable qui reste lisible mais garanti 100% sans deadlock ? Que recouvre le reactive manifesto et les termes : conflation, sequencer, immutable state ? Après vous avoir présenté les besoins et contraintes du trading électronique, nous répondrons à toutes ces questions dans une session qui s’annonce…technique.

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.
Anne Beauchart
Chargée de marketing chez Xebia.
Xebia France
Xebia est un cabinet de conseil international spécialisé dans les technologies Big Data, Web, les architectures Java et la mobilité dans des environnements agiles. Depuis plus de 11 ans nous avons la volonté de partager notre expertise et nos actualités à travers notre blog technique.

9 réflexions au sujet de « DevoxxFR – Basses latences, hauts débits : les secrets de la finance pour avoir des systèmes réactifs »

  1. Publié par Anas, Il y a 3 années

    Il n’y a que le le métier de la finance qui persiste à croire à l’hypothèses d’un « marché transparent » et par conséquent à toujours pousser les limites technologiques vers un temps de latence qu’il souhaiterais un jours « égal à zéro ».
    La majorité des métiers ne nécessitent pas un temps de latence proche de zéro. C’est même une constante qui n’évolue que très rarement (transformation d’usages suite à une rupture technologique majeurs) et qui est rarement en dessous de l’ordre de grandeur de la seconde.

  2. Publié par Yannick Grenzinger, Il y a 3 années

    Bonjour,

    D’abord le débat éthique sur la finance et encore plus sur le trading à haute fréquence n’a malheureusement pas sa place sur un blog technophile et c’est justement ce côté technophile qui peut faire apprécier les défis techniques du monde financier.

    Enfin je ne suis pas complètement d’accord avec « La majorité des métiers ne nécessitent pas un temps de latence proche de zéro ». Oui la grande majorité des DSIs et des métiers de gestion n’ont pas besoin d’un flux d’information dont la latence soit la plus faible possible. Ils ont des problèmes bien plus importants à régler d’abord. Cependant on peut aller chercher ce besoin dans des métiers plus extrêmes comme les besoins d’un hôpital, la sécurité de technologies à risque, la recherche physique, etc. J’extrapole mais c’est juste pour indiquer que tous les métiers ne sont pas solubles dans une feuille excel :)

  3. Publié par Cyrille Dupuydauby, Il y a 3 années

    La présentation portait sur comment concevoir un système capable de gérer de fortes charges avec une consommation de ressource raisonnable. Les mécanismes présentés s’appliquent parfaitement à des services web par exemple (cf la programmation réactive). En ce qui concerne latence finance, la discussion est intéressante, mais ce n’est ni l’objet de ce billet ni celui de la présentation faite.

  4. Publié par Anas, Il y a 3 années

     » Cependant on peut aller chercher ce besoin dans des métiers plus extrêmes comme les besoins d’un hôpital, la sécurité de technologies à risque, la recherche physique, etc »
    On est d’accord le besoin d’un temps de latence proche de zéro est réservé à des cas particuliers qui ne sont pas la majorité.
    Il serait intéressant de jetter un coup d’oeuil coté Spark (http://spark.apache.org/) qui un dispositif innovant et très bien adapté pour des temps de latence de l’ordre de la seconde.
    Pour la remarque sur la finance, c’était pour charrier, l’humour c’est très stimulant pour l’intellect :-)

  5. Publié par Thomas Pierrain (@tpierrain), Il y a 3 années

    Je ne suis absolument pas d’accord avec Anas en ce qui concerne l’humour: ces choses sont beaucoup trop grave !!!

    D’ailleurs, ne dites surtout pas à mes parents que je bosse dans la finance… car ils pensent tous que je suis vétérinaire !

    Sur le sujet de la latence sinon, il est intéressant de noter que la tendance actuelle en finance est plutôt d’arrêter cette course à l’armement sur le low latency (le ratio coût d’investissement/rendement est beaucoup plus discutable de nos jours, étant donné les limites physiques atteintes, et la pression des régulateurs qui tendent de taxer ceux qui font trop de bruits avec leurs armes de latence massives).

    La tendance actuelle dans le « vétérinariat » est d’ailleurs plutôt d’aider la décision (d’achat et de vente) à l’aide d’analytics et d’exploitation de big data au fil de l’eau (c.ad. pas en mode batch) => des systèmes à la HADOOP, mais en plus rapides (ce qu’on appelle ici où là le « big data in motion ». Et oui : notre industrie a besoin de buzz words pour avancer ;-)

    Certains « poètes » aux US ont même tenté de brancher directement leurs automates de passage d’ordre sur de l’analyse sémantique de twitter… ;-) Vu la déculotté (mais surtout les pertes) qu’il se sont pris, je pense qu’ils auront montrés à toutes et à tous où ne pas aller en état (de l’art).

    Au passage et pour finir, merci aux auteurs pour cet excellent résumé de notre session.

    Thomas

  6. Publié par Thomas Pierrain (@tpierrain), Il y a 3 années

    Pour ceux qui sont intéressés par le pattern du sequencer, Cyrille a continué sa série de posts sur le sequencer, en nous proposant une implémentation cette fois.

    Celle-ci étant encore un peu naïve (pour des raisons pédagogiques), vous êtes appelés à contribuer et à faire vos propositions avant la publication de son 3eme post sur le sujet.

    La question est : comment pouvez-vous améliorer l’implémentation proposée pour garantir que les tâches seront bien exécutées dans le même ordre que celui de leur soumission au sequencer ?

    Tous les détails sur: http://dupdob.wordpress.com/2014/05/09/the-sequencer-part-2/

    A vos propositions !

  7. Publié par Laurent Valdes, Il y a 3 années

    Si vous souhaitez trouver un domaine ou les latences doivent être en dessous de réseau, il y en a un assez couru, qui est celui des réseaux informatiques. Je vous laisse imaginer la vie numérique si les temps de latence n’y étaient pas inférieurs à 1 seconde.

    D’ailleurs cisco propose des hardware spécialement dédiés à la basse latence: http://www.cisco.com/c/en/us/products/switches/nexus-3548-switch/index.html

    Page qui comme par hasard renvoie vers des brochures de low latency trading.

    Sinon il est aussi un domaine ou la latence est importante, c’est le rendu en cluster en passant par MPI

    https://www.pdc.kth.se/education/tutorials/summer-school/mpi-exercises/mpi-lab-3-bandwidth-latency-and-timings/mpi-lab-3-bandwidth-latency-and-timings.

    Si votre grand-mére fait du calcul par éléments finis, il est fort possible qu’elle s’intéresse au low-latency.

    Cordialement,

  8. Publié par Smithd44, Il y a 3 années

    I truly appreciate this post. I’ve been looking everywhere for this! Thank goodness I found it on Bing. You’ve made my day! Thank you again! gfceebekkgcfbkke

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *