Cache & Flux

Ce très court travail a été une de mes premières expérience dans le milieu de la recherche. Ce travail marquera le début d’une grande collaboration avec Claudia Roncancio et Cyril Labbé. Il a été effectué en tant que module optionnel de la deuxième année ENSIMAG (2007-08) : TER (Travaux d’Etude et de Recherche). A l’époque, je n’avais aucune connaissance sur les flux de données et encore moins le domaine des capteurs. Conclusion : le résultat est vraiment pas top comparé à la complexité du domaine et à ce que je suis capable de faire maintenant.

Par contre c’est assez marrant, dernièrement l’idée a resurgit lors d’une discussion. Le point important étant : est-ce que les n-uplets dupliqués ont une importance dans les flux de données ? Il faudra que je l’implémente un jour dans Astral…

Le contexte

Le laboratoire LIG, Laboratoire d’Informatique de Grenoble, fait partie des grands pôles de la recherche sur Grenoble. Il est notamment spécialisé dans le domaine des systèmes d’informations (peu de mathématiques appliqués). L’équipe dans laquelle j’ai travaillé est l’équipe HADAS, ou encore Heterogenous Autonomous DAtabases Systems, qui s’intéresse notamment au domaine vaste des bases de données. Plus précisément, l’équipe concentre ses recherches sur la gestion ubiquitaire des données et services.

Le projet sur lequel je me suis penché est au centre d’un domaine très actif depuis quelque temps : la gestion de flux de données et le domaine des capteurs. En effet, le traitement des bases de données a un lourd passé, mais les flux de données sont très jeunes. La principale différence est que le fonctionnement est pris à l’inverse. Dans les SGBD classiques, on stocke les données de façon persistante et on traite des requêtes une seule fois, alors que dans les Systèmes de Gestion de Flux de Données (SGFD), on exécute de façon permanente les requêtes et les données sont transitionnelles. Les efforts se sont donc concentrés pour établir un comportement de type base de données classiques, avec des requêtes déclaratives (SQL par exemple).

Le problême

Si on considère un énorme parc de capteur. On voudrait pouvoir interroger l’ensemble de ceux-ci par des requêtes continues telles que : Rapporter toutes les 3 minutes l’ensemble des capteurs dont la température a excédé 15 degrés. Les problèmes apparaissent lorsqu’il y a une grande quantité de données, le système ne pourra sûrement pas traiter le tout.

Les systèmes hiérarchiques permettent de distribuer les différents calculs afin d’avoir un plan d’exécution répartis.

Mon travail a été de découvrir les opportunités de caches dans ces systèmes. Car sur des SGBD classiques c’est une technique couramment appliquer pour éviter les surcharges, or il n’y a pas d’équivalent pour les systèmes de capteurs.

Mon travail

L’assimilation des principes et des travaux existants ont déjà pris du temps de par leur complexité et leur importance (travaux de Levent Gurgen (thèse LIG), Tamer Omzu ou encore Stanford). Toutefois au fur et à mesure de mes lectures, j’ai pu commencer une ébauche de résultat.

Dans les SGFD courants, on traite toutes les données et non seulement les modifications des états. Par exemple, un capteur de température montrant 15°C pendant plus d’une heure, alors on aura une grande quantité de traitement alors que le résultat n’aura pas changé. Une première idée est de stocker le tout dans un cache (pour y accéder à n’importe quel moment) et ne transmettre que les changements d’état. Après en avoir discuté avec mes encadrants, nous avons commencé à voir jusqu’où ce type de traitement pourrait être applicables. Plusieurs scénarios ont étés imaginés et le tout avait l’air d’être efficace notamment dans les gros traitements. Seulement des problèmes de sémantiques sont apparus. Pour l’instant, nous n’avions qu’une idéologie. Il nous fallait un support.

L’idée alors m’est venue d’utiliser la formalisation des opérateurs (comme la sélection, la projection, les agrégations) que l’on utilise pour construire le plan d’exécution. Un opérateur pour enregistrer dans le cache, et l’autre pour supprimer les doublons qui se répartirons sur les entrées et sorties des passerelles. A partir de là, une théorie plus propre était possible et donc après avoir établit certains critères d’applications, nous avons pu avoir une gestion de cache stable et effective.

Au final : moins de paquets à traiter, ce qui implique moins de phénomènes d’engorgements, et moins de calculs évidemment (très efficace sur les jointures). De plus nous avons permis une ouverture à un partage de ressources entre les différentes requêtes ! Le fait de mettre le tout dans un cache, permet de le partager et sous réserve d’une gestion de concurrence, on obtient des traitements uniques.

La solution globale n’est toutefois pas si simple, des détails dont je ne parlerai pas ici (on est déjà dans un domaine spécialisé) gênent le fonctionnement, la théorie au complet est disponible dans le rapport final en pièce jointe.

Première expérience

J’en profite pour dire que l’expérience de ces jeudi après-midi au 3ème étage du batiment D ont été un réel plaisir. A ceux qui hésitent encore sur leur carrière : c’est une option à prendre elle sans hésitation. Le travail y est certes un peu plus dense qu’une autre matière, mais ce n’est pas rester assis simplement à écouter ce qu’un professeur a à dire. Ici, c’est écouter les conseils de votre tuteur pour pouvoir faire avancer la recherche, on devient un membre actif.

Si on souhaite faire une carrière de chercheur, le TER ouvre quelques portes car cela constitue une première expérience. J’ai pu avoir un stage dans un grand labo à Dublin pour l’été suivant en partie grâce à cette expérience.

Le rapport TER