[DB] 동시성 제어

Concurrency control(동시성 제어)

데이터베이스가 동시성 제어를 하려면 conflict serializable 또는 view serializable 을 지원해야함

그리고 기왕이면 recoverable 하고 cascadeless 함을 지원하면 좋음

스케쥴을 실행한 뒤에 serializability 를 알게 되는 것은 너무 늦기 때문에 Concurrency control protocol 을 정의하고, 이대로 실행하면서 serializability, recoverable 을 체크함

이 규약을 실행시켜주는 존재 = Concurrency control

 

Lock based protocol

X-lock = 읽기/쓰기 모두 가능한 lock

S-lock = 읽기만 가능한 lock

 

Lock compatibility matrix

서로 다른 트랜잭션이 동시에 lock 을 요청할 때 모두가 동시에 락을 얻는 경우는 모두 S락인 경우임

만약 서로 incompatible 한 락을 요청한다면 먼저 잡힌 락을 소유한 트랜잭션이 해당 락을 release 할때까지 대기

 

 

Two-phase locking protocol

Phase1 : growing phase : 락을 얻기만 하는 페이즈

Phase2 : shrinking phase : 락을 풀기만 하는 페이즈

Lock points : 트랜잭션 내에서 가장 마지막에 락을 획득한 순간

 

이 프로토콜은 conflict serializability 를 보장함 하지만 모든 conflict serializable 한 스케쥴을 만들어낼 수는 없음

Cascading rollback 이 일어날 수 있음

 : 이를 막기 위해서는 Strict two-phase protocol을 사용해야함 : 한 번 얻은 X-lock 은 commit / abort가 일어나기 직전까지는 풀지않고 갖고 있는 프로토콜

 

더 엄격한 Rigorous two-phase locking protocol 은 S-lock 또한 commit / abort 직전까지 풀지않고 갖고 있음 : 이 프로토콜이 주로 사용됨

 

two-phase locking protocol 은 데드락이 발생할 수 있음

 

Lock conversion

Phase1 : 락을 얻는 페이즈이므로 S-lock 을 X-lock 으로 업그레이드 가능함 (downgrade 는 불가능)

Phase2 : 락을 놓아주는 페이즈이므로 X-lock을 S-lock 으로 다운그레이드 가능함 (upgrade 는 불가능)

 

2PL 이 conflict serializablilty 를 보장함을 증명하기

2PL 이 conflict serializability 를 보장하지 않는다고 가정해보자.

2PL로 non-serializable 한 스케쥴 T0, T1, ... , Tn 을 만들었을때 이 스케쥴의 precedence graph의 사이클 유무를 판단하면 사이클이 있을 것이다. 그 사이클을 T1 -> T1 -> … -> Tn -> T1 이라고 하자. 그리고 ai 를 Ti의 락을 마지막으로 얻은 시점인 lock point 라고 하자. 그렇다면 모든 트랜잭션 Ti -> Tj 에 대해서 ai < aj 가 성립하며 우리의 사이클 T1 -> T2 -> … Tn -> T1 는 a1 < a2 < … < an < a1 을 만족해야한다. 하지만 a1 에 대해서 이는 만족하지 않으므로 모순이다.

 

Automatic Acquisition of Locks : 자동 lock 획득 : 명시적으로 락 획득을 요청할 필요가 없음

만약 어떤 트랜잭션이 Q의 S-lock 에 대해 read 하고자하면 다음과 같이 처리됨

if (이미 S-lock을 가짐) -> read(Q)

else ->

if (다른 트랜잭션이 Q에 대해 incompatible 한 락을 갖고 있음) -> 대기 -> 락 획득 -> read(Q)

else -> 락 획득 -> read(Q)

 

X 락에 대해서는 다음과 같음

if (이미 X-lock을 가짐) -> read(Q)

elif (이미 S-lock을 가짐) ->

if (다른 트랜잭션이 Q의 X-lock에 대해 incompatible 한 락을 갖고 있음) -> 대기 -> 락 업그레이드 -> read(Q)

else -> 락 업그레이드 -> read(Q)

else ->

if (다른 트랜잭션이 Q의 X-lock에 대해 incompatible 한 락을 갖고 있음) -> 대기 -> 락 획득 -> read(Q)

else -> 락 획득 -> read(Q)

 

Locking 구현

Lock-Manager 라는 독립된 프로세스를 통해 구현하며, 트랜잭션이 해당 프로세스에 락을 요청함 -> 락 매니저로부터 응답이 올때까지 대기함

락 매니저는 데드락 발생 시 롤백함. 락 획득 여부를 테이블로 관리함 (in memory hash table)

 

 

