schedule, serializability

Schedule

• transaction1: A가 B의 계좌에 20만원을 이체하는 작업
• transaction2: B가 자신의 계좌에 30만원을 입금하는 작업

이렇게 두 개의 트랜잭션이 존재합니다.

여러 트랜잭션이 동작할 때 여러 트랜잭션에서 수행해야 하는 작업들의 순서를 나열한 것을 scehdule이라고 합니다.

설명이 좀 복잡하니까 예를 들어 살펴봅시다.

transaction1: A가 B의 계좌에 20만원을 이체하는 작업

1. r1(A): A의 계좌를 조회합니다.(DB read)
2. w1(A): A의 계좌에서 20만원을 뺍니다.(DB write)
3. r1(B): B의 계좌를 조회합니다.(DB read)
4. w1(B): B의 계좌에 30만원을 더해줍니다(DB write)

transaction2: B가 자신의 계좌에 30만원을 입금하는 작업

1. r2(B): B의 계좌를 조회합니다.(DB read)
2. w2(B): B의 계좌에 30만원을 더해줍니다(DB write)

이 두 트랜잭션은 transaction1이 동작한 후 transaction2가 동작할 수도 있고,

schedule1. r1(A)-w1(A)-r1(B)-w1(B)-commit1-r2(B)-w2(B)-commit2

transaction2가 동작한 후 transaction1이 동작할 수도 있습니다.

schedule2. r2(B)-w2(B)-commit2-r1(A)-w1(A)-r1(B)-w1(B)-commit1

또한, transaction1이 동작하는 중간에 transaction2가 겹쳐서 동작할 수도 있습니다. 이를 interleaving이라고 합니다.

schedule3. r1(A)-w1(A)-r2(B)-w2(B)-commit2-r1(B)-w1(B)-commit1

schedule4. r1(A)-w1(A)-r1(B)-r2(B)-w2(B)-commit2-w1(B)-commit1

• 여기서 transaction을 수행하는 각 작업들 하나하나(sql문)를 operation이라고 부르며, 여러 transaction들이 동시에 실행될 때 각 transaction에 속한 operation들의 실행 순서를 scehdule이라고 합니다.
• 또한 각 transaction 내의 operation들의 순서는 바뀌지 않습니다.

즉 여러 transaction들이 동시에 실행될 때 operation들의 실행 순서가 schedule이지만 한 transaction을 수행하기 위해 동작해야하는 operation들의 순서는 어떤 case를 살펴보아도 바뀌지 않는다는 것입니다.

위에서 나열한 케이스들은 예로 든 것 뿐이고 위 예시의 schedule들 말고 더 많은 schedule이 존재합니다.

Serial schedule, Nonserial schedule

schedule1과 2를 살펴봅시다.

각 transaction들이 겹치지 않고 수행되고 있습니다.

이렇게 transaction들이 겹치지 않고 한 번에 하나씩 실행되는 schedule을 serial schedule이라고 부릅니다.

schedule3과 4를 살펴봅시다.

transaction들이 겹쳐서 실행되고 있습니다.

이렇게 transaction들이 겹쳐서(interleaving) 실행되는 schedule을 non-serial schedule이라고 합니다.

Nonserial schedule vs serial schedule

Nonserial schedule은 transaction들이 겹쳐서 실행되기 때문에 동시성이 높아져서 같은 시간 동안 더 많은 transaction들을 처리할 수 있습니다.

Nonserial schedule의 단점

Nonserial schedule의 단점은 transaction들이 겹쳐서 실행되기 때문에 어떻게 실행되는지에 따라 의도하지 않은 결과가 발생할 수 있습니다.

schedule3은 Nonserial schedule이지만 우리가 의도한 결과가 잘 나옵니다.

하지만 schedule4를 살펴봅시다.

r1(A)-w1(A)-r1(B)-r2(B)-w2(B)-commit2-w1(B)-commit1

transaction1
A의 계좌를 읽습니다.(A 계좌 100만원)
A의 계좌에서 20만원을 뺍니다(A 계좌 80만원)
B의 계좌를 읽습니다.(B 계좌 200만원)
	transaction2
    B의 계좌를 읽습니다.(B 계좌 200만원)
    B의 계좌에 30만원을 더합니다.(B 계좌 230만원)
    commit
