[DB System 이론] Multiple Granularity Locking Protocol, Timestamp-Ordering Protocol(TSO), Thomas’ Write Rule

이전글을 보고 오면 더 쉽게 글을 읽을 수 있다.

[DB System] Two-Phase Locking(2PL) Protocol, Lock table

이전 글은 locking을 사용한 concurrency control 기법에 대해 알아봤었다.

이번 글은 locking을 사용하는 방법을 조금 더 알아보고,

locking을 사용하지 않는 방법도 알아보자.

---

graph-based protocol

역시 락을 사용하는 방법 중 하나이다.

추가 정보인 "dbms가 각 데이터에 접근하는 순서를 정해놓은 정보"가 있다면 이 방법을 사용할 수 있다.

예를 들어 데이터A에 접근 전에 데이터B를 접근해야한다고 정하는 것이다.

만약 두 트랜잭션이 각각 A와 B에 대한 lock이 있고 서로 B와 A에 대한 락이 필요하다면 deadlock이 발생하는데,

이 방식을 사용하면 이런 일을 방지할 수 있다.

 

위 정보를 나타내는 database graph가 concurrency control을 위한 정보로 제공이 된다.

 

이 graph-based protocol중 그래프가 트리 구조일 때 특별히 사용하는 tree protocol이 있다.

 

---

tree protocol

이 protocol은 아래 4개의 규칙을 따른다.

1. 첫 락은 아무노드에나 잡을 수 있다.

2. 이후로는 부모가 락이 잡혀있어야 그 대상에 락을 잡을 수 있다.

3. 락을 제거하는 것은 아무때나 가능하다.

4. 락을 풀고나서는 다시 잡을 수 없다.

이 방식은 conflict serializability를 보장한다.

 

장단점을 조금 살펴보자.

<장점>

1. conflict serializability를 보장한다.

2. deadlock이 발생하지 않는다.

3. 2PL방식보다 lock을 일찍 푼다. 따라서 기다리는 시간이 감소하고 concurrency가 증가한다.

 

<단점>

1. recovarability를 보장하지 않고, cascade rollback을 방지하지 않는다.

2. 내가 실제로 부모에 접근할 필요없는데 자식에게 접근하기 위해 부모까지 락을 잡아야한다. 이러면 concurrency 떨어진다.

 

<기타>

2PL에서 불가능한 스케줄도 트리 프로토콜에서는 가능, 그 반대도 가능하다.

 

 

1번 단점을 해결하기 위해 commit dependency라는 것을 도입했다.

 

<commit dependency>

기본 원리는 이전 글에서 설명한 것처럼,

write한것을 읽고 커밋했는데 wirte쪽에서 abort하면 문제가 된다.

따라서 커밋하고 읽으라고 하는 것이다.

 

내가 아직 커밋되지 않은 데이터를 읽게되면 그 데이터를 write한 트랜잭션에 대해 commit dependency가 생긴다.

commit dependency의 모든 트랜잭션들이 commit 했다고 나와야 나도 커밋을 할 수 있게 된다.

아직 commit 되지않은 트랜잭션이 있다면 나도 commit을 보류한다.

그러다가 dependency가 있는 트랜잭션이 abort되면 rollback을 해야한다.

 

---

deadlock prevention

OS를 공부했다면 알겠지만 데드락은 4개의 조건이 충족되야만 발생한다.

그래서 데드락을 막기 위해 4개 조건 중 적어도 하나가 충족되지 못하게 하면 된다.

DB에서도 아래처럼 비슷하게 해결이 가능한 부분들이 있다.

 

circular wait을 DB에서는 tree protocol로 해결한다.

hold and wait을 DB에서는 필요한 데이터에 대해 모두 락을 얻어야 트랜잭션을 시작한다.

 

Transaction timestamp-based schemes

DB는 OS보다 훨씬 다양한 정보가 있다.

OS에는 없는 모든 트랜잭션의 시작시간을 기록한 timestamp라는 것이 있는데,

이걸 이용하는 방법이 Transaction timestamp-based schemes이다.

 

timestamp를 이용해 DB의 deadlock을 막는 2가지 방법이 있다.

이제부터 timestamp값이 크면 시작된지 얼마 안된 트랜잭션이므로 '젊다/어리다'라고 표현하고,

