jeudi 30 avril 2015

Analyse du livre "Big Data et machine learning" (dernier article, point de vue "computer vision")

Introduction


Cet article est le dernier (sur quatre au total) présentant un livre très récent dédié au Big Data, à la Data Science et notamment au Machine Learning.
Ce dernier article donnera ma vision du livre d'un point de vue de la vision par ordinateur.

Les 3 "V" du Big Data et la vision artificielle


Le spécialiste de la vision par ordinateur se retrouve confronté d'une manière beaucoup plus marquée que n'importe quel "Data Miner" ou "Data Scientist" aux 3 "V" du Big Data :
  • Variété: Ici, une image où seuls les pixels peuvent nous donner des informations de plus haut niveau est autrement plus difficile à traiter qu'une table SQL ou même des données au format XML ou JSON
  • Volume: Une image couleur au format FullHD (1920*1024) prend 3 à 4 octets par pixel.  Soit lorsque l'image est traitée sans compression en mémoire pour analyse, cela prend 5,6Mo d'emprunte mémoire.  Si nous devons analyser une image (ou sa signature c.a.d un résumé) de manière naïve dans une vidéo FullHD de 2 heures (2h*3600sec*24image/sec) soit 172 800 images, cela représente 945Go. Bien sûr, on peut analyser plus intelligemment, cependant, certains descripteurs d'une image sont plus volumineux que l'image elle-même (surtout lorsqu'on utilise les points d'intérêts voir la 2ème illustration) 
Exemple de point d'intérêt SIFT (vecteur à 128 dimensions)
Crédit Wikimedia CC by 2.0
A titre d'exemple dans cette petite image à gauche (320*288 en JPG de 56Ko) 
on a 2128pts d'intérêts d'une taille de 128 dimensions soit en mémoire RAM ~290Ko soit plus de 5 fois la taille JPG) voir l'image de droite indiquant les points d'intérêts en rouge.

à gauche, l'image originale, à droite les points d'intérêts repérés
où chaque point d'intérêt est une donnée à 128 dimensions

  • Vitesse:  En vision par ordinateur, certains traitements demandent d'être traités en temps réel (par exemple la réalité augmentée ou la vision des robots). Il faut donc en général, analyser l'image en moins de 33 millisecondes (1 seconde divisée par le nombre d'image seconde de la caméra, soit 30ips d'où 1000/30).

La malédiction de la dimension, un mal nécessaire en vision artificielle

