Optimaler Hash-Algorithmus und Strategie für Dateivergleiche, Verzeichnisbaum

[Rollo62]

Zitat von Delphi.Narium:

Die Daten bilde ich immer in 'ner Datenbanktabelle ab

Interessant, das ist auch eine Möglickeit.
Ich bin bisher davon ausgegangen, dass es wohl zu langsam wäre, aber stimmt, das muss es ja gar nicht.
Wie verwaltest Du denn da die Baumstruktur, mit selbst-referenzierten Keys in einer Tabelle?
Vielleicht hast Du dafür schon eine optimale SQL-Struktur gefunden, Baumstrukturen in einer DB sind etwas problematisch.

Mit FDMemTable könnte das schon ziemlich performant sein, vielleicht sogar mit sqlite, was noch weitere Vorteile hätte.

Was mich bisher nicht auf den Gedanken gebracht hat, war, das ich sowas wie ein Einlesen aller Verzeichnisse oder
ein Hinzufügen von Verzeichnissen einbauen möchte.
Mit Unterverzeichnissen und Dateien, da könnte eine DB etwas schwächeln, gegenüber einen optimierten Speicherliste mit Hash-Option.

Eigentlich wollte ich die Struktur immer on-the.fly laden, und dabei auf Änderungen prüfen,
aber ja, eine permanente DB würde das regelmäßige Einladen sparen.

Zitat von Michael II:

Ich würde auch Parameter, welche rasch zu gewinnen sind früh auswerten und jene, welche Kosten verursachen erst spät. Der Informationsgehalt der verschiedenen Parameter muss natürlich mitberücksichtigt werden.

Ja, ich möchte beim Einlesen möglichst schnell auf Änderungen Prüfen, bzw. Vergleichen ob sich Lokale und Remote-Verzeichnisse geändert haben.
Danke für die Vorschläge mit den zusätzlichen Parametern, aber im Moment reichen mir die JA/NEIN Aussagen zu Files welche geändert wurden, völlig aus.
Zusätzlich dazu wäre dann noch entsprechend der letzte Zuugriff interessant, aber optional.

Weiterhin war mein Gedanke, dass diese Struktur dan auch gleich das Navigieren in den Dateien übernehmen kann.
Also eine Klasse für Verzeichnisstruktur mit Navigation und schneller Hash-Suche.

Womöglich ist aber auch eine Trennung beider "Concerns" sinnvoller, gefühlt würde ich momentan aber eher alles in eine Baumstruktur packen,
um nicht noch viel Redundanz und Komplexität beim Aufrufer reinzubekommen.
Ausserdem wäre eine zentrale Klasse sicher fehlertoleranter auszulegen als zwei separate, die sich überschneiden können.

[Kas Ob.]

Hi,

Sorry if i am missing the subject,

I would like to suggest to skip any multi parameters, and use concatenation, example: MD5 could be more than enough and as "Delphi.Narium" mentioned use the file size this will make collision probability a lot smaller, but prefix the hash with the (aligned to 4 byte by zeros) size like this :
the MD5 hash for "This is MD5" = f6eda1d8b4b2dba89938db14285cf78a
Length("This is MD5") = 11 then your custom hash will be
0000000bf6eda1d8b4b2dba89938db14285cf78a

The advantage here :
1) removing the need for multiple parameters.
2) reduce the collision chance.
3) in its binary (non hex format) it can be used in Trees or DBs .. with only 20 bytes length.
4) if you have files size that need 64bit then use the lower 32bit only and it will be fine, this doesn't affect the collision chance, if there is too many big files then use 5 bytes for the file size, but this really not needed.
5) and as Stefan did point, use an optimized implementation for MD5.

[Delphi.Narium]

Also ganz kurz (oder eher doch etwas lang geworden ):

