[DB] Transaction Conflict Serializability

[Schedule]

 

여러 트랜잭션들이 동시에 실행될때

각 transaction에 속한 operation 들이 실행되는 순서

 

예를 들어

transaction1이 X를 read 하고 그 뒤에 write 하고

transaction2도 X를 read 하고 그 뒤에 write 한다면

 

transaction1과 transaction2가 실행되는 schedule은 아래와 같이 다양할 수 있다

 

1) r1(x) w1(x) r2(x) w2(x)

2) r1(x) r2(x) w1(x) w2(x)

3) r1(x) r2(x) w2(x) w1(x)

4) r2(x) w2(x) r1(x) w1(x)

 

이때 1과 4처럼 transaction 하나가 끝나면 다른 하나가 시작되는 형태를

serial schedule이라고 한다!

 

---

[Serial Schedule vs Non-Serial Schedule]

 

---

[Conflict = 2개의 operation에 대해서 사용되는 개념]

 

하나의 schedule 내 존재하는 두 개의 operation에 대해 사용할 수 있는 개념

 

한 schedule 내에 있는 두 operations가 아래 세 가지 조건을 만족하면 '두 operations는 conflict하다' 라고 말할 수 있다

 

1. 두 operation이 서로 다른 transaction에 속해 있다

2. 두 operation이 같은 데이터에 접근한다

3. 두 operation 중 적어도 하나는 데이터를 쓴다(write)

 

두 개의 트랜잭션이 동일한 데이터에 접근할때 서로 간섭하거나 경쟁하는 상황 그 자체를 의미
conflict라고 해서 다 문제가 되는 것이 아님!! (충돌이라고 직역해서 무조건 부정적인거로 생각하지 말자)

conflict해도 서로의 연산을 직렬화했을때 schedule 순서(read-write)가 동일하면 그건 문제가 없는 conflict 상황

서로 다른 트랜잭션들이

동일한 데이터에 대해

접근하는 순서를 파악해보면 된다

 

이러한 operation들의 조합을 모두 고려해봐야한다!!

 

w2와 r1은 서로 다른 트랜잭션에 속해있다

w2와 r1 모두 H라는 자원에 접근한다

둘 중 하나는 write operation 이다. (w2)

 

---

[Conflict equivalent = 2개의 schedule에 대해서 사용되는 개념]

 

두 개의 Schedule에 대해

conflict 들이 동일하면

두 Schedule은 Conflict Equivalent 하다

 

그래서 찾을 수 있는 모든 conflict operation 순서조합에 대해 모두 따져봐야한다!!

그래서 해당 순서들이 두 schedule 간에 모두 동일한지 봐야한다!!

 

 

 

---

[Conflict Serializable]

 

특정 schedule에 대해 conflict equivalent한 schedule들이 존재하면

해당 schedule은 conflict serializable 하다고 한다

 

그래서 다음과 같은 질문을 할 수 있다

 

특정 schedule에 대해

1) conflict equivalent 한 스케줄이 있는지 확인하고

2) 1을 통해 해당 스케줄이 conflict serializable 한지 확인해봐라

 

or

 

특정 schedule A가 conflict serializable 한가?

이 질문은 conflict equivalent한 스케줄이 있는지 확인해보라는 것이다

즉 operation들을 조합해서 conflict equivalent한 스케줄이 있는지 검사해봐야한다

 

 

sched3 conflict

 

r2(H) w1(H)

w2(H) r1(H)

w2(H) w1(H)

 

sched2 conflict

 

r2(H) w1(H)

w2(H) w1(H)

w2(H) r1(H)

 

sched3 과 sched2의 conflict operations 순서가 모두 동일하므로!!

 

 

 

각 스케줄 내에서

서로 다른 트랜잭션 1,2가

데이터 H에 대해

트랜잭션들의 작업 순서(operation 순서 = read, write 순서) 조합을 살펴보면

 

sched4

r1(H) > w2(H)

r2(H) > w1(H)

w2(H) > w1(H)

 

sched2

r2(H) > w1(H)

w2(H) > r1(H)

w2(H) > w1(H)

 

이렇게 4가지가 나오는데 여기서 (r1-w2)랑 (w2-r1) 이 다른 순서이다

따라서 not conflict equivalent 이다!! 

 

 

결론은

만약 하나의 schedule이

serial schedule가 conflict equivalent

즉, 트랜잭션들이 공유하는 자원에 대해 트랜잭션들이 작업하는 순서가 동일하다면

이를 conflict serializable이라고 함!!