Transaktioner
En transaktion Àr en sekvens av operationer över data som har en början och ett slut.
En transaktion Àr en sekventiell utföring av lÀs- och skrivoperationer. Avslutningen av en transaktion kan antingen vara att spara Àndringar (commit) eller att Ängra Àndringar (rollback). NÀr det gÀller databaser Àr en transaktion flera förfrÄgningar som tolkas som en enskild förfrÄgan.
Transaktioner mÄste uppfylla ACID-egenskaperna.
Atomicitet. En transaktion antingen genomförs helt eller inte alls.
Konsistens. Vid avslutandet av transaktionen fÄr inga begrÀnsningar som stÀlls pÄ data (till exempel constraints i databasen) brytas. Konsistens innebÀr att systemet kommer att överföras frÄn ett korrekt tillstÄnd till ett annat korrekt.
Isolering. Parallellt utförda transaktioner fÄr inte pÄverka varandra, till exempel genom att Àndra data som en annan transaktion anvÀnder. Resultatet av att parallella transaktioner genomförs ska vara sÄdant att transaktionerna utfördes sekventiellt.
BestÀndighet. Efter en commit fÄr inte Àndringarna gÄ förlorade.
Transaktionslogg.
Loggen lagrar Àndringar utförda av transaktioner och sÀkerstÀller atomaritet och bestÀndighet av data vid systemfel.
Loggen innehÄller vÀrdena som data hade före och efter Àndringen av transaktionen. Write-ahead log-strategin krÀver att tidigare vÀrden ska lÀggas till i loggen innan transaktionen pÄbörjas, och slutvÀrden efter att transaktionen har avslutats. Vid ett plötsligt systemstopp lÀser databasen loggen baklÀnges och Ängrar Àndringar gjorda av transaktionerna. NÀr databasen stöter pÄ en avbruten transaktion utförs den och Àndringar om den görs i loggen. NÀr databasen Àr i det tillstÄnd som rÄdde vid felet lÀser den loggen framÄt och ÄterstÀller Àndringar gjorda av transaktionerna. PÄ sÄ sÀtt bevaras bestÀndigheten av transaktioner som redan har bekrÀftats och atomariteten av den avbrutna transaktionen.
En enkel upprepning av felaktiga transaktioner Àr otillrÀcklig för ÄterstÀllning.
Exempel. AnvÀndarens konto har 500$ och anvÀndaren vÀljer att ta ut dem via en bankautomat. TvÄ transaktioner utförs. Den första lÀser av saldo och om det finns tillrÀckligt med medel, ger den pengar till anvÀndaren. Den andra drar den nödvÀndiga summan frÄn saldot. Anta att det intrÀffar ett systemfel och den första operationen misslyckas, medan den andra lyckas. I det hÀr fallet kan vi inte ge pengar till anvÀndaren igen utan att ÄterstÀlla systemet till det ursprungliga tillstÄndet med ett positivt saldo.
IsoleringsnivÄer
LĂ€sa fasta data (Read Committed)
Problemet med smutsig lÀsning (Dirty Read) ligger i att en transaktion kan lÀsa ett mellanliggande resultat av en annan transaktion.
Exempel. StartvÀrdet pÄ saldot Àr 0$. T1 lÀgger till 50$ till saldot. T2 lÀser saldo (50$). T1 Ängrar Àndringarna och avslutas. T2 fortsÀtter med att ha felaktiga data om saldot.
Lösningen Àr att lÀsa fasta data (Read Committed) som förbjuder att lÀsa data som Àndrats av en transaktion. Om transaktion A har Àndrat en uppsÀttning data, sÄ mÄste transaktion B vÀnta pÄ att transaktion A ska avslutas innan den kan begÀra dessa data.
à terkommande lÀsning (Repeatable Read)
Problemet med förlorade förÀndringar (Lost Updates). T1 sparar Àndringar ovanpÄ T2:s Àndringar.
Exempel. StartvÀrdet pÄ saldot Àr 0$ och tvÄ transaktioner fyller samtidigt pÄ saldot. T1 och T2 lÀser saldot som Àr 0$. Sedan lÀgger T2 till 200$ till 0$ och sparar resultatet. T1 lÀgger till 100$ till 0$ och sparar resultatet. Det slutgiltiga resultatet Àr 100$ istÀllet för 300$.
Problemet med icke-Äterkommande lÀsning (Unrepeatable Read). à terkommande lÀsning av samma data ger olika vÀrden.
Exempel. T1 lÀser av saldot som Àr 0$. Sedan lÀgger T2 till 50$ till saldot och avslutas. T1 lÀser om data och upptÀcker en mismatch med det tidigare resultatet.
à terkommande lÀsning (Repeatable Read) garanterar att en andra lÀsning ger samma resultat. Data som lÀses av en transaktion fÄr inte Àndras av andra innan transaktionen Àr avslutad. Om transaktion A lÀste en viss uppsÀttning data, mÄste transaktion B vÀnta pÄ att transaktion A ska avslutas innan den kan begÀra dessa data.
Seriell lÀsning (Serializable)
Problemet med spöklÀsning (Phantom Reads). TvÄ förfrÄgningar som hÀmtar data baserat pÄ ett visst villkor returnerar olika vÀrden.
Exempel. T1 begÀr antal alla anvÀndare vars saldo Àr större Àn 0$ men mindre Àn 100$. T2 drar av 1$ frÄn en anvÀndare med saldo 101$. T1 utför förfrÄgan igen.
Ordnad lÀsning (Serializable). Transaktioner utförs helt sekventiellt. Att uppdatera och lÀgga till poster som faller under sÄdana villkor Àr förbjudet. Om transaktion A begÀr data frÄn hela tabellen sÄ fryses hela tabellen för de andra transaktionerna tills transaktion A Àr slutförd.
SchemalÀggare (Scheduler)
FaststÀller i vilken ordning operationer skall utföras vid parallella transaktioner.
SÀkerstÀller en given nivÄ av isolering. Om resultatet av operationerna inte beror pÄ deras ordning, Àr dessa operationer kommutativa (Permutable). LÀsoperationer och operationer pÄ olika data Àr kommutativa. LÀs-skriv och skriv-skriv operationer Àr inte kommutativa. SchemalÀggarens uppgift Àr att vÀxla mellan operationer utförda av parallella transaktioner sÄ att resultatet blir ekvivalent med sekventiell utförande av transaktionerna.
Mechanismer för kontroll av parallella uppgifter (Concurrency Control)
Optimistisk grundar sig pÄ upptÀckten och lösningen av konflikter, pessimistisk pÄ förebyggande av konflikter.
Vid den optimistiska metoden fÄr flera anvÀndare rÄdata kopior. Den som först slutför redigeringen sparar Àndringar, medan de andra mÄste göra en sammanslagning av Àndringarna. Den optimistiska algoritmen tillÄter en konflikt att intrÀffa, men systemet mÄste ÄterhÀmta sig efter konflikten.
Vid den pessimistiska metoden förhindrar den första anvÀndaren som fÄngar data att andra fÄr Ätkomst. Om konflikter Àr sÀllsynta kan det vara rimligt att vÀlja en optimistisk strategi, eftersom den erbjuder högre nivÄ av parallellism.
LĂ„sning (Locking)
Om en transaktion har lÄst data, mÄste andra transaktioner vÀnta pÄ att lÄsningen ska hÀvas.
Block kan tillÀmpas pÄ en databas, tabell, rad eller attribut. Dela lÄs (Shared Lock) kan tillÀmpas pÄ samma data av flera transaktioner, vilket tillÄter alla transaktioner (inklusive den som har tillÀmpat lÄset) att lÀsa, men förhindrar förÀndringar och exklusiva lÄs. Exklusiv lÄs (Exclusive Lock) kan endast tillÀmpas av en transaktion, vilket tillÄter alla ÄtgÀrder av den tillÀmpande transaktionen, men förhindrar alla ÄtgÀrder frÄn andra.
En dödlÀges-situation uppstÄr nÀr transaktioner befinner sig i ett oÀndligt vÀntelÀge.
Exempel. Den första transaktionen vÀntar pÄ att data som fÄngats av den andra ska frigöras, medan den andra vÀntar pÄ att data som fÄngats av den första ska bli tillgÀngliga.
En optimistisk lösning pÄ problemet med dödlÀgen tillÄter att en dödlÀge uppstÄr, men ÄterstÀller sedan systemet genom att rulla tillbaka en av transaktionerna som Àr involverade i dödlÀget.
Med jÀmna mellanrum genomförs sökningar efter dödlÀgen. Ett sÀtt att upptÀcka dem Àr att bedöma tiden, det vill sÀga att anta att ett dödlÀge har intrÀffat om en transaktion tar för lÄng tid. NÀr ett dödlÀge hittas, rullas en av transaktionerna tillbaka, vilket ger andra transaktioner som Àr involverade i dödlÀget möjlighet att slutföras. Valet av offer kan baseras pÄ kostnaden för transaktionerna eller deras Älder (Wait-Die och Wound-wait scheman).
Varje transaktion T tilldelas en tidsstÀmpel TS som innehÄller tiden för nÀr transaktionen startade.
Wait-Die.
Om TS(Ti) < TS(Tj), sÄ Ti vÀntar, annars Ti rullas tillbaka och börjar om med samma tidsstÀmpel.
Om en yngre transaktion har fÄngat en resurs, och en Àldre begÀr samma resurs, tillÄts den Àldre transaktionen att vÀnta. Om den Àldre transaktionen har fÄngat resursen, kommer den yngre transaktionen som begÀr denna resurs att rullas tillbaka.
Wound-wait.
Om TS(Ti) < TS(Tj), sÄ Tj rullas tillbaka och börjar om med samma tidsstÀmpel, annars Ti vÀntar.
Om en yngre transaktion har tagit kontroll över en resurs och en Àldre transaktion begÀr samma resurs, kommer den yngre transaktionen att ÄterstÀllas. Om en Àldre transaktion har tagit kontroll över en resurs, tillÄts den yngre transaktionen som begÀr den resursen att vÀnta. Valet av offer baserat pÄ Älder förhindrar uppkomsten av dödlÀgen, men rullar tillbaka transaktioner som inte Àr i ett dödlÀge. Problemet Àr att transaktioner kan rullas tillbaka flera gÄnger, eftersom en Àldre transaktion kan hÄlla resursen under lÄng tid.
En pessimistisk lösning pÄ problemet med dödlÀgen tillÄter inte att en transaktion pÄbörjar sin execution om det finns en risk för dödlÀge.
För att upptÀcka dödlÀgen byggs en graf (vÀntande graf, wait-for-graph) dÀr noderna Àr transaktioner och kanterna Àr riktade frÄn transaktioner som vÀntar pÄ frigörande av data till transaktionerna som har tagit dessa data. Det anses att ett dödlÀge har intrÀffat om grafen har cykler. Att bygga en vÀntande graf, sÀrskilt i distribuerade databaser, Àr en kostsam process.
TvÄfaslÄsning Àr att förhindra dödlÀgen genom att ta kontroll över alla resurser som anvÀnds av transaktionen i början av transaktionen och frigöra dem i slutet.
Alla blockerande operationer mĂ„ste föregĂ„ den första avblockerande. Den har tvĂ„ faser â Growing Phase dĂ€r resurser ackumuleras och Shrinking Phase dĂ€r resurser frigörs. Om det inte gĂ„r att ta kontroll över en av resurserna börjar transaktionen om frĂ„n början. Det kan uppstĂ„ situationer dĂ€r en transaktion inte kan ta kontroll över nödvĂ€ndiga resurser, till exempel om flera transaktioner konkurrerar om samma resurser.
TvÄfascommit sÀkerstÀller att commit utförs pÄ alla repliker av databasen.
Varje databas registrerar information om de data som kommer att Àndras i loggen och svarar koordinatorn med OK (Voting Phase). NÀr alla har svarat okej skickar koordinatorn en signal som ÄlÀgger alla att utföra commit. Efter commit servern svarar de okej; om nÄgon inte svarade okej, skickar koordinatorn en signal för att avbryta Àndringarna till alla servrar (Completion Phase).
Metod för tidsstÀmplar
En Àldre transaktion rullas tillbaka vid försök att fÄ Ätkomst till data som anvÀnds av en yngre transaktion.
Varje transaktion tilldelas en tidsstÀmpel TS som motsvarar starttiden för utförandet. Om Ti Àldre Tj, sÄ TS(Ti) < TS(Tj).
NĂ€r en transaktion rullas tillbaka tilldelas den en ny tidsstĂ€mpel. Varje databasobjekt Q som pĂ„verkas av transaktionen mĂ€rks med tvĂ„ stĂ€mplar. W-TS(Q) â tidsstĂ€mpeln för den yngsta transaktionen som framgĂ„ngsrikt har skrivit Q. R-TS(Q) â tidsstĂ€mpeln för den yngsta transaktionen som har utfört en lĂ€soperation Q.
NÀr transaktionen T begÀr att lÀsa data Q finns tvÄ alternativ.
Om TS(T) < W-TS(Q), det vill sÀga om datan har uppdaterats av en yngre transaktion, sÄ rullas transaktionen T tillbaka.
Om TS(T) >= W-TS(Q), dÄ utförs lÀsningen och R-TS(Q) att skapa MAX(R-TS(Q), TS(T)).
NÀr transaktionen T begÀr att Àndra data Q finns tvÄ alternativ.
Om TS(T) < R-TS(Q), det vill sÀga att datan redan har lÀsts av en yngre transaktion och om en Àndring genomförs, sÄ uppstÄr en konflikt. Transaktionen T tillbaka.
Om TS(T) < W-TS(Q), det vill sÀga att transaktionen försöker skriva över ett nyare vÀrde, transaktionen T rullas tillbaka. I övriga fall genomförs Àndringen och W-TS(Q) blir lika med TS(T).
Det krĂ€vs inget kostsamt byggande av vĂ€ntediagram. Ăldre transaktioner beror pĂ„ yngre, och dĂ€rför finns det inga cykler i vĂ€ntediagrammet. Det finns inga dödlĂ€gen, eftersom transaktionerna inte vĂ€ntar, utan rullas tillbaka direkt. KaskadĂ„terstĂ€llningar kan förekomma. Om Ti rullas tillbaka, och Tj har lĂ€st de data som den Ă€ndrade Ti, sĂ„ Tj mĂ„ste ocksĂ„ rullas tillbaka. Om detta sker Tj redan har begĂ„tts, sĂ„ intrĂ€ffar ett brott mot stabilitetsprincipen.
En lösning pÄ kaskadÄterstÀllningar. Transaktionen utför alla skrivoperationer i slutet, och övriga transaktioner mÄste vÀnta pÄ att denna operation ska slutföras. Transaktioner vÀntar pÄ commit innan de lÀser.
Thomas write rule â en variant av tidsstĂ€mpelmetoden dĂ€r data som har uppdaterats av en yngre transaktion inte fĂ„r skrivas över av en Ă€ldre
Transaktion T begÀr att Àndra data Q. Om TS(T) < W-TS(Q), det vill sÀga att transaktionen försöker skriva över ett nyare vÀrde, sÄ rullas inte transaktionen T tillbaka som i tidsstÀmpelmetoden.
KĂ€lla: habr.com
