19. Two-Phase Locking, 2PL

서울대학교 데이터사이언스대학원 정형수 교수님의 "데이터사이언스 응용을 위한 빅데이터 및 지식 관리 시스템" 강의를 필기한 내용입니다.

• 목차

2PL Intro. §

• 2PL 은 PCC 의 대표격이라고 할 수 있는 놈이다.
• 여기서는 serializable 한 txn schedule 을 제공해야 하는데, 이 schedule 이라는 것을 미리 알수는 없기 때문에 Lock 을 이용해서 conflict detection 을 한다는 것이 기본 아이디어이다.
• 그래서 Lock Manager 가 있어서 txn 은 이놈을 통해 lock 을 얻는다.
  • Lock manager 에서는 어떤 txn 이 어떤 데이터를 어떤 권한으로 요청했는지를 전부 추적하고 있고,
  • 만약에 다른 txn 이 lock 을 잡았으면 그 다음에 오는 lock 요청은 deny 한 다음 해당 lock 이 풀렸을때 grant 하는 식으로 작동한다.
  • 이렇게 해서 conflict 를 발견하고, 나중에 grant 해주는 방식으로 serializable 하게 바꿀 수 있다는 것.

Lock §

Lock & Latch §

• Latch 와 비교해서 lock 의 특성에 대해 알아보면:

• 잡는 주체는 txn 이고
• Database content 를 보호하며
• Txn 이 관련된 작업을 하는 동안 lock 을 잡기 때문에 txn 의 lifetime 과 유사해진다.
  • 사실상 txn 의 lifetime 과 같다. 이건 COMMIT 시점에 lock 을 전부 풀기 때문인데, 뒤에 가면 알 수 있다.
• Deadlock detection, prevention 이 필요하다 (latch 는 deadlock 이 일어나면 그건 DBMS 설계 문제다: 버그임).
  • lock 은 txn 이 잡고, 이것을 잡는 순서는 DBMS 가 관리할 수 없기 때문에 (사실상 client 가 잡는것이기 때문에) deadlock 이 얼마든지 발생할 수 있다.
• 그리고 이것을 관리하는 중심인 lock manager 가 있다.
  • 이것은 in-memory table 인데 모든 txn 이 접근하기 때문에 여기가 contention 이 된다
  • 뭐 oracle 에서는 별도의 table 이 아닌 system column 처럼 기존 data table 에 녹여낸다고 한다.

Lock Types §

• Lock 의 type 에는 shared lock (SLOCK) 과 exclusive lock (XLOCK) 두 가지가 있다.
  • 이건 너가 아는거랑 별반 다르지 않기 때문에 생략 (C++ Shared Mutex, C++ Unique Lock)

Lock Manager, Lock Table §

• Lock 은 Lock Manager 에 의해 중앙 관리되고, 이놈은 Lock Table 로 status 를 관리한다.

• 위 그림이 Lock manager 를 통해 lock 을 사용하는 방법을 그린 것이다.
  • Txn 은 lock 을 Request (혹은 Upgrade) 하는 요청을 보내면
  • Lock manager 는 Lock table 을 확인해서 해당 object 를 locking 할 수 있으면 Grant 를, 없으면 Deny (혹은 Block) 한다.
  • 그리고 txn 은 grant 받은 lock 을 다 사용한 후에는 Release 한다.
• Lock manager 에서는 이 lock table 로 어떤 txn 이 어떤 권한 (SLOCK, XLOCK 등) 으로 어떤 object lock 했는지와 이놈을 어떤 txn 들이 더 요청해서 대기하고 있는지를 관리한다.
• 통상적으로 lock table 은 hashtable 로 관리된다.
  • 그래서 lock hash table 로 부르기도 한다.
  • Conflict detection 의 목적이기에, CURP 에서 witness 와 유사한 목적이라고 할 수 있는 것.
  • tuple 의 conflict 를 체크해야 하기 때문에 tuple (RID?) 를 key 로 해서 찾게 한다.
