Les contraintes des systèmes distribués

Cet article a pour but de discuter des problèmes fondamentaux que posent les systèmes informatiques distribués. Il aborde des questions un peu pointues d’informatique théorique et risque de paraître sibyllin au néophyte. Cette complexité est malheureusement nécessaire afin d’atteindre le plus rapidement possible la frontière technique et aborder les problèmes algorithmiques dans une certaine profondeur pour pouvoir en dire plus que des banalités. Au travers de cet article, je souhaite tenter d’expliquer en quoi des réseaux sociaux distribués comme diaspora* posent des problèmes d’un genre nouveau et que certaines fonctionnalités classiques comme l’édition de messages — facilement implémentable sur n’importe quel réseau social centralisé — deviennent extrêmement compliquées à mettre en œuvre dans le cadre d’un réseau social distribué.

Internet et les systèmes distribués

Internet a produit dans le domaine des systèmes de communications une révolution en permettant de bâtir des réseaux d’une forme nouvelle. Cependant, et bien que c’est ce qu’on lise un peu partout sur le web, internet — si l’on l’amalgame à l’ensemble de ses applications — est un réseau acentré — l’ensemble du réseau n’est pas contrôlé par un seul gros nœud ou un ensemble réduit de gros nœuds — mais pas décentralisé —  chacun de ses nombreux nœuds ne contrôle qu’un ensemble fini et restreint du réseau et non pas une grosse partie du réseau, potentiellement des parties aussi contrôlées par d’autres nœuds. Pour le démontrer, je prendrai deux des plus célèbres applications d’internet : le web et l’email.

Le web est en effet une application acentrée. Il n’existe pas un très gros site web ou un petit ensemble de très gros sites web qui représente(nt) la totalité de l’application et ladite application est elle-même extensible — il est possible de créer un nouveau site web sans modifier les sites web pré-existants. Cependant, l’application est tout de même centralisée : chaque site web n’est hébergé que sur un, et un seul, serveur à la fois et ne gère qu’une, et une seule base de données à la fois[1].

L’email, quant à lui, est effectivement une application décentralisée mais faisant intervenir un ensemble limité d’utilisateurs. En effet, il est assez rare que l’on poursuive une conversation mail avec plusieurs milliers d’utilisateurs. Cependant, lorsque cela arrive, la solution de gestion directe est alors de recentraliser l’application au travers des mailing-lists. Les utilisateurs, croyant discuter avec plusieurs centaines ou milliers de personnes, ne discutent en fait chacun qu’avec un seul utilisateur : le serveur de mailing-list. L’application, si elle est effectivement décentralisée, ne peut pas supporter la montée en charge facilement et ne peut donc pas constituer une réponse appropriée aux problèmes que posent les réseaux sociaux distribués.

Au travers de ces deux exemples, nous avons donc cerné deux propriétés que doit présenter un réseau social distribué pour fonctionner :

  • la décentralisation en ce qu’elle constitue sa définition,
  • la résistance à la montée en charge.

La résistance à la montée en charge est le plus gros problème que rencontre un réseau comme diaspora* : une conversation publique doit pouvoir faire intervenir plusieurs centaines ou milliers d’utilisateurs sans perdre en cohérence au fil du temps.

Le théorème CAP

Au tournant des années 2000, quelques gros sites à fort trafic comme Google ou Facebook ont atteint une masse critique d’utilisateurs journaliers telle que leurs serveurs furent mis à rude épreuve. Une épreuve si rude, en fait, qu’est apparu le besoin de créer un nouveau type de bases de données conçues pour pouvoir répartir à la fois physiquement et logiquement la charge sur plusieurs machines. Ces bases de données sont appelées bases de données à grappes de nœuds ou, plus communément, par leur nom commercial de big data. L’idée derrière ces bases étant de posséder en plusieurs endroits une copie des données — un nœud — mais de manipuler les données comme s’il n’existait qu’une seule base. Les bases de données à grappes de nœuds ont pour objectif de se rendre résistantes au pannes.

Auparavant, pour parvenir à ce but, la solution classique était d’effectuer régulièrement des sauvegardes multiples et complètes de la base en plusieurs endroits. Cette solution, cependant, laisse reposer la disponibilité des données que sur une seule base si bien que si celle-ci tombe en panne, il faut alors dresser une nouvelle base et restaurer les données depuis la sauvegarde la plus récente. Avec les contraintes de disponibilité pesant sur des sites à fort trafic comme Google ou Facebook, cette solution était devenue inenvisageable.