B의 계좌에 20만원을 더합니다(B 계좌 220만원)
commit

정상적으로 수행되어 우리가 기대한 결과는 B의 계좌에 250만원이 있어야 하는데 220만원만 있는 상황입니다.

transaction2에서 B의 계좌에 업데이트한 내용이 사라졌습니다.

• 이를 lost update 현상이라고 합니다.

어떻게 해야 할까?

성능을 고려하면 여러 transaction을 겹쳐서 실행해서 같은 시간동안 더 많은 transaction을 처리할 수 있는 nonserial schedule을 실행하고 싶은데,

아까와 같이 우리가 기대한 결과가 아닌 의도하지 않은 이상한 결과가 나오는 것은 안됩니다.

그래서 nonserial schedule로 실행해도 이상한 결과가 나오지 않는 방법을 찾다가,

serial schedule은 이상한 결과를 만들지 않으니까 serial schedule과 equivalent한 nonserial schedule을 실행하기로 하였습니다.

그래서 이제 nonserial schedule이지만 serial schedule과 equivalent함을 정의하는 방법이 필요해졌습니다.

Serializability

conflict of two operations

두 schedule이 equivalent 함을 정의하기 위해서 우선 conflict라는 개념을 알아야 합니다.

confilct of two operation은
1. 두 operation은 서로 다른 transaction에서 수행되는 작업이며
2. 같은 데이터에 접근해야 하고
3. 적어도 하나는 write operation이어야 합니다.

두 operation이 세 가지 조건을 만족하면 두 operation이 conflict하다고 말할 수 있습니다.

schedule3. r1(A)-w1(A)-r2(B)-w2(B)-commit2-r1(B)-w1(B)-commit1

r2(B)와 w1(B)를 살펴봅시다.

transaction2에서 B의 계좌를 읽는 operation
transaction1에서 B의 계좌를 쓰는 operation

이렇게 봤을 때 두 operation은 서로 다른 트랜잭션 소속이며, B의 계좌라는 같은 데이터에 접근하고, 최소 하나의 operation이 쓰기 작업입니다.

따라서 두 operation은 conflict하다고 할 수 있습니다. 그리고 이렇게 하나는 읽고, 하나는 쓰는 이런 형태의 conflict를 read-write conflict라고 말합니다.

w2(B)와 r1(B)도 마찬가지로 read-write conflict입니다.

w2(B)와 w1(B)도 conflict입니다. 이런 conflict는 write-write conflict라고 부릅니다.

그래서 이렇게 schedule3에는 세 개의 conflict가 존재합니다.

conflict가 왜 중요할까

• conflict가 중요한 이유는 conflict operation은 그 실행 순서가 바뀌면 결과도 바뀌기 때문이며 이 conflict를 가지고 conflict equivalent를 정의할 수 있기 때문입니다.

w2(B)과 r1(B) conflict를 살펴봅시다.

이 순서로 operation이 실행되면 w2(B)는 B의 계좌에 230만원을 쓰고, r1(B)는 B의 계좌 230만원을 읽습니다.

하지만 이 두 operation의 순서가 바뀐다면 어떻게 될까요?

r1(B)는 B의 계좌 200만원을 읽고 w2(B) B의 계좌에 230만원을 씁니다.

아까 r1(B)의 결과는 230만원 이었는데 이번에는 r1(B)의 결과가 200만원입니다.

지금까지 이 이야기를 한 이유가 nonseiral schedule이지만 serial schedule과 동일함을 정의하는 방법을 이야기하고 싶어서 였습니다.

이 conflict를 가지고 conflict equivalent를 정의함으로써 두 schedule이 동일하다고 말할 수 있습니다.

conflict equivalent for two schedules

conflict equivalent는 다음과 같은 조건을 만족하면 conflict equivalent라고 합니다.

1. 비교하는 두 schedule이 같은 transaction들을 가지고 있다.
2. 어떤 conflict operation의 순서도 양쪽 schedule 모두 동일하다.

