7. Concurrency Control

Uncontrolled Sharing Problems

1. Lost Update Problem

-> T1에 의해 쓰여진 값을 잃게 된다.

 

2. Uncommitted Dependency Problem

-> T2에서 커밋하지 않은 값을 T1이 읽어 올바르지 않은 값을 사용하게 된다.

 

3. Inconsistent Analysis Problem

-> T1이 A를 먼저 읽고 B를 T2보다 나중에 읽게 되면 올바르지 않은 값을 계산한다.

 

---

Schedules

• Serializable Schedule: 결과가 순차적으로 트랜잭션을 실행한 것과 동일한 스케줄
• Conflict Serializable Schedule: 연산 순서를 재배치해서 직렬 가능하게 만들 수 있는 스케줄
  • 이를 보장하는 방법
    1. 2PLP(2-Phase Locking Protocol)
    2. TBO(Timestamp-based Ordering)
    3. OCC(Optimistic Concurrency Control)

---

Lock-Based Protocols

• Lock-compatibility matrix
  
  • Shared Lock(lock-S()): 데이터를 읽을 때 사용하는 락
  • Exclusive Lock(lock-X()): 데이터를 읽고 쓸 때 사용하는 락

• Lock requests는 concurrency-control manager에 의해 만들어진다.
• 다른 트랜잭션에 의해 아이템에 대해 락이 걸려 있다면 요청 락이 compatible할 때 락이 주어진다.
  • 한 아이템에 여러 개의 공유 락을 걸 수 있지만 exclusive 락의 경우 다른 락을 요청 불가능
• 락을 얻지 못하면 해제될 때까지 기다려야 함

• 위 상황의 경우 락이 serializability를 보장하지 못한다.
• locking protocol: 락을 요청하고 해제하는 동안 트랜잭션이 따르는 규칙의 집합

The Two-Phase Locking Protocol

• conflict-serializable schedule을 보장하는 프로토콜이다.
• Phase 1: Growing Phase
  • 트랜잭션은 락을 얻기만 하고 해제하지 않음
• Phase 2: Shrinking Phase
  • 트랜잭션은 락을 얻지 않고 해제만 함
• serializability 보장: lock points(트랜잭션이 마지막 락을 얻는 때) 순서에 따른 직렬화를 보장

• deadlocks 발생 가능
• cascading roll-back 발생 가능 -> 이를 피하기 위한 프로토콜 strict two-phase locking
  • 트랜잭션이 끝날 때까지 모든 exclusive lock을 유지
• Rigurous two-phase locking이 더 엄격: 트랜잭션이 끝날 때까지 모든 락을 유지
  • 트랜잭션 커밋 순서에 따라 직렬화 가능

 

 

Implementation of Locking

• lock manager: 트랜잭션에게 락을 보내고 락 해제를 요청하는 별도의 프로세스
• 트랜잭션이 락 요청을 보내면 lock grant messages를 보내 응답
  • 데드락의 경우 트랜잭션에게 롤백 요청 메세지를 보냄
• lock manager는 lock table을 유지 - granted lock과 pending requests를 기록
  • 보통 락이 걸린 데이터의 이름으로 색인되는 in-memory hash table로 구현됨

• 검은 사각형 - granted locks / 하얀 사각형 - waiting requests
• lock table은 락의 종류도 기록함
• 새로운 요청은 데이터 아이템에 대한 요청 큐의 마지막에 추가됨
• unlock 요청은 락을 삭제하고 다음 요청을 허용가능한지 확인
• 트랜잭션이 중단되면 해당 트랜잭션의 모든 락 요청이 삭제됨

 

Pitfalls of Lock-Based Protocols

deadlock

• T3은 A에 대한 락을 기다리고 T4는 B에 대한 락을 기다림 -> deadlock 발생
• 이를 해결하기 위해서 T3와 T4 중 하나는 반드시 롤백되어 락을 해제해야 함

deadlock prevention

• Timeout-Based Schemes
  • 트랜잭션은 특정 시간 동안 락을 기다리고 시간이 지나면 롤백함
  • 데드락은 발생하지 않지만 starvation 발생 가능
  • 적절한 timeout interval을 결정하기 어려움

starvation

• 트랜잭션이 아이템에 대한 X-lock을 기다릴 때 다른 트랜잭션들이 같은 아이템에 대해 S-lock을 요청
  • S-lock만 계속 허용되면서 데드락으로 인해 트랜잭션이 반복적으로 롤백됨