Perché la cartella Git .git / objects / folder è suddivisa in molte cartelle con prefisso SHA?

È possibile inserire tutti i file in una directory, anche se a volte può diventare un po 'più grande. Molti file system hanno un limite . Vuoi mettere un repository git su un disco formattato FAT32 su una chiavetta USB? È possibile archiviare solo 65.535 file in un'unica directory. Ciò significa che è necessario suddividere la struttura delle directory in modo che riempire una singola directory sia meno probabile.

Questo potrebbe persino diventare un problema con altri file system e repository git più grandi. Un repo git relativamente piccolo che ho preso in giro (circa 360MiB) e ha 181.546 oggetti per file 11k. Estrai il repository Linux e avrai a disposizione 4.374.054 oggetti. Se si inserissero tutti questi elementi in un'unica directory, sarebbe impossibile eseguire il check-out e si verificherebbe un arresto anomalo del sistema di file (per alcuni significati di 'crash').

E allora? Lo hai diviso per byte. Approcci simili sono fatti con applicazioni come 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_

Oltre a questo, si passa anche a una questione di prestazioni. Considera Rendimento NTFS con numerosi nomi di file lunghi :

Windows NT takes a long time to perform directory operations on Windows NT file system (NTFS) formatted drives that contain a large number of files with long file names (names that do not conform to the 8.3 convention) in a single directory.

When NTFS enumerates files in a directory, it has to look up the 8.3 names associated with the long file names. Because an NTFS directory is maintained in a sorted state, corresponding long file names and 8.3 names are generally not next to one another in the directory listing. So, NTFS uses a linear search of the directory for every file present. As a result, the amount of time required to perform a directory listing increases with the square of the number of files in the directory. For small numbers of files (less than a few hundred) the time delay is negligible. But as the number of files in a directory increases to several thousand, the time required to perform a listing can increase to minutes, hours, or even days. The problem is aggravated if the long file names are very similar -- differing only in the last few characters.

Con i file chiamati dopo i checksum SHA1, questa potrebbe essere una ricetta per le prestazioni disastrose e pessime.

Mentre il precedente è tratto da una nota tecnica di Windows NT 3.5 (e NTFS 1.2 - comunemente usato dal 1995 all'inizio del 2000) questo può anche essere visto in cose come EXT3 con implementazioni del filesystem che sono liste collegate richiede O (n) ricerca. E anche con quella modifica B-tree:

While the HTree algorithm significantly improved lookup times, it could cause some performance regressions for workloads that used readdir() to perform some operation of all of the files in a large directory.
...
One potential solution to mitigate this performance issue, which has been suggested by Daniel Phillips and Andreas Dilger, but not yet implemented, involves the kernel choosing free inodes whose inode numbers meet a property that groups the inodes by their filename hash. Daniel and Andreas suggest allocating the inode from a range of inodes based on the size of the directory, and then choosing a free inode from that range based on the filename hash. This should in theory reduce the amount of thrashing that results when accessing the inodes referenced in the directory in readdir order. In it is not clear that this strategy will result in a speedup, however; in fact it could increase the total number of inode blocks that might have to be referenced, and thus make the performance of readdir() + stat() workloads worse. Clearly, some experimentation and further analysis is still needed.

Per inciso, questo bit su come migliorare le prestazioni è stato dal 2005, lo stesso git dell'anno è stato rilasciato.

Come si vede con Firefox e molte altre applicazioni che hanno molti file hash memorizzati nella cache, il progetto di suddividere la cache per byte. Ha un costo di prestazioni trascurabile e, se utilizzato su più piattaforme con sistemi che potrebbero essere un po 'vecchi, potrebbe benissimo essere la differenza tra il funzionamento del programma o meno.

Ci sono due ragioni per cui è desiderabile.

Le directory non possono essere arbitrariamente grandi. E.g. alcuni (ragionevolmente moderni!) filesystem sono limitati a 32000 voci in una singola directory. Il numero di commit nel kernel di Linux è in questo ordine di grandezza. La suddivisione dei commit con le loro prime due cifre esadecimali limita la dimensione di livello superiore a 256 voci. Le sottodirectory saranno molto più piccole per i tipici repository git.

Le scansioni sono scansionate linearmente. In alcuni file system (ad esempio la famiglia Ext *), una directory è una lista o una tabella di voci collegate. Per cercare un file, l'intero elenco viene scansionato fino a trovare un nome di file corrispondente. Chiaramente, questo non è auspicabile per le prestazioni. Molti moderni file system utilizzano inoltre hash table o B-trees per una rapida ricerca, ma non tutti possono averli. Mantenere ogni directory piccola significa tempi di accesso rapidi.

Questi 256 bucket consentono a git di archiviare repository più ampi su file system che limitano i file di numeri in una directory e forniscono prestazioni di discesa su file system che diventano più lenti con le directory contenenti molti file.

Ci sono alcune implementazioni di filesystem e / o filesystem e / o implementazioni di libc in cui le prestazioni si degradano con un gran numero di voci di directory.