Auflistung aller Files + suche nach Duplikaten?

Hi Leutz,

Ich will ein Script oder nen Programm schreiben was sämtliche Dateien auf unserem Fileserver auflistet (Pfad, Dateiname, Dateityp, Dateigröße, CHMOD-Status, wann zu letzt angefasst, wem gehört sie) und anschliessend soll es noch möglich sein nach gleichen Dateien zusuchen und auszugeben.

Das könnte man denk ich mal alles in Form von nem Shell-Script schreiben mit den entsprechenden Befehlen (muss ich mal schauen kenn mich da nicht so sehr aus).
Wahrscheinlich liese es sich das irgendwie mit dem find-Befehl realisieren, aber ich denke bei über 1 Terrabyte an Daten aufm Server wird das vermutlich ewig dauern. Vielleicht ginge es schneller wenn man dass ganze irgendwie in ne Datenbank schreibt (wie keine Ahnung, vielleicht kann mir dabei auch jemand hier helfen) und dann dort sucht? (wie der locate Befehl)
Gibs da vielleicht ne effizientere Idee oder würd es darauf hinaus laufen? Könnt ihr mir da Tipps geben oder gar etwas helfen?
Ich weiß imo noch überhaupt nicht wie ich das mit der Datenbank machen kann und wie ich nach der Auflistung aller Files dann noch nach gleichen Files suchen soll (wenn es geht natürlich vergleich des Inhaltes einer Datei, nicht nur Dateiname und -größe vergleichen)?

Ich wär euch über jeden Tipp und jede Hilfe dankbar!

sirzero schrieb:

Das könnte man denk ich mal alles in Form von nem Shell-Script schreiben mit den entsprechenden Befehlen (muss ich mal schauen kenn mich da nicht so sehr aus).
Wahrscheinlich liese es sich das irgendwie mit dem find-Befehl realisieren, aber ich denke bei über 1 Terrabyte an Daten aufm Server wird das vermutlich ewig dauern.

Zum Vergrößern anklicken....

Ich würde sogar für einen ersten Ansatz einen rekursiven ls mit entsprechenden Parametern nehmen.

Ich weiß imo noch überhaupt nicht wie ich das mit der Datenbank machen kann und wie ich nach der Auflistung aller Files dann noch nach gleichen Files suchen soll (wenn es geht natürlich vergleich des Inhaltes einer Datei, nicht nur Dateiname und -größe vergleichen)?

Zum Vergrößern anklicken....

Wenn du auf Dateiinhalt gehen willst wird natürlich die Laufzeit erheblich vergrößert, weil du nicht nur auf die Verzeichniseinträge sondern auch auf den Datenbereich zugreifst. Aber egal: Hier wäre eventuell ein Lösungsansatz, für jede Datei eine Prüfsumme zu bilden (z.B. mit sum -r) und diese zu vergleichen. Schau dir einmal "man sum" an.

Ein ähnliches Problem wurde übrigens hier behandelt:
http://www.linux-club.de/viewtopic.php?t=31364

notoxp schrieb:

Ich würde sogar für einen ersten Ansatz einen rekursiven ls mit entsprechenden Parametern nehmen.

Zum Vergrößern anklicken....

Yup, Info über Dateigröße mitnehmen und die komplette Liste danach sortieren, denn nur was gleich groß ist kann auch identisch sein - sofern die Dateien nicht alle gleich groß sind kann man den Aufwand von n^2 auf (annähernd) n senken...

also die Abschätzung von panamajo kann ja wohl nur als dummer Schuss ins Blaue abgetan werden denn wo sollen bitte die n^2 herkommen?

schauen wir uns das Problem mal an:

gegeben:
viele Dateien (1TB klingt viel, können aber sehr wenig Dateien sein, ich hab schon Simulationen laufen lassen, die pro Lauf einige 10-100 GB an Daten in einer Datei produzieren, hier ein wenig Parameter variierne und das TB ist schnell voll), ich gehe aber mal von 'normalen' Daten aus, also 1TB== viele Dateien

Ziel:
1. Suchen in dem Datenbestand und Zugriff auf viele Daten, evtl. auch noch Statistiken etc

2. gesucht Duplikate:
hier ist jetzt erst mal die Frage, nach welchen Duplikatvariablen soll gesucht werden, nur identischer Inhalt? oder auch gleicher Zugriff, gleiches Datum, gleicher Name, etc.

