ext3? dir. entry-k sorrendje? e?

Naplózó filerendszerek (journaling)

Ezt most nem ertem. deb/lenny alatt, ext3fs: ha egy konyvtarat feltoltok file-okkal, szep sorrendben, majd egyesevel probalom elerni (masolas, feldolgozas, `ls -U`, barmi), akkor teljesen veletlenszeruen jonnek a file-ok. Mondhatni, kriptografiailag is megbizhato veletlenszamgeneratort kapunk... (najo talan nem, de annyira random hogy semmi rendszert nem ve'lek felfedezni benne). Ez viszont igy nyilvan nem az igazi es ez nem kifejezes (lasd: szekvencialis eleres; random seekek; uninterruble sleep, reszponzivitas hianya; diszk elettartama; ...)

Tehat ezt most igy hogy?

Pelda: 


#!/bin/sh
mkdir files
for f in `seq -w 1 1000` ; do echo $f > files/$f.dat ;  done
ls -U files | sed 's/\.dat//g' > out

gnuplot> plot 'out' u 0:1 w p pt 2
  • 4610 megtekintés

( apal v | 2009. 10. 30., p – 21:32 )

E? senki sem tapasztalt ilyesmit? miert nem irnak a man-ok errol semmit?

Ha jol emlekszem az ext3 manualbol, akkor a dir_index mount opcioval lehet kapcsolgatni, hogy hash-be tegye-e a dir. entryket. Defaultbol persze be van kapcsolva, es ez megmagyarazna, hogy miert is jon total random minden alkalommal.

man mount, es az ext3 kornyeken nezz korbe.

Ha nem, akkor paff, nemtom, google.

Egen, ez az. Koszi. Csakhat ez az opcio mar ket debiannal korabban is megvolt, es akkor nem kavarta ossze. Mindegy, most akkor lehet vegigmenni a sok ext3-on hogy ne csinaljon ilyet.

Eh, ez az etch => lenny atallas nagyon nyugos, sok aprosag jott elo" (portmap fagyas, lilo+raid, hwaddr forditva, ...).

Hozza kell tennem, ez igy ronda. Es ha egyszer mentesbol kell visszallitani a file-okat, akkor szejjelmegy az egesz rendszered? Tudtommal nincs olyan archivalo eszkoz, ami a file-ok sorrendjet is megtartana (mar a dump-ot kiveve).

Sokkal normalisabb ennel meg az is, hogy minden file ele odarakod a millisec pontossagu 64 bites epoch time-ot, vagy ilyesmi, es siman filenevre rendezel.

Ronda, ronda... oke. Csak ott a masik veglet is. Leirok egy konyvtarba 2000 db 5megas file-t (ez elofordul). Sorrendben, szepen lekeletkezik. Ha barmilyen modon el akarom erni, feldolgozni, ugy hogy a nyers sorrendre hagyatkozok (pl a program azt csinalja hogy "szaladj vegig ennek meg ennek a konyvtarnak a file-jain), akkor szarra'megy a diszk. hasonloan masolaskor, tar-ozaskor, biztonsagi menteskor, stb. detto.

7200rpm-es sata diszken az átlagos see ktime olvasásnál 9ms.
Átlagosan rosz esetben tehát lesz 18 másodperc seek time. Mentésnél másolásnál ekkora mennyiségű adatnál ez szerintem nem mérvadó.
Ha mégis, akkor irigylem a problémáidat. :)
Egyébként meg előbb utóbb a fájlrendszered úgyis fragmentálódik.

Ha tényleg olyan fontos az a pár másodperc, akkor jobban jársz 15k rpm-es diszkekkel, vagy SSD-vel.

Szemet szúrt a téma, és gyorsan rávetettem magam az Etch-re.

Létrehozási sorrend: 1.txt, 2.txt 6.txt 3.txt
ls- U sorrend: 2.txt, 1.txt, 3.txt, 6.txt

majd létrehoztam még: 4.txt, 5.txt
ls- U sorrend: 2.txt, 1.txt, 3.txt, 4.txt, 5.txt, 6.txt

Ugyanez Lenny-n: 1,3,2,6 majd 4,1,3,2,5,6

Szóval tényleg totál random. Jó ez a dolog amúgy valamire? Az is igaz, hogy ha nem merül fel a téma, nyugodtan éltem volna tovább :).

Etch-re.
etch? ott ezt nem csinalta... legalabbis nekem...

