Backstage News

Dans les coulisses de Fleet, Partie III – Gestion d’états

Read this post in other languages:

Cet article fait partie d’une série consacrée à la conception et au fonctionnement de Fleet, notre IDE nouvelle génération.

 

Précédemment, nous avons abordé les sujets de l’architecture de Fleet et des algorithmes et structures de données utilisés dans l’éditeur. Dans ce nouvel article, nous allons commencer à examiner l’approche adoptée pour implémenter la gestion des états. Il s’agit d’un sujet complexe, que nous développerons en plusieurs fois. Pour le moment, nous allons débuter avec la représentation et le stockage des éléments de l’état de l’application. Nous verrons plus en détail dans un prochain article quels sont les mécanismes transactionnels de la gestion des états dans Fleet.

 

Fleet comporte beaucoup d’éléments qui interagissent étroitement les uns avec les autres et exécute de nombreuses opérations différentes, notamment :

 

  • Le rendu des éléments de l’interface utilisateur et les interactions avec les utilisateurs.
  • Les interactions avec d’autres services pour obtenir des données et mettre à jour les éléments de l’interface utilisateur.
  • La gestion des fichiers, ce qui inclut leur enregistrement, leur chargement, leur analyse et l’affichage des différences entre eux.
  • L’orchestration des backends liés à l’analyse de code, à la saisie semi-automatique et aux résultats des recherches.

La plupart de ces opérations sont complexes et peuvent affecter la réactivité de l’interface. Et Fleet est une application distribuée pouvant avoir plusieurs frontends répartis sur le réseau, ce qui complique encore plus les choses. Néanmoins, nous devons présenter toutes les informations de façon cohérente et correcte à nos utilisateurs et leur garantir de pouvoir travailler harmonieusement sur leurs différents frontends.

 

En ce qui concerne la gestion d’états, toutes ces opérations peuvent se résumer à la lecture ou à la mise à jour d’états. Les éléments de l’interface utilisateur lisent les états pour fournir aux utilisateurs des données réelles, tandis que les utilisateurs mettent à jour les états en modifiant leurs documents et en déplaçant des éléments. Chaque minute, des milliers d’opérations de ce type sont exécutées, c’est pourquoi la gestion d’états est un élément clé de Fleet.

 

Nos principes

 

JetBrains développe des IDE depuis plus de 20 ans. C’est sur la base de cette expérience que nous avons adopté les principes suivants concernant la gestion d’états dans Fleet :

 

Principe 1 : Ne bloquer personne

 

Écrie du code concurrent n’est pas facile. Pour Kotlin (et dans Fleet), nous utilisons des primitives de concurrence légères, appelées coroutines, pour organiser notre code concurrent. Si la lecture d’états d’un grand nombre de coroutines simultanément ne cause quasiment aucun problème, leur mutation peut être dangereuse. L’approche traditionnelle consiste à imposer un verrouillage pour un seul thread rédacteur, ce qui génère de longues files d’attente pour lire quelque chose. Nous pensons que cela n’est pas approprié : les lecteurs devraient avoir la possibilité de lire un état potentiellement légèrement obsolète sans délai. Pour obtenir ce comportement, nous utilisons une variation du modèle MVCC (multiversion concurrency control) pour accéder aux éléments d’état des coroutines. Ces coroutines lisent une version de l’état ou modifient l’état en en fournissant la nouvelle version. Nous lisons et modifions l’état des transactions, ce qui est beaucoup plus facile à mettre en œuvre avec le modèle MVCC.

 

Principe 2 : Être réactif et efficace

 

Les états changent tout le temps et l’interface utilisateur doit refléter ces changements aussi rapidement que possible. Si vous avez déjà programmé des animations simples avec votre premier langage de programmation, vous savez comment faire : tout effacer et tout redessiner à partir de zéro. Malheureusement, tout redessiner prend beaucoup de temps. Il est plus judicieux de redessiner uniquement la partie qui a changé. Mais pour cela, il faut être en mesure de déterminer ce qui a changé exactement. Moins il y a de changements, mieux c’est. Une fois la partie de l’état qui a changé identifiée, il faut déterminer aussi rapidement que possible ce qui dépend de cette partie et exécuter la coroutine correspondante. Il ne s’agit pas seulement de réagir vite aux changements d’état, mais de le faire de manière efficace.

 

Principe 3 : Organiser les données intelligemment

 

Les deux premiers principes que nous venons de voir ne seraient que de belles paroles sans le troisième. Il est essentiel de réfléchir sérieusement à la façon de stocker et de traiter les données. Le stockage avec des options de recherches et de modifications avancées n’est plus réservé aux implémenteurs de systèmes de gestion de bases de données. Un outil comme Fleet, en tant qu’IDE distribué, en a besoin aussi. Ainsi, nous avons dû développer notre propre solution de base de données interne pour atteindre le niveau de flexibilité et les performances que nous souhaitions.

 

