Nořit, ale nepřenořit

Jako pořádkumilovní webmasteři dáváme všechny ikonky, obrázky a fotky do složky img. Co ale když jejich počet časem naroste na desetitisíce, nebude lepší si hned zpočátku rozmyslet jejich rozdělení do podadresářů?

Ne všechny informace se při tvorbě webového projektu hodí ukládat do databáze, mnohdy je rozumnější mít je k dispozici ve formě samostatných souborů. Typickým příkladem jsou multimediální nahrávky, fotografie prodávaného zboží, avatary uživatelů. Selekci pak provádí namísto databáze webový server prostřednictvím souborového systému. Položky se adresují statickou adresou, například http://projekt.cz/img/123456.png, takže mohou být uloženy ve vyrovnávací paměti uživatelova browseru a při opakovaném zobrazení tím šetří přenosovou kapacitu. Další výhodou pro webmastera je možnost snadné kontroly uložených souborů přímo na serveru pomocí souborového manažeru s prohlížečem obrázků.

Pokud je projekt úspěšný a počet položek naroste nad řádově tisíce, přímý přístup k souborům přestává být výhodný, jen pouhé vypsání názvů souborů v adresáři může trvat desítky sekund. Také webovému serveru trvá delší dobu požadovaný soubor poslat uživateli. Při jednom milionu souborů v adresáři totiž musí operační systém prohledat průměrně 500 000 položek, než najde požadovaný soubor. Správným řešením je samozřejmě rozdělit soubory do podadresářů a omezit jejich maximální počet v každé složce například na jeden tisíc.

Typické URL položky s identifikátorem 123456 pak je http://projekt.cz/img/123/123456.png a průměrný počet prohledání, které musí systém provést, je 500 (nalezení podadresáře) plus 500 (nalezení souboru), což je dohromady pětsetkrát méně než při ploché struktuře bez podadresářů.

Extrapolací bychom mohli dojít k závěru, že s větší hloubkou vnoření dosáhneme ještě rychlejšího přístupu. Například při omezení na max. deset souborů v adresáři by URL mělo tvar http://projekt.cz/img/1/2/3/4/5/123456.png a průměrný počet porovnání názvu by při tomto šestiúrovňovém vnoření byl 6×5, tedy ještě třiatřicetkrát menší oproti dvojí úrovni vnoření. Na druhé straně se ale zvyšuje počet podadresářů, které je nutno na disku najít a otevřít. Otevírání souborů a podadresářů je přitom časově nákladná operace, neboť OS musí zkoumat oprávnění ke čtení a konkurenční přístupy ostatních procesů, mnohdy to vyžaduje fyzické přesouvání diskových hlav. Intuitivně tedy cítíme, že optimální řešení bude někde mezi oběma extrémy.

Hledání optimální organizace souborů

Rozborem činnosti operačního systému můžeme odvodit, že celková doba přístupu T v závislosti na počtu prohledávaných podadresářů H (hloubce vnoření) se řídí vztahem
T = H × (D + ½ × S × H N )

kde N je celkový počet souborů,
D je čas k otevření a načtení adresáře a
S je čas porovnání jednoho názvu v načteném adresářovém záznamu.

Najít analyticky optimální hloubku vnoření H pro minimalizaci přístupové doby T není snadné kvůli obtížnému odhadu časů D a S. Ty totiž závisejí na technologii disku, na množství disponsibilní paměti pro diskovou cache, na souborovém systému. Rozhodl jsem se je zjistit empiricky, skriptem měřícím přístupovou dobu při otevírání náhodně zvolených souborů.

Pomocný skript nejprve vygeneruje na disku zvolený počet N souborových vzorků v adresářových strukturách pro různé hloubky vnoření (H=1,2,3,6). Pak pro každou hloubku opakovaně otevírá pseudonáhodně zvolené soubory a měří přitom čas. Výsledky zapisuje na konsolu a do deníkového souboru.

Výsledky testu

Čísla ve sloupcích H=1 až H=6 jsou zprůměrované přístupové doby otevření jednoho souboru v milisekundách. Menší hodnota znamená příznivější výsledek.

Max. počet souborů ve složce → 106 103 102 101
DISK FS RAM N H=1 H=2 H=3 H=6
disk array NTFS 16GB 106
0,54
0,62
0,73
0,86
disk array reiserFS 4GB 106
1.60
1.40
0.57
0.70
disk array efs3 4GB 105
0.13
0.09
0.09
0.11
7200 rpm NTFS 2GB 105
0,19
0,21
0,24
0,32
5400 rpm NTFS 1GB 104
2,30
1,50
1,68
2,15
USB flash FAT32 1GB 104
25,97
29,87
35,75
53,74

Závěr

Rotační disky je dobrým zvykem při instalaci projektu nejprve defragmentovat a pak vytvořit kompletní prázdnou podadresářovou strukturu, aby se minimalizovala nutnost přesouvání hlav během přechodů mezi podadresáři.

Víme-li bezpečně, že počet souborů nepřesáhne několik tisíc, není třeba jejich strukturování do podadresářů vůbec řešit. Podobně pokud má server dostatek operační paměti, kdy většina prohledávání probíhá v diskové cache. V ostatních případech je vhodné už při návrhu projektu počítat s omezením maximálního počtu souborů v jedné složce na několik set. I když rozdíly v přístupové době nejsou příliš markantní, rozdělení do podadresářů usnadní manipulaci se soubory na serveru, jejich prohlížení, zálohování apod.

Kdo má pochyby, může si skript v PHP použitý při mých testech stáhnout zde a vyzkoušet v konkrétních podmínkách svého webu.

Autor žije a pracuje ve Vítkově, kde se zajímá o informační techniku až na dřeň.

Komentáře: 15

Přehled komentářů

Pavel Lang
Pavel Lang Re:
Wagus Sekvencne
Miloslav Ponkrác Re: Sekvencne
Bretislav Wajtr Nechapu
veros Re: Nechapu
Jirka Kosek Uhm
W nedotažený..
Pavel Šrubař Nořit, ale nepřenořit
Miloslav Ponkrác Re: Nořit, ale nepřenořit
Ondřej
Pavel Šrubař Re: Ondřej
Miloslav Ponkrác Re: Ondřej
DeathWalker
Miloslav Ponkrác Re:
Zdroj: https://www.zdrojak.cz/?p=12287