[gull] Petit problème de maths, pour créer de liens

[Félix Hauri]

On Wed, Apr 30, 2008 at 11:45:04PM +0200, Marc Mongenet wrote:
> MD5 étant cracké, s'il faut se protéger contre des collisions
> malicieuses, alors il faut comparer l'intégralité des fichiers.
Bon, il s'agit d'archives persos, à priori pas de malice, donc.

On Thu, May 01, 2008 at 02:01:03PM +0200, Daniel Cordey wrote:
> Est-ce bien necessaire :-)
Tout est relatif!

>...
>> Donc, sans repeter ce que Marc Mongenet a deja dit, je me pencherais sur la
> necessite d'utiliser md5 sur tous les fichiers...
>
> En effet, dans le but de perdre un minimum de temps, je me contanterais donc
> d'etablir une liste croissee inode et... taille des fichiers... Puis, pour
> tous les inodes ayant la meme taille, je calculerais le md*...
Hmmm..
Oui, c'est sûr, la taille des fichier est un élément important de
comparaison, et si j'évite de calculer des md5 sur des fichiers
parfaitement uniques, je vais effectivement économiser du temps
dans la première étape, mais ce n'est pas la plus longue.

Mais merci, cela modifie la perspective:
A savoir que les md5 soit identique, ainsi que les tailles de fichiers
ne garanti pas que les fichiers soit identiques... Mais à partir de quel
pourcentage de comparaison des fichier puis-je être à peu près
tranquille? La question demeure...

On Thu, May 01, 2008 at 05:03:56PM +0200, Sebastien Chassot wrote:
> premièrement tu parles de gagner du temps en ne vérifiant qu'un
> pourcentage des fichiers dans la phase deux. Est-ce que ce ne serait pas
> mieux de le faire dans la phase un (en sortant un md5 sur qqs block
> seulement) puisque tu risques au pire d'avoir plus de fichiers à
> tester ? Le gains de temps est peut-être faible mais au moins sans
> risque.
Hmmm oui, l'idée est intéressante, mais la lecture d'un seul fichier
est nettement mois difficile que la comparaison de deux fichiers,
c'est pourquoi je compte surtout rationnaliser la deuxième étape
(ce sera en fait la troisième, puisque je vais simplement ajouter
une première étape qui consistera au recensement pur et simple,
afin de ne calculer, en deuxième étape, les md5 que sur des fichiers
dont la taille ne sera pas unique après la première étape. J'espère
ainsi terminer la liste de md5 environ 5 à 10% plus rapidement.
Je vais en profiter pour trier ma liste par nro d'inode, afin de
réduire les déplacement de tête de lecture d'un bout à l'autre du
disque... )

> Avant de comparer l'intégrité de deux fichiers j'imagine que tu ne le
> feras que pour des fichiers qui se ressemblent "beaucoup" et que tout
> les testes plus rapides et qui éliminent les faux doublons auront été
> effectués (taille,...)
Si taille et md5 correspondent, c'est qu'ils se ressemblent ``beaucoup''!

>...
> Encore une fois la différence est à mon avis
> théorique mais pas significative.
>
> Si tu as plus de chance de gagner 1000 fois d'affilée au loto que
> d'avoir 2 fichiers avec 1% de ressemblance et une somme md5 identique,
> tu peux prendre le risque.
Le problème avec les risques statistiques vient de la loi de Murphy,
très importante dans ce genre d'opérations...

On Thu, May 01, 2008 at 06:55:48PM +0200, Yves Martin wrote:
> Comme Sébastien, il me semble judicieux de faire un "stat" sur le fichier
> pour faire une première comparaison sur la taille du fichier avant de
> faire un hachage sha512sum par exemple sur des fichiers de taille identique.
Oui, alors c'est noté! Je prendrais en considération la taille des
fichiers! ;-)

>
> Tout dépend des données manipulées mais SHA a nettement de risque de collision
> que MD5... Mais il reste encore possible que si les fichiers sont des logs
> répétitifs d'une application, des collisions soient fréquentes (même hash pour
> des contenus différents)
Oui, mais sha et particulièrement sha512 est nettement plus cher que
md5, il me ferait passer la première étape de 3heures à environ 1 jour
et demi...

> Ce qui est dommage en terme de performance est de lire un fichier deux fois:
> une fois pour le hash, une fois pour le diff.
Ça, je ne te le fais pas dire, je vais encore réflechir un brin,
peut-être que triant ma liste d'abord par taille. puis pour chaque
taille rechercher les md5 identiques, alors je pourrais profiter du
cache pour lire un maximum de fichier effectivement une seule fois...

> Quelque soit le type de données, un "diff -q" sur des fichiers de taille
> identique devrait être fournir une réponse fiable sans passer par des sommes de
> contrôle - en supposant que le diff sorte au premier octet différent, c'est
> autant d'économisé en accès disque.
On peut utiliser diff pour des fichiers binaires?

J'utilisais cmp, en me disant que ce n'est probablement pas le
meilleur choix!?...

> Tes temps d'exécution me laisse penser qu'il y a une optimisation possible de
> ton implémentation.
> En effet, si la génération des hash sur 80 Go te prend 6 heures, avec une
> lecture complète des fichiers donc - je ne comprends pas que le diff des
> fichiers avec hash identique (donc moins de fichiers) prennent 3/4 jours ??
Ben c'est beaucoup plus facile de lire 80Go fichier par fichier que de
lire systèmatiquement deux fichiers simultanement pour les comparer...

> En moyenne, combien de multiples sont détectés pour un fichier ?
Beaucoup! Il s'agit d'archives de machines différentes mais basées sur
les même programmes et distributions, avec des sources de données
similaires. En fait les fichiers à un seul exemplaire sont plutôt rares...

> En fonction de cette statistique, une optimisation pourrait être l'usage d'un
> algorithme de comparaison de N fichiers en une passe (N lectures) - au lieu de
> les comparer 2 par 2 (2*(N-1) lectures).
Hmm oui. cela pourrait effectivement faire jouer la chose...
... comparer N fichier en N lecture et en ressortir X séries de
fichiers identiques... pas évident. mais à réflechir...

> Comment implémenter une comparaison par N: ouvrir N file descriptor en mmap et
> comparer par bloc de 4k - 2 par 2 en mémoire - normalement la gestion des
> fichiers en mémoire cache par Linux devrait t'éviter des lectures multiples du
> disque, le bloc du premier fichier servant de référence étant en
> cache.
En n'oubliant que le premier n'est peut être pas identique à aucun,
mais le deuxième identique au qatrieme et au huitième, tandis que le
troisième est lui identique au 54ème... Algorithme à creuser...

> Voilà pour la théorie - en pratique il faut voir avec les possibilités de ton
> langage de programmation favori.
Je, pour l'instant, le fais en perl, mais à voir, je risque de passer
le tout en lisp... A suivre;-)

Merci à tous pour vos précieux points de vues.

-- 
 Félix Hauri  -  <felix at f-hauri.ch>  -  http://www.f-hauri.ch