[DB] Serializability

Lost Update

두 개 이상의 트랜잭션이 동일한 데이터를 동시에 갱신하려고 할 때 발생하는 문제이다. 이로 인해 한 트랜잭션의 결과가 다른 트랜잭션에 의해 덮어써져 이전의 변경 내용이 사라지게 된다.
예시:

• 초기 상태: B의 계좌 잔액은 100만 원이다.
• 트랜잭션 1 (T1): A가 B에게 20만 원을 입금한다.
• 트랜잭션 2 (T2): B가 본인 계좌에 30만 원을 입금한다.

Lost Update 시나리오:

1. T1과 T2가 동시에 B의 잔액을 읽어온다. 두 트랜잭션은 B의 현재 잔액을 각각 100만 원으로 인식한다.
2. T1이 B의 잔액에 20만 원을 더해 120만 원으로 업데이트한다.
3. T2가 B의 잔액에 30만 원을 더해 130만 원으로 업데이트한다.
4. 최종 결과: B의 잔액은 130만 원이 되며, T1에서 수행한 20만 원의 입금 작업은 사라지게 된다. T1의 갱신이 T2에 의해 덮어써진 것이다.

 

스케줄

여러 트랜잭션이 동시에 실행될 때 각 트랜잭션에 속한 연산들이 어떤 순서로 실행될지를 정의하는 것이다. 혹은 각 트랜잭션에 속한 operation들의 실행 순서라고 할 수 있다.
스케줄의 유형에는 직렬 스케줄(serial schedule)과 병행 스케줄(concurrent schedule)이 있다.

• 직렬 스케줄:
  • 트랜잭션들이 순차적으로 실행되며, 서로 간섭하지 않는다.
  • 결과적으로 데이터베이스의 일관성이 유지된다.
  • 각 트랜잭션 내의 연산들의 순서는 바뀌지 않는다.
  • 현실적으로는 I/O 작업이 필요한 동안 CPU가 유휴 상태가 되므로 사용하기 어려운 경우가 많다.
  • 예제:
    • 이 스케줄에서는 트랜잭션 T1이 완료된 후, 트랜잭션 T2가 실행된다:
    • T1: B의 잔액을 읽어 20만 원을 더하고 저장한다.
    • T2: B의 잔액을 읽어 30만 원을 더하고 저장한다.
    • 최종 결과: B의 잔액은 150만 원이 된다.
• 병행 스케줄:
  • 여러 트랜잭션이 동시에 실행된다.
  • Lost Update 문제가 발생할 수 있다.
  • 예제:
    • T1: B의 잔액을 읽어 20만 원을 더하고 저장한다.
    • T2: B의 잔액을 읽어 30만 원을 더하고 저장한다.
    • 최종 결과: B의 잔액은 130만 원이 된다.

 

Conflict

두 트랜잭션 내의 연산들이 서로 간섭하여 데이터의 일관성을 해칠 수 있는 상황을 의미한다. 구체적으로, Conflict는 다음 세 가지 조건을 모두 만족할 때 발생한다:

1. 서로 다른 트랜잭션의 연산: 연산들이 서로 다른 트랜잭션에 속해 있어야 한다.
2. 동일한 데이터 항목 접근: 연산들이 동일한 데이터 항목에 접근해야 한다.
3. 적어도 하나의 쓰기 연산: 두 연산 중 적어도 하나는 데이터를 수정하는 쓰기 연산이어야 한다.

 

Conflict Equivalent

두 개의 스케줄이 동일한 트랜잭션 집합을 가지며, 모든 conflicting operations의 순서가 동일하여 결과적으로 동일한 데이터베이스 상태를 만들어내는 경우를 의미한다. 두 스케줄이 Conflict Equivalent 하려면 다음 조건을 만족해야 한다:

1. 동일한 트랜잭션 집합: 두 스케줄이 동일한 트랜잭션들로 구성되어 있어야 한다.
2. Conflicting Operations의 순서: 두 스케줄에서 모든 Conflict를 일으키는 연산들의 순서가 동일해야 한다.

예시:

• 스케줄 1:
  • T1: READ(X)
  • T1: WRITE(X) // T1이 X를 수정함
  • T2: READ(Y)
  • T2: WRITE(Y) // T2가 Y를 수정함
  • T1: READ(Y)
  • T1: WRITE(Y) // T1이 Y를 수정함
• 스케줄 2:
  • T2: READ(Y)
  • T2: WRITE(Y) // T2가 Y를 수정함
  • T1: READ(X)
  • T1: WRITE(X) // T1이 X를 수정함
  • T1: READ(Y)
  • T1: WRITE(Y) // T1이 Y를 수정함

Conflict 분석:

1. 스케줄 1과 스케줄 2는 같은 트랜잭션 집합을 포함하고 있다 (T1과 T2).
2. 두 스케줄 모두 T1과 T2의 연산 순서에서 conflicting operations의 순서가 동일하다:
   • T1의 WRITE(X)는 T2의 연산 이전에 실행됨 (스케줄 1에서는 T1이 X를 수정한 후 T2가 Y를 수정함, 스케줄 2에서는 T2가 Y를 수정한 후 T1이 X를 수정함).
   • T1의 WRITE(Y)는 T1의 READ(Y)와 WRITE(X) 후에 실행됨.

따라서, 스케줄 1과 스케줄 2는 Conflict Equivalent이다. 이 두 스케줄은 모든 conflicting operations의 순서를 유지하며 동일한 최종 결과를 만들어낸다.
 

Conflict Serializable

Conflict Serializable은 병행 스케줄이 직렬 스케줄과 conflict equivalent일 때, 즉 병행 스케줄이 직렬 스케줄의 실행 순서와 동일한 순서로 연산이 이루어졌을 때, 해당 병행 스케줄이 Conflict Serializable하다고 한다. Conflict Serializable 한 병행 스케줄을 허용하면 성능에 대한 고민 없이 데이터의 일관성을 유지할 수 있다.