Qu’est-ce qu’un état ?

 

Il y a trois points à prendre en compte concernant les états dans Fleet.

 

Tout d’abord, les états sont représentés en tant que structure de données persistante avec différentes versions qui modélisent le changement dans le temps. Pour décrire cela, on peut se référer à une séquence linéaire d’époques qui se succèdent, ce que l’on appelle modèle temporel à époques. Toutes les parties concernées (les coroutines !) lisent toujours l’une des époques, mais pas forcément la plus récente.

 

Deuxièmement, notre état est une base de données d’entités contenant des informations sur tout ce que vous voyez à l’écran et tout ce qui se passe en coulisses. Comme c’est le cas pour de nombreuses bases de données, ces entités sont liées entre elles d’une façon ou d’une autre. 

 

Troisièmement, l’état et ses mutations peuvent se résumer à des triplets de base, appelés datoms, qui sont des éléments de données primitifs nous permettant d’atteindre le niveau d’efficacité dont nous avons besoin. Examinons ces trois idées plus en détail.

 

Un modèle temporel à époques

 

Pendant longtemps, nos programmes modifiaient leurs états. Malheureusement, mettre à jour une seule variable n’est jamais vraiment suffisant. Généralement, nous devons en modifier plusieurs les unes à la suite des autres de façon cohérente. Que se passe-t-il si quelqu’un observe notre état dans une forme incomplète ou tente de le modifier ? Imaginons que nous ayons augmenté la longueur de la chaîne, mais sans avoir fourni de nouveau contenu. Il ne faudrait vraiment pas que nos utilisateurs puissent voir cela. L’idée est de cacher les états incohérents derrière une façade. Passer d’un état cohérent à l’autre prend du temps. C’est comme si une époque succédait à une autre.

 

Le modèle temporel à époques a d’abord été présenté à la communauté des programmeurs par Rich Hickey lors de son intervention Are We There Yet (voir la transcription), dans laquelle il exposait ses idées concernant l’implémentation du langage de programmation Clojure. Il explique que nos programmes peuvent vivre dans un environnement immuable et cohérent pendant un certain temps. L’immuabilité facilite l’implémentation de nombreux éléments, mais il est impossible de rester dans le même environnement pour toujours. Du fait des activités des rédacteurs d’états, un nouvel environnement immuable et cohérent succède toujours au précédent.

 

L’état de Fleet est accessible sous forme d’un instantané immuable, une collection de tous les éléments de l’état entre lesquels la cohérence est garantie. Dans ce modèle, la mise à jour de l’état crée un nouvel instantané. Afin de garantir la cohérence à mesure que les états changent, nous implémentons des transactions.

 

Dans Fleet, le Kernel (ou noyau) est responsable de la transition des instantanés suite aux activités des rédacteurs d’états et fournit une référence à l’instantané le plus récent. Les parties intéressées (lecteurs ou les rédacteurs) peuvent obtenir cette référence lorsqu’ils en en besoins, mais ils ne peuvent pas avoir la certitude qu’elle correspondra bien à la version la plus récente de l’environnement lorsqu’ils l’utiliseront. Le noyau est également chargé de diffuser les modifications auprès des parties qui en dépendent. L’avantage est qu’il n’est pas nécessaire de s’abonner manuellement, il suffit de lire une valeur quelconque pour être prévenu de ses modifications ultérieures.

 

 

Les rédacteurs font la queue pour créer de nouveaux instantanés, mais les lecteurs ne sont jamais bloqués. Ils peuvent toutefois recevoir des informations quelque peu obsolètes.

 

Le modèle de données de notre état

 

Nous sommes maintenant prêts à répondre à la question : qu’y a-t-il dans notre état ? Eh bien, presque tout : le contenu du document avec des informations sur le fichier correspondant, toutes les informations déduites à partir de ce contenu, les positions des curseurs, les plugins chargés et leur configuration, les emplacements des vues et des panneaux, etc. Le modèle de données correspondant est décrit dans Fleet via des interfaces Kotlin, comme suit :

 

interface DocumentFileEntity : SharedEntity {
 @Unique
 @CascadeDeleteBy
 var document: DocumentEntity

 @Unique
 var fileAddress: FileAddress

 var readCharset: DetectedCharset
 // ...
}

interface DocumentEntity : SharedEntity {
 var text: Text
 var writable: Boolean
 // ...
}

 

Remarque : le type Text est en fait une corde, la structure de données dont nous avons parlé dans le précédent article de cette série.

 