C’est alors tout un pan de l’informatique théorique qui s’est créé et développé autour de ces bases à grappes de nœuds avec une première formulation théorique des contraintes sous la forme du théorème de Brewer ou théorème CAP[2]. Ce théorème affirme qu’un système distribué peut, au maximum, ne présenter que deux des trois propriétés suivantes :

  • cohérence des données (Consistency)
  • disponibilité (Availability),
  • résistance au partitionnement (Partition)

La cohérence est la propriété selon laquelle la donnée est la même sur tous les nœuds, la disponibilité est la possibilité d’accéder à la donnée sur tous les nœuds à un même instant t et la résistance au partitionnement est une propriété intrinsèque aux systèmes distribués[3]. Il s’agit donc alors de faire un choix entre la cohérence et la disponibilité.

Dans le cas d’une base à grappe de nœuds, le choix se présente ainsi :

Soit A et B deux utilisateurs du système, soit N1 et N2 deux nœuds du système. Si A modifie une valeur sur N1, alors pour que B voie cette valeur sur N2 il faut attendre que N1 et N2 soient synchronisés.

Si N1 et N2 doivent toujours servir des valeurs cohérentes, alors il y a un temps incompressible entre le début de l’écriture, la synchronisation et la lecture suivante. Sur un système très chargé et très vaste, ce temps incompressible va considérablement influencer la disponibilité et la résistance au morcellement. Il existe bien évidemment des techniques pour optimiser ce temps mais plus le système est vaste, plus il est difficile à réduire.[4]

La solution est donc soit d’éteindre tous les autres nœuds le temps de répliquer la donnée — perte en disponibilité — soit de perdre en cohérence le temps que la donnée soit répliquée. Dans la cas d’un réseau social comme diaspora*, le choix est cependant évident : si les pods sont les nœuds de notre exemple, ceux-ci sont donc indépendants et il est inconcevable que l’on rende un pod indisponible le temps de synchroniser les données.

Les problèmes induits par les réseaux sociaux distribués.

Comme nous venons de le voir, lorsqu’une donnée est créée ou modifiée — par exemple lorsqu’un utilisateur rédige un nouveau post ou écrit un commentaire sur un post existant — il est nécessaire de sacrifier momentanément la cohérence des données. On sait alors que, pendant un laps de temps, les posts ou commentaires ne seront pas dans le même état entre plusieurs pods. Cet état de fait n’est cependant pas vraiment grave car la nature de réseau social de diaspora* le permet. Aucune application critique ne dépend de la cohérence des données et les utilisateurs ne s’offusqueraient pas qu’un message n’arrivât pas dans la minute suivante. Tout l’enjeu, cependant, repose sur la détection de ces incohérences et leur correction rapide. Et là, c’est un peu plus velu. Car la gestion des incohérences présente trois gros problèmes.

Le premier, c’est évidemment qu’il faut les détecter. Là, le problème prend alors une complexité algorithmique exponentielle car si l’on considère que chaque pod de chaque participant à une conversation peut modifier cette conversation, lorsque l’une de ces modifications est introduite dans le réseau, tous les pods doivent contacter tous les autres pods pour savoir qui possède la dernière version de la conversation afin de ne pas introduire des incohérences dans le flux de ladite conversation. Si celle-ci est publique, on parle alors de l’intégralité des pods qui composent diaspora*[5]. Bien évidemment, ce problème peut être résolu en introduisant des métadonnées aux modifications. Par exemple, en incrémentant un numéro de version ou en changeant une date de modification. Mais alors apparaît un second problème.

Comme les pods sont sur un pied d’égalité, chacun d’entre eux peut introduire à tout moment une modification régulièrement comme tous les autres. Si plusieurs utilisateurs introduisent alors, dans un laps de temps court, chacun une modification différente, la conversation perd sa propriété de linéarité et, quelque soit le numéro de la version, rien ne garanti qu’une modification présente la qualité d’antériorité à une autre et, par corollaire, rien ne garanti qu’une version de la conversation présente une qualité d’antériorité sur un serveur ou sur un autre. L’on pourrait alors se retrouver dans un cas paradoxal où deux versions différentes de la conversation présentent le même numéro de version ou la même horodate. Ce problème — déjà complexe lorsque les modification ne sont que des ajouts (nouveau commentaire) — grandi encore s’il s’agit de laisser l’utilisateur modifier un commentaire ou le post lui-même. Un autre utilisateur pourrait alors réagir à quelque-chose qui vient d’être réécrit. Si la réécriture n’a pas été répercutée sur tous les pods concernés, le conversation pourrait tourner au quiproquo le plus gênant. C’est déjà le cas lorsqu’un utilisateur commente un post ou un commentaire qui a été supprimé entre-temps.