timestamp값이 작으면 예전에 시작된 트랜잭션이므로 '늙었다'라고 표현하자.

이 방법은 노인우대 방법처럼 생각하면 이해가 쉽다.

 

1. wait-die : 어린애가 가지고 있는 락이 풀리기를 늙은이가 기다리는 것이다.

반대의 경우는 젊은 애를 롤백시킨다.

젊은이로부터 강제로 락을 뺏지는 않음(non-preemptive)

 

2. wound-wait : 강제로 락을 뺏는다.

노인이 젊은애가 가지고 있는 락이 필요하면 강제로 롤백시키고 락 가져온다.(preemptive)

반대의 경우에는 기다린다.

 

이 두가지 방법 모두 starvation이 있을 수 있다.

따라서 롤백이 되는 트랜잭션이라도 처음의 timestamp를 가지고 계속 다시 시작한다.

이렇게 하면 롤백을 많이 당하게 되면 점점 늙은이가 되고 점차 노인우대를 받아 우선순위가 높아질 것이다.

 

그런데 좀 생각해보면 데드락이 아니고 단순히 조금 기다리면 반환될 락에 대해서도

그냥 롤백을 시키는 것이 좀 비효율적이다.

 

lock timeout-based schemes

이 방식은 위 방법처럼 바로 롤백시키지 않고 락이 풀리기를 기다리는 방법이다.

기다렸는데도 너무 락이 반환되지 않는다면 롤백시킨다.

이 방법도 데드락임을 확정적으로 알고 처리하는 것이 아니다.

역시나 쓸데없는 롤백이 발생하고 효율 떨어진다.

starvation도 발생가능하다.

 

deadlock detection

이번에는 데드락을 확인하고 처리하는 방식도 있다.

 

<wait-for graph>

어떤 트랜잭션이 어떤 트랜잭션의 락이 풀리기를 기다리는지를 그래프로 그린다.

이 그래프에서 사이클이 보이면 데드락이다.

이 중 비용이 가장 적을 애를 롤백시켜 해결한다.

롤백을 할 때도 두 가지 선택지가 있다.

total rollback, partial rollback

starvation을 막기 위해 가장 나이 많은 애는 victim안되게 설정한다.

---

Multiple Granularity Locking Protocol

이름처럼 이 프로토콜도 락을 사용한다.

 

이 방법의 아이디어는 여태까지 개별 데이터(튜플)에 대해서만 락을 잡았었는데, 이 범위를 늘려보자는 것이다.

어떤 테이블 전체를 스캔해야하는 일이 있으먼 이 각각의 튜플에 락을 잡지 말고 테이블 전체에 락을 크게 한 번만 잡는게 더 효율적일 수 있다.

 

Granularity Hierarchy

그래서 lock의 단위를 조절할 수 있다.

DB전체에 대한 lock부터, Area lock, File lock, Record lock처럼 다양한 범위의 lock이 있다.

아래 그림처럼 범위에 따라 계층구조를 그래프처럼 나타낼 수 있다.

이런 방식을 도입하면 자연스럽게 몇가지 해결해야할 의문이 생긴다.

 

1. 어떤 하위 노드에 락을 걸 수 있는지 없는지 어떻게 체크할 것인가?

 

2. 어떤 노드보다 더 상위의 노드에 락을 잡으려고 할 때 어떻게 이를 판단할 수 있는가?

 

1번은 락을 걸려는 노드의 조상들을 계속 확인했을 때 락이 하나도 걸려있지 않으면 가능하다.

2번은 이 노드의 모든 하위노드에 락이 없으면 가능하다.

 

말은 쉽지만 이게 오버헤드가 크다.

따라서 사람들은 좋은 해결책을 도입헀다.

 

Intention Lock Modes

그래서 나온게 intention lock modes이다.

기존의 S,X lock에 IS, IX, SIX라는 lock을 추가로 도입했다.

 

각 lock의 의미는 아래와 같다.

IS : 하위노드에 S lock을 걸 의도가 있다

IX : 하위노드에 X lock을 걸 의도가 있다

SIX : 현재 노드에는 S lock을 걸고, 하위노드에는 X lock을 걸 의도가 있다

 

이처럼 의도를 얘기하기 때문에 이 방법의 이름이 intention이라고 지어졌다.

