[ DB ] Chapter 18. Concurrency Control

 

1. Lock-Based Protocols

 

look-based protocol이란 lock을 이용하여 공유되는 데이터를 관리하는 시스템이다. lock이란 공유되는 데이터에 대한 동시접근을 제어하는 메커니즘이다. 동시접근을 방지하지 않으면 rase condition이 발생할 수도 있다. 공유데이터를 동시에 읽는것은 문제가 되지 않다. 이에 read연산은 굳이 막을 필요가 없다. 이에 lock은 두가지 모드로 존재한다.

• Exclusive(X) mode
  • lock-X instruction을 사용하여 얻어야한다
  • 트랜잭션이 이 모드로 lock을 잡았다면 write와 read 모두 가능하다.
  • 우리가 보통 알고있는 lock으로 데이터에 이 lock이 걸려있다면 이후에 오는 트랜잭션은 read도 write도 못한다.
• Shared(S) mode
  • lock-S instruction을 사용하여 얻어야한다
  • 트랜잭션이 이 모드로 lock을 잡았다면 read만 가능하다.
  • 이 lock이 걸린 데이터는 다른 트랜잭션에 의해 read될 수 있다.

이러한 lock 요청은 concurrency-control manager에게 해야하며, 요청이 승인되어야 트랜잭션을 진행할 수 있다. lock을 요청하면 manager가 lock의 상태를 확인하고 사용가능하면 grant, 아니면 waiting 시킨다.

 

shared lock에 대한 트랜잭션 수는 제한되어있지 않다. exclusive lock은 어떤 데이터와도 동시에 lock할 수 없다.

 

 

한 트랜잭션의 예시이다.

이는 동시접근에 대한 제한은 잘 해주었지만serializability나 conflict는 보장되어있지 않다. A에 대한 연산이 모두 끝나고 B에 대한 연산이 시작하기 전에 다른 트랜잭션이 A를 수정할 수도 있고 A+B를ddisplay하기 전에 다른 트랜잭션과 conflict 할 수도 있다.

 

1.1 Schedule With Lock Grants

 

이 스케쥴은 serializable 하지 않다. T1과 T2의 실행순서가 바뀌면서 T2가 T1이 A에 대한 연산을 다 끝내기 전에 A에 접근하기 때문이다. locking protocol은 모든 트랜잭션이 따르는 lock에 대한 규칙의 집합이다. lock protocol은 스케줄이 serializability 하도록 스케줄을 제한한다.

1.2 Deadlock

deadlock이란 둘 이상의 프로세스 또는 스레드가 서로가 가진 자원을 기다리며 무한히 진행하지 못하는 상태를 말한다.

 

 

왼쪽 스케줄은 데드락에 걸리게된다. T4가 T3이 lock-X를 걸어놓은 B를 기다리고 있는 상황에서 T3이 T4가 lock-S를 걸어놓은 A를 기다리고 있다. 둘다 무한히 서로를 대기하게된다.

이를 처리하기 둘 중 하나를 rollback하고 lock을 해지해야한다. 하지만 이런 과정에서 starvation이 생길 수 있다. 오래걸리는 트랜잭션을 rollback 하라는 정책이라면 한 트랜잭션만 계속 rollback 되어 실행되지 못할 수도 있다. concurrency control manager은 이를 방지하도록 설계되어야한다

 

1.3 The Two-Phase Locking Protocol (2PL)

two-phase locking protocol은 conflict serializable을 보장해주는 protocal이다. DBS에서 가장 많이 쓰인다. 이는 lock을 2가지 단계로 나누어 실행한다.

• Phase 1 : Growing Phase : 락을 획득할 수 있지만 어떠한 락도 해제할 수 없다.
• Phase 2 : Shrinking Phase : 락을 해제할 수 있지만 새로운 락을 획득할 수는 없다.

하지만 이는 deadlock의 가능성도 가지고 있고 cascading rollback이 발생할 수도 있다. 이런 2PL의 단점을 보완하기 위해 확장된 두가지 프로토콜이 있다.

