Mit Bash durch alle Verzeichnisse inklusive Unterverzeichnisse

Mit find durch den Verzeichnisbaum laufen und erst mit -exec Dein Skript aufrufen?

Zitat von masi

Mit find durch den Verzeichnisbaum laufen und erst mit -exec Dein Skript aufrufen?

Wäre auch meine Vorgehensweise. Entweder mit -exec oder die Treffer mit pipe (|) an xargs übergeben

Wie viele Dateien sind es denn ingesamt (größenordnungsmäßig), wie eng bist Du an bash gebunden, und was hast Du mit den Dateien vor?

läuft bei dir ein locate?

OK, zu große Nummer für mich.

Ich hab sowas auch schonmal gemacht. Ist aber nicht ganz fertig geworden. Aber ein paar Tipps hätte ich noch im Kopf.

Bei find gibt’s den Parameter „-type d“ der liefert nur die Verzeichnisse.

Ich hab gern temporäre Zwischenergebnisse verwendet. Die sind zwar recht groß, können aber Zeit sparen, wenn du verschiedene Ansätze probierst.

Bei der Suche nach gleichen Dateien hab ich hauptsächlich die Größe als Kriterium verwendet. Eine Liste der Dateien mit der Größe vorne und dem Pfad dahinter, sortiert (mit sort) kannst du dann z.B. mit awk nach aufeinander folgenden Zeilen mit gleicher Größe suchen.

Das mit den Inodes verstehe ich nicht, das klappt doch nur bei Hardlinks oder automatisch deduplizierendem Filesystem.

Der übliche Weg dafür ist, find mit xargs zu kombinieren:

find . -print | xargs <befehl>

xargs sammelt so viele Zeilen auf stdin ein, wie sich auf einmal an einen Befehl als Argumente übergeben lassen, und ruft dann <befehl> damit auf.

find kennt -print0 als Option und xargs kennt -0, beide kombiniert man, wenn die Dateinamen Spaces und oder Newlines enthalten dürfen.

Mir fällt da das Hilfsprogramm/der Befehl 'fdupes' ein. Ist schon 8 Jahre alt, funktioniert aber immer noch.

Du hast oben geschrieben, dass es Dir vor allem auf Geschwindigkeit ankommt.

Ich fürchte, dann ist die bash doch wohl raus. Vor allem, wenn Du immer wieder "externe" Programme wie md5sum, grep und cut aufrufen möchtest.

Schau Dir doch mal python an. da bist Du einerseits näher am Betriebssystem , kannst immer noch fast wie gewohnt scripten und bleibst zumindest zur Laufzeit des Programms im gleichen Kontext.

Für den letzten boost kann man python code aber auch kompilieren

Auch könntest Du Dir das FS ansehen. Da gibt es durchaus welche, die mit vielen kleinen Dateien besser klar kommen als andere

Die Aufgabe selbst habe ich noch nicht ganz verstanden.

Wenn es darum geht identische Dateien (gleiche Inodenummer) zu identifizieren, also quasi die selbe Datei, dann gibt es sicher bessere Methoden als sich zu jedem zeitpunkt jede datei anzusehen um zu schauen, auf welche Inode sie zeigt um dann eine weitere Dateien zu finden, die den gleichen inode benutzen.

Ich stelle mir vor, dass es möglich sein müsste alle Aufrufe der Library , welche die Funktion bereitsellt, welche von "ln" (also ohne -s) bzw. aus Programmen heraus aufgerufen wird, zu protokollieren. Dann pflegt sich diese "DB" quasi von selbst und ist jderzeit aktuell.

Ich habe sowas ähnliches mal vor Jahren auf einem Amiga gemacht

Noch ne Idee und noch eine Anmerkung

zuerst die Idee:

Mit "find . -printf %n%p\\n"

bekommt man eine Liste von Filenamen zusammen mit der Anzahl der Hardlinks, die es zu diesem File gibt. Wenn man man dann noch, wie oben beschrieben, den type mit angibt, kann man sich auf Dateien beschränken und directories ausklammern. Evtl. muss man noch -noleaf mit angeben

Dann kann man sich auf das Konzentrieren, was einen hard link count >1 hat. Find hat dafür sogar einen test befehl (-links)

Dann die Anmerkung:

Ich habe gerade mal ein find . | wc in einem Verzeichnis gemacht, welches rekursiv 1, 7 mio Dateien enthält. Das hat etwa 1min22 gedauert.

Aktuell lasse ich einen Befehl laufen, der für jede dieser Dateien einen ls -i macht und den Dateinamen wegschreibt. Der Befehl brauchte insgeamt 27 Minuten und hat dabei 2 Minuten CPU Zeit gebraucht. der rest geht für die File- und Fork- operationen drauf- Das gibt einen Hinweis darauf wie "teuer" der Aufruf eines externen Programms ist (hier : ls). Er zeigt mir aber, dass das Ganze weit unterhalb der Möglichkeiten bleibt.

Denn:

Die VM auf der ich das mache hat zwei cores und der find Befehl braucht nur 10% CPU. Wenn Du also bei der bash bleiben *musst*, solltest Du Dir Gedanken machen, wie man das parallelisieren kann. Ich kann mir vorstellen, dass die hardlinks fachlich durchaus nicht kreuz und quer verteilt sind, sondern in "ihrem" Verzeichnisbaum bleiben.

Evtl. geht es doch mit der bash. bzw. vor allem mit dem find Befehl und den richtigen Parametern

Mal so aus der Hand geschüttelt...

Das teuerste in nem Rechner dürften doch Fopen sein, oder?

