Reliable File System

• Schema spodní vrstvy file systému
• Struktura dat na disku
  • Master Boot Record
  • Boot Record
  • The Second Boot Record
  • Statistika grup
  • Oblast ( myšlena partition )
  • Grupy
• Fyzické chyby media a jak jsme se s nimi vyrovnali
• Striping
• CacheMan = Cache + Swap, package, konzistentní zápisy
  • Čtení
  • Zápis
  • Velikost cache, swapovací oblasti
  • Commit package
  • Byly tu i jiné možnosti...
• TRANSAKCE a LOGY : *.ALF, *.NOT, *.OKA, *.HLP, *.CML
  • *.ALF - ALLOC/FREE log
  • *.NOT - NOT PackageID Alloc/Free log
  • *.OKA - OK Allocated/Released log
  • *.HLP - HeLP Alloc/Free undo log
  • *.CML - Commit undo/redo log
• Co se děje při inicializaci RFS...
• RECOVERY aneb jak se opravuje pomocí logů po pádu systému
• Co se děje při zavírání RFS...

• Dirty flag oblasti: je TRUE pokud oblast nebyla čistě uzavřena. Tento flag se kontroluje při startu systému. Pokud je oblast dirty nastartuje se záchranná a kontrolní utilita. Při uzavírání systému se nastavuje na FALSE.
• Adresa FNODU root recordu v oblasti ( adresa logická, relativní od začátku oblasti ).
• Počet grup v oblasti.
• ...

• Grupa se skládá z bitmapy ( 1 sektor )a datových sektorů ( 4096=512*8 sektorů ). Bitmapa informuje o obsazení sektorů v grupě: BIT: 1..sektor je volný, 0..sektor je plný. Umístěna je u sudých grup na počátka a u lichých na konci => tím vzniká souvislý datový prostor délky 4MB.
  
• Čísla týkající se grup:
  Datová kapacita grupy v sektorech: 12b sektorů ... 4k * 512B = 2MB
  Počet grup v oblasti: 20b ... 1M grup
  Velikost grupy: 4k datových sektorů + 1 sektor bitmapa
• Poslední grupa v oblasti vyjde zpravidla neúplná. Při formátování ji vytvořím - vytvořím hlavičku, verify sektory, do hlavičky poznačím sektory které v grupě chybí ( za koncem oblasti ) jako plné. Později ji tedy lze použít. Nyní je, ale implementace tak ová, že se poslední grupa nepoužívá vůbec. Proč ji nepoužívám:
  1. Při každém zápisu či čtení musí být test zda to není poslední grupa. Do té se přistupuje jinak - ať lichá či sudám má bitmapu vždy na počátku - velmi to zpomalovalo.
  2. může mít velikost do 1 do 4096 sektorů a tak se mi může stát, že budu mít pouze sektor na bitmapu. Kdybych ji chtěl používat na nějaké servisní informace opět nevím co vše by se tam dalo uložit.
• Jak se vyrovnávám s BADSEKTORY...
  • Vyskytnou-li se při formátování: sektor se označí v hlavičce bitmapy jako zaplněný. Vyšší vrstva si ho nealokovala ... nemůže tedy o něj požádat a nižší vrstva si myslí, že je plný a tak ho nikomu nedá ... tak se sektor nepoužívá.
  • Vyskytnou-li se za běhu: řeknu vyšší vrstvě, že sektor se nepodařilo zapsat a já ho označím jako plný. Vyšší vrstva už to vyřídí ( pokusí se sektor zapsat jinam: naalokuje si jinde místo a zapíše ho tam ). Když to nastane při readu postupuje se obdobně p ouze nahoru dodám co jsem na třikrát přečetl ( většina bude asi špatně protože CRC nesedlo, ale je lepší dodat něco než nic ).
