algorithm - temporales - ¿Por qué es importante eliminar los archivos para eliminarlos más rápido?
eliminar archivos temporales windows 7 (5)
El reequilibrio para B-Trees es más barato que las implementaciones de B-Tree +, por eso la mayoría de implementaciones de sistemas de archivos e índices de base de datos las utilizan.
Hay muchos enfoques cuando se eliminan, dependiendo del enfoque, puede ser más eficiente en términos de tiempo y la necesidad de reequilibrar el árbol. También deberá considerar el tamaño del nodo, ya que la cantidad de claves que el nodo puede almacenar afectará la necesidad de reequilibrar el árbol. Un tamaño de nodo grande solo reordenará las claves dentro del nodo, pero un pequeño probablemente hará que el árbol se reequilibre muchas veces.
Un gran recurso para comprender esto es el famoso libro CLR (Thomas Cormen) "Introducción a los algoritmos".
Hace algún tiempo aprendí que rsync elimina archivos mucho más rápido que muchas otras herramientas .
Hace unos días me encontré con esta maravillosa respuesta en Serverfault que explica por qué rsync es tan bueno para eliminar archivos.
Cita de esa respuesta:
Revisé esto hoy, porque la mayoría de los sistemas de archivos almacenan sus estructuras de directorio en formato btree, el orden en el que borra los archivos también es importante. Uno debe evitar volver a equilibrar el btree cuando realiza el desvío. Como tal, he añadido una ordenación antes de que se produzcan eliminaciones.
¿Podría explicar cómo la eliminación de archivos en orden evita o reduce el número de rebalanceados de btree?
Espero que la respuesta muestre cómo eliminar a fin de aumentar la velocidad de eliminación, con detalles de lo que sucede a nivel de btree . Las personas que escribieron rsync y otros programas (ver enlaces en la pregunta) utilizaron este conocimiento para crear mejores programas. Creo que es importante que otros programadores tengan esta comprensión para poder escribir mejor en software.
En los sistemas de almacenamiento donde se alojan grandes directorios, la memoria caché del búfer estará bajo presión y los búferes se reciclarán. Por lo tanto, si tiene eliminaciones separadas por tiempo, entonces la cantidad de lecturas del disco para devolver el btree en el núcleo a la caché del búfer, entre eliminaciones, puede ser alta.
Si ordena los archivos que desea eliminar, efectivamente está retrasando los borrados y agrupándolos. Esto puede tener el efecto secundario de más eliminaciones por bloque de btree paginado. Si hay estadísticas para indicar cuáles son los aciertos de caché del búfer entre los dos experimentos, puede indicar si esta hipo es incorrecta o no.
Pero, si no hay estrés en el caché del búfer durante las eliminaciones, entonces los bloques btree podrían permanecer en el núcleo y entonces mi hipótesis no es válida.
No es importante, ni el tema del árbol b. Es solo una coincidencia .
En primer lugar, esto es muy dependiente de la implementación y muy ext3 específico. Por eso dije que no es importante (para uso general). De lo contrario, coloque la etiqueta ext3 o edite la línea de resumen.
En segundo lugar, ext3 no usa b-tree para el índice de entrada de directorio. Utiliza el Htree. El Htree es similar a b-tree pero diferente y no requiere balanceo . Busque "htree" en fs/ext3/dir.c
Debido al índice basado en htree, a) ext3 tiene una búsqueda más rápida en comparación con ext2, pero b) readdir() devuelve las entradas en orden de valor hash. El orden del valor hash es aleatorio en relación con el tiempo de creación del archivo o la disposición física de los datos. Como todos sabemos, el acceso aleatorio es mucho más lento que el acceso secuencial en un medio rotativo.
Un documento sobre ext3 publicado para OLS 2005 por Mingming Cao, et al. sugiere (énfasis mío):
para ordenar las entradas de directorio devueltas por readdir () por número de inodo .
Ahora, en rsync. Rsync ordena los archivos por nombre de archivo. Consulte flist.c::fsort() , flist.c::file_compare() y flist.c::f_name_cmp() .
No probé la siguiente hipótesis porque no tengo los conjuntos de datos de los cuales @MIfe obtuvo 43 segundos . pero supongo que ordenado por nombre fue mucho más cercano al orden óptimo en comparación con el orden aleatorio devuelto por readdir (). Por eso viste un resultado mucho más rápido con rsync en ext3. ¿Qué sucede si genera 1000000 archivos con nombres de archivos aleatorios y luego los elimina con rsync? ¿Ves el mismo resultado?
No estoy convencido de que la cantidad de reequilibrio del árbol B cambie significativamente si se eliminan los archivos en orden. Sin embargo, creo que la cantidad de búsquedas diferentes de almacenamiento externo será significativamente menor si haces esto. En cualquier momento, los únicos nodos en el árbol B que necesitan ser visitados serán el límite más a la derecha del árbol, mientras que, con un orden aleatorio, cada bloque de hoja en el árbol B se visita con igual probabilidad para cada archivo.
Supongamos que la respuesta que publicaste es correcta y que el sistema de archivos dado realmente almacena cosas en un árbol equilibrado. Equilibrar un árbol es una operación muy costosa. Mantener un árbol "parcialmente" equilibrado es bastante simple, ya que cuando permite que un árbol se desequilibre ligeramente, solo se preocupa por mover las cosas alrededor del punto de inserción / eliminación. Sin embargo, cuando se habla de árboles completamente equilibrados, cuando elimina un nodo dado, puede encontrar que de repente, los hijos de este nodo podrían pertenecer al lado opuesto completo del árbol, o un nodo secundario en el lado opuesto se ha convertido en la raíz. nodo, y todos sus hijos necesitan ser girados hacia arriba en el árbol. Esto requiere que realice una larga serie de rotaciones, o que coloque todos los elementos en una matriz y vuelva a crear el árbol.
5
3 7
2 4 6 8
Ahora quita el 7, fácil ¿verdad?
5
3 8
2 4 6
Ahora quita el 6, todavía es fácil, sí ...?
5
3 8
2 4
Ahora quita el 8, uh oh
5
3
2 4
Conseguir que este árbol sea la forma equilibrada adecuada como:
4
3 5
2
Es bastante caro, comparado al menos con las otras eliminaciones que hemos hecho, y empeora exponencialmente a medida que aumenta la profundidad de nuestro árbol. Podríamos hacer que esto vaya mucho (exponencialmente) más rápido eliminando el 2 y el 4, antes de eliminar el 8. En particular si nuestro árbol tenía más de 3 niveles de profundidad.
Sin clasificación, la eliminación es en promedio una O (K * log_I (N) ^ 2). N representa el número de elementos en total y K el número que se eliminará, I el número de hijos que se permite en un nodo determinado, log_I (N) siendo la profundidad, y para cada nivel de profundidad aumentamos el número de operaciones de forma cuadrada.
La eliminación con un poco de ayuda para pedidos es en promedio O (K * log_I (N)), aunque a veces el pedido no puede ayudarlo y está atascado eliminando algo que requerirá un nuevo equilibrio. Aún así, minimizar esto es óptimo.
EDITAR:
Otro posible esquema de ordenación de árboles:
8
6 7
1 2 3 4
Lograr una eliminación óptima en esta circunstancia sería más fácil, ya que podemos aprovechar nuestro conocimiento de cómo se ordenan las cosas. Bajo cualquiera de las dos situaciones es posible, y de hecho ambas son idénticas, bajo esta lógica, la lógica es un poco más fácil de entender, porque el ordenamiento es más fácil para el escenario dado. En cualquier caso, en orden se define como "quitar primero la hoja más alejada", en este caso resulta que las hojas más alejadas son también las más pequeñas, un hecho que podríamos aprovechar para hacerlo incluso un poco más pequeño. más óptimo, pero este hecho no es necesariamente cierto para el ejemplo de sistema de archivos presentado (aunque puede ser).