• 근데 사실 여기에는 문제가 있다.
  • 일단 하나의 tuple 에 lock 을 잡고 release 할 때마다 lock manager 에 접근하기 때문에 여기에의 contention 이 몰리게 된다.
  • 또한 txn 은 각 tuple 별로 lock 을 잡기 때문에 통상적으로 lock 을 여러개 잡는다.
    • 근데 만약 lock manager 에서의 hash table 에 slotted latch 를 사용해 버리면 deadlatch 가 발생하게 된다.
    • 따라서 lock hash table 은 table-wide latch 를 사용하고, 이 또한 bottleneck 이 된다.

Lock Manager API Reference §

• 수업 자료에 있는 것인데, 아마도 PostgreSQL 인갑다.

• Lock manager 에는 RID (record_id) 를 인자로 lock_acquire() 를 호출하고, 만약 grant 된다면 *lock_obj pointer 를 받게 된다.
• Release 할 때는 받았던 *lock_obj pointer 를 인자로 lock_release() 를 호출한다.

• Lock hash table 은 Table ID 와 Record ID 를 combine 해서 hash 를 돌려 hash table entry 를 찾아가게 된다.
• 이때 hash table implementation 은 구현하기 나름이다. 어떤 collision handling 을 사용하던 상관없다.

• 각 hash table entry 는 위처럼 생겼다. 해당 entry 가 대변하는 Table ID 와 Record ID 가 적히고, 여기에 linked list 가 있어서 해당 lock 을 사용하거나 대기중인 thread 가 매달려 있다.
  • head 에 있는 놈만이 해당 lock 을 잡고 실행중에 있고, 나머지는 대기중이게 된다.
  • 만약 head 에 있던 놈이 끝나면, 다음 놈을 깨워주게 된다. 이때는 condition variable 을 이용한 spinlock 으로 구현되는 (것 같은) 데, 이건 다음 그림에서 보자.

• 이게 각 lock object 의 모습이다.
• 여기에는 linked list 를 위한 prev, next pointer 와 hash table entry 를 가리키는 sentinel pointer 가 달려 있다.
• 그리고 여기에 condition variable 이 달려 있어서 running 과 waiting 을 관제하게 된다.
  • 즉, head 에 있던 놈이 release 를 하면, 그놈은 지우고 다음 놈을 head 로 만든 다음 이 conditional variable 을 atomic 하게 바꿔서 깨우게 되는 것.

Two-phase Locking, 2PL §

• Lock 을 잡아서 conflict 를 detect 하고, 다른놈이 오면 block 이 되니까 자연스레 conflict serializable 로 되겠거니 하겠지만, 실제로는 그렇지 않다.
• 다음의 상황을 보자.

• 보면 lock 을 아주 정상적으로 사용하는데에도, lock 을 중간에 놓아버리면 다른 txn 이 끼어들어 값을 바꿔 Unrepeatable Read 가 발생한다.
• 즉, serializable 에 위배되는 것. 따라서 이것을 그냥 naive 하게 적용하면 안된다.
• 여기서의 문제점은 잡았다가 commit 전에 풀어버리면 다른놈이 들어와서 잡게 되기 때문에 발생하는 것이다.
  • 따라서 release 은 최대한 늦게하도록 하는데, 다른관점에서 보면 푼 다음에 다시 잡으면 안되게 하는 것이 핵심 아이디어이다.
• 그래서 Two-phase locking (2PL) 이 등장하게 되는데, 이것은 phase 를 2개로 나눠 첫번째 phase 에서는 lock 을 잡을수만 있게 하고 (Growing Phase), 두번째 phase 에서는 놓을수만 있게 하는 것이다 (Shrinking Phase).
  • 즉, 한번 unlock 했으면 그 이후에는 계속 unlock 만 할 수 있다.

• 이걸 그림으로 나타내면 위와 같다.
• 이 방법을 이용하면, 아래 그림처럼 schedule 이 의도한 대로 serializable 로 바뀌게 된다.

Strong Strict 2PL §

• 근데 위와 같이 2PL 을 적용하는 것은 cascading abort 문제가 있다.
• 아래의 예시를 보자.