Nous utilisons des annotations de propriétés pour décrire les composants des entités et les relations entre eux. Dans cet exemple, une entité fichier de document décrit la relation entre un fichier unique sur un périphérique de stockage de données et un document unique que nous avons lu à partir de ce dernier. L’entité document correspondante doit être supprimée lors de la suppression de l’entité fichier de document.

 

Pour maintenir une telle base de données d’entités, nous avons implémenté notre propre moteur de base de données : RhizomeDB. Il n’impose pas de hiérarchie aux entités, d’où le nom Rhizome, en référence à la tige souterraine qui développe des racines et des bourgeons à partir de ses nœuds.

 

Pour accéder à des entités en tant qu’objets qui implémentent des propriétés depuis les interfaces, comme dans les exemples ci-dessus, RhizomeDB fournit une API. Nous pouvons par exemple obtenir un document basé sur une adresse de fichier, comme suit :

 

val document = lookupOne(DocumentFileEntity::fileAddress,
                         fileAddress)?.document

 

L’objet document implémente maintenant l’interface DocumentEntity et nous pouvons l’utiliser pour accéder au contenu du document chargé dans Fleet.

 

Notre modèle de données d’entités est suffisamment flexible pour représenter non seulement les données, mais aussi le modèle de données lui-même. Supposons que nous devions développer un plugin (nous parlerons des plugins de Fleet dans un prochain article). Les plugins chargés font partie de l’état de Fleet. Tous les plugins partagent certaines données communes nécessaires pour une intégration fluide avec l’application. Cependant, chaque plugin a son propre état, décrit avec son propre modèle de données. Ce n’est pas un problème pour RhizomeDB. Nous pouvons représenter le modèle de données du plugin avec des entités. Lorsque nous chargeons un plugin, nous chargeons également son modèle de données en tant que nouvelle entité. Par conséquent, le système de gestion d’états de Fleet est prêt à accepter les données d’état du plugin.

 

Représentation d’état en tant que triplet

 

Nous ne stockons pas les objets que nous fournit notre API pour travailler avec des entités en tant que tels. Nous les représentons sous forme de triplets : [entity_id, attribute, value]. Nous appelons ces triplets datoms (ce terme fait référence à la base de données Datomic, sur laquelle nous nous sommes basés pour modéliser nos structures de données). 

 

Supposons que l’id de l’entité d’un fichier donné faisant référence à un document est 18, et que l’id de l’entité du document correspondant est 19. Les données seront stockées en tant que triplets :

 

  • [18 :type DocumentFile]
  • [18 :document 19]
  • [18 :fileAddress "~/file.kt"]
  • [18 :readCharset "UTF-8"]

Notez que les propriétés des interfaces deviennent des attributs de triplets. Il existe également divers attributs, tels que :type, qui ont des significations particulières. Les types de valeurs dépendent des types de propriétés. Lorsqu’on fait référence à d’autres entités, les valeurs de propriétés sont des ID.

 

La structure de triplet apparemment primitive est assez efficace quand il s’agit d’interroger des données. Notre moteur est capable de renvoyer des réponses très rapides aux requêtes sous la forme d’un masque : [entity_id?, attribute?, value?], dans lequel n’importe quel composant peut être présent ou manquant. Le résultat d’une requête est toujours un ensemble de datoms qui satisfont le masque donné.

 

Par exemple, nous pouvons demander tous les noms de fichiers des fichiers de documents actuellement chargés :

 

[? :fileAddress ?]

 

Ou alors nous pouvons rechercher entity_id, qui correspond à un fichier avec le nom donné :

 

[? :fileAddress "~/file.kt"]

 

Pour la deuxième requête, l’ensemble de résultats ne peut pas comprendre plus d’une réponse en raison de la contrainte d’unicité.

 

Pour permettre une exécution suffisamment rapide des requêtes, RhizomeDB gère quatre index (chacun implémenté en tant que hash trie) :

 

  • Entité | Attribut | Valeur
  • Attribut | Entité | Valeur
  • Valeur | Attribut | Entité
  • Attribut | Valeur | Entité

La famille de fonctions lookup* de l’API RhizomeDB opère sur ces index pour trouver les triplets correspondants et construire les objets d’entités résultants.

 

RhizomeDB s’inspire fortement de Datomic, mais apporte plusieurs idées nouvelles, telles que le suivi de lecture et la réactivité des requêtes, ce qui fonctionne avec notre cas d’utilisation. Ces fonctionnalités nous permettent de faire face aux changements d’état, comme nous allons le voir bientôt.

 

Comment gérer le changement ?

 

