Alternative zu MD5 gesucht

[Tom]

Hello,

ich muss für Files eine Identifikation schaffen, so wie es mit MD5() möglich wäre. Allerdings braufht MD5 zu lange... Die Performance geht damit vollkommen in die Knie.

Gibt es eine Kontrollsummenbildung, die vielleicht etwas mehr theoretische Doppelungen hat, die aber dafür weniger Performance frisst?

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom

[Maxx]

Hallo Tom,

ich muss für Files eine Identifikation schaffen, so wie es mit MD5() möglich wäre.

für eine einfache Prüfsumme die feststellt, ob Änderungen in einem Datensatz vorgenommen wurden verwende ich Adler32

Grüße,

Jochen

[Tom]

Hello Maxx,

ich muss für Files eine Identifikation schaffen, so wie es mit MD5() möglich wäre.

für eine einfache Prüfsumme die feststellt, ob Änderungen in einem Datensatz vorgenommen wurden verwende ich Adler32

Danke für den Tipp.
Probier ich morgen mal aus.

Von den dreien, die in PHP implementiert sind (sha1, crc32, md5) ist md5 bei ca. 160 Dateien im Test noch der schnellste.

In der Produktion müssen dann täglich ca. 6.000 Dateien geprüft werden, und das sollte tunlichst nicht länger als 3ß Minuten dauern...

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom

[Sven Rautenberg]

Moin!

In der Produktion müssen dann täglich ca. 6.000 Dateien geprüft werden, und das sollte tunlichst nicht länger als 3ß Minuten dauern...

Worauf geprüft?

Es gibt so viele schöne Dateieigenschaften, die man wesentlich schneller abprüfen kann, als den Inhalt durch eine Prüfsumme zu schicken.

Typische Dinge, die sich bei Dateiänderungen verändern (können):

• Dateigröße
• file-mtime
• file-atime

In Abhängigkeit von der Art der Dateiänderung muß außerdem nicht jedes Prüfsummenverfahren geeignet sein. Prüfsummen haben jeweils typische Aufgabenstellungen, auf die sie spezialisiert sein können, was ermöglicht, dass sie bei anderen Aufgaben scheitern können.

Nur mal angenommen, als Prüfsumme würde man einfach die Addition aller Bytes einer Datei nehmen - dann würden Veränderungen, die die gleiche Summe ergeben, nicht entdeckt werden. Genauso kann man bei MD5 reinfallen, weil das eine Megabyte an Daten dummerweise den gleichen Wert hat, wie eine komplett leere Datei mit 0 Byte.

Nur: Das Dateisummieren ist sicherlich schneller erledigt, als MD5 - aber die Mehrinvestition in MD5-Rechenzeit erzeugt eine höhere Sicherheit gegen solche dummen Zufälle. Die Summe aller Bytes einer Datei ist nämlich nicht gleichverteilt über den verfügbaren Zahlenraum, kleinere Zahlen kommen wesentlich häufiger vor, als sehr große - MD5 hingegen hat den Anschein, als sei genau das der Fall.

- Sven Rautenberg

[Tom]

Hello,

Es gibt so viele schöne Dateieigenschaften, die man wesentlich schneller abprüfen kann, als den Inhalt durch eine Prüfsumme zu schicken.

Typische Dinge, die sich bei Dateiänderungen verändern (können):

• Dateigröße
• file-mtime
• file-atime

Das war auch erst meine erste Idee.
Die nützt mir aber leider nichts.
Hier geht es um den _Inhalt_ der Dateien.

Die eine heißt "abcde - (1958)", die andere "ABCDE - 50er Jahre" und beide enthalten Sie denselben Inhalt. Alle Files sollen in eine DB eingetragen werden. Es soll keine doppelten Inhalte geben.

REPLACE macht es möglich...

Und da erschienen mir md5() oder ähnliche Verfahren die intelligenteste Lösung zu sein ;-))

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom

[Sven Rautenberg]

Moin!

Typische Dinge, die sich bei Dateiänderungen verändern (können):

• Dateigröße
• file-mtime
• file-atime

