[데이터베이스] 병행 제어

📂 트랜잭션(Transaction)

트랜잭션(Transaction)은 데이터베이스에서 일어나는 일련의 연산들의 집합으로서, 하나의 논리적 기능을 수행하기 위한 작업의 단위이다. 이는 데이터베이스의 상태를 하나의 일관된 상태에서 다른 일관된 상태로 변환시킨다. 

이를 위해 트랜잭션에 포함된 모든 연산은 완전히 처리되거나 아니면 하나도 처리되지 않아야 하는 "All-or-Nothing" 방식으로 처리되어야 한다. 

트랜잭션을 표현할 때는 Begin_Trans와 End_Trans를 하나로 묶은 형태로 표시하고, 하나의 트랜잭션은 Begin_Trans와 End_Trans 안에서 실행되는 모든 명령문들을 말한다. 

📄 트랜잭션의 특성

데이터베이스의 회복과 병행 제어는 대부분 트랜잭션을 기반으로 수행된다. 트랜잭션은 아래의 4가지 특성을 만족해야 한다. 이를 트랜잭션의 ACID 성질이라고도 한다. 

1. 원자성(Atomicity) : 트랜잭션은 All-or-Nothing 실행만 있지 부분적으로 실행되지 않는다. 즉, 한 트랜잭션의 모든 연산이 데이터베이스에 완전히 반영되거나, 전혀 반영되지 않아야 한다. 
2. 일관성(Consistency) : 트랜잭션이 실행되고 나면 데이터베이스가 하나의 일관된 상태에서 다른 일관된 상태로 바뀐다. 예를 들어, A 계좌와 B 계좌의 잔액을 합한 결과가 트랜잭션이 끝난 후에도 변하지 않아야 한다. 
3. 격리성(Isolation) : 다수의 트랜잭션들이 동시에 수행되고 있는 경우, 실행 중인 트랜잭션이 완전히 완료될 때까지 다른 트랜잭션들이 접근하지 못하도록 막아야 한다. 즉, 다수의 트랜잭션들이 동시에 실행되더라도 그 결과는 어떤 순서에 따라 트랜잭션들을 하나씩 차례대로 실행한 결과와 같아야 한다. 
4. 영속성(Durability) : 트랜잭션이 모든 작업을 성공적으로 실행 완료해 데이터베이스에 내용을 반영하였다면 그 결과는 영구적이어야 한다. 시스템이 고장 난 경우에도 그 실행 결과 값이 손실되어서는 안 된다. 

📄 트랜잭션의 연산

트랜잭션의 원자성을 보장하는 연산으로 Commit(완료)과 Rollback(복귀) 연산이 있다.

트랜잭션이 Commit 연산을 수행하면 그 트랜잭션이 성공적으로 실행되었다는 것을 선언하는 것이다. 따라서 데이터베이스 상태는 일관성 있게 변환된 것이고, 갱신된 데이터 항목들의 값은 데이터베이스에 영구적으로 보관될 수 있다. 

반면 트랜잭션이 Rollback 연산을 수행한다는 것은 트랜잭션의 실행이 실패했다는 것을 선언하는 것으로, 데이터베이스 상태는 모순되게 되어 부정확한 상태가 되었다는 것이다. 따라서 트랜잭션이 수행한 모든 연산을 취소하여 그 결과를 원상 복귀시켜야 한다. 

📄 트랜잭션의 상태

데이터베이스를 접근하여 갱신 연산을 수행하는 트랜잭션은 다음과 같은 5가지의 상태 중 어느 하나에 속하게 된다.

1. 활동(Active) : 트랜잭션이 실행을 시작하였거나 현재 실행 중인 상태를 의미한다. 다음 상태는 [부분완료]나 [실패]이다. 
2. 부분 완료(Partially committed) : 트랜잭션이 마지막 명령문을 실행시킨 직후의 상태를 의미한다. 다음 상태는 [완료]나 [실패]이다. 
3. 실패(Failed) : 트랜잭션 실행 중에 장애나 오류가 발생해 정상적인 실행을 더 이상 계속할 수 없는 상태를 말한다. 다음 상태는 [철회]하는 상태이다. 
4. 철회(Aborted) : 트랜잭션이 실행을 실패하여 Rollback 연산을 수행한 상태이다. 이 상태가 되면 시스템은 트랜잭션을 재시작하거나 강제 종료시켜야 한다.  
5. 완료(Committed) : 트랜잭션이 실행을 성공적으로 완료하여 commit 연산을 수행한 상태를 의미한다. 변경된 내용이 데이터베이스 내에 안전하게 저장되어 영속성을 보장받는다. 