• strict 2PL
  • 트랜잭션은 commit이나 abort전까지 모든 exclusive lock을 hold해야한다.
  • 트랜잭션이 시작할 때 모든 lock을 잡는데, 그 lock이 exclusive lock이고 이를 commit/abort 될 때까지 unlock하지 않아야한다.
• rigorous 2PL
  • 트랜잭션은 commit이나 abort 전까지 exclusive lock 뿐 아니라 shared lock까지 hold하고 있어야한다.
  • 트랜잭션은 commit하는 순서대로 serialize될 수 있다
  • reverability를 보장하고 casecading roll-back을 방지한다.

대부분의 데이터베이스는 Regorous two-phase locking을 구현하지만, 이를 단순한 two-phase locking이라고 한다. 하지만 모든 2PL은 deadlock으로부터 자유롭지 않다.

2PL with Lock conversion

이는 Lock 변환을 할 수 있는 2PL이다. 이는 다음과 같은 두가지 phase로 구성된다.

• Growing Phase : 락을 획득할 수 있지만 어떠한 락도 해제할 수 없다. 현재 lock-S를 가지고 있는 상태라면 lock-X로 업그레이드 가능하다.
• Shrinking Phase : 락을 해제할 수 있지만 새로운 락을 획득할 수는 없다. 현재 lock-X를 가지고 있는 상태라면 lock-S로 다운그레이드 가능하다.

이 프로토콜은 serializability를 보장한다. 이를 사용하면 기존 보다 더 좋은 concurrency를 보장할 수 있다. 원래라면 X락을 계속 잡아야하는 상황에도 중간에 S락으로 바꿔줄 수 있기 때문이다.

Automatic Acquisition of Locks

이는 트랜잭션에 대한 적절한 lock과 unlock 명령을 자동으로 생성하도록 하는 방법이다. 이는 트랜잭션의 read/write 명령어를 기반으로 동작한다.

 

 

• 트랜잭션이 read작업을 호출하면 시스템음 lock-S 명령어를 호출한 후 read 를 실행시킨다.
• 트랜잭션이 write 작업을 호출하면 시스템은 트랜잭션이 현재 shared-lock을 가지고 있다면 upgrade 명령어를 호출한 후 write 명령어를 동작시키고, 가지고 있지 않다면 lock-X 명령어를 호출한 후 write 명령어를 실행시킨다.
• 트랜잭션이 커밋하거나 중단된다면 해당 트랜잭션이 획득한 모든 락은 unlock 된다.

 

1.4 Implementation of Locking

 

lock manager는 독립된 프로세스로 구현할 수 있다. 트랜잭션은 lock manager에게 lock 권한을 요청하고, lock manager운 grant 메세지를 보내거나 데드락이 발생했다면 rollback을 요청한다. 이때 lock을 요청한 트랜잭션은 응답이 올때까지 기다린다. lock manage는 granted lock과 pending request를 기록하기 위해 lock table이라는 in-memory data-structure를 관리한다.

 

파란색 사각형은 granted lock을 나타내고, 하늘색 사각형은 대기중인 request를 나타낸다.

번호가 쓰여진 흰색 사각형은 현재 존재하는 lock을 나타낸다. 새로운 lock 요청이 들어오면 request queue 끝에 추가되며, 이전의 모든 lock과 호환되는 경우 grant된다. unlock 요청이 오면 해당 request를 삭제하고 다음 request의 상황을 판단한다.

만약 트랜잭션이 중단되면 모든 대기중이거나 grant된 트랜잭션 request가 제거된다. look manager는 이를 효율적으로 구현하기 위해서 lock의 list를 보관할 수 있다.

 

I234을 보면 T1, T8이 lock을 잡고 있고 T2는 lock을 잡지 못했다. 이 그림을 보면 T1, T8은 shared lock을 잡고있고 T2는 X-lock을 요청했다는 것을 알 수 있다.

 

1.5 Graph-based Protocol