Das war auch erst meine erste Idee.
Die nützt mir aber leider nichts.
Hier geht es um den _Inhalt_ der Dateien.

Dein allererster Filter sollte dann aber trotzdem die Dateigröße sein.

Dateien können nicht identisch sein, wenn sie unterschiedliche Größen haben.

Und die Gruppen mit gleichen Größen kannst du dann mit MD5 "behandeln", um Duplikate zu entdecken.

Die eine heißt "abcde - (1958)", die andere "ABCDE - 50er Jahre" und beide enthalten Sie denselben Inhalt. Alle Files sollen in eine DB eingetragen werden. Es soll keine doppelten Inhalte geben.

Warum die gesonderte Datenbank? Das Dateisystem ist doch schon eine sehr gute Datenbank.

REPLACE macht es möglich...

Replace für was?

Was soll das Ergebnis der Aktion sein? Festzustellen, dass es doppelte Dateien gibt, ist ja nicht alles. Das muß doch dann irgendeine Form von Reaktion auslösen, beispielsweise, alle bis auf eine Datei zu löschen.

Programmtipp:
"FDUPES is a program for identifying or deleting duplicate files residing within specified directories."
http://premium.caribe.net/~adrian2/fdupes.html

- Sven Rautenberg

[Tom]

Hello,

Warum die gesonderte Datenbank? Das Dateisystem ist doch schon eine sehr gute Datenbank.

Die Dateien enthalten unterschiedliche Informationen, nach denen wahlweise und/oder kombiniert sortiert gelistet werden soll. Eine Datenbank ist da einfach noch der bessere Partner, wenn man nicht Cluster von Rechnern stehen hat, wie Google.

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom

[fanelf.de]

ich muss für Files eine Identifikation schaffen, so wie es mit MD5() möglich wäre. Allerdings braufht MD5 zu lange... Die Performance geht damit vollkommen in die Knie.

du brauchst eine identifikation ?????

Gibt es eine Kontrollsummenbildung, die vielleicht etwas mehr theoretische Doppelungen hat, die aber dafür weniger Performance frisst?

oder eine kontrollsumme ?????

md5 ist ein hash. dieser ist für schnellen zugriff gedacht und soll kollisionsfrei sein (eben hash).  oft wird md5 auch benutzt um veränderungen festzustellen.

eine kontrollsumme ist eine prüfsumme. diese dient nicht als hash sondern mehr bei übertragungen. daher sind kollisionen bedeutungslos. so etwas läßt sich einfacher bestimmen.

aber wie du mit md5 die performance in die knie bekommst bleibt ein rätsel.

[Tom]

Hello,

aber wie du mit md5 die performance in die knie bekommst bleibt ein rätsel.

Mir nicht.

PHP bestimmt mittels der md5()-Funktion der Reihe Nach die Ergebnisse von Files der Größe 3 bis 8 MByte. Das dauert dann schon ein bis zwei Sekunden...

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom

[Alexander Brock]

Hallo Freunde des gehobenen Forumsgenusses,

PHP bestimmt mittels der md5()-Funktion der Reihe Nach die Ergebnisse von Files der Größe 3 bis 8 MByte. Das dauert dann schon ein bis zwei Sekunden...

Du könntest versuchen, ob ein Systemaufruf von md5sum schneller ist (und das Ergebnis hier posten :-)).

Gruß
Alexander Brock

[Henryk Plötz]

Moin,

Du könntest versuchen, ob ein Systemaufruf von md5sum schneller ist (und das Ergebnis hier posten :-)).

Ist er in der Tat. Hier das Ergebnis meines total unwissenschaftlichen Mini-Benchmarks:

md5  sha1 crc32  null
python            1:30 3:54 1:41   0:04
php               2:40 4:00 1:58   1:13
system            1:03 3:53        0:13

Testobjekt: 1 Datei mit 50 Megabyte die aus Nullbytes besteht (dd if=/dev/zero of=foo bs=1M count=50).
Anzahl der Durchläufe: 100
Gemessen: user-Zeit, das was time in der zweiten Zeile anzeigt
(null zeigt die Zeit an die nur für das Einlesen der Datei ohne weitere Berechnung gebraucht wird)