---

📂 병행 제어

DBMS의 장점 중 하나는 데이터의 공유와 병행 수행을 제어할 수 있다는 것이다. 

복수 사용자 DBMS에서는 몇 개의 트랜잭션들을 동시에 수행시켜야 하는 복잡한 병행 수행(Concurrency)을 지원한다. 컴퓨터 시스템 내에서 프로그램 $P_1$과 $P_2$가 인터리브(Interleaved) 형태로 병행 실행되는 예는 아래 그림과 같다. 

병행 수행이 적절히 제어되지 않을 때는 트랜잭션들 간의 간섭으로 예기치 못한 결과가 생성될 수 있다. 이러한 문제점들은 다음과 같다. 

🏷 갱신 분실(Lost update)

위의 그림에서 트랜잭션 $T_1$이 레코드 x를 읽고 x의 값을 100만큼 증가시킨 뒤에 트랜잭션 $T_2$가 다시 레코드 x를 읽고 x의 값에 200을 감소시켰다. 그 뒤에 트랜잭션 $T_1$은 자신이 변경시킨 x값을 저장하고 바로 뒤에 트랜잭션 $T_2$도 변경시킨 x값을 저장했다. 그 결과 트랜잭션 $T_1$의 갱신 연산은 트랜잭션 $T_2$가 겹쳐 저장하는 바람에 데이터베이스에 실제로 반영되지 못하고 분실되고 말았다. 즉, $T_2$만 갱신한 결과가 되고 $T_1$의 갱신 연산은 무효가 되었다. 

🏷 모순성(Inconsistency)

위 그림에서 x, y의 초기 값을 100이라고 가정하자. 독립된 사용자인 $T_1$, $T_2$는 각자 수행 결과를 x=200과 y=200으로 생각할 것이다. 하지만 실제로는 x에 100을 더한 후 $T_2$가 이 값을 가로 채 2를 곱한 후 x=400이 되고, y 값은 2를 곱한 후 y=200을 저장했다. 이 결과는 사용자가 원하는 결과가 아닐뿐더러 데이터베이스가 일관성이 없는 모순된 상태로 남게 된다. 

🏷 연쇄 복귀(Cascading Rollback)

위 그림에서는 트랜잭션 $T_1$이 x를 읽고 100을 더한 후 이를 저장했다. 그 뒤에 바로 트랜잭션 $T_2$가 갱신된 x 값을 읽고 갱신을 완료하였다. 바로 이때 트랜잭션 $T_1$이 레코드 y를 읽고 갱신하려다 문제가 발생해 갱신을 취소하고 원래 상태로 복귀해야 하는 상황이 발생되었다. 이렇게 되면 Rollback 연산이 수행된 $T_1$이 수행한 결과(x=200)를 읽은 트랜잭션 $T_2$도 당연히 복귀하여야 하지만 이미 트랜잭션 $T_2$는 작업을 완료한 상태로 시스템을 떠난 뒤이기 때문에 사실상 복귀하기 어려운 상황이 발생된 것이다. 

---

📄 트랜잭션 스케줄(Transaction Schedule)

트랜잭션 스케줄이란, 데이터베이스 트랜잭션을 구성하는 연산들의 실행 순서를 의미하는 것이다. 인터리브 형태로 여러 트랜잭션들이 병행 수행되는 환경에서 트랜잭션에 포함된 각각의 연산들에 대해 실행 순서를 지정하는 것은 매우 중요한 일이다. 

직렬 스케줄

위의 그림과 같이 트랜잭션별로 모두 순차적으로 실행되는 스케줄을 직렬 스케줄(Serial schedule)이라 한다. 이 경우 어떤 경우에라도 데이터베이스에 대한 결과는 항상 정확하다. 하지만, 값비싼 CPU의 낭비로 이어질 수 있다는 단점이 있다. 

🏷 직렬 가능 스케줄(Serializable Schedule)

비직렬 스케줄(non-serial schedule)은 트랜잭션들이 병행 수행하는 스케줄을 의미하며, 인터리빙 방식으로 처리된다. 

이는 CPU 활용도는 높일 수 있지만, 그 결과 값이 항상 정확성을 만족한다고는 할 수 없다. 

 

하지만, 비직렬 스케줄로 실행되지만 정확한 결과를 생성하는 경우가 있다.

