Tharkun homelands

En informatique, il existe des problèmes récurrents. Le stockage de fichiers de cache en est un. Mais revenons d’abord sur la notion de fichier de cache. Même en optimisant le système, certains traitements peuvent prendre du temps, temps qu’il n’est pas permis de répercuter lors des nombreux autres traitements. Pour illustrer ce propos, prenons l’exemple des droits des utilisateurs. Le calcul des droits d’un utilisateur peut être long, plus ou moins compliqué mais une fois calculé, il est inutile de le recalculer tant que les droits n’ont pas changé. L’utilisation de fichiers de cache permet dans ce cas précis de faire le calcul une fois, d’écrire un fichier avec le résultat du traitement, puis d’aller lire le fichier. Lire un fichier rend ici la récupération des droits de l’utilisateur beaucoup plus rapide.

Après avoir identifié des fichiers de cache à créer il est nécessaire de voir le stockage. Il existe pour cela plusieurs solutions. Dans toute l’explication qui va suivre, on considérera que le stockage de nos fichiers se fait dans le répertoire /var/cache/user-rights/. De plus chaque utilisateur correspond à un numéro qu’on appellera « id ».

Stocker dans un répertoire

La première solution à laquelle pensent souvent les débutants est de stocker tous les fichiers dans le répertoire. On se retrouve ainsi avec l’arborescence suivante :

/var/cache/user-rights/145.cache
/var/cache/user-rights/156.cache
/var/cache/user-rights/28.cache
/var/cache/user-rights/2456.cache
/var/cache/user-rights/58964.cache

Cette méthode est très simple de conception. Elle est très adaptée lorsque le nombre maximum de fichiers de cache est peu élevé. Cette méthode peut s’avérer très dangereuse si le nombre de fichiers croit beaucoup et que l’on a pas d’accès ssh pour faire le ménage. Lister via un client ftp le contenu d’un tel répertoire ayant un grand nombre de fichiers devient tout simplement impossible. On peut ainsi perdre le contrôle sur le répertoire ce qui n’est évidemment pas acceptable.

Créer une arborescence

Tout mettre dans un même répertoire pose également un problème physique d’accès aux données. En effet les systèmes au delà d’un certain nombre de fichiers dans un même répertoire deviennent plus lents. La récupération des droits d’un utilisateur devient ainsi plus lente et l’utilisation de fichiers de cache perd de son efficacité.

La solution à laquelle on pense instantanément est de créer une arborescence de fichiers dans notre répertoire de cache. Pour cela, il suffit de découper l’ »id » utilisateur. On obtient donc l’arborescence suivante:

/var/cache/user-rights/1/4/145.cache
/var/cache/user-rights/1/5/156.cache
/var/cache/user-rights/2/28.cache
/var/cache/user-rights/2/4/5/2456.cache
/var/cache/user-rights/5/8/9/6/58964.cache

Dans un répertoire, on ne peut donc avoir que dix sous répertoires et dix fichiers de caches. Le nombre de sous répertoire pour accéder à un fichier est égale à la formule suivante :

$iNumberOfFolder = floor( log10( $iUserID ) ); // Nombre entier inférieur du logarithme du numéro utilisateur

Cette méthode rend la maintenance bien plus rapide, puisque chaque sous répertoire ne contient que peu d’éléments. La mise en place n’est pas compliquée. Cependant elle pose également quelques problèmes. L’arborescence créée dépend du nombre maximum d’utilisateurs. Quid de l’arborescence quand on atteint un « id » de l’ordre du million ? Cela implique par exemple /var/cache/user-rights/1/5/4/5/2/0/1545200.cache. On voit ici qu’on arrive en fait à l’extrême inverse de la solution précédente. Ici nous avons peu de fichiers et répertoires par sous répertoires mais avons potentiellement une très grosse arborescence.

Minimiser le nombre de sous répertoire

Si on considère qu’on doive créer l’arborescence complète, on s’aperçoit après un petit calcul rapide que le nombre de fichiers et de répertoires suivent les formules suivantes :

$iTotalNumberOfFolder = floor( max( $iUserID ) / 10 ); // Nombre entier inférieur du logarithme du numéro utilisateur
$iTotalNumberOfFile = max( $iUserID );

Dans le cas où l’ »id » utilisateur atteint le million, cela signifie qu’il faut créer quelques cent mille répertoires. C’est énorme. Cela surcharge clairement les serveurs et rend la maintenance très compliquée. Il faut donc trouver un moyen de diminuer le nombre de sous répertoires. Pour cela, il faut modifier le découpage. Au lieu de générer l’arborescence en utilisant un seul chiffre, il est plus intéressant d’en utiliser deux voire trois. En utiliser deux permet de diviser le nombre de répertoire par dix par rapport à la précédente méthode tandis que découper en trois permet de diviser par cent. Le choix dépend après de chaque utilisation. On obtiendrait donc /var/cache/user-rights/15/45/20/1545200.cache ou /var/cache/user-rights/154/520/1545200.cache

Pour les exemples à suivre ci-dessous, nous prendrons un découpage à deux chiffres.

Optimiser la répartition de l’arborescence

Si l’on prend 12012 utilisateurs, on aura à la racine de notre répertoire de cache 90 répertoires allant de 10 à 99. Le nombre de sous fichiers dans chaque de ces sous répertoire n’est pas identique. Calculons le nombre de fichiers pour les sous répertoires 10, 12 et 20.

Sous répertoire 10 : fichiers 100 à 109 + 1000 à 1099 + 10000 à 10999 => 10 + 100 + 1000 = 1110 fichiers

Sous répertoire 12 : fichiers 120 à 129 + 1200 à 1299 + 12000 à 12012 => 10 + 100 + 13 = 123 fichiers

Sous répertoire 20 : fichiers 200 à 209 + 2000 à 2099 => 10 + 100 = 110 fichiers

La répartition dépend ici des deux premiers chiffres du nombre maximum. L’idée pour améliorer la répartition est de découper le nombre en utilisant son nombre inversé. Ainsi pour générer l’arborescence pour le nombre 12456, on utilisera le nombre 65421, ce qui donnera /var/cache/user-rights/65/42/12456.cache. Avec cette méthode, le nombre de répertoire à la racine sera de 100, allant de 00 à 99. Le nombre de fichiers dans chaque sous répertoire correspond à la quantité de nombre se terminant par la valeur de ce sous répertoire. Calculons le nombre de fichiers pour les sous répertoires 10, 12 et 20 de nouveau.

Sous répertoire 10 : fichiers 101 ... 901 + 1001 ... 9901 + 10001 ... 11901 + 12001 => 10 + 100 + 120 + 1 = 231 fichiers

Sous répertoire 12 : fichiers 121 ... 921 + 1021 ... 9921 + 10021 ... 11921 => 10 + 100 + 120 = 230 fichiers

Sous répertoire 20 : fichiers 102 ... 902 + 1002 ... 9902 + 10002 ... 11902 + 12002 => 10 + 100 + 120 = 231 fichiers

Sous répertoire 99 : fichiers 199 ... 999 + 1099 ... 9999 + 10099 ... 11999 => 10 + 100 + 120 = 230 fichiers

On voit avec cette méthode que les fichiers sont plus équitablement répartis.