Database 20장

Single-User versus Multiuser Systems

두가지 처리방식
1. Interleaved processing : A,B가 동시에 수행될때 교대로 수행한다
2. Parallel processing : C,D가 동시에 수행된다

여러 프로그램이 돌아갈때 위의 두가지 방식 존재
concurrency control에 관련된 대부분의 것들은 interleaved concurrency를 기반으로 둔다.

 

TRANSACTIONS : 논리적으로 하나의 단위로 프로그램을 수행

-begin transaction - end transaction : 단위를 묶는 명령
-하나의 transaction 내에는 여러 DB접근 연산이 포함된다 : 삽입,삭제,수정,검색
-큰 프로그램의 경우 하나의 프로그램에 여러 transaction이 포함될 수 있다.
Read(검색 transaction) / Read-Write(갱신연산 transaction) 으로 나뉜다

 

Transaction R/W Operation

read-item(x) : transaction에서 어떤 data를 읽는 연산
프로그램 변수에 X라는 item을 읽어온다

1.X가 위치한 disk block의 주소를 찾는다
2.disk block을 MM의 buffer에 카피한다 (만약 disk block이 MM buffer에 존재하지 않을때)
3.buffer에 가져오면 buffer에서 부터 X 데이터를 program 변수로 가져오는 작업을 한다

 

disk -> buffer -> program , read x를 또 수행하면 buffer에 이미 존재하므로 buffer->program

write-item(x) : 쓰기 연산

1.read와 동일하게 주소찾기
2. 이미 존재하면 buffer에 넣을필요 없다
3. x item을 program 영역으로 가져와서 내용 수정
4. 해당 되는 update block을 다시 buffer에서 disk로 내보낸다 ( update의 종류 즉시, 차후에 한번에)

 

disk -> buffer -> program -> buffer -> disk

read - set : transaction에서 read를 위한 set (X,Y)   wirte - set : transaction에서 write를 위한 set (X,Y)

Why Concurrency Control(병행수행제어, 동시성 제어) is Needed 

동시성 제어가 안될시 생기는 문제들
Problems
-Lost update
-Temporary update : Cascading rollback
-incorrect summary
-Unrepeatable read

 

lost update problem, T2의 write_item(x)에서 T1의 write값을 덮어버리므로 T1의 연산이 무의미해 진다.

temporary update problem, T1의 X가 마지막에 FAIL이 발생하면 그 이전의 연산들또한 함께 취소되야 한다(Cascading rollback) 그리고 이때 T2가 읽은 중간과정의 data를 dirty data라고 한다.

incorrect summary problem, T1의 두 연산 가운데서 T3의 연산이 실행되면 Y값에 update 되기 전 value가 들어온다.

uprepeatable read, T1에서 X를 두번 읽을때 그 사이에서 T2가 연산과정을 거치면, T1에서 읽는 X값이 다르다. ex) 항공예약시스템, 빈자리를 예약하려고 눌럿는데 이미 누가 그사이에 예약해버리는 경우. 해결책으로는 다른 연산이 개입하지 못하게 한다

Why Recovery Is Needed

transaction이 잘못됬을때 원위치 시키는 작업
transaction은 logical unit으로 나눌수 없는 atomic한 단위
committed : transaction내의 모든 연산이 잘 수행되어서 그 결과가 db에 영구히 기록시키는 연산
aborted : transaction이 제대로 수행되지 않아 아예 수행되지 않게 취소시키는 연산

transaction에 error(fail)가 나면 , 그 연산자체를 없던일로 돌려놓는다 -> 가장 기본적 원칙 : 완벽히 수행시키거나, 아예 수행을 안하거나

 

Recovery가 필요한 상황

Transaction States, Additional Operations

 

1.Active상태에서 Abort 발생시 Failed로 가게된다. 그렇게 되면 모든 변화사항들을 수행되기 전 상태로 돌려놔야 한다 -> terminated 상태
2.Active 상태에서 End transaction이 끝나면, buffer에 내용이 남아 있을 수 있다. 그것이 disk에 잘 반영이 되면 commit이 되고 committed상태가 된다
3.Partially commited 상태에서 h/w failure or no disk output이 발생시 Abort 발생. Failed -> Terminated
Abort = ROLLBACK , commit = COMMIT_TRANSACTION

 

The System Log

 