위의 경우 트랜잭션 $T_1$은 x를 읽고 100을 더한 후 x를 저장한다. 다음 트랜잭션 $T_2$에서 이 저장된 x를 읽고 x 값을 2배 증가시킨다. 그다음 y 값은 $T_1$에서 100을 더한 후 $T_2$에서 이 값을 2배 증가시킨다. 

이와 같이 만약 두 개의 트랜잭션이 같은 데이터 항목에 접근하지 않는다면 상호 간섭이 발생되지 않으며 연산의 순서도 중요하지 않다. 따라서 비록 비직렬로 수행되지만 직렬 스케줄로 수행되는 것과 같은 결과를 만드는 것을 직렬 가능 스케줄(Serializable schedule)이라 한다. 

하지만, 현실적으로 직렬 가능 스케줄을 검사하는 것은 매우 어려운 일이다. 

📄 병행 제어(Concurrency Control) 기법

트랜잭션들을 실행시킨 뒤에 스케줄 자체에 대한 직렬 가능성 검사를 하지 않고도 직렬 가능성이 보장되는 방법이 있는데, 이 중에 로킹과 타임스탬프 방법이 있다. 

로킹(Locking) 기법은 여러 트랜잭션들이 동일한 항목에 대해 임의적인 병행 접근을 하지 못하게 하는 것이다.

타임스탬프(Time-stamp) 기법은 타임스탬프 순서에 따라 실행되게 하는 것이다. 타임스탬프는 시스템에서 각 트랜잭션을 실행할 때 부여하는 고유 식별자이다. 

 

로킹에 대해서만 자세히 알아보자. 

---

📂 로킹 기법

📄 Lock의 개념

로킹(Locking) 기법은 병행 수행 시 공유하고자 하는 데이터 항목을 제어하기 위해 두 개의 연산 lock, unlock을 사용한다. 다음과 같은 로킹 규약(locking protocol)을 지킨다면 두 개의 트랜잭션이 같은 데이터 항목을 동시에 접근하는 경우는 없음을 보장하는 것이다. 

1. 트랜잭션 T가 read(x)나 write(x) 연산을 수행하기 위해서는 먼저 lock(x)를 실행해야 한다. 
2. 트랜잭션 T가 실행한 lock(x)에 대해 해당 트랜잭션이 모든 실행을 종료하기 전에 unlock(x)를 실행해야 한다. 
3. 트랜잭션 T는 다른 트랜잭션에 의해 이미 lock이 걸려 있으면 다시 lock(x)를 실행하지 못한다. 
4. 트랜잭션 T가 x에 대해 lock을 자신이 걸지 않았다면 unlock(x)를 실행하지 못한다. 

하지만 이 로킹 규약은 너무 제한적일 수 있다. 그 이유는 어느 때고 각 데이터 항목에 대해 하나의 트랜잭션만 lock을 걸 수 있기 때문이다. 만일 트랜잭션이 단지 읽기(read) 목적으로만 특정 데이터 항목에 접근하려 한다면, 여러 트랜잭션들이 동시에 데이터 항목을 병행적으로 접근 수행해도 문제가 없을 것이다. 

즉, 데이터 항목 접근이 읽기만을 위한 목적이라면 트랜잭션들에 대해 병행 접근을 허용할 수 있는데, lock 연산은 다음과 같이 나눌 수 있다.

• Lock-S : 공용 로크(shared-lock)
  • 트랜잭션 T가 x에 대해 lock-S를 설정할 경우, 트랜잭션 T는 이 항목에 대해 read 할 수는 있지만 write 할 수는 없다. 이때 이 x에 대해서 다른 트랜잭션은 공용 로크를 동시에 걸 수 있다. 
• Lock-X : 전용 로크(exclusive-lock)
  • 트랜잭션 T가 데이터 항목 x에 대해 lock-X를 설정하면, 트랜잭션 T는 이 항목에 대해 read, write 모두 할 수 있다. 이때 다른 트랜잭션은 이 x에 대해 어떤 lock도 걸 수 없다. 

이 두 가지 lock 연산에 대해 양립성(Compatibility)을 표로 살펴보면 다음과 같다. 

하지만, 트랜잭션들이 로킹 규약을 따랐다는 것만으로 병행 수행의 직렬 가능성이 보장되는 것은 아니다. 아래는 트랜잭션들이 모두 로킹 규약을 따랐음에도 모순성이 발생한 예를 보여주고 있다. 

