Sandoriai
Sandoris yra su duomenimis susijusių operacijų seka, turinti pradžią ir pabaigą.
Sandoris yra nuoseklus skaitymo ir rašymo operacijų vykdymas. Operacijos pabaiga gali būti pakeitimų išsaugojimas (įsipareigojimas) arba pakeitimų atšaukimas (grįžimas). Kalbant apie duomenų bazę, operaciją sudaro kelios užklausos, kurios laikomos viena užklausa.
Sandoriai turi atitikti ACID savybes
Atomiškumas. Sandoris užbaigiamas visiškai arba neįvykdomas.
Nuoseklumas. Vykdant operaciją neturi būti pažeisti duomenims taikomi apribojimai (pavyzdžiui, apribojimai duomenų bazėje). Nuoseklumas reiškia, kad sistema bus perkelta iš vienos teisingos būsenos į kitą teisingą būseną.
Isolation. Lygiagrečiai vykdomos operacijos neturėtų turėti įtakos viena kitai, pavyzdžiui, pakeisti kitos operacijos naudojamus duomenis. Lygiagrečių operacijų vykdymo rezultatas turėtų būti toks pat, kaip ir tuo atveju, jei operacijos būtų vykdomos nuosekliai.
Tvarumas. Įsipareigojus, pakeitimai neturėtų būti prarasti.
Sandorių žurnalas
Žurnale saugomi operacijų atlikti pakeitimai, užtikrinamas duomenų atomiškumas ir stabilumas sistemos gedimo atveju
Žurnale yra duomenų reikšmės, kurias turėjo prieš ir po to, kai buvo pakeista operacija. Taikant išankstinio įrašymo žurnalo strategiją, reikia pridėti žurnalo įrašą apie ankstesnes reikšmes prieš pradedant ir apie galutines vertes po operacijos. Staigiai sustojus sistemai, duomenų bazė nuskaito žurnalą atvirkštine tvarka ir atšaukia operacijų atliktus pakeitimus. Duomenų bazė, susidūrusi su nutrūkusia operacija, ją vykdo ir atlieka pakeitimus žurnale. Būdama gedimo momento būsenoje, duomenų bazė nuskaito žurnalą išankstine tvarka ir grąžina operacijų atliktus pakeitimus. Taip išsaugomas jau įvykdytų operacijų stabilumas ir nutraukto sandorio atomiškumas.
Atkūrimui neužtenka paprasčiausiai pakartotinai vykdyti nepavykusias operacijas.
Pavyzdys. Vartotojas savo sąskaitoje turi 500 USD ir vartotojas nusprendžia juos atsiimti iš bankomato. Vykdomos dvi operacijos. Pirmasis nuskaito likučio vertę ir, jei likute yra pakankamai lėšų, išduoda pinigus vartotojui. Antrasis iš likučio atima reikiamą sumą. Tarkime, sistema sugedo ir pirmoji operacija nepavyko, bet antra. Tokiu atveju negalime pakartotinai išleisti pinigų vartotojui negrąžinus sistemos į pradinę būseną su teigiamu likučiu.
Izoliacijos lygiai
Skaitykite Įsipareigoję
Dirty Read problema yra ta, kad operacija gali nuskaityti tarpinį kitos operacijos rezultatą.
Pavyzdys. Pradinė balanso vertė yra 0 USD. T1 prideda 50 USD prie jūsų balanso. T2 nuskaito balanso vertę (50 USD). T1 atmeta pakeitimus ir išeina. T2 tęsia vykdymą su neteisingais balanso duomenimis.
Sprendimas yra nuskaityti fiksuotus duomenis (Read Committed), kuris neleidžia skaityti operacijos pakeistus duomenis. Jei operacija A pakeitė tam tikrą duomenų rinkinį, tada operacija B, kai pasiekia šiuos duomenis, yra priversta laukti, kol operacija A bus baigta.
Pakartotinis skaitymas
Prarasta naujinimų problema. T1 išsaugo pakeitimus be T2 pakeitimų.
Pavyzdys. Pradinė balanso vertė yra 0 USD, o dvi operacijos vienu metu papildo likutį. T1 ir T2 balansas yra 0 USD. Tada T2 prie 200 USD prideda 0 USD ir išsaugo rezultatą. T1 prideda $100 prie $0 ir išsaugo rezultatą. Galutinis rezultatas yra 100 USD, o ne 300 USD.
Nepakartojama skaitymo problema. Pakartotinai skaitant tuos pačius duomenis, gaunamos skirtingos reikšmės.
Pavyzdys. T1 nuskaito 0 USD balanso vertę. Tada T2 prideda 50 USD prie balanso ir baigiasi. T1 dar kartą nuskaito duomenis ir nustato neatitikimą ankstesniam rezultatui.
Pakartotinis skaitymas užtikrina, kad antras skaitymas duos tą patį rezultatą. Vienos operacijos nuskaityti duomenys negali būti keičiami kitose, kol operacija nebaigta. Jei operacija A nuskaitė tam tikrą duomenų rinkinį, tada operacija B, kai pasiekia šiuos duomenis, yra priversta laukti, kol operacija A bus baigta.
Užsakytas skaitymas (serializuojamas)
Phantom Reads problema. Dvi užklausos, parenkančios duomenis pagal tam tikrą sąlygą, pateikia skirtingas reikšmes.
Pavyzdys. T1 prašo visų vartotojų, kurių likutis didesnis nei 0 USD, bet mažesnis nei 100 USD, skaičiaus. T2 išskaičiuoja 1 USD iš vartotojo, kurio likutis yra 101 USD. T1 pakartotinai išsiunčia prašymą.
Užsakytas skaitymas (serializuojamas). Operacijos vykdomos visiškai nuosekliai. Draudžiama atnaujinti ar pridėti įrašus, kurie atitinka užklausos sąlygas. Jei operacija A paprašė duomenų iš visos lentelės, visa lentelė užšaldoma kitoms operacijoms, kol A operacija bus baigta.
Tvarkaraštis
Nustatoma tvarka, kuria turi būti atliekamos operacijos lygiagrečių operacijų metu
Suteikia tam tikrą izoliacijos lygį. Jei operacijų rezultatas nepriklauso nuo jų eilės, tai tokios operacijos yra komutacinės (Permutable). Skaitymo operacijos ir operacijos su skirtingais duomenimis yra komutacinės. Skaitymo-rašymo ir rašymo-rašymo operacijos nėra komutacinės. Planuotojo užduotis yra sujungti lygiagrečių operacijų atliekamas operacijas, kad vykdymo rezultatas būtų lygiavertis nuosekliam operacijų vykdymui.
Lygiagrečių užduočių valdymo mechanizmai (lygiagrečio kontrolė)
Optimistas remiasi konfliktų aptikimu ir sprendimu, pesimistinis – konfliktų prevencija.
Optimistiškai žiūrint, keli vartotojai turi duomenų kopijas. Pirmasis asmuo, baigęs redaguoti, išsaugo pakeitimus, o kiti turi juos sujungti. Optimistiškas algoritmas leidžia kilti konfliktui, tačiau sistema turi atsigauti po konflikto.
Taikant pesimistinį požiūrį, pirmasis vartotojas, užfiksavęs duomenis, neleidžia kitiems gauti duomenų. Jei konfliktai pasitaiko retai, išmintinga rinktis optimistinę strategiją, nes ji užtikrina aukštesnį lygiagretumo lygį.
Užrakinimas
Jei vienos operacijos duomenys yra užrakinti, kitos operacijos turi palaukti, kol ji bus atrakinta, kai pasiekia duomenis.
Blokas gali būti perdengtas ant duomenų bazės, lentelės, eilutės ar atributo. Bendras užraktas gali būti taikomas tiems patiems duomenims keliomis operacijomis, leidžia nuskaityti visas operacijas (įskaitant tą, kuri ją nustatė), draudžia modifikavimą ir išskirtinį fiksavimą. Išskirtinis užraktas gali būti įvestas tik vienu sandoriu, leidžia atlikti bet kokius įvedimo sandorio veiksmus, draudžia bet kokius kitų veiksmus.
Aklavietė yra situacija, kai sandoriai patenka į laukiančią būseną, kuri trunka neribotą laiką.
Pavyzdys. Pirmoji operacija laukia, kol bus išleisti antrojo užfiksuoti duomenys, o antroji laukia, kol bus išleisti pirmojo užfiksuoti duomenys.
Optimistiškas aklavietės problemos sprendimas leidžia įvykti aklavietėje, bet tada atkuria sistemą, atšaukdamas vieną iš aklavietėje dalyvaujančių operacijų.
Tam tikrais intervalais ieškoma aklavietės. Vienas iš aptikimo metodų yra pagal laiką, ty manyti, kad atsitiko aklavietė, jei operacija trunka per ilgai. Kai randama aklavietė, viena iš operacijų atšaukiama, leidžiant užbaigti kitas su aklaviete susijusias operacijas. Aukos pasirinkimas gali būti pagrįstas sandorių verte arba jų stažu (Wait-Die ir Wound-Wait schemos).
Kiekvienas sandoris T priskiriama laiko žyma TS kuriame nurodytas operacijos pradžios laikas.
Palauk - Mirk.
jei TS (Ti) < TS(Tj), Tada Ti laukia, kitaip Ti atsukamas atgal ir pradedamas iš naujo su ta pačia laiko žyma.
Jei jauna operacija įsigijo išteklių, o senesnė operacija prašo to paties resurso, senesnei operacijai leidžiama palaukti. Jei senesnė operacija įsigijo išteklių, jaunesnė operacija, prašanti šio resurso, bus atšaukta.
Žaizda-lauk.
jei TS (Ti) < TS(Tj), Tada Tj sukasi atgal ir pradeda iš naujo su ta pačia laiko žyma, priešingu atveju Ti laukimas.
Jei jaunesnė operacija įsigijo išteklių, o senesnė operacija reikalauja tų pačių išteklių, jaunesnė operacija bus atšaukta. Jei senesnė operacija įsigijo išteklių, jaunesnei operacijai, prašančiai to resurso, leidžiama laukti. Aukų atranka pagal pirmenybę apsaugo nuo aklavietės, bet grąžina operacijas, kurios nėra aklavietėje. Problema ta, kad sandorius galima daug kartų atšaukti, nes... senesnė operacija gali turėti išteklių ilgą laiką.
Pesimistinis aklavietės problemos sprendimas neleidžia pradėti vykdyti operacijos, jei yra aklavietės rizika.
Norint aptikti aklavietę, konstruojamas grafikas (laukimo grafikas, laukimo grafikas), kurio viršūnės yra operacijos, o briaunos nukreipiamos nuo operacijų, laukiančių duomenų išleidimo, į šiuos duomenis užfiksavusią operaciją. Laikoma, kad aklavietė atsitiko, jei grafikas turi kilpą. Laukimo grafiko sudarymas, ypač paskirstytose duomenų bazėse, yra brangi procedūra.
Dviejų fazių užraktas – užkerta kelią aklavietėms, nes operacijos pradžioje paimami visi operacijos naudojami ištekliai, o pabaigoje atleidžiami
Visos blokavimo operacijos turi būti atliekamos prieš pirmąjį atrakinimą. Jis turi dvi fazes – auginimo fazę, kurios metu kaupiasi rankenos, ir susitraukimo fazę, kurios metu rankenos atleidžiamos. Jei vieno iš išteklių užfiksuoti neįmanoma, operacija pradedama iš naujo. Gali būti, kad sandoris negalės įgyti reikiamų išteklių, pavyzdžiui, jei dėl tų pačių išteklių konkuruos keli sandoriai.
Dviejų fazių įteikimas užtikrina, kad įsipareigojimas būtų vykdomas visose duomenų bazės kopijose
Kiekviena duomenų bazė įveda informaciją apie duomenis, kurie bus pakeisti į žurnalą ir atsako koordinatoriui Gerai (balsavimo fazė). Visiems atsakius gerai, koordinatorius siunčia signalą, įpareigojantį visus įsipareigoti. Po įsipareigojimo serveriai atsako gerai, jei bent vienas neatsako gerai, koordinatorius siunčia signalą atšaukti pakeitimus visiems serveriams (užbaigimo fazė).
Laiko žymos metodas
Senesnė operacija atšaukiama, kai bandoma pasiekti duomenis, susijusius su jaunesne operacija
Kiekvienai operacijai priskiriama laiko žyma TS atitinkantis vykdymo pradžios laiką. Jeigu Ti vyresni Tj, Tada TS (Ti) < TS(Tj).
Kai operacija atšaukiama, jai priskiriama nauja laiko žyma. Kiekvienas duomenų objektas Q sandoryje dalyvaujantis pažymėtas dviem etiketėmis. W-TS(Q) — jauniausios operacijos, sėkmingai užbaigusios įrašą, laiko žyma Q. R-TS(Q) — jauniausios operacijos, kuri atliko skaitymo įrašą, laiko žyma Q.
Kai sandoris T prašymus perskaityti duomenis Q Yra du variantai.
jei TS(T) < W-TS(Q), tai yra, duomenys buvo atnaujinti atlikus jaunesnę operaciją, tada operacija T rieda atgal.
jei TS(T) >= W-TS(Q), tada atliekamas skaitymas ir R-TS(Q) tampa MAX(R-TS(Q), TS(T)).
Kai sandoris T prašo pakeisti duomenis Q Yra du variantai.
jei TS(T) < R-TS(Q), tai yra, duomenis jau perskaitė jaunesnis sandoris ir jei bus atliktas pakeitimas, kils konfliktas. Sandoris T rieda atgal.
jei TS(T) < W-TS(Q), tai yra, operacija bando perrašyti naujesnę reikšmę, operacija T atšaukiama. Kitais atvejais pakeitimas atliekamas ir W-TS(Q) tampa lygus TS(T).
Nereikia brangios laukimo grafiko konstrukcijos. Senesnės operacijos priklauso nuo naujesnių, todėl laukimo grafike nėra ciklų. Nėra aklavietės, nes operacijos nelaukiamos, o nedelsiant grąžinamos. Galimi pakopiniai atšaukimai. Jeigu Ti nuriedėjo ir Tj Perskaičiau duomenis, kuriuos pakeičiau Ti, Tada Tj taip pat turėtų atsukti atgal. Jei tuo pačiu metu Tj jau buvo padaryta, tuomet bus pažeistas stabilumo principas.
Vienas iš sprendimų kaskadiniam atšaukimui. Operacija užbaigia visas rašymo operacijas, o kitos operacijos turi palaukti, kol ta operacija bus baigta. Sandoriai laukia, kol bus įvykdyti, prieš juos perskaitydami.
Thomaso rašymo taisyklė – laiko žymos metodo variantas, pagal kurį duomenis, atnaujintus naudojant jaunesnę operaciją, draudžiama perrašyti senesnei operacijai.
Sandoris T prašo pakeisti duomenis Q. Jei TS(T) < W-TS(Q), tai yra, operacija bando perrašyti naujesnę reikšmę, operacija T neatšaukiama, kaip taikant laiko žymos metodą.
Šaltinis: www.habr.com