근데 의도라는 말이 어떤 의미인지 잘 이해가 되지 않을 수 있다.

 

lock은 상위노드부터 걸면서 내려온다.

내가 가장 작은 데이터 단위인 튜플에 S lock을 걸려고 한다면,

그 상위노드부터 '내 하위노드에 S lock을 걸거야'라는 시그널이 필요하다.

이미 중간의 어떤 노드에 X lock이 걸려있으면 S lock을 거는 것에 실패한다.

실패 여부에 상관없이 '나는 S lock을 걸 의도가 있었던 것'이기 때문에 의도라는 단어가 사용되었다.

 

이전 글에서 X,S락에 대해 어떨 때 두 락이 양립가능한지 나타낸 표를 봤을 것이다.

이번에는 총 5개의 lock에 대해 표를 살펴보자.

먼저 어떤 종류던 S계열 lock끼리의 lock은 동시에 존재할 수 있다.

표의 이해를 위해 IS, IX가 만났을 때의 경우를 예시로 살펴보자.

어떤 노드에 대해 하위노드 두 개가 서로 같은 노드가 아니면 S lock과 X lock은 각 노드에서 존재할 수 있다.

따라서 IS,IX는 양립가능하다.

 

하지만 만약 우연히 S가 걸려있는 노드에 X를 걸려고 생각해보면,
먼저 이 충돌 전까지는 IX를 마킹하며 하위노드로 이동한다.

그러다가 이 충돌 상황을 만나면 방금까지 표시했던 IX를 모두 지운다.

이러면 IX,IS에 true라고 적지 못하는 것 아닌가? 라는 생각이 든다.

 

하지만 충돌 상황은 S lock에 X lock을 걸려고 했던 것이기 때문에

이때는 IX,IS칸이 아니라 S,X가 만나는 칸의 false를 보는 것이다.

 

결론적으로 아래의 룰을 따라서 락을 걸면 된다.

 

<규칙>

1. 양립가능한지는 위 표를 따른다.

2. 상위 노드부터 락이 걸려야한다.

3. 어떤 노드에 S나 IS를 잡고 싶으면 그 부모 노드가 IX,IS여야한다.

4. 어떤 노드에 X,IX,SIX를 잡고 싶으면 그 부모 노드가 IX,SIX여야한다.

5. 락을 풀면 다시 잡을 수 없다.

6. 락을 푸는건 하위 노드에 하나도 락이 없어야 가능하다.

 

<lock granularity escalation>

만약 어떤 노드의 하위 노드 100개 중 90개가 락이 잡혀있으면

큰 범위의 락 하나로 단순화하는 것을 얘기한다.

 

 

<insert delete operation>

여태까지는 read,write에만 신경을 썼었다.

하지만 insert, delete도 있는데, 이런 경우는 어떻게 할까?

두 가지 경우 모두 X락을 잡으면 된다.

---

이전글에서부터, 이번글의 graph-based protocol,Multiple Granularity Locking Protocol처럼 lock을 사용하는 방법을 알아봤다.

이번에는 lock을 안 쓰고도 concurrency control이 가능한 방법을 보자.

 

timestamp-based protocol

위에서 얘기했던 timestamp를 사용하는 방법들이 몇 개 있다.

먼저 시작한 애가 먼저 끝나도록 timestamp를 기준으로 serial한 스케줄로 바꿨을 때의 순서가 정해진다.

이전에 설명했던 2PL은 growing phase가 끝났을 때의 상태를 기준으로 serial 순서가 정해진다.

 

모든 데이터는 두개의 timestamp가지고 있다.

R-timestamp : 이 데이터에 대해 가장 최근 read를 한 트랜잭션의 timestamp

W-timestamp : 이 데이터에 대해 가장 최근 write한 트랜잭션의 timestamp

 

---

Timestamp-Ordering Protocol(TSO)

모든 read,write 동작에 대해서 conflict난다면 늙은 명령어 먼저 되도록 보장하겠다는 것이 목적이다.

 

쉬운 이해를 위해 예시를 살펴보자.

 

1. read(Q)

만약 어떤 트랜잭션T가 데이터 Q에 대해 read(Q)를 한다고 하자.

read와 conflict를 만들 수 있는 것은 write이므로 write가 언제 되었는지가 중요하다.

 

