트랜잭션 이론

트랜잭션 개념

트랜잭션의 성질 ACID

트랜젝션은 데이터베이스 무결성을 유지하기 위해 ACID 성질을 가져야한다.
데이터의 무결성은 데이터의 정확성, 일관성, 유효성이 유지되는 것을 말한다. 즉 현실세계의 데이터와 같아야함을 말한다.

• Atomicity (원자성)
  트랜잭션의 모든 연산은 데이터베이스에 올바르게 반영되거나, 하나도 반영되지 말아야 한다.

• Consistency (일관성)
  단일 트랜젝션의 수행은 데이터베이스의 데이터 무결성을 유지해야 한다.

• Isolation (고립성)
  여러 개의 트랜잭션이 동시에 수행되더라도, 각 트랜잭션은 다른 수행되는 트랜잭션의 존재를 몰라야 한다. 트랜잭션 수행과정의 중간값은 다른 트랜잭션으로부터 숨겨져야 한다.

• Durability (지속성)
  데이터베이스에 성공적으로 반영된 트랜잭션은 후에 데이터베이스 시스템 장애가 발생하더라고 지속되어야 한다.

트랜잭션 상태

• Active
  처음 상태이다. 트랜잭션이 수행되는 동안 이 상태에 머문다.
• Partially committed
  마지막 문장이 수행되고 난 이후이다.
• Aborted
  트랜잭션이 rollback되고 데이터베이스가 트랜잭션 시작 이전의 상태로 복구된 이후이다.
• Commited
  트랜잭션이 성공적으로 종료된 이후이다.

트랜잭션 직렬가능성

트랜잭션의 올바른 실행

다수의 트랜잭션을 수행하면서 무엇이 올바른 동시성 제어인지 알아야 한다.
트랜잭션을 순차적으로 실행하는 것 (serial execution)은 상상 올바르다. 하지만 이는 현실적으로 불가하여 올바른 트랜잭션의 판단기준으로 삼는다.

트랜잭션 동시성 오류

nonserializable 하게 트랜잭션을 수행하면 3가지 오류가 있을 수 있다. (Read Write만 고려하였을때)

• Dirty Read
  완료되지 않은 값 (uncommitted value)를 읽는 것을 말한다.
• Lost Update
  자신이 갱신한 값을 commit하기 이전에 다른 트랜잭션의 갱신에 의해 잃어버리는 것을 말한다.
• Unrepeatable read
  한 트랜잭션 내에서 두 개의 순차적인 Read 연산이 있고, 그 사이에 Write연산이 없을 때, 각 Read연산이 읽은 값이 다른 값을 가지는 것을 말한다.

동시성 제어는 이 세 현상을 방지하기 위한 이론이다.

직렬가능성

스케줄이란 다수의 트랜잭션에 속하는 연산이 수행된 시간 순서이다. 동시적으로 수행된 트랜잭션의 모든 연산이 스케줄에 나와야 하고, 스케줄에 있는 특정 트랜잭션에 속하는 연산순서는 해당 트랜잭션 내의 연산순서와 동일해야 한다.

스케줄이 직렬수행 스케줄 결과와 동일하다면 이를 직렬가능 스케줄 (serializable Schedule)이라고 한다. 스케줄과 관련되는 트랜젝션이 N개라면 경우의 수는 N!인데, 직렬가능 스케줄은 이 N!중 최소 하나의 스케줄이 직렬스케줄과 동일한 결과를 보여야 한다.

스케줄 결과의 동일함을 정의하는 방식은 Conflict Serializability, View Serializability 가 있다.

충돌 직렬가능성 (Conflict Serializability)

동일한 데이터에 대한 두 개의 연산 중, 최소 한 개 연산이 Write라면, 두 개 연산은 충돌한다고 한다.
충돌연산은 연관되는 트랜잭션의 직렬실행 순서를 결정한다. 비충돌연산은 두 연산의 순서를 스케줄에서 바꾸어도 연산 효과가 동일하게 나오나, 충돌연산은 효과가 다르게 나온다.'

스케줄에서 비충돌 연산을 서로 바꾸어 직렬 스케줄이 되면 충돌 직렬 가능 스케줄이라고 한다.'

뷰 직렬가능성 (View Serializability)

스케줄 S와 S'가 있고 Ti, Tj가 있을 때, S의 각 트랜잭션의 Read 연산과 S'의 각 트랜잭션의 Read 연산이 같은 값을 읽고, S와 S'의 마지막 write연산의 값이 동일하다면, S와 S'를 view equivalent하다고 한다.

serial 스케줄과 view squivalent하면 view Serializabile하다고 한다.

충돌 직렬가능성 vs 뷰 직렬가능성

뷰 직렬 가능 스케줄의 일부가 충돌 직렬가능 스케줄이다.

직렬 가능실험

Conflict Serializability한 경우에 대해서는 precedence graph를 사용한다. 자원 A가 있을 때 자원 A를 가진 Ti에서 자원 A를 요구하는 Tj로 화살표를 그린다. 이 그래프를 그려 cycle이 나오면 충돌 직렬 가능하지 않은 스케줄이다.

View Serializability를 확인하는 algorithm은 np problem이다. 따라서 실질적으로 확인할 수 없다.

회복가능

회복 가능 스케줄

트랜잭션 Tj가 Ti에 의해 Write된 정보를 읽는다고 할때, Ti의 commit 연산이 Tj의 commit연산 이전에 있어야 회복가능 스케줄이라고 한다.

Cascading Rollbacks

Cascading Rollback은 트랜 잭션 하나의 rollback이 다른 트랜잭션의 rollback을 유도하며 이는 다른 트랜잭션에서 commit한 데이터만 읽도록 함으로써 방지할 수 있다.

Cascadeless Schedule (Avoiding Cascading Aborts)

Cascadeless Schedule에서, 트랜잭션 Tj, Ti가 있을 때, Ti가 한 데이터를 Read하기 이전에, Tj가 그 데이터를 Write하고 commit한다. 즉 임의의 트랜잭션이 Read 하는 데이터에 대해서, 트랜잭션이 해당 데이터를 읽기 이전에 그 데이터를 마지막으로 Write한 트랜잭션이 commit하기를 요구하는 스케줄이다.

결론

데이터 베이스는 conflict serializable하거나 view serializele하고, recoverable하면서 cascadeless한 스케줄을 제공하는 메커니즘을 제공해야 한다.

직렬 스케줄만 하는 것은 결과는 올바르나, 동시성이 매우 떨어져 성능이 매우 좋지 않게된다. 또한 이미 수행된 스케줄에 대해 serializability를 테스트 하는 것은 너무 늦고 성능이 좋지 않다. 따라서 우리는 우리가 만족하는 스케줄이 나오도록 하는 프로토콜을 만들 필요가 있다. 이를 동시성 제어 규약이라고 한다.