Module Apache mod_unique_id

Théorie

Tout d'abord un bref rappel de la manière dont le serveur Apache fonctionne sous Unix (cette fonctionnalité n'étant actuellement pas supportée sous Windows NT). Sous Unix, Apache crée plusieurs processus enfants, ces derniers traitant les requêtes une par une. Chaque processus enfant peut traiter plusieurs requêtes pendant sa durée de vie. Dans le cadre de cette discussion, nous supposerons que les différents processus enfants ne s'échangent pas de données entre eux. Nous nous référerons aux processus enfants sous le nom de processus httpd.

Votre site web est réparti entre une ou plusieurs machines dont vous êtes l'administrateur, et que nous nommerons cluster de serveurs. Chaque serveur peut exécuter plusieurs instances d'Apache. L'ensemble de ces dernières sera considéré comme "l'Univers", et sous certaines hypothèses, nous montrerons qu'il est possible dans cet univers, de générer des identifiants uniques pour chaque requête, sans pour autant nécessiter une communication importante entre les différents serveurs du cluster.

Les machines de votre cluster doivent satisfaire ces conditions (même si le cluster ne comporte qu'une machine, vous devez synchroniser son horloge avec NTP) :

• Les temps des machines sont synchronisés via NTP ou tout autre protocole de synchronisation du temps en réseau.
• Les nom d'hôtes des machines sont tous différents, de façon à ce que le module puisse recevoir une adresse IP différente pour chaque machine du cluster en effectuant une recherche sur le nom d'hôte.

Au vu des caractéristiques actuelles du système d'exploitation, nous supposerons que les pids (identifiants processus) sont codés sur 32 bits. Si le système d'exploitation utilise plus de 32 bits pour un pid, la correction est triviale mais doit être effectuée dans le code.

Ces hypothèses posées, à un instant donné, nous pouvons distinguer tout processus httpd sur toute machine du cluster de tous les autres processus httpd. Pour ce faire, il suffit d'utiliser l'adresse IP de la machine et le pid du processus httpd. Ainsi, afin de générer des identifiants uniques pour chaque requête, il suffit d'effectuer une distinction en fonction du temps.

Pour déterminer le temps, nous utiliserons un repère de temps Unix (les secondes écoulées depuis le 1er janvier 1970 UTC), et un compteur 16 bits. La précision du repère de temps n'étant que d'une seconde, le compteur va représenter 65536 valeurs par seconde. Le quadruplet (adresse IP, pid, repère de temps, compteur) est en mesure de distinguer 65536 requêtes par seconde par processus httpd. Il peut cependant arriver que le même pid soit réutilisé au cours du temps, et le compteur est là pour pallier cet inconvénient.

Lorsqu'un processus enfant httpd est créé, le compteur est initialisé avec (nombre de microsecondes actuel divisé par 10) modulo 65536 (cette formule a été choisie pour éliminer certains problème de variance avec les bits de poids faibles du compteur de microsecondes sur certains systèmes). Lorsqu'un identifiant unique est généré, le repère de temps utilisé est le moment où la requête arrive sur le serveur web. Le compteur est incrémenté à chaque création d'identifiant (et peut repasser à 0 lorsqu'il a atteint sa valeur maximale).

Le noyau génère un pid pour chaque processus lors de sa création, et le compteur de pid est réinitialisé à une certaine valeur lorsqu'il a atteint sa valeur maximale (les pid sont codés sur 16 bits sous de nombreux Unixes, mais les systèmes les plus récents les ont étendus à 32 bits). La même valeur de pid pourra donc être réutilisée au cours du temps. Cependant, tant qu'elle n'est pas réutilisée dans la même seconde, elle ne remet pas en cause l'unicité de notre quadruplet. Nous supposerons donc que le système ne créera pas plus de 65536 processus en une seconde (ce nombre peut être de 32768 sous certains Unixes, mais même dans ce cas, on est en général loin de cette situation).

Il est possible que le temps se répète pour une raison quelconque. Supposons par exemple que l'horloge système soit retardée et repasse par un temps passé (ou bien, comme elle avançait, elle a été remise à l'heure, et elle repasse par un temps futur). Dans ce cas, il peut être facilement démontré que le couple pid/repère de temps peut être réutilisé. Le choix de la formule d'initialisation du compteur a été effectué dans l'intention de pallier ce problème. Notez qu'un nombre vraiment aléatoire serait souhaitable pour initialiser le compteur, mais il n'existe pas de tel nombre directement lisible sur la plupart des systèmes (c'est à dire que vous ne pouvez pas utiliser rand() car vous devez déclencher le générateur avec une valeur unique, et vous ne pouvez pas utiliser le temps à cet effet car celui-ci , au moins à la seconde près, s'est répété). Il ne s'agit donc pas d'une défense parfaite.

