DB Concurrency Control - Schedule, Serializability, Recoverability

데이터베이스 공부 중 DB lock과 관련하여 이슈가 생겼음. 알고보니 concurrency control이라는 중요한 이슈와 관련되어 있는 것 같아 자료를 서치하고, 정리하고자 함. 많은 자료를 찾아본 결과 쉬운코드님의 강의가 concurrency control과 관련하여 가장 통합적이고 자세한 정보를 전달해주시는 것 같음

 

(1부) concurrency control 기초 : schedule과 serializability. 트랜잭션들이 동시에 실행될 때 isolation을 보장하는 기초 이론

(2부) concurrency control 기초 : recoverability. 트랜잭션들이 동시에 실행될 때 rollback이 발생하면 어떤 일이 벌어질까요?

 

---

우선 글의 결론부터!

=> DB에서 Concurrent Control은 Serializability와 Recoverability를 제공해야 한다

 

 

Schedule

여러 개의 트랜잭션이 concurrent하게 진행이 될 때 많은 문제가 발생함. 이 문제를 정확하게 정의하고 해결하기 위해 많은 개념과 이론이 등장. 이 중 Schedule은 여러 트랜잭션들이 동시에 실행될 때 각 트랜잭션에 속한 operation들(하나의 작업 - select, insert, update 등등)의 실행 순서를 나타내는 용어.

 

Serial Schedule & Nonserial Schedule

Schedule은 다시 Serial Schedule과 Nonserial Schedule로 나뉨

 

• Serial Schedule: 트랜잭션들이 겹치지 않고 한 번에 한 번씩 실행되는 스케쥴
  • 이상한 결과를 만들어내지는 않지만, 한 번에 하나만 처리하므로 처리량이 낮음 (I/O 작업 동안 아무것도 안 하고 대기 등)

 

• Nonserial Schedule: 트랜잭션들이 겹쳐서 실행되는 스케쥴
  • 처리량은 높지만(트랜잭션 1에서 I/O completion 기다리는 동안 트랜잭션 2 진행 등) 경우에 따라 이상한 결과가 나올 수 있음

 

 

 

자연스럽게 고민은 Nonserial schedule로 처리하되 이상한 결과가 나오지 않게 하려면 어떻게 할까로 이어짐

-> serial schedule과 동일한 nonserial schedule을 실행하면 되겠다

 

 

Schedule Equivalent

'스케쥴이 동일하다(equivalent)'는 것을 정의하는 방법은 여러가지가 있지만, 그 중 conflict equivalent 하다면 스케쥴도 동일하다고 정의하는 방법을 사용. 

 

conflict: 두 개의 operation에 대해서 아래 세 가지 조건을 모두 만족하는 경우 conflict (read-write conflict, write-write conflict가 있음) → conflict operation은 순서가 바뀌면 결과도 바뀌기 때문에 매우 유의해야 함

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

conflict equivalent: conflict operation의 순서가 바뀌면 결과가 바뀐다는 것은, 둘의 순서가 같다면 결과도 같기 때문에 같은 schedule이라고 정의할 수 있다는 생각. 아래 두 조건을 모두 만족하면 conflict equivalent

• 두 schedule은 같은 transaction들을 가진다
• 어떤 conflict operations의 순서도 양쪽 schedule이 모두 동일하다

 

 

Serializability

어떤 nonserial schedule이 serial schedule과 동일하는 것은 무슨 뜻일까?

어떤 nonserial schedule이 serial schedule과 conflict equivalent하다면 nonserial schdule로 실행해도 이상한 결과가 나오지 않는다는 것! 이 상태를 conflict serializable 하다고 함. 다시 말해 nonserial schedule이 conflict serializable하다면 정상적인 결과를 낸다! 허용하자! (뇌피셜이지만 Serializable이라는 용어를 잘 보면 직렬화 가능하다는 것, 즉 nonserial을 1자로 쭉 펼칠 수 있다는 것을 의미하는 것이 아닐까?)

 

DBMS에서는 여러 트랜잭션을 동시에 실행해도 schedule이 conflict serializable하도록 보장하는 프로토콜을 적용하는 방식으로 이를 구현함. Concurrency control은 어떤 스케쥴도 serializable 하도록 만드는 역할을 수행 ⇒ 이것과 밀접한 것이 isolation

 

 

 

Recoverability

어떤 스케쥴이 serializable 하다고 해서 문제가 없는 것이 아님.

 

Unrecoverable Schedule

위 그림처럼 한 트랜잭션에 의존성을 지닌 트랜잭션이 먼저 커밋될 경우 문제가 발생. t1에서 이미 커밋을 했기 때문에 t2에서 롤백을 시도해도 DB의 Durability 속성(한 번 커밋된 내용은 영구히 보존되어야 함) 때문에 롤백이 안 됨.

 

위와 같이 롤백해도 온전히 돌아갈 수 없는 스케쥴을 unrecoverable schedule이라고 함. 이런 스케쥴은 DBMS가 허용해서는 안 됨

 

 

Recoveralbe Schedule

그렇다면 반대로 롤백하면 온전히 돌아갈 수 있는 스케쥴을 recoverable schedule이라고 함. 어떤 스케쥴이 recoverable하기 위해서는 스케쥴 내에서 그 어떤 트랜잭션도 자신이 읽은 데이터를 write한 트랜잭션이 먼저 커밋/롤백 될때까지는 커밋을 하지 않아야 함. 즉, 어떤 트랜잭션(t3)이 다른 트랜잭션(t4)에 종속성을 지닐 경우, 독립성(약간 뇌피셜 표현임)을 지니고 있는 트랜잭션(t4)가 커밋 혹은 롤백 된 이후에 의존하는 트랜잭션(t3)가 커밋되거나 롤백되어야 한다.

 

 

Cascade Rollback, Cascadeless schedule, Strict Schedule

만약 t4가 롤백된다면, t3도 롤백되어야 하는데, 이처럼 하나의 트랜잭션이 롤백하면 의존성이 있는 다른 트랜잭션도 롤백하는 것을 cascading rollback이라고 한다.

 

Cascadeless schedule: cascading rollback의 경우 처리 비용이 크기 때문에 되도록 이런 현상이 나타나지 못하는 스케쥴이 나왔고, 이를 cascadeless schedule 혹은 avoid cascading rollback이라고 한다. 이는 어떤 트랜잭션이 커밋 혹은 롤백되기 전까지는 읽지 못하게 하는 것이다. 

 

Strict Schedule: Cascadeless Schedule에서는 read를 막기 때문에 냅다 write부터 갈기는 경우는 막지 못한다. 이를 막기 위해서 어떤 트랜잭션이 커밋 혹은 롤백되기 전에 읽지도, 쓰지도 못하게 하는 것을 Strict Schedule이라고 한다.

Recoverable Schedule의 종류

 

위에서 알아본 cascadeless schedule, strict schedule 모두 결국 recoverable schedule의 일부이다. 중요한 것은 DBMS가 concurrent한 트랜잭션을 처리함에 있어서 recoverability, 즉 롤백을 해도 이전의 상태로 온전히 돌아갈 수 있는 스케쥴만 허용해야 한다는 것이다.

 

 

글의 결론! DB에서 Concurrent Control은 Serializability와 Recoverability를 제공해야 한다