동시성 제어를 위한 Serializability

 

목차

1. 트랜잭션 스케줄
2. Serial / Nonserial 스케줄
3. Serial / Nonserial 스케줄 성능 비교
4. Nonserial 스케줄의 문제점
5. Conflict serializable
6. Serializable 스케줄로 Nonserial 스케줄의 문제 해결

 

설명을 위해 예시

• 사용자 A의 계좌에는 100만원, 사용자 B의 계좌에는 200만원이 있다.
• 사용자 A는 사용자 B에게 20만원을 송금한다. 동시에 사용자 B는 자신의 계좌에 30만원을 예금한다. 

 

1. 트랜잭션 스케줄

• 여러 트랜잭션이 동시에 실행되는 경우에 각 트랜잭션에 속한 작업들의 실행 순서다. 
• 각 트랜잭션 내의 작업들의 순서는 바뀌지 않는다. 
• 여러 트랜잭션에 대해 스케줄은 수많은 조합이 나올 수 있다. 

트랜잭션 스케줄은 DB 동시성 제어 이론의 근간이고, 범용적인 DBMS는 conflict-serializable과 strict recoverable schedules를 채택한다. 

 

Schedule 1

사용자 A	잔고	사용자 B
read(A_balance)	100
write(B_balance)	80
read(B_balance)	200
write(B_balance)	220
	220	read(B_balance)
	250	write(B_balance)

 

 

Schedule 2

사용자 A	잔고	사용자 B
	200	read(B_balance)
	230	write(B_balance)
read(A_balance)	100
write(A_balance)	80
read(B_balance)	230
write(B_blance)	250

 

 

Schedule 3

사용자 A	잔고	사용자 B
read(A_balance)	100
write(A_balance)	80
	200	read(B_balance)
	230	write(B_balance)
read(B_balance)	230
write(B_balance)	250

 

Schedule 4

사용자 A	잔고	사용자 B
read(A_balance)	100
write(A_balance)	80
read(B_balance)	200
	200	read(B_balance)
	230	write(B_balance)
write(B_balance)	220

 

Schedule 4에서 Lost Update가 발생했다. 사용자 A의 read(B_balance) 작업과 write(B_balance) 작업 사이에 사용자 B의 read(B_balance) 작업이 실행됐고, 이로 인해 사용자 B의 업데이트 내용이 삭제되었다. 이에 대한 해결은 뒤에서 알아보자. 

 

 

2. Serial Schedule과 Nonserial Schedule

• Serial Schedule: 트랜잭션들이 겹치지 않고 실행되는 스케줄
• Nonserial Schedule: 트랜잭션들이 겹쳐서(interleaving) 실행되는 스케줄 

위 예시에서 Schedule 1, 2는 Serial Schedule이고, Schedule 3, 4는 Nonserial Schedule이다. 

 

 

3. Serial / Nonserial Schedule 성능 비교

Serial Schedule과 Nonserial Schedule 스케줄의 성능을 간단하게 비교해 보자.

 

Serial Schedule에서 여러 트랜잭션은 동시에 실행될 수 없다. 하나의 트랜잭션이 종료되어야 다음 트랜잭션이 실행된다. 한 트랜잭션은 read와 write 작업으로 구성되는데 이 작업들은 모두 물리 장치에서 데이터를 읽고 쓰는 I/O 작업이다. 하나의 작업이 실행될 때마다 시스템 I/O가 발생하고 CPU는 I/O 작업이 끝나길 기다린다. CPU가 아무 일도 하지 않고 놀기에 성능이 좋지 못하다. 

 

Nonserial Schedule에서는 여러 트랜잭션이 동시에 실행될 수 있다. 사용자 A의 트랜잭션의 어떤 작업이 실행되어 I/O를 기다리고 있을 때 CPU는 사용자 B의 트랜잭션을 처리할 수 있다. CPU가 놀지 않기 때문에 Serial Schedule과 비교하여 성능에 이점이 있다. 즉, 트랜잭션의 동시성이 높아져서 동일 시간 내에 더 많은 트랜잭션을 처리할 수 있다. 범용적인 DBMS라면 Nonserial Schedule를 선택한다. 

 

 

4. Nonserial Schedule의 문제점