• Co se týče alokace sektorů v grupě:
  • Vyšší vrstva má možnost si říci za kterým sektorem a v které grupě má alokovaná oblast začínat - spodní vrstva se jí snaží vyhovět ( CacheManAllocateSector() CACHEMAN.H ).
  • PŘEDALOKOVÁVÁNÍ nechávám na vyšší vrstvě - ta si řekne o víc než chce a já jí takovou oblast dodám ( sám však nevím, jestli všechno využije nebo si syslí do budoucnosti ).
  • HLEDÁNÍ GRUPY VHODNÉ PRO ALOKACI: k dispozici je statistika zaplnění celé oblasti + jednotlivých grup ( viz. výše ). Pokud caller specifikoval, kde by měla alokovaná oblast začínat tak skouším hledat od tohoto sektoru v grupě dále. Pokud nic nenaj du prohledám grupu od začátku až po specifikované místo. Pokud neuspěji ani teď hledám v následující grupě ( a tak eventuelně projdu všechny grupy oblasti ). Při hledání se hojně využívají statistiky ( než načtu bitmapu grupy ze statistiky zjistím zda to má vůbec smysl).
    Pokud caller nespecifikoval, kde má alokovaná oblast začínat - vystřelím do grup náhodně. A pak při hledání postupuji výše uvedeným způsobem. Funguje to celkem spolehlivě. Důvod proč to provádím je ten, že se file system zaplňuje rovnoměrně ( nealokuje s e od počátku - data jsou roztroušena po disku ) a tak se snižuje pravděpodobnost fragmentace. Jakmile je místa méně, tak procházím statistiku a hledám podle ní. Velikosti děr v grupách si nepamatuji. Udržování takové informace by bylo jak časově tak pamě ťově velmi náročné a podle mého názoru by se to ve výsledku ani nevyplatilo. Já v nejhorším případě musím navštívit více grup. Díky alokační strategii uvedené výše a statistikám se docela slušně orientuji a souvislé prázdné oblasti se zpravidla najdou. S e zaplňováním filesystemu se vše samozřejmě zpomaluje.
    Alokace provádí funkce CacheManAllocateSector() z CACHEMAN.H ).
• Co grupy daly a co vzaly...
  • Data jsou soustředěna více u sebe. Grupy jsou menší a tak pokud ztratíme jednu grupu nepřijdeme o tolik informací.
  • Použití grup umožnilo zvolit jako alokační jednotku sektor ( ve smyslu úspornosti režijních informací ) a tím se zmenšil slack space.
  • Udržování grup = bitmap něco stojí.

