[Database] Transaction

Transaction Concept

 

Transaction이란 프로그램의 실행 단위입니다. 예를 들어 $50을 A계좌에서 B계좌로 이동하는 Transaction은 다음과 같습니다:

Transaction to transfer $50 from account A to account B

 

이 과정에서 두 가지 issues가 있을 수 있습니다. (1) 만약 hardware failure나 system crashes와 같이 다양한 종류의 failure가 중간에 발생하는 경우 어떻게 대처해야하는지, (2) 그리고 하나의 Transaction만을 수행하면 performance가 좋지 않으니 어떻게하면 여러개의 transaction을 동시에 처리해야하는지... 가 있습니다. * 위 예시 transaction에서 A:= A - 50은 local buffer(memory)에서 이뤄지는 연산이지 실제 DB인 disk에 적용되는 연산이 아닙니다. 예를 들어 B := B + 50 이후 write(B)가 실행되기 전에 system crash로 인해 그 다음이 실행되지 않는다면, A 계좌에서는 $50이 빠져나갔지만, B 계좌에서는 $50이 들어오지 않는 문제가 발생할 수도 있습니다. 

 

Atomicity requirement

 

위 *에서 말한 예시가 Atomicity requirement를 만족시키지 않는 예시입니다. 즉 시스템은 transaction의 부분적인 실행을 허용하지 않습니다. transaction 실행 중에 어떤 문제가 발생하면, 이를 끝까지 진행시키거나 아니면 아에 transaction이 실행되기 전으로 돌려놔야합니다. *All or Nothing 

 

Durability requirement

 

Durability requirement는 한 번 transaction이 실행 완료되면 그 결과는 softwar나 hardware failure에도 불구하고 database에 남아있어야합니다. 즉 영구성이 보존되어야합니다.

 

Consistency requirement

 

어떤 database는 user가 정해둔 consistency 조건이 있고 이를 만족시켜야할 수도 있습니다. 아까 봤던 계좌 송금 예시를 보겠습니다. A계좌에서 B계좌로 송금하는 과정에서 반드시 지켜져야하는 consistency는 A계좌의 잔고의 합과 B계좌의 잔고의 합이 송금 전과 후에 변함이 없어야 한다는 것입니다:

Consistency requirement

 

consistency에는 Explicit consistency(e.g., primary key or foreign key)와 Implicit consistency(like above example)이 존재합니다. 그리고 transaction은 이 consistency를 지켜야합니다.

 

Isolation requirement

 

transaction의 isolation이란 transaction 과정에서는 다른 transaction이 끼어들 수 없다는 것을 말합니다. 아까 봤던 계좌 송금 예시에서 계좌를 송금하는 transaction T1과 A와 B, A와 B의 잔고의 합을 출력하는 transaction T2가 있다고 가정했을때, T1이 실행하는 중에 T2가 실행된다면 이는 transaction의 isolation을 위반한 것이 됩니다:

Transaction Isolation

 

위 그림에 따르면 T2는 우리가 원하는 결과를 보여주지 않습니다. *계좌 B는 아직 $50이 들어오지 않은 상태에서 계좌 잔고를 출력하기 때문입니다. Transaction의 isolation은 transaction들을 serially 실행하면 이를 보장할 수 있긴 합니다. 하지만 이는 performance problem이 존재합니다. 따라서 최대한 serializability를 유지하면서 concurrency를 보장하는 방법을 찾는 것이 중요합니다.

 

ACID Principles

 

이들을 모아 ACID Principles라고 부릅니다:

• Atomicity - Either all operations of the transaction are properly reflected in the database or none are. All or Nothing.
• Consistency - Atomic execution of a transaction in isolation preserves the consistency of the database.
• Isolation - Although multiple transactions may execute concurrently, each transaction must be unaware of other concurrently executing transactions. Intermediate transacti on results must be hidden from other concurrently executed transactions.
  • That is, for every pair of transactions Ti and Tj , it appears to Ti that either Tj , finish ed execution before Ti started, or Tj started execution after Ti finished.