Le troisième problème, c’est lorsqu’un ou plusieurs pods sont plus chargés que d’autres et traitent donc les informations plus lentement que les pods plus petits[6]. Lorsque deux modifications sont introduites dans un temps court depuis deux pods différents, il peut alors arriver qu’elles soient noyées parmi d’autres modifications et que l’une soit traitée beaucoup plus tard que l’autre. Les deux modifications sont alors traitées presque simultanément sur les petits pods mais la latence s’agrandit considérablement sur les gros pods. C’est ce qui arrive lorsque vous voyez des gens répondre à un commentaire que vous ne voyez pas — parce qu’il a déjà été traité par les autres pods mais pas encore par le vôtre.

C’est en ça que les réseaux sociaux distribués induisent des problématiques nouvelles. On ne peut pas, comme dans le cas des bases de données à grappes de nœuds, faire de présupposés sur le matériel sur lequel tournera l’application ou le réseau auquel elle sera connectée. C’est pourquoi il est impossible de concevoir des solutions en Java comme Apache Cassandra[7] ou Google BigTable[8]. L’application devrait pouvoir tourner sur un Raspberry Pi comme sur un serveur qui carbure au Xeon et être disponible quelque soit l’état du réseau.

Un petit mot sur XMPP

Récemment, j’ai eu un petit échange avec edhelas, le très sympathique créateur du réseau social Movim. Le bougre avait écrit une diatribe vantant les mérites du protocole XMPP. Son billet, quoi qu’intéressant, se leurre cependant, je pense, sur les capacités du protocole XMPP à gérer un réseau social distribué. J’ai répondu à quelques uns de ses arguments dans les commentaires mais le reste de ma réponse ne pouvait pour moi ne s’écrire qu’à la lumière des éléments présentés plus haut.

XMPP est, à la base, un protocole permettant de faire de la messagerie instantanée. En cela, il souffre donc, pour moi, du même problème que l’email : il n’est conçu que pour gérer des conversations de dimension limitée, c’est à dire, avec un nombre de participants fini et restreint. Certes, edhelas ne se fourvoie pas lorsqu’il avance l’avantage du protocole à gérer nativement l’asynchrone. Cependant, en se focalisant sur cet aspect, il manque la plus grosse partie du problème : la détection et la correction des incohérences à une échelle infiniment grande et qui n’est pas gérée nativement par le protocole (parce que le problème ne se présente que marginalement à l’échelle d’un conversation à peu d’utilisateurs).

Mais je peux comprendre qu’il soit passé à côté de cette problématique. Les réseaux sociaux reposant sur XMPP — principalement Movim et Salut à toi — comportent très peu de nœuds et un nombre relativement faible d’utilisateurs comparé à diaspora*. Il est donc logique que leurs développeurs respectifs n’aient pas encore rencontré les problèmes d’incohérences induits par des méga-pods comme JoinDiaspora ou Framasphère. Cependant — et comme cela reste le problème majeur posé par les réseaux sociaux décentralisés — ce seul point — bien plus que le manque des fonctionnalités que je cite dans les commentaires de son billet — fait à lui seul de XMPP un protocole fondamentalement pas encore prêt pour faire du réseau social.

Notes de bas de page :
  1. Moyennant les sites miroirs qui posent les même problèmes que ceux abordés plus bas.
  2. Conjecture de Brewer, MIT, 2002
  3. Puisque la donnée existe théoriquement sur plusieurs nœuds, si un ou plusieurs nœuds sont séparés du reste du réseau par une panne, la donnée reste disponible
  4. Wikipédia, bitches.
  5. Ce qui fait un sacré nombre
  6. C’est notamment très visible sur les méga-pods comme JoinDiaspora ou Framasphère
  7. Base à grappes originellement développée par Facebook
  8. Base à grappe de chez Google

Déjà un avis pertinent dans Les contraintes des systèmes distribués :

Les commentaires sont fermés.