동시성 제어(Concurrency Control) 기초 (1) Schedule과 Serializability

쉬운 코드 채널의 Youtube 영상을 보고 정리한 내용입니다.
(1부) concurrency control 기초 : schedule과 serializability. 트랜잭션들이 동시에 실행될 때 isolation을 보장하는 기초 이론

 

Schedule

• 여러 transaction들이 동시에 실행될 때 각 transaction에 속한 operation들의 실행 순서

• 여러 transaction들이 동시에 실행된다면, 시간적 순서를 일종의 '줄'이라고 했을 때 서로 다른 transaction에 속한 operation(예를 들면 한 transaction 내의 쓰기 작업)이 섞여서 줄 서 있을 수 있다.
• 이렇게 여러 transaction들이 동시에 실행될 때, 각 operation이 어떤 순서로 실행되는지를 설명하는 것이 schedule 이다.
• 단, 각 transaction 내의 operation들의 순서는 바뀌지 않는다 !!

Serial Schedule

• transaction들이 겹치지 않고 한 번에 하나씩 실행되는 schedule
• CPU가 놀고 있는 시간(ex. transaction이 I/O 작업을 하는 시간)이 많아서 성능이 떨어진다.

Nonserial Schedule

• 서로 다른 transaction들을 겹쳐 실행되는 shedule
• 실행한 transaction이 I/O 작업을 하는 동안, 다른 transaction의 작업을 할 수 있다.
• 동시성이 높아져서 같은 시간 동안 더 많은 transaction들을 처리할 수 있다.
• 하지만, 동시성으로 인한 이슈를 주의해야 한다. transaction들이 어떻게 중첩되느냐에 따라 이상한 결과를 초래할 수 있다.
  • 예를 들면 동일한 계좌에 대한 서로 다른 쓰기 작업을 둘 다 처리하면서, 한 쪽의 업데이트가 누락될 수 있다. (Lost Update)

그렇다면 Nonseriable schedule로 성능을 챙기면서, 이상한 결과가 나오지 않으려면 어떻게 해야 할까?
이상한 결과를 피하기 위해서 Conflict라는 개념을 알고 가자.

 

Conflict의 정의

두 개의 operation에 대해 사용하는 개념. 아래 세가지 조건을 만족하는 경우를 말한다.

1. 두 operation이 서로 다른 transaction 소속

2. 두 operation이 같은 데이터에 접근
3. 두 operation 중 최소 하나는 write operation이다.

즉, 서로 다른 transaction 소속의 두 operation에 대해서, 같은 데이터에 대해 쓰기 동작이 중첩되면 문제가 발생한다.

종류로는 read-write / read-write / write-write 연산 세 가지가 존재할 것이다.

 

이러한 Conflict operation은 순서가 바뀌면 결과도 바뀐다.

예를 들면 아래와 같은 두 동작의 순서에 따라 결과는 달라진다.
A. 계좌에 1000원 입금 / B. 계좌 잔액 조회

그래서 NonSeriable Schedule에서 Conflict가 중요한 것이다.

Conflict Equivalent

두 개의 schedule에 대해, 두 조건을 만족하면 Conflict Equivalent 한 것이다.

1. 두 schedule은 같은 transaction을 가진다.
2. 어떤 conflicting operations의 순서(write-read / read-write / write-write )도 양쪽 schedule 모두 동일하다.

ex) 두 schedule의 세 가지 Conflict를 확인 했을 때, 모두 아래와 같이 같은 순서를 가지는 경우
(1) write-read Conflict : 항상 A 트랜잭션의 쓰기를 먼저 하고, 이후 B 트랜잭션의 읽기를 한다.
(2) read-write Conflict : 항상 A 트랜잭션의 쓰기를 먼저 하고, 이후 B 트랜잭션의 읽기를 한다.
(3) write-write Conflict : 항상 A 트랜잭션의 쓰기를 먼저 하고, 이후 B 트랜잭션의 쓰기를 한다.

 

이미지 출처: youtube 쉬운코드

