[DB] CH15. 동시성 제어(Concurrency control)

 

Lock이란?

Data item에 대한 concurrent access를 control하기 위한 메커니즘

다음의 두 가지 모드가 있다.

• exclusive mode : r/w 모두 가능. lock-X 명령어로 사용
• shared mode : r만 가능. lock-S 명령어로 사용

Lock based protocol 기본

다음과 같은 lock-compatibility가 있다.

쉽게 말해, 

• 모든 트랜잭션은 shared lock을 hold할 수 있다.
• 다만, 어떤 트랜잭션이 exclusive lock을 갖고 있다면 그 어떤 트랜잭션도 어느 lock이든 hold하지 못한다.

아래는 lock based protocol을 사용하는 스케쥴의 예시이다. 좀 더 나아가서, 아래 예시를 보면 conflict, view serializable하지 않은 것을 알 수 있다. 즉, 단순한 lock based protocol은 serializability를 보장하지 않는다.

 

Lock-based protocol의 단점

아래 그림과 같은 경우를 생각해보면 두 가지 가능성이 있다.

• Deadlock : T3와 T4는 서로가 lock release하기를 기다린다.
• Starvation : 한 트랜잭션이 지속적으로 lock을 할당받지 못하게 될 수도 있다. 가령, 여러 트랜잭션 중 유독 하나만 rollback되는 victim으로 선정된다거나.

concurrency control manager는 이러한 것들을 잘 해결하도록 디자인되어야 한다.

Lock-based protocol의 Deadlock 발생

Two-Phase locking protocol(2PL)

2PL은 conflict serializability를 보장한다. 구체적으로는 한 트랜잭션 안에서 다음의 두 가지 phase로 구성된다.

• Growing Phase(Phase1)
  • 트랜잭션은 lock을 obtain할 수 있다.
  • lock을 release할 수 없다.
• Shrinking Phase(Phase2)
  • 트랜잭션은 lock을 release할 수 있다.
  • lock을 obtain할 수 없다.

아래는 2PL을 사용하는 예시이다.

2PL의 단점

• deadlock의 가능성 O
• cascading rollback의 가능성 O

이를 보완하기 위한 다음과 같은 2PL의 좀 더 엄격한 버전도 있다.

• strict 2PL : 트랜잭션은 commit이나 abort전까지 모든 exclusive lock을 hold해야 한다.
• rigorous 2PL : strict보다 더 엄격. exclusive lock 뿐 아니라 shared lock까지 hold하고 있어야 함.

Lock conversion(2PL with lock conversion)

기존의 2PL에서 lock conversion을 추가한 것이다. 다음의 두 가지 phase로 구성된다.

• First Phase
  • lock-S, lock-X를 acquire할 수 있다.
  • lock-S를 lock-X로 convert할 수 있다.(Upgrade)
• Second Phase
  • lock-S, lock-X를 release할 수 있다.
  • lock-X를 lock-S로 convert할 수 있다.(Downgrade)

이러한 lock conversion의 도입은 기존 2PL보다 more concurrency를 보장한다. 아래와 같은 경우에 그러하다. 가장 왼쪽과 같은 스케쥴이 있는데 이를 original 2PL과 lock conversion으로 구현한 것이다. 만약 lock conversion이 없어서 기존의 original 2PL을 쓴다면 a1에 대한 lock이 T8에서 무조건 lock-X가 되어야 한다. 왜냐하면 write(a1) instruction이 있기 때문이다. 따라서 이 경우 T8과 T9을 concurrent하게 동작시키지 못한다. 하지만 lock conversion의 경우 upgrade(a1)이 있어 둘을 concurrent하게 수행시킬 수 있다.

 

Locking의 구현

lock manage는 트랜잭션의 lock request에 lock grant를 보내 응답한다. 트랜잭션은 lock manager로부터 grant 응답을 받을 때까지 wait한다. lock manage는 granted lock과 pending request를 기록하기 위해 lock table이라는 자료구조를 사용한다. lock table은 보통 메모리 내에 data item name으로 indexed된 hash table로 존재한다.

Lock table 예시

Graph-based protocol

2PL의 대안으로 나온 것이다. data item set D={d1,d2,...,dn}에 partial ordering을 붙여 locking 순서를 정해둔 것이다.(impose partial ordering) 예컨대, d1->d2라면 d1,d2 item에 모두 접근하는 트랜잭션은 반드시 d1을 먼저 access하고 d2를 access해야 한다. tree-protocol이 대표적인 graph-based protocol의 한 종류이다.

아래는 트리 프로토콜의 모식도이다. 각 노드는 data item을 나타낸다.

tree-protocol은 다음과 같이 동작한다.

tree-protocol

