[DB System 이론] Validation-based protocol(Optimistic Concurrency Control, OCC)

concurrency control을 위한 마지막 방법을 알아보자.

 

Validation-based protocol(Optimistic Concurrency Control, OCC)

이전까지는 한번에 올바른 스케줄을 생성하는 방식이다.

하지만 이 방식은 일단 만들고 유효한지 확인해본다.

기본적으로 잘 만들어졌을 거야 라는 낙관적인 생각을 기반으로 한다.

그래서 이름에 optimistic이 들어가는 것이다.

 

이 방법은 read가 많을 때 많이 사용한다.

read가 많으면 아무렇게나 스케줄을 만들어도 conflict가 적게 발생할 것이기 때문이다.

이렇게 read가 많은 기능의 예시로는 현재 데이터를 읽어 통계 처리하는 OLAP(Online Analytical Processing)같은 것이 있다.

 

그러나 write가 약간 포함되어 있을 수도 있기 때문에 validation과정이 필요하다.

 

<validation 개요>

OCC는 하드디스크에 있는 데이터가 버퍼(shared buffer)로 올라오는데 여기에 직접 수정을 하지 말고,

트랜잭션이 동작하는 쓰레드의 로컬에 copy를 만들어서 여기서 수정한다.

write가 나오면 그때 버퍼에 써주고, 이때가 되어야 다른 트랜잭션이 볼 수 있다.

 

OCC는 여기서 write동작 바로 전에 잠시 멈춰서 write를 해도 문제가 없는지 확인한다.

대신 매번 검사하면 너무 오버헤드가 크기 때문에 write를 뒤로 몰아놓는다.

막판에 버퍼에 모든 내용을 몰아서 반영하는데, 이때 반영하기 전에 validate한지 검사한다.

만약 문제가 있으면 롤백할 필요없이 그냥 로컬의 내용만 버리면 된다.

---

<validation 단계>

1. read and execution phase

데이터를 읽어 로컬로 가져온다. 여기서만 수정을 한다.

 

2. validation phase

validation test를 한다. concurrent한 동작들이 serializability를 훼손하지 않는지 확인한다.

 

3. write phase

DB에 실제로 반영하는 과정이다.

 

2,3번은 하나의 묶음(validation & wirte)으로 같이 실행된다고 가정하자.

 

 

---

<validation test 과정>

트랜잭션은 3가지 종류의 타임스탬프를 가진다.

 

StartTS : 기존에 알고 있던 타임스탬프. 트랜잭션이 시작했을 때의 타임스탬프

ValidationTS : execute단계 이후 validation으로 넘어갈 때의 타임스탬프

이 타임스탬프를 기준으로 serial 순서를 생각한다.

FinishTS : DB업데이트까지 끝났을 때의 타임스탬프

 

또 2가지의 set을 가진다.

 

read set : 이 트랜잭션에 의해 읽어지는 데이터들의 집합

write set : 이 트랜잭션에 의해 써지는 데이터들의 집합

 

---

"나는 나보다 먼저 시작한 트랜잭션만 신경쓰겠다.

나보다 늦게 시작한 트랜잭션은 너가 나를 신경써라."

라는 기본 아이디어를 가지고 동작된다.

 

내가 트랜잭션 $T_i$, 다른 트랜잭션을 $T_k$라고 하자.

나보다 먼저 시작한 모든 트랜잭션에 대해, 즉 $TS(T_k) < TS(T_i)$일 때, 아래 단계를 거친다.

 

나보다 먼저 시작한 애가 내가 시작한 시점보다 더 이전에 끝났다면

둘이 동시에 수행되는 시간대가 없는 것이므로 신경쓸 필요 없다.

$FinishTS(T_k) < StartTS(T_i)$

 

그러나 위의 식을 만족하지 않는다면 겹치는 시간대가 있다는 것이다.

겹친다고 항상 다 문제는 아니고, 누군가 write한 내용을 다른 트랜잭션이 write/read했을 경우가 문제이다.

이 validation과정에서는 어떤 명령어를 누가 먼저 실행되었는지 모르기 때문에 이 경우 그냥 나를 롤백시킨다.

로컬의 내용을 버려서 버퍼에 수정을 반영하지 않는 것이다.

 

따라서 검사할 것은 conflict가 발생할 수 있는지 확인하는 것이다.

1. $T_k$의 wirte set이 나의 read set과 교집합이 없는지 (쟤가 쓴 데이터가 나한테 영향이 없다)

2. $T_k$가 write phase까지 끝나고 나서 나의 validation phase가 시작했는지 (내가 쓴 데이터가 쟤한테 영향이 없다)

 

이 두가지 조건을 모두 만족하면 ($StartTS(T_i) < FinishTS(T_k) < ValidationTS(T_i)$)

validation test를 통과하는 것이고 아니라면 내가 롤백된다.

---

<예시>

아래 예시를 보자.

각 트랜잭션의 set은 아래와 같다.

T25 : read set = (A,B), write set = 0

T26 : read set = (A,B), write set = (A,B)

 

T26(나)입장에서 T25(다른 트랜잭션)에 대해 검사하는 것이다.

1. 둘이 겹친다

2. T25의 write set은 0이므로 T26에 영향이 없다. + T26의 validation이전에 T25가 끝났다.

따라서 문제없는 스케줄이다.

 

 

---

정리하면 최종 과정은 아래와 같다.

 

1. 로컬 카피

2. write 뒤로 몰아놓기

3. DB에 반영하기 전에 validation 검사 진행

3-1. $TS(T_k) < TS(T_i)$인 모든 트랜잭션에 대해

3-2. $FinishTS(T_k) < StartTS(T_i)$이 아니고,

3-3. $StartTS(T_i) < FinishTS(T_k) < ValidationTS(T_i)$라면

test통과, 아니면 $T_i$롤백