• stripovací jednotka je oblast - nemusí to tedy být celý fyzický disk. Swapovací oblasti tedy nepodléhají stripingu a systém zbytečně nebrzdi.
• stripovací oblasti musí být stejně velké
• stripovacích datových oblastí může být teoreticky libovolný počet ( paritě je to jedno ).
• overhead: (1/počet datových disků+1)*100 procent. Čím více disků, tím menší overhead.
• při výpadku jednoho z datových disků se dopočte jeho obsah z ostatních datových disků a disku paritního.
• při výpadku paritního disku se nikam nepočítá parita - systém je bez zabezpečení.
• výpadek 2 a více disků. Vypadá to sice nepravděpodobně, ale stát se to může. Disky mohou začít fungovat odděleně. Obsah 2 disků je ztracen, obsah ostatních disků je zachován.
• BADSECTORY na discích a jejich souvislost se stripingem.
  • BADSECTOR na datovém disku: obsah sektoru se dopočte z ostatních datových disků a disku paritního. Do vyšší vrstvy se ohlásí, že se sektorem nelze pracovat, ale že data byla zachráněna. Opravená data se pošlou do vyšší vrstvy, v bitmapě se sektor označ í jako full. Parita se nyní počítá tak, že pokud sektor nelze pro výpočet parity přečíst, nahradí se pro výpočet jeho obsah 0x000... a takto se parita vypočte.
  • BADSECTOR na paritním disku. Celé patro ( datové sektory ze kterých se parita počítala ) se postupně musí prohlásit za neplatné. Prázdné sektory se označí jako full a poznačí se, že jsou bad ( i když to není pravda ). Použité sektory: kdykoli si vyšší vr stva řekne o data z tohoto levelu, ohlásí se, že datový SEKTOR je bad ( i když to není pravda ) a že data byla zachráněna. Tím se postupně data z postiženého levelu přesunou jinam.
    Nic lepšího jsem nevymyslel. Podle mého názoru je nesmysl po výpadku paritního sektoru dohledávat, kterému filu sektor patří a přealokovávat ho - to by bylo časově neúnosné. Takto se ale může stát, že se nepoužívané sektory nepřesunou.

 //---------------------------------------------------------------------------------
 //- STRIPING STRUCTURES - STRIPING STRUCTURES - STRIPING STRUCTURES -
 //---------------------------------------------------------------------------------

 struct _StripItem : PriQueueItem
 {
  byte  Device;
  byte  Party;
  dword Begin;  // logical HD sector 0..
  dword End;    // logical HD sector 0..
  dword Number; // End-Begin+1 ( data devices )
  byte  Type;   // PARITY_STRIP || DATA_STRIP - used for table on disk
 };

 typedef struct far _StripItem StripItem;



 class far DataStripsQueue : public PriQueue
 {
  public:

   DataStripsQueue( void ):PriQueue() { return; };
    void      Insert( StripItem far *Item  );

    StripItem far *FindFirstParty( void );
    StripItem far *FindNextParty( StripItem far *Actuall );
    bool      IsInStripingArea( byte Device, dword Logical );
    void      Show( void );
    word      DeleteParty( byte Device, byte Party );

    word      WriteSingleTable( byte Device, byte Party );
    word      WriteTablesToPartys( void );
              // these two functions would be methods of StripSession
              // but here is easier implementation

    bool      IsStriped( byte Device, byte Party ); // checks ParityHD too
    word      WriteSingleOffTable( byte Device, byte Party );
    word      WriteOffTablesToPartys( DataPartysQueue far * DirtyDataPartys );

   ~DataStripsQueue();
 };



 struct far _StripSession
 {

  byte StripingIs;              // ON / OFF

  DataStripsQueue DataHDs;      // data HDs queue

  StripItem       ParityHD;     // parity HD

 };

 typedef struct far _StripSession StripSession; // static structure in stripe.cpp

word ReadLogicalSector( byte Device, dword Logical, void far *Buffer, byte Number )
// this function is used by upper level
{
 #ifdef DEBUG
  printf("\n READing sector %lu... ", Logical );
 #endif

 if(
     StripingSession.StripingIs==ACTIVE
     &&
     StripingSession.DataHDs.IsInStripingArea( Device, Logical )
   )
 {
  #ifdef DEBUG
   printf(" STRIPing version...", Logical );
  #endif

  return STRIPReadLogicalSector( Device, Logical, Buffer, Number );
 }
 else
 {
  return CLASSICReadLogicalSector( Device, Logical, Buffer, Number );
 }
}

• NOTDIRTY položky se dealokují.
• DIRTY položky se ukládají na swap a ponechávají se v paměti ( při jejich zápisu do filu se totiž později UŠETŘÍ jeden read - nemusí se číst ze swapu, ale zapíšou se rovnou z paměti. Tento postup je korektní, protože pokude vypadne proud tak se po res tartu ze swapu dočtou... ). Jejich seznam se zapisuje do logu.

1. Docházelo by k velké fragmentaci dat. Se zaplňováním file systemu by už data nebyla u sebe ( připomínám, že horní vrstva si může říci za kterým sektorem chce nové sektory naalokovat, spodní vrstva se potom snaží alokovat co nejblíže tomuto sektoru ), natož v té samé grupě. Ve výsledku by to, podle mého názoru, bylo méně výkonné než poměrně rychlé souvislé zápisy ( méně seekování ).
2. Swapovalo by se mezi data
3. Problém by šel mnohem hůře rozdělit na horní a spodní vrstvu tak jak je tomu nyní. Spodní vrstva by totiž musela hrabat ve strukturách vrstvy horní a vice versa.

