Warum ist das Löschen von Dateien mit Namen schmerzhaft langsam und auch außergewöhnlich schnell?

Fauxpas: Die unten erwähnte "schnelle" Methode ist nicht 60-mal schneller als die langsame. Es ist 30 mal schneller. Ich werde den Fehler auf die Stunde zurückführen (3 Uhr morgens ist nicht meine beste Tageszeit für klares Denken :) ..

Update: Ich habe eine Zusammenfassung der Testzeiten hinzugefügt (siehe unten).
Es scheint zwei Probleme mit dem Geschwindigkeitsfaktor zu geben:

• Die Wahl des verwendeten Befehls (Zeitvergleiche siehe unten)
• Die Art der großen Anzahl von Dateien in einem Verzeichnis ... Es scheint, dass "groß ist schlecht". Die Dinge werden mit zunehmenden Zahlen unverhältnismäßig langsamer.

Alle Tests wurden mit 1 Million Dateien durchgeführt.
(Die tatsächlichen, Benutzer- und Systemzeiten sind in den Testskripten angegeben.)
Die Testskripte finden Sie unter paste.ubuntu.com

#
# 1 million files           
# ===============
#
#  |time   |new dir   |Files added in  ASCENDING order  
#  +----   +-------   +------------------------------------------------- 
#   real    01m 33s    Add files only (ASCENDING order) ...just for ref.
#   real    02m 04s    Add files, and make 'rm' source (ASCENDING order) 
#                      Add files, and make 'rm' source (DESCENDING order) 
#   real    00m 01s    Count of filenames
#   real    00m 01s    List of filenames, one per line
#   ----    -------    ------
#   real    01m 34s    'rm -rf dir'
#   real    01m 33s    'rm filename' via rm1000filesPerCall   (1000 files per 'rm' call)
#   real    01m 40s    'rm filename' via  ASCENDING algorithm (1000 files per 'rm' call)
#   real    01m 46s    'rm filename' via DESCENDING algorithm (1000 files per 'rm' call)
#   real    21m 14s    'rm -r dir'
#   real    21m 27s    'find  dir -name "hello*" -print0 | xargs -0 -n 1000 rm'
#   real    21m 56s    'find  dir -name "hello*" -delete'
#   real    23m 09s    'find  dir -name "hello*" -print0 | xargs -0 -P 0 rm'
#   real    39m 44s    'rm filename' (one file per rm call) ASCENDING
#   real    47m 26s    'rm filename' (one file per rm call) UNSORTED
#                                                       

Ich habe kürzlich 10 Millionen leere Testdateien erstellt und gelöscht . Beim Löschen von Dateien auf Namensbasis (dh rm filename) habe ich auf die harte Tour herausgefunden, dass es einen großen Zeitunterschied zwischen zwei verschiedenen Methoden gibt ...

Beide Methoden verwenden genau den gleichen rm filenameBefehl.

Update: Wie sich herausstellte, waren die Befehle nicht genau gleich ... Einer von ihnen sendete 1000 Dateinamen gleichzeitig an 'rm' ... Es war ein Problem mit der Erweiterung der Shell-Klammer, bei dem ich dachte, jeder Dateiname würde geschrieben in die Feeder-Datei in einer eigenen Zeile, aber tatsächlich waren es 1000 pro Zeile

Die Dateinamen werden über eine 'Feeder-Datei' in einer while readSchleife bereitgestellt .
Die Feeder-Datei ist die Ausgabe von. ls -1 -f
Die Methoden sind in allen Aspekten identisch, mit einer Ausnahme:

• Die langsame Methode verwendet die unsortierte Feeder-Datei direkt vonls -1 -f
• Die schnelle Methode verwendet eine sortierte Version derselben unsortierten Datei

Ich bin mir nicht sicher, ob die Sortierung hier das Problem ist oder ob die sortierte Feeder-Datei zufällig mit der Reihenfolge übereinstimmt, in der die Dateien erstellt wurden (ich habe einen einfachen Algorithmus für aufsteigende Ganzzahlen verwendet).

Bei 1 Million Dateien ist die schnelle rm filename Methode 60- mal schneller als die langsame Methode. Auch hier weiß ich nicht, ob es sich um ein "Sortier" -Problem oder ein Problem mit der Hash-Tabelle hinter den Kulissen handelt ... Ich vermute Es ist kein einfaches Sortierproblem, denn warum sollte ls -1 -fich absichtlich eine unsortierte Auflistung einer frisch hinzugefügten "sortierten" Folge von Dateinamen erhalten ...

Ich frage mich nur, was hier los ist, also brauche ich keine Tage (ja Tage), um die nächsten 10 Millionen Dateien zu löschen :) .... Ich sage "Tage", weil ich so viele Alternativen ausprobiert habe, und die Die damit verbundenen Zeiten steigen überproportional zur Anzahl der beteiligten Dateien. Ich habe also nur 1 Million im Detail getestet

Übrigens: Das Löschen der Dateien über die "sortierte Liste" von Namen ist tatsächlich schneller als rm -rfum den Faktor 2.
und: rm -rwar 30-mal langsamer als die Methode "sortierte Liste"

... aber ist das Problem hier "sortiert"? oder hängt es eher mit einer von ext4 verwendeten Hashing-Methode (oder was auch immer) zusammen?

Die Sache, die mich ziemlich verwirrt, ist, dass jeder Anruf zu rm filenamenichts mit dem vorherigen zu tun hat . (Nun, zumindest ist es aus der 'Bash'-Perspektive so)

Ich verwende Ubuntu / bash / 'ext4' / SATA II-Laufwerk.

Es wird erwartet, dass rm -r als rekursiv langsam ist. In der Verzeichnisstruktur muss eine erste Tiefenüberquerung durchgeführt werden.

Wie haben Sie 10 Millionen Dateien erstellt? Hast du ein Skript verwendet, das sich in einer bestimmten Reihenfolge wiederholt? 1.txt, 2.txt, 3.txt ... Wenn ja, können auch diese Dateien in zusammenhängenden Blöcken in hdd. in derselben Reihenfolge zugewiesen werden. Das Löschen in derselben Reihenfolge ist also schneller.

"ls -f" aktiviert -aU, das in Verzeichnisreihenfolge auflistet, die wiederum rekursiv ist.

Sie sollten die Dateistruktur optimieren. Also statt

for i in $(seq 1 1000); do touch file.$i; done

Mach etwas schlaueres wie (Bash angenommen):

function bucklocate() 
{ 
    hash=$(echo -n "$1"|md5sum|cut -f1); 
    echo -n "${hash:1:1}/${hash:7:1}/${hash:9:2}/$1"; 
}

hexdig="{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}"
eval mkdir -p $hexdig/$hexdig/$hexdig$hexdig


for i in $(seq 1 1000); do touch $(bucklocate file.$i); done

Dieses Beispiel ist aufgrund der Verwendung von md5sum [1] ziemlich langsam. Verwenden Sie Folgendes, um eine schnellere Antwort zu erhalten. Solange Sie keine bestimmten Dateinamen benötigen, sind Duplikate nicht von Belang und es besteht keine Notwendigkeit für a wiederholbarer Hash eines bestimmten Namens :)

mkdir -pv {0,1,2,3,4,5,6}/{0,1,2,3,4,5,6,7,8,9,10,12}
for  a in $(seq 1 100); do i=$RANDOM; echo touch "$(($i%7))/$(($i%13))/file.$i"; done

Natürlich ist dies alles schlampig das Ausleihen von Konzepten aus Hashtabellen