Transaction Concept
- A transaction is a unit of program execution
that accesses and possibly updates various data items
- ex). Transfer $50 from account A to account B
1. read(A)
2. A = A - 50
3. write(A)
4. read(B)
5. B = B + 50
6. write(B)
- 2가지 main issue
- hardware failure, system crash와 같은 다양한 실패
- 여러 transaction들의 동시 실행
ACID Properties
4가지 requirement
Atomicity Requirement
- 만약 step 3와 step 6 사이에서 transaction이 fail했으면,
money will be "lost"
- ALL OR NOTHING. 100% 반영하거나, 그게 아니라면 아예 database에 반영하지 않는다.
Durability requirement
- user가 transaction이 완료되었다고 notify하면,
transcaction에 의한 db update는 반드시 진행되어야 한다.
(even if there are software or hardware failures)
Consistency requirement
- 위 예시에서). transaction 실행에 의한 A + B 값은 변함이 없어야 한다.
- 일반적으로 consistency requirement는 다음을 포함한다 :
- explicitly specified integrity constraints such as primary keys and foreign keys
- implicit integrity constraints such as sum of balances of all accounts
- During transaction execution, db may be temporarily inconsistent
- When transaction completes successfully, db must be consistent
Isolation requirement
- 위 예시에서). 3번과 6번 step 사이에 다른 transaction T2가 A, B값에 접근하려고 하면, inconsistent database가 된다.
- transaction들을 순차적으로(serially) 실행시킴으로서 보장받을 수 있다.
- 하지만, multiple transaction을 동시에 실행시키는 건 분명히 이점이 있다.
Summary
-
A transaction is a unit of program execution
that accesses and possibly updates various data items.
To preserve integrity of data, db system must ensure 4 things
-
Atomicity : Either all operations of the transaction are properly reflected in the db or none are.
-
Consistency : Execution of a transaction in isolation preserves the consistency of the db.
-
Isolation : Although multiple transaction may execute concurrently,
each transaction must be unaware of other concurrently executing transactions.
Immediate transaction results must be hidden from other concurrently executed transactions.
-
Durability : After a transaction completes successfully,
the change it has made to the db persist,
even there are system failures.
Transaction State
- Active : 현재 진행중.
- the initial state;
- transaction이 실행중일 때 이 state에 있는다
- Partially committed : buffer에 update 완료 (disk에 쓰기 전)
- after the final statement has been executed
- Failed
- after the discovery that normal execution can no longer proceed
- Aborted : 실행 중단 -> 실행하기 전 상태
- after the transaction has been rolled back and the db restored to its prior to the start of the transaction.
- Two options
- Restart the transaction
- internal logical error가 없을 때 가능
- Kill the transaction
- Committed : disk에 write 완료
- after successful completion
Concurrent Executions
- multiple transaction은 동시에 실행될 수 있다
- Advantages :
- 향상된 processor와 disk의 utilization,
leading to better transaction throughput
- transaction에 대한 average response time 감소 :
short transactions need NOT wait behind long ones
- Concurrency control schemes
: Mechanisms to achieve isolation
- concurrent transactions 사이의 interaction을 control한다
Schedule
- A sequence of instructions that specify the chronological order in which instructions of concurrent transactions are executed
- transaction 집합의 schedule은 그 transaction들의 모든 instruction을 포함하고 있어야 한다
- 각 transaction의 instruction 순서를 유지해야 한다
- 성공적으로 실행을 마친 transaction은 마지막 statement에서
commit instruction을 갖는다
- 성공적으로 실행을 실패한 transaction은 마지막 statement에서
abort instruction을 갖는다
Schedule 1
A serial schedule in which T1 is followed by T2 :
- A + B 계속 200 유지
- (100, 100) (50, 150) (45, 155)
Schedule 2
A serial schedule where T2 is followed by T1 :
- A + B 계속 200 유지
- (100, 100) (90, 100) (40, 160)
Schedule 3
NOT a serial schedule, equivalent to Schedule 1
- A + B 계속 200 유지
- (100, 100) (50, 100) (45, 100) (45, 150) (45, 155)
Schedule 4
- Does NOT preserve the value of A + B
- (100, 100) (90, 100) (50, 100) (50, 150) (50, 110)
Serializability
- 기본 가정 : Each transaction preserves db consistency
- 따라서, transaction 집합의 serial execution은 preserves db consistncy
- 어떤 schedule이 serial schedule과 동일한 결과를 내면,
it is serializble
- Conflict serializability와 View serializability가 있는데, 주로 conflict serializability에 대해 배운다.
- Simplified View of transaction
- read와 write 이외의 operation은 모두 무시한다
Conflict Instruction
- transaction Ti, Tj와
각각의 instruction Ii, Ij,
얘네가 둘 다 접근하는 item Q에 대해,
다음과 같은 상황에서 conflict 발생 (전자가 Ii, 후자가 Ij)
- read(Q), read(Q) : Don't conflict
- read(Q), write(Q) : conflict
- write(Q), read(Q) : conflict
- write(Q), write(Q) : conflict
- 둘 사이의 conflict는 강제적으로 순서를 갖게 한다
-
schedule에서 둘이 연속적이고, conflict가 발생하지 않으면,
둘이 순서가 바뀌어도 결과는 동일하다
-
만약 non-conflicting instruction의 swap에 의해
schedule S가 S'으로 바뀌었다면,
S와 S'은 conflict equivalent하다
- schedule S가 serial schedule과 conflict equivalent하면,
S는 conflict serializable하다
conflict serializable example
- schedule 3는 schedule 6로 바뀔 수 있다.
- T2의 read(A)/write(A)와 T1의 read(B)/write(B)는 서로 conflict하지 않기 때문에 위치가 바뀔 수 있다.
- schedule 6는 serial schedule이기 때문에,
schedule 3는 conflict serializable하다
NOT conflict serializable example
- 위 schedule을 <T3, T4> 또는 <T4, T3>처럼 serial schedule로 바꿀 수 없다.
NOT conflict serial but same outcome
Testing for Serializability
- Consider some schedule of a set of transactions T1, ..., Tn
- Precedence graph : vertices가 transaction name인, direct graph
- 만약 graph가 acyclic하면, schedule is conflict serializable
- acyclic한지는 DFS를 이용해서 찾는다. (n^2 or n+e)
- graph가 acylic할 때, serializability order는 topological sorting에 의해 계산될 수 있다.
- 노드의 indegree가 0인 노드 먼저 하고, 이거 삭제하고
다음 indegree가 0인 노드 하고, 삭제하고,
계속 반복한다
Recoverability
Recoverable schedule
- Tj가 이전에 Ti에 의해 write된 data를 읽을 때,
Ti의 commit operation이 Tj의 commit 보다 이전에 나타나야 한다.
- NOT recoverable
- 뭐가 문제나면,
만약 T8이 abort되면, T8에 의한 작업은 모두 취소가 되어야 한다.
T9은 이미 commit이 되었기 때문에 취소가 안되는 상태인데,
그럼 얘가 읽은 A값은 inconsistent한 값이 된다!!
Cascading Rollback
- single transaction failure가 series of transaction rollbacks을 발새시킨다
- 아래 그림은 아무 transaction도 commit이 되지 않은 schedule이다.
- T10이 abort나면, T11, T12도 모두 취소된다.
- recoverable
Cascadeless Schedule
- cascading rollback이 일어날 수 없다.
- Tj가 Ti에 의해 write된 data를 read할 때,
Ti의 commit operation이 Tj의 read보다 먼저 나타난다.
- Every cascadeless schedule is also recoverable
- 아주 바람직한 방법이다.
Concurrency Control
- db는 반드시 모든 schedule이 다음 조건을 만족하게 해야 한다
- conflict serializable 하거나,
- recoverable하고 가능하다면 cascadeless.
- 단순히 serializable하게 하면 좋긴 하지만 concurrency 측면에서 낮은 결과가 나온다.
- Goal : to develop concurrency control protocols that will ensure serializability
- Schedule은 반드시 conflict serializable하고, recoverable하고, 가능하다면 cascadeless해야 한다. db의 consistency를 위해.
- concurrency-control은 amount of concurrency they allow와 amount of overhead that they incur 사이의 tradeoff가 있다.