이 트랜잭션의 타임스탬프 값 TS(T) < Q의 W-timestamp값 이라면

T보다 더 젊은 애가 이미 Q에 write를 한 것이다.

이러면 T는 예전 값을 read하게 되므로 read를 하지 않고 rollback을 한다.

 

반대로 TS(T) >= Q의 W-timestamp 라면

아무 문제 없다.

정상적으로 read를 한 후 Q의 R-timestamp의 값을 max(R-TS(Q), TS(T))로 바꾼다.

 

2. write(Q)

이번에는 write을 한다고 하자.

write은 read,write 둘 모두와 conflict가 생긴다.

TS(T)<R-TS(Q)

이 경우 자신보다 젊은 애가 이미 read를 해버린 상태이므로 잘못되었다.

내가 늙은 트랜잭션이므로 내가 write를 한 값을 젊은 애가 read를 해야하기 때문이다.

이 경우는 쓰기를 하지않고 롤백시킨다.

 

TS(T)<W-TS(Q)

이것도 비슷한 이유로 문제가 있다.

나보다 젊은 트랜잭션이 write한 값을 내가 예전 값으로 write하려는 꼴이기 때문이다.

역시 롤백을 해야한다.

 

위 두 경우가 아닐경우 write이 정상적으로 실행된다.

즉 나보다 나중에 데이터를 건드려야하는 젊은 애들이 나보다 먼저 건든 적이 없다는 뜻이다.

 

---

아래 예시를 보자.

 

편의를 위해 T25의 타임스탬프 값을 25,

T26의 타임스탬프 값을 26이라고 가정하자.

위 규칙에 따라 타임스탬프 값을 써보면 아래처럼 된다.

이 예시는 정상적인 스케줄이다.

 

이번에는 잘못된 예시를 보자.

T27의 read(Q)를 실행하면 R-TS(Q)=27 가 된다.

T28의 write(Q)를 실행하면 W-TS(Q)=28 이 된다.

여기까지는 정상적이다.

하지만 T27의 write(Q)가 실행되면,

현재 Q의 W-TS값은 28인데, 이 값은 T27의 타임스탬프 값인 27보다 크기 때문이다.

 

serial 하게 실행한다면 T27이후 T28이 실행되어야 한다.

그럼 T27이 write한 값을 T28이 갱신하는게 정상적인 것이지만, 이 경우 그 반대가 된다.

---

Thomas’ Write Rule

위의 TSO에서 조금 더 개선된 방법이다.

T가 Q에 대해 write를 하고 싶다고 생각해보자.

 

TS(T) < R-TS(Q)

이 경우는 기존 TSO와 같이 이미 내가 write하기 전에 더 젊은 애가 이 데이터를 읽은 것이므로 롤백을 한다.

 

TS(T) < W-TS(Q)

이 경우는 내가 write하기 전에 더 젊은 애가 이미 write를 한 것이다.

여기서 내가 write를 해버리면 더 오래된 값을 대입하려는 꼴이므로 원래는 롤백을 했었다.

하지만 어떤 경우에는 이 명령을 그냥 무시해도 된다.

 

따라서 이 방법이 적용가능한지를 판단하는 방법은 아래와 같다.

 

1.  TS(T) >= R-TS(Q) 를 만족하는지 확인한다.

더 최신의 트랜잭션이 아직 Q를 읽지 않았다는 의미이다.

이미 읽어버렸다면 이 룰을 적용할 일이 없이 바로 롤백을 해야한다.

 

2. TS(T) < W-TS(Q) 가 만족되는지 확인한다.

자신보다 더 젊은 트랜잭션이 write를 했어야 내 write를 무시를 할 수 있다.

 

이 두 조건을 합치면 R-TS(Q) <= TS(T) < W-TS(Q) 이다.

이 의미는 Q를 쓴 젊은 트랜잭션이 Q를 읽은 적은 없다는 것이다.

만약 이 트랜잭션이 Q를 읽었다면 그 값이 내가(더 늙은 트랜잭션) write한 값일 수 있기 때문에 write의 의미가 있어 무시할 수 없다.

하지만 읽지 않았기에 내 write는 무시해도 되는 것이다.

이 방식은 concurrency를 더 높여준다.