0. 개요
직렬가능화 스케쥴(Serializable schedule)을 사용해 병행 제어를 수행해야하며, 직렬가능화 스케쥴을 보장하기 위해 일반적으로 Strict 2PL Locking을 사용함.
일관성을 유지하면서 여러 트랜젝션을 동시에 처리하고자, (3가지 conflict가 발생할 수 있음)
RW, WR, WW conflict (RR은 문제되지 x)
Ch16-“직렬화스케쥴을 만드는것” : 직렬스케쥴과 동일한 결과를 내는 interleaving schedule
: 이게 ‘동시성 제어’ 이다
Dependency graph를 그려서 cycle 생성 여부를 확인=>직렬화 스케쥴이 아님(cycle이 생기면)
1. Lock-Based Concurrency Control
: Strict 2PL Locing Protocol
S(shared) lock : object를 읽기 전에 S lock을 얻어야함
=> 여러 트랜잭션이 하나의 object에 대해 S lock을 가질 수 있음
X(exclusive) lock : object에 쓰기 전에 X lock을 얻어야함
=> 하나의 object는 하나의 트랜잭션만 X lock을 얻을 수 있음 (해당 object에는 어떤 S lock, X lock도 걸려있지않아야 X lock을 요청할 수 있음)
1) Deadlock
: cycle of transaction wating for locks to be released by each other
- Deadlock prevention
- Deadlock detection
① Deadlock preventiontimestamp를 사용하여 우선수위를 부여
e.g. Ti가 Tj가 가지고 있는 lock을 요청한다고 하자.
- Wait-Die : Ti의 우선순위가 높다면 Tj가 종료될 때까지 기다리거나/ Ti의 우선순위가 더 낮다면 Ti는 abort한다
- Wound-wait : Ti의 우선순위가 높다면, Tj가 abort하거나 / Ti의 우선순위가 낮다면 Ti는 Tj가 종료될 때까지 기다린다.
② Deadlock detection
waits-for-graph를 주기적으로 검사하여 cycle 발생 여부를 확인
(cycle이 존재한다면 deadlock이 발생)
- node : Transaction
- if edges from Ti to Tj : Ti is waiting for Tj
1. growing phase : Locking phase
2. shrinking phase : Unlocking phase
2. Multiple-Granularity Locks
: 여러 level을 locking (hiararchy)
위 그림과 같이 locking의 대상은 하나의 tuple뿐 아니라 Table, Database로 확장될 수 있다.
Table level locking
- e.g T1이 t_camera를 locing(X lock)하였다면 다른 트랜잭션은 t_camera 테이블에 접근하지 못하게 된다. (ineffective)
=> 독점으로 인한 동시성 및 효율성 저하
이와 같은 '테이블 수준의 잠금'에서의 비효율성을 해결하고자 "Intention Lock" concept을 사용
| -- | IS | IX | S | X | |
|---|---|---|---|---|---|
| -- | O | O | O | O | O |
| IS | O | O | O | O | |
| IX | O | O | O | ||
| S | O | O | O | ||
| X | O |
① IS (Intention Shared lock) : T1이 튜플이 처리되는 동안 안정성을 보장하도록 설정한 S-Lock
② IX (Intention Exclusive lock) : ①-IS 개념 + IX가 설정된 튜플들은 갱신(UPDATE)될 수 있음
③ SIX(S&IX) : S & IX lock at the same time
- X lock : 쓰기 잠금, 다른 어떤 트랜잭션도 X lock이 부여된 튜플에 접근할 수 없다.
- IX lock : X lock을 요청할 의도로 수행됨. 여러 트랜잭션이 하나의 튜플에 IX lock을 요청할 수 있음
- SIX lock : R에 대해 S lock을 지속적으로 수행하다가 가끔 X lock을 쓰겠다. (WRITE할때 X lock으로 upgrade)
=> 가끔 write하는데 X lock을 걸어두는거는건 비효율적이므로
＠ 3번의 예를 통해 IS와 IX의 활용에 대해 다시 이해해 볼 수있다.
3. Tree Locking Algorithm
B+ Tree 구조의 index file 또한 locking 되어야 한다.
1) Simple
-
search : 루트 노드부터 스캔. 스캔하는 노드마다 S lock을 생성함과 동시에 부모 노드의 Slock을 unlock
-
insert/delete : 루트 노드부터 스캔. 스캔하는 노드마다 X lock을 생성함 & safe한 node인지 확인
* safe 한 노드란?
insert의 경우 > 노드가 full이 아닌 경우
delete의 경우 > 노드가 d/2보다 큰 경우 (즉, half full 보다 많이 차있어야함)
if node is safe => unlock ancestors'
2) Better
- Search : 1)와 동일
- insert/delete : 루트 노드부터 스캔. 각 노드에 S lock 생성 & 부모 노드 unlock, 리프 노드에서 X lock을 생성
만약 리프노드가 unsafe하다면 ?
모든 lock을 해제하고 1)방식으로 insert/delete 수행
delete 38
① S lock A
② S lock B, unlock S(A)
③ S lock C, unlock S(A),S(B) (C is safe)
④ X lock D, delete 38 and unlock S(C)
3) Even Better
- search : 1)와 동일
- insert/delete : 루트 노드부터 스캔, IX lock 생성, 리프노드에서 X lock 생성 시 모든 IX lock을 X lock으로 변경 (top-down 방식)
1)과 차이점은 X lock 대신 IX lock을 사용해 동시성 향상
delete 38*
① IX lock A
② IX lock B (B is not fase)
③ IX lock C, unlock IX(A),IX(B)
④ X lock D, unlock IX(C),
4) Hybrid Algorithm
: 루트 > 비단말 > 단말 hierarchy
상위 레벨로 갈수롤 X lock을 쓸 확률이 적다는 아이디어에 기반하여 루트노드에는 S lock / 비단말 노드에는 SIX lock / 리프 노드에는 X lock을 생성
=> 결론은 동시성 향상을 위해서는 X lock을 최소화하자
(누군가 object를 X lock 하면 모든 다른 트랜잭션은 해당 object에 접근할 수 없으므로)
4. Optimistic CC (Kung-Robinson Model)
(idea) conflict 가 발생활 확률이 매우 낮을거라는 긍정적 관점
① READ : Xacts가 db에서 읽고, CPU 연산까지 한 후 m/m에서는 변경이 적용됨 but, disk는 변경x
② VALIDATE : 충돌 확인 (RW/WR/WW)
③ WRITE : disk에 변경 사항을 반영
②-validation을 어떻게 수행하는가?
: timestamp를 사용
ReadSet(Ti) = Ti가 read한 object의 집합
WriteSet(Ti) = Ti가 write한 object의 집합
Test-① 항상 Tj가 시작하기 이전에 Ti를 완료한다
conflict 발생 X
Test-② Tj가 Write 단계를 시작하기 이전에 Ti를 완료한다
Test-③ Tj가 Write 단계를 시작하기 이전에 Ti가 Read를 완료한다
- Test-②의 경우, Tj가 시작하기 전에 WriteSet(Ti)와 ReadSet(Tj)의 교집합이 공집합인 확인 (check for RW conflict)
- Test-③의 경우, Tj가 시작하기 전에 WriteSet(Ti)와 ReadSet(Tj)의 교집합 && WriteSet(Ti)와 WriteSet(Tj)의 교집합이 "모두" 공집합인지 확인
