[17장] 동시성 제어 (2)

다단계 잠금 프로토콜

Intention Lock

테이블에 대해 tuple에 걸릴 수 있는 lock을 표시하는 선행적인 테이블 수준 lock이다.
DB는 file의 집합이고, file은 page의 집합 , page는 tuple의 집합이다.
이런 계층구조에서의 lock은 모든 자식들에 대한 묵시적 lock이 존재한다고 생각해도 무방하다.

상세 설명

위의 예시처럼, lock을 할 수 있는 Object는 여러개이다 ( DB , Table, Tuple...)
상이한 lock 단계를 지정하여 , 최대한 동시성을 보장하는 프로토콜이다.
다단계 잠금 프로토콜은 아래와 같다.

• 각 TX은 계층적으로 root부터 시작한다.
• 노드에 대해 S 혹은 IS lock을 획득 하고자 한다면 , 부모 node는 IS 혹은 IX lock을 소유하고 있어야 한다.
• 노드에 대해 X 혹은 IX 혹은 SIX를 획득하고자 한다면, 부모 node는 또한 IX 혹은 SIX를 소유하고 있어야 한다.
• 아래에서 위로 ( bottom - up) 소유하고 있는 lock을 순차적으로 release한다.

쉽게 말하자면 어떤 노드에 대해 S(X) lock으로 잠그기 위해서는 , 모든 조상들에 대해 IS(IX) lock으로 잠궈야한다.

• 어떤 TX이 특정 노드에 대해 S lock을 하게된다면 , 다른 TX들은 해당 노드의 모든 조상에 대해서 X lock이 불가능하다.
• 비슷하게, 어떤 TX이 특정 노드에 대해 X lock을 하게 된다면, 다른 TX들은 해당 노드의 모든 조상에 대해서 S 혹은 X lock이 불가능하다.

위의 프로토콜을 통해, 어떠한 다른 TX도 그 노드에 대한 lock인 S lock 혹은 X lock과 충돌하는 조상 노드에 대한 lock을 소유하고 있지 않다는 것을 보장한다.

프로토콜 사용 예시

• TX1이 R을 Scan하고 , 몇몇 tuple을 업데이트 하는 상황
  • TX1은 R에 대해 SIX lock을 획득, 그 후 반복적으로 R의 tuple들에 대해서 S lock을 획득한다. 이 후, 업데이트가 필요한 tuple들에 대해서 S lock을 X lock으로 업그레이드 해준다.
• TX2가 index를 사용하여 , R의 일부분을 read하는 상황
  • TX2가 R에 대해 IS lock을 획득. R의 tuple들에 대해서 S lock 획득.
• TX3가 R의 모든 부분을 read하는 상황
  • TX3가 R의 S lock을 획득
  • 혹은 , TX2가 했던것처럼 할 수도 있음

동적 DB에서의 비일관성 문제

Strict 2PL 프로토콜은 일반적인 DB에서의 인터리빙한 TX들에 대한 동시성 문제를 해결해 줄 수 있지만, 동적 DB의 경우에는 일관성을 보장하기 힘들다.

이런게 있다는 것 정도만 알고 넘어가자

Index Locking

인덱스 또한 lock이 필요한 자료구조이다. 만일, 원래 DB상의 데이터의 수정이 생긴다면 index lock이 없을 경우 비일관성이 발생할 수 있다.

B+ Tree Locking

• 어떻게 효과적으로 B+ Tree의 leaf에 대하여 lock을 할 수 있을까?
• 편하게 구현하고 쓸려면 , 사용하고 있는 Index를 lock 해버린다면 mutex가 보장된다. 하지만 , 그 성능은 끔찍할 것이다.

간단한 Tree Index Locking 알고리즘

• Search 연산
  index의 root부터 시작해서 S lock을 획득한다. 이후, Child의 S lock을 획득하고 parent의 lock을 release 해준다. leaf node에 닿을때까지 반복
