Přejít k navigační liště

Zdroják » Různé » Nořit, ale nepřenořit

Nořit, ale nepřenořit

Články Různé

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.

Komentáře

Subscribe
Upozornit na
guest
15 Komentářů
Nejstarší
Nejnovější Most Voted
Inline Feedbacks
View all comments
Pavel Lang

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.

Pavel Lang

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 ;-)

Wagus

Pri hledani souboru se opravdu pouziva linearni vyhledavani?

Miloslav Ponkrác

Samozřejmě, že nepoužívá.

Bretislav Wajtr

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 ;)

veros

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 :-)

Jirka Kosek

Č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.

W
  1. Tak nějak jsem čekal, že se v závěru dozvím, jaké zanoření je tedy ještě optimální a co už je moc, nebo jestli to nehraje roli ?
  2. V srovnávací tabulce mi chybí test SDD, protože tam bych čekal zásadní rozdíl od těch ostatních v rychlosti, nebo ne ?
    Shrnutí: článek mi připadá hodně nedotažený…
Miloslav Ponkrác

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.

Ondřej

„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.“

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.

Miloslav Ponkrác

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í.

DeathWalker

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…

Miloslav Ponkrác

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.

Enum a statická analýza kódu

Mám jednu univerzální radu pro začínající programátorty. V učení sice neexistují rychlé zkratky, ovšem tuhle radu můžete snadno začít používat a zrychlit tak tempo učení. Tou tajemnou ingrediencí je statická analýza kódu. Ukážeme si to na příkladu enum.