Jó ez a dolog amúgy valamire?
hat hogy mire _nem_ jo azt tudom. egyebkent nem ertem, amennyire en ismerem az ilyen tree-jellegu implementaciokat, eleg extrem ez a sorrend. bar ha hashtree-t hasznal, akkor mondjuk valahol meg lehet ideologizalni. mar egy crc32 is jol kever, ilyen celokra pont jo hash.

( uid_2716 | 2010. 05. 27., cs – 02:15 )

Hevenyészve, spekulálva, bizonyítékok nélkül,

  1. A directory egy file, amiben bejegyzések vannak. Egy entry-ben alapesetben semmi más nincs benne, csak egy név->inode leképezés.
  2. Az inode tartalmazza az összes többi infót a file-ról (például link count, permission bit-ek, tulajdonos, csoport, méret, időbélyegek), a néhány első blokk közvetlen címét a diszken, aztán a másodlagos inode blokkok címet stb.
  3. Amikor név szerint
    stat()

    -olsz egy file-t, akkor az adott könyvtárban meg kell keresni a megfelelő entry-t (ehhez a könyvtár-file blokkjait kell olvasni), majd a megtalált név->inode leképezés alapján el kell menni az inode-ot tartalmazó diszk blokkhoz a metaadatokért. Amikor egy 

    ls -l

    -t csinálsz, akkor a könyvtárat is végig kell olvasni, meg mindegyik hivatkozott inode-ot is meg kell nyitni.

  4. Amikor egy file-t még olvasni is akarsz, akkor az inode után még el kell menni a megfelelő adatblokkhoz is.

A 3. lépésben leírtak már az 

ls -l

-nél is rángatták a fejet, részben ezért vezették be az ext2-nél a 

filetype

opciót, ami a könyvtárbejegyzésben duplikálta az inode-ból a file típusát (az nem tud megváltozni az inode-ban, ezért nem gond, ha akárhány link van is az inode-ra). A directory-file blokkjainak végigolvasására alapból a 

readdir()

függvény szolgált (megfelelő megnyitás után, persze). Ha megnézed, hogy a visszaadott entry mit tartalmazott hordozhatóan, akkor csak egy nevet és egy inode number-t találsz. Ha viszont a linuxos (mint kernel) 

readdir()

manlapot nézed meg, ott látsz még egy 

d_type

-ot is, ami pontosan a fenti 

filetype

funkció miatt elérhető.

Régen a könyvtárak szervezése szekvenciális volt. Ebből két következmény fakadt:

  1. Olyan sorrendben kaptad meg
    readdir()

    -rel a bejegyzéseket, ahogy létrehoztad (legalábbis akkor, ha a könyvtárban korábban sosem volt több file, ezért mindig a végére ragasztott létrehozáskor),

  2. nagy könyvtárakban lassú volt egy adott entry név szerinti elérése (O(n)).