Abort가 되는 경우 상태를 기록해놓는 곳
log : 모든 transaction operations를 저장
Log records
1.start_transaction, T T에서 시작이 되었다
2.쓰기연산 T가 X를 쓴다, old value에서 new value로 값이 바뀌었다
3.읽기연산, T가 X를 읽는다
4.commit T
5.abort T

 

Desirable Properties of Transactions

 

ACID properties
-Atomicity : 원자성 ( 되든지 다 안되든지) 
-Consistency preservation : 일관성 (db가 일관성을 유지해야한다)
-Isolation : 고립성 (동시에 수행되는 다른 transaction에 대해 영향을 받지 말아야한다 = concurrency control)
-Durability or permanency : 영속성, 지속성 ( 한번 transaction이 commit되면 그 update는 취소가 되면 안된다)

 

Schedules of Transactions

-Schedule : 여러개의 transaction이 섞여서 수행될때 순서
서로다른 transactions의 경우 interleaved 되어 S내에서 수행될 수 있다.
하지만 Transaction내의 연산들의 순서는 바뀌어선 안된다
nonserial execution의 경우 섞여서 수행되어도 각 Ti의 순서는 유지가 되어서 수행된다

 

Schedule 예시

Conflicting Operations in a Schedule = 연산간의 충돌

conflictiong operations 조건
1. 다른 transactions에 속한다
2. 같은 DB item에 접근
3. 둘중 하나는 write 연산

Schdule이 이런 Conflict 연산들을 확인하여 문제의 발생여부를 확인한다

 

Characterizing Schedules Based on Recoverability

Conflict 연산의 존재는 Schedule의 특성을 결정짓는데 중요한 역할을 한다

-Recoverable schedules : transactions의 durability를 이론적으로 만족시켜준다
-Non '' : transaction이 commit 되었는데 recovery 과정에서 roll back되는것

-Schedule S 가 recoverable하다 = T'가 쓴 item을 T가 읽을때 T가 먼저 commit되어선 안된다.

 

recoverable한 스케줄의 예, 
WT'(x),RT(x),CT는 문제가 없어보이지만 abort T'가 발생하면 T가 읽은것은 잘못된 것이므로 문제가 생긴다.(Nonrecoverable)

 

T reads from T' in S => commit (T') -> commit(T) 를 지켜야 recoverable하다

 

recoverable 하지만 , T2가 w1(x)를 덮어버리므로 lost update 문제는 발생한다.

T2가 먼저 commit하고 T1에 abort가 발생해서 T2의 r2(X)가 invalid 값이 되버린다. nonrecoverable S

T1이 먼저 commit한다면 recoverable

recoverable한 schedule도 abort 발생시 cascading rollback문제는 피할 수 없다. cascadeless schedule : strict schedule ( cascading문제가 발생하지 않는다)

Schedule 다이어그램

Characterizing Schedules Based on Serializability

-Serializable schedules
concurrent transaction이 수행이 될때 그 수행이 정확한 schedule
serial schdules : interleaving없이 차례대로 수행 -> 항상 정확하다 ( serial과 serializable은 다름!)
nonserial schedules : interleaving 연산 -> 정확하지 않을 수있다

 

Serializability of schedules
Schedules이 정확한지 판단하는데 사용되는 개념, serial과 같진 않지만 동등한 효과가 있다.

 

serial, correct

nonserial , c에선 lost update problem 발생 X = X +M과정에서 X-N이 수행되지 않은 X로 연산됨

serializability

-Serializable Schedule
n개의 transaction으로 이루어진 Schdule S가 어떤 serial schedule과 동등하다면 그 Schdule은 serializable하다
S가 serializable 하면 S는 correct하다.

 

Equivalence of Schedules

-Result equivalence(적절하지 않은 방식)
두 Schedule의 최종state가 동일하면 두 Schedule을 동일하다고 한다.
S1,S2는 X가 100이면 같지만 다르면 달라지기 때문에 동일하다 할 수 없다, 

 

가장 안전하고 일반적인 접근
-연산에 가정이 없어야한다
-양쪽 연산이 동일하게 적용될때
Conflict,View Equivalence 고려

 

Conflict Equivalence

2개의 schedule내에 있는 conflict되는 연산들의 순서가 동일하다

S1: r,w  S2: w,r 두 Schedule은 conflict equivalent하지 않다. 

S1:w,w S2:w,w  두 Schedule은 conflict equivalent하지 않다. 

 