Zu Punkt 1: sinnvoll erscheint mir bei dieser Anforderung die Anwendung einer relationalen Struktur (hier ist die Frage, ob es eine DB sein soll, oder ob es verschiedene Textdateien auch tun

Problem 1: wie gehst Du mit Links um?

Problem 2: wie stellst Du sicher, dass die Liste aktuell bleibt, soll es dynamisch sein, müsstest Du direkt in den Filesystemtreiber eingreifen und bei entsprechenden Zugriffen die DB aktualisieren, oder aber ein Meta-Filesystem drüberlegen. Alternativ könnte auch ein Blick auf die Jounal-Bäume sinnvoll sein, ob man da etwas hacken könnte
reichen relativ statische Daten, kann das durch ein Script erledigen, dass 1x pro Zeiteinheit läuft.

Zu Ziel 2: die Duplikatsuche kann dann relativ einfach auf der in 1 angelegten Datenbasis stattfinden, hier ist dann nur eine entsprechende Indizierung für die passenden Schlüssel nötig (eine Variabilität spricht für eine DB oder mehere Textdateien, Vorschlag siehe unten)

machen wir eine Aufwandsabschätzung: den Index kannst Du mit einem Durchlauf erschlagen, d.h. O bzgl. der Dateien, allerdings muss hier bei entsprechenden Rekursionen die Baumgröße und die temporären Daten (Verzeichnisse) beachtet werden, ob es evtl. Sinn macht, alle Verzeichnislisten nur rekursiv im Speicher zu halten, oder ob die auch ausgelagert werden müssen.

Anschließend muss sortiert werden, und da müssten bei manueller Realisierung mit je einer Sortierung pro Schlüssel (Größe, Name, evtl. Hash, ...) also m*O(n log n), da m<<n reicht ein O(n log n) als Abschätzung

Wie richtig betrachtet, müssen bei Duplikaten die Schlüsselwerte gleich sein (d.h. gleiche Größe, gleicher Name,...), also kann im Anschluss je nach Schlüssel in O bei linearen Textdateien bis O(log n) bei entsprechenden Suchbäumen gesucht werden.

Bei vielen csv-Textdateien nach diesem Muster:

MASTER:
lfd-Nummer; Name; Pfad; Größe; MD5-Hash; CTIME; ...

KEY:
KEY ; lfd-Nummer
(also Abbildung Name -> lfdNummer oder Größe->lfdnummer) die jeweils nach dem Key-Wert sortiert sind kann man für eine Datei XXX den entsprechenden Schlüsselwert KEY_xxx berechnen und wenn der in der KEY-Datei nur einmal drin steht, gibts kein Duplikat, sonst bekommt man alle lfd-Nummern der Duplikate, deren Details dann aus der MASTER-Tabelle kommen

damit kommen wir zu einem Aufwand von:
einmalig: O(C*n) mit sehr großem C für das durchlaufen der Dateien,
m mal: O(n log n) sortieren für m Keys

d.h. O(C+n) + m* O(n log n)

pro Suche 2*O(c*n) mit kleinem c oder entsprechend weniger bei passenden Suchdatenstrukturen.

Die c und C sind die Konstanten, die die Filesystemzugriffe beschreiben, in der Theorie fallen die noch unter den Tisch, und m ist so klein, dass es einmalig vereinfacht O(n log n) sind und dann entsprechend der Suchaufwand

von einem O(n^2) sind wir zum Glück weit entfernt

ganz konkret: ich würde die Daten in ein Datenbanksystem schreiben (postgresql oder mysql) das Schema ist einfach, eine Tabelle mit entsprechenden Indizes auf den ganzen Schlüsselwerten. Ein gutes System liefert dann die Suchergebnisse auch nicht mit O sondern weniger, so dass Du sparst. Zusätzlich fallen die O(n log n) weg, da die Sortierungen implizit passiert und mit den entsprechenden Datenstrukturen eher im Bereich von O(log n) liegen, so dass es sich um ein einmaliges O + O(log n) pro Abfrage)

Das Script muss halt nur über das Dateisystem iterieren, bei normalen Dateisystemzugriffen halt rekursiv in einem DFS-Algo wobei wie beschrieben die Grenzen auf dem Stack berücksichtigt werden müssen, hier weiß ich nicht, wie gut die Bash geeignet ist

