1. 동시성 제어 방식 (Concurrency control) : Lock-based protocols
이 방식을 제어 프로토콜 중 이 방식이 성능이 좋아서 가장 많이 쓴다
concurrent access를 제어하는 메카니즘으로, locking protocol에 맞는 가능한 스케쥴 중 일부분만 사용하게 제한하는 것이다.
lock-based protocol에는 2가지 lock mode가 있는데, exclusive mode (X lock, write lock) , shared mode (S lock, read lock)이 있고, 다음과 같은 lock compatibility를 갖는다.
이 방식에서 Transaction은 lock에 대한 request가 수용되었을 때 진행된다(lock을 받고 진행됨). 또한 다른 transaction이 가지고 있는 lock들에 대해서 자신의 lock이 compatible 할 때만 transaction이 수용 된다. 만약 요청에 대해서 lock을 받지 못한다면, incompatible lock이 release될 때 까지 기다려야 한다.
실제 operation에는 어떻게 진행될까? 다음과 같은 예시를 확인해보자.
read를 위해서 lock을 받고, 연산 후에 unlock하여 release해주고, B는 그것을 기다렸다가 이후에 처리하는 예시이다.
하지만 이 방식은 serializability를 보장해주지는 못하는데, 그 이유는 A와 B를 읽는 것과 A+B를 출력하는 사이에 다른 transaction의 write가 존재할 수 있기 때문이다.
그렇다면 이를 방지해주기 위해서 추가직인 protocol이 필요하다 그 예시로 Two-Phase Locking Protocol(2LP)와 Automatic acquisition of locks와 Tree-based protocol을 소개하고자 한다.
2. Two-Phase Locking Protocol (2LP)
Two-phase locking protocol은 다음과 같은 두가지 단계로 나뉜다.
Phase 1 : Growing phase
Phase 2 : Shrinking phase
여기서 growing과 shrinking은 lock의 범위와 강도에 대한 것이다. 이 lock에 대한 phase가 이분화 된 방식이 Two-Phase Locking Protocol이다. 단, 이 phase들은 아래의 사진과 같이 순서가 바뀌지도, 추가 및 반복되지도 못한다.
이 방식은 isolation관점에서의 conflict serializable schedule을 보장하지만 atomic, durability, recovery에 관점으로 보았을 땐 추가적인 제한이 필요하다(Cascading rollback은 가능하지만 다른건 안된다). 따라서 ACID를 위해서 조금 더 규제가 강한 strict two-phase과 Rigorous two-phase locking이 존재한다.
strict two-phase는 exclusive locks를 잡으면 이 lock을 transaction이 끝날 때 까지[commits/aborts] 놓지 않는 방식이고, Rigorous two-phase locking은 모든 lock을 transaction이 끝날 때 까지 놓지 않는 방식이다.
하지만 이 모든 Two-phase locking은 deadlocks를 방지해주지는 못하고, 모든 경우에 대해서 conflict serializable schedule를 생성할 수 있는 것은 아니다! (그 중 일부분만 가능한것이다~)
Issue : Lock Conversions
lock을 상황에 따라서 upgrade / downgrade 하는 것! two phased locking protocol에서는 upgrade는 phase1에서만, downgrade는 phase2에서만 가능하다
이 방식은 serializabilty를 보장한다.
3. 2PL이 어떻게 conflict serializability를 보장하는가?
귀류법을 통해 2PL이 conflict serializability의 보장을 증명할 수 있따.
위와 같은 cycle transaction 케이스를 보자. 모든 transaction에 대해서 T_i -> T_j로 넘어간다고 할 때, lock을 보유하고 있는 시간인 a_i보다 그 다음 연산이 lock을 소유하는 a_j보다 적다 / 늦다. (즉, two phase locking 때문에 T_i -> T_j이 a_i < a_j이다 [충돌하지 않게 하는 locking 과정 때문에])
이를 모든 노드에 대해서 확장해보면, a_0 < a _1 < a_2 ... < a_n < a_0이고, a_0 < a_0라는 모순이 생기므로, cycle이 존재할 수 있다. 따라서 2PL은 non-serializable schedules를 만들 수 없다.
4. Automatic acquisition of locks
Lock을 잡고 있다면 연산하고, 그렇지 않다면 기다리는 방식
write는 lock compatibility때문에 lock을 기다리는 방식이나, read로 먼저 upgrade를 방식이 있는것이다.
Locking의 구현은 Separate process로 구현되기도 하고, 내장되기도 한다.
Lock table이라는 data item의 이름을 기준으로 하는 hash table을 이용하여 관리한다. 다음은 lock table의 예시이다.
Lock table
T1와 T8이 하나의 transaction에 granted되었다는 것으로 보았을 때 반드시 Read lock이다
5. Lock이 야기하는 문제
Deadlock : Lock based system에서 어쩔 수 없이 발생하는 현상으로 서로 무한정으로 기다리는 상황이다.
Starvation : Deadlock과 다르게 잘못 설계될 때 발생하는 문제이다. read되고 있는 item에 대해서 transaction에 대해서 X-lock을 기다릴 때, 다른 transaction에서 read 요청할 때, read lock을 먼저주는 현상이다.
6. Tree-based protocol
Graph-based protocol : Data에 대해서 partial order가 존재 할 때 쓰일 수 있다.
여기서 partial order란? : d_i -> d_j라는 데이터가 존재한다면, d_i가 d_j보다 반드시 먼저 접근되도록 하는 규칙
Tree-based protocol
특정 area에서만 쓰인다~ Graph-based protocol의 한 종류이다.
초기에는 lock을 아무거나 잡을 순 있지만, tree의 partial order에 따라 아래의 노드들만 lock을 잡을 수 있도록 하는 방식이다. lock을 푸는것은 아무거나 가능하다
이 방식은 Conflict serializability를 보장하고 deadlock으로 부터 자유롭다는 장점이 있다. 또한 two-phase와 다르게 Unlocking을 아무곳에서 할 수 있으므로 waiting time이 줄고 concurrency가 향상된다는 장점이 있다.
하지만, recoverability와 cascade를 보장해주지 못하고, Tree의 order에 따라 lock을 잡을 수 있으므로 Transaction 불필요 한 lock을 잡아야 한다는 단점이 있고, 또한 데이터 간의 순서가 정의 된 경우에만 사용할 수 있어서 인덱싱 할 때 주로 쓰인다.
two-phase locking에서 가능한 것이 tree protocol에서는 불가능 할 수 있다.
MGL Example
t11에 대해서 연산하고 싶을 때 R1을 먼저 locking한다. 이 과정에서 R1이 locking되므로 R1의 다른 child인 t12와 t13에 대한 transaction도 wait하게 한다.
'학교 공부 > 데이터베이스' 카테고리의 다른 글
DynamicSQL와 StaticSQL의 차이 (0) | 2021.05.05 |
---|---|
오라클의 조인 타입 / 표준 조인과 비표준 조인의 차이점 (0) | 2021.05.05 |
1.트랜잭션의 4대 특징, ACID (2) | 2021.05.05 |
DB 인덱스와 Join (0) | 2021.04.15 |
RDBMS의 연산과 키 (0) | 2021.04.15 |