A második felgyorsítására kitalálták, hogy fába szervezik (O(log(n)), vagy hash-be (ha ritkán módosul a könyvtár, akkor ez megéri, mert az újraszervezés ugyan drága, de utána a lookup O(1)), ez viszont agyonvágta az elsőt. Annak idején a reiserfs körül volt valami hiszti, még a különféle szabványok bizottságai is hozzászóltak, ha jól emlékszem: a felhasználók (userspace programozók) ragaszkodtak a szekvenciális végigolvasáshoz (

opendir()

, 

readdir()

, 

closedir()

), az új fs fejlesztőinek viszont nyűg volt, mert az új implementációt visszafogta az, hogy kompatibilisnek kellett maradni a régi felülettel.

Egy 2005. nov. 30-ai feljegyzésem szerint egy régebbi (2.4.32) kernelen már volt 

dir_index

opció az ext2-nél is, de a kernel csak akkor vette figyelembe, ha ext3-ként volt mount-olva, és úgy is csak akkor, ha valóban ext3-ként volt használva, azaz 

has_journal

flaggal. Az újabb kerneleken (2.6) már önmagában is megy a 

dir_index

ext2-vel (és én a mai napig ext2-t használok). Tehát ha régi kernelen kapcsoltál be 

dir_index

-et, akkor hatástalan volt.

Gyakori feladat egy könyvtár végigolvasása, és minden egyes file megnyitása. Ez ugye a fentiek szerint miből tevődik össze:

  • könyvtár blokkjainak végigolvasása, mindig vesszük a következő entry-t, valamilyen sorrendben megkapva
  • minden egyes entry-re csinálunk az open()-ben egy teljesen különálló lookup-ot. Ez szekvenciális (lista) ábrázolásnál azt jelentette, hogy egy n elemű könyvtár végignyitogatásához O(n^2) lépés kellett. Fánál O(n*log(n)), de még ez is gáz, hiszen ott állunk az adott entry-n, ott az inode number, mért nem nyitjuk meg a szerencsétlen file-t? Na erre találták ki az
    openat()

    függvényt. (Szerkesztés: ez baromság volt, az openat()-ot egyáltalán nem erre találták ki. Bocsánat.) Drepper mester bemutatja, hogyan kell használni. Az 

    openat()

    által visszaadott fd-ből utána lehet 

    fdopen()

    -nel stdio stream-et csinálni.

  • Minden megynyitott file-nál el kell mennünk az inode-hoz (minimum jogok ellenőrzése), még az
    openat()

    -os módszerrel is.

  • Minden file-nál el kell ugranunk az adatblokkokhoz, hiszen beolvassuk.

Ez irdatlan fejrángatást jelent. Egy kicsit azonban lehet trükközni (persze nem hordozhatóan), és állítom, hogy ez a negyedik alkalom, hogy ezt leírom a hupon.

Először is, a 

vm.vfs_cache_pressure

sysctl-t vegyük le 1-re; így lényegében a directory blokkjai és az inode-ok blokkjai nem fognak kikerülni a kernelmemóriából, ha már egyszer bekerültek. Akárhogy érjük is el az entry-ket, legalább a fejet nem kell rángatni, csak az adatblokkokhoz.

Az adatblokkokon pedig azzal lehet segíteni, hogy az ext2 (ext3 is talán) meghálálja az alábbi tevékenységet:

  • létrehozunk egy új file-t
  • szekvenciálisan végigírjuk

és ezt ismételgetjük. Ilyenkor az új file létrehozásakor növekvő inode számot kapunk, az adatblokkok pedig nemcsak file-okon belül fognak egymás után elhelyezkedni a diszken, hanem a file-ok is szépen egymás mellé lesznek pakolva.

A felhasználás módja pedig az, hogy a könyvtárat beolvassuk úgy, ahogy (amúgy is dentry cache-ből jön), lerendezzük inode szám szerint, majd végigolvassuk a file-okat. Mivel az inode blokkok is cache-ben vannak, a fejnek el sem kell mozdulnia az adatblokkok fölül. Az adatblokkok pedig mind file-on belül szekvenciálisan helyezkednek el, mind (az inode szerint növekvő file-elérés miatt) file-ok között ugrándozás nélkül következnek.

Az lbzip2 teszteléséhez felhasználtam ezt a fuzz-olt test suite-ot. 321818 kerge bz2 file van benne, amelyeket egy könyvtárba bontott ki. Amikor egy ilyen könyvtárat letöröltem, alapból név szerint rendezve, ahol a név a tartalom SHA1-e volt, vagyis lényegében random, nagyon sokat kellett várnom. Inode szerint rendezve 1000*-es gyorsulást értem el (megmértem).

Szerkesztés: ellenőriztem a tavaly októberi post-omat, rosszul emlékeztem. Egyrészt nem (csak) rm volt, hanem előtte grep, másrészt az 1000*-es szorzót most a légből kaptam, nem mértem meg. Mindenesetre azt írtam, hogy "iszonyatos" volt a gyorsulás.

Vagyis ha tar-hoz kell a dolog, akkor 

find ... -printf '%i %p\n' | sort -n | cut -f 2- -d ' ' | tar -c -T -

.

A fentieknek megfelelően, ha sparse file-t hozunk létre és össze-vissza seek-elve írjuk, vagy preallokáció nélkül írogatunk ötven file-nak mindig a végére, akkor azokat a file-okat szekvenciálisan végigolvasni lesz katasztrófa. Pont erre találták ki az extent-eket, hogy előre le lehessen foglalni az összefüggő területet kézi végigírás nélkül, és persze van hordozható API-ja is (ami nyilván nem beszél a lefoglalt terület összefüggőségéről (It is implementation-defined whether a previous posix_fadvise() call influences allocation strategy), de ettől az még minden épkézláb OS-en nyilván össze fog függeni).