Aujourd'hui nous allons analyser un fichier log d'un serveur web et déterminer le nombre d'adresses IP distincts dans la trace.
Le fichier d'entrée est un fichier texte, avec une ligne requête HTTP. Les différents informations liées à la requête sont séparées par des blancs. On ne s’intéressera qu'à la première entrée, qui contient l'adresse IP du client HTTP. Une adresse IP est un entier sur 32 bits, qui est notée comme une suite de 4 entiers de 8 bits séparés par des points. Par exemple l'adresse 199.120.110.21 correspond à l'entier ((199*256 + 120)*256 + 110)*256 + 21.
Pour des raisons d'économie de place certains fichiers log ne contiennent seulement les adresses IP sans autre information.
Trois fichiers sont mis à votre disposition.
Les fichiers proviennent du Lawrence Berkeley Lab. Ils ont été filtrés en remplaçant les noms de domaines par des adresses IP privées aléatoires, de manière consistante et pour des raisons de confidentialité les adresses IP ont été perturbées par une bijection choisie au hasard.
La dernière trace pèse 1.8 Go et pour gagner de la place les lignes y sont réduits à l'adresse IP client. Les fichiers se trouvent dans le répertoire /Vrac/cpa2016/ des serveurs des salles informatique.
Votre programme affichera une ligne contenant un seul nombre, l'estimation du nombre d'éléments distincts.
Écrivez une classe FluxIP qui lit un fichier texte et produit un flux d'entiers 32 bits. Elle sera muni d'un constructeur qui prend en paramètre le nom du fichier à lire, et d'une méthode next qui retourne le prochain entier du flux, ou la constante 0 si la fin du flux est atteint. (Le choix de cette constante est valable car l'adresse 0.0.0.0 n'apparaît pas dans un fichier log.)
En Java on utilisera le type long qui est codé sur 64 bits pour faciliter la manipulation des adresses. Le type int est codé sur 32 bits, et peut représenter les entiers de -231 à 231-1. Avec le type long toutes les adresses IP sont représentés par des entiers positifs, ce qui est plus simple.
Vos implémentations d'un algorithme de flux devront hériter de la classe suivante.
abstract class StreamingAlgo {
abstract public void update(long ip);
abstract public int val();
}
class StreamingAlgo:
def update(self, ip):
raise NotImplementedError
def val(self):
raise NotImplementedError
Écrivez un premier programme qui compte le nombre d'éléments distincts à l'aide d'un ensemble stockant tous les adresses déjà vus. Concrètement vous écrivez une classe F0naive, qui hérite de StreamingAlgo.
Écrivez également un programme principal qui lit en boucle toutes les adresses IP d'un fichier et les passe à une instance A de la classe F0naive par la fonction update. Finalement le programme affichera la valeur calculée par A.
Écrivez une classe HashFunction qui implémente une fonction de hashage choisie uniformément dans une famille de fonctions 2-universelle. Concrètement le constructeur sera sans argument choisit aléatoirement une fonction de hashage et la méthode hash permet d'appeler cette fonction. Elle envoie des entiers non-négatifs 32 bits vers les entiers non-négatifs 32 bits.
En Java vous devriez utiliser le type long qui est sur 64 bits, car les entiers non-négatifs de type int terminent à 231-1 déjà.
Concrètement implémentez la famille basé sur le ou-exclusif vu en cours. Donc travaillez avec matrice binaire de dimension 32x32, ou de manière équivalente un vecteur de 32 nombres aléatoires indépendants sur 32 bits.
Écrivez une classe F0AMS qui implémente l'interface StreamingAlgo, et suit l'algorithme AMS donnée en cours.
Pour cela vous aurez besoin d'une fonction auxiliaire zerosGauche ou zerosDroite qui retourne pour un entier positif x donnée le nombre de zéros consécutifs tout à gauche ou tout à droite de la représentation binaire de x sur 32 bits.
Vous observez probablement que l'algorithme produit de bien mauvais estimations. Seul dans 47% (sqrt(2)/3) des cas, l'estimation approche avec un facteur entre 1/3 et 3 la valeur exacte. Pour diminuer cette probabilité d'erreur, vous allez utiliser la méthode du médian, vue en cours.
Concrètement écrivez une classe MedianTrick qui implémente StreamingAlgo et dont le constructeur prend en argument A, p, delta. A est de type StreamingAlgo, p est la probabilité que A sur- ou sous-estime la valeur à calculer, et delta est la probabilité d'erreur qu'on veut garantir. Votre classe exécute simplement k copies de A en parallèle. Donc sur update vous appellerez update de chacune des k instances de A. Puis sur val vous retournerez le médian des k réponses de chacune des instances.
Ne cherchez pas à implémenter l'algorithme du médian avec la complexité O(k). Un tri en O(k log k) du tableau des réponses suivi de la lecture du milieu du tableau serait suffisant pour nos besoins.
Déterminez la valeur k suffisamment grande pour garantir une probabilité de succès de delta.
Votre programme principal recevra en premier argument de ligne de commande le nom de fichier à lire. Si c'est le seul argument la classe F0naive sera appelée, s'il y a un deuxième argument il sera interprété comme une valeur delta et servira à l'appel de la classe MedianTrick appliquée à la classe F0AMS.
Le traitement des grands données peut bien prendre de l'ordre d'une demi-heure. Donc c'est peut-être une bonne idée d'afficher à des intervalles réguliers une estimation intermédiaire pour montrer le progrès de votre programme.
Faites plusieurs exécutions de votre implémentation de l'algorithme AMS + MedianTrick avec paramètre delta et mesurez la fraction des réponses qui est à facteur 3 près du nombre correct d'éléments distincts du fichier NASA_access_log_Jul95_ip.log. Est-ce que la majoration delta de la probabilité d'échec se confirme en pratique ?
Nos tests sur 1000 essais avec paramètre delta=10% ont données les résultats suivants.
| fréquence | estimation | |
|---|---|---|
| 71 | 46341 | |
| 517 | 92682 | |
| 0 | 81865 | (valeur exacte) |
| 344 | 185364 | |
| 62 | 370728 | |
| 6 | 741455 |