¿Por qué la carpeta Git .git / objects / está subdividida en muchas carpetas de prefijo SHA?

21

Git almacena internamente objetos (blobs, árboles) en la .git/objects/carpeta. Cada objeto puede ser referenciado por un hash SHA1 que se calcula a partir del contenido del objeto.

Sin embargo, los objetos no se almacenan dentro de la .git/objects/carpeta directamente. En cambio, cada objeto se almacena dentro de una carpeta que comienza con el prefijo de su hash SHA1. Por lo tanto, un objeto con el hash b7e23ec29af22b0b4e41da31e868d57226121c84se almacenaría en.git/objects/b7/e23ec29af22b0b4e41da31e868d57226121c84

¿Por qué Git subdivide su almacenamiento de objetos de esta manera?

Los recursos que pude encontrar, como la página de las partes internas de Git en git-scm, solo explicaban cómo , no por qué .

Qqwy
fuente

Respuestas:

33

Es posible colocar todos los archivos en un directorio, aunque a veces puede ser un poco grande. Muchos sistemas de archivos tienen un límite . ¿Desea colocar un repositorio git en una unidad formateada FAT32 en una memoria USB? Solo puede almacenar 65.535 archivos en un solo directorio. Esto significa que es necesario subdividir la estructura del directorio para que sea menos probable llenar un solo directorio.

Esto incluso se convertiría en un problema con otros sistemas de archivos y repositorios git más grandes. Un repositorio de git relativamente pequeño que tengo colgado (aproximadamente 360MiB) y tiene 181,546 objetos para 11k archivos. Tire del repositorio de Linux y obtendrá 4,374,054 objetos. Si tuviera que poner todo esto en un directorio, sería imposible verificarlo y bloquearía (por algún significado de "bloqueo") el sistema de archivos.

¿Asi que? Lo divide por byte. Se realizan enfoques similares con aplicaciones como FireFox:

~/Li/Ca/Fi/Pr/7a/Cache $ ls
0/           4/           8/           C/           _CACHE_001_
1/           5/           9/           D/           _CACHE_002_
2/           6/           A/           E/           _CACHE_003_
3/           7/           B/           F/           _CACHE_MAP_

Más allá de esto, también se trata de una cuestión de rendimiento. Considere el rendimiento de NTFS con numerosos nombres largos de archivo :

Windows NT tarda mucho tiempo en realizar operaciones de directorio en unidades con formato del sistema de archivos de Windows NT (NTFS) que contienen una gran cantidad de archivos con nombres largos (nombres que no se ajustan a la convención 8.3) en un solo directorio.

Cuando NTFS enumera archivos en un directorio, tiene que buscar los nombres 8.3 asociados con los nombres largos de archivo. Debido a que un directorio NTFS se mantiene en un estado ordenado, los nombres de archivo largos correspondientes y los nombres 8.3 generalmente no están uno al lado del otro en la lista del directorio. Entonces, NTFS usa una búsqueda lineal del directorio para cada archivo presente. Como resultado, la cantidad de tiempo requerida para realizar un listado de directorio aumenta con el cuadrado del número de archivos en el directorio. Para pequeñas cantidades de archivos (menos de unos pocos cientos), el retraso de tiempo es insignificante. Pero a medida que el número de archivos en un directorio aumenta a varios miles, el tiempo requerido para realizar un listado puede aumentar a minutos, horas o incluso días. El problema se agrava si los nombres largos de archivo son muy similares y solo difieren en los últimos caracteres.

Con los archivos que llevan el nombre de las sumas de verificación SHA1, esto podría ser una receta para el desastre y el rendimiento abismal.

Si bien lo anterior es de una nota técnica de Windows NT 3.5 (y NTFS 1.2, comúnmente utilizado desde 1995 hasta principios de la década de 2000), esto también se puede ver en cosas como EXT3 con implementaciones del sistema de archivos que son listas enlazadas que requieren búsqueda O (n) . E incluso con ese cambio de árbol B:

Si bien el algoritmo HTree mejoró significativamente los tiempos de búsqueda, podría causar algunas regresiones de rendimiento para las cargas de trabajo que usaban readdir () para realizar alguna operación de todos los archivos en un directorio grande.
...
Una posible solución para mitigar este problema de rendimiento, que ha sido sugerido por Daniel Phillips y Andreas Dilger, pero que aún no se ha implementado, implica que el núcleo elija inodos libres cuyos números de inodo cumplan con una propiedad que agrupa los inodos por su hash de nombre de archivo. Daniel y Andreas sugieren asignar el inodo de un rango de inodes según el tamaño del directorio, y luego elegir un inodo libre de ese rango según el hash del nombre de archivo. En teoría, esto debería reducir la cantidad de sacudidas que resulta al acceder a los inodos a los que se hace referencia en el directorio en orden readdir. Sin embargo, no está claro que esta estrategia dé como resultado una aceleración; de hecho, podría aumentar el número total de bloques de inodo a los que podría tener que hacer referencia, y así empeorar el rendimiento de las cargas de trabajo readdir () + stat (). Claramente,

