Remplacement de cache et éviction de répliques

Libérer de l’espace mémoire

L’algorithme présenté ici permet de sélectionner quelle donnée ôter du cache quand celui-ci est plein et qu’une nouvelle donnée doit être répliquée localement. Nous allons tout d’abord voir le principe, puis l’algorithme lui-même, avant de l’illustrer par un exemple. 

Principe

Comme dans LRU, on conserve une liste d’identifiants des données triés par ordre d’accès. Cette liste est mise à jour à chaque accès local, en plaçant l’identifiant de la donnée utilisée en fin de liste. Quand un remplacement de cache est demandé, on choisit la donnée à éliminer selon le critère suivant : 1. On parcourt la liste et on cherche la première donnée dont le nombre de répliques est supérieur au nombre de répliques de garde, nécessaire à la disponibilité des données. Si aucune donnée ne satisfait cette condition, on passe à l’étape suivante. 2. On parcourt la liste à partir de la fin, et on cherche la donnée avec le plus grand nombre de répliques. Si deux données ont le même nombre de répliques, on sélectionne celle qui a été utilisée le moins récemment. Il est possible que toutes les copies disparaissent suite au remplacement de cache si : – de manière concurrente, tous les hôtes décident de la supprimer. – tous les hôtes disparaissent avant que de nouvelles copies n’aient été créées 165 def cooperativeLRU(self): rmCandidate= self.sorted_LCL_AccessList[0] i=1 while datas[rmCandidate].howMany()<=rate*len(peers) and i0 : postMaxPeer=self.sortedAccessList[posMax] currentPeer= self.sortedAccessList[j] if datas[postMaxPeer].howMany()<=datas[currentPeer].howMany() : posMax=j j-=1 rmCandidate=self.sortedAccessList[posMax] self.rmReplica(rmCandidate) self.sortedAccessList.remove(rmCandidate) Figure 7.1 – Algorithme de remplacement de cache coopératif

Algorithme

La figure 7.1 présente l’algorithme Cooperative-LRU. On peut voir les variables suivantes : – sorted_LCL_AccessList : la liste des données présente dans le cache, triée par date d’accès. – peers : la liste des pairs dans le groupe stable. – rate : le taux de réplication demandé. – datas : une structure de données qui stocke les copies locales, et la liste des autres hôtes.

Exemple

La figure 7.2 présente un exemple d’application de notre algorithme, dans un cas où l’application de LRU conduit à la perte d’une donnée. Il se déroule en 2 étapes. Etape 1 : A accède à la donnée 10, B accède à la donnée 3 1. La donnée 10 n’est pas présente sur A, le cache de A n’est pas plein, 10 est donc répliqué sur A. 2. La donnée 3 n’est pas présente sur B, le cache de B est plein, B exécute donc l’algorithme de remplacement de cache. 3. 2 algorithmes : LRU : la donnée sortie est 1. Cooperative-LRU : dans le réseau il existe : – 2 copies de 1, 2 étant le nombre de copies de réserve, on ne l’élimine pas, – 3 copies de 5, la donnée sortie est donc 5. 166 7. Remplacement de cache et éviction de répliques 5 6 2 3 5 8 2 1 3 1 8 10 4 9 7 6 6 4 9 5 7 10 C B A D 10 3 2 3 5 8 7 4 5 5 8 1 6 4 9 10 6 6 9 3 2 7 10 C B A D 10 3 2 3 5 8 7 4 5 1 8 1 6 4 9 10 6 6 9 3 2 7 10 C B A D A: accès 10, B: accès 3 1 5 Accès le plus récent A : accès 8 8 5 2 3 5 8 7 9 10 5 8 4 6 4 9 10 6 6 3 5 2 7 10 C B A D 8 3 2 3 8 7 4 10 1 8 1 6 4 9 10 5 6 9 5 2 7 10 C B A D 1 3 LRU Cooperative-LRU Donnée entrant Donnée sortant Cooperative LRU 2 repliques Figure 7.2 – Remplacement de cache, Cooperative LRU vs LRU Les modifications des états des caches sont propagées avant l’étape 2. Etape 2 : A accède à la donnée 8 1. la donnée 8 n’est pas présente sur A, et le cache de A est plein, A exécute donc l’algorithme de remplacement de cache. 2. 2 algorithmes : LRU : la donnée sortie est 1. Cooperative-LRU : dans le réseau il existe : – 2 copies de 1, – 2 copies de 4, – 2 copies de 9, – 3 copies de 3, la donnée sortie est donc 3. On voit donc qu’à l’issue de ces deux étapes, la donnée 1 est perdue si on utilise LRU. En revanche, Cooperative-LRU préserve la donnée 1.

Diminuer la charge réseau

Chaque nouvelle réplique d’une donnée génère une charge liée à la maintenance de la cohérence. Toutes ces répliques ne sont pas nécessairement utiles cependant : elles peuvent avoir été créées suite à un accès passé, mais ne plus intéresser l’utilisateur. Le trafic généré par ces répliques est donc superflu. Afin de diminuer la charge du réseau, nous voulons donc éliminer ces répliques. 167 On veut donc pour ce faire déterminer l’utilité de la copie locale d’une donnée. Nous allons d’abord voir le principe appliqué puis l’algorithme, avant de présenter un exemple.

Principe

Une réplique peut avoir été créée à deux fins : soit elle est utilisée localement, soit elle est nécessaire pour maintenir la disponibilité des données en cas d’événement de mobilité. Si une réplique n’est dans aucun de ces deux cas, on peut l’éliminer. Cependant, il n’est pas nécessaire d’éliminer toutes les répliques de ce type : on préfère garder des répliques de données tant qu’elles n’ont pas d’impact sur l’utilisation du réseau, afin d’être plus susceptible de tolérer une partition. La décision d’éliminer une copie superflue se fait donc localement, si la fréquence d’accès depuis l’extérieur dépasse la fréquence d’accès local. Pour ce faire, à chaque donnée on associe un compteur d’accès local cptL, et un compteur d’accès extérieur cptE, afin de calculer : – fE la fréquence de mise à jour depuis l’extérieur – fL la fréquence d’accès à la donnée localement Les compteurs sont incrémentés à chaque accès à la donnée, depuis le terminal ou depuis le réseau. L’algorithme d’éviction est ensuite appliqué périodiquement, avec une période T. Tout d’abord, les fréquences d’accès sont mises à jour : – fE = 0.5 ∗ fE + 0.5cptE – fL = 0.5 ∗ fL + 0.5cptL Pour chaque donnée, on effectue ensuite les tests suivants : 1. le rapport fL fE est-il inférieur à EvictThreshold, que nous avons fixé à 0,1 ? 2. le nombre total de répliques dans le réseau est-il supérieur au nombre de répliques désiré pour maintenir la disponibilité des données ? Alors on peut éliminer la donnée du cache, et on diffuse un message aux autres hôtes pour le signaler.