[데이터베이스 설계] 동시성 제어

동시성 제어 기본 (Prologue)

• 동시성 제어는 트랜잭션의 기본 속성인 고립성(Isolation)을 보장하기 위해 필요
• 여러 트랜잭션이 동시에 실행될 때 고립성이 깨질 수 있으므로, DBMS는 동시 실행되는 트랜잭션 간의 상호작용을 제어가 필요
• 가장 자주 사용되는 방식은 2단계 락(Two-phase locking)과 스냅샷 고립(Snapshot isolation)

---

락 기반 프로토콜 (Lock-Based Protocols)

• 락(Lock)은 데이터 항목에 대한 동시 접근을 제어하는 메커니즘
• 락은 두 가지 모드가 있음:
  
  • Exclusive (X) 모드: 데이터 항목을 읽고 쓸 수 있습니다. lock-X 명령으로 요청
  • Shared (S) 모드: 데이터 항목을 읽기만 할 수 있습니다. lock-S 명령으로 요청
• 트랜잭션은 **동시성 제어 관리자(Concurrency-control manager)**에게 락을 요청하며, 승인되어야만 작업을 진행할 수 있습니다.

락 호환성 (Lock Compatibility)

• 락 요청은 해당 항목에 이미 설정된 락과 호환될 경우에만 승인
• 락 호환성 매트릭스:
  
  • S 락과 S 락: True (호환 가능)
  • S 락과 X 락: False (호환 불가)
  • X 락과 S 락: False (호환 불가)
  • X 락과 X 락: False (호환 불가)
• 여러 트랜잭션이 한 항목에 대해 S 락을 동시에 보유할 수 있음
• 하지만 한 트랜잭션이 X 락을 보유하면, 다른 어떤 트랜잭션도 해당 항목에 S 락이나 X 락을 보유할 수 없음
• 락을 승인받지 못하면, 호환되지 않는 락이 해제될 때까지 대기

락 사용 예시 (문제 상황)

• 트랜잭션 T1 (B에서 A로 50 이체):

T1: lock-X(B);
     read(B);
     B := B - 50;
     write(B);
     unlock(B);
     lock-X(A);
     read(A);
     A := A + 50;
     write(A);
     unlock(A).

• 트랜잭션 T2 (A와 B의 합계 출력):
  

  T2: lock-S(A);
       read(A);
       unlock(A);
       lock-S(B);
       read(B);
       unlock(B);
       display(A + B).
  

• 문제점: T1이 B에 대한 작업을 마치고 unlock(B)를 너무 일찍 수행하면 , T2가 중간에 끼어들어 lock-S(B)를 얻고 B를 읽을 수 있음
• 이때 T1은 아직 A에 50을 더하기 전이므로, T2는 (A=100, B=150)과 같이 일관성 없는 상태를 보게 되어 250이라는 잘못된 합계를 출력

락 문제 해결 및 데드락

• 해결책: 락 해제(unlock)를 트랜잭션이 끝날 때까지 지연
• 트랜잭션 T3 (수정된 T1):
  

  T3: lock-X(B);
       read(B);
       B := B - 50;
       write(B);
       lock-X(A);
       read(A);
       A := A + 50;
       write(A);
       unlock(B);
       unlock(A).
  

• 트랜잭션 T4 (수정된 T2):
  

  T4: lock-S(A);
       read(A);
       lock-S(B);
       read(B);
       display(A + B);
       unlock(A);
       unlock(B).
  

• 이렇게 하면 T4는 일관성 없는 결과를 출력하지 않음
• 새로운 문제 (데드락): 이 방식은 교착상태(Deadlock)를 유발할 수 있음
  
  1. T3가 lock-X(B)를 실행
  2. T4가 lock-S(A)를 실행
  3. T3가 lock-X(A)를 요. (T4가 A의 S 락을 풀 때까지 대기) 
  4. T4가 lock-S(B)를 요청. (T3가 B의 X 락을 풀 때까지 대기)
• T3는 T4를 기다리고, T4는 T3를 기다리는 순환 대기 상태, 즉 데드락이 발생
• 데드락 해결을 위해 둘 중 하나의 트랜잭션을 롤백(Rollback)해야 함
• 결론: 데드락은 바람직하지 않지만 , 일관성 없는 상태보다는 낫다
• 롤백으로 처리 가능하기 때문
• 데드락은 일관성을 지키기 위한 필요

락 승인과 기아 상태 (Starvation)