그러니까 비교하는 schedule A와 B를 살펴보았을 때,

schedule A에 등장하는 conflict operation 하나를 잡았을 때, 그 operation의 순서가

schedule B에도 동일하게 나타나는 conflict operation이어야 합니다.

그런데 "어떤" 이라고 했으니까 임의로 conflict operation을 잡았을 때 양쪽 schedule에서 동일하게 나타나야 하니까 양쪽 모두 동일한 conflict operation을 가지고 있어야 합니다.

• 그래서 해당 조건을 만족하는 두 schedule을 conflict equivalent하다고 말합니다.
• 그리고 nonserial schedule이 serial schedule과 conflict equivalent할 때 이 nonserial schedule을 Conflict serializable하다고 말합니다

아까 schedule 3번은 interleaving으로 실행되는 nonserial schedule이지만 우리가 의도한 결과가 나오는 scehdule이라고 말했습니다.

schedule 3은 nonserial schedule이지만 serial schedule인 schedule 2와 conflict equivalent하기 때문에 conflict serializable하며, 그렇기 때문에 schedule3은 interleaving schedule이지만 정상적인 결과를 반환하는 schedule인 것이었습니다.

schedule 4는 정상적인 결과를 반환하지 않는 nonserial schedule이었습니다.

그 이유는 schedule 4와 serial schedule인 schedule 2를 비교했을 때 conflict equivalent하지 않습니다.

하지만 아직 schedule 1이 남아있죠. 그래서 schedule 1과도 비교했지만 conflict equivalent하지 않습니다.

따라서 nonserial schedule인 schedule 4는 그 어떤 serial schedule과도 conflict serilizable하지 않아서 정상적인 결과를 내지 못하는 schedule이었던 것입니다.

정리

우리는 transaction 처리를 할 때 성능적인 관점에서 여러 transaction들을 겹쳐서 실행하면 좋으니까 nonserial schedule로 처리하고 싶습니다.

하지만 지금까지 살펴보았듯이 nonserial schedule은 정상적이지 않은 결과를 냅니다.

우리는 정상적인 결과만 나오길 원합니다.

따라서 serial schedule과 conflict serializable한 nonserial schedule은 실행할 수 있도록 허용하도록 하자는 것입니다.

이걸 DBMS가 구현하는 가장 간단한 방법은 여러 transaction이 실행할 때마다 이 schedule이 conflict serializable 한지 확인하는 것입니다.

하지만 DBMS가 구현하는 방식은 이게 아니고

여러 transaction들을 동시에 실행해도 schedule이 conflict serializable하도록 보장하는 프로토콜을 적용하여 구현합니다.

아예 conflict serializable한 schedule만 실행될 수 있도록 보장하는 프로토콜을 적용하는 것입니다.

serializable

어떤 schedule A(serial이든 nonserial이든)가 있고 이 schedule이 다른 임의의 serial schedule과 equivalent하다면 "schedule A는 serializable" 하다고 말합니다.

혹은 "schedule A 가 serializability 속성을 가진다" 라고 말합니다.

그런데 이 equivalent(동일한)함을 정의할 수 있는 방법이 바로 conflict equivalent였습니다.

schedule A가 어떤 serial schedule과 conflict equivalent하다면 "schedule A는 conflict serializable하다 혹은 conflict serializability속성을 가진다" 라고 말합니다.

이 개념 말고 view equivalent도 존재합니다. 말하는 것은 위와 같습니다.

concurrency control

그 어떠한 schedule도 serializable 하도록 만드는 역할을 하는 것이 바로 concurrency control입니다.

그리고 이 concurrency control과 아주 밀접한 관련이 있는 transaction 속성이 Isolation입니다.

하지만 이 Isolation 수준을 너무 엄격하게 하여 serializablity를 완벽하게 추구하면 성능이 떨어집니다. 제약이 많아져 동시성이 떨어지기 때문입니다.

그래서 완화된 isolation도 제공을 하게 되었고 이 완화된 isolation 종류를 isolation level이라고 하며, 개발자들이 필요에 따라 isolation level을 선택할 수 있도록 하였습니다.