10. Concurrency Control

1. Concurrency Control Techniques

Serializability를 보장하기 위한 규칙이다.

Two-phase locking(2PL)

Locked (1) / Unlocked (2)

Data를 접근했는데 Unlock 상태이면, Lock을 걸고 데이터를 사용한다.

만일 Lock 상태라면, data가 unlock이 될 때까지 기다리는 방식이다.

Data의 Lock은 operation을 종료하면서 풀어준다.

Lock을 관리하는 subsystem을 필요로하며, DB에 binary lock은 너무 제한적이다.

--> Shared/Exclusive read/write lock을 사용한다.

read_lock(X), write_lock(X) (exclusive), unlock(X)

Lock conversion	Upgrading	Downgrading
Lock을 가지고 있는 transaction은 lock을 변경할 수 있다.	read_lock을 write_lock보다 먼저 수행한다.	read_lock을 write_lock 다음에 수행한다.

Static 2PL	Strict 2PL	Rigorous 2PL
Transaction이 사용하는 모든 item에 transaction 시작 전에 lock을 걸어둠 Deadlock이 발생하지 않음	Exclusive lock을 transaction commit이나 abort 전까지 놔주지 않음	그 어떤 lock도 commit이나 abort 전까지 놔주지 않음

Locking은 기본적으로 overhead가 큼

 

Deadlock

T1과 T2가 서로 lock이 풀리기를 기다리는 상황이다.

이를 해결하기 위해서는 Victim selection, Timeouts, Starvation이 필요하다.

Victim selelction	Timeouts	Starvation
Transaction 하나 abort하기	일정시간 이상 Transaction이 진행이 안되면,abort하기	다른 Transaction은 정상 수행되는데, 수행되지 않는 Transaction -> First-come-First-served queue를 사용한다.

 

Timestamp-based oredering

Transaction의 유일한 식별자인 timestamp를 이용해 concurrency를 관리하는 방법이다.

Deadlock이 발생할 수 없다는 장점을 가지고 있다.

Equivalent serial order(먼저 수행되면 먼저 끝낸다)

Timestamp Ordering(TO)

• Interleaving 가능
• Timestamp order에 맞춰서 conflict 해결

Basic TO algorithm	Strict TO algorithm	Thomas's wirte rule
Conflict 발생하면, later operation aborted Starvation이 발생할 수 있음	전 Transaction이 commit, abort되기 전까지 다음 Transaction은 수행되지 않음	Basci TO의 변형으로, write가 빈번하게 발생하는 경우 마지막 write만 반영하는 방법임

 

Multiversion protocols

여러 버젼의 item을 시스템에 유지시키는 방법이다.

다른 기법에서 거부될 read가 여기서는 가능할 수 있다.

많은 저장공간을 요구하게 된다.

Optimistic techniques를 사용한다.

(Conflict 확인을 뒤로 미루었다가, 나중에 한번에 검증하는 방식, local copy로 진행, commit이거나 abort면 반영)

 

Snapshopt isolation

Commit이 일어나면 Snapshot을 찍고 timestamp와 함께 저장한다.

업데이트된 값을 확인할 수 있어, read lock은 없고 write lock만 사용하게 된다.

 

2. Data item granularity

Granularity는 data의 크기이다. 

Data small = Lock 사용

Data big = Concurrency Control 사용

Intention Lock
하위 노드에서 뭐 할 예정이니 위에서 막아주는 Lock이다.
Intention-shared(IS)	Shared lock이 자손에 요청됨
Intention-exclusive(IX)	Exclusive lock이 자손에 요청됨
Shared-intention-exclusive(SIX)	현재 노드가 shared mode에서는 lock이지만, 다른 자손에 exclusive lock 가능