MARGO

Actualité

Les horloges de Lamport et le pattern de l’Idempotent Producer (Kafka)

Découvrez notre retour sur la conférence algorithmes distribués pour le Big Data saison 3: une histoire du temps

Par Yannick Decourtray Software Engineer
26/04/2018

Connaissez-vous les horloges de Lamport ? Devoxx France 2018 était l’occasion, lors du très intéressant talk de DuyHai DOAN, de découvrir ou redécouvrir cet algorithme formalisé par Leslie Lamport en 1978, plus que jamais utilisé aujourd’hui dans le domaine des systèmes distribués, et qui aurait notamment inspiré les développeurs de Kafka dans l’implémentation du pattern de l’Idempotent Producer.

Les horloges de Lamport, qu’est-ce que c’est ?

Dans un système centralisé, il n’y a qu’un seul processus, et la datation des événements est triviale. Elle se base sur l’horloge physique de l’unique processus, et l’ordonnancement de ces événements ne pose donc aucun souci. Autrement dit, il est naturellement possible de dire quel événement s’est produit avant un autre.

Dans un système distribué par contre, il y a plusieurs processus interconnectés, et chacun d’entre eux a sa propre horloge physique. La datation des événements est donc relative à chaque processus, et l’ordonnancement des événements n’est pas trivial. Autrement dit, il est difficile de dire avec certitude qu’un événement sur un processus donné s’est produit avant un autre sur un autre processus.  

L’algorithme de Lamport propose une solution pour établir l’ordre partiel d’une suite d’événements dans un système distribué, basé sur un mécanisme d’horloges logiques. Dans quel but ? Et bien il existe à vrai dire dans le domaine de l’informatique distribuée des quantités de problématiques résolues par la datation logique des événements entre processus… Nous verrons plus loin le cas de Kafka, qui s’inspire des horloges de Lamport pour résoudre un problème relatif à son mode de livraison Exactly once. Mais avant cela, étudions le principe de base.

Les horloges de Lamport, comment ça marche ?

Imaginons un système composé de n processus communiquant entre eux. Si un événement local se produit en même temps sur le processus a et sur le processus b, tout le monde comprend que cela n’arrive pas en réalité tout à fait simultanément. Il n’est pas possible de définir une relation de précédence entre ces deux événements, et l’ordre exact d’exécution de chacun n’est pas défini d’un point de vue logique. On dit que ces événements sont concurrents, et ils n’ont pas de lien de causalité. En réalité, toujours d’un point de vue logique, l’ordre d’exécution de ces événements n’a pas d’importance.

Par contre, si a transmet un message à b, cela se traduit par un événement d’envoi sur a qui se produit obligatoirement avant celui de la réception sur b. Ces deux événements sont alors unis par un lien de causalité, et leur ordre logique est parfaitement défini. Par extension, tout événement antérieur à l’envoi de message précité à partir du processus a est de facto aussi antérieur à celui de la réception sur b.

Ceci est le postulat de base de Lamport.

En résumé, nous avons donc trois types d’événements :

  • Les événements locaux aux processus,
  • Les envois de messages,
  • Les réceptions de messages.

Afin de pouvoir dater logiquement chacun de ces événements sur chaque processus, et d’être capable de les ordonner entre eux, Lamport propose d’utiliser un simple compteur sur chaque processus, qu’il nomme Horloge du processus. L’Horloge du processus à un instant t vaut toujours la date du dernier évènement qui a eu lieu sur ce processus. Et au démarrage du système, les Horloges de tous les processus sont synchronisées à 0.

Lorsqu’un événement survient, il est daté de la manière suivante :

  • S’il s’agit d’un événement local, sa date logique sera Horloge + 1
  • S’il s’agit d’un événement d’envoi, sa date logique sera aussi Horloge + 1. Cette date sera transportée dans le message, afin d’aider le receveur à dater logiquement son propre événement de réception.
  • S’il s’agit d’un événement de réception, sa date logique sera [MAX(Horloge, Date transportée par l’event)] + 1