[eddi]

Moi Moin!

php               2:40 4:00 1:58   1:13

welche Version genau?

Gruß aus Berlin!
eddi

[Henryk Plötz]

Moin,

welche Version genau?

PHP 4.4.2-gentoo (cli)

[Tom]

Hello,

Du könntest versuchen, ob ein Systemaufruf von md5sum schneller ist (und das Ergebnis hier posten :-)).

Der ist rasant schnell.
Wir haben Danke diesem Versuch inzwischen auch gefunden, woran es liegt.
Es ist nicht der md5-Algorithmus. md5() in PHP ist nur unwesentlich langsamer, als das direkt in der Konsole aufgerufene.

Aber wir müssen das Verfahren mit mehreren ins Linux-System gemounteten _Windows_ Dateisystemen durchführen. Und das ist der Flaschenhals. Die Files müssen zur Auswertung leider einmal vollständig gelesen werden.

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom

[Sven Rautenberg]

Moin!

Aber wir müssen das Verfahren mit mehreren ins Linux-System gemounteten _Windows_ Dateisystemen durchführen. Und das ist der Flaschenhals. Die Files müssen zur Auswertung leider einmal vollständig gelesen werden.

SMB ist arschlahm, das weiß man doch. Damit kriegst du keine gute Performance hin. Und lastest das Netzwerk aus.

Alternative Methoden würden mit Sicherheit besser funktionieren. Eine davon wäre das Eliminieren des Netzwerktransfers.

- Sven Rautenberg

[Tom]

Hello,

Alternative Methoden würden mit Sicherheit besser funktionieren. Eine davon wäre das Eliminieren des Netzwerktransfers.

Das wäre eventuell eine gute Idee.

Man könnte ja die MD5-Berechnung lokal auf dem entfernten Host anstossen, und dann nur die Tabelle der Pfade und md5-Codes abholen...

Ich werde das mal durchexerzieren und sollte der Thread dann noch existieren, hier das Ergebnis posten.

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom

[fanelf.de]

PHP bestimmt mittels der md5()-Funktion der Reihe Nach die Ergebnisse von Files der Größe 3 bis 8 MByte. Das dauert dann schon ein bis zwei Sekunden...

nicht php bestimmt was gemacht wird. php führt nur das aus, zu was es angewiesen wird. z.b. von einem programm des programmierers.
was sind dann die ergebnisse? und für was soll das gut sein????

deine frage ist:
ich muss für Files eine Identifikation schaffen, so wie es mit MD5() möglich wäre. Allerdings braufht MD5 zu lange... Die Performance geht damit vollkommen in die Knie.

was ist eine identifikation?
wenn du die files identifizieren willst, benötigst du ein eindeutiges merkmal für jede datei. z.b. einen hash.
daher solltest du den dateinamen (mit dem pfad) für md5 heranziehen. dieser sollte praktisch kollisionsfrei sein.

welchen sinn soll es haben den inhalt einer datei durch md5 zu jagen? dies dauert natürlich länger. hier ist auch die wahrscheinlichkeit einer kollision wesentlich größer. md5 hat nur 128 bit.

wenn du nur eine prüfsumme möchtest, gibt es sinnvollere verfahren, welche nicht kollisionfrei sein müssen. beispiele hierfür gibts im bereich datenübertragung oder datenspeicherung (z.b. crc).

[Tom]

Hello,

ich muss für Files eine Identifikation schaffen, so wie es mit MD5() möglich wäre. Allerdings braufht MD5 zu lange... Die Performance geht damit vollkommen in die Knie.

was ist eine identifikation?
wenn du die files identifizieren willst, benötigst du ein eindeutiges merkmal für jede datei. z.b. einen hash.
daher solltest du den dateinamen (mit dem pfad) für md5 heranziehen. dieser sollte praktisch kollisionsfrei sein.

Du bringst verschiedene Dinge durcheinander. Mir geht es hier um den Datei-Content, nicht um ihre Metainformationen.

Harzliche Grüße vom Berg
http://www.annerschbarrich.de

Tom