• 기아 상태(Starvation)는 특정 트랜잭션이 락을 영원히 얻지 못하는 상황입니다.
• 시나리오:
  
  1. T2가 Q에 S 락을 보유 중
  2. T1이 Q에 X 락을 요청하고 대기
  3. T3가 Q에 S 락을 요청. (T2의 S 락과 호환되므로 승인) .
  4. T2가 락을 해제해도, T1은 여전히 T3의 S 락 때문에 대기
  5. 이후 T4, T5... 등이 계속 S 락을 요청하고 승인받으면, T1은 X 락을 영원히 받지 못할 수 있.
• 해결책: 락 관리자는 락을 요청한 순서를 고려
• 즉, (1) 충돌하는 락이 없고, (2) 자신보다 먼저 락을 요청해서 대기 중인 트랜잭션이 없을 때만 락을 승인

---

2단계 락 프로토콜 (Two-Phase Locking Protocol, 2PL)

• 충돌 직렬 가능성(Conflict-serializability)을 보장하는 프로토콜
• 트랜잭션의 락/언락 요청을 두 단계로 나뉨.
  • 1. Growing Phase (확장 단계): 트랜잭션이 락을 **획득(obtain)**할 수만 있는 단계입니다. 락을 해제(release)할 수 없음
  • 2. Shrinking Phase (축소 단계): 트랜잭션이 락을 **해제(release)**할 수만 있는 단계입니다. 새로운 락을 획득할 수 없음
• 트랜잭션은 Growing Phase로 시작하며 , 단 하나의 락이라도 해제하는 순간 Shrinking Phase로 진입하고 다시는 락을 획득할 수 없음
• 트랜잭션이 마지막 락을 획득하는 시점을 락 포인트(Lock point)라고 함

2PL 예시

• 위의 T3와 T4는 2PL을 준수
  • T3: lock-X(B), lock-X(A) (Growing) -> unlock(B), unlock(A) (Shrinking).
  • T4: lock-S(A), lock-S(B) (Growing) -> unlock(A), unlock(B) (Shrinking).
• 반면 T1과 T2는 2PL을 위반.
  • T1: lock-X(B) -> unlock(B) (Shrinking 시작) -> lock-X(A) (Shrinking 중 락 획득 시도).
  • T2: lock-S(A) -> unlock(A) (Shrinking 시작) -> lock-S(B) (Shrinking 중 락 획득 시도).

2PL의 문제점

1. 데드락: 2PL은 충돌 직렬 가능성을 보장하지만, 데드락을 방지하지는 못합니다. T3와 T4의 데드락 예시가 2PL을 준수하는 상황에서도 발생할 수 있음.
2. 연쇄 복귀 (Cascading Rollback): 2PL 하에서도 연쇄 복귀가 발생할 수 있음.
   
   1. T5가 A에 X 락을 걸고 쓰고 unlock(A)를 함. (T5는 Shrinking Phase 진입)
   2. T6이 A에 X 락을 걸고 씀. (T5가 쓴 값을 읽음)
   3. T7이 A에 S 락을 걸고 읽음. (T6이 쓴 값을 읽음)
   4. T5가 Abort (철회)됨.
   • 결과: T5가 쓴 값을 읽은 T6도 롤백해야 하고, T6이 쓴 값을 읽은 T7도 연쇄적으로 롤백해야 함

Strict 및 Rigorous 2PL

• Strict 2PL (엄격한 2PL): 연쇄 복귀를 방지
  
  • 규칙: 트랜잭션이 보유한 모든 Exclusive (X) 락은 트랜잭션이 Commit (완료)될 때까지 해제하지 않음.
  • 다른 트랜잭션이 커밋되지 않은 데이터를 읽는 것을 막아줌
• Rigorous 2PL (준엄한 2PL): Strict 2PL보다 더 엄격
  
  • 규칙: 트랜잭션이 보유한 모든 락 (X와 S)은 트랜잭션이 Commit (완료)될 때까지 해제하지 않음.
  • 구현이 더 쉽지만 , 동시성이 일부 희생
  • 대부분의 DBMS는 Rigorous 2PL을 구현하면서 간단히 2PL이라고 부름

락 변환 (Lock Conversions)

• 2PL은 락 모드를 변환할 수 있음.
  • Upgrade (승격): S 락을 X 락으로 변환. Growing Phase에서만 가능
  • Downgrade (강등): X 락을 S 락으로 변환. Shrinking Phase에서만 가능
