[Database] DBA급 개발자로 - #8 Index Concurrency Control

이전 포스팅에서 B+Tree에 대해 살펴봤습니다. 이번 포스팅에서는 인덱스 동시성 문제를 어떻게 해결하는지 살펴보겠습니다. 

Concurrency Control 

여태까지 논의했던 B+Tree는 단일 스레드 환경에서만 정상적으로 동작합니다. 멀티 스레드 환경에서는 두 개 이상의 스레드가 동일한 노드에 동시에 접근할 수 있습니다. DBMS는 concurrency control protocol을 통해 동시에 접근되는 데이터를 물리적 또는 논리적으로 보호합니다. 

물리적 단위에서 데이터를 보호하는 것은 메모리 상의 데이터가 일관된 상태를 유지할 수 있도록 보호하는 것입니다. 
논리적 단위에서 데이터를 보호하는 것은 논리적으로 스레드가 접근할 수 있는 데이터에 접근할 수 있도록 보장하고 접근할 수 없는 데이터는 접근할 수 없도록 보장함으로써 보호하는 것입니다.  

 

이번 포스팅에서는 DBMS가 데이터를 어떻게 물리적으로 보호하는지 살펴보겠습니다. 

 

Latch 

이전 포스팅에서 latch는 데이터를 물리적으로 보호하기 위해 사용된다고 말씀드렸습니다. 더 자세하게 latch는 메모리에 저장된 데이터를 여러 스레드가 읽고 쓰더라도 정상적인 상태를 보장하기 위해 사용됩니다. Latch는 read와 write 모드를 가집니다. 

Read Mode: Read mode의 latch가 걸린 데이터는 다른 스레드에서 read latch 획득이 허용됩니다. 데이터에 write latch가 걸려 있다면 read latch는 획득할 수 없습니다. 
Write Mode: Write mode의 latch는 어떠한 스레드도 latch 획득을 시도할 수 없습니다.  

 

	read mode	write mode
read mode	o	x
write mode	x	x

다음으로는 latch가 내부적으로 어떻게 구현되는지 살펴보겠습니다. 

 

Blocking OS Mutex

std::mutex m;
...
m.lock();
// do something in critical section
m.unlock();

Blocking OS Mutex는 std::mutex와 같이 사용법이 단순합니다. 하지만 lock, unlock 함수의 실행 시간이 길기 때문에 확장성이 떨어집니다. 

Test-and-Set Spin Latch

std::atomic_flag latch;
...
while (latch.test_and_set(...)) {
  // retry ? yield ? abort ? 
}

CPU에서 단 하나의 명령으로 latch/unlatch가 가능하므로 속도가 빠릅니다. 하지만 위의 코드에서 볼 수 있듯이, while문을 통해 latch를 획득할 수 있는지 끊임없이 확인합니다. Latch 획득을 위한 경합이 많을수록 while 문을 도는데 소모되는 CPU cycle은 기하급수적으로 증가합니다. 

Reader-Writer Latches

Read-Write Latch

Read 또는 Write latch를 획득한 스레드의 수를 내부적으로 저장합니다. Read latch는 여러 개를 획득할 수 있지만 Write latch는 하나만 획득이 가능합니다. Reader-Writer latch는 latch를 획득하기 위해 대기 중인 스레드가 오래 기다리지 않도록(starvation) 구현해야 합니다. 

Hash Table Latching 

다음으로는 latch가 hash table에 어떻게 적용될 수 있는지 살펴보겠습니다. 스레드는 hash table의 page 또는 slot에 순차적으로 접근합니다. 스레드가 hash table에 접근하는 방법이 순차적이므로 deadlock이 발생하기 어렵습니다. 

Page Latch 

Page latch는 페이지 단위로 Reader-Writer latch를 사용하는 방식입니다. 페이지 전체에 latch를 거는 방식이므로 사용되지 않는 slot에도 불필요한 latch가 걸린다는 단점이 있습니다.

Page Latch

Slot Latch 

Page Latch와 다르게 작업이 필요한 slot에만 latch를 거는 방식입니다. 각각의 slot은 개별 latch를 가집니다. 

Slot Latch

B+Tree Concurrency Control

다음으로 B+Tree가 latch를 통해 어떻게 동시성 문제를 해결하는지 살펴보겠습니다. B+Tree에는 다음과 같은 동시성 문제가 발생할 수 있습니다. 

• 여러 스레드가 동시에 동일한 위치의 데이터를 수정하려고 하는 문제 
• 하나의 스레드가 B+Tree를 순회 중일 때 다른 스레드가 B+Tree split/merge를 유발하는 문제 

이런 문제를 해결하기 위해 B+Tree는 Latch crabbing/coupling을 활용합니다. 

Latch Crabbing / Coupling 

Latch crabbing/coupling은 latch를 획득하는 과정이 마치 게가 이동하는 과정과 유사해서 붙여진 명칭입니다. Latch crabbing/coupling은 다음과 같이 동작합니다. 

1. 부모 노드의 latch를 획득 
2. 부모 노드의 latch를 획득한 상태에서 자식 노드의 latch를 획득 
3. 자식 노드가 안전하다고 판단되면 부모 노드의 latch를 해제 

다음 조건을 만족하면 자식 노드가 안전하다고 판단됩니다. 

• 노드가 꽉 찬 상태가 아닐 때(insert가 수행되더라도 노드의 split이 발생하지 않을 때) 
• 노드가 절반 이상 차있을 때(delete가 수행되더라도 노드 간 merge가 발생하지 않을 때) 

Latch crabbing/coupling을 활용하면 동시에 여러 스레드가 효율적으로 B+Tree를 순회하거나 데이터 조작을 수행할 수 있습니다. 하지만 모든 스레드는 루트 노드에서 리프 노드로 향하기 때문에 루트 노드에 가까이 위치한 노드일수록 더 많은 래치 획득 경합이 발생합니다(병목이 될 수 있습니다). 만약 자식 노드 중 하나라도 안전하지 않다고 판단되면 해당 노드의 부모 노드들은 모두 latch가 걸리게 되므로 성능이 좋지 않을 수 있습니다. 이를 해결하기 위해 optimistic concurrency control을 활용할 수 있습니다. 

Optimistic concurrency control은 다음과 같이 동작합니다. 

1. 해당 노드의 latch만 획득하고 노드를 떠나면서 latch를 해제 
2. Leaf node에 도달하면 latch를 획득 
3. 만약 leaf node가 안전하지 않다면 기존의 방식(Latch Crabbing/Coupling)처럼 동작. 

 

마무리 

이번 포스팅을 통해 인덱스의 동시성 문제를 어떻게 처리하는지 살펴봤습니다. 다음 포스팅에서는 sorting와 aggregation 작업에 대해 살펴보겠습니다.