Gsf.hhg.to

Gagnagrunnar eru geymdir á diskum. Diskar vinna með blokkir (512 bæti). Blokk erminnsta einingin í samskiptum við disk.
Diskur heldur utan um auka bókhald, m.a. villukóða (checksum) fyrir hverja blokk.
Villukóði uppfærður eftir að blokk er skrifuð.
Þrjár mögulegar útkomur þegar blokk er skrifuð á disk: 1) ekkert skrifað, 2) alltskrifað, 3) eitthvað skrifað (og villukóði rangur!) Villukóði kemur upp um hálfkláraðar breytingar. En hvernig getum við bjargað okkurúr slíku ástandi? Eldri gögn í blokkinni eru töpuð.
Hvað ef við viljum uppfæra margar blokkir samtímis og fá sama eiginleika (allt eðaekkert) ? Áreiðanleg kerfi:
Hvernig er hægt að smíða áreiðanlega gagnageymslu úr óáreiðanlegum einingum(unreliable components) ? Atómískar aðgerðir:
Hvernig er hægt að framkvæma atómíska breytingu á gögnum þegar þau hvílaí geymslu sem styður ekki slíka aðgerð? Hálfkláraðar breytingar:
Hvernig getum við tryggt okkur gegn því að tapa gögnum og enda með hálfk-láraðar breytingar? Hreyfing:
Hreyfing (e. transaction) er þægilegt hugtak.
Gott dæmi um abstraktion í tölvunarfræði. Skilgreinum nýtt hugtak til að getaunnið á hærra stigi.
Leyfir okkur að vinna með breytingar í ”áreiðanlegum einingum”, án þess aðþurfa að hugsa um hvernig það er útfært.
Í dag munum við fjalla um hvernig það er hægt að útfæra hreyfingar (nánar tiltekið A og D eiginleikana).
Bottom-up umfjöllun. Byrjum með einfalt líkan og vinnum okkur upp.
Atomicity (A): (all-or-nothing atomicity)
Hreyfing er atómísk á þann hátt að annaðhvort er allt gert eða ekkert gert Consistency (C):
Hreyfing viðheldur réttleika gagnasafnsins. Ef gagnasafn er í löglegri stöðu þáverður það áfram í löglegri stöðu eftir hreyfingu.
Isolation (I): (before-or-after atomicity)
Ef tvær hreyfingar T1 og T2 eru framkvæmdar samtímis þá er niðurstaðan súsama og að framkvæma þær í röð, þ.e. T1, T2 eða T2, T1 Durability (D):
Eftir að hreyfing hefur verið bókuð (committed) þá helst hún bókuð.
Hugsum okkur einfalt kerfislíkan. Lögleg breyting færir kerfið úr einni löglegristöðu í aðra löglega stöðu. Stöðubreyting er ekki atómísk (og kerfið gæti hruniðí miðri breytingu.) S1 → S2 → S3 → . → Sn Kerfishrun:
Grundvallarspurning: hvað gerist ef kerfið hrynur skyndilega á tímapunkti T? Íhvaða stöðu er kerfið? Ef kerfið hrynur þegar það er í löglegri stöðu þá er ekkert vandamál.
En hvað ef kerfið hrynur í miðri færslu Sn → Sn+1 ? Það er hvorki í Sn né íSn+1 heldur í e-u óskilgreindu millibilsástandi.
Endurreisn eftir hrun:
Endurreisn eftir hrun (e. crash recovery) snýst um að taka kerfi í ólöglegu mil-libilsástandi og endurreisa það þ.a. það sé í löglegu ástandi.
Ef kerfið hrynur í færslu Sn → Sn+1 þá mun endurreisn kerfisins færa þaðannaðhvort í stöðu Sn eða Sn+1 Samhliða vinnsla:
Einfalda líkanið gerir bara ráð fyrir einni stöðubreytingu í einu, en hvað ef viðviljum leyfa margar breytingar samtímis? Hvernig skilgreinum við löglegu stöðurnar í slíku líkani? Hvernig má fléttabreytingar saman? Lýsing:
Skulum hugsa okkur einfalt bankakerfi þar sem innistæður eru geymdar á disk.
Höfum aðgerð xfer(a,b,amount) sem millifærir upphæð frá reikningi a yfir áreikning b.
Millifærsla felur í sér tvær breytingar. Millifærsla er því ekki atómísk breyting.
S1 → S2 → . → Sn Ef kerfið hrynur í miðri millifærslu þá er það í ólöglegu millibilsástandi.
Hvernig getum við útfært xfer þ.a. það sé atomískt (all or nothing) ? Einföld útfærsla á atomic xfer (shadow copy) Forsendur:
Allar innistæður eru geymdar í einni stórri skrá í skráarkerfinu.
Atomic rename aðgerð í skráarkerfinu.
Linux man page: rename(oldpath,newpath): If newpath already exists it will beatomically replaced Atomic xfer:
Afritum skrána. Breytum afritinu. Framkvæmum atomic rename.
Ef kerfið hrynur í framkvæmd xfer þá eru tveir möguleikar: búið að framkvæmarename eða ekki. Kerfið er þá annaðhvort í Sn+1 eða Sn. Það eru engir aðrirmöguleikar.
Ein skrá:
Aðgerðin virkar fyrir eina skrá en erfitt að útvíkka og nota fyrir margar skrár.
Dýrt að afrita alla skrána fyrir hverja breytingu (sama hversu stór eða lítil) Raðbundið:
Raðbundin vinnsla, þ.e. ein aðgerð í einu. Styður ekki að óbreyttu samskeiðavinnslu þar sem margar xfer aðgerðir eru í gangi samtímis.
Notendur:
Þrátt fyrir ýmsa ókosti þá er shadow copy mjög einföld og þægileg útfærsla á”all or nothing” atomískum aðgerðum. Mörg forrit sem nota shadow copy, t.d.
ritlar (editors).
Bókun (e. commit point):
Í tilfelli shadow copy þá er atomíska rename kallið svokallað commit point.
Hrun fyrir bókun gefur gömlu stöðuna; hrun eftir bókun gefur nýju stöðuna.
Hætt við bókun (e. abort):
Ef við erum byrjuð á breytingu en viljum síðan hætta við hana (abort) þá gætumvið einfaldlega hent afritinu og sleppt rename.
Gullna reglan:
Gullna reglan um útfærslu á atómískum aðgerðum: never modify the only copy! Í shadow copy er gert afrit af skránni og breytingin er framkvæmd á afritinu(síðan atomic rename). Fylgir gullnu reglunni.
Dagbók (e. log):
Skrifum allar breytingar í svokallaða dagbók. Yfirskrifum aldrei gögn í dag-bókinni, bætum bara inn nýjum færslum (dagbókin er append-only).
Dæmi: xfer(a,b,50) - fjórar færslur skráðar í dagbókina
Dagbók:
Breytingar sem tilheyra sömu atómísku einingu (s.k. hreyfingu eða transaction)eru settar saman í blokk sem byrjar á begin og endar á commit.
Bókar hreyfingu. Skráning á commit færslu er commit point fyrir hreyfinguna.
Uppfærir innistæðu. Inniheldur bæði nýja og gamla gildið.
Til að finna núverandi innistæðu á reikningi þá lesum við yfir alla dagbókina ogfinnum síðustu bókuðu breytinguna Skráning:
Skráning í dagbókina verður að vera atómísk (all or nothing). Litlar færslur oglíklegt að færsla komist fyrir í einni blokk.
Samt mögulegt að lítil færsla spanni tvær blokkir (byrjar í lokin á einni blokkog heldur áfram í þeirri næstu) Ef það verður hrun í miðri skráningu á færslu þá er mögulega síðasta færslan ídagbókinni hálfkláruð.
Einföld lausn: lesum yfir alla dagbókina þegar kerfið er ræst aftur eftir hrun, efþað er hálfkláruð færsla í lokin þá skerum við hana burt (log truncate) Núverandi útfærsla:
Í núverandi útfærslu erum við bara með dagbók.
Mjög dýrt að lesa innistæðu. Þarf að spóla í gegnum alla dagbókina.
Betri útfærsla:
Höldum bæði dagbók yfir breytingar og geymum núverandi stöðu á disk.
S1 → S2 → . → Sn Dagbókin inniheldur allar hreyfingar: T1, T2, ., Tn Geymum aukalega Sn á disk. Ódýr lestur: lesum bara núverandi gildi af disk.
Framkvæmd:
Sn → Sn+1 þá þarf að skrá Tk í dagbókina (e.
log updates) og uppfæra núverandi stöðu á disk (e. install updates) Röðun:
Eigum við að uppfæra stöðu á disk fyrst og síðan skrá færslur í dagbókina eða skrá fyrst færslur í dagbókina og síðan uppfæra stöðuna? Röðun:
Skiptir röðin á log og install máli? Já! Tveir möguleikar:
Ef við uppfærum stöðuna fyrst: ef það verður hrun í miðri uppfærslu þá erumvið í vondum málum! Brýtur gullnu regluna: ekki breyta eina eintakinu.
Ef við skráum í dagbókina fyrst (Write-Ahead Logging) og uppfærum síðanstöðuna þá eru tveir möguleikar: 1. Hrun við skráningu í dagbók: þá er hætt við bókun á hreyfingunni 2. Hrun við uppfærslu á stöðunni: ekkert vandamál, notum dagbókina til að Einföld regla: ”Always log the update before installing it” Trygg röðun:
Hvernig getum við tryggt að það sé búið að skrifa dagbókina á disk áður en viðbyrjum að breyta stöðunni? Við viljum ekki að dagbókarfærslurnar hangi í page cache stýrikerfisins. Gætumlent í ófyrirsjáanlegri I/O verkröðun sem brýtur WAL regluna.
fsync(fd): skrifar allar dirty síður sem tengjast skránni fd út á disk. Kallið snýrekki til baka fyrr en allt hefur verið skrifað.
(Notum frekar fdatasync(fd) ef það er til staðar, það skrifar ekki metadata útá disk, t.d. last modified time, bara dirty síður sem tengjast gögnum í skránni) Endurbót 1: frestum install og notum cache Lazy update:
Uppfærum alltaf dagbókina á disk en uppfærum ekki stöðuna á disk strax.
Uppfærum í staðinn stöðuna í minni (fáum dirty page í buffer cache) og uppfærumsíðan stöðuna á disk lazily (t.d. reglulegt flush í bakgrunnsþræði.) Lesum stöðuna úr minni ef hún er í cache, en förum annars út á disk (og sækjumsíðu af disk yfir í buffer cache).
Misræmi:
Möguleiki á misræmi, þar sem staðan á disk er ekki endilega sú nýjasta.
Misræmi:
Möguleiki á misræmi, þar sem staðan á disk er ekki endilega sú nýjasta.
Gætum haft uppfærslur á stöðu í minni (dirty pages) sem á eftir að skrifa út ádisk.
Ef við uppfærum jafnóðum þá gæti staðan á disk gæti innihaldið uppfærslursem var hætt við að bóka (aborted updates).
Endurreisn:
Göngum yfir dagbókina og leiðréttum stöðuna á disk.
Afbókum (undo) allar breytingar í hreyfingum sem var hætt við að bóka.
Endurgerum (redo) allar breytingar í hreyfingum sem voru bókaðar.
Núverandi hönnun:
Núverandi hönnun gerir ráð fyrir að dagbókin stækki endalaust. Ekki mjög prak-tískt.
Megum henda öllum hreyfingum úr dagbókinni fram að tilteknum punkti ef þæreru allar lokaðar, þ.e. endanleg niðurstaða (commit/abort) er skráð, og staðaná disk endurspeglar stöðuna í dagbókinni í þeim punkti.
Stytting:
Grf. að engin hreyfing sé í gangi, þ.e. stytting er framkvæmd á milli hreyfinga.
1. Skráum svokallaða checkpoint færslu í dagbókina 2. Skráum allar breytingar á disk (flush updates).
3. Styttum dagbókina: hendum öllum hreyfingum fram að checkpointinu.
Opnar hreyfingar:
Ef það eru hreyfingar í gangi þá framkvæmum við sömu skref, nema í þriðjaskrefi styttum við fram að fyrstu opnu hreyfingu á undan checkpoint Dagbækur:
Skráning í dagbók er almenn aðferð til að útfæra all-or-nothing atomicity.
Notað í gagnasafnskerfum til að útfæra hreyfingar.
Runubundin skrif í dagbók (sequential logging), því hún er append-only Hægt að fá hraðan lestur með því að geyma einnig stöðuna á disk (og enn betrihraða með því að geyma stöðu í minni) Lykilatriði:
WAL: einföld regla sem tryggir örugga uppfærslu og möguleika á endurreisneftir hrun

Source: http://gsf.hhg.to/09-TX.pdf