[데이터 베이스] 트랜잭션 시리즈 #3 : Serializability and Recoverability (cascadeless? strict?)

Serializabiltiy와 Recoverability는 여러개의 트랜잭션을 동시에 실행할 때, 데이터에 이상 현상이 발생하지 않도록 보장해야 하는 특성들이다. 이 개념을 익히고 트랜잭션 개념을 공부해야 용어들이 익숙하고 이해가 쉽다. 한번 드루가보자.

 

Serializability란?

DBMS는 여러 사용자들의 요청을 처리할 때 성능을 위해 요청을 동시에 수행하는게 필수적이다. 하지만 이렇게 동시에 요청을 처리하면서도 트랜잭션간의 간섭이 일어나지 않은 것처럼 데이터를 처리하기 위한 방법이 필요하다. 이를 데이터베이스의 Isolation을 보장한다고 표현하는데, 이를 다르게 표현하면 Seralizability가 보장됐다고 표현할 수 있다. 다시 말해 여러 트랜잭션들이 동시에 실행된다고 하더라도, 마치 순차적으로 실행된 것처럼 실행결과가 보장되는 상태를 serializability라고 표현한다. 따라서 본 글에서는 serializability가 데이터베이스의 동작에서 어떤식으로 보장될 수 있는지, 그리고 serializability가 보장된다는 것이 어떤 의미인지에 대해 구체적으로 알아보려고한다. 그 전에 알아둘어야 할 기본적인 용어들을 먼저 알아보자.

 

Schedule

Schedule이란 다수의 트랜잭션이 동시에 실행될 때 그 트랜잭션들에 속한 oepration들의 실행 순서를 의미한다. 예를 들어 T1, T2, T3 세개의 트랜잭션이 동시에 실행될때, 이들이 순차적으로 실행되는게 아니라 동시에 실행되면서 내부의 operation들이 겹쳐서 실행될 때 어떻게 실행되냐에 따라 실행결과가 다르게 나타날 수 있다. 따라서 DBMS에서는 스케줄을 serial schedule, non-serial schedule 두 가지로 구분한다.

 

Serial schedule

여러 트랜잭션 요청이 들어와도 각 트랜잭션 별로 구분해서 트랜잭션들이 겹치지 않고 한 트랜잭션이 모두 실행되고 나면 다른 트랜잭션을 실행하는 스케줄을 의미한다.

serial schedule의 장점은 트랜잭션들의 serializability를 완벽하게 보장할 수 있다는 점이다.

반대로 serial schedule의 가장 큰 단점은 바로 성능이다. 예를들어 각 operation들이 디스크 I/O가 필요한 경우라면, 트랜잭션이 끝날 때까지 다른 트랜잭션을 실행할 수 없기 때문에 모든 트랜잭션들이 CPU보다 훨씬 느린 I/O작업을 끝날 때까지 기다려야 한다. 따라서 성능 이슈때문에 현실적으로 serial schedule은 사용되지 않는다.

 

Non-serial schedule

Interleave 실행기법을 통해 트랜잭션 내부의 연산들이 번갈아가면서 병렬로 실행되는 스케줄을 의미한다. 동시성이 높아지기 때문에 다른 트랜잭션이 I/O작업 등 시간이 소요되는 작업을 수행하는 동안 다른 operation을 수행할 수 있기 때문에 serial schedule보다 같은 시간 내에 더 많은 트랜잭션을 처리할 수 있다.

하지만 non-serial schedule의 문제는 serializability를 보장할 수 없다는 치명적인 단점이 있다. 트랜잭션 내 operation들이 interleaving하게 병렬적으로 처리되게 되면 의도하지 않았던 결과가 나타날 수 있다.

 

Serializable schedule

serial schedule과 non-serial schedule은 서로 매우 치명적인 trade-off가 있다. 이를 해결하기 위해 나온 스케줄이 바로 serializable schedule이다. 성능을 개선하기 위해 non serial schedule을 사용하면서도 직렬 스케줄과 이용한 ‘동일한’ 결과가 나올 수 있도록 하는 스케줄을 의미한다. 이를 conflict serializable 혹은 serial schedule과 conflict equivalent하다 표현하고, 이를 이해하기 위해서는 우선 conflict라는 개념을 알아야 한다.

 