• Insert / Delete 연산
  index의 root부터 시작해서 필요에 따라 X lock을 획득한다. Child가 lock을 획득하면 , Safe한지 검사하여 Safe할 경우 모든 Ancestor들의 lock을 release한다.
  • Safe 하다는 것은 delete/insert 연산시에 해당 노드의 차수규칙 ( d <= m <= 2d )이 지켜질 수 있는지 판정하는 것
    위와 같은 Node에서는 35가 삭제될 경우 , 차수규칙에 위배하게 되므로 안전하지 않은 상황이다.

하지만, 이렇게 Insert/Delete시에 조상들에 대하여 X lock을 획득한다면 다른 TX들이 해당 index를 동시에 활용하기 어려워진다.

향상된 Tree Locking 알고리즘

• Search 연산
  이전과 같다.
• Insert/Delete 연산
  ancestor에는 S lock을 걸어주고 , leaf에만 X lock을 걸어준다.(동시성 증가)
  만일 leaf가 not safe하다면( 즉, 연산의 결과로 index structure에 변화가 생긴다면) 소유했던 모든 lock을 풀어주고 기존의 Tree Locking 알고리즘을 사용한다.

더더욱 향상된 Tree Locking 알고리즘

그냥 처음부터 좀 알려주지...

• Search 연산
  이전과 같다.
• Insert / Delete 연산
  • Original Locking 알고리즘을 사용한다. 그 대신 , X lock대신에 IX lock을 사용한다.
  • leaf가 lock이 된다면 , top-down ( deadlock 감소 ) IX lock을 X lock으로 바꿔준다.

하이브리드 알고리즘

Lock을 사용하지 않는 알고리즘들

낙관적 동시성 제어 알고리즘

Kung Robinson Model
충돌이 일어날 확률은 낮다는 것에 기대는 알고리즘 ( 마치, OS에서 배웟던 타조 알고리즘과 같다. ) , TX을 진행하고 맨 마지막에 Conflict를 체크한다.
TX에는 3가지 단계가 존재한다.

• Read
  DB로부터 데이터를 read , 데이터 변경 후 local buffer에만 반영한 상태
• Validate
  충돌을 탐지. 충돌 시 , 해당 TX abort
  • 충돌을 탐지한다
  • 각 TX들은 numeric id(timestamp)를 부여
  • Read phase의 끝 , Validate의 직전에 id를 부여받는다
  • ReadSet(Ti) : TXi에 의해 read된 Object Set
  • Write(Ti) : TXi에 의해 write된 Object Set
• Write
  local change를 public에 반영

첫번째 케이스

• 겹치는 게 없이 Ti가 Tj의 시작전에 작업을 완료했으므로 OK

두번째 케이스

• Ti의 완료시점이 Tj의 write 이전이다
• WriteSet(Ti) 와 ReadSet(Tj) 의 교집합이 공집합이다

위의 필요조건이 만족되면 OK

세번째 케이스

• Ti의 readphase가 Tj의 readphase 전에 종료
• WirteSet(Ti)와 ReadSet(Tj)의 교집합이 공집합
• WriteSet(Ti)와 WriteSet(Tj)의 교집합이 공집합

위의 필요조건이 만족되면 OK. 그러나, 구현이 어렵다.

Time Stamp를 사용한 동시성 제어

각 DB Object에 대해서 read timestamp와 write timestamp를 준다.
각 TX이 시작될 때 TX timestamp를 준다.

• TX의 timestamp < Object의 wirtestamp
  • abort
• TX의 timestamp > Object의 writestamp
  • TX의 Object read를 허용
  • Object의 readtimestamp = max(TX타임스탬프 , Object 리드스탬프)

• T의 타임스탬프 < Object readtimestamp
  • abort
• T의 타임프탬프 < Object writetimestamp
  • abort
• 이 외의 경우, TX이 Object에 대한 write 허용