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. Un processus httpd peut traiter plusieurs requ�tes simultan�ment si vous utilisez un module MPM multi-thread�. Pour identifier les threads, Apache httpd utilise en interne un index de threads. 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 144 bits (adresse IP sur 32 bits, pid sur 32 bits, rep�re de temps sur 32 bits, compteur 16 bits et index de threads sur 32 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 24 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. 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).