NonSerial Schedule이 Serial Schedule과 Conflict Equivalent하면, Conflict Serializable 해 정상적인 결과를 낼 수 있다.

그러니 Conflict Serializable한 NonSerial Schedule을 쓰면, 성능을 지키면서 믿고 쓸 수 있다.

왜?

Serial Schedule은 트랜잭션 내의 실행 순서와 schedule 에서의 operation 실행 순서가 동일하다.  
그런데 NonSerial Schedule이 Conflict Equivalent 하다면,
서로 다른 트랜잭션의 operation이 중첩되어 있어도 실제로 같은 데이터에 접근하는 두 operation의 순서는 보장되기 때문인 것 같다.

스케줄마다 어느 트랜잭션이 write를 먼저 하는지가 달라지면, 결과가 달라지기 때문이다.

여러 Serial Schedule 중 하나라도 Conflict Equivalent 하면 된다. 하지만 어떤 것과도 동일하지 않다면 Serializable할 수 없다.

💭 이 때 비교하는 이 모든 Serial Schedule은 어디서 오는거지? 가능한 경우의 수?

 

실제로 RDBMS에서 어떻게 구현하나?

실제 구현 방식으로는, 동시에 실행될 수 있는 Transaction을 통해 가능한 schedule의 serializablity를 확인할 것 같지만 그렇지 않다. (아마도 너무 경우의 수가 많으니까.. 비용 문제일 듯)

대신, 여러 transaction을 동시에 실행해도, shedule의 conflict serializable 하도록 보장하는 프로토콜을 적용한다.

 

정리

어떤 schedule이 어떤 serial schedule과 동일(equivalent)하면, 이에 대해 serializable 하다고 할 수 있는데,

이 '동일성'을 정의하는 방법 중 하나가 Conflict Equivalent이다.

Conflict Equivalent는 Scheudle의 동일성을 정의하는 방법 중 하나이고, 이 동일성을 만족하면 Conflict Serializable 이라고 하는 것이다.

View Equivalent를 만족한다면, View Serializability를 가진다.

이런 경우를 Seriailizable Schedule 이라고 한다.

더 나아가보기

어떤 schedule도 serializable하게 만들어주는 역할을 하는 것이 Concurrency Control이다.

이 때, 밀접하게 관련된 속성으로 Transaction ACID 중 Isolation 이 있다.

Isolation의 완벽한 추구와 성능은 트레이드 오프이므로 이에 대해 적절히 완화된 것을 제공할 수 있다. -> Isolation level

---

질문해보기

1. 내가 모르는 키워드 : Conflict Serializable

Conflict Equivalent 하면 Conflict Serializable 하고, 이상한 결과를 받지 않을 수 있는 이유가 내가 이해한 게 맞는지?
세 Conflict의 순서가 모두 같으면, 같은 데이터에 대해 중복된 쓰기를 하기 전에 조회를 할 것이므로 이상한 동작이 벌어지지 않는다.

2. 이걸 공부해서 나누고 싶은 키워드 : 

NonSerial Schedule 쪽의 Conflict 순서를 확인할 때, 두 operation 사이에 commit이 이루어지지 않는 건 상관 없는지?
-> 이 부분에서 격리 수준과 연관성이 있는걸까? 격리 수준에 따라 상관이 있을 수도 있나?
NonSerial Schedule이지만 Conflict Serializable하다면, 트랜잭션 격리 수준이 꼭 SERIALIZABLE이 아니어도 된다. Conflict Serializable은 트랜잭션 스케줄의 성질을 나타내는 것이며, 스케줄이 Conflict Serializable하다는 것은 해당 스케줄을 Serial Schedule로 변환할 수 있다는 의미이기 때문이다.
격리 수준과 상관 없이, 해당 스케줄로 Serial Schedule'처럼' 결과를 얻을 수 있음을 의미한다.
https://tecoble.techcourse.co.kr/post/2022-11-07-mysql-isolation/

3. 알고 가야 하는 키워드 : Transaction Schedule

데이터베이스의 일관적인 상태를 유지하기 위해서 동시에 실행되는 트랜잭션들의 연산 순서를 정하는 것