Conflict

conflict는 두 개의 operation(트랜잭션 아님)이 충돌한다는 것을 의미한다. 여기서 말하는 충돌은 아래 세가지 조건을 충족하는 경우를 의미한다.

(1) operation이 서로 다른 트랜잭션에 속해 있는 경우

(2) operation이 같은 데이터에 작업하는 경우

(3) 둘 중 하나의 operation이 쓰기 작업을 하는 경우

 

예를 들어보자

 

(R1(A), W2(A)) = read-write conflict

• 같은 데이터인 A에 대한 작업이고 하나가 write임

(R1(A), W2(A)) = write-write conflict

• 같은 데이터 A에 대해 둘 다 write함

(R1(A), W2(B)) = non conflicting

• Read는 A에 대한 작업이고, W는 B에 대한 작업임

이렇게 conflict를 정의한 이유는, 두 개의 트랜잭션이 동시에 처리될때, 이 conflict가 있는 operation들의 실행 순서가 바뀌면 실행 결과가 바뀌기 때문이다.

conflict equivalent

앞서 서로 다른 트랜잭션들에 대해 non serial schedule로 operation들이 수행되도 직렬 스케줄과 ‘동일한’결과가 나온다는 것을 serial schedule과 conflict equivalent하다고 표현했다. 그리고 여기서 conflict equivalent 하다는 것은 아래 조건을 만족해야 한다

(1) 같은 트랜잭션들의 operation들로 구성된 schedule이다.

(2) 양쪽 트랜잭션 내의 conflicting operation들의 실행 순서가 동일하다

 

예를 들어보자. 참고로 R1에서 R= read, 1은 트랜잭션 1번에서 실행된 것을 의미한다. W도 마찬가지다.

S1: R1(A), W1(A), R2(A), W2(A), R1(B), W1(B), R2(B), W2(B)
S11: R1(A), W1(A), R1(B), W2(A), R2(A), W1(B), R2(B), W2(B)

두개의 스케줄은 conflict equivalent하다고 표현할 수 있다.

먼저 S1의 conflict operation들의 실행순서를 먼저 알아보자

데이터 A에 대한 conflict operations 실행 순서

• R1(A) → W2(A)
• W1(A) → R2(A)
• W1(A) → W2(A)

데이터 B에 대한 conflict operations 실행 순서

• R1(B) → W2(B)
• W1(B) → R2(B)
• W1(B) → W2(B)

 

하나하나 비교해보면 non-conflict operation인 R2(A)와 R1(B)의 순서만 바뀌었고, conflict operation들의 순서는 그대로다. 따라서 위와 같은 경우는 conflict equivalent하다고 표현한다.

 

그리고 만약 non-serial 스케줄이 serial schedule과 conflict equivalent하면 두 개의 스케줄의 결과는 동일하게 된다. 그리고 이러한 non-serial schedule을 conflict serializable 혹은 conflict serializability의 속성을 가진다고 표현한다. 사실 Serializable 스케줄에는 View Serializable이라는 개념도 있는데, 이번에는 다루지 않고 나중에 별도의 글로 다루도록 하겠다.

 

serializability 정리

자 그럼 이제 우리는 non-serial 스케줄로 실행하더라도 serial schedule과 conflict equivalent한 스케줄만 실행하도록 하면 serialiazability를 보장하면서도 serial schedule보다는 훨씬 성능높게(동시성 있게) 여러 트랜잭션들을 처리할 수 있을 것이다. 따라서 DBMS는 여러 트랜잭션들이 동시에 실행되더라도 serializable schedule로 실행될 수 있도록 할 수 있는 프로토콜을 사용해 serializability를 보장하고 이러한 방법을 concurrency control이라고 표현한다. concurrency control에는 여러 가지 방법이 있고 이는 추후 다른 글에서 다룰 예정이다. 이 글에서는 serializability가 무엇인지, 그리고 serializable schedule이 무엇인지에 대해서만 이해하고 넘어가도록 하자. 이어서 concurrency control에서 serializability말고 보장해야 하는 또 다른 특성인 recoverability에 대해 알아보자.

 

Recoverability

앞서 serializability는 데이터베이스의 concurrent execution에서 serial schedule과 conflict equivalent한 결과를 보장하는 것을 의미했다. 이와 더불어 한 가지 더 알아두어야 할 개념은 recoverability다.

