Concurrency Control (1) - Schedule(feat. Serializability, Recoverability)

들어가며

DB 동시성 제어는 분량이 꽤 많을 것 같아 4편으로 나누어 작성하려고 한다.

이번엔 DB 동시성 제어 이해에 필요한 Schedule에 대해 정리할 것이다.

 

Schedule

Schedule이란 여러 트랜잭션들이 동시에 실행될 때 각 트랜잭션에 속한 operation의 실행 순서를 의미한다.

 

Lost Update

다음처럼 H와 K의 계좌 잔액을 조회하거나 변경하는 등의 작업을 수행하는 2개의 트랜잭션이 존재한다고 생각해 보자.

해당 케이스에서 Tx2가 실행되고 나서 Tx1은 이 사실을 알지 못한 채 H의 계좌 잔액을 220만 원으로 변경한다. 이때 Tx2의 변경사항은 유실되어 버리는데 이를 Lost Update라고 한다.

 

Serial Schedule, Non-Serial Schedule

먼저 봤던 케이스를 간소화하고 operation의 위치를 바꾸는 식으로 다음 그림처럼 케이스를 나눌 수 있다.

여기서 각 트랜잭션 내에 있는 operation끼리는 순서가 바뀌지 않는다.

여기서 case4처럼 트랜잭션이 서로 겹치지 않고 한 번에 하나씩만 실행될 경우 이 스케줄을 Serial Schedule이라고 한다.

물론 두 트랜잭션끼리 순서를 뒤바꾼 경우도 존재할 수 있을 것이다.

 

그리고 case1, 2, 3은 Non-Serial Schedule이라고 한다. 

 

SS는 한 번에 하나의 트랜잭션만 실행되기 때문에 성능이 낮은 반면, NS는 상대적으로 더 많은 트랜잭션을 처리할 수 있다.

 

Non-Serial Schedule 문제점

NS는 처음에 봤던 케이스, 그러니까 case1 같은 경우 실행되는 순서 때문에 Lost Update 현상이 발생해 의도와는 다른 결과가 발생할 수 있다는 문제점을 안고 있다.

 

당연히 사람들은 성능이 더 좋으면서도 동일한 결과를 도출하는 NS를 사용하고 싶었을 테고, 이상한 결과가 나오지 않도록 하는 방법을 연구하다가 SS와 Conflict Equivalent한 NS를 실행하면 문제가 없다는 점을 발견했다.

 

Conflict

두 operation이 다음 3가지 조건을 모두 만족할 때 Conflict라고 한다.

 

1. 서로 다른 Tx에 소속되어 있다.

2. 같은 데이터에 접근한다.

3. 적어도 둘 중 하나는 write operation이어야 한다.

 

Conflict한 operation끼리는 순서를 뒤바꾸면 결과가 달라진다는 특징을 갖고 있다.

 

Conflict Equivalent

두 schedule이 다음 2가지 조건을 모두 만족할 때 Conflict Equivalent하다고 한다.

 

1. 두 schedule은 같은 트랜잭션을 가지고 있다.

2. Conflict가 발생한 operation들의 순서는 두 schedule 모두 동일하다.(s1에서 r1-w1의 순서라면 s2에서도 r1-w1의 순서라는 의미이다.)

 

Conflict Serializable

어떤 스케줄과 SS와 Conflict Equivalent할 때 이 상태를 Conflict Serializable라고 한다.

해당 스케줄이 NS라면 NS이면서도 SS와 동일한 결과를 도출한다는 것을 보장할 수 있는 것이다.

 

결론

DBMS에서는 여러 트랜잭션을 동시에 실행해도 스케줄이 Conflict Serializable하도록 보장하는 프로토콜을 사용하는데, 이 부분은 다음 편에서 알아보자.

 

Unrecoverable Schedule

위 그림처럼 스케줄 내에서 commit된 Tx가 rollback된 Tx가 write했었던 데이터를 조회할 경우 해당 스케줄을 Unrecoverable Schedule이라고 한다.

이러한 스케줄을 rollback 하더라도 원래 상태로 회복이 불가능할 수도 있으므로 DBMS 차원에서 막아야 한다.

 

Recoverable Schedule(Cascading Rollback)

이번에는 위 그림처럼 스케줄 내에서 어떤 Tx도 자신이 읽은 데이터를 write한 Tx가 먼저 commit 되거나 rollback되기 전까지는 commit하지 않는 경우 해당 스케줄을 Recoverable Schedule이라고 한다.

그리고 DBMS는 원래 상태로 회복 가능한 이런 스케줄만 허용해야 할 것이다.

 

이 스케줄에서 rollback을 하게 되면 원래 상태로 돌아가기 위해 연쇄적으로 rollback이 발생해야 하므로 이를 cascading rollback이라고도 한다. 다만 cascading rollback은 비용이 많이 소모되므로 방금 전보다는 아래와 같은 형태의 스케줄만 허용하는 게 더 효율적이다.

 

Cascadeless Schedule(avoid Cascading Rollback)

스케줄 내에서 어떤 Tx도 commit이 되지 않은 Tx들이 write한 데이터를 read 하지 않는 경우를 말한다.

 

Strict Schedule

다음 그림은 Cascadeless Schedule이라고 할 수 있으나 Lost Update가 발생할 수 있다.

 

그래서 Cascadeless Schedule에 기존 정의에 write 조건도 추가하여, 

스케줄 내에서 어떤 Tx도 commit이 되지 않은 Tx들이 write한 데이터를 read 하지도, write 하지도 않는 스케줄을 Strict Schedule이라고 한다.