Insert and Delete Operations

Insert and Delete Operations

원칙적으로, Insert와 Delete는 X-Lock을 가지고 수행되어야 한다.

그러나 tuple 을 Insert와 Delete하려고 할 때 Phantom 현상이 생길 수 있다.

 

Phantom Phenomenon

T1 : Account 테이블에서 부산의 모든 balance 의 합과 Assets의 부산의 값이 같은지 비교한다.

T2 : Account 테이블에 <400, Busan, 700> tuple 을 추가하고, Assets 테이블 도 업데이트한다.

 

Possible 2PL-based execution

여기서 T1 은 1500 (처음에 Account 의 Sum) 과 2200 (Assests 에서 읽은 값) 을 비교하여 둘이 다르다고 생각한다.

위 결과는 <T1, T2> 혹은 <T2, T1> 그 어떤 것과도 같지 않으므로 serializable 하지 않다.

 

tuple level locking 을 하면 T1트랜잭션 관점에서 Busan 계좌의 합이 맞지 않다고 생각하는 오류가 발생한다.

-> 이를 팬텀 현상이라고 한다.

팬텀 현상이 일어나는 스케줄은 직렬가능하지 않다.
팬텀 현상은 tuple level locking 에 의해 일어난다.

 

How to Handle Phantom Problem

- Insert, Delete 하는 tuple 이 없으면 phantom 현상은 발생하지 않는다. -> 비현실적

- Table Locking을 한다. -> 문제는 해결되나, 동시성이 매우 낮다

- Index Locking (동시성 보장)

- 모든 관계 테이블은 최소 하나의 인덱스를 가진다.
- 트랜잭션은 하나, 또는 여러개의 인덱스들을 통해서만 튜플에 접근할 수 있다.
- Index Lokcing은 특정한 인덱스 노드에 Lock을 취함으로써 더 높은 동시성을 가진다.
-> 위의 예시에서 T2가 새로운 튜플을 insert 해야하는데, T1이 해당 index 노드에 대해 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

index 는 트랜잭션이 데이터에 접근하는 것을 도와준다. 

index 구조는 실제 데이터 아이템보다 훨씬 자주 접근된다.

index 구조에 2-phase locking 을 적용하면 동시성이 매우 떨어진다.
index 구조의 내부 노드에 대한 lock을 미리 해제하는 동시성 제어 방식이 더욱 효율적일 것이다.

 

Crabbing for Index Structures

two-phase locking 대신에 Crabbing을 사용하면 동시성을 보장할 수 있다.

- B+ Tree에서 루트노드에 대한 S-Lock을 건다.
- 필요한 자식 노드를 S-Lock을 걸고, 부모 노드(자기 자신)의 lock 은 푼다.
- Insert, Delete 연산을 하는 중에는 leaf node 의 lock들을 X-Lock으로 upgrade 한다.
- split/merge을 함으로써 부모노드를 변화시켜야 한다면, 부모 노드에 X-Lock으을 건다.
- 과도한 deadlock을 일으킬 수 있다.