인터리빙한 TX 스케줄에서, 우리가 운영체제에서 배웠던 것 처럼
Race condition , Deadlock 등등 비일관성 문제가 발생할 수 있다. 이런, TX의 동시성에 의해 발생하는 비일관성 문제를 해결할 수 있는 방법들을 알아보자
트랜잭션 스케줄
- 직렬 스케줄
트랜잭션별로 연산을 연산을 순차적으로 실행하는 스케줄 - 비직렬 스케줄
인터리빙하게 트랜잭션을 실행하는 스케줄 - 직렬 가능 스케줄
트랜잭션이 인터리빙하게 수행되어도 직렬 스케줄과 동일한 결과를 가지는 스케줄
충돌
인터리빙한 두개 이상의 TX 사이에서 동일한 DB Object에 대해 접근이 발생했고 ,
하나 이상의 Write 연산이 발생했을 경우
충돌 직렬 가능
- 충돌 동등
스케줄 S가 비충돌 명령어의 교환으로 스케줄 S'으로 변환될 수 있다면
충돌동등이라고 한다.
스케줄 S가 직렬 스케줄과 충돌동등하다면, 즉 동일한 결과를 가진다면 S를
충돌 직렬 가능 스케줄이라고 한다.
왼쪽 스케줄과 오른쪽 직렬 스케줄은 충돌동등이므로 충돌 직렬 가능하다.
의존성 그래프
T1이 A를 가장 마지막으로 wirte 했고 , T2가 A를 read/write 하려는 경우 T1에서 T2로 A의 가중치를 가진 간선을 그려준다. 그 역( B에 대하여)도 마찬가지로 그려준다.
Node간의 싸이클이 생기면 의존성이 발생했고, 이는 직렬화 불가능한 스케줄이다.
의존성 그래프가 사이클이 발생하지 않았을 경우에만 충돌 직렬화가 가능하다
Strict 2 Phase Locing Protocol
TX들의 직렬화를 위해 엄격한 2 페이즈 락킹 프로토콜을 사용할 수 있다.
- TX이 어떤 Object에 대해 read할 경우 S lock 획득, 추후 X lock으로 업그레이드 가능
- TX이 어떤 Object에 대해 write할 경우 X lock 획득
- TX이 Commit / Abort 되었을 경우 소유하고 있던 모든 lock을 반환
- 특정 TX이 어떤 Object에 대해 X lock을 소유하고 있을 경우, 다른 TX이 해당 Object에 대해 S/X lock을 획득할 수 없다.
Strict 2PL 프로토콜을 통해 교착상태가 발생하는 것을 방지할 수 있다.
뷰 직렬 ( View Serializability )
스케줄 S1과 S2는 다음의 경우 뷰 동등 ( view equivalent ) 하다.
- 동일한 Object A에 대해서 TX1이 스케줄 S1에서 초기값으로 A를 read 한다면, 스케줄 S2에서도 초기값으로 A를 read한다.
- 동일한 Object A에 대해서 스케줄 S1에서 TX1이 Write(A) 후 TX2가 Read(A)라면, 스케줄 S2에서도 TX1이 Write(A) 후 TX2가 Read(A)
- 동일한 Object A에 대해서 스케줄 S1에서 TX1이 최종적 Write(A) 했다면,
스케줄 S2에서도 TX1이 최종적으로 Write(A) 수행
말이 조금 어렵지만 요약해보자면
인터리빙하게 수행되는 스케줄 S와 순차적으로 수행되는 스케줄 S'를 비교해서 동일한 데이터 Q를 '초기 읽기', '쓰기/읽기', '마지막 쓰기' 순서만 같다면 뷰동등이다.
만일, 스케줄 S가 직렬 스케줄 S'과 뷰동등이라면 뷰 직렬 가능하다.
Lock Management
- lock과 unlock의 요청은 DBMS lock manager에 의해 관리된다.
- locking과 unlocking은 atomic 해야한다. 또한, 반드시 unlock 해야한다.
- S lock은 X lock 으로 업그레이드 가능하다.
Deadlock
운영체제 시간 때 배운 , 그 데드록이다. 결국 공유되는 자원에 대한 interleaving한 접근은 교착 상태를 만들 수 밖에 없다.( e.g. 잠자는 이발사 문제 , 식사하는 철학자 문제 )
A TX은 B TX이 lock을 반납하길 기다리고 , B TX은 A TX이 lock을 반납하길 기다린다면 결국 영원히 이 딜레마는 해결될 수 없을 것이다.
데드록 예방 기법
데드록 자체를 예방하는 방법이지만 , 실제로는 사용하기 까다롭다.
그냥 이런 게 존재한다는 것 정도만 알고 넘어가자
- Wait-Die 기법
- Wound-Wait 기법
데드록 탐지 기법
우선 TX 노드간의 가중치 그래프를 그려준다. 사이클이 발생했다는 것은, 교착상태가 발생했다는 뜻이다.
TX1은 TX2가 획득한 X(B)가 반납되길 기다리므로 화살표를 그려준다.
나머지 TX들도 위와 똑같이, 자신이 R/W 하고자하는 Object에 대하여 lock을 가지고 있는 TX 노드에 화살표를 그려준다.
최종적인 결과로, Cycle이 생성된다면 DeadLock이 발생한 것이다.
다중 세분도 잠금 기법
다중 세분도 잠금 프로토콜 ( Multiple Granularity Locking Protocol )
DB 오브젝트에 대한 lock을 획득할 때, 어떠한 단위로 locking을 할 지 정해야한다.
지금까지의 locking protocol은 record 단위로 lock을 획득했지만, 아래와 같이 lock의 단위를 변화시킬 수 있다.
TX이 진행중인 DB를 잠글 수도 , Table을 잠글 수도 , 혹은 페이지, 튜플을 잠글 수도 있다. 높은 Object 단위에 lock을 걸면 동시성은 낮아지지만 overhead가 작아진다.
낮은 단위의 Object에 lock을 걸면 동시성은 높아지지만 overhead가 커진다.
위의 트리는 4단계 ( DB , Area, File, Record) 로 이루어져있다.
특정 DB object에 대해서 lock을 획득한다는 것은 , 그 자손 node 또한 암묵적으로 lock을 획득해야한다는 것을 알 수 있다.( 자손 node들은 lock이된 parent를 참조하기 때문이다)
만일 TX이 특정 node에 대해 lock을 걸기 위해서는 system이 lock을 걸 수 있는지 판단 할 수 있어야 한다. 전체적인 Tree를 스캔하여 판단할 수 있겠지만 , 다중 세분도 잠금 프로토콜의 경우 새로운 lock flag를 도입해 lock을 획득할 수 있는지 유무를 판단한다.
- IS lock ( Intentional Shared Lock )
- IX lock ( Intentional Shared Lock )
- SIX lock ( S와 IX Lock을 동시에 획득 )
결론
길어질 것 같아, 2편에서 마저 기술하겠다!