위 그림에서 x, y를 각각 100, 200이라 하자. $T_1$→$T_2$ 순서로 실행하는 직렬 스케줄의 결과는 x=400, y=600이 된다. $T_2$→$T_1$ 순서로 실행되는 스케줄의 결과는 x=300, y=500이 된다. 하지만, 위의 스케줄에 따라 병행 수행했을 때의 결과는 x=400, y=500과 같이 이상한 결과가 나온다. 다시 말해 직렬 가능성을 보장하지 못한다. 

이런 모순된 결과가 나오는 이유는 트랜잭션 $T_1$이 x에 대해 너무 일찍 unlock(x)를 실행시켜, 아직 작업이 끝나기도 전에 트랜잭션 $T_2$가 일관성이 없는 데이터에 접근하였기 때문이다. 

 

따라서 직렬 가능성을 보장하기 위해서는 트랜잭션이 lock과 unlock 연산을 수행하는 시점에 추가 약속이 필요하다. 이러한 문제점을 해결하기 위해 2단계 로킹 규약을 적용하게 된 것이다.

📄 2단계 로킹 규약

직렬 가능성을 보장할 수 있는 규약으로 알려진 기법이 2단계 로킹 규약(2PLP: Two Phase Locking Protocol)이다. 이 규약에서 모든 트랜잭션들은 다음과 같이 2단계로 구분하여 수행할 것을 요구하고 있다. 

1. 확장 단계(growing phase) : 트랜잭션이 lock 연산만 수행할 수 있고 unlock 연산은 수행할 수 없는 단계
2. 축소 단계(shrinking phase) : 트랜잭션이 unlock 연산만 수행할 수 있고 lock 연산은 수행할 수 없는 단계

위의 그림은 2PLP를 준수하고 있는 직렬 가능 스케줄의 예를 보여준다. 두 트랜잭션 모두 처음에는 lock을 수행하는 확장 단계로 들어가다가 일단 unlock을 수행하면 그 시점부터는 더 이상 새로운 lock 연산을 수행할 수 없고 unlock 연산만 수행 가능하다. 

스케줄 내의 모든 트랜잭션들이 2단계 로킹 규약(2PLP)을 준수한다면 그 스케줄은 직렬 가능하다.
즉, 정확한 결과를 생성한다. 

📄 교착 상태(Deadlock)

2PLP는 간결한 병행 제어 기법을 제공해 주고 있지만 문제점으로는 교착 상태가 발생될 수 있다. 

교착 상태(Deadlock)란, 둘 이상의 트랜잭션이 서로 상대가 가지고 있는 데이터 항목의 로크가 해제되기만을 기다림으로 인해 트랜잭션의 실행이 중단되고 무한정 기다리는 상태를 말한다. 

위의 그림에서 트랜잭션 $T_1$과 $T_2$는 각각 x, y에 대해 lock을 유지하고 있으며, $T_1$은 $T_2$가 lock 하고 있는 y에 대해 unlock 되기를 기다리고 있는 상태이다. $T_2$는 $T_1$이 lock하고 있는 x에 대해 unlock 되기를 기다리고 있는 상태이다. 이와 같이 두 트랜잭션이 아무 일도 하지 못한 채 서로 unlock 되기만을 무한정 기다리는 상태를 교착 상태라고 한다. 

 

이러한 교착 상태가 발생하는 원인은 상호 배제, 대기, 비선점, 순환 대기의 4가지 조건이 동시에 성립될 때 발생된다. 즉, 이들 중 한 가지라도 만족하지 않으면 발생하지 않는다.

1. 상호 배제(Mutual exclusive) : 트랜잭션들이 자원을 배타적으로 점유해 다른 트랜잭션들이 자원을 사용하지 못함
2. 대기(Wait for) : 트랜잭션이 어떤 자원을 할당받아 점유하고 있으면서 다른 자원을 요구함
3. 비선점(No preemption) : 트랜잭션에 할당된 자원은 사용이 종료될 때까지 강제로 획득할 수 없으며 점유하고 있는 트랜잭션 자신만이 해제 가능
4. 순환 대기(Circle wait) : 트랜잭션 간 자원 요구가 하나의 원형 모양일 경우

 

교착 상태의 해결 방법으로는 회피, 예방, 탐지 방법이 있을 수 있다. 

🏷 회피(Avoidance)

자원을 할당할 때마다 deadlock이 일어나지 않도록 실시간 알고리즘을 사용해 감시하는 방법이다. 현실성은 그다지 없어 보인다...