Un état immuable n’a rien de bien intéressant. Cela devient intéressant lorsque nous effectuons des modifications. Nous aimerions savoir ce qui a changé dans l’état et quels éléments de l’interface utilisateur doivent être mis à jour. Pour gérer les modifications, nous avons implémenté les trois idées suivantes :

 

  • Nous enregistrons de façon précise ce qui a changé en tant que nouveauté liée au changement.
  • Nous effectuons un suivi des recherches que font les lecteurs.
  • Nous déterminons quelles requêtes donneraient de nouveaux résultats en raison de ce changement.

Examinons ces idées plus en détail et voyons comment elles fonctionnent dans Fleet.

 

Valeurs de nouveauté

 

Souvenez-vous que nous cherchons autant que possible le maintien de l’immuabilité, nous ne sommes donc pas autorisés à modifier les valeurs. Rappelez-vous aussi que notre état prend la forme d’un instantané contenant un ensemble de triplets avec des identifiants (ID) d’entités, des attributs et leurs valeurs, représentant les entités de données correspondantes. Au lieu de modifier les valeurs des attributs, nous produisons un nouvel instantané d’état avec la nouvelle valeur de l’attribut que nous voulons modifier. La modification consiste alors simplement dans la suppression d’une ancienne valeur et l’ajout d’une nouvelle. Par exemple, pour renommer un fichier, nous procédons de la façon suivante :

 

- [18 :fileAddress "~/file.kt"]
+ [18 :fileAddress "~/newFile.kt"]

 

Notez que ces deux opérations doivent être exécutées dans une transaction, à défaut de quoi, l’état n’aura pas de nom de fichier. L’exécution de cette transaction génère un nouvel instantané d’état avec un nouveau nom de fichier.

 

Finalement, toute modification est juste un ensemble de retraits et d’ajouts de datoms. De nombreux retraits et ajouts pour différents entités et attributs peuvent résulter d’une transaction. De plus, la différence entre deux instantanés est aussi un ensemble de retraits et d’ajouts de datoms. À partir des identifiants des entités et des attributs de l’ensemble de modifications nous pouvoir savoir précisément quels composants d’état ont été modifiés lors d’une transaction. Cela ce que l’on appelle la nouveauté liée au changement. Une fois la transaction exécutée, nous enregistrons ces valeurs de nouveauté.

 

Suivi de lecture et réactivité des requêtes

 

Nous savons que les lecteurs accèdent aux données de l’état via des requêtes. Les requêtes ont la forme d’un masque. Il est facile de suivre l’ensemble des masques depuis une fonction donnée. Lorsque nous avons ces informations pour toutes nos fonctions, nous pouvons déterminer quelles fonctions dépendent de quel masque.

 

Une fois toutes les modifications réalisées, nous obtenons ses valeurs de nouveauté. En examinant tous les masques interrogés, on peut voir quelles requêtes sont affectées par le changement. Grâce au suivi de lecture, nous savons désormais quelles fonctions sont affectées. Par conséquent, nous pouvons invalider les éléments de l’interface utilisateur qui appellent ces fonctions. Cela augmente la réactivité de l’interface utilisateur.

 

Le suivi de lecture ne nous sert pas uniquement à mettre à jour les éléments de l’interface utilisateur. Il s’agit d’un mécanisme général qui permet d’exploiter des schémas utiles pour la programmation réactive. Par exemple, si nous avons une fonction qui interroge l’état, nous pouvons facilement la transformer en flux asynchrone. Chaque fois que des changements d’état influent sur le résultat d’une telle fonction, nous émettons un nouvel élément de flux. Nous pouvons également mettre les résultats d’une requête en cache en toute sécurité, sans risquer d’avoir des valeurs obsolètes dans le cache. Lorsque la valeur est mise à jour dans l’état, nous le savons immédiatement.

 

En résumé

 

Dans cet article, nous avons utilisé un modèle temporel à époques via une série d’instantanés immuables, et construit une représentation de données intelligente afin de maintenir notre état. Nos données existent à deux niveaux : en tant qu’entités de données pratiques pour le travail des développeurs et en tant que triplets pour une recherche efficace. Lorsque nous effectuons une modification, nous enregistrons ce qui a été modifié, déterminons qui est intéressé par ces changements et les utilisons pour mettre à jour les éléments de l’interface utilisateur correspondants.

 

Maintenant que vous avez toutes ces informations, nous allons pouvoir parler de la nature distribuée de l’état de Fleet et des mécanismes transactionnels qui nous permettent de le faire évoluer de façon cohérente. Nous verrons cela dans le prochain article de cette série. Restez à l’écoute !

Auteur de l’article original en anglais :

 

Delphine Massenhove

Vitaly Bragilevsky

image description

Discover more