CTH* : exemple d'illustration | |||
|
|||
La
figure donne les états finaux des clients et des serveurs après
l'insertion de la séquence des 25 clés (chaînes de
caractères ) par les clients correspondants (4 clients): (1
js), (1 hw), (3 c), (2 gwmr), (3 g), (2 km), (4 zur), (1 ewg), (3 lewhv),
(2 nrq), (3 mf), (4 pem), (4 rl),
(2 bqyg), (3 v), (1 j), (2 qcm), (4 czxav), (2 lhgd), (3 z), (1 lrz),
(3 kiyfg), (4 pbtpr), (3 hpqtp), (4 h)
La figure montre 4 clients et 9 serveurs. Chaque client a sa propre fonction d'accès représentée par un arbre digital compact. Le fichier est distribué sur 9 serveurs à raison d'un serveur par case. Chaque serveur possède un intervalle indiquant l'ensemble des clés que le serveur peut abriter, un arbre digital compact gardant la trace des éclatements qui ont lieu sur ce serveur et une case contenant les articles insérés. Les arbres des clients représentent des vues du fichier. Ainsi, pour le client 1 avec son arbre e 0 g 4 k 1 | 2 il voit le fichier comme étant composé des serveurs 0, 4, 1 et 2 avec la partition suivante : [Petite, e] : 0 ; ]e, g] : 4 ; [g, k] : 1 ; ]k, Grande] :2. Pour le client 3, il y a la partition suivante : [Petite, g] : 0 ; ]g, k]: 1 ; [k, n] : 2 ; [n, r] : 3 ; ]r, Grande] :5. Aucune des deux partitions (vues) ne reflète la réalité. Si le client 1 recherche la clé ' g', il trouve le serveur 4. Si le client 1 recherche la clé 'j’, il trouve d'abord le serveur 1. Comme 'j’ n'appartient pas à l'intervalle de ce serveur, une erreur d'adressage apparaît. Le client met à jour son arbre avec l'arbre du serveur 1( selon l'algorithme A). Son arbre devient : e 0 g 4 h 1 j 8 k 7 | 2. La re calcul de l'adresse sur le nouvel arbre donne cette fois-ci le serveur 8, qui est le bon. Supposons maintenant que le client 2 veuille insérer la clé 'sdds' . l'application de son arbre sur cette clé donne le serveur 3. Bien que l'arbre du client 2 ne reflète pas la réalité, le client 2 trouve le bon serveur car la clé recherchée appartient à l'intervalle du serveur 3. Le serveur 3 ne peut contenir la nouvelle clé comme sa case est pleine. Une collision apparaît donc sur ce serveur. Elle est résolue comme suit : on considère la suite de clés ordonnée composée des clés du serveur 3 et de la nouvelle clé : 'pbtpr', ' pem', ' qcm', ' rl', 'sdds'. Ensuite, on détermine la plus petite séquence de digits ( caractères) qui permet de distinguer la clé du milieu (‘qcm’) de la dernière clé (‘sdds’). Il s'agit donc de la séquence 'q'. L'arbre du serveur 3 qui est r 3 | 5 devient q 3 r 9 | 5. le serveur 9 est crée avec un arbre vide (| 0) et l'intervalle ]r, Grande] . Les clés sont divisées entre les serveurs 3 et 9 de telle sorte que les clés strictement supérieurs à ' q' migrent vers le nouveau serveur. Donc, après l'éclatement, les clés ‘pbtpr’, ‘pem’, et ‘qcm’ restent dans la serveur 3 alors que les clés ‘rl’ et ‘sdds’ vont vers le serveur 9. Considérons la situation suivante qui est rare. Soit à insérer la clé 'me’ par le client 2. L'application de l'arbre du client (fonction d'accès) sur le client 2 donne le serveur 1. La clé ‘me’ n'appartient pas à l'intervalle de ce serveur. L'arbre du client est modifié comme suit g 0 h 1 j 8 k 7 n 2 | 3. La ré application du nouvel arbre sur le client donne cette fois-ci le serveur 7. Comme 'me' n'appartient pas à l'intervalle du serveur 7 et comme celui-ci a un arbre vide (| 7) , on est en présence d'une impasse. Elle est résolue par l'envoi d'un multicast à tous les serveurs. Le serveur 6 répond favorablement et la clé 'm' y est insérée. L'arbre du client 2 est mis à jour ( selon l'algorithme B) et devient définitivement g 0 h 1 j 8 k 7 n 6 | 3. Le Multicast
est aussi utilisé quand un client rencontre un noeud Nil
quand il applique son arbre sur une clé donné. Il remplace alors dans
son arbre Nil par le serveur trouvé par multicast. |