• Durability - After a transaction completes successfully, the changes it has made to th e database persist, even if there are system failures.

 

Transaction State

 

Transaction에는 state가 존재하며 tansaction은 이 상태들을 이동합니다.

• Active - transaction의 초기 상태입니다. transaction은 그것이 실행되는 동안 해당 state에 머무릅니다.
• Partially committed - transaction의 마지막 statement를 실행하고 난 후의 상태입니다.
• Failed - 정상적인 실행이 불가능함을 확인한 후의 상태입니다.
• Aborted - transaction이 roll back하고, database에는 transaction 이전의 상태로 다시 저장된 상태를 말합니다. abort후에는 두 가지 옵션이 존재합니다:
  • Restart the transaction - 이는 transaction 자체에는 논리적 오류가 없는 경우에 사용합니다.
  • Kill the transaction - transaction 자체에 문제가 있어서 다시 실행해도 의미가 없을때 사용합니다.
• Committed - 완전히 transaction이 끝나고, database에 그 결과를 저장한 상태입니다.

Transaction State Transition Diagram

 

Concurrent Executions

 

많은 수의 transaction들이 성능을 위해 동시에 실행될 수 있습니다. 이는 (1) Processor나 disk의 utilization의 측면에서 유리합니다. 이는 더 나은 transaction throughput을 만듭니다. (2) 또한 Reduced average response time을 만듭니다. 짧은 transaction들이 긴 길이의 transaction을 기다릴 필요가 없기 때문입니다(like convoy effect).

 

Concurrecy control schemes는 일반적으로 lock을 통해서 수행됩니다.

 

Schedules

 

Schedule은 실행해야하는 transaction의 instruction 순서를 말합니다. 따라서 transaction들을 scheduling한다는 것은 transaction들을 구성하는 instruction들을 모두 포함하며, instruction들의 순서를 조절하는 것을 말합니다. 어떤 transaction이 완벽하게 끝난다는 것은 last statement에 의해 commit instruction이 실행됨을 말합니다. 만약 last statement에서 abort를 발생시켰다면, 이는 transaction이 해당 명령들을 실행하는데 실패했다는 것을 의미합니다.

 

Serial Schedule 1

 

아까 송금 예시를 들어보겠습니다:

A에서 B로 $50을 송금하는 transaction을 T1, A의 잔고의 10%를 B에 송금하는 transaction을 T2라고 했을때, 이를 serial하게 실행하면 다음과 같습니다(serial하게 실행했으므로 isolation을 보장합니다):

Serial Schedule 1

 

Serializable Schedule

 

다음의 명령은 serial한 명령 순서는 아니지만 serial schedule 1과 동일한 결과를 발생시키므로 이를 serializable schedule이라고 부릅니다:

Serializable Schedule

 

Schedule 4

 

반면 schedule 4는 A+B의 결과를 보전하지 않으므로 Serializable Schedule이 아닙니다:

Schedule 4

 

*T2에서 read(A)는 T1에서 A := A - 50의 결과를 반영하지 않기 때문에 serial schedule 1과 같은 결과를 만들지 않습니다. 따라서 Serializable schedule이 아닙니다.

 

Serializability

 

각각의 transaction들이 database consistency를 만족한다고 가정했을때, serial excution의 결과와 임의의 schedule의 결과가 같다면 이를 serializability가 있다고 합니다:

Serializability

 

Serializability의 종류는 크게 두 가지입니다. (1) Conflict serializability와 (2) View serializability입니다.

 

Conflicting Instructions

 

Transaction T1과 T2의 instruction I1, I2가 있을때, 공유하는 item Q에 대해 다음과 같은 명령들이라면 conflict가 있다고 합니다:

