Julien Sopena

TD 08 – Gestion de cache en réparti

Exercice 1: Gestion de cache en réparti

On veut gérer un cache dans un système de fichiers réparti. Un site serveur gère les données sur disque. Les sites clients accèdent à ces données en faisant des requêtes au serveur. Chaque client possède un cache. Les lectures et écritures se font directement dans le cache. Dans un premier temps les écritures sont directement envoyées sur le serveur.

Question 1.1 )

Pour assurer une cohérence forte, le serveur diffuse chaque mise à jour à tous les clients possédant une copie. Programmez en pseudo-code les fonctions suivantes :
Lire(donnée) :
appelée par le client
Ecrire(donnée) :
appelée par le client

Vous programmerez aussi les fonctions nécessaires au serveur en définissant les structures de données utiles. Quelle hypothèse faut-il faire sur les canaux de communication (justifiez) ?

Question 1.2 )

Sachant qu'une donnée est utilisée en moyenne chez M clients, quelle est la complexité moyenne (en nombre de messages) de l'algorithme proposé à la question 1 ?

Question 1.3 )

Pour réduire la charge des serveurs, lorsqu'un client modifie des données, il diffuse directement à tous les autres clients un message invalidant la donnée dans leur cache. La donnée modifiée n'est pas envoyée au serveur. Quel est l'avantage de cette stratégie par rapport à celle de la question 2 ?

Question 1.4 )

Décrire un algorithme permettant à un client de charger la dernière version d'une donnée sans effectuer aucune diffusion. Vous définirez clairement les structures de données et variables utiles sur chaque site. Vous considérerez les hypothèses suivantes :
H1 :
les mises à jour ne sont pas transmises au serveur
H2 :
pour réduire la charge du serveur celui-ci ne connaît que le premier site client possédant une copie de la donnée.

Question 1.5 )

Exécuter l'algorithme de la question 4 sur le scénario suivant :
  • Les clients C1, C2 et C3 modifient la donnée A.
  • Initialement A = 0 sur le serveur S et A n'est présente dans aucun cache.
  • On souhaite qu'au final A soit égal à 16.
Vous représenterez clairement les échanges de messages.

Question 1.6 )

De manière générale, quelle est la complexité moyenne en nombre de messages de votre algorithme ?

Question 1.7 )

Peut-on réduire le nombre de messages lorsque un client réclame à nouveau une donnée qu'il possédait préalablement ? Si oui, modifiez votre algorithme en conséquence.

Exercice 2: Etude de la diffusion

Question 2.1 )

Des clients envoient des requêtes à 3 serveurs répliqués. 8 Quels sont les avantages et inconvénients de répliquer les serveurs

Question 2.2 )

Les serveurs gèrent des mises à jour sur une variable a. Deux clients C1 et C2 diffusent à chaque fois leurs mises à jour aux trois serveurs. Soit le scénario suivant, où les points représentent les diffusions aux serveurs :

Quelles sont les valeurs possibles de a sur les différents serveurs si les clients utilisent un ABCAST, un CBCAST et un ACBCAST ? Dans quels cas peut on avoir des valeurs différentes sur les serveurs ?

Designed by OWSD.org. Valid CSS & XHTML
Ce site et l'ensemble de son contenu est mis à disposition sous un contrat Creative Commons.
Creative Commons License