이를 위한 한 가지 방법으로 각 트랜잭션의 타임스탬프를 이용하는 방법이 있다. 이 타임스탬프는 기다려야 할 것인지 복귀(Rollback) 해야 할 것인지를 결정하는 데 사용된다. 

이 방법에는 다음과 같은 두 가지 기법이 있다. 

1. Wait-die 기법
   트랜잭션 $T_i$가 이미 트랜잭션 $T_j$가 lock 한 데이터 항목을 요구할 때, 만일 $T_i$의 타임스탬프가 $T_j$의 타임스탬프보다 작을 경우($T_i$가 고참인 경우) $T_i$를 기다리게(wait)하고, 그렇지 않으면($T_i$가 신참인 경우) $T_i$는 포기(die)했다가 나중에 같은 스탬프를 가지고 다시 시작한다. 즉, 이 기법은 다른 트랜잭션이 데이터를 점유하고 있을 때 기다리거나(wait) 포기(die)하는 방식이다. 
   위 그림의 경우, $T_1$은 이미 $T_2$가 lock한 데이터 y를 요구했다. 이때 $T_1$의 타임스탬프는 $T_2$의 타임스탬프보다 작으므로 $T_1$을 기다리게 한다. 
2. Wound-wait 기법
   $T_i$가 이미 $T_j$가 lock한 데이터를 요구할 때, 만일 $T_i$의 타임스탬프가 $T_j$의 타임스탬프보다 작을 경우 $T_i$는 데이터를 선점(Wound)한다. 그렇지 않으면 $T_i$을 기다리게(wait) 한다. 즉, 이 기법은 다른 트랜잭션이 데이터를 점유하고 있을 때 빼앗거나(wound) 기다리는(wait) 방식이다. 
   위 그림의 경우, $T_i$이 고참이므로 데이터를 선점(wound)한다. 

🏷 예방(Prevention)

트랜잭션을 실행시키기 전에 필요한 lock을 한꺼번에 모두 요청해 전부 부여받지 못하면 실행시키지 않는 방법이다. 하지만 이 방법은 데이터 요구에 대한 사전 지식을 필요로 하기 때문에 현실성이 없다. 또한, 데이터 항목이 한꺼번에 lock 되기 때문에 상당한 기간 동안 데이터가 실제로 사용되지 않을 수 있기 때문에 데이터 항목의 활용도가 매우 낮게 된다. 

🏷 탐지(Detection)

lock 상태를 조사해 일단 교착 상태가 탐지되면 트랜잭션 하나를 취소시켜 다시 스케줄을 실행시키는 것이다. Deadlock을 탐지하는 간단한 방법은 대기 그래프(Wait for graph)를 사용하는 것이다. 

즉, 현재 $T_2$가 lock 한 y를 $T_1$이 lock 하기 위해 기다리고 있으면 방향 간선 $T_1$→$T_2$로 표시한다. 이런 방식으로 구축된 대기 그래프에 사이클이 생기면 Deadlock으로 판단한다. 

Deadlock이 감지되면 트랜잭션 하나를 취소시켜 사이클을 제거해야 하는데, 취소시킬 트랜잭션은 작업이 가장 적게 수행된 트랜잭션이 선정되는 것이 효율적이다. 

 

결론적으로는 현재 Deadlock을 완전히 해결하는 방법은 아직 없고 임시적으로 탐지 방법을 적용해 해결하고 있는 상황이다. 

📄 로킹 단위

로킹 단위(Locking granularity)란 로킹의 대상이 되는 데이터 객체의 크기를 말한다. 이는 병행 제어의 데이터 단위가 된다. 

일반적으로 로킹 단위가 클수록 병행 제어 수준이 낮아지지만 병행 제어 기법은 간단해진다. 만약 극단적으로 로킹 단위가 DB 전체가 된다면 병행성은 전혀 없게 된다. 따라서 적절한 로킹 단위의 결정은 시스템 성능 향상을 위한 하나의 중요한 요소이다. 

 

만약 데이터 항목 단위로만 lock을 한다면 모든 항목들에 대해 lock 연산을 실행해야 되기 때문에 많은 로킹 연산이 필요하다. 이러한 비효율성을 해결하기 위해 여러 종류(레코드, 파일, 데이터베이스...)의 로킹 단위를 지원할 수 있는 다중 단위 로킹(Multiple granularity locking) 기법이 필요하다.