• 사용 예시 (T8): T8이 a1...an을 읽고 마지막에 a1을 쓴다고 가정 .
  
  • 처음부터 a1에 X 락을 걸면 T9(a1, a2를 읽음)의 동시 실행을 불필요하게 막음.
  • 해결: T8은 처음에 a1에 S 락을 걸고 , 모든 읽기를 마친 후 write(a1)이 필요할 때 S 락을 X 락으로 Upgrade함

---

락 구현 (Implementation)

• 락 관리자 (Lock Manager): 별도 프로세스로 구현.
• 트랜잭션은 락 관리자에게 메시지로 락/언락을 요청
• 락 관리자는 **락 테이블(Lock Table)**이라는 메모리 내 자료구조를 유지하며 승인된 락과 대기 중인 요청을 기록
• 락 테이블은 각 데이터 항목별로 락을 요청한 트랜잭션들의 큐(Queue)를 관리.
• I23 항목에 대해 T1, T8이 (S 락) 승인을 받았고, T2가 (X 락) 대기 중

그래프 기반 프로토콜 (Graph-Based Protocols)

• 2PL의 대안으로, 모든 데이터 항목에 부분 순서(Partial ordering)를 부여
• di -> dj 순서가 정해져 있다면, 두 항목을 모두 접근하는 트랜잭션은 반드시 di를 dj보다 먼저 접근
• 이 순서는 방향성 비순환 그래프(DAG)로 표현되며, 트리 프로토콜(Tree Protocol)이 단순한 예

트리 프로토콜

• 규칙:
  1. X 락만 허용.
  2. 첫 번째 락은 아무 항목에나 걸 수 있음.
  3. 이후 항목 Q에 락을 걸려면, 반드시 Q의 부모(Parent) 노드가 현재 락이 걸린 상태여야 함.
  4. 락 해제는 아무 때나 가능.
  5. 한번 락을 해제한 항목은 다시 락을 걸 수 없음.
• 장점:
  - 충돌 직렬 가능성을 보장하며 데드락이 발생하지 않음
  - 2PL보다 락을 일찍 해제할 수 있어 동시성이 증가
• 단점:
  - 연쇄 복귀를 보장하지 않음
  - 또한, 접근할 필요가 없는 부모 노드까지 락을 걸어야 할 수 있어 오버헤드가 발생할 수 있음

---

데드락 처리 (Deadlock Handling)

• 데드락은 여러 트랜잭션이 집합 내 다른 트랜잭션을 기다리는 순환 대기 상태
• 처리 방법은 크게 두 가지:
  1. 데드락 예방 (Prevention): 시스템이 데드락 상태에 절대 빠지지 않도록 보장하는 프로토콜 (데드락 확률이 높을 때 유용).
  2. 데드락 탐지 및 회복 (Detection & Recovery): 데드락 발생을 허용한 뒤, 주기적으로 탐지하여 롤백을 통해 회복 (데드락이 드물 때 더 효율적)

데드락 예방 (Prevention)

 

순환 대기가 발생하지 않도록 락 요청 순서를 강제

• 방법 1 (Pre-declaration): 트랜잭션 시작 전에 필요한 모든 락을 한꺼번에 획득.
• 방법 2 (Timestamp 사용): 트랜잭션에 타임스탬프(고유 번호)를 부여하여 우선순위를 정함. (오래된 트랜잭션 = 타임스탬프 값이 작음)
• Wait-Die (대기-죽음) 방식 (비선점):  
  • T(Old)가 T(New)가 가진 락을 요청: T(Old)는 Wait (대기).
  • T(New)가 T(Old)가 가진 락을 요청: T(New)는 Die (롤백). (젊은 트랜잭션은 늙은 트랜잭션을 기다리지 않음)
  • 예시 (T14=5, T15=10, T16=15):
    • T14(Old)가 T15(New)의 자원 요청 -> T14 대기.
    • T16(New)이 T15(Old)의 자원 요청 -> T16 롤백.
• Wound-Wait (상처-대기) 방식 (선점):
  
  • T(Old)가 T(New)가 가진 락을 요청: T(Old)가 T(New)를 Wound (롤백시킴).
  • T(New)가 T(Old)가 가진 락을 요청: T(New)는 Wait (대기). (늙은 트랜잭션은 절대 기다리지 않음)
  • 예시 (T14=5, T15=10, T16=15):
    • T14(Old)가 T15(New)의 자원 요청 -> T15 롤백 (T14가 선점).
    • T16(New)이 T15(Old)의 자원 요청 -> T16 대기.
  • Wound-Wait 방식이 Wait-Die보다 롤백 횟수가 적을 수 있음.