Es gibt eine Komponente für das rekursive Einlesen der Dateien. Je Datei wird ein Ereignis OnFile ausgelöst. In dem Ereignis wir der Dateiname an eine Komponenten übergeben, die die Datei liest und Dateigröße, MD5, Dateityp (sofern ermittelbar), ... in Attributen zurückgibt.
Danach wir für jede Datei genau ein Datensatz in der Tabelle (egal ob Datenbank oder Memorytable) angelegt (Spalten: einfach alle Werte, die ich im späteren Verlauf benötige(n könnte). Per AutoInc wird ein eindeutiger technischer Schlüssel festgelegt, mit dem kann man dann jederzeit jede Datei eindeutig identifizieren, ginge zwar auch über den vollständigen Dateinamen (der immer 'nen eindeutigen Index hat) ist per AutoInc aber einfacher zu handhaben, da ggfls. auch mal das Tag-Attribut einer Komponente ausreichen kann, um den Schlüssel jederzeit zur Verfügung zu haben.

Damit ist die Datenhaltung erledigt. Und sofern ich 'ne Datenbank nutze, muss ich auch nicht immer alle Daten im Arbeitsspeicher haben, sondern nur das, was ich gerade für 'ne Auswertung auch benötige.

Auswertungen erfolgen über SQL oder Filter, je nach dem, was Datenbank oder Memorytable gerade unterstützen.

Da mich für gewöhnlich nur die Dubletten interessieren, komme ich mit 'nem Select MD5 from tabelle having count(*) > 1 aus. Alles was da dann vorkommt, kann per Filter oder Select in weiteren Abfrage (oder etwas komplexeren SQLs) ausgewählt werden. Und nur aus dem so erstellten Ergebnis wird dann die Anzeige zusammengebaut. Für 'nen Tree muss man dann ggfls. die Pfadangabe am PathDelimiter aufbröseln, um den Baum optisch korrekt zu erstellen. Aber die ganze Baumstruktur für 'ne Million Dateien aufzubauen, nur um dann festzustellen, dass ich eventuell irgendwo 'ne Dublette haben könnte (oder eben auch keine), ist mir zu aufwändig.
Sind die Zeitstempel der Datei mit in der Tabelle, kann ich so auch auf Dateiänderungen prüfen und die entsprechenden Werte in der Tabelle ändern. Ist 'ne Datei schon in der Tabelle, muss ich nicht bei jedem Prüfvorgang alles neu einlesen, sondern nur das Neue oder das Veränderte. Das kann dann (je nach Datenmenge und Datenträgergeschwindigkeit) das eine oder andere Kaffeezwangspäuschen obsolet machen.

Kommt alles in 'ne Datenbanktabelle, muss ich aber auch ab und an mal prüfen, ob's das, was in der Tabelle steht, im realen Leben noch gibt und nicht inzwischen gelöscht wurde. Spätestens bei Auswertungen, die Dubletten erkannt haben, muss man dann noch mal auf die Existenz der Dateien prüfen, um nicht z. B. umbenannte Dateien mit altem und neuem Dateinamen als Dubletten zu identifizieren.

Es ist also nicht ganz banal, aber vermutlich einfacher, als mit komplexen Baumstrukturen im Arbeitsspeicher zu hantieren.

In kurz:

Einmal alles in 'ne Datenbanktabelle und dann per SQL auswerten. Wenn es dann tatsächlich was zu prüfendes, sprich Dubletten, gibt, kann man sich um eine entsprechende Optik kümmern.

[Benmik]

Ich möchte deine Aufmerksamkeit auf xxHash richten, das ich mittlerweile statt MD5 verwende. Die Seite von Cyan4973 auf Github ist interessant, ich habe den Wrapper von YWtheGod (auch auf Github) genommen.
Ich fand es auch günstig, zunächst nur den Anfang zweier Dateien zu vergleichen, insbesondere bei sehr großen Dateien. Da unter Windows immer mindestens 256 KB eingelesen werden, lese und vergleiche ich zunächst einmal diese ersten 256 KB, was schon einmal so gut wie alle nicht gleichen Dateien aussieben sollte.
Bei mir sind Hardlinks ein Thema, weswegen ich auch mittels GetFileInformationByHandle die FileID ermittle und vergleiche.
Mir haben auch die Hinweise von Uwe Raabe und Andreas Hausladen sehr geholfen.

[himitsu]

Es geht hier doch garnicht um extreme Sicherheit,
es geht auch nicht um Vergleiche "ähnlicher" Dateien,
sondern nur um Ändernung jeweils einzelner Dateien mit sich selbst,
womit die Möglichkeit extrem selten vorkommender Hash-Kollisionen sehr unwahrscheinlich ist, vor allem, wenn niemand (Hacker und Co.) absichtlich die Datei gezielt und mit enormem Aufwand daraufhin ändert.

* das Archiv-Attribut
* Datum des letzten Schreibzugriffs
* und ansonsten sind doch immernoch MD5/SHA1/SHA256 ausreichend

System.Hash :
THashMD5 (128)
THashSHA1 (128)
THashSHA2 (224,256,384,512)
THashBobJenkins (32, verwendet Dlelphi für Listen)

[Delphi.Narium]

Hab' einfach mal wieder die KI meiner Wahl befragt:

Zitat von Frage:

Wie hoch ist die Wahrscheinlichkeit, dass es bei der Verwendung eines MD5-Hashes beim Vergleich von Dateien zu einer Kollision kommt, d. h., das zwei unterschieldiche Dateien über einen identischen MD5-Hash verfügen?

Zitat von Antwort:

Die Wahrscheinlichkeit einer Kollision bei der Verwendung von MD5-Hashes hängt von der Anzahl der eindeutigen Eingaben ab, die gehasht werden. MD5 erzeugt einen Hash-Wert von 128 Bit, was bedeutet, dass es 2^128 oder etwa 3.4 x 10^38 eindeutige Hash-Werte gibt.

Die Wahrscheinlichkeit einer Kollision kann mit der Geburtstagsparadoxon-Formel berechnet werden. Wenn wir n als die Anzahl der eindeutigen Eingaben und d als die Anzahl der möglichen Hash-Werte betrachten, dann ist die Wahrscheinlichkeit P einer Kollision gegeben durch:

P ≈ n^2 / 2d

Für MD5, wenn wir annehmen, dass wir etwa 2^64 eindeutige Eingaben hashen (eine große, aber realistische Anzahl), dann ist die Wahrscheinlichkeit einer Kollision:

P ≈ (2^64)^2 / 2 * 2^128 = 1 / 2^64

Das ist eine sehr kleine Wahrscheinlichkeit, aber es ist nicht null. In der Praxis sind Kollisionen mit MD5 bekannt und das Verfahren wird daher für sicherheitskritische Anwendungen nicht mehr empfohlen. Es ist jedoch immer noch weit verbreitet für weniger kritische Anwendungen wie die Überprüfung der Integrität von Dateien.

Bitte beachten Sie, dass diese Berechnung eine Vereinfachung ist und die tatsächliche Wahrscheinlichkeit aufgrund verschiedener Faktoren, einschließlich der spezifischen Eigenschaften des MD5-Algorithmus, abweichen kann. Es ist auch wichtig zu beachten, dass selbst eine sehr geringe Kollisionswahrscheinlichkeit in bestimmten Kontexten ein Sicherheitsrisiko darstellen kann.

Zitat von Frage:

Wie verändert sich bei einem Dateivergleich die Wahrscheinlichkeit einer MD5-Hash-Kollision, wenn zusätzlich noch die Dateigröße und das Datum der letzten Dateiänderung mit berücksichtigt werden?

Zitat von Antwort:

Die Berücksichtigung zusätzlicher Informationen wie Dateigröße und Datum der letzten Änderung kann die Wahrscheinlichkeit einer Kollision beim Vergleich von Dateien erheblich reduzieren.

Wenn zwei Dateien denselben MD5-Hash haben, aber unterschiedliche Größen oder Änderungsdaten, dann können wir sicher sein, dass es sich um unterschiedliche Dateien handelt, auch wenn der MD5-Hash identisch ist. In diesem Fall würde die Kollision beim MD5-Hash nicht zu einer falschen Übereinstimmung führen, da die zusätzlichen Informationen (Dateigröße und Änderungsdatum) die Unterschiede aufzeigen.

Es ist jedoch wichtig zu beachten, dass diese Methode nicht vollständig vor Kollisionen schützt. Es ist theoretisch möglich (wenn auch extrem unwahrscheinlich), dass zwei unterschiedliche Dateien denselben MD5-Hash, dieselbe Größe und dasselbe Änderungsdatum haben. Aber die Wahrscheinlichkeit dafür ist so gering, dass sie in der Praxis vernachlässigbar ist.

Insgesamt kann die Berücksichtigung von Dateigröße und Änderungsdatum bei der Verwendung von MD5-Hashes zur Dateivergleichung die Sicherheit erheblich verbessern. Es ist jedoch immer noch empfehlenswert, sicherere Hash-Funktionen wie SHA-256 zu verwenden, insbesondere für sicherheitskritische Anwendungen.

Zitat von Frage:

Es ist aber doch im Rahmen des Möglichen, dass zwei Dateien mit gleichem MD5-Hash und identischer Dateigröße, aber unterschiedlichen Änderungszeitpunkten identisch sind, z. B. weil eine Datei von einem Datenträger auf einen andern kopiert wurde oder nur ein Kopieren unter einem anderen Dateinamen oder in ein anderes Verzeichnis erfolgte. Wäre es in diesem Falle nicht zielführender zum Vergleich nur Dateigröße und erst bei identischer Dateigröße zusätzlich den MD5-Hash zu verwenden? Wie würde sich dadurch die Wahrscheinlichkeit eines Kollision der MD5-Hashs verändern?

Zitat von Antwort:

Sie haben absolut recht. In der Praxis ist es durchaus möglich, dass zwei Dateien mit demselben MD5-Hash und der gleichen Größe, aber unterschiedlichen Änderungsdaten tatsächlich identisch sind. Dies könnte der Fall sein, wenn eine Datei kopiert oder unter einem anderen Namen gespeichert wurde.

In solchen Fällen könnte es sinnvoll sein, zuerst die Dateigröße zu vergleichen und nur bei Übereinstimmung der Größe den MD5-Hash zu berechnen und zu vergleichen. Dies könnte die Effizienz des Vergleichsprozesses verbessern, insbesondere wenn eine große Anzahl von Dateien verglichen wird, da die Berechnung von Hashes rechenintensiv sein kann.

Was die Wahrscheinlichkeit einer Kollision betrifft, so würde sich diese nicht ändern, da die Wahrscheinlichkeit einer Kollision nur von der Anzahl der eindeutigen Eingaben und der Größe des Hash-Raums abhängt (bei MD5 sind das 2^128 mögliche Hashes). Die Reihenfolge, in der Sie die Größe und den Hash vergleichen, hat keinen Einfluss auf die Wahrscheinlichkeit einer Kollision. Es ändert jedoch die Wahrscheinlichkeit, dass eine Kollision zu einer falschen Übereinstimmung führt, da Dateien mit unterschiedlichen Größen bereits vor der Hash-Berechnung ausgeschlossen werden.

Es ist jedoch wichtig zu beachten, dass diese Methode immer noch nicht vollständig vor Kollisionen schützt. Es ist theoretisch möglich (wenn auch extrem unwahrscheinlich), dass zwei unterschiedliche Dateien denselben MD5-Hash und dieselbe Größe haben. Aber die Wahrscheinlichkeit dafür ist so gering, dass sie in der Praxis vernachlässigbar ist. Für sicherheitskritische Anwendungen wird daher empfohlen, sicherere Hash-Funktionen wie SHA-256 zu verwenden.

Mein Fazit:

Eine Tabelle mit Dateinamen, Dateigröße, MD5-Hash und den Änderungsdaten sollten für die gestellte Aufgabe ausreichend sein.

Das Erstellen einer Baumstruktur ist nicht erforderlich, es sei denn, man möchte es für die Anwender schön aussehen lassen. Dann reicht es aber aus die Baumstruktur nur für die Daten zu erstellen, die die Anwender auch zu Gesicht bekommen sollen und zwar erst dann, wenn die Daten zur Anzeige gebracht werden.

Mein Vorgehen wäre:

Rekursives Einlesen der Verzeichnisstruktur(en) und je Datei Pfad und Name, Dateigröße und Änderungsdaten in einer Tabelle speichern, dazu reichen FindFirst und FindNext mit TSearchRec aus.

In der so erstellten Tabelle alle Sätze suchen, bei denen die Dateigröße mehr als einmal vorkommt:

SQL-Code:

select * from tabelle a where exists (
  select 1 from tabelle b 
  where a.dateigroesse = b.dateigroesse
  group by b.dateigroesse having count(*) > 1
)
order by a.Dateigroesse;

Für die so ausgewählten Dateien den MD5-Hash berechnen und in der Tabelle speichern.

Anschließend die Dateien suchen lassen, bei denen die Kombination aus Dateigröße und MD5-Hash mehr als einmal vorkommen.

SQL-Code:

select * from tabelle a where exists (
  select 1 from tabelle b 
  where a.dateigroesse = b.dateigroesse
  and a.md5 = b.md5
  group by b.dateigroesse, b.md5 having count(*) > 1
)
order by a.Dateigroesse, a.md5;

Aus dem Ergebnis wird dann die Anzeige für die Anwender befüllt, egal ob als TreeView, ListView oder auch einfach nur in 'nem DBGrid.

[Rollo62]

Hallo Delphi.Narium,

ich bin nicht ganz sicher ob Du nur die Hash-Verwaltung beschreibst, oder ob Hash und Tree-Verwaltung zusammen integriert sind.
Ich hatte ja schon geschrieben, dass dies vielleicht zwei verschiedene Aufgaben sind, die man nicht mischen sollte.
Persönlich fände ich das Mischen beider Aufgaben aber sehr sinnvoll, eben weil es dann keine Redundanzen und Fehler durch getrente Datenhaltung auf das gleiche physikalische System geben kann.

Ich meine Du beschreibst das aufnehmen der Hashes in die DB usw., und dann nur am Rande, dass daraus Tree, ListView usw. erstellt werden können.
Welche Struktur schlägst Du denn dafür vor?

Ich sehe dafür erstmal zwei sinnvolle Optionen in einer DB, vielleicht gibt es aber noch weitere:

Delphi-Quellcode:

-- Adjacency List
CREATE TABLE FileSystem (
    id INT PRIMARY KEY,
    parent_id INT,
    name VARCHAR(255),
    hash_value VARCHAR(255),
    type VARCHAR(50),
    FOREIGN KEY (parent_id) REFERENCES FileSystem(id)
);

-- Nested Set
CREATE TABLE FileSystem (
    id INT PRIMARY KEY,
    name VARCHAR(255),
    lft INT,
    rgt INT,
    hash_value VARCHAR(255),
    type VARCHAR(50)
);

In jedem Fall ist der "hash_value" sozusagen nur ein nützliches Abfallprodukt, mit dem sehr schnell verifiziert werden kann,
ob es eine Datei bereits im System gibt und wie oft, unabhängig von der zu Grunde liegenden Baumstruktur.

Das trifft das was ich suche schon ganz gut, danke sehr für die Idee mit der DB, das scheint eine Menge Vorzüge über einer spezifischen Klasse zu haben.

Meine Frage war zu Deiner Erfahrung mit "Adjacency List" bzw. "Nested Set" oder eventuell auch "Flat table" mit kompletten Pfadangaben,
was davon sich für das Durchlaufen von Filesystemen am besten eignet.

Ich muss wahrscheinlich öfters die gesamten Filesysteme abgleichen, eben weil es mehrere Parteien gibt, welche unabhängig voneinander darauf zugreifen können.

Remote-Verzeichniss (es kann mehrere geben)
- ist ein zentrales Filesystem mit entfernten Daten, gehostet auf einem Fileserver im Internet
- es kann durchaus mehrere, redundante oder auch ergänzende Remote-Verzeichnisse geben, auf verschiedenen Servern
- dieses kann auf verschiedenen Wegen bearbeitet werden (z.B. automatisch aus einem anderem Dokumentenmanagementsystem, manuell per Website)
- kann über verschiedene Protokolle bearbeitet werden (z.B. FTP, REST-API, direkt über WebClient auf dem Serversystem)
- das von verschiedenen Parteien aus bearbeitet werden kann (automatische Ausleitungen von verschiedenen Systemen)
- eine Verwaltung von Änderungen, Verzeichnisbaum auf dem Server ist erstmal nicht so ohne Weiteres möglich.
- die Möglichkeit eine DB auf dem Server zu halten, welche das Ganze zentral abbildet, wäre denkbar ist aber auch eher ungewünscht.



Lokal
- ist eine lokale Kopie zur Zusammenführung, Bearbeitung und Analyse spezifischer Daten (lokal um den Server nicht zu belasten)
- die lokale Kopie sollte möglichst nur bei Änderungen aktiv werden, daher die Frage nach Vergleich ganzer Baumstrukturen mit Hash
- insbesondere das Einstellen neuer Dateien soll abgeprüft und verhindert werden (das gleiche File, mit anderem Namen, an andere Stelle).


Eine Möglichkeit wäre noch das Erzeugen und Speichern von Fingerprints (*.md) auf den Servern, was aber auch eher ungewünscht ist.
Die Datenmengen sind jedenfalls nicht so groß, dass eine Synchronisation Remote-Lokal generell ein Problem wäre.


Deshalb trifft der Vergleich zu GIT/GitHub von Benmik schon ganz gut zu, nur eben geht es in erster Linie um binäre Dateien, nicht nur um Text.

Es gäbe noch einen anderen Vergleich, z.B. mit einem FTP-Client, welcher auch Locale und Remote Filesysteme abgleichen kann,
aber nicht unbedingt Änderungen in den Files erkennen kann.

Ich denke der Ansatz mit einer DB ist einen Versuch Wert, das werde ich mal nächste Woche angehen.

[Delphi.Narium]

Habe momwentan keine Zeit ausführlich zu antworten, bitte hab' da etwas Geduld.

Ja, ich beschreibe nur die Hash-Verwaltung. Einen Baum halte ich für überflüssig. Mir erschließt sich nicht, wofür er nützlich sein sollte, außer für die Anzeige der Daten. Dann kann man ihn mit 'nem Treeview gezielt aus der benötigten Teilmenge der Tabelle erstellen.

Die Baumstruktur für die Anzeige kann man immer "on the fly" aus den Pfadangeaben und dem Dateinamen erstellen und muss sie nicht permanet vorhalten, zumal sie für das Erkennen von Dubletten, ... keinerlei Mehrwert hat.

[Stevie]

Zitat von Benmik:

Ich möchte deine Aufmerksamkeit auf xxHash richten, das ich mittlerweile statt MD5 verwende. Die Seite von Cyan4973 auf Github ist interessant, ich habe den Wrapper von YWtheGod (auch auf Github) genommen.

FWIW xxh32 gibt's auch als native Implementierung in Spring4D (natürlich für Windows in asm implementiert, somit durchaus vergleichbare Performance).
Ist seit 2.0 die Standard Hashfunktion für Dictionary und Co

[Benmik]

Zitat von Stevie:

FWIW xxh32 gibt's auch als native Implementierung in Spring4D (natürlich für Windows in asm implementiert, somit durchaus vergleichbare Performance).Ist seit 2.0 die Standard Hashfunktion für Dictionary und Co

Ich habe mal Spring.Hash und XXHASH verglichen (1.400 Dateien, 14,3 GB); Letzteres hat ja auch eine 64 Bit-Implementierung. Spring.Hash und HashXXH32 waren genau gleich schnell, HashXXH64 jedoch spürbar (20% - 25%) schneller. Erstaunlich. Das ASM bringt offenbar gar nichts.

Hat denn das MD5 beim Dateivergleich überhaupt eine Existenzberechtigung? Es ist ja offenbar unfassbar langsam.