1. I1 = read(Q), I2 = read(Q); I1과 I2는 conflict가 아닙니다. read끼리는 conflict를 발생시키지 않기 때문입니다.
2. I1 = write(Q), I2 = read(Q); I1과 I2는 conflict입니다.
3. I1 = read(Q), I2 = write(Q); I1과 I2는 conflict입니다.
4. I1 = write(Q), I2 = write(Q); I1과 I2는 conflict입니다.

 

만약 conflict에 해당하는 instruction이 conflict가 아니기 위해서는 두 instruction의 순서를 바꿨을때도, 같은 결과를 만들어야합니다. 만약 임의의 schedule S와 S'에 대해, non-conflict instructions들을 교환함으로써 serial schdule을 만들 수 있다면 S와 S'을 conflict equeivanlent하다고 합니다. 또한 S와 S'를 conflict serializable하다고 합니다.

 

예를 들어 다음과 같은 경우 Schedule 3을 conflict serializable한 schedule이라고 부릅니다:

Conflict Serializability

 

서로 non-conflict인 instructions들인 <read(A), write(A)>와 <read(B), write(B)>의 순서를 swap하면 serial한 schedule인 Schedule 6로 만들 수 있기 때문입니다. *<read(A), write(A)>와 <read(B), write(B)>는 서로 다른 item을 참조하고 있기 때문에 non-conflict instructions입니다. 

 

반면 다음과 같은 경우 conflict serializable하지 않다고 말합니다:

Conflict Serializability

 

우선 non-conflict instruction이 T3와 T4사이에 없으며, non-conflict instructions들을 swap해서 serial schedule과 동일한 결과를 만들 수도 없습니다. <T3, read(Q)>, <T3, write(Q)>, <T4, write(Q)>와 동일한 결과를 만들지 않기 때문입니다.

 

View Serializability

 

같은 transaction set에 대한 schedule S와 S'에 대해 다음의 조건을 만족한다면 서로 view equivalent하다고 합니다:

1. 만약 S에서 T1이 Q에 대해 가장 먼저 read를 했다면, S'에서도 T1이 Q에 대해 가장 먼저 read해야합니다. 즉, 가장 처음 read하는 Transaction은 서로 동일해야합니다.
2. 만약 S에서 T1이 Q에 대해 가장 마지막으로 write을 했다면, S'에서도 T1이 Q에 대해 가장 마지막으로 write해야합니다. 즉, 가장 마지막으로 write하는 Transaction은 서로 동일해야합니다.
3. 만약 S에서 T1이 Q에 대해 read한 것이 T2(if any)에서 생산해낸 결과라면, S'에서도 T2(if any)가 생산해낸 결과를 T1에서 read해야합니다.

 

다음의 예시는 conflict serializable하지는 않지만 view serializable한 예시입니다:

View Serializabilty

 

serial schedule <T27, T28, T29>와 비교했을때, 가장 먼저 Q를 read한 transaction은 T27로 동일하며(condition 1), 가장 마지막에 Q을 write한 transaction도 T29로 동일합니다(condition 2). condition 3에 대한 case는 아에 존재하지 않아 view serializable하다고 볼 수 있습니다.

 

하지만 conflict serializable하지는 않은데, instruction을 swap하여 serial schedule로 만들기 위해서는 conflict instruction을 swap해야하기 때문에(T27의 write(Q)와 T28의 write(Q)를 교환해야합니다), conflict serializable은 아닙니다. 이때 view serializable schedule들은 blind writes들을 갖고있다고 말합니다. *conflict의 결과가 마지막 write에 의해 가려지는 것을 말합니다.

 

Is this a view serializable schedule?

 

view serializable condition 1과 2는 만족하지만(T1에서 Q를 처음 읽고, T3에서 Q를 가장 마지막에 write하는 것은 동일합니다), condition 3인 read한 데이터는 두 schedule에서 같은 transaction이 생산해낸 것이어야합니다. 하지만 serial schedule에서는 T2의 read는 T2에 의해 produce된 것이며, 위 예시 schedule의 경우는 T1에 의해 produce된 것이기 때문에, condition 3에 위배, view serializable하지 않습니다.

 