TeXpert schrieb:

ganz konkret: ich würde die Daten in ein Datenbanksystem schreiben (postgresql oder mysql) das Schema ist einfach, eine Tabelle mit entsprechenden Indizes auf den ganzen Schlüsselwerten.

Zum Vergrößern anklicken....

Das müsste man ausprobieren. Eventuell würde ein "normaler" Linux-sort schon ausreichen. Mit diesem habe ich schon einmal eine Kundendatei mit 3,5 Mio Sätzen nach PLZ sortiert. Das hat etwa eine halbe Stunde gedauert. Allerdings nützt die Zeitangabe nicht viel, da das schon 5 Jahre zurückliegt und ich die Rechnerkonfiguration nicht mehr weiß.

Was ich mir gemerkt habe: Wenn man einen entsprechend großen Temp-Bereich auf der Festplatte hat, ist ein sort kein Problem und vielleicht schneller, als eine ganze DB aufzubauen.

wie ich schon schrieb es kommt drauf an, bei einer Datei ist das ok, aber das Problem hier sind ja m Schlüssel, die alle sortiert werden müssen und wenn man dann sucht kommt man nie unter O so dass es langfristig sinnvoller sein kann eine DB zu nehmen... zusätzlich steht ja auch noch das Thema der Aktualisierungsrate im Raum.

WOW...das musst ich jetzt glaub ich ein paar mal lesen um es zu verstehen und dann noch soviel -> DANKE für diese Ausführliche Beschreibung

Also, ich hab es mir auch so gedacht jetzt, dass die komplette Auflistung mit den entsprechenden Indizes in eine MySQL Datenbank kommen und dass man danach dann in dieser Datenbank nach den identischen Daten suchen kann.

Ich denke für vergleichen, ob Daten gleich sind sollten die Parameter Dateiname, Dateigröße, Datentyp und eine CRC oder MD5 Checksumme genügen oder?

Zu dem Script...ich hab keine Vorstellung, da wenig Ahnung, ob es besser ist das Script in PHP, PERL oder ein Shell-Script (wäre das einzige wovon ich imo ahnung hätte) zu schreiben und die Ausgabe dann gleich in die Datenbank zu leiten. Hab ich noch gar keine Vorstellungen wie das geht, aber wenn ihr mir vielleicht sagen könntet welche Programmiersprache vielleicht am besten dafür geeignet ist, werd ich das schon hinbekommen. *hoff*

So waren noch mehr offene Fragen? Achja, also ich hab mir gedacht, dass das Script dann immer Nachts die DB aktualisiert.

mfg sirzero

sirzero schrieb:

So waren noch mehr offene Fragen? Achja, also ich hab mir gedacht, dass das Script dann immer Nachts die DB aktualisiert.

Zum Vergrößern anklicken....

Na dann ist eine "echte DB" auf jeden Fall besser. Die neuesten Daten könnte man mit find suchen.

Für perl gibt es entsprechende Module, mit denen man eine DB z.B. via ODBC ansprechen kann. Aber sicher gibt es noch andere Lösungsmöglichkeiten. Wenn du den Vorschlag mit der Prüfsumme durchführen willst, reicht eventuell ein find mit integriertem ls und anschließend ein sum (oder ähnliches). Damit bewegst du dich sowieso schon auf Shell-Ebene. Deswegen würde ich dir empfehlen, einfach den ersten Ansatz als Shell-Script zu schreiben.

Wenn du unbedingt etwas neues machen willst, würde ich natürlich perl empfehlen...

als Sprache würde ich Dir auch zu einer der P* Sprachen raten (also Python, Perl, PHP) je nachdem in welcher Du fit bist, denn mit Bash möchte man nicht wirklich SQL-Strings zusammen bosseln geht auch aber ist teilweise mörderisch...

und welche Daten Dir reichen um Duplikate zu finden, musst Du schon selber wissen denn was ist ein Duplikat, nur die die Byteweise identisch sind? oder müssen die auch den Gleichen Zeitstempel haben? reichen die gleichen Namen etc, etc.


und sirzero, wenn Du nach ein paar mal lesen noch Fragen hast einfach stellen...