recoverability는 트랜잭션이 실패했을때의 회복 가능성을 의미한다. 트랜잭션은 hardware failure, system crash, 소프트웨어 이슈 등 다양한 이유로 중간에 실패할 수 있다. 이때에도 트랜잭션은 atomicity가 보장되어야 하기 때문에 트랜잭션이 실패하면 트랜잭션 이전 상태로 복원될 수 있어야 한다. 이를 롤백한다고 표현하는데 이때 이상현상 없이 데이터를 복원할 수 있는 것을 recoverable하다고 표현한다. 따라서 DBMS는 스케줄이 recoverable하도록 보장해야 하며, recoverable한 스케줄이 무엇인지에 대해 한번 알아보자.

irrecoverable schedule

irrecoverable schedule이란 롤백을 해도 이전 상태로 회복 불가능한 스케줄을 의미한다. 이러한 스케줄은 DBMS에서는 허용하면 안되기 때문에 어떠한 경우에 스케줄이 irrecoverable할 수 있는지 알아보자.

 

irrecoverable한 스케줄은 아래와 같이 Dirty Read가 있는 경우다.

Dirty read란 위 케이스처럼 T1 트랜잭션의 작업이 다 끝나지 않았는데, T2에서 트랜잭션에서 작업 내용을 보는 경우를 의미한다. 위 예시를 보면 T2가 T1이 아직 완료되기전에 T1이 write한 A의 값을 읽고 작업을 수행했으나, T1이 중간에 실패를 해 롤백을 하게되면 T2는 유효하지 않은 데이터를 읽는 경우, 즉 Dirty Data를 가지게 되는 경우를 의미한다. 하지만 T2는 이미 커밋을 했기 때문에 유효하지 않은 데이터로 작업된 트랜잭션임에도 불구하고 롤백을 할 수 없는 상태가 돼 이런 경우를 irrecoverable schedule이라고 표현한다.

 

recoverable schedule

recoverable schedule이란 트랜잭션은 자신이 읽고 있는 데이터를 변경하고 있는 다른 트랜잭션들이 모두 커밋 혹은 롤백이 되기 전까지는 커밋하지 않는 스케줄을 의미한다. 다르게 표현하면 T1이 T2가 변경하거나 쓰고 있는 값을 읽고 있다면 T2가 커밋된 후에야 T1이 커밋할 수 있는 경우를 의미한다.

 

예를 들어보자

위와 같은 경우는 T1이 T2전에 커밋이 됐기 때문에 T2가 읽은 데이터가 유효한게 되고 따라서 recoverable하다. 하지만 이런 경우 하나의 트랜잭션 실패가 일련의 트랜잭션의 rollback을 양상할 수 있고, 이를 cascading rollback이라고 표현한다. 하지만 이렇게 cascading rollback으로 인해 여러 트랜잭션이 연쇄적으로 실패하게 되면 처리하는 비용이 크다. 따라서 이를 방지하는 스케줄을 cascadeless schedule이라고 한다.

 

cascadeless schedule

cascadeless schedule이란 데이터를 write한 트랜잭션이 커밋 혹은 롤백이 된 뒤에만 데이터를 읽을 수 있는 스케줄을 의미한다. 예를 들면 아래와 같다.

 

T2는 T1원이 커밋된 뒤에 A의 값을 읽고 있다.

또 다른 예로 만약 T1이 커밋전에 Fail했을 때, 아직 T2가 T1이 실패하기 전까지는 A를 읽지 않은 상태였다면 T2를 롤백할 필요가 없다. 이렇게 commit 되지않은 트랜잭션이 write한 데이터는 읽지 않는 스케줄을 cascadeless schedule이라고 표현한다.

 

strict schedule

하지만 cascadeless schedule은 read를 하지 않는 스케줄이고, write까지 막지는 않는다. 만약 아래와 같이

W1(A) → W2(A) → W2 Commit → W1 rollback

