15 komentářů k článku Nořit, ale nepřenořit:

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

    1. Pavel Lang

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

  2. Bretislav Wajtr

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

    1. veros

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

  3. Jirka Kosek

    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.

  4. W

    nedotažený..

    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ý…
  5. Pavel ŠrubařAutor příspěvku

    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.

    1. Miloslav Ponkrác

      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.

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

  7. Pavel ŠrubařAutor příspěvku

    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.

    1. Miloslav Ponkrác

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

  8. 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…

    1. Miloslav Ponkrác

      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.

Napsat komentář

Tato diskuse je již příliš stará, pravděpodobně již vám nikdo neodpoví. Pokud se chcete na něco zeptat, použijte diskusní server Devel.cz

Zdroj: https://www.zdrojak.cz/?p=12287