Dlaczego usuwanie plików z nazwy jest boleśnie powolne, a jednocześnie wyjątkowo szybkie?

Faux pas: Wspomniana poniżej metoda „szybka” nie jest 60 razy szybsza niż metoda powolna. Jest 30 razy szybszy. Będę winić błąd za godzinę (3 rano nie jest najlepszą porą dnia na jasne myślenie :) ..

Aktualizacja: dodałem podsumowanie czasów testu (poniżej).
Wydaje się, że istnieją dwa problemy związane ze współczynnikiem prędkości:

• Wybór użytej komendy (porównania czasowe pokazano poniżej)
• Charakter dużej liczby plików w katalogu ... Wygląda na to, że „duży jest zły”. Sprawy stają się coraz wolniej rosnące wraz ze wzrostem liczby.

Wszystkie testy zostały wykonane z 1 milionem plików.
(czasy rzeczywiste, użytkownika i sys podano w skryptach testowych)
Skrypty testowe można znaleźć na stronie 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
#                                                       

Niedawno utworzyłem i usunąłem 10 milionów pustych plików testowych. Usuwając pliki według nazwy (tj. rm filename), Dowiedziałem się na własnej skórze, że istnieje ogromna różnica czasu między 2 różnymi metodami ...

Obie metody używają dokładnie tego samego rm filenamepolecenia.

Aktualizacja: jak się okazuje, polecenia nie były dokładnie takie same ... Jedno z nich wysyłało jednocześnie 1000 nazw plików do 'rm' ... To był problem z rozszerzaniem nawiasów klamrowych, w którym myślałem, że każda nazwa pliku jest zapisywana do pliku feeder w osobnej linii, ale tak naprawdę było to 1000 na linię

Nazwy plików są dostarczane przez „plik feeder” do while readpętli.
Plik feeder jest wyjściem ls -1 -f
Metody są identyczne we wszystkich aspektach, z wyjątkiem jednej rzeczy:

• powoli metoda wykorzystuje niesegregowanych podajnika bezpośrednio z plikuls -1 -f
• szybka metoda wykorzystuje posortowaną wersji tego samego pliku niesegregowanych

Nie jestem pewien, czy kwestia sortowania jest tutaj problemem, czy może jest tak, że posortowany plik podajnika po prostu pasuje do sekwencji, w której pliki zostały utworzone (użyłem prostego algorytmu rosnącej liczby całkowitej)

W przypadku 1 miliona plików metoda szybka rm filename jest 60 razy szybsza niż metoda powolna ... znowu nie wiem, czy to jest problem z sortowaniem, czy problem z tabelą skrótów za kulisami ... Podejrzewam nie jest to prosty problem z sortowaniem, ponieważ dlaczego miałbym ls -1 -fcelowo dać mi nieposortowaną listę świeżo dodanej „posortowanej” sekwencji nazw plików ...

Zastanawiam się tylko, co się tutaj dzieje, więc usunięcie następnych 10 milionów plików nie zajmuje mi dni (tak dni) :) .... Mówię „dni”, ponieważ próbowałem tylu alternatyw, a czasy zaangażowany wzrost disproportionatly do pliku numberof zaangażowany .. więc mam tylko przetestowane 1 mln w szczegółach

BTW: Usuwanie plików za pomocą „posortowanej listy” nazw jest faktycznie szybsze niż rm -rf2
- rm -rkrotnie i: było 30 razy wolniejsze niż metoda „posortowanej listy”

... ale czy problem jest tutaj „rozwiązany”? czy jest to bardziej związane z hashującą (lub jakąkolwiek inną) metodą przechowywania używaną przez ext4?

Rzeczą, która mnie dość zastanawia, jest to, że każde połączenie do rm filenamenie ma związku z poprzednim. (Przynajmniej tak jest z perspektywy „bash”)

Używam dysku Ubuntu / bash / 'ext4' / SATA II.

Oczekuje się, że rm -r będzie powolny, ponieważ jest rekurencyjny. Najpierw należy wykonać głębokość przejścia w strukturze katalogów.

Jak utworzyłeś 10 milionów plików? czy użyłeś jakiegoś skryptu, który zapętla się w jakiejś kolejności? 1.txt, 2.txt, 3.txt ... jeśli tak, te pliki mogą być również przydzielone w tej samej kolejności w ciągłych blokach w hdd. Więc usuwanie w tym samym porządku będzie szybsze.

„ls -f” włączy -aU, która wyświetla listę w kolejności katalogów, która również jest rekurencyjna.

Powinieneś zoptymalizować strukturę plików. Więc zamiast

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

zrób coś mądrzejszego (zakłada bash):

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

Teraz ten przykład jest raczej powolny z powodu użycia md5sum [1], użyj czegoś takiego jak poniżej, aby uzyskać znacznie szybszą odpowiedź, o ile nie potrzebujesz żadnych konkretnych nazw plików, duplikaty nie mają znaczenia i nie ma potrzeby powtarzalny skrót o określonej nazwie :)

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

Oczywiście to wszystko niechlujnie zapożycza koncepcje z tablic skrótów