Das heißt man müsste die Anzahl an Befehlen die nach geladen werden in der Shell reduzieren, um Geschwindigkeit zu erzeugen. Zumindest um die erste Liste zu erzeugen:

cd <todir>
find . -type f -exec md5sum {} \; -exec ls -l {} \; > /tmp/lange-liste.txt

Das dürfte eine Liste an Dateien ergeben, die den Pfad, Dateigröße und eine md5sum enthalten. Wenn man will könnte man noch ein "-size +50M" dem find hinzufügen, um kleine Dateien zu ignoriren. Die Datei müsste anschließend noch überarbeitet werden, aber nu hat man ja zeit dafür?!? Hier mal mein Vorschlag:

Zunächst bereinigen wir die Datei von Hardlinks:

awk '{if ($2<2) print $5,$9}' /tmp/lange-liste.txt > /tmp/no-hardlinks.txt
sed -i '/^\s$/d' /tmp/nohardlinks.txt

ich hab mal den sed hinterher gejagt, da ich aus unerklärlichen Gründen doppelte Zeilenumbrüche hatte. Vermutlich druckt er eine Leerzeile für die nicht Treffer.

Nun holen wir uns mal die Zeilen mit den md5sumem aus der ersten liste, die zu der no-hardlinks passen:

for i in $(awk '{print $2}' /tmp/no-hardlinks.txt); do grep "*$i" /tmp/lange-liste.txt | awk '{print $1}'; done >/tmp/no-hardlinks2.txt

hier hat man nun in der richtigen Reihenfolge die md5sumen ohne Dateien. Nun fügt man beides zusammen:

paste /tmp/no-hardlinks2.txt /tmp/no-hardlinks.txt | sort -n

Wenn alles passt, sollten die Tabelle nun so formatiert sein:

md5sum Dateigröße Dateiname Zeilenumbruch

... und in jeder Zeile ein vollständiger Wert eingetragen sein. Durch den Sort sollten die checksumen die gleich sind auch untereinander stehen. Alternativ könnte man auch mit "sort -nk 2,2" nach der Dateigröße sortieren, wenn das einem lieber ist.-

Fazit:

Ob das alles Sinn macht oder auch nicht ist jedoch offen, da man die ganzen Randbedingungen gar nicht kennt. Wenn das tatsächlich so Zeitkritisch ist, frage ich mich warum? Wird der Dateibaum so schnell verändert? Wenn ja, macht dann die Suche nach Dubletten Sinn?

Anmerkung:

Auf Leerzeichen und Sonderzeichen in Dateinamen hab ich mal nicht geachtet. Hier dürfte wohl noch etwas Arbeit versteckt sein.

Hast sowas mal probiert?

Gerade wegen den Datenmengen würde ich über eine Lösung in C, oder so, nachdenken. Da lohnt es sich doch, mal 3 Tage zu coden.

Zitat von nalkem

Problem ist gerade einfach die immensen Mengen an zu vergleichenden Daten ...

Was heißt den Datenmenge genau?

ich mache meine Backups meiner Platte per RSYNC und lasse hinterher eine md5sum aller Dateien erzeugen, die gebackupt wurden. Das dauert, dürfte aber mit C auch nicht flotter werden, da ja jedes Bit durch md5sum muss und das auch bei einem C Programm.

Ich würde mich freuen, wenn hier mal wer tatsächlich Werte ermitteln würde...

Ich würde die Verzeichnisse in eine Datenbank importieren [*] und da dann weitersuchen und -verarbeiten. Bei diesem Volumen an Daten ist das deutlich effizienter, als auf den Verzeichnissen herumzuturnen. Alternativ kannst Du versuchen, die Verzeichnisse in Textdateien zu exportieren und dann mit den Unix-Standardwerkzeugen zu durchsuchen. Wenn du genug Hauptspeicher hast, könnte das schnell genug sein.

[*] Output von find . -ls mit einem einfachen Filter (awk, Perl) in CSV umwandeln und das dann in Postgres oder MySQL importieren.

Zitat von nalkem

Es geht hier um mehr als 200.000.000 Dateien bei über 200tb an Daten .....

ich bin auf die Statistik und Hochrechnungen gespannt
Ist echt nicht sarkastisch oder böse gemeint. Das ist tatsächlich spannend

200TB hab ich natürlich zuhause nicht. Da sind es nur 2TB.

Ein DB könnte hier tatsächlich was bringen, aber Wunder würde ich nicht erwarten. Die 200TB müssen dennoch durch den md5 (oder was du auch für ein Checksum wählst) durch. Hier wäre sicherlich interessant welches die CPU in Hardware gegossen hat. Mache Checksummen gehen dann deutlich flotter als andere.

Die Prüfsumme oder den Hash zu berechnen geht schneller, als die Daten von den Platten zu lesen. Wichtig ist, dass man das nur einmal macht und den Datensatz dann so ablegt, dass man ihn effizient analysieren kann.

Wenn das grosse Dateien sind, könnte man evtl. auch so tricksen, dass man erstmal nur nen Hash über das 1. Kilobyte, oder so, berechnet. Wenn sich das unterscheidet muss man ja gar nicht weiter vergleichen.

Zitat von daybyter

Wenn das grosse Dateien sind, könnte man evtl. auch so tricksen, dass man erstmal nur nen Hash über das 1. Kilobyte, oder so, berechnet. Wenn sich das unterscheidet muss man ja gar nicht weiter vergleichen.

Und wenn man zuvor die Dateigrößen vergleicht, muß man auch dieses erste Kilobyte nur noch selten anschauen.