Other Notions of Serializability

 

아래의 예시의 경우 conflict serializable이지도, view serializable도 아닌 schedule이지만 serial schedule과 동일한 결과를 만들어내는 schedule입니다:

Other notions of serializability

 

이는 중간 연산의 종류가 +, -이기 때문입니다. +나 -는 교환법칙이 성립하여 연산 순서가 바뀌어도 동일한 결과를 만들어내기 때문입니다. 즉, read와 write뿐만 아니라 operation의 종류 또한 분석해야합니다.

 

Testing for Serializability

 

serializability를 분석하기 위해서 precedence graph를 사용할 수 있습니다. 이는 transaction을 정점으로하는 방향 그래프입니다. T1과 T2가 서로 conflict transaction이며, T1이 T2에 대해 해당 item에 먼저 접근했다면, T1에서 T2로 향하는 화살표를 그립니다. 만약 사이클이 존재한다면 이는 serializable하지 않다고 분석할 수 있습니다. *conflict instruction들의 순서가 Transaction의 순서와 달리 꼬여있으면 swap을 통해 serial한 schedule로 만들 수 없기 때문입니다.

 

다시 말해, precedence graph가 acyclic하다면 conflict serializable하다고 볼 수 있습니다. 이를 detection하는 algorithm은 O(N^2) 혹은 더 나은 알고리즘을 통해서 O(N + E) 만큼의 시간복잡도를 갖습니다. 이는 topological sorting을 통해 serializability order를 얻을 수 있습니다:

왜 사이클이 있는 선행(precedence) 그래프 ⇒ Conflict-serializable 하지 않다?

핵심 논리

1. Conflict-serializability
   한 스케줄 S가 어떤 직렬(serial) 스케줄 Sʹ과 동일한 conflict 효과를 가지면 S를 conflict-serializable 하다고 정의한다.
2. 선행 그래프(Precedence / Serialization graph)
   • 정점 : 트랜잭션
   • 방향 간선 Tᵢ → Tⱼ : S 안에 Tᵢ 의 연산 과 Tⱼ 의 충돌(conflict) 연산 이 존재하며,
     그 연산 순서가 Tᵢ 먼저, Tⱼ 나중 인 경우
   • Acyclic ⇔ topological order 존재
     → 그래프의 위상 정렬이 직렬 순서가 됨.
   • Cycle ⇒ 어떤 위상 정렬도 불가능
     → 직렬 순서가 존재하지 않으므로 conflict-serializable 하지 않음.

직관적 해석 — “순서를 동시에 두 방향으로 요구”

사이클이 있다는 것 =
어떤 트랜잭션 집합이 “내가 네 앞” / “네가 내 앞” 요구를 원형으로 꼬아 놓음.
직렬 스케줄은 한 줄로 나열한 단일 순서를 뜻하므로,
원형 요구를 선을 끊지 않고 만족시키는 방법이 없다는 뜻이다.

 

⚡ Precedence Graph (직렬가능성 검사 그래프)에서 간선(Edge)을 그리는 규칙

조건한국어 풀이간단 예시 스케줄 (→ 는 시간 순서)그려지는 간선

① 두 트랜잭션이 같은 데이터 항목 X를 둘 다 접근 그리고 그 접근들이 충돌한다	충돌 = (R/W, W/R, W/W) 조합 단순 R/R 은 충돌 아님	T₁ : … W(X) … T₂ : … R(X) …	충돌 O
② Tᵢ 가 먼저, Tⱼ 가 나중	스케줄에서 실제로 먼저 발생한 방향으로 간선	… W₁(X) … R₂(X) …	T₁ → T₂

 

같은 항목에 대해 읽기-쓰기 / 쓰기-읽기 / 쓰기-쓰기가 시간 차를 두고 발생하면 앞선 트랜잭션 → 뒤따른 트랜잭션 방향의 간선 하나를 그린다.
간선에 X 라벨을 붙여두면 “무슨 항목 때문에 생긴 의존인지” 기록할 수 있다.

