LockBased Protocol

##이전 LockBased Protocol 내용은 추가 예정##

Two-phase locking protocol

• 어떠한 데이터에 대해 Lock을 걸고(growing phase), 어떠한 데이터에 대해 Lock을 풀어준다.(shrinking phase)
• 해당 프로토콜에서는 이미 해제한 lock을 다시 걸어줄 수 없다.
• Dirty Read, Non-Repeatable Read 방지
• DeadLock, Cascading Rollback 문제점 유발

공유잠금 Shared Lock(Lock-S): 읽기 작업 시 사용 , 여러 트랜잭션이 동시에 읽을 수 있음

배타 잠금 Exclusive Lock(Lock-X): 쓰기 작업시 사용, 한 트랜잭션만 접근 가능

왼쪽 Deadlock상황

1. T1: lock-X(B); read(B); B := B - 50; write(B); lock-X(A) → 대기.
2. T2: lock-S(A); read(A); lock-S(B) → 대기.
   • 결과: T1은 A를 기다리고, T2는 B를 기다려 Deadlock(교착 상태) 발생. DBMS는 이를 감지하고 한 트랜잭션을 롤백합니다.

오른쪽 cascading Rollback상황

1. T5: lock-X(A); read(A); lock-S(B); write(A); unlock(A).
2. T6: lock-X(A); read(A); write(A); → T7 대기.
3. T7: lock-S(A); read(A); …
   • T6에서 오류 발생 시, T7이 T6의 변경된 A를 읽었으므로 T7도 롤백(Cascading Rollback). T6와 T7이 롤백 대상.

장점

• 안전성 보장: Dirty Read(커밋되지 않은 데이터를 읽음)를 방지. Strict 2PL(커밋 후에만 잠금 해제) 변형은 Recoverable Schedule을 보장.
• 간단한 구현: 잠금 관리자(Lock Manager)가 트랜잭션 요청을 처리하면 됩니다.
• 효과적: 대부분의 실시간 시스템(예: Oracle, MySQL InnoDB)에서 기본으로 사용.

문제점

• Deadlock (교착 상태): 이미지 왼쪽처럼 순환 대기(Cycle in Wait-for Graph)가 발생. 해결: Deadlock Detection(주기적 그래프 검사) 또는 Prevention(잠금 타임아웃).
  • 빈도: 고부하 시스템에서 1-5% 발생.
• Cascading Rollback (연쇄 롤백): 이미지 오른쪽처럼 한 트랜잭션 오류가 다른 트랜잭션을 연쇄적으로 롤백. 성능 저하(Undo 비용 증가).
  • 해결: Strict 2PL (커밋 후 잠금 해제)로 방지.
• 성능 오버헤드: 잠금 대기로 throughput(처리량) 감소. 장기 트랜잭션에서 Lock Escalation(세밀 잠금을 테이블 수준으로 확대) 필요.
• Starvation (기아 상태): 일부 트랜잭션이 영원히 대기할 수 있음. 해결: 우선순위 큐 사용.

2PL Lock Conversion 과 Rigororous 2PL

자동적으로 2Phase에 맞게 Lock을 잘 걸어주면 괜찮은데 read에 X를 걸어버리면 Lock-X가 풀릴때까지 기다려야 한다.

Growing Phase에서 공유 잠금(S-Lock)을 배타 잠금(X-Lock)으로 업그레이드(Upgrade)하고 Shrinking Phase에서 X-Lock을 S-Lock으로 다운그레이드(Downgrade)할 수 있도록 하여 동시성 수준을 높이는 메커니즘이다.

Rigorous 2PL(Strick 2PL의 강화버전)

• 모든 잠금을 트랜잭션 커밋(Commit) 또는 중단(Abort) 후에만 해제하여 Cascading Rollback을 방지하지만, 동시성이 낮아질 수 있다.
• DeadLock가능성을 유지하며 데이터 일관성을 보장

왼쪽그림

• T8 (Rigorous 2PL 예시): lock-X(A1); read(A1); ... read(An); write(A1); unlock(A1); ...
  • 모든 읽기/쓰기 후 잠금을 즉시 해제하지 않고, 트랜잭션 끝까지 유지. 하지만 이미지에서 T9가 A1에 접근하려 할 때 WAIT(대기) 발생. 이는 Rigorous 2PL의 엄격함으로 인한 동시성 저하를 보여줍니다.