• $T_1$ 이 shringking phase 가 되어서 $A$ 를 unlock 했을 때, $T_2$ 이 lock 을 잡아서 읽는 것이 가능한데, $T_1$ 이 ABORT 가 되면 $T_2$ 가 읽은 것은 dirty read 가 되어서 이놈도 ABORT 된다.
  • 근데 이런 dependency chain 이 길어지게 되면, 한놈이 ABORT 되면 이놈의 uncommited write 을 읽은 모든 txn 들이 전부다 ABORT 된다.
  • 이 문제를 Cascading Abort 라고 한다.
• 따라서 이런 문제를 없애기 위해 COMMIT, ABORT 직전에만 unlock 할 수 있게 하는 방법이 Strong Strict 2PL, Rigorous 2PL 혹은 그냥 2PL 이라고 한다.
  • 위에서 말한 2PL 은 naive 버전이고, 통상적으로 2PL 이라고 하면 이런 Strong Strict 2PL 을 일컫는다.
• 그래서 이때는 txn 의 lock count 가 요래 된다.

• 이런 2PL 을 사용하게 되면 한 txn 이 write 한 내용은 이놈이 끝날때까지 그 누구도 읽거나 쓸 수 없다.
  • 이런 “Write value 를 txn 종료 전까지 그 누구도 read, write 할 수 없는 schedule” 을 Strict Schedule 이라고 한다.
  • 이 정책은 cascading abort 도 막을 수 있고, ABORT 시에 그냥 자신이 변경한 데이터를 원래대로 되돌려놓기만 하면 되는 장점이 있다.
• 이런 2PL 에서는 첫번째 conflict 가 나면 먼저 시작한 놈이 끝날때까지 다음 시작한 놈은 전부 밀린다: 이것이 conflict serializable 에서의 첫번째 conflict 순서를 따라간다는 관찰과 동일한 것.

Early Lock Release (ELR) §

• Strong Strict 2PL 하지 않고, Lock 을 미리 푸는 것을 ELR (Early Lock Release) 이라고 부른다.
• 이때는 lock 을 소지하는 시간이 보다 짧아지기 때문에 concurrency 를 더 높일 수는 있지만, cascading abort 가 발생할 수 있다.
• 이런 위험성을 감안하고서라도 ELR 을 사용하겠다고 한다면, 다음과 같은 Parking Mechanism 을 사용할 수 있다.
  • ELR 된 데이터에는 마킹을 해놓아 이놈이 위험한 놈이라는 것을 표시해놓고
  • 이 데이터를 사용하는 txn 들이 생성한 데이터들도 전부 마킹을 하도록 한다.
  • 그리고 COMMIT 하기 전에 내가 의존하고 있는 txn 도 COMMIT 되었냐를 확인하고 그렇지 않다면 기다린다.
  • 그래서 저놈이 COMMIT 하면 나도 COMMIT 되는 것이고, 저놈이 ABORT 되면 나도 ABORT 되는 것.

여기부터는 2024-11-20 강의

2PL Deadlock §

• 2PL 에서는 당연히 여러개의 lock 을 잡기 때문에 deadlock 이 발생할 수 있다.
• 하지만 txn 이 어떻게 요청될 지 모르기 때문에 이 deadlock 을 선천적으로 막아버릴 수 (avoid) 는 없기 때문에
• Deadlock 를 미리 방지하거나 (prevent) 발생했을 때 풀어주는 (detect) 방법이 필요하다.

Deadlock Prevention §

• Deadlock Prevention 은 deadlock 이 발생할만한 lock acquire request 가 들어오면, 둘 중 하나를 kill 해버려 deadlock 을 미연에 방지하는 것이다.
• Deadlock Prevention 의 가장 기본 원리는 (OS 에서 배운것 처럼) ordered locking 이다.
  • 즉, 한쪽 방향으로만 lock 을 잡게 해서 deadlock 이 발생하지 않게 하는 것.
  • B+ concurrency 에서 latch coupling 에서는 index scan 방향을 한쪽으로만 수행하게 해서 이런 deadlatch 를 방지한다고 한다.