Por cierto, esta parte sobre cómo mejorar el rendimiento fue a partir de 2005, el mismo año en que se lanzó git.

Como se ve con Firefox y muchas otras aplicaciones que tienen muchos archivos hash en caché, el diseño de dividir el caché por byte. Tiene un costo de rendimiento insignificante, y cuando se usa multiplataforma con sistemas que pueden ser un poco anticuados, bien podría ser la diferencia entre que el programa funcione o no.

Comunidad
fuente
1
Notó que el artículo de rendimiento de NTFS que cita se aplica a NT 3.5, lanzado en 1994, ¿verdad?
Avner Shahar-Kashtan
1
@ AvnerShahar-Kashtan sí. Git se lanzó en 2005. Sé lo que estaba usando los sistemas de archivos basados ​​en NTFS v1.2 en un entorno corporativo a principios de la década de 2000 (no obstante, en una empresa de tecnología). Ciertamente, existe una superposición entre los requisitos de git y los sistemas de archivos en los sistemas comúnmente disponibles en ese momento.
Quizás sería más claro si usted declara que esto podría ser un artefacto histórico del estado de la tecnología cuando se introdujo git, porque tal como está, para una pregunta formulada en 2015, citando una limitación técnica de veinte años (retomando la respuesta ) parece confuso.
Avner Shahar-Kashtan
Para ser justos, gitel sistema de "paquete" mitiga muchos de estos problemas. Teóricamente, gitpodría estar usando un solo directorio y simplemente volver a empaquetar cuando el número de archivos en ese directorio excedió un cierto límite (posiblemente dependiente de FS).
nneonneo
55
@ AvnerShahar-Kashtan si lee el artículo de SO vinculado, puede ver que tratar con directorios que contienen una gran cantidad de archivos es problemático en múltiples sistemas de archivos y sistemas operativos, no solo NT 3.5. Dejando a un lado los límites de los archivos, incluso solo enumerar los archivos puede generar una gran cantidad de sobrecarga.
8

Hay dos razones por las cuales esto es deseable.

Los directorios no pueden ser arbitrariamente grandes. Por ejemplo, algunos sistemas de archivos (¡razonablemente modernos!) Están limitados a 32000 entradas en un solo directorio. El número de confirmaciones en el kernel de Linux está en ese orden de magnitud. Subdividir las confirmaciones por sus dos primeros dígitos hexadecimales limita el tamaño de nivel superior a 256 entradas. Los subdirectorios serán mucho más pequeños para los repositorios típicos de git.

Los directorios se escanean linealmente. En algunos sistemas de archivos (por ejemplo, la familia Ext *), un directorio es una lista vinculada o una tabla de entradas. Para buscar un archivo, se escanea toda la lista hasta que se encuentre un nombre de archivo coincidente. Claramente, esto no es deseable para el rendimiento. Muchos sistemas de archivos modernos también usan tablas hash o árboles B para una búsqueda rápida, pero no todos pueden tenerlos. Mantener cada directorio pequeño significa tiempos de acceso rápidos.

amon
fuente
1
"Algunos sistemas de archivos (¡razonablemente modernos!) están limitados a 32000 entradas en un solo directorio". Si esa es la limitación más estricta que cumple Git, ¿no sería mejor para Git haber usado los primeros tres caracteres del hash, en lugar de los dos primeros ? Esto significaría que el objectsdirectorio podría contener hasta 4096 subdirectorios en lugar de limitarse a 256, cumpliendo el requisito anterior, pero con la ventaja adicional de que esos subdirectorios serían 16 veces menos propensos a terminar conteniendo> 32000 archivos.
sampablokuper
1

Estos 256 depósitos permiten a git almacenar repositorios más grandes en sistemas de archivos que limitan la cantidad de archivos en un directorio y proporcionan un rendimiento descendente en sistemas de archivos que se vuelven más lentos con directorios que contienen muchos archivos.

Kasper van den Berg
fuente
1

Hay algunos sistemas de archivos y / o implementaciones de sistemas de archivos y / o implementaciones de libc donde el rendimiento se degrada con un gran número de entradas de directorio.

Jörg W Mittag
fuente