하지만 Nonserial Schedule은 문제가 있다. 위 예시의 Schedule 4에서 Lost Update가 발생한 것을 확인했다. 이처럼 Nonserial Schedule는 여러 트랜잭션의 작업들 간의 순서를 보장하지 못하고, 잘못된 결과가 저장될 수 있다. 

 

 

5. Conflict serializable

• 어떤 Schedule이 Serial Schedule과 conflict equivalent하다면 Conflict serializable하다. 
• 즉, 연산 결과의 올바름을 보장하는 Serial Schedule과 conflict equivalent하면, 해당 Schedule의 연산 결과가 올바르다는 것을 보장한다. 
• 그리고 그것을 Conflict serializable라고 한다. 
• 어떤 Nonserial Schedule의 연산 결과가 올바르다는 것을 보장하기 위해 나온 개념이다. 

 

다음 개념을 차례로 이해하면 위 정의를 이해할 수 있다. 

 

Conflict

 

어떤 작업 2개가 다음 3가지 조건을 모두 만족하면 Conflict 작업이라고 한다. Conflict 작업은 작업 순서를 바꾸면 연산 결과가 바뀐다. 

1. 서로 다른 트랜잭션 소속
2. 같은 데이터에 접근
3. 최소 하나는 write operation

트랜잭션 A에서 사용자 B의 데이터에 read 연산을 실행하고 트랜잭션 B에서 사용자 B의 데이터에 write 연산을 실행하는 것이 예시이다. 

 

Conflict equivalent

 

어떤 트랜잭션 스케줄 2개가 다음 2가지 조건을 모두 만족하면 Conflict equivalent한 트랜잭션이라고 한다. 

1. 두 스케줄이 같은 트랜잭션을 가진다. 
2. 어떤 Conflict 작업의 순서가 양쪽 스케줄에서 동일하다. 

글로만 이해하기 어려운 개념이다. 이해가 안된다면 참고 자료를 보자. 

 

 

6. Serializable Schedule로 Nonserial 스케줄의 문제 해결

성능을 높이기 위해 여러 트랜잭션 처리의 동시성을 높이려 했다. Nonserial 스케줄로 해결할 수 있는데, 결과가 이상해지는 문제가 있었다. Serial 스케줄과 결과의 동일성을 보장하기 위해 Conflict serializable한 Nonserial 스케줄을 허용하기로 한다. Nonserial 스케줄 중 Conflict serializable한 스케줄을 Serializable Schedule이라고 한다. 

 

이것으로 문제가 완전히 해결되지 않는다. Conflict serializable하다는 것은 어떻게 알 수 있을까? 여러 트랜잭션이 동시에 실행할 때마다 연산할 것인가? 동시에 수많은 요청이 들어오면 현실적으로 어려울 것 같다. 실제 구현은 여러 트랜잭션이 들어왔을 때 Conflict serializable한 스케줄만 실행하는 것을 보장하는 프로토콜을 사용한다. 

 

여기까지 어떤 스케줄도 Serialzable하게 만드는 Concurrency Control의 기본 개념에 대해 알아보았다. 이것과 밀접한 관련이 있는 트랜잭션의 특징은 Isolation이다. Isolation을 너무 완벽히하면 성능에 저하가 있을 수 있다. 개발자에게 Isolation 정도를 조절할 수 있게 한 것이 Isolation Level이다. 

 

 

간단 요약

• 트랜잭션 스케줄은 여러 트랜잭션이 동시에 실행되는 경우에 각 트랜잭션에 속한 작업들의 실행 순서이다. 
• 트랜잭션을 순차적으로 실행하는 직렬 스케줄과 트랜잭션을 동시에 실행하는 비직렬 스케줄이 있다. 
• 비직렬 스케줄은 결과 오류가 발생할 수 있다.
• 결과적으로 직렬 스케줄과 동일한 비직렬 스케줄을 직렬 가능 스케줄이라고 한다. 
• DB Read, Write는 I/O 작업으로 CPU 사용이 적다.
• 동시성을 높이면 CPU를 효율적으로 사용하여 성능에 이점이 있다. 
• Isolation 레벨로 동시성 정도를 제어할 수 있다. 

 

참고 자료

https://en.wikipedia.org/wiki/Database_transaction_schedule

https://www.youtube.com/watch?v=DwRN24nWbEc