• 그럼 이제 어떻게 ordered locking 을 할 것이냐 (메커니즘을 어떻게 설계할 것이냐):
  • 기다리는 상황이 발생했을 때 “나이 (age)” 를 기준으로 priority 를 정하는데
  • Wait-die: Old waits for Young
    • Old 가 기다리고 Young 이 사용: Age 가 적은 놈이 우선순위가 높음
  • Wound-wait: Young waits for Old
    • Young 이 기다리고 Old 이 사용: Age 가 많은 놈이 우선순위가 높음
  • 이 둘중 하나의 정책을 이용해 기다리는 순서를 전부 통일시키게 되는 것.
  • 만약 우선순위가 밀려 내가 사용중이었는데 기다려야 하는 상황이 되면 나는 ABORT 되는 방식으로 대기상태로 가게 된다.
    • 다만 ABORT 되면 원래의 txn ID 를 유지해 우선순위가 바뀌지 않게 한다.
    • 만약 그렇지 않으면 우선순위가 낮아서 ABORT 되었는데 이후에는 우선순위가 높아져 내가 저놈을 빼앗게 되고, 이런식으로 계속 우선순위가 바뀌며 서로 ABORT 를 해버리는 상황이 발생할 수 있기 때문.

Deadlock Detection §

• 여기서는 Waits-For Graph 를 그린다.
  • 각 txn $T_i$ 와 txn $T_j$ 가 node 가 되고
  • Edge $T_i\to T_j$ 면 txn $T_i$ 가 txn $T_j$ 을 기다리고 있다는 의미
  • 이때 cyclic 이 되면 deadlock 이 발생한다.
• Lock manager 가 주기적으로 이 graph 를 그리면서 deadlock 이 발생했는지 확인한다.
  • Lock manager 의 check 주기는 고정되어있지 않고 deadlock 이 없으면 점점 주기를 늘려가다가 deadlock 이 발생하면 다시 자주 체크하는 것으로 줄이는 방식을 사용한다.
• Deadlock 을 풀기 위해 kill (혹은 rollback) victim 을 정하는 것은 뭐 정해진 규칙은 없고 DBMS 마다 다르다.
  • 가령 AWS RDS 에서는 write 를 많이 할수록 우선순위가 높아져 kill 되지 않게 한다.
    • 왜냐면 write 를 많이 했다는 것은 수행한 작업이 많다는 의미이기에, kill penalty 가 커지기 때문.
  • 아니면 age 를 활용하거나, 지금까지 몇번 victim 으로 선정됐냐 등을 고려할 수도 있다고 한다.
• Victim 을 정하고 나서도 어떻게 할지도 DBMS 마다 다르다.
  • 일반적으로는 그냥 ABORT 를 때려 해당 txn 이 처음부터 다시 시작하도록 하는데
  • 그렇게 안하고 일부 operation 만 rollback 해서 올라가는 방법을 사용하기도 한다.

Lock Granularity, Lock Hierarchy §

• Lock 은 latch 에 비해 잡는 overhead 가 더 크다.
  • Latch 는 그냥 단순히 atomic instruction 혹은 mutex (syscall) 정도지만
  • Lock 은 lock manager 에게 접근해서 lock table 에 넣는 등의 귀찮은 작업을 해야 하기 때문.
• 그럼 lock 을 잡는 단위 (lock granularity) 를 어떻게 가져갈 것이냐:
  • 만약 너무 작게 설정하면 많은 데이터에 접근할 때 많은 lock 을 잡아야 하는 문제가 생기고
  • 너무 크게 설정하면 concurrency 가 줄어드는 trade-off 가 있다.

• 그래서 여러 granularity 로 lock 을 잡을 수 있도록 한다.
  • Database, table, page, tuple, domain(attr) 등의 단위가 존재하며
  • 이런애들을 Granular Lock 이라고 한다.
• 다만 coarse-granular lock 을 잡는 것은 concurrency 를 줄이는 효과가 나고 fine-granular lock 을 너무 많이 잡는 것은 lock table overflow 의 효과가 나는 tradeoff 가 있다.
• 이때 low-level lock 을 너무 많이 잡으면 더 높은 level 의 lock 으로 promotion 해버리는 Lock Escalation 라는 최적화도 있다고 한다.

Intention Lock §

