개념

잠금은 직렬성(serializability)을 위해 가장 널리 사용되는 방법 중 하나이다.

개념은 다음과 같다.1

  • 각 트랜잭션은 사용하는 데이터에 대한 액세스를 예비할당(reservation)한다. 이 예비할당을 잠금이라고 한다.
  • 읽기 잠금(read lock)과 쓰기 잠금(write lock)이 있다.
  • 데이터를 읽기 전에 트랜잭션은 읽기 잠금을 설정한다. 데이터를 쓰기 전에는 쓰기 잠금을 설정한다.
  • 읽기 잠금은 쓰기 잠금과 충돌을 일으키며, 쓰기 잠금은 읽기 잠금 및 쓰기 잠금과 충돌을 일으킨다.
  • 트랜잭션은 같은 데이터 항목에 대하여 다른 트랜잭션과 충돌을 일으키는 잠금이 없을 경우에만 잠금을 설정할 수 있다.
    • 트랜잭션은 데이터 항목 x에서 쓰기 잠금이 없는 경우에만 x에서 읽기 잠금을 설정할 수 있다.
    • 트랜잭션은 데이터 항목 x에서 읽기 잠금과 쓰기 잠금이 없는 경우에만 x에서 쓰기 잠금을 설정할 수 있다.

  • 충돌(Conflict): 동일한 데이터에서 일어나는 두 연산 중 적어도 하나가 쓰기 연산이라면 두 연산은 충돌을 일으킨다.

  • 잠금은 트랜잭션과 트랜잭션 사이의 간섭을 방지한다.
  • 동시에 실행 중인 트랜잭션이 많을수록 지연이 발생할 확률이 높다.

2단계 잠금 (two-phase locking)

2단계 잠금을 줄여서 2PL 이라고 부르기도 한다.

모든 경우에 직렬 실행을 보장하는 잠금 규칙을 2단계 잠금(two-phase locking)이라고 한다. 이것은 트랜잭션이 잠금을 해제하기 전에 목적을 완료해야 한다는 것이다. 트랜잭션은 이 규칙을 따를 때 2단계 잠금, 즉 트랜잭션이 잠금을 얻는 단계와 트랜잭션이 잠금을 해제하는 단계를 거친다.
2단계 잠금 이론: 어떤 실행에서 모든 트랜잭션을 2단계로 잠금을 하는 경우에 그 실행은 직렬적이다.2

2단계 잠금은 이름대로 두 단계로 이루어진다.

  1. Expanding phase: 트랜잭션이 잠금을 얻는 단계
    • 확장 단계. growing phase라고도 한다.
  2. Shrinking phase: 트랜잭션이 잠금을 해제하는 단계
    • 축소 단계.

2단계 잠금 이론은 다음을 가정한다.

  • 트랜잭션은 읽기와 쓰기 연산을 통해서만 상호작용한다.
  • 트랜잭션이 상호작용할 수 있는 모든 연산은 잠금으로 보호해야 한다.

다음은 두 개의 트랜잭션 \(T_1, T_2\)가 데이터 x, y를 읽고 쓰며 잠금을 설정하고 해제하는 실행(\(E\))의 예이다. 이 실행은 잠금 해제 타이밍에 문제가 있어 직렬적이지 못하다.

\[\begin{align} E = & rl_1[x] \ r_1[x] \ ru_1[x] \\ & rl_2[y] \ r_2[y] \ wl_2[x] \ w_2[x] \ ru_2[y] \ wu_2[x] \\ & wl_1[y] \ w_1[y] \ wu_1[y] \end{align}\]

복잡해 보이지만 하나하나 읽어보면 다음과 같다.