해시 테이블의 key 는 DB, Table, Record 등 락의 대상이 되는 객체

해석 : Record I4의 lock 을 T1이 갖고있으며, T23 이 대기중이다.

특정 트랜잭션이 rollback 되었을 때 lock 을 해제시켜주어야하는데 그 탐색 범위를 줄이기 위해 트랜잭션 노드들끼리 연결 리스트로 연결되어 있음

 

데드락

Starvation(기아)

특정 X-lock 이 계속 롤백(Repeatedly rolled back) 되거나 lock 을 아예 얻지 못하는 현상

 

데드락 현상은 피할 수 없지만 기아현상은 피할 수 있음

 

Graph based protocol

그래프 기반 프로토콜도 사실 락 베이스 프로토콜의 일환임

D = {d1, d2, …, dn}, di가 dj 보다 반드시 먼저 실행되어야하는 부분 순서 조건을 만족하는 D에 대해서 di -> dj 간선을 그림

그러한 D는 directed acyclic graph 이며 이를 데이터베이스 그래프라고 부름

실제로 쓰기는 힘들지만 tree 기반의 index 에 주로 사용됨

 

Tree based protocol

그래프 기반 프로토콜의 일환

오로지 X-lock 만 존재하며 데이터 Q에 대해서 Ti 가 락을 걸려면 반드시 Ti가 Q의 부모에 대한 락을 갖고 있어야함

two-phase locking과는 다르게 언제든 락을 얻고, 풀 수 있음

한 번 락을 걸고, 풀었다면 해당 트랜잭션은 다시는 그 락을 얻을 수 없음

 

예제

Tree protocol 은 conflict serializability 를 보장하며 deadlock 에서 안전함(단방향 접근이기 때문 = 반드시 부모의 lock이 있어야하고, tree는 순환이 없기 때문)

하지만 recoverability와 cascade rollback 을 지원하지 않음 (언제든지 unlock 을 할 수 있기 때문에)

굳이 접근하지 않아도 되는 데이터(Parent) 에 대해 락을 얻어야하므로 오버헤드가 큼

따라서 waiting time 이 증가하고 concurrency 가 떨어짐

 

Multiple Granularity locking(MGL)

락의 단위를 다르게 가져가는 기법

데이터베이스는 크게는 DB, Table 작게는 Record 단위로 락을 얻고 풀 수 있게 함

 

Fine granularity : 레코드 단위로 잘게 쪼개어 락을 관리 : 동시성 향상, 락 오버헤드 증가

Coarse granularity : 테이블처럼 큰 단위로 락을 관리 : 동시성 하락, 락 오버헤드 하락

Multiple granularity : Find, Coarse 를 적절히 섞어 사용

 

Intention lock

노드 N에 대해 Intention lock 을 건다는 것은 미래에 N의 하위 노드에도 락을 얻을 것이다 라는 명시임

• IS : Intention Shared Lock
• IX : Intention Exclusive Lock
• SIX : Shared + Intention Exclusive Lock = S 락을 걸면서 IX락도 거는 것

어떤 노드에 락이 걸리게 되면 해당 노드의 모든 부모 노드에 적절한 Intention lock 을 걸게됨

예를 들어 r222에 S-lock 을 걸게되면 p22, R2, DB에 IS 락이 걸리게되며, 나중에 이들이 락을 얻을 때 도움이 됨

DB가 나중에 S-lock을 얻고자 했다면 IS락이 있으므로 락을 얻을 수 있음

하지만 X-lock 을 얻고자 한다면 IS락이 있으므로 락을 얻을 수 없음(내부 자식 중 S 락을 갖고 있는 자식이 있다는 뜻이며, X-lock 은 S-lock 과 incompatible 하기 때문)

 

목적 : 큰 단위의 granularity에 락을 걸 때 하위 노드의 모든 락의 compatible을 검사해야 하는데 이 오버헤드를 줄이기 위함

 

 

MGL 동작 방식

• 트리의 루트 노드가 가장 먼저 lock 에 걸려야함 (어떤 락이든 상관 X)
• 노드 Q에 S 또는 IS 락을 걸려면 그 부모 노드의 IX 또는 IS 락을 가진 상태여야함
• 노드 Q에 X, SIX, IX 락을 걸려면 그 부모 노드의 IX 또는 SIX 락을 가진 상태여야함
• Two-phase 를 따르기 때문에 어떤 락이든 해제한 적이 있다면 그 뒤로는 락을 얻는 행위는 하지 못함
• 노드 Q의 락을 해제하고 싶다면 하위 노드 중 락이 걸린 노드가 없어야함