• Table 에 대해 SLOCK 을 잡는다는 것은 table 의 모든 tuple 에 SLOCK 을 잡는 것과 동치이다.
• 근데 만약에 어떤 tuple 에 대해 XLOCK 이 잡혀있다면, table 에 SLOCK 을 잡는 것은 불가능한 것이 맞을 것이다.
• 근데 문제는 table level 에서는 각 tuple 에 lock 이 잡혔는지 안잡혔는지 모르고, 이것을 알기 위해서는 일일이 찾아보는 수밖에 없다.
• 이런 것을 쉽게 하기 위해 나온 것이 Intention Lock 이다.
• Txn 이 lock 을 잡을 때 해당 object 의 상위 계층의 object 에 의도 (intention) 를 담은 lock 을 잡는 것을 Intention Lock 이라고 한다.
  • 즉, 이 Intention Lock 이라는 것은 “내가 당신의 children 에 이런 의도로 lock 을 잡으려고 합니다” 라는 것을 명시하는 용도인 것이다.
• 그래서 Intention Lock 의 종류는:
  • IS: “더 작은 단위의 obj 에 대해 shared lock 을 걸 것이다.”
  • IX: “더 작은 단위의 obj 에 대해 xclusive lock 을 걸 것이다.”
  • SIX: “큰 단위의 obj 에 shared lock 을 걸어 읽은 뒤에 (big shared), 작은 단위의 obj 를 변경할 것이다 (small intented xclusive).”
• 그리고 Intention Lock 까지 다 포함한 compatibility matrix 는 다음과 같다.

• 하나씩 살펴보자.
  • IS 를 걸면 lower level 에 누군가 shared 를 걸었다는 것이다. 따라서 이때는 upper level 에 xclusive 를 거는것 (X) 만 막힌다.
  • IX 를 걸면 lower level 에 누군가 xclusive 를 걸었다는 것이다. 따라서 이때는 upper level 에 shared 및 xclusive 를 거는 것 (S, SIX, X) 이 모두 막힌다.
  • S 를 걸면 내가 지금 upper level 에 shared 를 걸었다는 의미이다. 따라서 이때는 upper, lower level 모두에 xclusive 를 거는 모든 것 (IX, SIX, X) 이 막힌다.
  • SIX 를 걸면 내가 지금 upper level 에 shared 를 걸고, lower level 에 xclusive 를 걸었다는 의미이다. 따라서 이때는 lower level 에 shared 를 거는 (IS) 만 허용된다.
  • X 를 걸면 내가 지금 upper level 에 xclusive 를 걸었다는 것이다. 따라서 이때는 모든게 막힌다.
• 그럼 이때 locking protocol 은 다음과 같이 된다:
  • 만약에 S 나 IS 를 걸고자 한다면, parent 에 적어도 IS 는 먼저 잡아야 한다.
  • 만약에 X, IX, SIX 를 걸고자 한다면, parent 에 적어도 IX 는 먼저 잡아야 한다.
• 실제 구현에는 table 에 S 대신 IS 를 잡고 각 tuple 에 S 를 그때그때 잡기도 한다.
  • 이렇게 하면 concurrency 를 좀 더 늘릴 수 있기 때문.
  • 다만 이렇게 하면 중간중간 tuple 에 걸린 X 를 기다려야 할 수도 있다.

Example §

• Intention Lock 까지 추가된 locking protocol 을 예를 들어 설명해 보자.
• 우선 txn $T_1$ 은 table $R$ 를 scan 하고 tuple $t_n$ 을 변경하려고 한다.
• 따라서 이놈은 $R$ 에 SIX 를 걸고 $t_n$ 에 X 를 걸게 된다.

• 다음으로는 txn $T_2$ 가 $R$ 의 tuple $t_1$ 하나를 읽으려고 한다.
• 따라서 이때는 $R$ 에 IS 를 걸고 $t_1$ 에 S 를 건다.

• 마지막으로 txn $T_3$ 가 $R$ 을 scan 하려고 한다.
• 따라서 이때는 $R$ 에 S 를 걸려고 하지만, SIX 에 막혀서 block 된다.

Manual Locking §

• 일반적으로는 명시적으로 lock 을 잡지 않아도 되지만 concurrency hint 를 위해 명시적으로 잡는 것도 가능하다.
  • 가령 LOCK TABLE ... 으로 table lock 을 명시적으로 잡을 수 있고
  • SELECT ... FOR UPDATE 으로 SIX 를 잡을 수 있다고 한다.