Conflict Serializability

Conflict serializables schedule S
-만약 어떤 serial sechedule S'과 conflict equivalent라면
-conflict한 연산들을 영향을 주지 않고 움직여서 serial schedule을 만들 수 있다면 serializable하다

Schedule D는 conflict연산들을 움직여서 Schedule A를 만들었고, Schedule A는 serial schedule이 되므로 D는 Conflict Serializable하다
Schedule C는 어떻게 해도 serial하게 만들어 줄 수 없으므로 Conflict serializable하지 않다.

 

recedence graph를 이용해 판단이 가능하다

S내의 T(transaction)에 대해서 보기 예시와 같이 화살표를 그려준다 (wr,rw,ww)

그래프에 cycle없다면 S는 serializable해진다
어떤 serial Schedule S'에서 Ti->Tj순서가 적용되면, serializable schedule 에서도 똑같은 순서가 정의될 수 있다.

 

 

rw wr ww 세가지 경우중 하나라도 발생시 그려진다.

a,b,d : conflict serializable c : not conflict serializable

conflict에 따른 graph, cycle이 존재하기 때문에 conflict equivalent한 schedule이 아니다

cycle이 없고, 위상순서가 존재하므로 Conflict equivalent한 scheudule이다

f, 위상순서는 두가지 모두 같은 의미

Testing for Conflict Serializability

 

dependency graph가 cycle이 없으면 serializable하다

-그래프에서 cycle을 찾기 힘들다
-선형 순서가 너무 많다
대부분 상업 DBMS는 Scheudule에 참여하는 모든 transaction이 규칙만 지켜준다면 correct하게 되는 규칙을 만들어 놓는다.(Concurrency control protocol)

 

Concurrency control protocols 종류

View equivalence : 제약이 conflict보다 덜하다

view equivalent는 read연산만 본다
두 Schedule에서 read연산을 읽는 값이 동일하면 그 두 Schedule은 View Equivalence하다.

1.동일한 transaction 가짐
2.S에서 Ti가 Tj가 write한것을 읽었다고 가정한다면, S'에서도 똑같은 조건을 가져야한다.

Wj(x)...Ri(x) 두 연산사이에 어떤것이 존재하든 j가 마지막으로 쓴것을 i가 읽는다면 두 Scheudle이 View Equivalence하다.

3.S에서 Y를 마지막으로 write한것이 Wk라면, S'에서도 같아야한다
두 Schedule이 y에 대해 마지막으로 write한게 Wk라면 View Equivalence하다. (이렇게 해야 나중에 read가 같으니까)

 

-두 Schedule에서 read 연산은 동일한 view를 갖는다
-Schedule이 끝났을때 DB상태가 동일해야한다
-View equivalence는 conflict equivalence보다 덜 제한적이다
-View serializable schedule S
serial S'과 view equivalent하면 serializable하다.
nonconflicting operation을 reorder해서 serial schedule 만드는게 가능

 

non conflict serializable하지만 view serializable함, 모든 read 연산이 동일한 X를 읽고, 끝날떄 write이 같으니까 ( 연산 순서를 바꿨더니 전혀 다른 Schedule이 됬으므로 non conflict serializable)

blined write : W2,W3같이 read하지 않고 먼저 write하는 경우 . Constrained write assumption(blind write을 제약한다) 만약 허용이 된다면, view serializable의 경우가 더 많아진다

Constrained write assumption이 적용된다면 View = conflict

그렇지 않다면 V.s > C.s

View serializability를 찾아내는것 또한 N.P complete한 문제 (실행시간 내에 불가능)
해결책 : conflict와 같이 protocol 사용

 

SQL에서 transaction 지원

-begin transaction에 대한 선언문은 따로 없고 시작시 실행
-commit or Rollback으로 끝낸다
-각 transaction에 대해 속성이나 특성의 정의를 선언가능
SET TRANSACTION
access mode, diagnostic area size, isolation level
diagnostic : 에러 판단

 

SET TRANSACTION statement in SQL

n : diagnostic area에서 동시에 가질 수 있는 조건 숫자
isolation level 뒤로 갈수록 통제가 심해지며, 통제가 심할수록 성능면에서 손해를 보지만 통제가 적으면 충돌문제 발생

phantom : insert나 delete연산 도중 중간 결과가 바뀌는 record