[Concurrency Control]Insert and Delete opertaion

phantom phemnomenon

부산 지점에 있는 모든 계좌의 금액을 합쳐서 부산 지점의 잔고와 비교하는 트랜잭션이 있다고 하자. 이 때, 동시에 부산 지점에 계좌가 하나 추가 된다면 어떻게 될까?

 

2 phase locking을 해도 insert, delete는 non-serializable schedule을 만들게 될 수 있다. 이런 상황을 phantom phemnomenon이라 한다.

 

이것을 해결하는 방식으로 delete, insert는 X lock를 획득한 상태로 진행해보자. 2PL 방식이다.

처음에 주어진 상황을 설명하는 예시는 다음과 같다.

phantom examxple

 

 

insert가 있어서 2PL을 해도 잘못된 결과가 나온다. 락의 단위를 튜플로 하면 이런 상황이 발생하게 된다. 테이블 단위 락을 사용하면 이 상황을 막을 수 있다. T2가 insert를 하려고 할 때 T1: read-Account를 하고 T1: read-Asset 이후에 언락 페이즈가 진행되기 때문이다. 즉, Account 테이블에 대한 락이 걸려있으므로 insert가 기다리게 된다.

하지만, 이 방식은 concurrency는 떨어진다. 

 

index locking

 2PL 대신 인덱싱 락킹을 사용하여 phantom problem을 막고 concurrency도 유지해준다. 이 방법은 tuple에 b+ 인덱스를 써서 인덱스에 락을 거는 것이다. b+ 트리 구조를 이용하여 튜플들을 찾아갈 수 있도록 만들어 놓고 운영한다.

 

read할 때에는 b+ 트리 상에서 노드에 락을 걸어서 read를 하는 도중에 다른 트랜잭션이 insert하지 못하도록 막는다. 정확하게는 root에 s 락을 걸고 read하려는 leaf까지 연관된 노드에 락을 건다. insert, update, delete인 경우에는 root부터 해당 튜플의 leaf 노드에 x락을 건다. 그런데 이렇게 해결하면 phantom problem은 해결되나 concurrency가 떨어진다.

 

crabbing

 concurrency를 높일 수 있는 개선 방안은 crabbing이다.

search, insert, delete 할 때 락을 이렇게 관리한다.

1. b+ 트리를 접근할 때 root에 s lock을 건다. 

2. leaf를 가기위해 필요한 하위 노드에 s 락을 걸고 root 락을 해제한다.

3. 필요한 leaf에 s 락을 걸고 2에서 건 락을 푼다.

4. insert, delete는 3에서 건 락을 업그레이드 한다. 

부모 노드에서 splitting이나 coalescing이 발생하면 부모 노드에 X락을 걸어야 한다.

단점 : 데드락이 생길 수 있다. 

 

이 경우는 leaf에서만 충돌이 발생하므로 concurrency를 높일 수 있다. 실제적으로 이렇게 구현한다고 한다. 더 좋은 protocol이 있다고 하니 관심있으면 찾아보면 좋을 것이다.