Por que a exclusão de arquivos pelo nome é dolorosamente lenta e também excepcionalmente rápida?

Question

Faux pas: O método "rápido" que menciono abaixo, não é 60 vezes mais rápido que o lento. É 30 vezes mais rápido. Eu culpo o erro na hora (3AM não é a minha melhor hora do dia para um pensamento claro :) ..

Atualização: adicionei um resumo dos tempos de teste (abaixo). Parece haver dois problemas envolvidos com o fator de velocidade:

• A escolha do comando usado (Comparações de tempo mostradas abaixo)
• A natureza de um grande número de arquivos em um diretório ... Parece que "big is bad". As coisas ficam desproporcionalmente mais lentas à medida que os números aumentam.

Todos os testes foram feitos com 1 milhão de arquivos.
(tempos reais, de usuário e de sistema estão nos scripts de teste)
Os scripts de teste podem ser encontrados em 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
#                                                       

Eu criei e excluí recentemente 10 milhões de arquivos de teste vazios. Excluindo arquivos em um nome por base de nome (ou seja, rm filename ), descobri da maneira mais difícil que existe uma diferença de tempo enorme entre dois métodos diferentes ...

Ambos os métodos usam exatamente o mesmo comando rm filename .

Update: as it turns out, the commands were not exactly the same... One of them was sending 1000 filenames at a time to 'rm'... It was a shell brace-expansion issue where I thought each filename was being written to the feeder file on a line of its own, but actually it was 1000 per line

Os nomes dos arquivos são fornecidos por meio de um 'arquivo alimentador' em um loop while read ..
O arquivo do alimentador é a saída de ls -1 -f
Os métodos são idênticos em todos os aspectos, exceto por uma coisa:

• o método lento usa o arquivo do alimentador não classificado diretamente de ls -1 -f
• o método rápido usa uma versão classificada desse mesmo arquivo não classificado

Não tenho certeza se a classificação é o problema aqui, ou talvez o arquivo do alimentador classificado corresponda à sequência na qual os arquivos foram criados (usei um algoritmo simples de crescente ascendente)

Para 1 milhão de arquivos, o método rápido rm filename é 60 vezes mais rápido do que o método lento ... novamente, eu não não sei se isso é um problema de "classificação", ou um problema de tabela de hash por trás dos bastidores ... Eu suspeito que não é um problema de classificação simples, porque porque ls -1 -f intencionalmente me daria um unsort listagem de uma sequência "classificada" recém-adicionada de nomes de arquivos ...

Eu só estou querendo saber o que está acontecendo aqui, por isso não me leva dias (sim dias) para apagar os próximos 10 milhões de arquivos :) .... eu digo "dias" porque eu tentei tantas alternativas , e os tempos envolvidos aumentam desproporcionalmente ao número de arquivos envolvidos. Então, eu testei apenas 1 milhão em detalhes

BTW: Excluir os arquivos por meio da "lista classificada" de nomes é realmente mais rápido que rm -rf por um fator de 2.
e: rm -r foi 30 vezes mais lento que o método "lista de classificação"

... mas a questão está "resolvida" aqui? ou é mais relacionado a um método de armazenamento hash (ou qualquer outro) usado pelo ext4?

A coisa que mais me intriga é que cada chamada para rm filename não tem relação com a anterior ... (bem, pelo menos é assim na perspectiva do 'bash')

Estou usando o drive Ubuntu / bash / 'ext4' / SATA II.

    

Answer 1

Espera-se que o rm -r seja lento como recursivo. Uma primeira passagem de profundidade deve ser feita na estrutura de diretório.

Agora, como você criou 10 milhões de arquivos? você usou algum script que faz um loop em alguma ordem? 1.txt, 2.txt, 3.txt ... se sim, então esses arquivos também podem ser alocados na mesma ordem em blocos contíguos no hdd.so excluir na mesma ordem será mais rápido.

"ls -f" ativará -aU, que lista em ordem de diretórios que é novamente recursiva.

    

Answer 2

Você deve otimizar a estrutura de arquivos. Então, ao invés de

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

faça algo mais inteligente como (bash supostamente):

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

Agora este exemplo é bastante lento por causa do uso de md5sum [1], use algo como o seguinte para uma resposta muito mais rápida, contanto que você não precise de nenhum nome de arquivo específico, duplicatas não são preocupantes e não há necessidade de um hash repetível de um certo nome:)

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

É claro que tudo isso é um conceito de empréstimo indesejado de hashtables