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ářů?
Okamžiky z WordCamp Prague 2019. Sesbírali jsme z Twitteru.
Doporučení WCAG (Web Content Accessibility Guidelines, Směrnice o přístupnosti webového obsahu) aktuálně ve verzi 2.1 představuje v současné době nejrozšířenější a celosvětově uznávanou metodiku tvorby přístupného (nejen webového) obsahu. Za jeho vytvořením stojí pracovní skupina WAI v rámci konsorcia W3C. Pokud to s přístupností myslíte aspoň trochu vážně, je vhodné se s obsahem tohoto doporučení seznámit.
Heslovitě: Google Docst REST API. Bootstrap 4.3.0. ImmortalDB. Linaria 1.0. WebBluetooth. Články 11 a 13. Přetečení v GPS. Logstalgia. Ngrok. Domény .dev.
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.
Re:
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 ;-)
Sekvencne
Pri hledani souboru se opravdu pouziva linearni vyhledavani?
Re: Sekvencne
Samozřejmě, že nepoužívá.
Nechapu
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 ;)
Re: Nechapu
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 :-)
Uhm
Č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.
nedotažený..
Shrnutí: článek mi připadá hodně nedotažený…
Nořit, ale nepřenořit
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.
Re: Nořit, ale nepřenořit
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.
Re: Ondřej
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.
Re: Ondřej
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…
Re:
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.