[Concurrency Control] Index-locking Protocol: The Way to Prevent Phantom Reads

* 본 글은 'Database System Concepts - 7th Edition(데이터베이스 시스템 7판)'을 바탕으로 작성하였습니다.

 

What is phantom read ?

---

i.e., Phantom phenomenon

 

이미 전 포스팅에서 다룬 개념이지만, 다시 명확하게 하는 겸 작성한다.

https://eunajung01.tistory.com/166

 

 

두 개의 transaction, T_1과 T_2가 있다고 하자. 둘은 각각 다음과 같은 SQL을 실행한다.

# T_1
insert into instructor values(11111, 'Feynman', 'Physics', 94000);

# T_2
select count(*)
from instructor
where dept_name='Physics';

T_2는 instructor relation에서 "dept_name='Physics'"인 모든 tuple에 접근해야 한다.

 

 

S를 T_1과 T_2를 포함하는 schedule이라고 한다면, T_1과 T_2는 다음과 같은 이유로 인해 conflict가 발생할 수 있다.

 

• T_2가 count(*)를 계산할 때 T_1이 새로 삽입한 tuple을 포함한다면 T_2는 T_1이 기록한 값을 읽는 것이다.
  그러므로 S와 동등한 seralizable schedule에서 T_1은 반드시 T_2 보다 먼저 나와야 한다.
• T_2가 count(*)를 계산할 때 T_1이 새로 삽입한 tuple을 포함하지 않는다면
  S와 동등한 seralizable schedule에서 T_2는 반드시 T_1 보다 먼저 나와야 한다.

 

특히 두 번째 경우를 보면, T_1과 T_2가 공통으로 접근하는 tuple이 없는데도 둘 사이에 conflict가 존재한다.

즉, T_1과 T_2는 phantom(유령) tuple로 인해 충돌을 일으키는 것이다.

 

만약 concurrency control을 tuple 단위로 하면 이러한 conflict를 탐지하지 못할 수 있고,

그 결과 시스템은 nonserializable schedule을 방지하지 못할 수 있다.

 

 

위는 insert 연산에 대한 예시였고, phantom phenomenon은 update 연산에 의해서도 발생할 수 있다.

(e.g., 어떤 tuple의 ‘dept_name’을 ‘Physics’로 변경하는 경우)

 

 

In general, the phantom phenomenon is rooted in predicate reads

that conflict with inserts or updates that result in new/updated tuples that satisfy the predicate.

 

 

How to prevent phantom reads ?

---

위 예시에서, phantom read를 방지하기 위해서는

 

T_2가 "dept_name='Physics'" 조건을 갖는 tuple을 instructor relation에 insert 하지 못하도록 막고,

이미 존재하는 instructor relation tuple의 dept_name을 'Physics'로 update 하지 못하도록 막아야 한다.

 

이를 위해서는 현재 접근하려는 tuple 하나에만 lock을 거는 것만으로는 충분하지 않고,

tuple을 검색하기 위해 사용하는 정보에 lock을 걸어야 한다.

 

1. Locking the entire data item

구현하기 가장 쉬운 방법이다.

 

Locking of information used to find tuples can be implemented by associating a data item with the relation;

the data item represents the information used to find the tuples in the relation.

 

여기서 data item은 index 전체라고 해석하면 된다.

 

 

• T_2와 같이 어떤 tuple이 relation에 있는지에 관한 정보를 읽어야 하는 transaction은
  그 relation에 대응하는 data item에 shared lock을 걸도록 한다.
• T_1과 같이 relation에 어떤 tuple이 있는지에 관한 정보를 갱신하는 transaction은
  그 relation에 대응하는 data item에 exclusive lock을 걸도록 한다.

이렇게 함으로써 T_1과 T_2는 (유령이 아닌) 실제 data item과 충돌을 하게 된다.

 

 

그러나, data item에 lock을 거는 것으로는

다른 transaction이 relation에 어떤 tuple이 있는지에 관한 정보를 갱신하지 못하도록 제한하는 것이 끝이다.

 

만약 tuple에 직접적으로 접근하는 transaction이 존재한다면 이는 소용이 없어지므로, 각 tuple에도 lock이 필요하다.

 

 

더 큰 문제는, 전체에 대한 lock을 걸어버렸으니 동시성이 떨어진다(== performance가 떨어진다)는 것이다.

즉, 하나의 relation에 서로 다른 tuple을 삽입하려고 하는 두 transaction을 동시에 처리할 수 없게 된다.

 

2. Index-locking protocol

위에서 거론한 문제들을 전부 해결할 수 있는 protocol이다.

 

한 relation에 tuple을 삽입하려는 transaction은

반드시 그 relation과 관련된 모든 index에 insert 하려는 tuple에 해당하는 정보를 추가해야 한다는 특성을 활용한다.

 

 

조건

• 모든 relation은 반드시 하나 이상의 index를 가져야 한다.
• Transaction T_i는 해당 relation의 index를 이용하여 검색한 다음에야 해당 tuple에 접근할 수 있다.
• Relation scan은 한 index의 모든 leaf node를 scan 해야 한다.

 

Transaction T_i가 range lookup 또는 point lookup을 하는 경우, 즉 reader인 경우

: T_i는 접근하려는 모든 index leaf node에 반드시 shared lock을 걸어야 한다.

 

Transaction T_i가 insert, delete 또는 update를 하는 경우, 즉 writer인 경우

• T_i는 relation r의 모든 Index를 갱신하지 않고는 relation r에 있는 tuple t_i를 갱신할 수 없다.
• T_i는 반드시 해당 연산으로 인해 영향을 받는 모든 index leaf node에 exclusive lock을 걸어야 한다.

 

이때 lock은 일반적인 경우처럼 tuple에 대해서 취해진다.

 

단, Index-locking protocol에서는 index의 internal node에 대한 동시성 제어를 포함하고 있지 않다.