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.
je dobré používat hash souboru (třeba SHA1 ale kolikrád by postačilo i MD5, dávám ale přednost prvnímu).
Dává totiž přirozený shard key a zároveň snižuje prediktivnost při „kdo zná link“ sdílení.
Pro routování takových mohutných „adresářových“ struktur je stejně vnodnější cluster nebo cloud. Pro relevantní použití na jednom stroji nemá smysl použít více než 2 úrovně zanoření (u archivů max 3 — obrovské úložiště, málo přístupů)
1024 × 1024 souborů si v ČR nikdo nebude prohlížet najednou.
Tím odkazem na mongo nechci říct, že by se objemná data měla ukládat do databáze (pokud není používána databáze na to určená, která má jako úložiště celý fyzický disk prosebe — najdete pak rozdíl mezi DB a souborovým systémem?)
V praxi to vyřeší proxy ;-)
Pri hledani souboru se opravdu pouziva linearni vyhledavani?
Samozřejmě, že nepoužívá.
Tedy jeste je rano a asi jsem se jeste „nerozjel“ (pred prvnim kafem ;)), ale clanek jsem asi nejak nepochopil:
S timto se da souhlasit:
„jen pouhé vypsání názvů souborů v adresáři může trvat desítky sekund.“
S timhle uz ale ne:
„Při jednom milionu souborů v adresáři totiž musí operační systém prohledat průměrně 500000 položek, než najde požadovaný soubor.“
Za prve, prumerne 500000 porovnani k nalezeni stringu mezi 1000000 stringy? Ja nevim, ale to je teda sakra neefektivni algoritmus. Muzu se zeptat jak autor dosel k tomu, ze je potreba tolik operaci? A za druhe, ze zbytku clanku jsem nabyl dojem, ze autor asi testoval NTFS, ale nechce se mi verit, ze by NTFS na tom bylo tak spatne, kdyz uz dlouho pouzivane ext2 pouziva k tomu samemu modifikovane B-Stromy – nazyvaji to HTree a udavana komplexita vyhledani souboru (mam na mysli operaci prevedeni nazvu souboru na inode s polohou prvniho bloku souboru na disku) je O(1), tedy konstantni (napr. zde http://stackoverflow.com/questions/6176547/python-complexity-of-os-path-exists-with-a-ext4-filesystem). Cas fyzickeho presunu hlavy je samozrejme ruzny pro ruzne soubory, v zavislosti na jejich poloze, fragmentaci atd.
Take tabulka s prehledem pristupovych dob mi pripada, ze spise dokazuje, ze ty casy jsou vice mene konstantni nehlede na hloubku adresarove struktury… Tzn. nemuzu si pomoct, ale problem reseny v clanku mi prijde jako virtualni a k zadnym performance problemum nedochazi…
A spravovat milion obrazku pomoci total commandera pres FTP je asi taky nesmysl….
Takze nevim… jdu si dat to kafe radsi ;)
Pokud mne paměť neklame, tak v nějakém defaultním nastavení ext2 se soubory v adresáři opravdu vyhledávaly ručně. Až ext3 už umělo zapnout dir_index.
Jinak úloha: „Vypiš všechny soubory z adresáře“ samozřejmě má složitost O(n) – je zřejmé, že bude trvat dlouho :-)
Článek tak nějak předpokládá, že hledání souboru v adresáři má lineární časovou složitost. Naprostá většina moderních FS nemá soubory v adresáři uloženy jako prostý seznam, ale používá B-strom nebo něco podobného, takže úvaha v článku je zcestná. Chápu rozdělení do několika úrovní kvůli přehlednosti, ale čistě z hlediska výkonu tak adresářová struktura jen simuluje strom místo lineárního seznamu — přitom nativní implementace stromové vyhledávací strukury ve FS je rychlejší, jak je ostatně vidět např. na datech naměřených pro NTFS.
Shrnutí: článek mi připadá hodně nedotažený…
SDDisk jsem bohužel neměl pro testy k dispozici, domnívám se ale, že eliminace času pro přesun hlav a čekání na sektor se projeví pouze zkrácením času D a relativní výsledky by tedy byly podobné.
K tvrzení, že k prohledání N názvů souborů je průměrně třeba N/2 porovnání, jsem došel odkrokováním kódu operačního systému debugerem. Je pravda, že už je tomu pár let a že se jednalo o FAT, ale stejná lineární složitost platí i pokud FS používá hašovací tabulky.
Rozdíl je jen kvantitativní (kratší čas S), neboť namísto porovnávání stringů operací REPE CMPS pro každý název souboru stačí k nalezení hashe v tabulce jedna strojová operace REPNE SCAS pro celý adresář, ovšem její trvání je opět přímo úměrné délce hashovací tabulky.
V případě indexovaných hash tabulek je situace příznivější, jak správně upozornil Bretislav Wajtr, a na místě činitele S bychom měli rekurzivně použít obdobný vzorec pro celkovou dobu nalezení souboru v jednom adresáři, kde by ovšem parametr H reprezentoval hloubku použitého HTree.
Souhlasím s Jirkou Koskem, že u FS interně využívajících víceúrovňový index je členění do podadresářů z hlediska výkonu redundantní, ale mnohdy je potřeba k souboru přistoupit nějakým tím filemanagerem, například pokud uživatel reklamuje chybné zobrazení svého avataru, obchodník chce dávkově nahradit obrázky zboží ap. Pak oceníme, když adresářová struktura má tolik úrovní, aby počet souborů v jedné složce nemusel překročit tisícovku.
MS-DOS zápasil s nedostatkem paměti. FAT měl navíc efektivnější přístup k hledání souborů než má ext filesystém, tak se to dalo.
Tomuto nerozumím, proč je délka trvání nalezení položky v hashovací taublce přímo úměrná délce hashovací tabulky? Nalezení položky v hashovací tabulce má přece typicky konstantní časovou složitost.
Ta lineární složitost se týká neseřazených hashovacích tabulek. Je ale fakt, že se v dnešních souborových systémech moc nepoužívá, přestože tato implementace má výhodu v rychlosti přidávání položek do hashovací tabulky (při vytváření nového souboru).
Ani u FS se stromem indexových hashů ale není doba vyhledání zcela nezávislá na počtu souborů, neboť s rostoucím N se zvyšuje četnost kolizí, jejichž řešení pak zpomaluje nalezení cílové hodnoty.
Takže jsme se v diskusi dozvěděli, jak správně a efektivně rozložit soubory, kdybychom to programovali před 20 a více lety. Kdybych shrnul celkový dojem z článku. O dnešku to neříká vůbec nic.
Nemluvě o tom, že dnes jde spíše o rychlost diskové keše, než o uspořádání na disku. A to přesto, že filesystémy mají jména souborů uložená i ve stromech pro rychlejší vyhledávání.
Nejde len o vyhladavanie ako take, to sa odohrava v RAM. Skor je problem s tym ze ak sa inode popisujuci prehladavany adresar nezmesti do jedneho clustra, potom ho najskor treba pozbierat kde tade po disku a az potom je ho mozne prehladat…
Ano?
Pomíjím to, že řada disk/filesystémů už dávno nepoužívá inody.
Dá se předpokládat, že pokud máte web, tak sem tam nějaký request na něj přijde. A tedy adresáře jsou v diskové cachi. Kromě prvního přístupu se vůbec při procházení adresářů nenačítají, ale pracuje se na úrovni paměti.