---

🔍 예시로 보는 간선 생성

예시 1) 단순 의존 (사이클 없음)

css

복사편집

스케줄 1) T1: W(A) 2) T2: R(A) 3) T2: W(B) 4) T3: R(B)

1. A 항목
   • W₁(A) → R₂(A) ⇒ T1 → T2 생성
2. B 항목
   • W₂(B) → R₃(B) ⇒ T2 → T3 생성

그래프: T1 → T2 → T3 (사이클 X) → 직렬가능

---

예시 2) 사이클이 생기는 경우 (직렬가능하지 않음)

css

복사편집

스케줄 1) T1: W(A) 2) T2: R(A) 3) T2: W(B) 4) T1: R(B)

1. A 때문 → T1 → T2
2. B 때문 → T2 → T1

두 간선이 서로 반대 방향으로 이어져 T1 ↔ T2 사이클 → 충돌 직렬화 불가능

---

예시 3) 읽기-읽기만 있는 경우

css

복사편집

T1: R(C) T2: R(C)

• R/R 조합은 충돌이 아님 → 간선 없음
• 그래프에 아무 엣지도 그려지지 않으므로 직렬화에 영향 X.

---

한 줄 정리

“같은 데이터 항목을 두 트랜잭션이 순서 차를 두고 ‘쓰기 또는 읽기+쓰기’로 접근했다면, 먼저 접근한 트랜잭션에서 나중 트랜잭션으로 간선 하나를 그린다.”
이때 그래프에 사이클이 없으면 스케줄은 충돌-직렬가능, 사이클이 있으면 직렬가능하지 않다.

Test for conflict serializability

 

Test for view serializability

 

conflict serializability를 검사하는 것과 달리, view serializability를 검사하는 것은 NP complete problem이기 때문에 충분조건을 확인하는 방법으로 실질적인 알고리즘이 정립되어있습니다. 이런 실용적인 문제 때문에 Conflict serializability가 DBMS에서 가장 많이 사용됩니다:

Conflict Serializability vs. View Serializability

 

Recoverable Schedules

 

만약 Transaction T1이 이전 Transaction T2에서 생산한 결과를 가지고 read했을때, T2가 T1이 commit하기 전에 commit을 이미 했다면 이를 Recovable Schedule이라고 부릅니다. 아래의 예시는 recoverable 하지 않은 schedule의 예시입니다:

not recoverable

 

T9에서 읽은 데이터를 T8에서 생산했는데, T9에서 commit하기 전에 T8에서 이에 대해 commit을 하지 않은 상황입니다(not recoverable). 이때 T8에서 abort가 발생한다면 T8은 모두 roll back되며, T9는 nothing이 된 데이터 A를 이용해서 commit을 했기 때문에 consistency에 문제가 발생할 수 있습니다. 즉, commit하지 않은 데이터로 read를 했고, commit을 했기 때문에 발생하는 문제입니다. 

 

Cascading Rollbacks

 

Cascading rollback은 하나의 transaction에서 failure가 발생했을때, 이에 관련된 모든 transaction들이 모두 rollback되는 것을 말합니다. 즉, 가장 마지막 commit되었던 상태로 모두 돌아가는 것을 말합니다(recoverable).

Cascading Rollbacks

 

많은 양의 transaction들을 rollback한다면 overhead가 매우 커질 것이며, 이를 줄이는 것이 목표가 됩니다. 그런 schedule을 cascadeless schedule이라고 부릅니다. 이를 cascading rollback이 발생하지 않는 schedule을 말합니다. 이는 T1에서 생산한 데이터를 T2에서 읽을 때, 반드시 그 전에 T1에서 commit을 하는 것으로써 보장할 수 있습니다. 즉 read는 반드시 commit한 데이터를 읽어야합니다!

 

모든 cascadeless schedule들은 recoverable하다고 볼 수 있습니다.