개념

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

개념은 다음과 같다.1

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

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

2단계 잠금 (two-phase locking)

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

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

  1. Expanding 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 시키는 경우가 있음.
    • 단점일 수도 있고 단점이 아닐 수도 있다.
  • 일찍 발생한 데드락을 타임아웃 시간이 되기 전까지는 발견하지 못하는 문제가 있다.

그래프 기반 탐지

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

분산 데드락의 탐지

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

희생자 선택

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

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

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

잠금 경합의 완화

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

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

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

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

참고문헌

  • 트랜잭션 처리의 원리 / 필립 A. 번스타인, 에릭 뉴코머 공저 / 한창래 역 / KICC(한국정보통신) / 1판 1쇄 2011년 12월 19일

주석

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

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

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

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