동시성 제어

록기반 규약

Lock-based Protocols

• lock은 데이터에 대한 동시적인 접근을 제한하는 방식이다.

• 록 규약은 트랜잭션의 동시성 제어를 위해 개발되었으며, 트랜잭션의 스케줄을 제한하여 원하는 트랜잭션이 생성되도록 한다.

• 데이터 아이템들은 2가지 lock 모드를 가진다.

  • exclusive (X) mode : read와 write 권한을 가질 수 있으면 흔히 Write lock이라고도 한다.
  • shared (S) mode : read만 할 수 있으며 read lock이라고도 한다.

• lock 호환성 은 아래의 표와 같다. true이면 다른 트랜잭션도 쓸 수 있고 false는 그렇지 못하다.

	S	X
S	true	false
X	false	false

• 트랜잭션은 적절한 락을 보유한 이후에 진행될 수 있으며 보유하지 않으면 기다려야 한다.
• 트랜잭션은 한 데이터에 요청한 락이 다른 트랜잭션에 의해 그 데이터에 이미 잡고있는 락과 호환될 수 있다면 락을 보유할 수 있다.
  • 아이템에 S락이 걸려있다면 다른 트랜잭션들도 S락을 걸 수 있다.
  • 아이템에 X락이 걸려있다면 다른 어떤 트랜잭션도 이 아이템에 락을 걸 수 없다.
• 만약 락을 걸 수 없다면 요청한 트랜잭션은 다른 트랜잭션에 의한 모든 호환되지 않은 락들이 풀릴 때 까지 기다려야 한다.
  • 그 이후에 락을 걸 수 있다.
• 트랜잭션의 직렬가능성을 보장하기 위해서는 추가적인 락 규약이 필요하다.

2-Phase Locking

• 2PL은 2단계로 구성이된다.

• Phase 1 : growing phase

  • 트랜잭션이 락을 얻는다.
  • 트랜잭션이 락을 풀지 않는다.

• Phase 2 : shrinking phase

  • 트랜잭션이 락을 푼다.
  • 트랜잭션이 락을 얻지 않는다.

• 이 규약은 충돌 직렬 가능성 스케줄을 제공하는 것을 보장한다.

• 연쇄 철회가 일어날 수 있다.

  • 이를 막기 위해서 "strict 2-phase locking"을 사용할 수 있는데, 모든 트랜잭션은 자신의 모든 X-Lock을 commit/abort 까지 끌고 간다.
  • Rigorous 2-phase Locking은 더 엄격한데, 모든 lock들이 commit/abort까지 간다. 이 프로토콜에서 트랜잭션들은 그들이 commit되는 순으로 직렬화 될 수 있다.

• 2PL은 deadlock을 일으킬 수 있다.

• 2PL이 생성하지 못하는 충돌직렬가능 스케줄이 있을 수 있다.

Lock Conversion

• 록 변환을 하는 2PL의 예시이다.

• First Phase

  • 데이터에 S-Lock을 잡을 수 있다.
  • 데이터에 X-Lock을 잡을 수 있다.
  • S-Lock을 X-Lock으로 Upgrade한다.

• Second Phase

  • S-Lock을 놓을 수 있다.
  • X-Lock을 놓을 수 있다.
  • X-Lock을 S-Lock으로 Down grade한다.

• 이 프로토콜은 직렬화를 보장한다.

Implementation of Locking

• 록을 담당하는 프로세스를 독립적으로 구성할 수 있다.
• 록을 담당하는 록 메니저는 내부적으로 록 테이블을 관리하면서 록 처리를 수행한다. 록 테이블은 주기억장치에서 빠른 접근을 위해 데이터 항목 이름으로 해쉬 색인을 구성한다.

Lock Table

• I는 자원이고, T는 트랜잭션이다.
• Lock Table은 허가되거나 요청된 Lock의 종류 또한 기록한다.
• 새로운 요청은 데이터 자원을 위한 큐의 끝에 더해지고, 모든 이전의 락들에 호환되면 허가된다.
• Unlock 요청에 의해 요청이 큐에서 제거되고, 이후의 요청이 그들이 허가될 수 있는지 확인한다.
• 트랜잭션이 abort되면 모든 기다리거나 허가된 트랜잭션의 요청들은 제거된다.

Dead Lock

• T3, T4가 진행할 수 없다.
  • T4의 Lock-S(B)는 T3의 Lock-X(B)를 기다리고, T3의 Lock-X(A)는 T4의 Lock-S(A)를 무한정 기다린다.
• 위와 같은 현상을 교착상태라고 한다.

Starvation

• 트랜잭션이 록을 획득하지 못하고 필요이상으로 록을 기다리는 현상을 말한다.
• 같은 트랜잭션이 데드락때문에 계속해서 rollback되어 록을 휙득하지 못한다.
• DBMS에서 기아상태는 없어야 한다.

Graph-based Protocol

