Il est possible de mettre tous les fichiers dans un répertoire, bien que parfois cela puisse devenir un peu volumineux. De nombreux systèmes de fichiers ont une limite . Vous souhaitez mettre un référentiel git sur un lecteur au format FAT32 sur une clé USB? Vous ne pouvez stocker que 65 535 fichiers dans un seul répertoire. Cela signifie qu'il est nécessaire de subdiviser la structure de répertoires afin que le remplissage d'un seul répertoire soit moins probable.
Cela deviendrait même un problème avec d'autres systèmes de fichiers et de plus grands référentiels git. Un dépôt git relativement petit que j'ai accroché (environ 360 Mo) et il a 181 546 objets pour des fichiers 11k. Tirez le dépôt Linux et vous avez 4 374 054 objets. Si vous les mettiez tous dans un seul répertoire, il serait impossible de vérifier et planterait (pour une certaine signification de «planter») le système de fichiers.
Donc? Vous le divisez par octet. Des approches similaires sont effectuées avec des applications telles que 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_
Au-delà, cela va aussi à une question de performance. Considérez les performances NTFS avec de nombreux noms de fichiers longs :
Windows NT prend beaucoup de temps pour effectuer des opérations de répertoire sur des lecteurs formatés avec le système de fichiers Windows NT (NTFS) qui contiennent un grand nombre de fichiers avec des noms de fichier longs (noms qui ne sont pas conformes à la convention 8.3) dans un seul répertoire.
Lorsque NTFS énumère des fichiers dans un répertoire, il doit rechercher les noms 8.3 associés aux noms de fichiers longs. Dans la mesure où un répertoire NTFS est conservé dans un état trié, les noms de fichiers longs correspondants et les noms 8.3 ne sont généralement pas côte à côte dans la liste des répertoires. Ainsi, NTFS utilise une recherche linéaire du répertoire pour chaque fichier présent. Par conséquent, le temps nécessaire pour effectuer une liste de répertoires augmente avec le carré du nombre de fichiers dans le répertoire. Pour un petit nombre de fichiers (moins de quelques centaines), le délai est négligeable. Mais comme le nombre de fichiers dans un répertoire atteint plusieurs milliers, le temps nécessaire pour effectuer une liste peut augmenter en minutes, heures ou même jours. Le problème est aggravé si les noms de fichiers longs sont très similaires - ne différant que par les derniers caractères.
Avec des fichiers nommés d'après les sommes de contrôle SHA1, cela pourrait être une recette pour des performances catastrophiques et abyssales.
Bien que ce qui précède provienne d'une note technique de Windows NT 3.5 (et NTFS 1.2 - couramment utilisé de 1995 au début des années 2000), cela peut également être vu dans des choses telles que EXT3 avec des implémentations du système de fichiers étant des listes liées nécessitant une recherche O (n) . Et même avec ce changement d'arbre B:
Bien que l'algorithme HTree ait considérablement amélioré les temps de recherche, il peut entraîner des régressions de performances pour les charges de travail qui utilisent readdir () pour effectuer une opération sur tous les fichiers d'un grand répertoire.
...
Une solution potentielle pour atténuer ce problème de performances, qui a été suggérée par Daniel Phillips et Andreas Dilger, mais pas encore implémentée, implique que le noyau choisisse des inodes libres dont les numéros d'inode correspondent à une propriété qui regroupe les inodes par leur hachage de nom de fichier. Daniel et Andreas suggèrent d'allouer l'inode à partir d'une plage d'inodes en fonction de la taille du répertoire, puis de choisir un inode libre dans cette plage en fonction du hachage du nom de fichier. Cela devrait en théorie réduire la quantité de thrashing qui en résulte lors de l'accès aux inodes référencés dans le répertoire dans l'ordre readdir. En revanche, il n'est pas certain que cette stratégie entraînera une accélération; en fait, cela pourrait augmenter le nombre total de blocs d'inode qui pourraient devoir être référencés, et ainsi aggraver les performances des charges de travail readdir () + stat (). Clairement,
Soit dit en passant, ce morceau sur la façon d'améliorer les performances date de 2005, la même année que git a été publié.
Comme vu avec Firefox et de nombreuses autres applications qui ont beaucoup de fichiers mis en cache de hachage, la conception de fractionner le cache par octet. Il a un coût de performance négligeable, et lorsqu'il est utilisé sur plusieurs plates-formes avec des systèmes qui peuvent être un peu à l'ancienne, cela pourrait très bien faire la différence entre le fonctionnement du programme ou non.
gitle système «pack» de 'atténue beaucoup de ces problèmes. Théoriquement,gitpourrait n'utiliser qu'un seul répertoire, et simplement reconditionner lorsque le nombre de fichiers dans ce répertoire a dépassé une certaine limite (éventuellement dépendante de FS).Il y a deux raisons pour lesquelles cela est souhaitable.
Les répertoires ne peuvent pas être arbitrairement volumineux. Par exemple, certains systèmes de fichiers (raisonnablement modernes!) Sont limités à 32 000 entrées dans un seul répertoire. Le nombre de validations dans le noyau Linux est dans cet ordre de grandeur. La subdivision des validations par leurs deux premiers chiffres hexadécimaux limite la taille de niveau supérieur à 256 entrées. Les sous-répertoires seront beaucoup plus petits pour les git repos typiques.
Les répertoires sont analysés de façon linéaire. Dans certains systèmes de fichiers (par exemple la famille Ext *), un répertoire est une liste liée ou une table d'entrées. Pour rechercher un fichier, toute la liste est analysée jusqu'à ce qu'un nom de fichier correspondant soit trouvé. De toute évidence, cela n'est pas souhaitable pour les performances. De nombreux systèmes de fichiers modernes utilisent en outre des tables de hachage ou des arborescences B pour une recherche rapide, mais tout le monde ne peut pas les avoir. Garder chaque répertoire petit signifie des temps d'accès rapides.
la source
objectsrépertoire pourrait contenir jusqu'à 4096 sous-répertoires au lieu d'être limité à 256, répondant à l'exigence ci-dessus, mais avec l'avantage supplémentaire que ces sous-répertoires seraient 16 fois moins susceptibles de contenir> 32000 fichiers eux-mêmes.Ces 256 compartiments permettent à git de stocker des référentiels plus importants sur des systèmes de fichiers qui limitent le nombre de fichiers dans un répertoire et fournissent des performances de descente sur des systèmes de fichiers qui deviennent plus lents avec des répertoires contenant de nombreux fichiers.
la source
Il existe certains systèmes de fichiers et / ou implémentations de système de fichiers et / ou implémentations libc où les performances se dégradent avec un grand nombre d'entrées de répertoire.
la source