[DB] 동시성 제어

Concurrency Control Techniques

Concurrency Control Protocols : guarantee serializability (직렬화 보장)

• Locking
• Timestamps
• multiversion CC protocols
• Optimistic protocols
• Multiple granularity concurrency control protocol

Two-phase Locking Techniques : 이중 라킹

lock 상태 1, unlock 상태는 0

 

Lock table : lock 정보를 관리하는 서브시스템

• plus a queue for transactions that are waiting to access item

Shared/Exclusive (or Read/Write) Locks : 공유(read lock), 배타(write lock)

• Multiple-mode lock

Shared locking protocol

1. 어떤 아이템을 읽기 전에 read lock 또는 write lock을 한다
2. 어떤 아이템을 쓰기전에는 Write lock 필요
3. 읽거나 쓴 이후 unlock
4. 다른 트랜젝션에 의해 unlock될 수 없음

Locking 만으로는 직렬화 보장이 불가능

 

Lock table

<아이템 이름, LOCK, no_of_reads, Locking_transaction>

LOCK(X) = write-locked : 배타 lock을 유지하는 단일 트랜젝션

LOCK(X) = read-locked : 공유 lock을 유지하는 하나 이상의 트랜젝션

2단계 라킹 프로토콜

two phase locking protocol (2PLP)

1. growing phase : lock 걸기 시작하면 계속 걸어야함
2. shrinking phase : unlock 시작 후 lock 생성불가

직렬가능한 스케줄의 충분조건이지만 필요조건은 아님

< Basic 2PL >

1. Conservative 2PL (= static 2PL) : 보수적/정적 2PL
   • 모든 lock을 시작부분에 미리 선언하기
   • deadlock-free!
2. Strict 2PL : 엄격한 2PL
   • 커밋될때까지 쓰기연산 unlock 불가능
   • recoverablity → dirty read 없음
   • not deadlock-free
3. Rigorous 2PL : 철저한 2PL
   • strict 스케줄 보장
   • 커밋될때까지 쓰기 & 읽기연산 unlock 불가능
   • 구현은 더 쉽지만 융통성이 떨어짐

Dealing with Deadlock and Starvation

• deadlock : 잠긴 항목을 무한대기중인 상태
• starvation : abort, restart 반복하는 기아 상태

Deadlock prevention protocols : 데드락 예방

1. Conservative 2PL (보수적 2pl, 모든 lock 미리 선언)
2. Ordering all the items
3. Transaction timestamp TS(T) : 시작 순서에 따라 정렬
4. Deadlock preventoin schemes ⇒ wait-die / wound-wait

wait-die : 아이템 뺏으려는 애가 older → 기다림

• younger → abort

wound-wait : 아이템 갖고있던 애가 younger → 기다림

• 아이템 갖고있던 애가 older → 갖고있는 애가 abort (뺏김)

Deadlock prevention protocol without timestamps

• no waiting algorithm
  • if 트랜젝션이 lock에 접근할 수 없으면 바로 abort&restart
  • no checking on deadlock
  • 근데 불필요한 abort가 많아져서 비효율적
• Cautious waiting algorithm
  • 불필요한 abort를 감소
  • if 트랜젝션이 lock에 접근할때, lock한 트랜젝션이 다른 아이템을 기다리고 있다면 (blocked 상태) : abort
    • lock한 놈이 not blocked : wait
  • deadlock-free
  • 둘 다 기다리는 경우, block 시간으로 정렬되므로 순차실행 가능

Deadlock Detection : 데드락 탐지

• victim selection : abort할 희생양을 고르기
• wait-for graph : if has cycle → deadlock
• Timeout
  • 일정 시간이 지나면 abort&restart
  • no deadlock check
• Recovery
  • minimum cost를 희생양으로.
  • rollback : abort & restart. 부분 롤백은 불가능
  • starvation (livelock)
    • 같은 희생양이 계속된다면 그게 never completes
    • first come first served

Granularity of data items and multiple granularity locking : 아이템 세분화와 다중세분화 라킹

• locking 단위가 작을수록 오버헤드 확률이 높다.
• locking 단위가 클수록 동시성 수준은 낮다.

Multiple Granularity level locking

상위 데이터 lock 시도 시, 데이터 전체를 뒤져서 sub item 중에 lock이 없다면 허용 가능.

 

Timestamp Mechanism : 타임스탬프 메커니즘

• deadlock-free
• cascading rollback
• cyclic restart (starvation)

Multiversion Scheme

• 원본과 여러 버전을 만든다.
• deadlock-free
• 대신 버전 관리가 필요함