 |
Mihai Budiu -- mihaib+ at cs.cmu.edu
http://www.cs.cmu.edu/~mihaib/
24 iunie 1997
Sistemul de fișiere (file system) este o parte a unui sistem de operare care oferă utilizatorului accesul la dispozitive de memorare permanentă (discuri mai ales) sub formă de fișiere. Aceasta nu este o sarcină facilă, pentru că transformarea unui spațiu de memorie cvadridimensional (cum este discul, cu coordonate cap/cilindru/sector/octet) într-o mulțime de fișiere cu nume ierarhice (directoare) și care cresc independent și simultan nu este o treabă tocmai banală.
De fapt tehnici pentru a face acest lucru sunt studiate în orice curs de structuri de date la capitolul ``alocarea dinamică a memoriei''. Problema esențială este însă că metoda cea mai simplă -- teoretic vorbind -- este adesea departe de a fi cea mai rapidă atunci cînd este implementată. Am scris aiurea un articol despre structurile de date ale sistemului de fișiere din sistemul de operare Unix tradițional (vezi PC Report Decembrie 1996, sau pagina mea de Web pentru o copie). Consacrăm acest articol expunerii la ``grămadă'' a unei serii întregi de trucuri făcute de proiectanții de sisteme de fișiere comerciale în lupta cu milisecundele.
Concluzia care se impune este că cele mai multe sisteme de fișiere sunt derivate mai mult sau mai puțin din sistemul clasic Unix (UFS: Unix File System), dar că efortul depus pentru a le face mai rapide este adesea reflectat dominant în cantitatea de cod. Astfel se ajunge de la un cod de 3-4000 de linii în UFS la 60000 de linii în sistemul de fișiere din IRIX 6.x, Unix-ul de la Silicon Graphics. Rețineți: pentru utilizator funcționalitatea este pînă la urmă aceeași!
Metodele care urmează arată de ce aria sistemelor de operare este atît de mult o îndeletnicire de inginerie (sau, dacă preferați, de meșteșug). Firește că nu toate tehnicile sunt aplicabile simultan, fiecare rezolvînd cîteodată o anumită clasă de probleme, dar creînd altele, socotite mai puțin importante de arhitect. Oricum, după părerea mea, chiar înșirarea tehnicilor este instructivă.
Desigur, este posibil să fi sărit din enumerare alte tehnici importante. Cei care le cunosc sunt rugați să-mi atragă atenția asupra lor, ca un viitor articol să fie mai comprehensiv.
Să mai observăm că majoritatea aserțiunilor făcute aici se potrivesc pentru sisteme de fișiere tradiționale, de gen Unix. Noi domenii de activitate, ca multimedia, tind să ceară propriile structuri de date, specializate, pentru a oferi proprietăți necunoscute de sistemele de fișiere tradiționale (de exemplu pentru reproducerea unui film video de pe disc trebuie oferită o rată de transfer constantă a informației, independentă de numărul de alte cereri la disc). Acest gen de fișiere probabil că nu este foarte bine reprezentat de curentul articol.
Să vedem cu ce material lucrăm.
Piața de discuri dure (hard-disk) la ora actuală are o creștere anuală mai mare decît cea de sisteme de calcul, de circa 60% pe an (volum de vînzări); discurile dure sunt dispozitivul dominant de memorie permanentă. Din această cauză vom discuta în acest articol despre hard-discuri în mod special (și nu despre CD-ROM-uri de pildă). Anumite dintre considerațiile pe care le facem sunt valabile numai pentru acest mediu de stocare a informației. De aici înainte cuvîntul ``disc'' înseamnă disc dur.
Figura 1 încearcă să ilustreze geometria discurilor1; în cuvinte lucrurile stau cam așa: un disc este o colecție de platane circulare pe o axă comună, fiecare avînd două capete de citire/scriere, cîte unul pe fiecare din fețe. Pe fiecare platan informația este așezată pe o serie de cercuri concentrice, numite piste (tracks) (în cercuri și nu în spirală ca la pick-up). Totalitatea pistelor de rază egală se numește cilindru (cylinder). Pentru că toate capetele unui disc sunt solidare, se află toate pe un același cilindru la un moment dat. Asta implică faptul că datele plasate pe un același cilindru se pot accesa fără a deplasa capetele, selectînd doar dintre capete pe cel activ (unul singur la un moment dat). Fiecare pistă este împărțită la rîndul ei în sectoare (sectors), care la rîndul lor sunt o colecție de octeți. Indicînd capul, pista (sau cilindrul), numărul sectorului din pistă și numărul octetului din sector identificăm unic un octet pe disc.
Discurile sunt toate sudate pe aceeași axă, și se află în mișcare permanentă de rotație (la laptop-uri ele sunt oprite după perioade prelungite de inactivitate pentru a economisi bateriile). Viteza de rotație este de aproximativ 5000-8000 de ture pe minut, depinzînd de disc. Viteza este constantă, spre deosebire de CD-uri, care se rotesc mai repede cînd se citește de la centru.
Timpul de mișcare a capetelor de citire între cilindri vecini (track-to-track seek time) este foarte mare (la scara de viteze a microprocesoarelor), și este dat de inerția mecanică a ansamblului de capete. O valoare tipică este de 3-4 milisecunde. Mișcarea capetelor între doi cilindri oarecare are o valoare medie (average seek time) de 8 milisecunde pentru discuri de vîrf. (To seek = a căuta.) Accelerarea și decelerarea sunt dominante ca durată, așa că o mișcare de 10 piste nu durează cît 10 mișcări de la pistă la pistă.
Cantitatea de informație de pe o pistă este constantă, deși pistele de la exterior sunt mult mai lungi decît cele de la interior. Asta înseamnă că densitatea informației la margine este mai mică. O tendință nouă este de a plasa informația cu densitate constantă peste tot, dar asta complică un pic calculul locului pe disc. De obicei această tehnologie se folosește pentru a ține niște blocuri ``ascunse'', de rezervă, pe pistele exterioare. Atunci cînd blocuri ale discului se strică (lucru foarte comun, de altfel), ele sunt automat ``mutate'' în blocurile de la periferie, ascunse, și cele originale sunt marcate ca defecte. Adesea această mutare este invizibilă calculatorului gazdă, fiind făcută de controlerul atașat la disc în mod transparent. (Acest lucru are consecințe nefaste dacă sistemul de operare optimizează accesul la disc bazat pe poziție.) O pistă tipică are între 32 și 64 de kiloocteți.
Iată de pildă specificațiile pentru un disc Western Digital Caviar de 3,5 inci, de ultimă oră:
| Capacitate | 2000 Mb |
| Timp mediu de căutare (seek) | 11ms |
| Viteză de rotație | 5200 rot/min |
| Cilindri | 3876 |
| Capete (2 * platane) | 16 |
| Sectoare/pistă | 64 |
| Cache intern | 256Kb |
| Rata de transfer | 16.6 Mb/s |
| Timp mediu între defecțiuni | 350 000 ore |
În momentul cînd utilizatorul indică ce octet de pe disc vrea să acceseze sunt implicate trei durate importante:
Pentru ilustrație să considerăm un transfer de 1 kilooctet, octeții transferați fiind plasați consecutiv. Cei trei timpi ar putea fi pentru discul de mai sus: căutare a pistei 11ms, întîrziere medie de rotație 1/(5200/60) * 1/2s = 5ms și timp de transfer 5/16 = 0.3ms (o pistă are 32k2, deci transferul a 1k este 1/16 din timpul mediu de rotație, sau 1/32 din timpul de rotație).
Spre deosebire de memorii și microprocesoare, creșterea performanțelor discurilor este mult mai lentă. Cele mai notabile progrese s-au înregistrat în creșterea densității de informație și viteza de rotație; în ultimii 10 ani însă timpul de mișcare a capetelor a înregistrat o scădere practic neglijabilă, și nici nu sunt semne că una s-ar produce în viitorul apropiat. Limitările mecanice sunt foarte greu de depășit.
Iată acum tehnicile folosite pentru a mări eficiența utilizării discurilor, fiecare discutată într-o secțiune separată.
Datorită faptului că accesarea locului unde informația se află pe disc este foarte costisitoare în milisecunde, un plasament bine-gîndit al informației pe disc poate aduce beneficii substanțiale.
Calculele anterioare arată că timpul de acces la informație este complet dominat de timpii de căutare (seek) și întîrziere de rotație. În acest caz este la fel de rapid să transferi o mulțime de octeți consecutivi sau unul singur; timpul plătit pentru mișcarea capului este cel dominant. Diferența de mărime este atît de importantă încît acest principiu este folosit în toate sistemele de fișiere existente (chiar și de cele care folosesc memorii flash3 în loc de discuri.
Din cauza asta toate implementările sistemelor de fișiere tratează discul ca pe o colecție de blocuri de mărime fixată, și nu ca pe o colecție de octeți. Alocarea și dealocarea, scrierea și citirea se fac toate la nivel de bloc. Valori tipice pentru mărimea unui bloc? Între 512 octeți și 8 kiloocteți.
Singurul dezavantaj al metodei este cunoscut din studiul algoritmilor de alocare dinamică a memoriei, și se numește ``fragmentare internă''. Asta înseamnă că uneori blocurile nu sunt folosite în întregime, ca de exemplu în cazul fișierelor care nu ocupă spațiu un multiplu întreg de mărimea blocului. Datorită faptului că la discuri capacitatea a crescut foarte repede în ultimii ani, iar mărimea medie a fișierelor de asemenea, spațiul pierdut prin fragmentare nu mai este considerat o problemă importantă.
În 1984 cercetătorii de la Universitatea Berkeley din California (K.M. McKusick, William Joy4, S. Laffler și L. Fabry) au publicat un articol epocal numit ``A Fast File-system for Unix'' (FFS). Acest articol arăta cum în sistemul de operare BSD (Berkeley Software Development, o variantă de Unix5) a fost implementat un sistem de fișiere mult mai rapid decît cel tradițional (UFS), care funcționa din 1974. Principala tehnică exploatată de McKusick și colegii lui pentru o dublare a vitezei a fost exploatarea ``localității''.
Intenționez să consacru un articol special managementului spațiului liber la discuri, dar pînă atunci iată esența tehnicii: sistemul de fișiere tradițional din Unix aloca blocuri libere practic la întîmplare, cum se găseau pe disc. Echipa de la Berkeley a ``spart'' discul în mulțimi de cilindri (cylinder groups) contigui, și a încercat să aloce blocuri consecutive ale aceluiași fișier (sau inod-urile dintr-un același director) în același grup de cilindri. Între cilindri din același grup timpul de căutare (seek) este apropiat de cel minim (3ms), spre deosebire de timpul mediu (11ms) între doi cilindri mai îndepărtați. De aici rezultă un beneficiu imediat. În plus, ei încercau pe baza unui algoritm complex să aloce blocul ``cel mai apropiat'' în sens temporal: blocul liber la care se ajunge prin cea mai rapidă mișcare, luînd în considerare și faptul că pe măsură ce se face ``seek'' discul se rotește.
Algoritmul lor a avut un succes instantaneu, încît schimbările propuse de ei au devenit standard, și au fost adoptate de întreaga lume Unix.
Și alte cîteva detalii secundare au contribuit la succesul FFS: blocuri de mărime foarte mare (8k față de 0.5k din UFS), ceea ce ducea la mult mai puține ``seek''-uri pentru un fișier (încăpea în mai puține blocuri), deci din nou la o eficiență sporită. Pentru a contracara efectele fragmentării interne, ei au folosit și o metodă prin care blocurile incomplet folosite sunt sparte în fragmente mai mici (1k), care pot fi folosite de fișiere diferite. Inutil de spus, algoritmii de management se complică puțin, dar viteza nu suferă scăderi considerabile.
Tehnica ``localității'' se rezumă astfel: alocă în blocuri ``apropiate'' (care se pot citi repede unul după altul; asta nu înseamnă neapărat consecutive!6) informațiile care probabil vor fi accesate consecutiv.
Un alt proiect de la aceeași universitate care a făcut vîlvă la vremea lui este cel al ``Sistemului de fișiere cu log-uri'' (Log-structured File-system, LFS pentru intimi) propus în 1991 de M. Rosenblum și J.K. Ousterhout. Vom discuta pe scurt despre acest sistem de fișiere mai jos, cînd vorbim de scrierile asincrone și folosirea cache-urilor. Performanța este obținută în LFS datorită faptului că toate scrierile se fac în felii de cîte 64 de kiloocteți (2 piste de pildă), care se scriu în blocuri consecutive, fără ``seek'' între ele (și dacă se poate, fără întîrziere rotațională).
Metoda cea mai bună de a face accese la disc este de a le evita. Pentru asta, datele citite de pe disc sunt ținute într-o memorie RAM, în speranța că vor fi refolosite. De asemenea, datele sunt citite de pe disc în blocuri, dar accesate de programe în bucăți arbitrare (poate chiar octet cu octet). O citire secvențială7 va aduce un bloc întreg la primul octet, după care va lucra direct în memorie8 Zona din RAM destinată memorării datelor de acest gen (al căror loc permanent este pe disc) se numește cache (sau memorie ascunsă)9.
Singura problemă reală cu cache-urile este că în general nu avem destulă memorie pentru a ține toate datele de pe disc, așa încît trebuie algoritmi care să arunce din date din RAM cînd nu mai e loc. Tema iese din domeniul acestui articol.
Să observăm că atunci cînd se folosește un server de fișiere (de pildă NFS -- Network File System -- într-o rețea de calculatoare, sau un server Novell) cache-ul poate fi plasat în mod logic în 3 locuri: la server în RAM, la client pe disc sau la client în RAM. Pentru rețelele locale rapide e mai eficient RAM-ul de la server decît discul de la client: o rețea este mai rapidă decît un disc!
Un cache este util deci în cazul în care informația este accesată în mod repetat. Iată în secțiunile următoare cum cache-ul se poate dovedi util în feluri diferite pentru scrieri și citiri.
Un cache funcționează în cazul scrierii pe disc astfel: un proces vrea să scrie, dar datele sunt copiate (de sistemul de operare de obicei) într-un cache, unde sunt ținute o vreme. Procesul care a scris poate însă să-și continue execuția imediat. Atunci cînd cache-ul crede de cuviință, scrie datele pe disc. Din cauză că între scrierea efectuată de proces și accesul la disc nu există nici o sincronizare (sunt practic independente), aceste scrieri ale procesului se numesc asincrone.
Un dezavantaj al scrierii asincrone este pierderea definitivă a datelor în cazul unei catastrofe survenite înainte de golirea cache-urilor. Sistemul de operare MS-DOS folosea scrieri sincrone pentru a evita astfel de situații, dar aceasta a dus și la o eficiență extrem de scăzută, care pînă la urmă i-a semnat sentința MS-DOS-ului: nu se mai produce; cînd totuși se mai utilizează, se folosesc programe (ca smartdrive) care implementează cache-uri.
Putem găsi patru beneficii ale scrierii asincrone:
O primă metodă prin care care cache-ul se dovedește benefic este că permite strîngerea mai multor scrieri laolaltă și efectuarea lor într-un singur acces. Vom vedea că sistemul de fișiere cu ``log''-uri face chiar acest lucru: toate blocurile modificate sunt scrise periodic în grup, în accese de 64k. Se economisesc astfel o grămadă de timpi de poziționare (seek) și întîrzieri rotaționale, care costă, nu glumă.
O tehnică folosită de toate driverele de disc normale este de a scrie blocurile pe disc în ordinea în care se minimizează timpul de deplasare. Astfel, cache-ul pasează permanent cereri driver-ului: vreau blocul ăsta, ia blocul ăsta. Driver-ul se întoarce asincron zicînd: ``ok, mă ocup eu, tu vezi-ți de treabă''. Astfel driver-ul poate avea (și în momentele de activitate intensă chiar are) o mulțime de cereri încă nesatisfăcute de blocuri. Atunci el aranjează aceste cereri în așa fel încît să fie cît mai puțină mișcare.
Un algoritm faimos este cel al ``liftului'' (elevator algorithm): aranjează blocurile în ordine crescătoare a cilindrilor, mișcă din capete de la cilindrul 0 la cel maxim, și scrie pe măsură ce avansezi. Algoritmul are tot felul de variante, este relativ eficient, și nici nu face vreun un bloc să aștepte prea mult pînă îi vine rîndul.
Foarte multe fișiere trăiesc un timp scurt; fișiere temporare, fișiere încuietoare (lock) există cîteodată pentru cîteva secunde. Dacă cache-ul evită scrierea acestor fișiere destul de mult timp, ar putea avea surpriza ca fișierele să dispară înainte de a le veni rîndul să fie scrise, și ca blocurile lor să fie eliberate.
Foarte adesea modificări succesive se aplică aceluiași bloc, sau chiar aceluiași octet. În cazul acesta cache-ul cumulează rezultatele tuturor modificărilor, și scrie numai rezultatul final, economisind niște accese la disc.
Al doilea beneficiu al cache-urilor se manifestă la citire. Este limpede de ce un cache este util dacă aceleași date sunt citite de mai multe ori. Paradoxal însă, un cache se poate dovedi util chiar dacă datele sunt citite o singură dată!
Un sistem de fișiere poate încerca să ghicească dinainte ce blocuri vor fi cerute în viitor de utilizatori, și să ceară driver-ului să aducă blocurile din timp. Atunci cînd aplicația face cererea de citire, datele sunt servite din cache imediat! Utilizatorul nu observă nici o întîrziere (sau o întîrziere mai mică, dacă datele sunt pe drum). Această tehnică se numește ``citire-înainte'' (read-ahead; pre-fetching).
Inutil de spus, riscul este, ca în cazul oricărui profet, de a face o prezicere eronată, care se soldează cu o citire inutilă. Vestea cea bună este că un studiu empiric asupra programelor obișnuite a observat că se pot prezice cu destul de mare acuratețe accesele secvențiale la un fișier: dacă un program a cerut primele 3 blocuri în ordine probabil va continua să le ceară și pe următoarele.
Toate sistemele de fișiere moderne folosesc această optimizare, cu destul de mult succes.
Firește, există un caz în care citirea în avans nu este cu nimic dăunătoare: cînd suntem siguri că ea va fi utilă. Sisteme experimentale pun la dispoziția programatorului apeluri de sistem speciale prin care poate indica porțiunile de fișiere pe care le va accesa în viitor.
Se fac de asemenea încercări de a crea compilatoare care să genereze automat ``indicații'' (hints) pentru sistemul de fișiere privitor la accesele viitoare, fără ca programatorul să trebuiască să abandoneze stilul obișnuit de programare.
O rudă a metodei cache-urilor folosită în cazul sistemelor de fișiere în rețea, această tehnică reduce traficul în rețea și numărul de accese la disc: mai multe cereri de scriere/citire și răspunsurile lor sunt grupate laolaltă (fie la client, fie la server) și transmise într-o bucată.
Viteza de transfer a datelor pe magistrale este mult mai mare decît cea între disc și magistrală. Limitarea ratei de transfer a discului este dată de viteza de rotație: discul Caviar de mai sus face 5200 rpm, iar la fiecare rotație poate transfera capacitatea unei piste, de 32k. Asta înseamnă o limită superioară (în absența oricăror poziționări) de 5200/60 * 32 k/sec = 2,77M/sec. (Viteza de transfer mult mai mare din specificațiile discului de mai sus poate fi atinsă cînd acesta are cache-ul propriu deja încărcat cu date.)
O idee interesantă este atunci de a folosi mai multe discuri conectate simultan la aceeași magistrală, și de a scrie informațiile în felii (stripes) care acoperă toate discurile. Astfel, folosind 3 discuri, primul bloc o să fie pe discul 1, al doilea pe discul 2, al treilea pe discul 3, al patrulea din nou pe discul 1, etc (puteți pune orice valoare în locul lui 3). Atunci fiecare disc poate transfera date din/spre memorie la viteza maximă a magistralei folosind propriul cache, de pe unitatea de disc, după care poate scrie cache-ul pe disc la o viteză mult mai mică, în timp ce vecinii săi se ocupă de celelalte blocuri.
Pentru că acolo unde ai trei aparate probabilitatea de defecțiune crește de mai mult de trei ori, în general tehnica de striping se combină cu una de redundanță (ideea este ca atunci cînd un disc se strică să nu devină toate inutilizabile). Cea mai folosită metodă este de a avea un al patrulea disc, pe care se află calculată paritatea (``sau exclusiv'') a celorlalte trei. Astfel, dacă un disc se strică, informația de pe el se poate reconstitui integral folosind celelalte 3 discuri (folosind proprietatea funcției paritate: dacă A + B + C = P (notînd cu ``+'' sau exclusiv), atunci B = A + C + P, deci discul B se poate reconstrui folosind A, C și discul de paritate P). De aici vine și numele dispozitivelor, RAID: mulțime redundantă de discuri independente.
Două cuvinte în plus despre această fascinantă metodă, despre care poate vom reveni într-un articol separat:
Cu toate aceste slăbiciuni, calitățile schemelor RAID depășesc defectele, așa încît este de așteptat ca utilizarea lor să devină din ce în ce mai răspîndită. Dacă controlerul de RAID are și o cantitate suficientă de NVRAM pentru a implementa un cache mare, atunci șocul scrierilor mici poate fi oarecum absorbit de acesta, utilizatorii ne-trebuind să aștepte calculul parității, percepînd deci o creștere substanțială de viteză (datorită paralelismului accesului la discuri).
În această secțiune vom arunca o privire rapidă asupra sistemului de fișiere bazat pe ``log''-uri LFS, citat puțin mai sus. Arhitectura sa este oarecum revoluționară, diferind substanțial de sistemele de fișiere clasice (UFS, FFS).
Tehnica ``log''-ului este împrumutată din bazele de date. Log-ul (în română o traducere aproximativă ar fi ``înregistrare'') descrie modificările făcute datelor. Astfel, în sistemul de fișiere bazat pe log, în loc să modifici fișierul, scrii un nou bloc (în log) în care zici: ``modific fișierul cutare aici cu atît''. Fișierul va subzista în forma originală, alături de înregistrările din log. În acest fel putem vorbi de versiuni ale datelor: fiecare nouă scriere în log produce o nouă versiune, care coexistă cu cele vechi, ocupînd un loc diferit pe disc. Dacă vrei să afli ultima valoare, citești ultima modificare.
Care e șpilul? De ce, adică, ar fi metoda asta eficientă? Pentru că avînd libertatea de a face scrierile oriunde (și nu în locurile unde fuseseră plasate blocurile inițial), poți alege să scrii toate blocurile consecutiv, făcînd foarte puține deplasări ale capului! În felul acesta se cîștigă o grămadă de timp.
Înainte de a vă entuziasma de ideea aceasta atît de simplă, să observăm și reversul medaliei: citirile trebuie să ia de pe disc blocurile din locurile în care se află, deci nu vor beneficia probabil de alocarea contiguă a blocurilor la scriere (în sensul că vor cauza la fel de multe deplasări de capete ca în schema UFS). LFS presupune deci că traficul dominant spre disc este de scrieri; pentru ca acest lucru să fie adevărat cache-ul de disc trebuie să fie foarte mare și cererile de citire de date trebuie să ia adesea datele din cache.
Un al doilea dezavantaj al acestui sistem de fișiere este generarea continuă de noi blocuri. Ce se întîmplă cu versiunile vechi? După ce discul a fost ocupat în întregime (ceea ce nu durează prea mult), de unde se mai obține spațiu suplimentar pentru scrieri, care trebuie să fie și contiguu (dacă spațiul liber este fragmentat am pierdut toate avantajele scrierii mari, pentru că trebuie să facem din nou toate deplasările de cap)?
Pentru acest scop sistemele de fișiere bazate pe log (LFS) au nevoie de un compactor care elimină versiunile vechi ale datelor (garbage collection) și strînge blocurile utilizate laolaltă. În general acest compactor funcționează ca un proces separat care traversează structurile de date ale discului atunci cînd spațiul liber a scăzut sub o anumită cantitate, strîngînd laolaltă blocurile utilizate și rescriindu-le. Activitatea compactorului este o sursă importantă de trafic spre disc, scăzînd dramatic din eficiența sistemului de fișiere.
Studii detaliate au fost făcute pentru a determina dacă schema LFS este mai bună decît cea a FFS, dar un rezultat clar în favoarea unuia dintre ele nu a fost obținut. Fiecare dintre ele se comportă mai bine în anumite condiții și pentru un anumit tip de trafic (de exemplu LFS cîștigă la scriere). Tehnici de gen LFS sunt folosite în sisteme comerciale, cum ar fi cel citat mai sus, Xfs, din sistemul IRIX, în care se folosesc log-uri numai pentru directoare, dar nu și pentru fișierele propriu-zise.
Un mare avantaj al log-urilor este reconstrucția extrem de rapidă a discurilor după o cădere a calculatorului. Pentru că sistemele de fișiere tradiționale (UFS, FFS) fac tot timpul modificări în toate zonele, o oprire subită a calculatorului poate lăsa sistemele de fișiere într-o stare incorectă, fiindcă informațiile din cache nu au fost salvate. Depistarea și corectarea acestui gen de defecte cere programe foarte sofisticate (fsck). Sistemele bazate pe log-uri în schimb au toate modificările recente la sfîrșitul log-ului, deci sunt foarte ușor de reparat. (Atenție: pierderi de informație se petrec în ambele cazuri, pentru că nimeni nu poate reconstitui informația ne-salvată din cache; problema care se pune este de a face din nou funcționale sistemele de fișiere.)
Aceste metode folosesc mai multe discuri beneficiind, ca în cazul RAID, de transferuri paralele spre controlere, care pot apoi face scrierile simultan.
Mai curînd o variație a schemei LFS, această îmbunătățire folosește un disc pentru scrierea log-ului, compactorul mutînd informațiile ``vii'' pe un alt disc, unde informația care trăiește mult timp (de pildă fișierele care se schimbă rar, cu executabile) se va strînge după o vreme.
Autorul acestui articol a transformat sistemul de fișiere din Linux numit ext2 (care este de tip FFS) pentru a folosi un disc pentru directoare și un altul pentru fișiere10. În felul acesta cache-ul poate programa scrieri sau citiri simultan pe ambele discuri. Au fost măsurate cu teste simple creșteri de performanță de 30% față de folosirea unui singur disc.
Un alt potențial avantaj al unei astfel de scheme este acela că se pot implementa politici de alocare a blocurilor speciale pentru directoare și fișiere obișnuite, care să exploateze caracteristicile speciale ale accesului (de exemplu directoarele tind să fie mici și nu ``scad'' niciodată).
O altă idee interesantă: prea multe cereri la un server? Atunci folosește mai multe servere, fiecare răspunzînd la o fracțiune din cereri. Sunt, firește, două posibilități: ori îi dai fiecărui server niște date de care e singur responsabil, ori pui aceleași date pe toate serverele. A doua metodă se numește replicare, pentru că are mai multe copii (replici) ale datelor. Clienții vor face cererile la servere diferite, și fiecare server va avea o coadă de cereri de satisfăcut mai scurtă, deci un timp de răspuns mai bun.
Cititorul ager a observat imediat că schema are iarăși dezavantaje: cu citirea totul e bine, dar ce faci dacă cineva vrea să modifice ceva? Trebuie să faci scrierea de mai multe ori! Există o serie întreagă de tehnici pentru a modifica fișiere replicate, dar ne vom mulțumi să le enumerăm; problemele ridicate sunt mult mai mari decît par la prima vedere.
Replicarea fișierelor de fapt este un fenomen foarte întîlnit, dacă stăm să ne gîndim bine: de fiecare dată cînd avem un sistem de fișiere în rețea, care poate fi accesat de mai mulți clienți, fiecare client va tinde să aibă în cache-ul lui propria lui copie a (unora) din fișiere. Este tot un caz de replicare, care pune aceleași probleme ale modificării fișierelor. Sistemele comerciale (NFS de la Sun, AFS -- Andrew File System -- de la compania Transarc și universitatea Carnegie Mellon) rezolvă fiecare problema replicării datelor în felul lui (mai mult sau mai puțin satisfăcător). Fără a intra în detalii, să reținem și replicarea ca o tehnică posibilă pentru creșterea eficienței.
Structurile de date de pe disc sunt foarte complexe: un arbore de directoare, blocurile unui fișier sunt grupate într-un arbore dezechilibrat, blocurile libere într-un fel de listă stufoasă sau un ``bitmap'', etc. Pentru a deschide un fișier trebuie traversate o mulțime din aceste structuri, accesînd poate zeci de blocuri. Construirea unor indexuri eficiente (idee împrumutată din tehnologia bazelor de date) poate mări foarte mult viteza de acces la disc.
Arbori, tabele de dispersie (hash tables), arbori B+ sunt folosiți pentru a crește performanța căutării, mai ales în cazul fișierelor și discurilor foarte mari. De asemenea, structurile de date din memorie, care descriu fișierele deschise și cache-urile (cache-ul blocurilor din memorie, cache-ul numelor de directoare, cache-ul inodurilor din memorie, etc.) sunt organizate după astfel de structuri de date, cu căutare rapidă (de exemplu pentru a verifica dacă un bloc se găsește în cache se folosește de obicei o tabelă de dispersie și nu căutare binară).
Activitatea unui server de fișiere are perioade febrile și zone de repaos. Acestea din urmă pot fi folosite pentru a programa activități auxiliare, care sunt utile, dar care nu trebuie să consume din timpul util. Candidați sunt: compactarea log-urilor, calculul parității în sisteme RAID, reconstrucția discurilor defecte în sisteme RAID, compresia fișierelor, compactarea spațiului liber, defragmentarea fișierelor (pentru citire rapidă secvențială).
În general în sistemele de fișiere tradiționale toate operațiile se desfășoară pentru că sunt cerute de cineva. În alte arhitecturi, gen LFS, există o serie de activități pentru care momentul execuției nu este precis determinat (compactarea log-ului la LFS). Toate activitățile citate mai sus, care se pot face în timpul liber, sunt de acest gen, iar cea mai eficientă implementare a lor este de a construi un thread (de preferință chiar în interiorul nucleului, ca să nu trebuiască să facă apeluri de sistem costisitoare) pentru fiecare din ele.
Ajungem la o tehnică foarte interesantă, care se bazează pe o observație destul de subtilă. Pentru aceasta trebuie să aruncăm o privire la momentul în care se alocă blocuri fișierelor. Un nou bloc se alocă atunci cînd se scrie în el pentru prima oară. Să presupunem că un utilizator cheamă un apel de sistem write() pentru a scrie ceva la într-un fișier, începînd de la octetul cu numărul offset_curent (valoarea acestuia a fost fixată de un apel lseek() anterior). Codul acestui apel de sistem arată cam așa într-un pseudo-cod C:
write(int fisier, char * sursa, int marime)
{
while (marime) {
bh = aloca_bloc(fisier, offset_curent);
copiaza_date(sursa, bh, MIN(marime, marime_bloc));
marcheaza_modificat(bh);
offset_curent += marime_bloc;
marime -= marime_bloc;
sursa += marime_bloc;
if (marime < 0) marime = 0;
}
}
(Codul este foarte simplificat: în mod normal în while se cheamă o funcție cauta_bloc(), care va aduce blocul care conține offset_curent, sau va chema ea însăși aloca_bloc() dacă acest bloc nu a fost încă alocat; în plus am asumat că datele sunt aliniate și scrierea se face de la un început de bloc; codul real este ceva mai complicat, însă acesta ilustrează perfect ce ne interesează.) Funcția aloca_bloc() caută un bloc liber pe disc și alocă simultan un bloc în cache pentru acel bloc; rezultatul întors este un bloc de cache numit bh, pe care cache-ul îl va salva pe disc asincron.
Observația interesantă este: chiar dacă avem o scriere de un megaoctet, blocurile sunt alocate unul cîte unul. Asta înseamnă că s-ar putea ca blocurile să nu fie unul lîngă altul, căci rutina de alocare aloca_bloc() nu are idee despre blocurile alocate anterior.
În plus, rutina de alocare trebuie să parcurgă structurile de date aflate pe disc, ori această operație este blocantă: pînă se citește structura de date de pe disc procesul curent este oprit și un altul se execută. Asta poate cauza interclasarea alocărilor blocurilor pentru două apeluri simultane write(): primul proces alocă un bloc, se blochează pînă structurile sunt citite, al doilea proces începe să se execute și alocă alt bloc, se blochează, dar primul termină și cere un al treilea, și tot așa.
Dacă implementarea lui aloca_bloc() extrage pur și simplu blocuri dintr-o listă de blocuri libere rezultatul va fi că blocuri succesive dintr-un fișier vor fi plasate pe disc cum vine la mînă, fără nici o relație între ele. Paradoxul este aceste: deși este clar de la început de cîte blocuri este nevoie (marime/marime_bloc), rutina de alocare obține blocurile unul cîte unul, și atunci ele nu sunt neapărat consecutive! (Plasarea în blocuri consecutive face accesul secvențial la fișier mult mai eficient, mai ales în combinație cu citirea anticipată.)
Se pot folosi patru scheme pentru a ocoli această deficiență a alocatorului:
O metodă interesantă este de a schimba complet unitatea de alocare a discului din blocuri cu mărime fixă în cantități de mărime variabilă (dar nu oricît de mici), numite extents (întinderi?). Astfel la apelul de sistem write() se alocă întreaga cantitate de spațiu pe disc de la început, după care este scrisă, dacă se poate dintr-o bucată. Aceasta complică codul alocatorului, dar nu este nicidecum o problemă nefezabilă.
De fiecare dată cînd trebuie să aloci un bloc, alocă și cîteva blocuri imediat consecutive pe disc, în eventualitatea creșterii fișierului. Această schemă este folosită cu succes în sistemul de fișiere din Linux, ext2.
Dacă fișierul nu mai crește, sau nu crește secvențial, blocurile pre-alocate sunt eliberate.
Nu se alocă pe disc blocurile pînă cînd nu vine momentul golirii cache-ului. Scrierea alocă blocuri doar în cache, iar algoritmul golirii cache-ului studiază pentru fiecare fișier cîte blocuri trebuie alocate pe disc și face această alocare. Această tehnică este folosită în sistemul de operare IRIX.
Această tehnică este o optimizare întîlnită în anumite implementări ale FFS: alocarea merge ca în codul de mai sus, însă procedura de golire a cache-ului încearcă să ``mute'' blocurile dacă ar fi util: blocuri consecutive din același fișier sunt puse contiguu dacă se poate.
Sistemul de fișiere este un serviciu oferit aplicațiilor, și poate fi plasat în mai multe locuri: într-o bibliotecă de funcții (foarte rar), în nucleul sistemului de operare sau într-un proces separat (server). Fiecare metodă are avantajele și dezavantajele ei, iar în anumite configurații speciale fiecare poate fi mai eficientă.
O încercare notabilă este cea de a distribui serviciul cît mai mult, în așa fel încît să nu existe o singură autoritate responsabilă cu majoritatea operațiilor. Un proiect foarte interesant în curs de desfășurare la universitatea Carnegie Mellon se numește ``Discuri sigure legate la rețea'': Network Attached Secure Disks (NASD). Ideea este de a avea o rețea locală rapidă (ATM, Fiber Channel, etc.) care leagă multe calculatoare client cu și mai multe unități de disc inteligente. Clienții folosesc serverul de fișiere numai pentru a afla care sunt discurile care conțin fișierele și pentru a obține o autorizație de acces, după care transferul de date se face direct între clienții interesați și discurile cu informație, fără a mai implica serverul nicicum.
Comparați această tehnologie cu cea tradițională, în care serverul, un proces obișnuit, trebuie să citească discul asociat în memorie și să trimită apoi imediat rezultatul pe rețea: pe lîngă faptul că o singură autoritate face toate operațiile, deci este foarte încărcată, se petrec o mulțime de copieri inutile; sistemele moderne în general nu oferă facilități de genul: ``trimite de pe disc direct pe rețea'', ci doar de genul ``citește de pe disc în memorie'' și ``trimite în rețea din memorie.'' Figura 2 arată diferențele între mersul informației în cele doua arhitecturi. Pentru citirea de date în formula client-server pașii sunt (scrierea este asemănătoare):
Pașii 4, 5, 6, 7, 8 copiază o cantitate mare de date dintr-un loc într-altul. Orice citire va trece prin această secvență de operații.
Pe cînd în NASD o citire trece prin următorii pași:
Transfer de date se face numai în pașii 9 și 10. Pașii 1, 3, 4, și 6 pot conține criptare/decriptare, care este o operație relativ costisitoare. Odată obținută autorizația clientul poate repeta de oricîte ori dorește pașii 7-10 fără a mai interveni pe lîngă server.
Discul trebuie să fie ``inteligent'' pentru că trebuie să:
Programe care dublează capacitatea discului sunt oricui familiare din MS-DOS. Un avantaj neevident al acestor programe este că reducînd cantitatea de date scrise pe disc reduc și timpul necesar transferului.
Dintre dezavantajele metodei: este greu de estimat spațiul ocupat după compresie, deci alocarea este mai dificilă, compresia este cu atît mai eficientă cu cît manipulează o cantitate mai mare de date, dar decomprimarea unui întreg fișier pentru a citi ultimele două linii este o irosire, compresia însăși consumă mult timp de procesor.