Autre point où le spécialiste en vision artificielle va plus loin que les Data Miner/Scientist, il manipule de multiples données avec des dimensions supérieures à 10 très souvent :

  • Les point d'intérêts sont des tableaux(vecteurs) contenant entre 32 à 128 dimensions et on peut facilement avoir plus de 300 points d'intérêts par image (en fait plus l'image est grande, plus elle en aura)
    Descripteur de point d'intérêt SIFT à 128 dimensions prenant en compte
    des informations sur les pixels voisins à de multiple échelle de l'image.
    Crédit par Indif - Wikimedia - CC BY-SA 3.0
  • La signature sur les couleurs d'une image (dans sa globalité) peuvent prendre entre 32 à 216 dimensions (on parle d'histogramme de couleur

Le vrai "machine learning"

Avec ces notions en tête, on comprendra que le "Machine Learning" abordé dans le livre fera gentiment sourire le spécialiste en vision par ordinateur qui pourra conseiller le livre à toute personne ne connaissant pas son travail et les notions qu'il doit pratiquer.

Cependant, en vision par ordinateur, le "machine learning" prend vraiment tout son sens.  On ne travaille qu'avec des données non structurées auxquelles il faut trouver du sens pour en faire de la classification ou de la prévision.

Pour s'en convaincre, voici des liens vers l'API OpenCV permettant de faciliter la vision par ordinateur:
Toujours en parlant d'apprentissage, aucun référence à l'apprentissage par renforcement n'est indiquée dans l'ouvrage. Pourtant, ce type d'apprentissage qui prend en compte le feedback de l'utilisateur est assez fréquent en "Machine Learning" pour l'analyse d'images (mais également utile pour réduire le fossé sémantique qui est la différence entre les descripteurs "bas niveau" de l'image et sa représentation sémantique).

Machine Learning et 64 dimensions ou plus

Comme le spécialiste en vision artificielle ne peut pas tout réduire à 2 ou 3 dimensions et faire des analyse en composante principale (ACP) à tout va, il doit être plus malin qu'un Data Scientist / Miner.

Pour continuer à travailler avec 64 dimensions ou beaucoup plus, il faut améliorer les algorithmes existants et la façon de stocker/rechercher les données.

Techniques d'indexation multi-dimensionnelles:

Les bases de données relationnelles reposent sur des données à une dimension (on n'a des index que sur un seul entier/flottant d'une colonne de la table SQL). Le type d'index le plus approprié pour retrouver des valeurs dans un intervalle est l'arbre B+ qui est la référence de nombreux SGBDR.
En augmentant à 3 dimensions il faut oublier l'arbre B qui commence déjà à montrer ces limites, on lui préférera le Kd-tree ou un octree.

Mais dès qu'on dépasse 4 dimensions, les algos classiques s'écroulent vite en pertinence et temps de traitement. D'autres structures d'arbres existent pour indexer des données à forte dimensions :
  • R-tree : reprend le principe des octree & kd-tree mais en ayant un système de zone de regroupement de données locales (ex : cube pour des données en 3D) avec possibilités de recoupement entre zones.
  • M-tree : reprend le principe d'un arbre B mais avec des calculs de distances basés sur des métriques (permettant de travailler avec des données non numériques).
Pour aller encore plus vite car l'analyse d'image le permet, on peut indexer de manière approximative :
  • VA-File (Vector Approximation) (PDF) Ici, l'idée est d'affecter un index binaire (ex:  0010001) en découpant l'espace où se trouvent les données. Cela reprend un peu le système de hachage où l'index est prévu pour tenir en mémoire RAM et donc de pouvoir stocker facilement et accéder rapidement aux vecteurs tout en permettant une recherche approximative des k plus proches voisins car affectés localement à priori au même index. Dans un second temps, on peut faire une recherche plus précise en regardant sur disque les données exactes des points associées à la "page" indexée par un numéro binaire unique.
Exemple de VA File.  Credit SCL
  • LSH (Locality Sensitive Hashing) où l'idée est que des points proches en terme de coordonnées multi-dimentionnelle aient la même signature de hachage (et facilite ainsi le regroupement et la recherche des k plus proche voisin).
Crédit TU-Berlin

Pour info, des index existent aussi dans les bases NoSQL mais se limitent toutes à un ArbreB. Donc aucune base NoSQL ne peut correctement contenir des données multimédias.
Cependant, du côté des SGBDR "classiques", il faut surveiller les index de type GIST qui peuvent généraliser le principe d'index.

Algorithmes améliorés:

L'algorithme des k plus proches voisins et celui du k-means sont très couramment utilisés en vision par ordinateur.

Il existe des variantes des KNN et K-means qui vont utiliser les index R ou M-tree pour accélérer la recherche des plus proches voisins.
On trouvera aussi des variantes utilisant les index approximatifs. Exemple à lire ici.

Grâce à ce genre d'améliorations, les données à dimensions multiples n'effraient plus un spécialiste en vision artificielle alors que cela laissera un mauvais souvenir à un Data Scientist et un Data Miner.

Pour aller plus loin 

Toujours en analyse d'images, il est intéressant de suivre les projets autour de la robotique comme PCL (Point Cloud Library). On y trouve des techniques :
  • sur la géométrie et l'indexation de nuage de point 3D (octree et Kd-tree)
  • la gestion des points d'intérêts
  • l'algo RANSAC pour pré-traiter les données. Il permet d'éliminer les "outliers" (valeurs extrêmes ou aberrantes) pour aider à la fusion d'images (voir la 2ème image ci-dessous).
Exemple d'ensemble de points d'intérêts ayant été utilisés pour reconstituer en 3D des objets et la géométrie du monde réel
Crédit PCL (CC By CA 3.0)
Exemple de fusion d'images en mode Panorama (image stitching) grâce aux points d'intérêts et à l'algo RANSAC
Crédit Wikimédia par Noso CC By SA 3.0

Conclusion

Le lecteur qui aura eu le courage de lire les 4 articles l'aura compris, le livre est une très bonne introduction, suffisamment abordable pour servir de base à un travail commun entre différents acteurs dont certains n'ayant jamais entendu parler de Big Data et encore moins de Machine Learning.


Ne faisant que 220 pages, les auteurs ont fait des choix sur les sujets à présenter cependant l'essentiel y est.

Avant de s'auto-proclamer "Data Scientist" après la lecture du livre, celui-ci reste néanmoins une invitation à pousser encore plus loin la porte de la curiosité et de plonger dans des notions approfondies dans les domaines suivants :

  • Statistique et probabilité
  • Data Mining (et aussi les réseaux de neurones au sens large)
  • Text Mining et analyse d'opinion
  • Machine Learning en Vision artificielle (ou en multimédia en général)
J'espère au travers des 3 derniers articles vous avoir donner envie de creuser par vous-même les aspects abordés et de vous en faire votre propre opinion.

dimanche 26 avril 2015

Analyse du livre "Big Data et Machine Learning" (vision Data Mining)

Introduction


Cet article est le troisième sur quatre prévus présentant un livre très récent dédié au Big Data, à la Data Science et notamment au Machine Learning.
Ce troisième article donnera ma vision du livre d'un point de vue du Data Mining.

On parlera essentiellement ici des :

  • chapitre 6 : Exploration et préparation des données
  • chapitre 7 : Machine Learning
Encore une fois, le livre est une excellente introduction à ce sujet complexe qu'est l'apprentissage artificiel (Machine Learning).


Que peut retenir un spécialiste du Data Mining du livre ?

Sur le chapitre 6 : Exploration et préparation des données

  • Sur cet aspect, l'essentiel est dans le livre présentant la diversité des types de données et des moyens de les explorer et de les préparer.
  • Cependant, le chapitre de 16 pages consacrés à ce sujet est sous-dimensionné par rapport à l'importance d'avoir de bonnes données en entrée.  Mes profs en Data Mining nous martelaient bien le message suivant : l'analyse et pré-traitement des données représentent au moins 80% du travail en Machine Learning (=> cette notion n'apparaît pas dans le livre). 
  • En exploration des données, il est étonnant de ne pas déjà parler de classifications automatisées pour se donner une idée des regroupements dans les données (la notion de kmeans est abordée en chapitre 7).
  • Il aurait été intéressant d'évoquer (ne serait-ce qu'en note de bas de page) les méthodes pour les fonctions de densité comme les fenêtres de Parzen qui sont une généralisation des histogrammes. (Ceci est présenté en chapitre 8 dans le livre dans la partie visualisation).

