Previous chapter
으 아 악
Transaction을 동시에 실행하면, Atomicity를 유지하지 못할 수도 있다.
시스템은 Atomicity를 보장하기 위해 동시에 실행되는 Transaction간의 상호작용을 제어해야만 한다.
동시성 제어 기법(Concurrency Control)은 Transaction간의 Atomicity를 보장하기 위한 상호작용 제어 규칙이다.
Lock-based Protocols
록은 데이터를 엑세스 하는데 있어서 가장 기초적인 방법.
1.
Exclusive(X) mode : Transaction Ti가 데이터 항목 Q에 대해 X모드를 가지고 있을 때 오직 Ti만 Q를 읽고 쓰기가 모두 가능하다.
2.
Shared(S) mode : Transaction Ti가 Q에 대해 S모드를 가지고 있다면 Ti는 Q를 읽을 수 있으나, 갱신할 수 없다.
모든 Transaction은 Concurrency Control Manager(이하 CC매니저)에게 Q에 대해 어떤 연산을 수행할지 리퀘스트해야한다.
Compatibility Function(or Matrix)
Transaction Ti가 Q에 대해 A모드 락을 요청했을 때 Tj는 Q에 대해 B모드 락을 가지고 있다고 가정하자.
만약 B형 록을 가진 상태에서 A모드 록을 동시에 취할 수 있을 때 두 모드는 서로 호환된다고 말한다.
위 표에서는 S모드 끼리만 서로 호환될 것이다.
Lock-based Protocol Performance
•
lock-S(Q)를 통해 Q에 공유모드의 록을 요청한다.
•
lock-X(Q)를 통해 Q에 X모드의 록을 요청한다.
unlock으로 데이터 Q에 자신이 걸었던 잠금을 해제할 수 있다.
Ti가 특정 록의 리퀘스트를 보냈을때 다른 Transaction에 의해 호환되지 않는 모드의 록이 걸려있다면, 모든 비호환 록이 해제될 때까지 CC매니저가 Ti의 리퀘스트를 거절한다. 따라서 Ti는 대기(wait) 상태로 존재한다.
Transaction이 데이터에 계속 접근하려고 하면 반드시 잠금을 가지고 있어야 한다.
T2는 Transaction의 Serializability에 대한 고려가 거의 없다. 락킹은 serializability를 반드시 보장해주지 않는다.
Schedule with Lock Grants
Transaction T1와 T2가 있을 때
T1의 연산이 다 수행되고, T2가 수행되어야 하는데, 바뀐 순서를 보면, T1의 하단과 T2의 연산이 바뀐 것을 알 수 있음. 두 연산 간 write와 read의 순서가 올바르지 않으므로 conflict-serializable하지 않음.
Deadlock
T3에서 B에 대해 X모드 록을 걸어둔다. 그 이후 T4에서 A에 대해 S모드 록과 B에 대해 S모드 록을 리퀘스트한다.
CC매니저는 A는 통과하나, B는 거절하므로 T4는 lock-S(B) 시점에서 대기상태에 돌입한다. 다른 Transaction이 록을 해제하길 기다려야 한다.
이후 T3가 X모드록을 A에 대해 걸려고 한다. CC매니저는 T4에 걸려있는 S모드 록 때문에 거절한다. T3도 대기상태에 걸린다.
이때부터 T3와 T4는 영겁의 시간동안 대기상태에 빠진다.
안타깝게도 데드록 현상은 거의 대부분의 록 프로토콜에서 일어날 수 있다. 필요악이라는 말씀.
데드락을 풀려고 하다가 Starvation이 발생할 수도 있다. CC매니저가 구리게 디자인되었을 때 일어날 수 있는데, 정책에 따라서 비슷한 녀석이 계속 종료될 수 있음을 기억하자.
2Phase Locking Protocol
락킹 프로토콜은 앞서 살펴봤듯이, 간단하고 구현하기 쉬우며 매니저 단계에서도 별로 할일이 없어 좋지만, 교착 상태에 쉽게 빠지기 쉬우며 Serializability를 보장하기 힘든 문제점이 있다.
2페이즈 잠금 프로토콜은 conflict-serializability를 보장하는 프로토콜이다.
다만, 2PL이 데드락을 반드시 막아주는 것은 아님!!
Phase 1 : Growing Phase
Transactinon이 록을 얻을 수는 있으나, 록을 해제할 수는 없는 단계다.
Phase 2 : Shrinking Phase
Transactinon이 록을 해제할 수는 있으나, 록을 얻을 수는 없는 단계다.
증가 단계에서 트랜잭션은 필요한 대로 잠금을 얻는다.
록 해제를 한 이후 감소 단계에 돌입하며, 이 단계에서는 절대 더 이상의 잠금을 요청할 수 없다.
2PL이 CS를 보장한다는 것을 확인할 수 있다.
스케쥴에서 Transaction이 마지막 록을 얻는 부분을 Lock point라고 하는데, 이 락포인트를 기준으로 트랜잭션을 정렬할 수 있다.
Strict 2PL : 엄격한
Transaction이 commit하거나 abort될 때까지 모든 락이 X락을 얻는다.
•
다른 Transaction은 접근 자체가 안될 수 있는 문제가 있다.
Rigorous 2PL : 덜 엄격함
Transaction이 commit하거나 abort될 때까지 모든 락을 얻어야 한다.
대부분 DB는 Rigorous를 사용한다.
•
cascading 롤백을 피한다. Recoverability를 보장한다
Lock Conversion
2PL은 보통의 경우 락을 업그레이드/다운그레이드가 가능하다.
Phase 1 : Growing Phase
•
S락을 얻을 수 있다.
•
X락을 얻을 수 있다.
•
S락을 X락으로 업그레이드할 수 있다.
Phase 2 : Shrinking Phase
•
S락을 릴리스할 수 있다.
•
X락을 릴리스할 수 있다.
•
X를 S로 다운그레이드할 수 있다.
Automatic Acquisition of Locks
read, write에 대해 자동적으로 락을 잡게끔 구현하는 방법도 존재한다.
if Ti has a lock on D
then
read(D)
else begin
if necessary wait until no other transaction has a lock-X on D
grant Ti a lock-S on D;
read(D)
end
C
복사
if Ti has a lock-X on D
then
write(D)
else begin
if necessary wait until no other trans. has any lock on D,
if Ti has a lock-S on D
then
upgrade lock on D to lock-X
else
grant Ti a lock-X on D
write(D)
end;
C
복사
Implementation of Locking
Transaction은 록 매니저(이하 록맨)에게 메시지의 형태로 락과 언락 메시지를 보낸다.
록맨은 Lock Table을 관리하고 있다.
Lock Table
Graph-Based Protocols
2PL은 Serializability를 보장해주기때문에 Data Correctness를 보장해주고 직관적인 장점이 있지만, 순서를 엄격하게 보장하고 있기 때문에 다소 성능이 느리다는 단점이 있다.
성능의 문제를 중점적으로 해결하려는 시도가 바로 Graph-Based Protocol이라 할 수 있겠다.
2PL이 아닌 다른 록 프로토콜을 개발하려면 Transaction이 Database를 어떻게 접근하는지에 대한 추가적인 정보가 필요하다.
가장 간단한 모델은 접근하려는 데이터 항목의 순서에 관한 사전 지식을 이용하는 것.
만약 일 때, Di와 Dj에 액세스하는 어떤 트랜잭션이라도 di를 dj 전에 방문해야한다.
Tree Protocols
여기에서는 Exclusive Lock만 가정한다.
Tree Protocol은 lock-X만 사용하며 각 트랜잭션 Ti는 한 데이터 항목에 대해 최대 한 번 잠금을 걸 수 있다.
트리 프로토콜은 다음의 규칙을 따른다.
1.
Ti의 첫뻔재 잠금은 어떤 데이터 항목에도 걸 수 있다.
2.
Ti는 Q의 부모에 해당하는 데이터 항목에 이미 잠금을 걸고 있는 경우에만 Q에 잠금을 걸 수 있다.
3.
데이터 록은 언제든지 해제할 수 있다.
4.
Ti가 록을 걸었다가 해제한 데이터는 다시 Ti가 잠금을 걸 수 없다.
이 규칙을 따르는 스케쥴은 모두 Conflict Serializability를 가진다.
•
Ti가 G와 I를 요구할 경우, B를 최우선적으로 잡은 후 D,E,G,I를 획득한다.
•
Ti와 Tj가 각각 I와 G를 가지고 있고, 서로 G와 I를 요구할 경우, 각각 부모노드를 가지지 않으므로,
락을 풀 때에는 상위 레벨의 노드에 대해 먼저 락을 풀 수 있다.
Example
lock-X(B); lock-X(E); lock-X(D); unlock(B); unlock(E); lock-X(G); unlock(D); unlock(G).
lock-X(D); lock-X(H); unlock(D); unlock(B).
lock-X(B); lock-X(E); unlock(E); unlock(B).
lock-X(D); lock-X(H); unlock(D); unlock(H).
위 스케쥴은 4개의 트랜잭션으로 조합가능한 스케쥴 중 하나를 나타낸 것이다.
Deadlock Handling
데드락은 100퍼센트 막는 것은 불가능하다.
따라서 여러가지 다양한 방법을 통해서 데드락을 예방하거나, 탐지하고, 이를 복구하는 작업을 구현해야한다.
Deadlock Prevention
데드락을 예방하는 것은
•
모든 프로토콜에서 사용가능한 것은 아니다.
•
wait-die : 비선점 방식
◦
오래된 Transaction이 새로생긴 Transaction이 데이터를 놓을 때까지 기다린다.
◦
새로생긴 Transaction은 Older한 Transaction을 기다리지 않는다. 즉, 롤백하여 죽는다.
◦
다만, 락을 잡기 전에 여러번 죽을 수도 있다.
•
wound-wait : 선점 방식
◦
오래된 Transaction이 새로 생긴 Transaction을 강제로 종료시킨다.
•
Timeout-Based Schemes
◦
락에 대해 시간을 쥐어주고 시간만큼 수행하지 못할 경우 롤백
◦
Transaction이 얼마나 실행될지는 알 수 없기 때문에(Halting Problem)
◦
구현하기 간단함.
Deadlock Detection
•
Wait-for Graph
◦
Vertices : Transactions
◦
Edge from Ti→Tj : Ti는 Tj가 가진 락을 기다리는 상태.
◦
만약 순환하는 사이클이 있을 경우, 데드락 디텍션이 가능하다.
◦
Deadlock Recovery
Multiple Granularity
•
Fine Granularity : 락 단위가 작아 높은 동시성, 락의 개수가 많아 오버헤드 큼
•
Coarse Granularity : 락의 개수가 적어 락 오버헤드 작음, 대신 락 규모가 개커서 동시성 작음
Intention Lock Mode
Compability Matrix with Intention Lock Modes
•
IS : 해당 노드보다 낮은 단계에 명시적 공유모드가 걸림
◦
IS를 건 해당 노드에 IS를 또 걸 수 있다.
◦
IS를 건 해당 노드에 IX를 걸 수 있다. 다만, 아무렇게나 다 호환되는 것은 아니며 IX를 거는 곳에 S락이 있는 노드가 없어야 한다.
◦
IS를 건 해당 노드에 S락을 걸어 전체를 덮을 수 있다.
◦
IS를 건 해당 노드에 SIX를 걸 수 있다.
•
IX : 해당 노드보다 낮은 단계에 명시적 독점 또는 공유모드로 잠금이 걸림
◦
IX를 건 노드에 S락을 걸게 될 경우, 하위 노드 중 X락이 걸려있을 경우 S락과 호환되지 않게 된다.
◦
마찬가지로 SIX또한 같은 원리로 호환되지 않음.
•
S : 해당 노드를 포함한 서브트리에 S락을 건다.
Multiple Granularity Locking Scheme
•
트랜잭션 Ti는 잠금 호환 관계를 따라야 한다.
•
트랜잭션 Ti는 먼저 트리의 루트에 모드에 상관없이 잠금을 걸어야 한다.
•
트랜잭션 Ti는 현재 Q의 부모가 IX나 IS모드로 잠금이 걸려있는 경우에만 노드 Q를 S 또는 IS 모드로 잠금을 걸 수 있다.
•
트랜잭션 Ti는 현재 Q의 부모가 IX 또는 SIX 모드로 잠금이 걸려있는 경우에만 노드 Q를 X, SIX 또는 IX 모드로 잠금을 걸 수 있다.
•
Ti가 이전에 어떤 락도 해제하지 않았을 때만 잠금을 걸 수 있다.(2PL이랑 동일한 규약)
•
Ti는 Q의 자손 중에 하나라도 잠금이 걸려있지 않아야 Q를 해제할 수 있다.
Insert/Delete Operations and Predicate Reads
•
Insert Delete 오퍼레이션의 룰
삭제 연산이
Phantom Phenomenon
select count(*)
from instructor
where dept_name = 'Physics';
C
복사
insert into instructor
values(11111,'Feynman', 'Physics', 94000);
C
복사
튜플 단위로 동시성 제어를 하면
Handling Phantom
결국에는 컨플릭이 데이터 레벨에 있다.
•
어떤 튜플이 어떤 Relation에 관계되어있고,
튜플에 잠금을 거는 것만으로는 충분하지 않으며, 튜플을 검색하기 위해 사용하는 정보에도 잠금이 필요하다.
Relation 전체에 락을 거는 것과 릴레이션에 대응하는 데이터에 락을 거는 것에 혼동하지 말자.
Index Locking to Prevent Phantoms
트랜잭션이 접근하는 모든 리프노드에 잠금을 건다.
Next-Key Locking to Prevent Phantoms
Next chapter