• graph-based protocol은 2PL의 대안이다.
• 그래프 규약은 데이터에 대한 부분 순서가 있어야 함을 가정한다.
  • 이 것은 일반 데이터에는 적용이 불가능하다.
  • 하지만, 색인에 대한 데이터는 적용이 가능하다.
• 트리 기반 규약이 가장 그래프 기반 규약이다.

Tree-based Locking

• X-Lock만이 허용된다.

• 첫 번째 Lock Ti는 아무 아이템에 적용될 수 있다.

• 이후 아이템은 Ti의 자식 노드만 가능하다.

• 데이터 아이템들은 언제든지 unlock이 가능하지만, 해제한 항목에 대해서는 다시 Lock을 잡을 수 없다
  

  

• T2, T3는 록을 취득하는 데이터는 동일하나 록을 해제하는 순서에만 차이가 있다.

• 교착 상태가 발생하지 않는다. 록 요구의 순서가 있기 때문이다.

• 하지만 회복 불가능한 스케줄과 연속 철회 스케줄을 생성하기도 한다.

• 또한 필요없는 데이터에 대한 Lock을 취득해야 한다.

• 다만 2PL에서 불가능한 스케줄이 트리 기반에서 가능하다. 이 역도 가능하다.

  Dead Lock

  Dead Lock Handling

• Timeout-based Schemes

  • 트랜잭션이 정해진 시간 만큼만 Lock을 기다린다. 그 이후, rollback한다.
  • 구현은 간단하지만, 기아가 발생할 수 있다.
  • 적절한 timeout 시간을 정하기 어렵다.

• DeadLock Prevention Protocol

  • 실행 이전 트랜잭션이 필요로 하는 락을 모두 알아야 한다. (predeclaration)
    • 미리 데이터 요구를 알 수 없기에 실효성이 없다.
  • 모든 데이터 아이템의 부분적인 순서를 두고, 트랜잭션이 아이템들을 이 순서에 따라 lock하도록 한다. (graph-based)

Wait-die/ Wound-wait schemes

• deadlock을 방지하기위해 트랜잭션 timestamps를 사용한다.

• Wait-die scheme

  • 비선점 방식
  • Old한 트랜잭션은 Young한 트랜잭션이 데이터 아이템을 내려놓을 때 까지 기다린다. (Wait)
  • Young한 트랜잭션은 Old한 트랜잭션을 기다리지 않고 rollback한다. (Die)
  • 트랜잭션은 필요한 아이템을 얻기 위해 여러번 rollback 당할 수 있다.

• Wound-wait scheme

  • 선점 방식
  • Old한 트랜잭션은 Young한 트랜잭션을 rollback 시킨다. (Wound)
  • Young한 트랜잭션은 Old한 트랜잭션을 기다린다. (Wait)
  • wait-die 보다 rollback이 적을 수 있다.

• 두 정책에서, rollback된 트랜잭션은 기존 타임스탬프를 가지고 재시작한다.

  • 기아를 예방한다.

Deadlock Detection & Resolution

• prededence graph에 cycle이 생기면 daedlock이다.
• deadlock이 생겼다면...
  • victim을 선정하여 rollback시킨다.
  • victim은 rollback하는데 최소의 비용이 드는 트랜잭션이다.
  • Total / Partial rollback
    • Total : 트랜잭션을 abort하고 재시작한다.
    • Partial : deadlock을 없애기 위해 필요한 만큼만 rollback
• 항상 같은 Victim이 생기면 Starvation이 일어난다.

Insert, Delete

Insert and Delete Op

• Insert와 Delete는 X-Lock을 가지고 수행되어야 한다.
• Tuple Lock System에서, Insert와 Delete에 의해 Phantom 현상이 생길 수 있다.
• Phantom Phenomena
  • Tuple Level Locking 시스템에서 일어난다.
  • Insert, Delete되는 터플이 의미적으로 다른 트랜잭션이 수행하는 연산 데이터와 관련이 된다.
  • 이 때문에 록킹 관점에서는 입력/삭제 연산을 지연해야 하지만, 터플 로킹을 하는 경우 해당 터플 Insert, Delete 여부를 다른 트랜잭션이 인식하지 못하여 발생한다.

Phantom Phenomenon

• 터플 레벨 로킹을 하면 록간에 충돌이 없으므로 수행이 가능하나, T1의 트랜잭션 관점에서 Busan 계좌의 합이 맞지 않다고 생각하는 오류가 발생한다. 이를 팬텀 현상이라고 한다.
• 팬텀 현상이 일어나는 스케줄은 직렬가능하지 않다.
• 팬텀 현상은 튜플 레벨 로킹에 의해 일어난다.

How to Handle Phantom Probelm

• Insert, Delete가 없으면 된다.
  • DBMS의 존재이유가 아니다.
• Table Locking을 한다.
  • 문제는 해결되나, 동시성이 매우 낮다