Graph-based protocol은 2PL의 대안책이다. 2PL은 비교적 엄격하게 하기 때문에 더욱 빠르게 하는 것을 중요시한다. 모든 data item의 집합에 partial ordering을 붙여 locking 순서를 정해둔 것이다. d1->d2라면 d1,d2 item에 모두 접근하는 트랜잭션은 반드시 d1을 먼저 access하고 d2를 access해야 한다. 보통 partially odering이 보장되면 4가지 데드락 조건 중 하나가 부정되어 데드락을 방지할 수 있다. tree-protocol이 대표적인 graph-based protocol의 한 종류이다.

Tree Protocol

이는 오직 exclusive lock만을 허용하고 Shared lock을 고려하지 않는다. unlock은 언제든지 가능하다는 것이 2PL과의 차이이다.

 

우선 Ti의 첫번째 lock은 어떤 데이터든지 상관없다. 하지만 두번째부터는 잡으려는 데이터의 parent data를 먼저 lock 해야만 원하는 데이터를 lock 할 수 있다. 또, 한번 unlock한 데이터는 연속적으로 lock을 다시 잡을 수 없다.

만약 T1이 처음에 B를 필요로 한다고 하자. 그럼 B에 대한 lock은 얻을 수 있다.(first lock은 어느 데이터든지 무관) 하지만 다음으로 I에 대한 lock을 얻으려면 T1은 그의 부모인 E에 대한 lock을 가지고 있어야만 한다.

tree protocol은 conflict serializability와 deadlock으로부터의 freedom을 보장한다. 2PL보다 unlock이 빨리 일어나 대기시간이 단축되고 concurrency가 향상된다. 이는 dead lock을 발생시키지 않아 rollback도 필요로하지 않는다. 하지만 이는 recoverability나 cascadeless을 보장하지는 않고 사용하지 않는 데이터도 lock 해야한다는 단점이 있다.

 

---

 

2.  Deadlock handling

 

모든 트랜잭션들이 다른 트랜잭션이 lock을 release하기를 기다리고 있는 상황을 deadlock이라 한다. 데드락을 완벽하게 막을 방법은 거의 없다. 하지만 deadlock handling을 고려해줘야한다.

handling에는 두 가지 approach가 존재한다.

• deadlock prevention
• deadlock detection & recover

2.1 Deadlock Prevent

이는 시스템이 deadlock에 절대 들어가지 않게하는 것이다. deadlock prevention에는 다음과 같은 전략이 존재한다.

• pre-declaration
  • 각 트랜잭션이 실행되기 전에 모든 data item들을 lock 해야한다
• partial ordering
  • 모든 데이터에 partial ordering 해준다 (graph-based protocol)
• wait-die scheme - non-preemptive
  • older 트랜잭션은 younger 트랜잭션이 release하기를 기다리지만, younger 트랜잭션은 절대 기다리지 않고 rollback된다
  • 이는 younger 트랜잭션이 lock을 획득하기 전까지 여러번 rollback하게 함
• wound-wait scheme - preemptive
  • older 트랜잭션이 younger 트랜잭션을 wound(force rollback)시키고, younger 트랜잭션은 older 트랜잭션이 release하기를 기다린다.
  • wait-die scheme 보다 rollback 횟수가 적다.
• Timeout based scheme
  • 트랜잭션은 정해진 시간동안만 lock을 기다리고 rollback된다.
  • 이는 deadlock이 일어났을 때 시간초과로 해결하도록한다.
  • 하지만 이는 deadlock이 없어도 불필요하게 rollback 될 수 있다.
  • 그저 오래걸리는 트랜잭션이 lock을 잡고 있는 것인데 계속 rollback 시켜 starvation 현상이 일어날 수 있다.

 

2.2 Deadlock Detection 

wait-for graph를 그리고 cycle이 있다면 deadlock 상태라는 의미이다. 각 노드는 트랜잭션을 의미하고 화살표는 기다리는 트랜잭션으로부터 lock을 가지고 있는 트랜잭션으로 그려진다. 이렇게 프로그램 실행 중 주기적으로 이를 그려주면 deadlock을 detect 할 수 있다.

 

 