• T9: read(A1); ... read(A2); display(A1 + A2); ...
  • T8의 X-Lock 때문에 A1 접근이 블록킹(Blocking)되어 WAIT. Rigorous 2PL은 잠금 해제를 커밋 후로 미루어 안전하지만, 이런 대기가 빈번합니다.

오른쪽그림

• T8: lock-S(A1); read(A1); ... read(An); upgrade(A1); write(A1); unlock(A1); ...
  • 초기 S-Lock으로 읽기 후, Growing Phase에서 upgrade(A1)로 X-Lock 변환 → 쓰기. Shrinking Phase에서 unlock.
• T9: lock-S(A1); read(A1); ... read(A2); display(A1 + A2); ...
  • T8의 upgrade 전까지 S-Lock으로 병렬 읽기 가능. 변환 후에도 downgrade를 통해 공유 가능.
• 흐름: 파란 화살표(→)는 변환 과정을 나타내며, T8이 A1을 업그레이드하면 T9는 잠시 대기하지만, 전체적으로 기본 2PL보다 빠른 동시 실행.

항목 기본 2PL 2PL with Lock Conversion Rigorous 2PL

항목	기본 2PL	2PL with Lock Conversion	Rigorous 2PL
잠금 변환	없음	Upgrade (Growing), Downgrade (Shrinking)	없음 (커밋 후 해제)
동시성 수준	중간	높음 (유연)	낮음 (안전 우선)
Deadlock 위험	높음	높음 (변환 시 증가)	중간
Cascading Rollback	가능	가능 (Downgrade로 완화)	불가능
적합 환경	일반	동적 쿼리 (OLAP)	안전 요구 (은행)

Lock manager

Lock manager가 Lock상황을 관리한다.

Lock Manager가 Lock table을 보고 Lock이 없나 확인 후 Lock을 부여

Lock리스트가 비어있을때

1. T1 이 Lock을 요청하고
2. Item즉 위 그림의 Lock 테이블을 확인한 후
3. T1을 locklist에 올린 후
4. 락을 허용한다.

Locklist가 있지만 실행 가능

1. T2가 Lock을 요청하고
2. item이 Lock을 확인하고
3. Lock리스트에 추가한후
4. Lock을 허용한다.

Locklist가 있지만 실행 불가할때

1. T3가 Lock을 요청
2. 리스트 확인
3. 리스트에 추가하지만 실행하지않고 대기
4. 대기락을 걸어줌

Locklist에 넣지 못하는 상황(데드락이 걸릴수 있는 상황)

1. 락 요청
2. 리스트 확인
3. 데드락 발생 가능성을 락메니저가 확인
4. 반려함

unlock 요청

1. unlock을 요청한다.
2. item을 확인하고,
3. T1을 제거한 후 T3가 실행 가능한지 확인(T3는 T2와 연관되어 실행불가)

unlock 요청2

1. unlock요청
2. 아이템 확인
3. T2를 지운 후 T3가 lock될수 있음을 확인
4. T2에겐 승인, T3에겐 락을 허용해줌.

Graph-based protocol

데이터 접근에 대한 순서가 위처럼 트리의 형태로 (사이클 없음) 명확하게 정해져 있을때

• Lock-X(exclusive Lock)만 진행됨.
• 데이터 항목 집합 D = {d1, d2, ..., dn}에 부분 순서(Partial Ordering) 부과: 데이터 항목 간 "d_i 전에 d_j 접근" 같은 순서를 그래프로 표현. 이는 유향 비순환 그래프(Directed Acyclic Graph, DAG)로, 순환(Cycle)이 없어 Deadlock을 방지합니다.
• 규칙: 만약 d_i < d_j (d_i가 d_j보다 앞 순서)라면, 어떤 트랜잭션도 d_i를 d_j보다 먼저 접근해야 합니다. (접근 순서 위반 시 대기 또는 거부).
• 데이터베이스 그래프(Database Graph): 부분 순서를 나타내는 DAG. 노드: 데이터 항목(d_i), 간선: 순서 관계 (d_i → d_j: d_i 후 d_j 접근).

데드락의 방지는 확실히 보장한다.

Ti가 E를 접근하려 할때 Tj가 아직 커밋되지 않았을 때 Tj가 정보를 가지고 있도록 하게 한 후 한번에 롤백 시킨다.

• cascading rollback문제