// Log structure:                                                 Size:  Off:
//
// LOG_BEG_TRANSACTION  ( 0 Alloc, 1 Free )                        8      0
//
//  LOG_BEG_WR_BMP                                                 8      8
//    write_to_log   GroupID                                       4      16
//    write_to_log   Logical                                       4      20
//    write_to_log   LogicalInBmp (0-4095)                         4      24
//    write_to_log   Number                                        2      28
//    write_to_log   Bitmap                                        512    30
//   LOG_CHECKPOINT                                                8      542
//    write_to_party Bitmap                                        ..
//  LOG_COM_WR_BMP                                                 8      550
//
//  LOG_BEG_WR_GRPSTAT                                             8      558
//    write_to_log   OldGrpFreeSpace                               2      566
//   LOG_CHECKPOINT                                                8      568
//    write_to_party NewGrpFreeSpace                               ..
//  LOG_COM_WR_GRPSTAT                                             8      576
//
//  LOG_BEG_WR_SCND_BOOT                                           8      584
//    write_to_log   OldPartyFreeSpace                             4      592
//   LOG_CHECKPOINT                                                8      596
//    write_to_party NewPartyFreeSpace                             ..
//  LOG_COM_WR_SCND_BOOT                                           8      604
//
//  LOG_BEG_WR_OKA                                                 8      612
//    ( call function ... which writes it transactionaly to OKA )  ..
//  LOG_COM_WR_OKA                                                 8      620
//
// LOG_COM_TRANSACTION                                             8      628
//                                                              ---------
//                                                        Total:   636

 typedef struct
 {
  dword  Record_Beg;    // ALLOC_RECORD || FREE+RECORD
   dword  State;        // NORMAL_STATE || ROLLBACKED_STATE
   dword  Logical;
   word   Number;
   dword  GroupID;
   dword  LogicalInBmp;
  dword  Record_End;    // OKA_RECORD_END
 }
 OkaRecord;                     // sizeof()=26

// Structure of CML record:
//
// TypeOfRecord  // CACHE_INTERVAL || NOT_LAST_RECORD ( SWAP ) || BEGIN COPY
//  Device;             // 0, ..
//  Party;            // 1, ..
//  SwapDevice;
//  SwapParty;
//  Logical;
//  LogicalSwap;
//  Number
//
//
// Structure of CML log file:
//  Type
//   CACHE_INTERVAL     // intervals moved in pack commit from cache to swap
//   ..
//   CACHE_INTERVAL     // intervals moved in pack commit from cache to swap
//   NOT_LAST_RECORD    // intervals in pack commit time on swap
//   ..
//   NOT_LAST_RECORD    // intervals in pack commit time on swap
//   BEGIN_COPY         // checkpoint: all data on swap, begin of copy
//                      // from swap party to data party