2.3 Deadlock Recovery

deadlock을 detect 했다면 recovery를 해야 한다. deadlock을 깨기 위해서는 특정 트랜잭션이 희생하여 rollback 되어야한다. 이때 우리는 rollback 비용을 최소로하는 트랜잭션을 골라 rollback 시킨다. 하지만 이는 cost만 고려하기 때문에 한 트랜잭션만 계속 rollback되어 starvation이 일어날 수 있다. 이때는 deadlock 집합에서 가장 오래된 트랜잭션이 선택되는것을 막음으로써 해결할 수 있다. 트랜잭션의 rollback 간격도 정할 수 있다.

• Total rollback - 트랜잭션을 중단한 다음 처음부터 다시 시작한다.
• Partial rollback - cycle 내의 다른 트랜잭션이 기다리고 있는 lock을 release하기 위해 필요한 만큼한 victim 트랜잭션을 rollback한다.

 

---

 

 

3. Multiple Granularity

 

Granularity란 lock을 거는 단위를 의미한다. 다양한 크기의 데이터를 허용하고 작은 크기의 데이터가 큰 크기로 중첩되는 data granularity 계층을 정의한다. 예를 들어 relation의 전체를 다루고 싶으면 전체에 모두 lock을 걸 수도 있고, 오직 몊개의 tuple만을 이용하고 싶다면, 몊개의 tuple에만 lock을 거는 것이 좋을 것이다.

이때 우리는 작은 단위가 큰 단위 내에 중첩되어있는 계층 구조를 표현하기 위해 tree를 이용한다. 이때의 tree를 tree protocol과 혼동하면 안된다. 이 tree는 가장 큰 범위가 node로 표현되고 하위노드는 큰 범위안에 포함되어있다. 그렇게 때문에 트랜잭션이 node를 lock 하면 하위노드들은 동인한 모드로 암시적으로 lock된다.

Granularity of locking 다음과같이 두가지 level이 있다.

• Fine granularity (lower in tree)
  • 작은 단위로 lock을 걸어 concurrency가 높고, lock을 걸거나 푸는 연산이 많아 overhead 클 수 있음
• Coarse granularity (higher in tree)
  • 한 번에 많이 걸면 동시 접근 가능한 놈이 적기 때문에 concurrency가 낮고 locking overhead는 낮을 수 있음

 

다음과 같이 표현해볼 수 있다.

• database
• area
• file
• record

 

3.1 Intention Lock Modes

shared lock과 exclusive lock을 제외하고도 다음과 같은 세가지 lock mode가 존재한다.

• Intense-shared : root에 IS라고 되어 있으면 아래 서브트리 중 어딘가에는 shared lock이 잡혀 있다는 것을 암묵적으로 나타낸다
• Intense-exclusive : 어떤 노드를 기점으로 아래 하위 어딘가에 exclusive 혹은 shared lock이 있음을 나타낸
• shared and intention-exclusive : 특정 노드는 shared lock이 걸려있고 아래 어딘가에 exclusive lock이 걸려있음을 나타낸다. exclusive lock을 가진 노드를 제외하고는 모두 shared lock이 걸려있다.

intention lock을 사용하면 하위 node를 모두 확인할 필요 없이 상위 level node를 S 또는 X mode로 lock 할 수 있다.

 

위 표는 한 노드에 lock을 동시에 걸 수 있는지에 대한 결과표이다. 이때 subtree끼리 겹치지 않는다고 가정하고 true라고 판단한다.

 

3.2 Multiple Granularity Locking Scheme

트랜잭션은 다음 규칙을 사용하여 Q를 lock할 수 있다.

