[Concurrency Control]Graph-based protocol

2PL의 대안인 graph-based protocol을 알아보자.

 

 

모든 데이터 아이템에 대한 set D이 있다고 하면 접근하는 순서가 partial ordering 을 만족시키면 acyclic한 그래프가 된다. 트리의 인덱스의 경우에는 이런 특정한 상황이 만족된다. 즉, tree-based protocol이 한 예이다.

 

tree-based protocol

X락만 허용

Ti의 첫 번째 락은 어떤 아이템에 대한 것이든 상관없다.

Ti가 데이터 Q에 락을 걸려면 Q의 부모에 락을 갖고 있어야 한다.

데이터는 언제든 언락 될수 있다.

같은 아이템에 대해서는 락을 걸고 풀었으면 락을 얻지 못한다.

 

참고적으로 이해하면 되겠다.

 

graph-based protocol은 conflict serializability을 보장하고 데드락에서 자유롭다(데드락 해소를 위한 롤백이 발생하지 않음). 즉, 데이터를 한 방향으로만 데이터를 접근하기 때문에 데드락이 발생하지 않고 언락이 자유롭기 때문에 기다리는 시간이 상대적으로 적다.

 

단점

하지만 2PL처럼 단계를 나누어 회복성을 보장하는 장치들이 없기 때문에 recoverability나 cascadeless rollback을 보장하지 못한다.

필요하지 않은 데이터에 락을 걸어야 한다. 이로 인한 대기 시간 증가나 concurrency를 감소시킬수 있다.