Et c’est tout  ! Avec cet algorithme, les dates logiques de tous les événements de réception sont bel et bien toutes supérieures à celles des événements qui les précèdent, que les événements en question aient eu lieu sur le processus receveur ou sur le processus envoyeur. Les relations de causalité sont donc respectées et l’ordonnancement est ainsi possible.

…Partiellement…

En effet, il reste toujours le problème des événements concurrents cités plus haut. Entre deux processus donnés, il existe des événements qui ont la même date logique et qui pourtant ne se sont pas produits au même instant. Dans la mesure où l’on voudrait établir une chronologie de ce qui s’est passé sur un système distribué, quelle est la priorité à appliquer aux événements ayant une date logique identique ? A cette question épineuse, Lamport rappelle simplement que les événements ayant la même date logique sont concurrents et n’ont pas de lien de causalité entre eux. Et donc, que l’ordre exact de leur exécution n’affecte pas le système.

Néanmoins, par convention, afin que tous les processus disposent tout de même de la même chronologie, on classera les événements concurrents grâce à l’identifiant du processus. Par exemple, on considérera toujours que l’événement ‘2’ du processus a s’est produit avant l’événement ‘2’ du processus b. Juste parce que a est avant b dans l’alphabet. Sans plus de complication. Tout simplement.

Cas d’application : Kafka et l’Exactly once delivery

Kafka est un broker de messages distribué très en vogue, initialement créé par LinkedIn et aujourd’hui maintenu par la communauté Apache, réputé pour ses performances et sa stabilité à basses comme à très hautes volumétries.

Exactly once delivery, c’est quoi ? Expliquons d’abord le mode par défaut, qui est le At least once delivery.

Comme tout broker de messages qui se respecte, Kafka se doit de garantir la bonne distribution des messages qu’il reçoit à ses clients. Un problème qui se pose d’hors et déjà ici : quand bien même le message est distribué par Kafka, comment être sûr que le client l’a bien reçu ? Un simple acquittement de sa part dans le sens inverse fera très bien l’affaire me direz vous. Mais quid si une coupure réseau intervient à ce moment précis, ou si le client subit un crash avant d’avoir pu envoyer ce fameux ACK ?

Et bien, de manière très classique pour Kafka, tout message non acquitté est considéré comme non-reçu, et doit donc être envoyé de nouveau. Et ceci, au risque que le client reçoive et traite le message en réalité deux fois (ou plus)… C’est ce qu’on appelle le At least once delivery. Autrement dit, dans ce mode précis, un même message peut être reçu plusieurs fois par le client. Et dans ce mode précis, donc, le client se doit d’être lui-même « idempotent », c’est à dire insensible à n réception d’un même event.

At least once delivery, est un bon début…

II se trouve que Kafka propose encore mieux… un mode Exactly once delivery. C’est à dire qu’un message ne sera distribué qu’une seule fois à chaque client. Garanti ! Magique ! Cette feature beaucoup plus poussée d’un point de vue technique, considérée comme une prouesse par certains, s’appuie sur trois concepts : un mécanisme de transaction inter-partitions, un système d’offset persisté, ainsi qu’un pattern d’idempotence appliqué entre les instances de brokers Kafka et… les producteurs.

Complexe ?… Pas de panique : nous ne nous attarderons pas sur les deux premiers concepts car ils sont en réalité hors sujet ! C’est le troisième qui nous intéresse ici, et que nous allons détailler dans cet article.

En effet… réfléchissons un peu. Pour qu’un client ne reçoive qu’une seule fois un événement donné, il faut déjà être certain que Kafka ne l’enregistre qu’une seule fois dans l’une de ses partitions. Même s’il y a d’autres problématiques à prendre en compte (mais qui sont réglées par les deux autres concepts cités plus haut sur lesquels nous ne reviendrons pas dans le cadre de cet article), celle-ci est la plus élémentaire. En mode Exactly once, un événement envoyé par un Producer, même à de multiples tentatives, se doit d’être absolument enregistré une, et une seule fois, par Kafka.

