¿Por qué eliminar archivos por nombre es dolorosamente lento y también excepcionalmente rápido?

11

Paso en falso: el método "rápido" que menciono a continuación, no es 60 veces más rápido que el lento. Es 30 veces más rápido. Culparé del error a la hora (3AM no es mi mejor momento del día para pensar claramente :) ..

Actualización: he agregado un resumen de los tiempos de prueba (a continuación).
Parece que hay dos problemas relacionados con el factor de velocidad:

  • La elección del comando utilizado (las comparaciones de tiempo se muestran a continuación)
  • La naturaleza de un gran número de archivos en un directorio ... Parece que "grande es malo". Las cosas se vuelven desproporcionadamente más lentas a medida que aumentan los números.

Todas las pruebas se han realizado con 1 millón de archivos.
(los tiempos reales, de usuario y sys están en los scripts de prueba)
Los scripts de prueba se pueden encontrar en 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
#                                                       

Recientemente creé y eliminé 10 millones de archivos de prueba vacíos. Eliminando archivos nombre por nombre (es decir rm filename), descubrí por las malas que hay una gran diferencia horaria entre 2 métodos diferentes ...

Ambos métodos usan exactamente el mismo rm filenamecomando.

Actualización: resulta que los comandos no eran exactamente los mismos ... Uno de ellos estaba enviando 1000 nombres de archivo a la vez a 'rm' ... Era un problema de expansión de llaves de concha donde pensé que cada nombre de archivo se estaba escribiendo al archivo del alimentador en una línea propia, pero en realidad era 1000 por línea

Los nombres de archivo se proporcionan a través de un 'archivo de alimentación' en un while readbucle.
El archivo de alimentación es la salida de ls -1 -f
Los métodos son idénticos en todos los aspectos, excepto por una cosa:

  • el método lento usa el archivo del alimentador sin clasificar directamente dels -1 -f
  • el método rápido usa una versión ordenada del mismo archivo sin clasificar

No estoy seguro de si la clasificación es este problema aquí, o tal vez es que el archivo del alimentador ordenado coincide con la secuencia en la que se crearon los archivos (utilicé un algoritmo entero ascendente simple)

Para 1 millón de archivos, el método rápido rm filename es 60 veces más rápido que el método lento ... de nuevo, no sé si este es un problema de "clasificación" o un problema de tabla hash detrás de escena ... sospecho no es un simple problema de clasificación, porque ¿por qué ls -1 -fintencionalmente me daría una lista sin ordenar de una secuencia de nombres de archivos "ordenados" recién agregados ...

Me pregunto qué está pasando aquí, así que no me lleva días (sí días) eliminar los próximos 10 millones de archivos :) .... Digo "días" porque probé muchas alternativas, y el los tiempos involucrados aumentan desproporcionadamente en relación con el número de archivos involucrados ... así que solo he probado 1 millón en detalle

Por cierto: eliminar los archivos a través de la "lista ordenada" de nombres es en realidad más rápido que rm -rfpor un factor de 2.
y: rm -rfue 30 veces más lento que el método de "lista ordenada"

... pero ¿está "resuelto" el problema aquí? ¿O está más relacionado con un método de almacenamiento hash (o lo que sea) utilizado por ext4?

Lo que me desconcierta bastante es que cada llamada a rm filenameno está relacionada con la anterior ... (bueno, al menos es así desde la perspectiva de 'bash')

Estoy usando Ubuntu / bash / 'ext4' / SATA II drive.

Peter.O
fuente
1
¡Lo estás haciendo mal! (tm) ¿Has oído hablar alguna vez find -delete?
alex
Sus 2 pruebas comienzan en condiciones desiguales (no pretendo que esto sea importante): uno lee los nombres de archivo de un archivo y el otro lee los nombres de archivo de un archivo que se ha creado (ordenado) inmediatamente antes de la prueba. Puede ser que el archivo que se está almacenando en caché en el segundo caso reproduce algo (o tal vez no, quién sabe). Para que las pruebas estén en condiciones más iguales, tal vez debería hacer un catarchivo simple a nuevo antes de la primera prueba, en lugar de sortantes de la segunda prueba.
imz - Ivan Zakharyaschev
Y le recomiendo que presente sus observaciones y su pregunta de una manera más clara. Por favor, una cosa a la vez: compare solo 2 casos en una pregunta, traiga los dos casos importantes al primer plano, el resto es solo información de fondo; por favor deja esto claro No mezcle varias observaciones en una publicación, por favor.
imz - Ivan Zakharyaschev
Presentar el sistema y el tiempo de espacio de usuario de su parte también puede ser importante para resolver el rompecabezas, así que inclúyalos en su pregunta. ¿Cuál de ellos hace la gran diferencia en tus pruebas?
imz - Ivan Zakharyaschev
1
La optimización prematura es la fuente de todos los males. :) ¿Cuándo eliminarás 10 millones de archivos? 100 000 por segundo me parece lo suficientemente rápido (para arruinar su sistema).
usuario desconocido