Sur le chapitre 7 : Machine Learning 

  • Voici le détail des algorithmes abordés:
                   - présentation des différentes familles d'algorithmes :
                          (paramétrique et non, supervisé ou non, probabiliste ou non...)
                   - régression linéaire
                   - k plus proches voisins
                   - classification naïve bayésienne
                   - régression logistique
                   - k-moyenne (ou k-means)
                   - arbre de décision
                   - forêt aléatoires
                   - machine à vecteur support SVM
                   - Des techniques de réduction dimensionnelle (dont l'ACP)
  • Ce que j'aime bien :
          La présentation claire avec schémas (et parfois quelques formules) de chaque algo : 
                   - une description théorique et accessible à tous 
                   - les avantages de l'algorithme
                   - ses inconvénients 

Hum... C'est tout? Y a pas d'autres algorithmes ?

Encore une fois, le livre ne fait que 220 pages ce qui est bien insuffisant pour devenir, malgré la phrase choc du livre, un "manuel du Data Scientist".

Là, le chapitre 7 m'a clairement laissé sur ma faim, le titre n'est-il  pas "Big Data et Machine Learning" ?  Dans "Learning" il y a apprentissage, la notion est abordée mais vraiment survolée. J'y reviendrais dans un article dédié à l'apprentissage articifiel.

Coté algorithme, aucune référence aux réseaux de neurones n'est faite ! C'est pourtant le classificateur universel de base en Data Mining.
Schéma interne d'un réseau de neurones (source Wikimédia CC3)
Sans les réseaux de neurones, il manque toute une famille d'algorithme :
  • Le perception multi-couche (MLP en anglais) qui sert universellement en classification, en régression et prévision.  Il est certes plus dur à expliquer aux néophytes mais le livre a réussi l'exploit d'expliquer les SVM de manière claire. Le problème des MLP est la mise en place de l'architecture du réseau de neurone et de son côté "boite noire" par la suite.
  • Les réseaux de neurones temporels (ex: TDNN)
  • Les chaînes de Markov cachée (HMM en anglais) pourtant très utilisées en prévision pour la reconnaissance vocale et gestuelle
Pour la classification également, il manque plusieurs algos :

De plus, sur certains algorithmes présentés, d'autres précisions auraient été utiles. Par exemple, c'est pour les SVM, où il n'a pas été mentionné en avantage qu'avec très peu de données, l'algo est performant. En autre car celui-ci s'intéresse aux frontières entre données à classifier (contrairement aux MLP et autre algo de stats).



Autre oubli, celui de la logique Floue. Tous les algos présentés dans le livre donnent l'impression de trouver une valeur numérique ou catégorielle unique. Or, il existe des variantes pour avoir des prévisions non pas "binaire" 0 ou 100% (oui/non) mais proposant des probas de réalisation (ex: 60%) d'une catégorie et 40% d'une autre. Cela rejoint aussi les algos de type mélange de gaussienne comme l'EM.

Concernant les techniques de réduction de dimension, il est dommage qu'elles n'apparaissent pas en chapitre 6 car c'est souvent un préalable en data mining.


Sur la comparaison entre modèles :

La validation croisée est expliquée par un schéma bien parlant, de même pour les courbes ROC et on a bien la notion de matrice de confusion, tout y est. Tout ceci est par contre découpé bizarrement entre le chapitre 7 et le 8.

Un statisticien apprécierait également que les notions plus mathématiques que sont les critères AIC et BIC soient abordées ne seraient-ce qu'en bas de page.

Et le Text Mining dans tout ça ?

Bien qu'une "analyse" de texte soit évoquée lors de la présentation d'Hadoop (Comptage de mots), une personne cherchant des entrées pour du Text Mining restera sur sa faim.
Il est juste dommage de ne pas avoir évoquer le sujet tant des outils comme WATSON d'IBM commence à prendre de plus en plus d'importance dans l'analyse du langage naturel.
D'ailleurs, les outils de "NLP" (Natural Language Processing) utilisent du Machine Learning pour déterminer à quel groupe grammatical appartiennent tel ou tel élément d'une phrase.
Voici un exemple de reconstruction de l'arbre grammatical à partir d'un parseur NLP (ici LanguageTool):



Pour conclure


Le livre permet d'avoir tous les concepts théoriques pour faire du Machine Learning, il est évident qu'un livre de 220 pages ne peut pas tout couvrir mais l'essentiel y est.
Comme souvent, le Data Scientist en herbe devra compléter ses connaissances d'algo notamment sur les réseaux de neurones car, même s'ils n'ont plus la côte, ils n'ont même pas été abordés dans l'ouvrage ainsi que tout ce qui concerne les mélanges de gaussiennes.

L'ouvrage a été l'occasion pour moi de découvrir les forêts aléatoires comme algo pouvant être performant. Ne croyant que ce que je teste, je validerais (ou pas) l'affirmation du livre sur la performance supérieure de cette famille d'algo sur les SVMs lors d'un prochain article.

lundi 20 avril 2015

Analyse du livre "Big Data et Machine Learning" (vision Statisticien)

Introduction


Cet article est le second sur quatre prévus présentant un livre très récent dédié au Big Data, à la Data Science et notamment au Machine Learning.
Ce deuxième article donnera ma vision du livre d'un point de vue du statisticien (à mon niveau c'est à dire ayant l'équivalent d'un BAC+2 à BAC+3 en statistique).

