(RDB) 트랜젝션이 동시에 실행될 때 isolation을 보장하는 기본 이론 (feat: schedule, serializability)

개요

현대의 데이터베이스 시스템은 다수의 사용자가 동시에 다양한 트랜잭션을 실행함에 따라 높은 성능과 일관성을 유지하는 것이 필수적이다. 이러한 환경에서 트랜잭션의 동시 실행은 시스템 자원의 효율적 활용을 가능하게 하지만, 동시에 데이터 일관성 및 무결성을 위협할 수 있는 여러 문제를 야기할 수 있다. 특히, 트랜잭션 간의 상호 간섭으로 인해 발생하는 일관성 오류는 데이터베이스 관리 시스템(DBMS)의 신뢰성을 저해할 수 있다.

이러한 문제를 해결하기 위해 트랜잭션의 격리성(Isolation)을 보장하는 것이 중요하며, 이를 위해 스케줄(Schedule)과 직렬 가능성(Serializability)이라는 기본 이론이 핵심적인 역할을 한다.

 

내용

Schedule이란?

 스케줄이란 여러 transactional들이 동시에 실행될 때 각 transactional에 속한 operation들의 실행 순서를 뜻한다.

[사진 1] DB schedule 예시

 

 여기에서 1, 2번 스케줄은 각각의 트랜젝션들의 실행 순서가 겹치지 않는데, 이런 경우 Serial Schedule이라고 하고, 3, 4번과 같이 겹치는 경우 NonSerial Schedule이라고 한다.

 

Serial Schedule의 성능

 Serial Schedule은 트랜잭션들이 순차적으로 하나씩 실행되는 스케줄을 의미한다. 이 방식에서는 한 번에 하나의 Operation만을 처리하므로, 특정 I/O Operation을 수행할 때 CPU는 유휴 상태에 있게 된다. 결과적으로, 시스템의 전반적인 성능은 낮아질 수 있다. 특히, 다수의 트랜잭션이 빈번하게 발생하는 환경에서는 처리 속도가 느려져 사용자 응답 시간이 증가할 수 있다.

 

그러나 Serial Schedule의 가장 큰 장점은 데이터 일관성 보장에 있다. 트랜잭션들이 서로 간섭하지 않고 독립적으로 실행되기 때문에, Lost Update, Dirty Read, Non-repeatable Read와 같은 이상 현상이 발생하지 않는다. 이러한 특성 덕분에 Serial Schedule은 데이터 무결성을 최우선으로 하는 시스템에서 신뢰할 수 있는 방법으로 사용된다.

 

NonSerial Schedule의 성능

Non-Serial Schedule은 여러 트랜잭션이 동시에 실행되는 스케줄을 의미한다. 이 방식에서는 트랜잭션들이 겹쳐서 실행되기 때문에, 시스템의 동시성(concurrency)이 높아져 동일한 시간 동안 더 많은 트랜잭션을 처리할 수 있다. 결과적으로, 시스템의 처리량(througput)이 향상되며, 사용자에게 더 빠른 응답 시간을 제공할 수 있다.

 

병렬로 처리하면서 이상현상이 나오지 않는 방법

 병렬로 트랜잭션을 처리하면서도 이상 현상이 발생하지 않도록 하기 위해서는, 기본적인 아이디어는 Serial Schedule과 동일한 결과를 도출하는 Non-Serial Schedule을 실행하는 데 있다. 이를 위해서는 '스케줄이 동일하다'는 의미를 명확히 정의할 필요가 있다. 이 개념을 이해하기 위해서는 Conflict Serializability(충돌 직렬 가능성) 이론이 핵심적인 역할을 한다.

 

Conflict of Two Operations

두 연산이 충돌(conflict) 한다는 것은 다음 세 가지 조건을 모두 만족할 때를 말한다

1. 서로 다른 트랜잭션 소속
   두 연산이 서로 다른 트랜잭션에 속해 있어야 한다.
2. 같은 데이터에 접근
   두 연산이 동일한 데이터 항목을 접근해야 한다. 이 접근은 읽기(Read) 또는 쓰기(Write)일 수 있다.
3. 최소 하나는 쓰기 연산
   두 연산 중 최소 하나가 쓰기 연산이어야 한다. 즉, 두 연산 모두 읽기 연산인 경우에는 충돌하지 않는다.

위 세 조건을 모두 만족하면 두 연산은 충돌한다고 할 수 있으며, 이러한 충돌은 트랜잭션 간의 상호 간섭을 초래할 수 있다. 충돌이 발생하는 경우, 트랜잭션의 실행 순서에 따라 데이터의 일관성이 깨질 수 있으므로 이를 적절히 관리하는 것이 중요하다.

 

Conflict Serializability의 정의

Conflict Serializability는 Non-Serial Schedule이 어떤 Serial Schedule과 충돌 없이 동일한 결과를 도출할 수 있는지를 평가하는 개념이다. 즉, 동시 실행되는 트랜잭션들이 충돌 없이 적절히 조정되어, 순차적으로 실행된 것과 동일한 결과를 얻을 수 있을 때 그 스케줄은 충돌 직렬 가능하다고 한다

 

이를 위해 다음과 같은 과정을 거친다

1. 충돌 그래프(Precedence Graph) 작성
   각 트랜잭션을 그래프의 노드로 간주하고, 충돌 관계에 있는 연산들 간의 순서를 간선으로 표현한다. 만약 트랜잭션 T₁의 연산이 트랜잭션 T₂의 연산보다 먼저 실행되어야 한다면, T₁에서 T₂로 향하는 간선을 추가한다.
2. 사이클 존재 여부 확인
   충돌 그래프에 사이클이 존재하지 않으면, 해당 스케줄은 충돌 직렬 가능하다. 사이클이 존재할 경우, 스케줄은 직렬로 재배열할 수 없으므로 충돌 직렬 가능하지 않다.
3. 직렬 스케줄과의 동일성 검증
   충돌 그래프가 사이클을 포함하지 않는 경우, 그래프의 위상 정렬을 통해 트랜잭션의 실행 순서를 결정할 수 있으며, 이 순서대로 트랜잭션을 직렬로 실행했을 때의 결과와 동일함을 보장한다.

 

참고 자료