1. lock끼리의 호환성이 맞아야한다.
2. tree의 root를 먼저 lock 하고 어떠한 모드로 lock한다.
3. 트랜잭션 Ti는 노드 Q를 S 또는 IS 모드로 잠그기 위해서는 현재 Ti가 Q의 부모 노드를 IX 또는 IS 모드로 잠갔어야 한다.
4. 트랜잭션 Ti는 노드 Q를 X, SIX, 또는 IX 모드로 잠그기 위해서는 현재 Ti가 Q의 부모 노드를 IX 또는 SIX 모드로 잠갔어야 한다.
5. 트랜잭션 Ti는 이전에 어떤 노드도 잠금 해제하지 않았을 때에만 노드를 잠글 수 있다. (즉, Ti는 two phase여야 한다.)
6. 트랜잭션 Ti는 노드 Q의 자식 노드 중 어떠한 노드도 현재 잠근 상태가 아닌 경우에만 노드 Q를 잠금 해제할 수 있다.

• 정리
  • 부모가 S → 자식은 S, IS 가능하지만 딱히 필요없음. X, IX, SIX 불가
  • 부모가 IS → 자식은 S, IS, X, IX, SIX 모두 가능
  • 부모가 X → 자식은 모두 불가능
  • 부모가 IX → 자식은 S, IS, X, IX, SIX 모두 가능
  • 부모가 SIX → 자식은 S, IS, X, IX, SIX 모두 가능

lock은 root-to-leaf 순서로 얻어지지만, unlock은 leaf-to-root 순으로 된다. 특정 수준에서 lock이 너무 많은 경우 더 높은 granularity S나 X lock mode로 전환하게 되는데 이를 Lock granularity escalation이라고 하다. 이 규칙을 따라야 트랜잭션들이 서로 충돌 없이 상호작용하고, serializable한 스케줄을 형성할 수 있다.

 

---

 

 

4. Insert , Delete and Predicate Reads

 

4.1 Insert/Delete

data를 delete하기 위해서는 해당 data에 대한 X-lock을 가져야한다. 그리고 새 값을 insert하기 위해서도 X-lock인 DB에 해야한다. 이렇게 되면 delete할때 read/write 연산과 conflict하지 않고 insert 한 데이터도 commit 하기 전까지 다른 트랜잭션이 접근할 수 없다.

4.2 Predicate Reads and The Phantom Phenomenon

relation 전체를 하나씩 읽는 트랜잭션이 있다고 해보자. 이 트랜잭션은 읽을 데이터 하나하나에 lock을 걸고 읽는다. 하지만 이때 다른 트랜잭션이 relation에 delete와 insert를 했다고 해보자. 이렇게 되면 non-serializable이 된다.

이는 data level에서 conflict가 일어난 것이다. 따라서 이를 보호하기 위해서는 더 큰 lock을 걸어야한다. 혹은 전체 index를 lock 하고 update 연산자가 이에 접근하려면 X-lock으르 얻도록하면된다.

4.3 Index Locking To Prevent Phantoms

모든 relation에는 하나 이상의 index가 있어야한다. 트랜잭션은 relation에 대한 index를 통해 튜플를 찾은 후에만 튜플에 access할 수 있다. lookup을 수행하는 트랜잭션은 access하는 index leaf node를 S-lock해야한다. 다른 트랜잭션이 이 realaion을 업데이트 해주려고 한다면 해당 업데이트의 영향을 받는 모든 index leaf node에서 X-lock을 얻이야한다. 이는 2PL의 규칙을 준수해야하고 phantom phenomenon이 발생하지 않음을 보장한다.

4.4 Next-Key Locking to Prevent Phantoms

 

이는 leaf 전체를 lock 하는 것을 막기 위해 제안된 방법이다. 이는 더 높은 concurrency를 제공한다. 이는 index lookup을 충족하는 모든 value와 그 다음 value에 S-lock 을 건다. update를 해주는 경우리는 X-lock을 건다. 그렇다면 읽는 도중에 들어오는 것을 효과적으로 방지할 수 있다. insert/delete/update와의 query conflict의 detection을 보장한다. 실제로 위에 7과 15를 삽입하려고 해도 S-lock 때문에 삽입할 수가 없다. 만약 삽입이 성공했다면 conflict가 일어났을 것이다.