Or les Producers sont exposés eux aussi à des problèmes d’acquittement – de la part de Kafka lui-même cette fois – (micro coupure réseau, crash d’une instance de broker Kafka…). Comment garantir d’un côté qu’un événement va être enregistré une seule fois, et que la causalité va être respectée de l’autre, c’est à dire que l’ordre des événements sera conservé, même si l’un d’entre eux est momentanément perdu puis rejoué ?

C’est la qu’intervient le pattern de l’Idempotent Producer. Et cela rappelle fortement les horloges de Lamport…

Pattern de l’Idempotent Producer

Pour comprendre ce qui va suivre, il vous faut connaître un minimum du fonctionnement de Kafka.

Kafka est un système de publish/subscribe distribué, qui gère les familles de messages par Topic. UnTopic est segmenté en n partitions réparties sur tout le cluster, un noeud (nommé broker) pouvant gérer éventuellement plusieurs partitions. Quand un Producer envoie un message sur un Topic donné, ce dernier va être routé vers un noeud particulier du cluster, en fonction de sa clé pour y être enregistré dans une seule partition. Les messages ayant la même clé seront toujours enregistrés sur la même partition, donc sur le même noeud Kafka. Relisez ce paragraphe attentivement si ce n’est pas parfaitement clair.

Chaque noeud garde une valeur appelée High Watermark pour chaque Producer. C’est l’équivalent de l’Horloge dans l’algorithme de Lamport. De plus, chaque Producer gère une séquence distincte pour chaque partition pour dater logiquement ses événements.

Dans Kafka on recherche la vélocité. Donc les Producers sont conçus pour envoyer des rafales de messages sans attendre d’acquittement entre chaque message. Ces derniers arriveront au fil de l’eau de manière asynchrone. Mais que se passe-t-il si l’un ce ces acquittements se perd ? Le Producer va évidemment retenter l’envoi du message concerné, mais il ne faut pas que cela cause d’incohérence dans l’ordre des messages réellement enregistré côté broker.  

Grâce à l’algorithme de l’Idempotent producer, Kafka est capable de détecter ces incohérences de séquences de réception de messages, et de rejeter ainsi tous les messages qui suivent. Concrètement chaque fois qu’un Producer publie quelque chose, le message transporte son propre identifiant logique incrémenté de un en un, et le broker ne l’acquittera que si cet identifiant est égal au Watermark + 1.

A défaut de l’application exacte, on retrouve bel et bien ici l’essence de l’algorithme des Horloges de Lamport, alors que cette théorie a vu le jour en 1978 et qu’à cette époque peu de systèmes étaient distribués. 

Conclusion

De manière amusante, Confluent a publié une documentation de 67 pages [1] expliquant de manière très détaillée comment le Exactly Once a été implémenté dans Kafka. Et si la notion d’idempotence des producers est bien mentionnée à de multiples reprises, l’application stricte de l’algorithme des Horloges de Lamport pour l’implémentation de ce pattern n’apparaît pas une seule fois. Qu’en déduire ?

Et bien peut-être qu’en réalité , les développeurs qui travaillent sur Kafka n’avaient pas les Horloges de Lamport en tête lorsqu’ils ont développé leur solution. La plupart des problèmes que nous nous posons aujourd’hui dans le domaine de l’architecture logicielle ont probablement déjà été tous théorisées il y a des années de cela, à des époques où les infrastructures étaient pourtant bien moins complexes. Même sans avoir la connaissance systématique de ces théories, le bon sens nous amène vers des solutions à ces problèmes qui convergent avec elles.

Il aurait été intéressant que DuyHai DOAN, lors de sa présentation à Devoxx, souligne le fait que le pattern de l’Idempotent producer de Kafka n’est peut-être pas, comme il le laissait entendre, une application stricte et mécanique de l’algorithme des Horloges de Lamport, mais bel et bien le fruit d’une réflexion sage qui prouve que cette théorie est correcte et plus que jamais d’actualité.

 