• exclusive lock만 가능
• unlock은 언제나 가능(2PL과의 차이)
• 예) 만약 T1이 처음에 B를 필요로 한다고 하자. 그럼 B에 대한 lock은 얻을 수 있다.(first lock은 어느 데이터든지 무관) 하지만 다음으로 I에 대한 lock을 얻으려면 T1은 그의 부모인 E에 대한 lock을 가지고 있어야만 한다.
• 한 번 unlock한 트랜잭션은 동일 data item에 대해 relock이 불가능

Graph-based protocol(Tree-protocol)의 장단점

장점

• tree protocol은 conflict serializability를 보장한다.
• data item을 항상 정해진 순서에 따라 hold하므로 deadlock free를 보장한다.
• 2PL보다 unlocking이 일찍 일어날 수 있기 때문에 waiting time을 줄여 concurrency를 증대시킨다.

단점

• recoverable과 cascadeless를 보장하진 않는다.
• 사용하지 않는 item을 불필요하게 lock해야 한다(overhead)->잠재적인 concurrency 감소 효과가 발생

잠깐 정리!!!

mechanism : lock(동시성 제어를 하기 위한 메커니즘)

protocol : 기본locking protocol->2PL->strict/rigorous 2PL->lock conversion->Graph-based

Deadlock handling

모든 트랜잭션들이 다른 트랜잭션이 lock을 release하기를 기다리고 있는 상황을 deadlock이라 한다. handling에는 두 가지 approach가 존재한다.

• deadlock prevention
• deadlock detection & recover

Deadlock prevention

시스템이 deadlock state에 절대 들어가지 않도록 보장한다.

deadlock prevention에는 아래와 같은 전략이 존재한다.

• predeclaration : 각 트랜잭션이 시작하기 전에 필요한 모든 data item을 lock하도록 한다.(concurrency가 매우 떨어지는 방법)
• graph-based protocol : 위에서 이미 설명(partial ordering)
• wait-die scheme : older 트랜잭션은 younger 트랜잭션이 release하기를 기다리지만, younger 트랜잭션은 절대 기다리지 않고 roll back된다.(rollback instead of waiting)
• wound-wait scheme : older 트랜잭션이 younger 트랜잭션을 wound(force rollback)한다. younger 트랜잭션은 older 트랜잭션이 release하기를 기다릴 수 있다.
• Timeout based scheme : 트랜잭션은 오직 정해진 시간동안만 wait하고, 그 시간이 넘어가면 roll back 된다.

정리!!!!

그러니까, deadlock prevention에는 크게 3가지 방법이 있다.

• predeclaration/graph-based
• wait-die/wait-wound
• timeout-based

이 때, wait-die와 wait-wound는 starvation free까지도 보장한다. 왜냐하면 older 트랜잭션이 항상 younger 트랜잭션에 대해 precedence를 갖기 때문이다. 하지만 timeout-based의 경우 starvation의 발생 가능성이 존재한다.

Deadlock detection

wait-for graph에 cycle을 검사. cycle이 있으면 deadlock detected->recovery

deadlock을 detect했으면 recovery를 해야 한다. 이 땐, 어떻게 rollback을 시킬지를 결정해야 하는데 total rollback을 시킬수도 있고 비용을 최소화하는 트랜잭션을 골라 rollback시킬 수도 있다. 주의할 점은 동일한 트랜잭션이 계속해서 victim으로 선정되면 starvation이 일어날 수 있다.

Timestamp-based protocol

모든 트랜잭션은 시스템에 들어갈 때 timestamp가 발급된다. 만약 T1이 T2보다 먼저 시스템에 들어간 트랜잭션이라면 TS(T1)<TS(T2)이다. timestamp-based protocol은 이러한 timestamp에 따라 concurrent execution을 결정하는 protocol이다.

data item마다 다음의 두 가지 timestamp를 갖는다.

• W-timestamp(Q) : write(Q)를 성공적으로 실행시킨 트랜잭션들의 timestamp 중 largest
• R-timestamp(Q) : read(Q)를 성공적으로 실행시킨 트랜잭션들의 timestamp 중 largest

timestamp ordering protocol은 conflicting read/write에 대한 timestamp order execution을 보장한다. 각 케이스별로 아래와 같이 동작한다.

• T1이 read(Q)를 수행한다면
  • if) TS(T1)<W-TS(Q) : T1 rollback(T1이 마지막 write(Q)보다 먼저 read(Q)를 하므로)
  • if) TS(T1)>=W-TS(Q) : 정상작동
• T1이 write(Q)를 수행한다면
  • if) TS(T1)<R-TS(Q) : T1 rollback
  • if) TS(T1)<W-TS(Q) : T1 rollback(T1은 obsolete write를 하므로)
  • 위 경우가 아닌 경우에 정상작동

Timestamp ordering protocol의 장단점

장점

• conflict serializability를 보장 : conflicting operation이 timestamp order에 따라 실행되므로
• deadlock free

단점

• cascadeless를 보장하진 X
• recoverable을 보장하진 X

Thomas' Write rule

obsolete write를 rollback시키는 대신 ignore한다. -> more concurrency