[CMU 15-445 Intro to DB Sys] Lec09 Index Concurrency

Concurrency Control

• to ensure "correct" results for concurrent operations on a shared object
  • logical correctness: 읽어야 하는 값을 잘 읽어온다는 의미
  • physical correctness: object의 internal representation이 제대로 되어 있다는 의미

Locks vs. Latches

• Locks(Transactions): high-level에서 db의 Logical contents를 다른 transaction들로부터 보호함. deadlock이 생기면 rollback할 수 있어야 함.
• latches(workers): low-level에서 DBMS의 internal data structure가 있는 critical section을 다른 worker(e.g. threads)로부터 보호함. 따라서 duration이 매우 짧으며, 별도의 rollback이 없음.

Latch modes

• read mode: 여러 스레드들이 동일한 object를 동시에 읽을 수 있음. 즉, 스레드는 다른 스레드가 read mode로 갖고 있으면 read latch를 획득 가능(write mode면 안 됨)
• write mode: 오직 한 스레드만이 객체를 접근할 수 있으며, 다른 스레드가 어떤 mode든 갖고 있으면 write latch를 가질 수 없음(즉, 어느 스레드도 latch를 갖고 있지 않아야 write latch를 가질 수 있다!)

Latch implementation

• goals: small memory footprint; fast execution path when no contention; deschedule thread when it has been waiting for too long; each latch should not have to implement own queue to track waiting threads

Test-and-Set Spin Latch(TAS)

• single instruction을 통해 test-and-set하여 latch/unlatch할 수 있기 때문에 매우 효율적이다.
• 하지만 (not scalable) CAS instruction이 여러 스레드에서 계속 수행되고 있기 때문에 high contention으로 축적되고, OS 입장에서 보았을 때는 스레드가 busy한 것처럼 보인다. (not cache friendly) NUMA에서 CPU가 멀리 있는 메모리의 latch를 획득하고 싶을 경우 다른 프로세서의 cache line을 계속 이용해야 해서 cache coherence를 저하시킨다.

Blocking OS Mutex

• OS의 mutex(e.g. C++의 std::mutex)를 사용하는 방법이다. 그래서 간단한데 역시 not scalable하다.
• 사실 C++의 mutex는 pthread_mutex로 구현되고, 이는 futex로 구현된다. 이는 user-space spin latch와 OS level mutex로 구성되어 있는데, 만약 user-space latch를 획득하지 못하면 OS level mutex를 획득해야 하고, 이는 kernel로 내려가야 하므로 expensive하다.

Reader-Writer Latches

• spin latch와 mutex는 기본적으로 Read/write를 구별하지 않는데, concurrent read를 허용하기 위해 reader-writer latch를 사용할 수 있다.
• 기본적으로 latch가 자체 read/write queue를 갖고 있다. 이를테면 이미 read 중인 스레드가 있으면 write하려는 스레드를 queue에 넣어서 기다리게 하는 식이다.
• 각 policy에 따라서 구현은 달라질 수 있는데, 이를테면 이미 read 중인 스레드로 인해 write를 기다리는 스레드가 있을 경우 새로운 스레드가 read하려고 해도 일단 queue로 보내는 식이다.
• C++의 std::shared_mutex를 사용하면 이는 pthread-rwlock으로 구현된다.

참고: Compare-and-Swap

• M 위치의 값을 주어진 값 V와 비교하는 atomic instruction
  • 만약 같으면, V'라는 새로운 값을 주고,
  • 그렇지 않으면 fail한다.

Hash Table Latching

• hash table에서는 자료구조에 접근할 수 있는 방법들이 제한되어 있기 때문에 비교적 concurrent access를 지원하기가 용이하다.
  • 모든 스레드들이 동일한 방향으로 움직이고 한번에 하나의 페이지/슬롯을 접근하기 때문에 deadlock은 발생하지 않는다.

Page Latches

• 각 페이지마다 reader-writer latch가 있다.

  Slot Latches

• 각 슬롯마다 reader-writer latch가 있다. parellel하게 접근할 수 있다는 장점이 있지만 storage 및 computational overhead가 발생한다.

B+tree Concurrency Control

Basic Latch Crabbing

• B+Tree에서는 여러 스레드가 동일한 노드의 내용을 동시에 바꾸려고 하거나, 한 스레드가 traverse하는 동안에 다른 스레드가 merge/split을 야기할 수 있다.
• 따라서 다음과 같은 순서로 latch crabbing을 한다.
  • 먼저, Parent에 대한 latch를 잡는다.
  • 다음으로, child에 대한 latch를 잡는다.
  • 만약 child가 "safe"하면 Parent에 대한 latch를 놓아도 된다.
    • 여기서 "safe"라는 것은 update로 인해 split/merge 등이 발생하지 않는다는 것이다. 즉, Insertion 연산에 대해서는 노드가 가득 차 있지 않으면 되고, deletion 연산에 대해서는 절반 초과로 차 있어야 한다는 것이다.
  • 단, read latch에서는 어차피 노드를 변화시키지 않기 때문에 safe 조건을 체크할 필요가 없다.

Improved Latch Crabbing

• 그러나 위의 pessimistic한 가정과 달리, 실제로 대부분의 변경은 split이나 Merge를 야기하지 않는다.
• 따라서 optimistic하게 read latch만을 사용하여 search하고, leaf에서 write latch를 건다. 만약 가정이 어긋났을 경우(즉 safe하지 않을 경우) 다시 시작해서 pessimistic하게 write latch로 traversal을 실시한다.
• 이렇게 하면 read를 더 많이 허용할 수 있으므로 parallelism을 강화해준다.

Leaf Node Scans

• 위와 같이 "top-down"으로 모두 같은 방향으로 움직일 때에는 deadlock이 발생할 수 없다. 하지만 leaf node에서는 여러 스레드가 서로 다른 방향으로 움직이면서 deadlock을 야기할 수 있다.
• 그런데 latch 입장에서는 이 상황이 deadlock인지를 알 수도 없고, 이를 피할 수도 없다. 따라서 coding discipline을 통해서만 이를 방지할 수 있다.
• leaf node sibling latch acquisition에 있어서는 "No-wait"을 지원해야 한다.