같은 순으로 스케줄이 진행됐다면, W1이 롤백하면서 W1이 발생하기 전의 데이터로 복구되면서 W2가 커밋한 데이터가 사라지는 경우가 발생할 수 있다. 하지만 위 스케줄은 read 자체가 없기 때문에 cascadeless하다고 볼 수 있다. 따라서 여기에 추가적으로 보강해 읽지도 않을 뿐 아니라 쓰지도 못하게 하는 경우를 strict schedule이라고 표현한다. 위와 같은 strict schedule은 롤백할 때 recovery가 쉽다.

 

Recoverability 정리

정리를 해보면 recoverable schedule이란 schedule중에 어떤 트랜잭션 T1이 write한 데이터를 또 다른 트랜잭션 T2가 read해야 한다면, write을 한 T1이 커밋되기 전까지는 read하지 않는 경우를 recoverable 스케줄이라고 한다. 그리고 이러한 스케줄을 recoverabilty 속성을 가지고 있다고 표현할 수 있다. 하지만 이러한 recoverable한 스케줄의 장점은 동시성이 떨어진다는 점이다. 트랜잭션이 커밋될 때까지 기다려야 하는 경우가 생기기 때문이다.

 

요약 정리

serializability와 recoverability는 여러 트랜잭션이 동시에 실행될 때 트랜잭션의 ACID특성을 어겨 데이터 정합성이 깨지는 문제를 미연에 방지하기 위해 보장돼야 한다.

 

serializability는 동시에 여러 트랜잭션이 실행될 때 serial schedule과 conflict equivalent한 상태, 즉 순차적으로 수행한 것과 같은 결과를 내는 것을 의미하고

 

recoverability란 트랜잭션이 실패하더라도 이상 현상 없이 데이터를 복원할 수 있는 상태를 의미한다.

 

그리고 위와 같이 serializability와 recoverability, 즉 ACID 원칙을 지키기 위한 기법을 concurrency control이라고 표현한다. 하지만 ACID원칙을 매우 엄격하게 지키기 위해서는 동시성을 희생해야 한다. 따라서 실제로 DBMS는 상황에 따라 개발자가 성능을 위해 ACID 원칙을 일부 희생해서 동시성을 얻을 수 있는 방법을 제공하는데, 그게 바로 Isolation level이다. 사실 고백하자면 Isolation level에 대해 공부하기전에 미리 알아두어야할 것은 concurrent 하게 트랜잭션이 실행됐을 때 발생할 수 있는 이상 현상들에 먼저 이해해야 한다.

 

Isolation level, 즉 격리 수준에 따라 이러한 isolation이 완전히 보장되지 못해 이상현상/문제들이 발생할 수 있고, 이들을 얼마나 제어하느냐에 따라 isolation level을 결정하기 때문이다. 따라서 본격적으로 concurrency control 기법들에 대해 알아보기 전에 다음 글에서는 이상현상들과 Isolation level에 대해 알아보도록 하겠다.

 

다시 한번 정리하면 concurrency control은 여러 트랜잭션이 동시에 실행될 때 serializability와 recoverability를 보장하기 위해, 다시말해 데이터 정합성을 보장하기위해 사용되는 기법들이다. 하지만 현실에서 성능 문제로 인해 일부 ACID한 특성을 희생하면서 동시성을 얻기 위해 Isolation level이라는 level을 조정해 serializability와 recoverability를 일부 희생하게 되는데, 이러한 isolation level을 조절해 격리 수준이 낮아지게 되면 트랜잭션이 동시에 실행되면서 발생할 수 있는 이상현상/문제점들이 발생하게 된다. 따라서 격리 수준을 조정하면서 발생할 수 있는 문제점들 그리고 이를 해결할 수 있는 Isolation level, 즉 격리 수준에 대해 공부해야 트랜잭션에 대해 어느정도 이해하고 내 상황에 적합한 Isolation level을 정할 수 있다. 그리고 이 Isolation level이 정해짐에 따라 트랜잭션의 동시성을 제어하는 여러 방법들이 있는데 이를 concurrency control이라고 표현하며, 대표적으로 2PL(two phase locking)그리고 MVCC가 있는데 이들에 대해 알아볼 예정이다.

 

 

 

참고 자료

https://www.geeksforgeeks.org/conflict-serializability-in-dbms/

https://www.gatevidyalay.com/recoverable-schedules-irrecoverable-schedules-non-serializable-schedules/

https://www.gatevidyalay.com/tag/serializability-and-recoverability-in-dbms/