• Index Locking
  • 모든 관계 테이블은 최소 하나의 인덱스를 가진다.
  • 트랜잭션은 하나, 또는 여러개의 인덱스들을 통해서만 튜플에 접근할 수 있다.
  • Index Lokcing은 특정한 인덱스 버킷 (노드)에 Lock을 취함으로써 더 높은 동시성을 가진다.
  • 위의 예시에서 T2가 새로운 튜플을 입력하려면 색인을 변경해야하는데, T1이 색인 노드에 대한 S-Lock을 취하고 있으므로 X-Lock을 걸 수 없어 기다려야 한다.

Applying 2PL for Index

• 인덱스에 접근하는 트랜잭션 T는 접근하는 모든 leaf/non-leaf 노드에 대해 S-Lock을 걸어야 한다.
• Insert, Update, Delete하는 트랜잭션 T는 접근하려는 모든 leaf/non-leaf 노드에 대해 X-Lock을 걸어야한다.
  • 노드가 split/merge하는 경우에 부모 노드도 락을 걸어야한다.
• phantom 현상은 일어나지 않으나, 너무나 비효율적이다.

Concurrency in Index Structures

• 색인 구조로의 접근은 굉장히 빈번하고, 데이터 아이템보다 더 많이 일어난다.
• 색인 구조의 내부 노드에 대한 록을 미리 해제하는 동시성 제어 방식이 다수 제안되었다.

Crabbing for Index Structures

• Crabbing은 색인 구조에 대한 동시성 제어 기술이다.
• B+-Tree에서 루트노드에 대한 S-Lock을 잡는다.
• 필요한 자식 노드를 S-Lock으로 잡고, 부모 노드의 락을 푼다.
• Insert, Delete 중에는, leaf node lock들을 X-Lock으로 강화한다.
• split/merge가 부모노드를 변화시켜야 한다면, 부모 노드를 X-Lock으로 잡는다.
• 과도한 deadlock을 일으킬 수 있다.
• 부모노드를 풀고 자식노드를 잡는 방식으로 개선할 수 있다.

Transaction Isolation in SQL

Transactions in SQL

• SQL에서, 트랜잭션은 암시적으로 시작한다.
• SQL에서 트랜잭션은 다음에 의해 종료된다.
  • Commit work : 현재 트랜잭션을 commit하고 새로운 트랜잭션을 시작한다.
  • Rollback work : 현재 트랜잭션을 abort한다.
• 대부분의 DBMS에서, 초기값으로, 모든 SQL 문장은 성공적으로 종료되면 암시적으로 commit한다. (Auto Commit)

Weak Levels of Consistency

• 상용 DBMS는 트랜재션에 대한 완전 분리도를 제공하기도 하지만, 응용의 요구에 의하여 완화된 트랜잭션 분리도를 제공한다.
• 약한 일치성을 제공하는 것은 응용에 따라서 완전한 분리도가 요구되지 않는 경우가 있으며, 이러한 응용에서는 데이터베이스 일치성보다는 데이터베이스 시스템 성능이 더 중요하기 때문이다.

Degree-two Consistency

• 2단계 일치성 : S-Lock이 언제나 풀릴 수 있다는 점, Lock이 언제나 잡힐 수 있다는 점에서 2PL과 다르다.
  • X-Lock은 트랜잭션의 끝까지 잡혀야 한다.
  • 직렬가능성이 보장되지 않기에, 프로그래머가 정상적인 데이터베이스 상태를 보증해야 한다.
• 커서 안정성
  • Read에 대해서, 각 튜플은 lock되고, read하고, unlock된다.
  • X-Lock들은 트랜잭션의 끝까지 유지된다.
  • 2단계 일치성의 한 종류이다.

Transaction Isolation SQL

• SQL은 non-serializable 실행을 허용한다.
  • Serializable : 기본
  • Repeatable Read : commit된 레코드만이 읽힐 수 있도록 허용한다. 또한 read를 반복하는 것은 같은 값을 리턴해야한다. 때문에, S-Lock은 유지되어야 한다.
    • 하지만, phantom 현상은 예방되지 않는다.
  • Read committed : 2단계 일치성과 같으나, 대부분의 시스템은 커서 안정성으로 구현한다.
  • Read uncomitted : commit되지 않은 데이터도 읽히는 것을 허용한다.

Transaction Isolation Effect

Common Name	Read Uncommitted	Read Committed	Serializable
Lock Protocol	Set long exclusive locks on data you write	Long exclusive lock Set short share locks on data you read	Long exclusive lock Set long share locks on data you read
Protection Provided	No lost update	No lost update No dirty read	No lost update No dirty read Repeatable read
Dirty Data	You don't overwrite dirty data Others don't overwrite your dirty data	Additionally, you don't read dirty data	Additionally, others don't
Committed Data	Writes visible at End Of Transaction	Same as left	Same as left