시간흐름 작업 데이터 X에 대해 데이터 Y에 대해
0 \(rl_1[x]\) \(\color{red}{T_1}\) read lock  
1 \(r_1[x]\) \(\color{red}{T_1}\) read  
2 \(ru_1[x]\) \(\color{red}{T_1}\) read unlock  
3 \(rl_2[y]\)   \(\color{blue}{T_2}\) read lock
4 \(r_2[y]\)   \(\color{blue}{T_2}\) read
5 \(wl_2[x]\) \(\color{blue}{T_2}\) write lock  
6 \(w_2[x]\) \(\color{blue}{T_2}\) write  
7 \(ru_2[y]\)   \(\color{blue}{T_2}\) read unlock
8 \(wu_2[x]\) \(\color{blue}{T_2}\) write unlock  
9 \(wl_1[y]\)   \(\color{red}{T_1}\) write lock
10 \(w_1[y]\)   \(\color{red}{T_1}\) write
11 \(wu_1[y]\)   \(\color{red}{T_1}\) write unlock

잠금을 생각하지 않고 읽기와 쓰기 연산만 남겨보면 다음과 같다.

\[E' = r_1[x] \ r_2[y] \ w_2[x] \ w_1[y]\]
시간흐름 작업 데이터 X에 대해 데이터 Y에 대해
1 \(r_1[x]\) \(\color{red}{T_1}\) read  
4 \(r_2[y]\)   \(\color{blue}{T_2}\) read
6 \(w_2[x]\) \(\color{blue}{T_2}\) write  
10 \(w_1[y]\)   \(\color{red}{T_1}\) write

\(E, E'\)가 직렬적이지 못하다. 왜냐하면 \(E\)의 결과가 \(T_1\)을 먼저 실행하고 \(T_2\)를 실행한 결과와 같지 않으며, \(T_2, T_1\) 순으로 실행한 결과와도 같지 않기 때문이다.

잠금 관리자의 구현

// data-item에 대해서 lock-mode로 지정한 잠금을 설정한다
Lock(transaction-id, data-item, lock-mode)

// transaction-id 트랜잭션에서 사용하는 data-item에 대해 잠금을 해제한다
Unlock(transaction-id, data-item)

// transaction-id 트랜잭션의 모든 잠금을 해제한다
Unlock(transaction-id)
  • 잠금/해제 연산은 잠금 정보를 lock table에 입력하거나 삭제한다.
  • lock table의 각 엔트리는 대상 데이터에 대해 다음을 포함한다.
    • 설정된 모든 잠금 정보.
    • (아직 허가하지 않은) 잠금 요청의 리스트.
  • 잠금 관리자가 잠금 요청을 받은 경우
    • 잠금을 잠금 요청 목록에 추가한다.
    • 충돌을 일으키는 잠금이 있다면, 문제의 잠금이 해제된 다음에 잠금을 승인한다.
    • (잠금을 요청한 트랜잭션은 잠금 요청이 승인될 때까지 차단되어, 기다려야 한다.)
  • 각 데이터 항목에 대한 잠금 연산은 서로에 대해 원자적이어야 한다.
    • 잠금 연산은 다음 연산을 시작하기 전에 완료되어야 한다.
  • 데이터베이스의 경우, 데이터베이스의 모든 레이어에서 잠금이 설정될 수 있다.
    • 페이지 지향 파일 레이어의 경우: 페이지 잠금 가능.
    • 레코드 지향 파일 레이어의 경우: 개별 레코드(row) 잠금 설정 가능.
    • 쿼리 실행기 레이어의 경우: 테이블이나 테이블 레코드에 대한 잠금 설정 가능.

멀티 단위 잠금

  • 서로 다른 잠금 단위에 대처하기 위한 기법.
    • 작은 단위 잠금을 하기 전에 큰 단위에 대해 의도적인 잠금을 설정하는 것.

데드락(Deadlock)

둘 이상의 트랜잭션이 충돌을 일으키는 잠금을 두고 경쟁할 때, 이들 가운데 어떤 것은 차단되어 잠금해제까지 기다려야 한다. 때로는 트랜잭션의 집합이 모두 상대를 기다린다. 그 집합의 각각은 차단되며 그것은 다시 다른 트랜잭션을 차단하고 있다. 이런 경우에는 시스템이 개입하지 않는 한 어떠한 트랜잭션도 진행할 수가 없는데, 이것을 트랜잭션이 데드락(deadlock)에 있다고 한다.

(중략)

데드락은 2단계 잠금이 비직렬성 실행을 탐지하는 방법이다. 데드락이 발생할 때에는 직렬성을 보장하면서 나머지 연산의 실행을 가능하게 하는 방법은 없다.

(중략)

일단 데드락이 발생하면, 데드락인 트랜잭션을 처리하기 위한 유일한 방법은 이들 가운데 적어도 하나가 다른 트랜잭션을 차단하고 있는 잠금을 포기하는 것이다. 트랜잭션이 잠금을 해제하면, 2단계 잠금 규칙에 따라 더 이상 잠금을 얻을 수 없다. 그러나 데드락에 있는 각 트랜잭션은 적어도 하나의 잠금을 얻어야만 하므로(그렇지 않으면 차단되므로) 어떤 잠금을 포기하여 2단계 잠금 규칙을 위반해야만 한다. 그러므로 트랜잭션이 꼭 하나의 잠금만 해제하게 하는 것은 의미가 없다. 데이터 관리자는 트랜잭션 전체를 abort 해야 한다. 즉, 데드락을 타개하는 유일한 방법은 데드락과 관련되는 트랜잭션 가운데 하나를 abort 하는 것이다. 3

데드락 방지

데드락 탐지

타임아웃 기반 탐지

  • 타임아웃 시간을 지정하여, 트랜잭션이 너무 오래 차단되면 데드락 발생을 추정하는 방식.
  • 실제로는 데드락이 아니라 오래 걸릴 뿐인 트랜잭션을 abort 시키는 경우가 있음.
    • 단점일 수도 있고 단점이 아닐 수도 있다.
  • 일찍 발생한 데드락을 타임아웃 시간이 되기 전까지는 발견하지 못하는 문제가 있다.

교착 상태를 해결하는 가장 간단한 방법은 타임아웃을 설정해 오랫동안 끝나지 않는 트랜잭션은 교착 상태가 발생한 것으로 간주하고 중단하는 것이다. 보수적 2PL의 경우 시작 전에 모든 잠금을 획득하지 못한 트랜잭션은 중단된다. 하지만 이와 같은 방식은 시스템의 동시성을 크게 저하시키기 때문에 대부분의 데이터베이스는 트랜잭션 매니저를 통해 교착 상태를 감지 및 방지(예방)한다.

교착 상태는 일반적으로 동시 수행 중인 트랜잭션 간의 대기 상태를 그래프로 표현하는 대기 그래프wait-for-graph를 사용해 감지한다. 4

그래프 기반 탐지

  • 주기적으로 데드락에 빠진 대기 상황이 있는지 체크한다.
  • 대기 상황 그래프 모델(waits-for graph)을 통해 체크하는 방식.
  • 주기적으로 데드락을 탐지하므로, 타임아웃 방식처럼 데드락이 발생하자마자 탐지하지 못하는 문제가 있다.
  • 그러나 타임아웃과는 다르게, 그래프 기반 탐지가 찾아내는 데드락은 실제로도 데드락이다.

분산 데드락의 탐지

  • 분산 데드락 탐지에 가장 많이 사용되는 방법은 타임아웃 방식이다.
    • 구현이 간단하다.
    • 서로 이질적인 시스템 사이에서도 사용할 수 있다.
    • 통신의 영향을 적게 받는다.

희생자 선택

데드락을 탐지하게 되면, 사이클 내 트랜잭션 중 하나를 희생자(victim) 삼아 abort 처리를 해야 한다.

데드락 탐지기의 희생자 선택 기준은 다양하다.

  • 데드락 사이클을 폐쇄하였던 사이클: 식별하기 가장 쉬운 방법. 데드락을 유발한 트랜잭션이라는 의미에서 공평하다.
  • 잠금의 수가 최소인 사이클: 잠금의 수는 트랜잭션이 얼마나 많은 작업을 했는지에 대한 척도이다. 가장 잠금을 작게 실행한 트랜잭션을 선택한다.
  • 로그 레코드를 최소로 생성한 사이클: 트랜잭션은 수행하는 각 업데이트를 위한 로그 레코드를 생성하므로, 이 트랜잭션은 비용 손실이 가장 적다.
  • 쓰기 잠금의 수가 가장 적은 사이클: 이것은 취소 비용손실이 가장 적은 방법이다.5
  • 데드락 탐지기 외에도 애플리케이션이 희생자를 선택하는 방법도 있다.
  • 희생자를 선택할 때 데드락 때문에 트랜잭션이 계속 재시작되어 완료를 하지 못하는 순환 재시작(cycle restart)이 발생하지 않도록 주의할 필요가 있다.
    • 순환 재시작을 방지하는 방법 하나는 가장 최신의 트랜잭션을 희생자로 선택하는 것이다.

잠금 경합의 완화

차단을 최소화하려면 트랜잭션이 잠금을 유지하는 시간을 줄여야 한다.

  • 트랜잭션에서 실행하는 작업의 수를 줄인다.
  • 트랜잭션을 둘 이상의 더 짧은 트랜잭션으로 분할한다.

두 번째 방법을 쓰면 잠금 유지 시간은 단축되지만 트랜잭션의 원자성을 보장할 수 없다는 문제가 생긴다.

따라서 복구에 대한 대책을 충분히 마련해야 한다.

인용: 교착 상태의 원인과 방지 방법

다음은 "한 권으로 읽는 컴퓨터 구조와 프로그래밍"에 삽입된, 책의 번역자인 오현석님이 작성한 글이다.

교착 상태의 원인과 방지 방법 - 옮긴이 작성

교착 상태가 발생할 수 있는 상황은 공유 자원과 이 자원을 함께 사용하는 프로세스가(물론 프로세스가 아니라 스레드 등일 수도 있다) 여럿 있는데 다음 네 가지 조건을 동시에 만족하는 경우에만 발생한다.

  1. 상호 배제(mutual exclusion): 공유 자원을 함께 쓸 수 없어서 어느 한 프로세스가 독점적으로 사용해야만 한다.
  2. 점유 대기(hold and wait): 프로세스들은 어느 자원을 점유한 상태에서 다른 자원을 요청한다.
  3. 비선점(no preemption): 프로세스가 할당받은 자원을 강제로 빼앗을 수 없다.
  4. 순환 대기(circular wait): 각 프로세스가 서로 순환적으로 다른 프로세스가 갖고 있는 자원을 요구한다

이 네 가지 중 어느 하나라도 없으면 교착 상태가 발생하지 않는다. 따라서 다음과 같은 방법으로 이를 해소 할 수 있다.

  1. 자원을 상호 배제하지 않고 언제든 공유할 수 있는 자원으로 만든다.
  2. 어느 자원을 점유한 다음에 다른 자원을 요구하지 않고 한꺼번에 자원을 요구한다.
  3. 선점형으로 바꾼다.
  4. 자원마다 우선순위를 부여해서 모든 프로세스가 다 서로 정해진 순서대로만 자원을 요구한다.

교착 상태를 해결하기 위해 코드를 잘 작성한다는 말은 이 네 가지 해법 중 하나를 적용한다는 말이다. 상황에 따라 네 가지 해법 중 어떤 방법을 택할지 잘 선택해야 한다.

– 한 권으로 읽는 컴퓨터 구조와 프로그래밍. 12장. 475쪽.

순환 대기를 순서 정렬로 해결하기

다음은 "운영체제 아주 쉬운 세 가지 이야기"를 인용한 것이다.

교착 상태의 예방

순환 대기(Circular Wait)

가장 실용적인 교착 상태 예방 기법은 (그리고 자주 사용되는 방법이기도 함) 순환 대기가 절대 발생하지 않도록 락에 관련된 코드를 작성하는 것이다. 간단한 방법은 락 획득을 하는 전체 순서(total ordering)를 정하는 것이다. 예를 들어 L1 L2라는 두 개의 락만이 시스템에 존재하면 L1을 무조건 L2 전에 획득하도록 하면 교착 상태를 피할 수 있다. 이 순서를 따르면 순환 대기는 발생하지 않고 따라서 교착 상태도 발생하지 않는다.

– 운영체제 아주 쉬운 세 가지 이야기. 32.3장. 426쪽.

다음은 "UNIX 고급 프로그래밍"을 인용한 것이다.

하나의 스레드가 같은 [[/jargon/mutex]]{뮤텍스}를 두 번 잠그려 하면 교착(deadlock) 상태에 빠짐은 명백하다. 그런데 그보다 덜 명백한 방식으로도 교착이 발생할 수 있다. 예를 들어 프로그램이 여러 개의 뮤텍스를 사용한다고 하자. 한 스레드가 뮤텍스 1을 획득한 상태에서 뮤텍스 2를 잠그려 하고, 그와 동시에 다른 어떤 스레드가 뮤텍스 2를 획득한 상태에서 뮤텍스 1을 잠그려고 하면 어떻게 될까? 그러면 두 스레드 모두 실행이 영원히 차단된다. 각 스레드는 상대방 스레드가 가진 자원을 원하며, 원하는 자원을 얻기 전까지는 자신이 가진 자원을 내놓지 않는다. 따라서 교착이 발생한다.

뮤텍스가 잠기는 순서를 세심하게 제어하면 교착을 피할 수 있다. 예를 들어 뮤텍스 A와 B를 동시에 잠근다고 하자. 만일 모든 스레드가 뮤텍스 A를 먼저 잠근 후에 B를 잠근다면 두 뮤텍스에 한해서는 교착이 발생하지 않는다(물론 다른 자원에 대해서는 여전히 교착이 발생할 수 있다). 마찬가지로, 모든 스레드가 항상 뮤텍스 B를 먼저 잠근 후에 A를 잠근다면 교착은 발생하지 않는다. 교착의 가능성은 한 스레드가 뮤텍스들을 다른 스레드와는 반대의 순서로 잠그려 할 때에만 생긴다.

그런데 응용 프로그램의 구조에 따라서는 그러한 잠금 순서를 제어하기 어려운 경우가 있다. 자물쇠와 자료구조가 너무 많고 다양해서 관련 함수들을 간단한 계통구조로 조직화하는 것이 현실적으로 불가능하다면 다른 접근방식을 시도할 수밖에 없다. 그런 경우, 만일 자물쇠들을 해제한 후 나중에 다시 시도하는 것이 가능하다면 pthread_mutex_trylock 인터페이스를 활용함으로써 교착을 피할 수 있다. 자물쇠들을 획득한 상태에서 pthread_mutex_trylock의 호출이 성공한다면 계속 진행해도 된다. 만일 자물쇠를 획득할 수 없다면, 이미 획득한 자물쇠들을 해제하고, 정리 작업을 수행하고, 나중에 다시 시도한다.

– UNIX 고급 프로그래밍. 11.6.2장. 494쪽.

경험

데드락 문제를 정렬로 해결

다음은 내가 마켓컬리에 재직중일 때 컬리 기술 블로그에 작성한 글이다.

신규 서비스 배포 전에 실험과 개선을 반복한 이야기

이 문서에서는 데드락 문제를 비즈니스 로직에 정렬 코드를 추가해 간단하게 해결한 사례를 소개한다.

내용을 간단히 요약하자면 다음과 같다.

  • 고객은 장바구니 여러 상품을 담고, 구매를 진행하게 된다. 
      장바구니 => (A 상품 3개, B 상품 1개, C 상품 2개, ...)
  • 그렇다면 각 상품 재고 수량의 차감은 다음과 같이 하나의 트랜잭션 안에서 시퀀셜하게 발생한다. 
      Tx1 => (A 상품 3 차감, B 상품 1 차감, C 상품 2 차감, ...)

이렇게 순서대로 작업하다가 중간에 문제가 발생하면 트랜잭션을 롤백하여, 작업을 취소하고 응답하게 개발해 두었다.

그런데 이 과정은 동시에 여러 고객이 구매를 진행하게 될 때 논리적으로 데드락이 발생할 가능성이 있다.

문제가 발생하는 상황을 단순하게 모델링하면 다음과 같다.

Tx1 => (A 상품 차감, B 상품 차감)
Tx2 => (B 상품 차감, A 상품 차감)
시퀀스 Tx1 Tx2
1 A 잠금  
2   B 잠금
3 B가 잠금에서 해제되길 기다림  
4   A가 잠금에서 해제되길 기다림
5 B가 잠금에서 해제되길 기다림  
6   A가 잠금에서 해제되길 기다림
… …(무한반복) …(무한반복)

Tx1 은 A를 잠금했고, Tx2는 B를 잠금하여 서로의 잠금이 풀리기를 기다리고 있으므로 교착 상태가 발생하게 된다.

image 6

나는 이 문제에 대한 해결 방법으로 각 트랜잭션의 차감 대상 상품을 정렬하는 방법을 제안했다.

작업 대상을 정렬하면 이론적으로 (A, B) (B, A)와 같은 순환 대기를 제거하고, 잠금 대상에 순서를 붙이므로 교착 상태를 방지할 수 있으리라 추측했기 때문이다.

Tx1 => (A 상품 차감, B 상품 차감)
Tx2 => (A 상품 차감, B 상품 차감)
시퀀스 Tx1 Tx2
1 A 잠금  
2   A가 잠금에서 해제되기를 기다림
3 B 잠금  
4   A가 잠금에서 해제되기를 기다림
5 작업 완료 A, B 잠금 해제  
6   A 잠금
7   B 잠금
8   작업 완료 A, B 잠금 해제

다음은 이 방법으로 실제로 문제를 해결한 코드이다. 이후 이 비즈니스 로직에서 데드락은 발생하지 않았다.

image

자세한 내용은 마켓컬리 기술 블로그: 신규 서비스 배포 전에 실험과 개선을 반복한 이야기 참고.

참고문헌

  • UNIX 고급 프로그래밍 [제3판] / 리처드 스티븐스, 스티븐 레이고 공저 / 류광 역 / 퍼스트북 / 인쇄일: 2014년 08월 28일 / 원제: Advanced Programming in the UNIX Environment
  • 데이터베이스 인터널스 / 알렉스 페트로프 저/이우현 역/이태휘 감수 / 에이콘출판사 / 2021년 01월 29일 / 원제: Database Internals: A Deep Dive into How Distributed Data Systems Work
  • 운영체제 아주 쉬운 세 가지 이야기 [제2판] / Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-dusseau 공저 / 원유집, 박민규, 이성진 공역 / 홍릉 / 제2판 발행: 2020년 09월 10일 / 원제: Operating Systems: Three Easy Pieces
  • 트랜잭션 처리의 원리 / 필립 A. 번스타인, 에릭 뉴코머 공저 / 한창래 역 / KICC(한국정보통신) / 1판 1쇄 2011년 12월 19일
  • 한 권으로 읽는 컴퓨터 구조와 프로그래밍 / 조너선 스타인하트 저/오현석 역 / 책만 / 2021년 04월 08일 초판 1쇄 / 원제: The Secret Life of Programs: Understand Computers – Craft Better Code

주석

  1. 트랜잭션 처리의 원리. 6 잠금. 185쪽. ↩

  2. 트랜잭션 처리의 원리. 6 잠금. 188쪽. ↩

  3. 트랜잭션 처리의 원리. 6.3 데드락. 197쪽. ↩

  4. 데이터베이스 인터널스. 5장. 144쪽. ↩

  5. 트랜잭션 처리의 원리. 6.3 데드락. 200쪽. ↩

  6. 트랜잭션 처리의 원리. 6.3장. ↩