Pourquoi 4 articles pour un même livre ?

Ce livre est, je le répète, une excellente introduction sur le sujet et permet à des néophytes à la fin du livre d'avoir à minima une compréhension à grosse maille des enjeux et des techniques de la "Data Science".

Ce qui me gêne dans la couverture c'est la phrase "Manuel du Data Scientist"... Sachant que le livre ne fait "que" 220 pages, difficile de tout aborder dans un livre aussi court.

Ce qui manque à un statisticien

Dans l'ouvrage, on parle de "Machine Learning" en vue de prévision. 

Quelques définitions

Nulle part dans l'ouvrage, nous avons droit ni en note de page, ni en glossaire à la fin du livre des définitions importantes comme :

  • On a une définition un peu simple de la notion d'intervalle de confiance mais suffisamment intuitive (p109).
  • La notion d'estimateur statistique. Celui est pourtant important dans toute modélisation statistique en vue d'inférence.
  • La notion précise du biais. Le mot est évoqué de temps en temps mais sans définition mathématique (encore une fois pour ne pas effrayer les personnes allergiques aux maths mais une note de bas de page aurait pu être utile pour les plus curieux).
  • Le fait que l'estimateur n'est jamais juste et on aura soit un problème de biais, soit un problème de variance, c'est le fameux dilemme biais-variance. Il y a cependant dans le livre en page 148, une explication non mathématique expliquant les écarts entre les données prévues et la dispersion du modèle.
  • Toujours en parlant d'estimateur, on ne retrouve pas la notion d'estimateur robuste (non basé sur la moyenne mais sur la médiane ou les centiles).
  • Quand on parle de prévision, on est sensé indiquer quel événement futur doit-on cherché à deviner. C'est la notion d'horizon.  Pour être plus clair, nous avons toutes nos données de Xt0 à Xtn (n étant la dernière données connues), l'horizon 1 cherche à trouver la valeur suivante c'est à dire Xtn+1, l'horizon 2 cherche la valeur suivante soit xtn+2, etc...
