Możliwe jest umieszczenie wszystkich plików w jednym katalogu, choć czasem może to być nieco duże. Wiele systemów plików ma ograniczenia . Chcesz umieścić repozytorium git na dysku sformatowanym w systemie FAT32 na pamięci USB? Możesz przechowywać tylko 65 535 plików w jednym katalogu. Oznacza to, że konieczne jest podzielenie struktury katalogów, aby zapełnienie jednego katalogu było mniej prawdopodobne.
Stałoby się to nawet problemem w przypadku innych systemów plików i większych repozytoriów git. Stosunkowo małe repozytorium git, które mam na hangoucie (około 360 MB) i ma 181 546 obiektów na pliki 11k. Wyciągnij repozytorium Linuksa, a otrzymasz 4 374 054 obiektów. Jeśli umieściłbyś je wszystkie w jednym katalogu, niemożliwe byłoby wyewidencjonowanie i spowodowałoby awarię (w pewnym sensie „awarii”) systemu plików.
Więc? Dzielisz to na bajty. Podobne podejścia stosuje się w aplikacjach takich jak 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_
Poza tym chodzi również o kwestię wydajności. Rozważ wydajność NTFS z wieloma długimi nazwami plików :
System Windows NT zajmuje dużo czasu na wykonywanie operacji katalogowych na dyskach sformatowanych w systemie plików Windows NT (NTFS), które zawierają dużą liczbę plików o długich nazwach plików (nazwach niezgodnych z konwencją 8.3) w jednym katalogu.
Gdy NTFS wylicza pliki w katalogu, musi wyszukać nazwy 8.3 związane z długimi nazwami plików. Ponieważ katalog NTFS jest utrzymywany w stanie posortowanym, odpowiadające im długie nazwy plików i nazwy 8.3 zazwyczaj nie znajdują się obok siebie na liście katalogów. Tak więc NTFS używa liniowego przeszukiwania katalogu dla każdego obecnego pliku. W rezultacie czas potrzebny na wykonanie listy katalogów wzrasta wraz z kwadratem liczby plików w katalogu. W przypadku niewielkiej liczby plików (mniej niż kilkaset) opóźnienie czasowe jest nieznaczne. Ale gdy liczba plików w katalogu wzrasta do kilku tysięcy, czas potrzebny na wykonanie listingu może wzrosnąć do minut, godzin, a nawet dni. Problem pogłębia się, jeśli długie nazwy plików są bardzo podobne - różnią się tylko kilkoma ostatnimi znakami.
W przypadku plików nazwanych na podstawie sum kontrolnych SHA1 może to być przepis na katastrofę i fatalną wydajność.
Chociaż powyższe pochodzi z uwagi technicznej z systemu Windows NT 3.5 (i NTFS 1.2 - powszechnie używanego od 1995 r. Do początku 2000 r.), Można to również zauważyć w takich rzeczach, jak EXT3 z implementacjami systemu plików będącego listami połączeń wymagającymi wyszukiwania O (n) . I nawet przy tej zmianie B-drzewa:
Chociaż algorytm HTree znacznie skrócił czas wyszukiwania, może powodować regresję wydajności dla obciążeń wykorzystujących readdir () do wykonywania niektórych operacji wszystkich plików w dużym katalogu.
...
Jedno potencjalne rozwiązanie w celu złagodzenia tego problemu z wydajnością, które zostało zasugerowane przez Daniela Phillipsa i Andreasa Dilgera, ale nie zostało jeszcze wdrożone, polega na tym, że jądro wybiera wolne i-węzły, których numery i-węzłów spełniają właściwość grupującą i-węzły według nazw plików. Daniel i Andreas sugerują przydzielenie i-węzła z zakresu i-węzłów na podstawie wielkości katalogu, a następnie wybranie wolnego i-węzła z tego zakresu na podstawie skrótu nazwy pliku. Teoretycznie powinno to zmniejszyć liczbę przeładowań, które powstają podczas uzyskiwania dostępu do i-węzłów, do których odwołuje się katalog w kolejności readdir. Nie jest jednak jasne, czy ta strategia spowoduje przyspieszenie; w rzeczywistości może to zwiększyć całkowitą liczbę bloków i-węzłów, które mogą wymagać odwołania, a tym samym pogorszyć wydajność obciążeń readdir () + stat (). Wyraźnie,
Nawiasem mówiąc, ten fragment dotyczący poprawy wydajności pochodzi z 2005 roku, tego samego roku, w którym wydano git.
Jak widać w Firefoksie i wielu innych aplikacjach, które mają wiele haszowanych plików buforowanych, projekt dzielenia bufora na bajty. Ma znikomy koszt wydajności, a gdy jest używany na wielu platformach z systemami, które mogą być nieco stare, może równie dobrze stanowić różnicę między działającym programem lub nie.
gitsystem „paczek” łagodzi wiele z tych problemów. Teoretyczniegitmożna użyć tylko jednego katalogu i po prostu ponownie go spakować, gdy liczba plików w tym katalogu przekroczy określony limit (prawdopodobnie zależny od FS).Są dwa powody, dla których jest to pożądane.
Katalogi nie mogą być dowolnie duże. Np. Niektóre (dość nowoczesne!) Systemy plików są ograniczone do 32000 pozycji w jednym katalogu. Liczba zatwierdzeń w jądrze Linuksa jest tego rzędu wielkości. Podział zatwierdzeń na dwie pierwsze cyfry szesnastkowe ogranicza rozmiar najwyższego poziomu do 256 pozycji. Podkatalogi będą znacznie mniejsze dla typowych repozytoriów git.
Katalogi są skanowane liniowo. W niektórych systemach plików (np. Rodzinie Ext *) katalog jest połączoną listą lub tabelą wpisów. Aby wyszukać plik, skanowana jest cała lista, dopóki nie zostanie znaleziona pasująca nazwa pliku. Oczywiście jest to niepożądane ze względu na wydajność. Wiele nowoczesnych systemów plików dodatkowo wykorzystuje tabele skrótów lub drzewa B do szybkiego wyszukiwania, ale nie każdy może je mieć. Utrzymanie małego katalogu oznacza szybki czas dostępu.
źródło
objectskatalog może pomieścić do 4096 podkatalogów zamiast ograniczać do 256, spełniając powyższy wymóg, ale z dodatkową zaletą, że podkatalogi te 16x rzadziej zawierają same> 32000 plików.Te 256 segmentów pozwalają gitowi przechowywać większe repozytoria w systemach plików, które ograniczają liczbę plików w katalogu i zapewniają wydajność opadania w systemach plików, które stają się wolniejsze w katalogach zawierających wiele plików.
źródło
Istnieją niektóre systemy plików i / lub implementacje systemu plików i / lub implementacje libc, w których wydajność spada wraz z dużą liczbą pozycji katalogu.
źródło