La présentation de DuyHai DOAN, tout comme ce billet, est grandement inspirée par cet article : https://cwiki.apache.org/confluence/display/KAFKA/Idempotent+Producer. La synthèse du pattern qui est faite ici étant volontairement résumée, nous vous invitons à le lire si vous avez besoin de détails techniques plus poussés.

[1] https://docs.google.com/document/d/11Jqy_GjUGtdXJK94XGsEIK7CP1SnQGdp2eF0wSw9ra8/edit#


Par Yannick Decourtray Software Engineer
Big Data
Data
DataScience
Actualité

Mener à bien un projet data : une route encore semée d'embûches

En 2020, les investissements des entreprises dans les projets data devraient dépasser les 203 milliards de dollars au niveau mondial. Mais à l'heure où beaucoup se revendiquent être des Data Driven Companies, nombre de projets data se soldent encore par un échec.

15/10/2018 Découvrir 
Actualité

Tutoriel : Quelques bases en python pour la prédiction de séries temporelles

Dans ce tutoriel, nous introduisons quelques concepts élémentaires en séries temporelles afin de pouvoir effectuer “rapidement” des prédictions de valeurs futures sur des données temporelles. Loin d’être exhaustif, ce premier tutoriel présente quelques outils de base en Python permettant d’effectuer de premiers traitements. Le code permettant de retrouver ces résultats est ici : https://gitlab.com/margo-group/public/SeriesTemporelles.

11/09/2018 Découvrir 
Actualité

Kaggle Challenge : Ad Tracking fraud detection pour TalkingData

TalkingData est la plus grande plateforme indépendante de services Big Data en Chine, couvrant plus de 70% des appareils mobiles actifs dans tout le pays. Ils traitent 3 milliards de clics par jour, dont 90% sont potentiellement frauduleux. Afin de garder une longueur d'avance sur les fraudeurs, ils se sont tournés vers la communauté Kaggle pour obtenir de l'aide dans le développement de leur solution. Le sujet du challenge : créer un algorithme qui prédit si un utilisateur va télécharger une application après avoir cliqué sur une annonce d'application mobile.

31/05/2018 Découvrir 
Actualité

La Data Science appliquée au monde du retail : les 10 use-cases incontournables

La Data Science impacte de plus en plus les business model dans toutes les industries, et notamment dans la vente de détail. Selon IBM, 62% des détaillants déclarent que l'utilisation de techniques relatives au Big Data leur donne un sérieux avantage compétitif. Savoir ce que veut votre client et à quel moment est aujourd’hui à portée de main grâce à la data science. Pour cela il suffit d’avoir les bons outils et les bons processus en place pour les utiliser. Nous présentons dans cet article 10 applications essentielles de la data science au domaine du retail.

18/05/2018 Découvrir 
Actualité

Introduction aux Chatbots avec Dialogflow

DialogFlow est un très bon outil pour apprendre à créer des Chatbots qui pourront ensuite être intégrés dans vos propres sites web ou applications. Dans cet article, je commencerai par introduire quelques notions sur Dialogflow et les Chatbots, puis je vous expliquerai comment créer simplement un Chatbot sur cette plateforme.

07/05/2018 Découvrir 
Actualité

Introduction aux systèmes réactifs

Les systèmes réactifs sont un style d’architecture permettant à de multiples applications individuelles de se fondre en une seule unité, en réagissant à leur environnement, tout en restant conscientes les unes des autres. La première formalisation de ce terme a vu le jour avec la création du « Reactive Manifesto » en 2013 par Jonas Boner qui, en rassemblant certains des esprits les plus brillants dans l’industrie des systèmes distribués, souhaitait clarifier la confusion autour de la réactivité (qui est devenu un « buzz-word ») et construire une base solide pour un style de développement viable.

04/05/2018 Découvrir