Même si elle n'est pas parfaite, quel est le degré d'efficacité de cette défense ? Supposons qu'une de vos machines serve au plus 500 requêtes par seconde (ce qui constitue une limite supérieure très raisonnable au moment où ce document est écrit, car les systèmes ne se contentent en général pas de débiter des fichiers statiques). Pour y parvenir, un certain nombre de processus enfants sera nécessaire, qui dépendra du nombre de clients simultanés présents. Mais soyons pessimiste et supposons qu'un seul processus enfant soit capable de servir 500 requêtes par secondes. Il existe 1000 valeurs de démarrage possibles du compteur pour lesquelles deux séquences de 500 requêtes puissent se recouvrir. Il y a donc 1,5% de chance que le processus enfant répète une valeur de compteur si le temps se répète (avec une résolution d'une seconde), et l'unicité sera alors remise en cause. C'est cependant un exemple très pessimiste, et avec les valeurs du monde réel, il y a bien moins de chances que cela ne se produise. Si vous estimez que ceci a tout de même quelque chances de se produire sur votre système, vous pouvez migrer vers un compteur à 32 bits (en modifiant le code).

On pourrait supposer que ceci a plus de chance de se produire lors du passage à l'heure d'hiver où l'horloge est "retardée". Cela ne constitue cependant pas un problème car les temps pris en compte ici sont des temps UTC, qui vont "toujours" de l'avant. Notez que les Unixes à base de processeur x86 peuvent nécessiter une configuration particulière pour que ceci soit vrai -- il doivent être configurés pour assumer que l'horloge système est en UTC et compenser de manière appropriée. Mais même dans ce cas, si vous utilisez NTP, votre temps UTC sera correct peu après le redémarrage.

La variable d'environnement UNIQUE_ID est construite par codage du quadruplet de 112 bits (adresse IP sur 32 bits, pid sur 32 bits, repère de temps sur 32 bits et compteur 16 bits) en utilisant l'alphabet [A-Za-z0-9@-] d'une manière similaire à celle du codage MIME base64, et sa valeur se présente sous la forme d'une chaîne de 19 caractères. L'alphabet MIME base64 est en fait [A-Za-z0-9+/] ; cependant, les caractères + et / nécessitent un codage particulier dans les URLs, ce qui rend leur utilisation peu commode. Toutes les valeurs sont codées dans l'ordre des octets d'une adresse réseau de façon à ce que le codage soit comparable entre des architectures où l'ordre des octets est différent. L'ordre réel de codage est : repère de temps, adresse IP, pid, compteur. Cet ordre de codage possède un but précis, mais il faut souligner que les applications n'ont aucun intérêt à entrer dans les détails de ce codage. Les applications doivent se contenter de traiter la variable UNIQUE_ID comme un symbole opaque, qui peut être comparé avec d'autres UNIQUE_IDs en ne testant que leur égalité.

L'ordre a été choisi de façon à ce qu'il soit possible de modifier le codage dans le futur sans avoir à se préoccuper de conflits éventuels avec une base de données de UNIQUE_IDs existante. Les nouveaux codages doivent conserver le repère de temps comme premier élément, et pour le reste, utiliser les même alphabet et longueur en bits. Comme les repères de temps constituent essentiellement un séquence croissante, il suffit que toutes les machines du cluster arrêtent de servir et de requérir dans la même seconde repère, et n'utilisent alors plus l'ancien format de codage. Ensuite, elles peuvent reprendre le traitement des requêtes en utilisant les nouveaux codages.

Nous pensons que ceci apporte une solution relativement portable au problème. Elle peut être étendue aux systèmes multithreadés comme Windows NT, et peut évoluer en fonction des besoins futurs. Les identifiants générés possèdent une durée de vie pratiquement infinie car les identifiants futurs pourront être allongés selon les besoins. Pratiquement aucune communication n'est requise entre les machines du cluster (seule la synchronisation NTP est requise, ce qui représente une charge très faible), et aucune communication entre les processus httpd n'est nécessaire (la communication est implicite et incluse dans le pid assigné par le noyau). Dans des situations très spécifiques, l'identifiant peut être raccourci, mais dans ce cas, d'avantage d'informations doivent être admises (par exemple, les 32 bits de l'adresse IP sont excessifs pour la plupart des sites, mais il n'existe pas de valeur de remplacement portable plus courte).