• Jako první se vyhledají všechny *.HLP logy ( které mají stejnou strukturu jako *.ALF ). Tyto logy se generují, když se provádí rollback OKA logu. HLP log se vytvoří a musí být kompletní. Po jeho kompletním vygenerování se přejmenuje na *.ALF a za volá se na něj funkce UndoAlfLog() z RECOVERY.CPP ) , která provede rollback jednoho OKA recordu z *.OKA logu ( to vše se provádí v rámci rollbacku OKA filu - NE NYNÍ - vyjasňuji pouze situaci vzniku HLP logu ). Zde se vš echny HLP logy smažou. Mohu to udělat protože budou v pozdější fázi recovery vygenerovány znovu. Ještě bych rád ujasnil, že pokud někde zůstane HLP log, znamená to že byl sice vygenerován, ale nebyl přejmenován a nemohlo se tedy ani začít s jeho roll backem - ničeho se nemusím bát když ho mažu.
• Nyní se vyhledávají *.NOT logy. Tyto logy jsou používány funkcemi pro alokaci a uvolňování sektorů operací, které nejsou cacheovány. Používají se například při práci s logy a s odkládacími oblastmi. Swap je na konci recovery naformátován takže o t en se nemusím starat. Ale misto alokované/uvoněné v datové oblasti musí být uvedeno do původního stavu - provede se tedy rollback NOT logu. Protože nebyla šance, jak změnu zaevidovat v FNODEu, protože než se operace skončila systém se složil. Kdyb y jsem rollback neprovedl vzniky by mi ztracené sektory, které by nikomu nepatřily nebo naopak obsazené sektory, které by byly v bitmapě označeny jako prázdné.
• Následuje vyhledání *.ALF logů jejich rollback a probublání skrz ně do jejich OKA filu ( z kterého byly volány ). Při rollbacku ALF file probublá do OKA a tam označí sobě odpovídající record jako rollbacked. Vše se provádí tak, aby v případě, že d ojde ke crash nyní v době opravy se mohlo vše dokončit ( idempotence rollbacku ALF logu je známa ). Rollback ALF logů uvádí do konzistentního stavu ostatní log fily. Tím je myšleno to, že už v nich nejsou zlomky nějakých recordů, ale recordy celé - recor dy jsou v nich buď typu commited nebo rollbacked.
• Na řadě je oprava pomocí CML logů. Ty se vytvářejí v průběhu commitu jak bylo popsáno výše. Opravu pomocí CML logů provádí RecoverUsingCml() z RECOVERY.CPP
  (i) pokud CML obsahuje magic BEGIN_COPY - provede se redo ( pokud došlo někdy dříve ke crash během této opravy může se stát, že se udělá některá z operací na swapu dvakrát, ale to nevadí , protože swap se v zápětí reformátuje ). OKA log tohoto package se smaže ( pokud se tak již nestalo, protože je jistota, že místo na swapu bude použito ).
  (ii) pokud CML magic BEGIN_COPY neobsahuje - musí se provést undo. To znamená, že CML se smaže. Protože některá data jsou na swapu a některá ne a swap se reformátuje. Musí se však provést rollback OKA logu odpovídajícího package, protože by v datové obla sti zůstalo místo na které se se volalo alloc/free a nebude využito.
  
• Teď už zbyly v oblasti pouze OKA logy. Na tyto OKA logy musí být provedena operace ROLLBACK. Tu provádí funkce RollbackOkaLog() z RECOVERY.CPP. Ta funguje takto:
  Poslední záznam v OKA logu nemusí být analyzován, protože byl označen jako ROLLBACKED při undo korespondujícího ALF logu. Zbývá tedy analyzovat zbývající, již kompletní recordy OKA logu. Recordy se čtou od zadu logu směrem k počátku. Pro každý record se vygeneruje ALF log. To se udělá tímto způsobem: nejdříve se vygeneruje HLP log funkcí GenerateHlpLog() z RECOVERY.CPP. který je potom přejmenován na *.ALF. Je to uděláno takto protože chci aby ALF byl vždy kompletní. Jestliz e se system složí před rename - HLP file se smaže. Jestliže, se systém složí po rename vím, že recovery ALF zpracuje jako první, dále vím, že v oblasti může být nejvýše jeden ALF log ( ten můj ) a také vím, že provedení rollbacku nad logem ALF je idempot entní -> vše je OK, po crash lze vklidu pokračovat v rollbacku.
  Zpět ke zpracovávání recordů. Record se načte, podívám se na magic: jestliže je rollbacknutý, vezmu načtu předchozí, jestli že je NORMAL zpracuji ho. Jestliže je typu ALLOC vygeneruji alloc HLP log, jestliže je typu FREE vygeneruji free HLP log. Přejmenu ji HLP log na ALF. Zavolám UndoAlfLog() která provede rollback za mě. Označím record v OKA jako rollbacked. Smažu OKA log.