Respuestas:

2

Se espera que rm -r sea lento ya que es recursivo. Se debe realizar un primer recorrido profundo en la estructura del directorio.

Ahora, ¿cómo creaste 10 millones de archivos? ¿Usaste algún script que repite en algún orden? 1.txt, 2.txt, 3.txt ... en caso afirmativo, entonces esos archivos también pueden asignarse en el mismo orden en bloques contigo en hdd, por lo que la eliminación en el mismo orden será más rápida.

"ls -f" habilitará -aU que enumera en orden de directorio que nuevamente es recursivo.

rajaganesh87
fuente
1
McAlot: No puedo ver cómo 'recursivo' importaría en este caso , ya que no hay subdirectorios involucrados ... Sí, utilicé "1.txt, 2.txt, 3.txt '. Quizás haya varios cosas interactúan entre sí: por ejemplo, ¿Por qué tarda solamente 1min 30s para crear 1 millón de archivos, pero se necesita 10s 7m para crear 2 millones y después de la eliminación de ellos, recreando los 1 millón. tanto lleva más tiempo (30 9m) su extraña; todo está funcionando lentamente, de repente. Esto también ha sucedido antes. Creo que (?) eliminar el directorio lo arregló. ¿Hay algún demonio de archivo involucrado (nautilus; localizar) tal vez? Continuará ...
Peter.O
En general, los sistemas de archivos no están optimizados para manejar grandes cantidades de archivos en el mismo directorio. No estoy familiarizado con ext4 específicamente, pero para otros formatos, las entradas del directorio se marcaron como no utilizadas cuando se eliminaron los archivos. Eso significa que todavía se deben omitir al realizar operaciones en el directorio. Eso explicaría el comportamiento que estás viendo.
KeithB
1
Eliminé el directorio 'ahora más lento' y usé un nombre diferente para un nuevo directorio. El tiempo para crear 1 millón de archivos ahora se reduce a 1 m 33 s (frente a 9 m 30 s cuando el directorio "contiene" 2 millones de archivos eliminados, el primer millón tiene el mismo nombre que el 1 millón recién agregado) ... interesante, y coincide con su comentario "... simplemente marcado como no utilizado" ... llegando allí; está empezando a tener sentido :)
Peter.O
@ fred.bear Mi mal, realmente no conocía la jerarquía real y mi respuesta fue adivinar. también su prueba realmente enfatiza los metadatos pero no los archivos reales, ya que son archivos vacíos. La mejor manera de evaluar este tipo de problema es tomar archivos de / var o caché del servidor web. de todos modos, su prueba también suena interesante, ¿puede intentar eliminar con dos métodos enumerados en diferentes directorios ... digamos /sample1/1.txt,2.txt ... y /sample2/1.txt,2.txt ..
rajaganesh87
@ Mr.Confused.A.Lot ... Gracias por su ayuda. Su explicación me ayudó a comprender más sobre el sistema de archivos y algunos de sus gestos ... Ahora tengo una idea razonable de lo que estaba causando los diferentes problemas de velocidad ... algunos eran solo la elección de comandos bash, y otros eran simplemente problemas del sistema de archivos ( Me queda un nuevo lema: "lo grande es malo" para los directorios ... (al menos para algunas acciones) ...
Peter.O
2

Debe optimizar la estructura de archivos. Entonces en lugar de

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

hacer algo más inteligente (bash asumido):

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

Ahora, este ejemplo es bastante lento debido al uso de md5sum [1], use algo como lo siguiente para obtener una respuesta mucho más rápida, siempre que no necesite ningún nombre de archivo en particular, los duplicados no son una preocupación y no hay necesidad de un hash repetible de cierto nombre :)

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

Por supuesto, todo esto es prestar conceptos descuidadamente de tablas hash

sehe
fuente
Creo que estás diciendo "usar directorios más pequeños" ... Esa es una idea interesante; un DBMS casero que hace un árbol a partir de un grupo de archivos 'sin árbol'. Algunos podrían llamarlo planificación anticipada :) ... Si funciona (y probablemente lo haga), ¡es una buena idea ! :) ... Estoy empezando a tener la idea de que "grande es malo" cuando se trata de la cantidad de archivos en un directorio (al menos para ext4) ... Usted ha presentado una solución preventiva (+1) y yo " lentamente me hago una idea de por qué algunos métodos de eliminación son más rápidos que otros en cualquier directorio dado; pequeño o grande ... Gracias
Peter.O
Sí, lo siento por no ser más explícito sobre la idea de mantener pequeños
directorios