Et du côté des probas :

  • Nous avons une note de base de page en 119 sur les probabilités conditionnelles P(A|B)
  • Cependant, je n'ai pas trouvé dans le livre des références ou des notes de bas de page sur les notions de : 
  • Expérience aléatoire, univers, événement, tribu ou encore espace probabilisé
  • Variable aléatoire, Espérance mathématique, loi statistique, fréquence... 

Et les séries temporelles (pour l'économétrie ou autre) ?

Toujours sur la partie prévision, éclipser quasiment totalement les séries temporelles vu par les mathématiques (même cela concerne des transformations linéaires et souvent mono-variable) est quand même un grand oubli.

Pour rappel, une série temporelle est caractérisée par :

  • une tendance (malgré la variance, les valeurs de la série diminuent-elle ou augmentent-elle au fur et à mesure du temps ?).
  • une saisonnalité (variation sur l'année et répétitif d'une année sur l'autre)
  • un éventuel cycle (comme une saisonnalité mais une plus grande période)
  • un bruit blanc (celui-ci est définit dans le livre en page 109)

Et Box et Jenkins ?


La seule référence à Box & Jenkins est une citation de Box sur les modèles statistiques et leurs utilités.
Nulle part, on parle du processus ARMA de Box & Jenkins qui fut pourtant un modèle dans les années 1970.
Même si le processus n'est pas parfait, il existe des variantes : ARIMA et GARCH, VAR, VARIMA...
Mais effectivement, ce modèle AR[I]MA est linéaire et peut-être trop loin des outils traditionnels de Data Mining.

Et les tests statistiques ?

Le statisticien possède plusieurs outils pour construire son modèle statistique et les tests statistiques sont un moyen de construire et valider son modèle.
L'ouvrage présente de quoi faire des validations croisées entre algo de Machine Learning et selon leur paramétrage initiaux, mais le statisticien pourra également faire d'autres types de tests en préparation des données (l'ajout de feature, l'indépendance de certaines variables par rapport à d'autres, test de conformité à une loi statistique qu'un informaticien "normal" n'aura pas repéré)

Il y a Manuel et manuel...

Pour conclure, le livre présente en 220 pages une très bonne présentation du sujet, c'est clair et compréhensible.
Je mets, par contre, en garde un profil ne connaissant uniquement que l'informatique et qui après avoir lu le livre pourrait se sentir "Data Scientist". Un statisticien pourrait très vite refroidir l’enthousiasme de notre jeune informaticien en lui posant des colles sur des notions qui doivent être vu en dehors du livre.

Encore une fois, le slogan "Manuel du data scientist" est plus à prendre comme un pense-bête du Data Scientist pour ne pas oublier certaines étapes.
Ce métier de Data Scientist exige des connaissances en informatique mais également de vraies notions en statistiques qui ne s'acquièrent pas par hasard.

Ma bibliographie du statisticien :

  • La statistique sans formule mathématique (excellent livre présentant les stats & proba sans aucune formule de math) de Bernard PY
  • Mini manuel de probabilités et statistique (livre d'exercices et de résumés de cours mais accessibles sur les notions de base) de Françoise COUTY, Jean DEBORD et Daniel FREDON
  • Probabilites Analyse des Données et Statistique (à l'opposé, c'est une bible de 660pages mais le style est plus un recueil de formules que d'un ouvrage permettant une compréhension) de Gilbert SAPORTA
  • Statistique - Méthodes pour décrire, expliquer et prévoir - (ouvrage plus poussé que celui de Bernard PY mais plus compréhensible que celui de G . Saporta) de Michel Tenenhaus

jeudi 16 avril 2015

Analyse du livre "Big Data et Machine Learning" (vision Chef de Projet)

Introduction


Cet article est le premier prévu sur quatre d'un livre très récent dédié au Big Data, à la Data Science et notamment au Machine Learning.
Ce premier article donnera ma vision du livre d'un point de vue gestion de projet ou même sur la gouvernance de ce type de projet de Data Science.
Les autres articles seront plus dédiés à la mention indiquant "Manuel du data scientist" avec 3 visions différentes :

  • du point de vue du statisticien
  • du point de vue du data miner 
  • du point de vue du spécialiste en computer vision

En deux mots


L'ouvrage est clair, construit en 3 grandes parties qui peuvent être abordée séparément :

  1. Les fondements du Big Data 
  2. Le métier de Data Scientist
  3. Les outils du Big Data

Il permet à des profils sans bagages mathématiques d'aborder les notions autour de ce mot galvaudé qu'est le "Big Data".

Même les notions plus ardues de Machine Learning (et donc de Data Mining) au travers de schémas et d'explications claires arrivent à être accessibles ou du moins dans le pire des cas le terme sera évocateur. Pas besoin ici, d'avoir mal à la tête avec des termes mathématiques comme le "maximum de vraisemblance" et d'autres termes pouvant très vite refroidir plus d'une personne allergique aux maths.

Au final

C'est un très bon livre d’introduction quasiment sans formules de math à faire peur, accessible à l'ensemble des acteurs de ce type de projet même côté métier.

Le livre peut être un excellent point de départ pour travailler en commun avec différents acteurs, connaître le vocabulaire et les notions sous-jacentes.

Enfin, pour la création d'un Data Lab, toutes les étapes y sont décrites. Côté gouvernance, le livre constitue donc la première pierre d'un édifice à construire à plusieurs dont les étapes et le vocabulaire seront partagés.



mercredi 15 avril 2015

Quand Java n'aime pas Linux

D'abord, désolé pour ce titre racoleur !

Linux est un très bon système cependant ce titre relate une réalité à propos de certaines applications Java (sous forme de batch en .jar ou d’applications Web .war ou .ear) qui sont sensibles à l’ordre de chargement des fichiers.


Commençons par un petit Quizz.  
Avez-vous déjà testé le résultat de la méthode list() de java.io.File sur différents systèmes d’exploitations et sur différents systèmes de fichiers également ?
Comme beaucoup de développeurs en entreprise ou freelance, vous travaillez essentiellement sous Windows ou MacOS X.


Voyons ce que nous dis la JavaDoc de la méthode list() de java.io.File (je mets en gras et en rouge la partie qui nous intéresse) :


public String[] list()
Returns an array of strings naming the files and directories in the directory denoted by this abstract pathname.
If this abstract pathname does not denote a directory, then this method returns null. Otherwise an array of strings is returned, one for each file or directory in the directory. Names denoting the directory itself and the directory's parent directory are not included in the result. Each string is a file name rather than a complete path.
There is no guarantee that the name strings in the resulting array will appear in any specific order; they are not, in particular, guaranteed to appear in alphabetical order.
...


En gros, rien ne garantie que le résultat du tableau renvoyé sera dans un ordre quelconque notamment un ordre alphabétique.


Toujours sceptique ? Voici le résultat du listage d’un répertoire sous Windows, Mac OS X, AIX, Linux:


...
File file = new File(strFolder);
if (file.exists() && file.canRead() && file.isDirectory()) {
String[] fileList = file.list();
           System.out.println("reading folder : " + file + "\n");
for (String fileToDisplay : fileList) {
       System.out.println("\t" + fileToDisplay);
}
}


OS
Windows
Mac OS X
AIX v6 (IBM)
Linux (Redhat 6.5)
Linux (Cent OS 7)
File
System
exemple du listage par
list() de la classe File

a
AB
b
o
P
y
Z

Applications
apps
..
dev
Developer
etc
...
Users
usr
var

AB
P
Z
a
b
o
y

o
Z
AB
y
P
a
b

boot
sys
etc
var
...
bin
lib64
home
mnt
opt
ordre constaté
ordre a-Z
indépendemment de la casse
ordre a-Z
indépendemment de la casse
ordre A-Z puis a-z

dépendant de la casse
ordre semblant “aléatoire”
ordre semblant “aléatoire”
Attention, ici, l’ordre semblant aléatoire de ext à ext4 et de XFS est dû à une combinaison d’un hachage du nom de fichier avec celui UNIQUE de la racine de la partition sur laquelle les fichiers sont installés.  Si le nom de fichier ne change pas (et c’est le cas d’un WAR et EAR décompressé), l’ordre non alphabétique reste exactement le même à chaque redémarrage de la JVM ou d’un appel à  list() de java.io.File()


Est-ce grave ?
Oui, l’application peut ne plus fonctionner selon qu’elle charge le bon fichier ou pas (par exemple un fichier properties ou potentiellement une classe Java spécifique).
C’est lors d’une mission de migration d’applications Java (développement interne et des progiciels) d’AIX à Linux que j’ai constaté cela.
Chez le client, rien n’avait été vu avant côté développement car sous Windows et aussi l’ancienne production en AIX le comportement est quasiment similaire (ordre de A à Z).  C’est de manière aléatoire qu’arrivaient certains problèmes, non repérés de suite car l’ordre n’est jamais le même en Linux d’une VM à l’autre et d’une partition FileSystem à l’autre. On pouvait donc avoir eu de la chance en recette Linux et aller en prod en erreur.

Nous avons eu le cas de la banque en ligne dont l’analyse à durer plus d’un mois afin d’être sûr du problème. Pourquoi autant de temps d’analyse ? Plusieurs circonstances dont le fait d’être en juillet / août mais aussi le fait principal que cela avait déjà marché une première fois en environnement de pilote Linux.  
C’est en tentant de basculer vers la vraie prod que les soucis étaient arrivés. Des événements ont été mis en avant par chacune des équipes (développement, socle et production) pour creuser l’analyse dans un sens où l’erreur est “sûrement” chez l’autre. 
Du coup, chaque équipe cherchait des arguments et contre-arguments pour ne pas être en cause. En fait et au final, les serveurs étaient bien installés, l’application était la même qu’en pilote Linux. La cause était ailleurs...

A quoi c’est dû ?
La sensibilité à l’ordre de chargement des fichiers via soit un framework maison, soit Spring (avec l’option classpath: ), soit directement par le serveur d’application lui-même ne peut intervenir que si l’application possède des fichiers en doublons et dont le contenu est différent.


Pour rappel, voici les différents problèmes liées à l’ordre des fichiers :
  • même nom de fichier .properties dans 2 répertoires différents avec un contenu différent le tout  gérer via un chargement à la “classpath: “. Ici, dans un classloader maison d’un framework maison.  Selon l’ordre de chargement, c’était soit le bon fichier, soit le mauvais qui était pris en compte selon la manière dont l’EAR avait été dézipper sous Linux.
  • même jar d’un framework éditeur mais avec 2 versions mineures présentes dans le WEB-INF\lib. Pareil, selon l’ordre de chargement des jars, sur certaines VM Linux, on avait une version n-1 chargée en premier ou sur d‘autre la version n
  • même classe (même package) dans 2 jars différents avec un contenu différent dans le WEB-INF\lib.  Ce problème a l’air simple mais il a fallu de multiples analyses et éliminer d’autres pistes avant d’envisager puis d’être sûr de cette conclusion.  Cela est une pratique très courante chez les éditeurs de progiciels Java de “patchers” soit leur propre jars applicatifs soit celle d’API / framework standard par la surcharge d’une classe (Ex: XmlCipher) ajoutant un comportement différent de la classe du jar original mais ici, selon l’ordre de chargement des jars du WEB-INF\lib du serveur d’application, cela sera la bonne ou la mauvaise implémentation de cette classe qui sera chargée en premier.
  • Attention car les bibliothèques natives (.so, .dll ou .dylib) appelées par Java via JNI sont également soumises à ce problème d’ordre des fichiers.


Ce constat est vrai aussi pour les applications construites par maven sans maîtrise de leurs dépendances (dont les transitives). Pour rappel, il n’existe pas que le scope “compile” mais attention aussi au scope “runtime” qu’on ne découvre qu’à l’exécution.
Ceux qui ont déjà dû jouer avec les SLF4J et les common logging dans leur gestion des dépendances (rien que sur les logs) savent de quoi je parles.
Pour résumer, mieux vaut éviter d’importer trop de JARs par dépendance directe ou transitive dont des classes Java avec un même package et un contenu différent pourrait se retrouver embarqué avec une chance sur deux que la “mauvaise” classe soit chargée avant.


Comment éviter cela et réconcilier applications & progiciels Java avec Linux ?
  • Détecter tous fichiers (et classe+package Java) en doublons dont le contenu est différents
  • Supprimer le (ou les) doublons de manière à ce qu’un seul fichier, qu’une seule classe java (de même package) soit intégrée au livrable Java
  • Une solution non pérenne est de forcer à trier les fichiers par ordre alphabétique juste après le list() de java.io.File. Cela peut se concevoir sur un framework maison, plus difficilement sur Spring et encore moins en forçant cela dans le serveur d’application (surtout s’il s’agit de WebSphere ou équivalent en terme de richesse/complexité).


Existe-t-il un outil pour faciliter ce travail de vérification ?
J’ai crée un outil dédié à cette problématique qui peut lever des alertes mais il peut y avoir des faux positifs. Je dois le rendre plus intuitif et plus flexible pour le distribuer.
Il existe sinon le projet TattleTale de JBoss pour vérifier déjà certains points.


En fait, mais pourquoi les File System (ext à ext4 et XFS) réagissent-ils comme cela ?
Le listage des entrées du répertoire sur ext (à ext4) et sur XFS s’appuie sur un mécanisme complexe de Hash Tree Directory. Voir ici pour les plus curieux. :
On combine la signature (hachage) du nom de fichier selon 3 algos possibles (Legacy, Tea et Half MD4)  avec un “Directory Hash Seed” du répertoire racine de la partition du File System.  Cette signature (“hash seed”) pour la racine de la partition est unique et la recopie de fichiers d’une partition à l’autre engendrera un ordre de listage différent.


Voici un exemple d’une partition ext2 vue avec l’outil “debugfs” :
Filesystem magic number:  0xEF53
Filesystem revision #: 1 (dynamic)
Filesystem features:   ext_attr resize_inode filetype sparse_super
Filesystem flags:         signed_directory_hash

Default directory hash:   half_md4
Directory Hash Seed:      6d5319ae-528e-494e-873b-8453642d8990


Ci-contre, un test de hachage avec DebugFS en fonction de l’algo sur le même fichier:
debugfs:  dx_hash -h tea F.properties     
                        Hash of F.Properties is 0x3e056e5e (minor 0x3e89959f)
debugfs:  dx_hash -h half_md4 F.properties
                        Hash of F.properties is 0x9df9c1d0 (minor 0x56df8f21)
debugfs:  dx_hash -h legacy F.properties
                        Hash of F.properties is 0x6defc07e (minor 0x0)
debugfs:  dx_hash -h half_md4 -s 6d5319ae-528e-494e-873b-8453642d8990 F.properties
                        Hash of F.properties is 0x92b564ba (minor 0x4315a3ab)
debugfs:  dx_hash -h half_md4 -s 6d5319ae-528a-494e-873b-8453642d8999 F.properties
                        Hash of F.properties is 0x2df1194a (minor 0xe0ebfce6)


Pour ceux qui veulent aller plus loin, voici le code de Linux sur le File System ext4 pour la fonction readdir() : https://github.com/torvalds/linux/blob/master/fs/ext4/dir.c


Les applications autre que Java sont-elles concernées aussi ?
En fait, elles aussi sont concernées.  Un programme C effectuant ce listage des répertoires utilise la fonction système “readdir()” qui à son tour réagira selon le FileSystem installé.
C’est donc toute application quelque soit le langage (et pas seulement Java) qui peuvent avoir des difficultés à migrer sous Linux.  Encore faut-il bien écrire son application et éviter les doublons.

Conclusion
En une seule phrase: Java s’avère être plus sensible au changement de File System que d’OS.
Le changement d’OS peut faire changer le file.encoding, la Locale et impacte les appels JNI en cas de bibliothèques C native en 32 ou 64bits mais ce périmètre est en général connu et maîtrisé.
Ici, le File System perturbe les applications packagées en supposant que l’ordre de parcours de répertoire et de fichiers sera toujours en ordre alphabétique.
Comme souvent, le problème se situe dans des habitudes de programmation et d’intégration qui abaisse la vigilance et provoque l’apparition de certaines mauvaises pratiques.