Transaction 개념
Transaction은 다양한 데이터 항목에 접근하고 업데이트할 수 있는 프로그램 실행 단위이다.
Transaction은 데이터베이스의 일관성을 유지하면서 안전하게 데이터를 처리하기 위한 메커니즘으로, 주로 두 가지 주요 문제를 다룬다: 하드웨어 고장이나 시스템 충돌과 같은 다양한 종류의 failure와 여러 transaction들의 concurrent execution이다.
Transaction의 기본 예시: 계좌 이체
Transaction의 개념을 이해하기 위해 계좌 이체 예시를 살펴보자. 계좌 A에서 계좌 B로 $50을 이체하는 transaction은 다음과 같은 단계로 구성된다:
- read(A) - 계좌 A의 잔액을 읽는다
- A := A - 50 - 계좌 A에서 $50을 차감한다
- write(A) - 수정된 A 값을 데이터베이스에 기록한다
- read(B) - 계좌 B의 잔액을 읽는다
- B := B + 50 - 계좌 B에 $50을 추가한다
- write(B) - 수정된 B 값을 데이터베이스에 기록한다
이 간단한 예시에서도 여러 가지 중요한 요구사항이 발생한다. 만약 transaction이 3단계 이후, 6단계 이전에 실패한다면 money가 "손실"되어 데이터베이스가 inconsistent state가 될 수 있다. 이러한 문제와 다른 여러 가지 이슈를 해결하기 위해 transaction은 ACID 원칙을 따라야 한다.
ACID 원칙
ACID는 데이터베이스 transaction이 안전하게 처리됨을 보장하기 위한 네 가지 핵심 속성을 나타낸다:
Atomicity (원자성)
Atomicity는 transaction의 모든 operation이 데이터베이스에 완전히 반영되거나 전혀 반영되지 않음을 보장한다. 이것은 "All or Nothing" 접근 방식이다.
위의 계좌 이체 예시에서, 만약 transaction이 중간에 실패하더라도 부분적으로 실행된 transaction의 updates가 데이터베이스에 반영되지 않도록 시스템이 보장해야 한다.
Consistency (일관성)
Consistency는 transaction이 실행된 후에도 데이터베이스가 일관된 상태를 유지함을 보장한다.
계좌 이체 예시에서, consistency 요구사항은 A와 B의 총합이 transaction 실행 전후에 동일하게 유지되어야 함을 의미한다.
예를 들어, A가 500이고 B가 800인 상태에서 transaction이 실행된 후, A는 450, B는 850가 되어 총합은 여전히 1300으로 유지된다.
일반적으로 consistency 요구사항에는 다음이 포함된다:
- Primary key와 foreign key 같은 explicit integrity constraints
- 모든 계좌 잔액의 합에서 대출 금액의 합을 뺀 값이 보유 현금과 같아야 한다는 implicit integrity constraints
또한, transaction은 항상 consistent database를 봐야 한다.
Isolation (격리성)
Isolation은 여러 transaction이 동시에 실행되더라도 각 transaction이 다른 transaction의 중간 결과를 볼 수 없도록 보장한다.
계좌 이체 예시에서, 만약 3단계와 6단계 사이에 다른 transaction T2가 부분적으로 업데이트된 데이터베이스에 접근할 수 있다면, T2는 inconsistent database(A + B의 합이 실제보다 적은)를 보게 된다.
Isolation은 transaction을 serially(순차적으로) 실행함으로써 간단히 보장할 수 있다.
그러나 multiple transaction을 sequential하게 실행하는 것은 performance 문제를 야기한다.
Isolation의 핵심은 모든 transaction 쌍 Ti와 Tj에 대해, Ti의 관점에서 Tj가 Ti가 시작하기 전에 실행을 완료했거나, Ti가 완료된 후에 실행을 시작한 것처럼 보여야 한다는 것이다.
Durability (지속성)
Durability는 transaction이 성공적으로 완료된 후에는 시스템 failure가 발생하더라도 해당 transaction에 의한 데이터베이스 변경 사항이 유지(persist)됨을 보장한다.
계좌 이체 예시에서, 사용자에게 transaction이 완료되었다고 통지한 후에는($50 이체가 이루어졌음), 소프트웨어나 하드웨어 failure가 발생하더라도 데이터베이스 업데이트가 지속되어야 한다.
Transaction 상태
Transaction은 실행 중에 여러 상태를 거친다:
Active
초기 상태로, transaction이 실행되는 동안 이 상태를 유지한다.
Partially committed
최종 statement가 실행된 후의 상태이다.
Failed
정상적인 실행이 더 이상 진행될 수 없다고 판단된 후의 상태이다.
Aborted
Transaction이 rollback되고 데이터베이스가 transaction 시작 전 상태로 복원된 상태이다. Aborted 후에는 두 가지 옵션이 있다:
- Transaction을 재시작한다 (내부 논리적 오류가 없는 경우에만 가능)
- Transaction을 종료한다
Committed
성공적인 완료 후의 상태이다.
Transaction State Transition Diagram
Transaction의 동시성 제어와 Serializability
Transaction의 동시성 실행(Concurrent Executions)은 현대 데이터베이스 시스템에서 필수적인 기능으로, 여러 transaction이 동시에 실행되면서도 데이터 일관성을 유지하기 위한 메커니즘을 제공한다.
Concurrent Execution의 필요성과 장점
데이터베이스 시스템에서 multiple transaction의 concurrent execution은 다음과 같은 주요 이점을 제공한다:
처리량 증가(Throughput Enhancement)
CPU와 disk 자원의 활용도를 극대화하여 단위 시간당 처리 가능한 transaction 수를 증가시킨다.
예를 들어 한 transaction이 CPU에서 연산을 수행하는 동안 다른 transaction이 disk I/O 작업을 병행할 수 있다.
응답 시간 단축(Response Time Reduction)
짧은 실행 시간을 요구하는 transaction이 오래 실행되는 transaction을 기다리지 않고 즉시 처리될 수 있도록 한다.
이는 특히 온라인 트랜잭션 처리(OLTP) 시스템에서 중요한 성능 요소로 작용한다.
자원 공유 효율성(Resource Sharing Efficiency)
메모리 버퍼, 캐시, 네트워크 대역폭 등 제한된 시스템 자원을 여러 transaction이 공유하며 사용할 수 있게 한다.
하지만 이러한 동시성 실행은 isolation 문제를 야기할 수 있다. 두 transaction이 동일한 데이터 항목에 접근할 때 발생할 수 있는 충돌을 관리하지 않으면 데이터 불일치(inconsistency)가 발생할 위험이 존재한다.
Schedule 관리 체계
Schedule의 기본 정의
Schedule은 동시에 실행되는 multiple transaction의 instruction 실행 순서를 정의하는 프로토콜이다. 효과적인 schedule 관리에는 다음 두 가지 기본 원칙이 적용된다:
- 명령어 완전성 : 하나의 schedule은 관련된 모든 transaction의 instruction을 포함해야 한다.
- 순서 유지 : 개별 transaction 내부의 instruction 순서는 반드시 유지되어야 한다.
Transaction 종료 시나리오에서는 두 가지 경우가 존재한다.
- 성공적인 완료(commit)의 경우 최종 statement로 commit instruction이 기록된다
- 실패(abort) 시에는 rollback을 위한 abort instruction이 최종 statement로 추가된다.
Serial Schedule 1
T1이 A 계좌에서 B 계좌로 $50을 이체하고, T2가 A 계좌의 잔액 중 10%를 B 계좌로 이체한다고 한다.
T1이 먼저 실행되고 그 다음 T2가 실행되는 직렬 스케줄(serial schedule)은 다음과 같다:
Serial Schedule 2
T2 -> T1으로 실행될 경우의 예이다.
Schedule 3
아래 스케쥴은 serial schedule이 아니지만, 스케쥴1과 결과가 같다.
스케쥴 1,2,3은 무결성 제약 조건인 A + B의 값이 보존된다.
Schedule 4
A + B 의 값을 보존을 하지 못하는 스케쥴의 예
Serializability
Serializability 이론의 기본 가정은 개별 transaction이 데이터베이스 일관성을 유지한다는 것이다.
따라서 transaction 집합을 직렬적으로(serial) 실행하면 전체 데이터베이스 일관성이 보존된다.
Serializability의 목표는 동시 실행 결과가 어떤 직렬 실행 결과와 동등(equivalent)함을 보장하는 것이다.
Serializability 유형
주요 serializability 유형은 다음과 같이 분류된다:
Conflict Serializability
instruction 간의 충돌 관계를 기반으로 한 동등성 판단 기준. 실제 시스템에서 가장 널리 사용되는 접근법이다.
View Serializability
데이터 읽기/쓰기 순서의 전체적인 관찰 가능성(view)을 기준으로 한 동등성 판단. 이론적으로 더 넓은 범위의 schedule을 허용하지만 계산 복잡도가 높아 실제 적용에는 제한적이다.
Simplified Transaction Model
실제 transaction 분석을 위해 다음과 같은 단순화 모델이 사용된다:
- read/write operation만 고려(기타 연산 무시)
- 로컬 버퍼에서의 중간 계산 작업 허용
- schedule 구성 요소를 read/write instruction로 제한
이 모델은 동시성 제어 메커니즘의 핵심적인 상호작용을 집중적으로 분석할 수 있는 틀을 제공한다.
Conflict Serializability
충돌 명령어 판별 기준
두 instruction li(Ti)와 lj(Tj)가 충돌하는 조건은 공유 데이터 항목 Q에 대한 접근 방식에 따라 결정된다:
- Read-Read: 양쪽 모두 read(Q)인 경우 - 비충돌
- Read-Write: 한쪽이 read(Q), 다른 쪽이 write(Q) - 충돌
- Write-Read: 한쪽이 write(Q), 다른 쪽이 read(Q) - 충돌
- Write-Write: 양쪽 모두 write(Q) - 충돌
충돌 발생 시 instruction 실행 순서가 최종 결과에 영향을 미치므로 순서 고정이 필수적이다.
비충돌 instruction의 경우 순서 변경이 결과에 영향을 주지 않는다.
Conflict Equivalent 변환
Schedule S가 일련의 비충돌 instruction 교환을 통해 S'로 변환 가능할 때, 두 schedule은 conflict equivalent하다고 판단한다. Conflict serializable schedule은 반드시 어떤 serial schedule과 conflict equivalent해야 한다.
예시:
Schedule 3은 T1과 T2의 비충돌 instruction 교환을 통해 T1→T2 직렬 schedule(Schedule 6)로 변환 가능하므로 conflict serializable하다.
반면 특정 schedule에서는 T3와 T4의 instruction 순서를 어떤 직렬 순서로도 배치할 수 없어 non-serializable로 판단된다.
View Serializability
View Serializability는 데이터베이스 트랜잭션의 동시 실행 관리에서 핵심적인 개념으로, 스케줄의 직렬 가능성 판단 기준 중 하나이다.
이 개념은 Conflict Serializability보다 더 넓은 범위의 스케줄을 허용하지만 계산 복잡도 문제로 인해 실제 시스템에서의 적용에는 제한적이다.
본 논문은 View Serializability의 수학적 정의부터 실무적 고려사항까지 종합적으로 분석한다.
View Serializability의 정의적 특성
두 스케줄 S와 S'가 view equivalent하다고 판단되기 위해서는 다음 세 가지 조건을 동시에 만족해야 한다:
- 초기 값 독립성: S에서 트랜잭션 Ti가 데이터 항목 Q의 초기 값을 읽은 경우, S'에서도 Ti는 반드시 Q의 초기 값을 읽어야 한다.
- 쓰기-읽기 일관성: S에서 Ti가 Tj에 의해 생성된 Q 값을 읽은 경우, S'에서도 Ti는 Tj의 동일한 write(Q) 연산 결과를 읽어야 한다.
- 최종 쓰기 동일성: S에서 Q에 대한 최종 write 연산을 수행한 트랜잭션이 있다면, S'에서도 동일한 트랜잭션이 Q에 대한 최종 write를 수행해야 한다.
이 조건들은 순수히 read/write 연산의 순서와 의존 관계에 기반을 두며, 트랜잭션의 내부 연산 내용이나 계산 로직은 고려하지 않는다. View Serializable 스케줄은 어떤 직렬 스케줄과 view equivalent 관계에 있을 때 성립한다.
Conflict Serializability vs View Serializability
포함 관계
모든 Conflict Serializable 스케줄은 View Serializable의 부분집합이다.
이는 conflict equivalence가 view equivalence보다 더 엄격한 조건이기 때문이다.
구체적으로, 두 스케줄이 conflict equivalent하면 자동으로 view equivalent하지만 그 역은 성립하지 않는다.
차이점 사례
다음 스케줄은 View Serializable이지만 Conflict Serializable이 아닌 대표적 예시이다:
이 경우 T1과 T2가 모두 Q에 write를 수행하지만 T3가 최종적으로 T2의 결과를 읽는다면, 이 스케줄은 T1→T2→T3 직렬 실행과 view equivalent하다.
그러나 T1과 T2의 write 연산이 충돌하므로 conflict serializable하지 않다.
conflict serializable하지 않지만 View Serializable하지 않은 스케쥴을 blind writes라고 부른다.
기타 Serializability 예시
- 아래 위 예시는 결과적으로 직렬 schedule <T1, T5>와 동일한 결과를 내지만, conflict equivalent나 view equivalent하지 않다.
- 즉, read/write 외의 연산까지 분석해야만 이러한 동등성을 판단할 수 있다.
Serializability 테스트 기법
데이터베이스 시스템에서 transaction의 동시 실행은 성능 향상에 중요하지만, 데이터 일관성을 유지하기 위해 serializability가 보장되어야 한다.
Serializability를 테스트하는 여러 방법들은 복잡도와 적용성 측면에서 차이가 있다.
Serializability 테스트를 위한 precedence graph
Serializability 테스트는 주로 precedence graph를 이용한다. 이는 transaction들의 실행 순서와 충돌 관계를 표현하는 directed graph이다.
Precedence graph에서:
- Vertex(정점)는 각 transaction(T₁, T₂, ..., Tₙ)을 나타낸다
- Ti에서 Tj로 arc(방향성 있는 간선)를 그리는 경우는 두 가지 조건을 모두 만족할 때이다:
- 두 transaction이 같은 데이터 항목에 접근하며 충돌한다
- Ti가 Tj보다 먼저 해당 데이터 항목에 접근했다
- Arc에 접근된 데이터 항목을 label로 표시할 수 있다
Conflict serializability 테스트
Schedule이 conflict serializable한지 판단하는 방법은 precedence graph의 특성을 분석하는 것이다. 가장 중요한 테스트 기준은 다음과 같다:
- Schedule은 precedence graph가 acyclic(순환이 없음)일 때만 conflict serializable하다
- Cycle detection algorithm은 보통 O(n²) 시간 복잡도를 가진다(n은 vertex 수)
- 최적화된 알고리즘은 O(n + e) 시간 복잡도를 가진다(e는 edge 수)
Precedence graph가 acyclic하다면, 해당 graph의 topological sorting을 통해 serializability order를 얻을 수 있다.
Topological sorting은 graph의 partial order를 반영하는 linear order를 제공한다.
View serializability 테스트
View serializability는 conflict serializability보다 더 넓은 범위의 schedule을 허용하지만, 테스트하기가 훨씬 어렵다.
- Conflict serializability를 위한 precedence graph 테스트는 view serializability 테스트에 직접 적용할 수 없다
- View serializability 테스트를 위한 확장 방법은 precedence graph 크기에 대해 exponential cost를 가진다
- Schedule이 view serializable한지 확인하는 문제는 NP-complete class에 속한다
- 따라서 효율적인 알고리즘의 존재 가능성은 extremely unlikely하다
실제 시스템에서는 view serializability의 일부 sufficient conditions만 확인하는 practical algorithm을 사용한다.
이러한 방식은 완벽한 view serializability 판단은 아니지만, 실용적인 측면에서 적절한 타협점을 제공한다.
Serializability 테스트는 데이터베이스 시스템의 concurrency control mechanism 설계에 핵심적인 이론적 토대를 제공한다.
특히 conflict serializability 테스트는 계산 복잡도 측면에서 효율적이기 때문에 실제 DBMS에서 널리 채택되고 있다.
Recoverable Schedule
- Recoverable schedule은 transaction failure가 동시에 실행되는 다른 transaction에 미치는 영향을 고려해야 한다.
- 정의: 어떤 transaction Tj가 이전에 Ti가 write한 데이터 항목을 read했다면, 반드시 Ti의 commit 연산이 Tj의 commit 연산보다 먼저 발생해야 한다.
Recoverable하지 않은 예시
- T8이 A를 read하고 write, T9가 A를 read한 뒤 commit
- 만약 T8이 abort하면, T9는 일관성 없는 데이터 상태를 읽었을 수 있다.
- 따라서 데이터베이스는 모든 schedule이 recoverable하도록 보장해야 한다.
Cascading Rollback
- Cascading rollback은 하나의 transaction failure가 연쇄적으로 여러 transaction의 rollback을 유발하는 현상이다.
Cascading rollback이 발생하는 예시
- T10이 A와 B를 읽고 A를 write, T11이 A를 read하고 write, T12가 A를 read
- T10이 abort하면, T11과 T12도 rollback해야 한다.
- 이 현상은 많은 작업이 한 번에 무효화될 수 있으므로 효율성 저하의 원인이 된다.
Cascadeless Schedule
- Cascadeless schedule은 cascading rollback이 발생하지 않는 schedule을 의미한다.
- 정의: Tj가 Ti가 write한 데이터를 read하는 경우, 반드시 Ti의 commit 연산이 Tj의 read 연산보다 먼저 발생해야 한다.
- 즉, commit된 데이터만 읽을 수 있다(Read committed data only).
- 모든 cascadeless schedule은 recoverable schedule이기도 하다.
- 실무적으로는 cascadeless schedule만 허용하는 것이 바람직하다.
댓글