|
Introduction
Nous assistons actuellement à une évolution poussée de l’informatique dans
le domaine de la technologie notamment celle des réseaux informatiques. Ces
derniers offrent des débits de plus en plus élevés. Plusieurs ordinateurs
peuvent être interconnectés, permettant ainsi de cumuler leurs ressources en
mémoire et disque pour le stockage de données, et d’augmenter leur puissance
de calculs. De nouveaux concepts sont proposés pour désigner ces systèmes,
tels que : multi-ordinateur, ou Réseau de Stations de Travail « Network
of Workstation » ou, plus récemment, « Peer-to-Peer Computing »
ou « Grid Computing ».
Cependant, les applications actuelles ne tirent pas
profit maximum de ces avancées. Pour pallier à ce manque, une classe de
structures de données est apparue afin d’ouvrir de nouvelles perspectives
pour la gestion des données sur les multiordinateurs, il s’agit des
Structures de Données Distribuées et Scalable (SDDS). Elles sont dites
scalables car les performances d’accès sont indépendantes de la taille du fichier
SDDS. Les SDDS sont une
étape dans l’implémentation, à base du modèle client/serveur, des systèmes
de gestion de bases de données distribuées et scalables, qui, actuellement,
sont un challenge à relever.
Historique
Dans un premier
temps, des SDDS basées sur le
hachage ont été proposées tels que LH* et ses variantes, DDH et EH*,
celles-ci constituent une généralisation des algorithmes de
hachage classiques. Cependant, dans le cas où le fichier doit supporter des
requêtes par intervalles ou un parcours transversal de tous les
enregistrements, les structures de données ordonnées telles que les arbres B
offrent de bonnes performances par rapport aux techniques de hachage qui ne
préservent pas l’ordre. Sur cette base, une autre famille de SDDS a été
proposée pour construire des fichiers distribués qui préservent l’ordre des
enregistrements. Citons à cet égard : RP* et DRT.
Des recherches poussées au sein de l’équipe CERIA à l’université Paris 9
Dauphine sous la direction du Professeur W. Litwin, notamment sur LH*, ont
permis de construire de nouvelles structures
de données distribuées et scalable dites sécurisées et à haute disponibilité
parmi lesquelles
nous trouvons : LH*s, LH*m, LH*g, LH*RS,
... .
Une autre tendance dans les recherches sur les SDDS a été
initiée ces dernières années et concerne les SDDS multidimensionnelles
telles que k-RP,
k-DRT, etc.
Motivations
Cependant, une remarque importante concernant les SDDS
développées jusqu’à présent est qu’elle constituent toutes une
généralisation soit de certains
k-d-arbres
tels que les arbres B+ (RP*, k-RP*, Distributed B+-tree),
soit des les arbres de recherche (DRT, DRT*, k-DRT,...)
soit des techniques de hachage unidimensionnelles classiques.
Ceci nous a inciter à mettre en évidence une nouvelle
approche dans le domaine des SDDS, il s’agit de la conception de Structures
de Données Distribuées et Scalable à base du hachage multidimensionnel (Multidimensional
Hash-based
SDDS), et plus particulièrement,
le hachage par interpolation de W.A.Burkhard.
IH* constitue
la première SDDS multidimensionnelle à base du hachage. IH* supporte toutes
les opérations standards sur les bases de données distribuées. Son point le
plus forts est qu'elle supporte efficacement les requêtes à intervalles
exactes, partielles et totales (partial and exact match queries).
Deux contributions ont été déjà faites sur IH* :
·
IH* : A New Hash-Based Multidimensional SDDS. Workshop on Distributed Data &
Structures - WDAS-2002 Université Paris IX
Dauphine.
France. 20-23 Mars
2002.
·
Hachage Linéaire Multidimensionnel Distribué et Scalable. CARI’02 : 6ième
Colloque Africain sur
la Recherche en
Informatique. 14-17 octobre 2002 Yaoundé. Cameroun.
Définition et objectifs de la thèse
Le sujet de
thèse s’inscrit comme une suite du travail déjà entamé dans le cadre d’une
thèse de Magister (INI, 2002). L’objectif de la thèse est de réétudier la
SDDS IH* et d'effectuer des recherches approfondies sur tous ses aspects.
Ces études concerneront la perfectionnement du IH* (Protocole de
communication et architecture du système) et l'ajout des fonctions non
encore implémentées tel que la suppression et les requêtes par intervalles.
Les objectifs suivants sont à atteindre :
·
Evaluation des requêtes à intervalles parallèle :
nous avons montrer que le mode d’envoi ciblé du IH* constitue une
amélioration considérable par rapport aux autres modes. Une perspective
envisageable serait d’étudier des mécanismes plus optimaux de découpage et
de terminaison des requêtes parallèles qui permettent d’alléger les charges
sur les serveurs de données.
·
Etude d’une structure interne de la case IH* :
Etant donné que l’accès aux enregistrements au niveau d’une case est
séquentiel, la taille de cette dernière doit avoir une influence sur les
performances des serveurs SDDS. Une étude intéressante serait d’étudier une
organisation interne d’une case IH* plus optimales (IH*IH par
exemple). Il serait aussi intéressant d’étudier l’influence de la taille
d’une case sur le temps de réponse d’un serveur.
·
Politiques de scalabilité :
par scalabilité on entend
Plusieurs cases par serveur :
Une étude intéressante serait de traiter le cas de l’hébergement de
plusieurs cases de données sur un même serveur à l’instar des travaux de
R.Vingralek sur les SDDS DDH et LH*.
Un module de contrôle de charge du serveur :
il serait intéressant d’ajouter un module de contrôle de charge du serveur.
Ce module permettrait, à partir d’un certain seuil d’augmenter dynamiquement
le nombre de threads d’écoutes ou éventuellement le nombre de threads de
travail. Plusieurs problèmes peuvent se poser, tels que la gestion des ports
d’écoutes, l’information des clients de l’existence de tels ports, l’accès
concurrent aux files d’attentes, etc.
·
Introduction de la mémoire secondaire : toutes les SDDS déjà implémentées résident dans la
mémoire distribué du multiordinateur. On parle pour certaines variantes de
haute disponibilité, cela n'empêche pas de doter le système de gestion de
la SDDS d'un module de sauvegarde /restauration de/vers la
mémoires de masse pour des éventuelle opération de maintenance, transfert ou
même de mise à niveau (upgrading) du système SDDS lui-même.
·
La mesure détaillée des performances :
le premier prototype que nous avons développé ne nous a pas permis
d’avoir des détails sur les performances réelles de la SDDS IH*. Une
perspective intéressante serait d’implémenter un prototype plus complet sous
un environnement Windows ou Linux réel et de mesurer ses performances
réelles. Ce système ainsi développé doit être doté d’un
module de contrôle
de flux pour éviter le problème de perte
de messages UDP. Ce module doit également gérer les time-out,
les messages d’acquittement et les situations d’erreur.
Echéancier
1ière année :
- Etat de l’art sur les SDDS récentes ;
2ième année :
- Extension du protocole existant avec un module de contrôle de flux ;
- Etude de l’organisation interne d’un serveur SDDS ;
3ième année :
- Proposition d’un mécanisme d’exécution des requêtes par intervalles ;
- Etude de diverses politiques de scalabilité ;
4ième année :
- Mesure des performances et comparaison avec les SDDS concurrentes ;
- Rédaction et finalisation de la thèse.
|
