[Database] DB concurrency control: schedule과 serializability, recoverability

Lost Update 현상

데이터베이스 시스템에서 Lost Update는 동시에 실행되는 두 트랜잭션이 동일한 데이터 항목을 업데이트하여 이전 업데이트가 손실되는 현상을 의미합니다.

다음과 같은 상황에서 발생할 수 있습니다.

이미지 출처: https://vladmihalcea.com/wp-content/uploads/2014/09/lostupdatesinglerequesttransactions.png

 

1. Alice가 Transaction을 시작합니다.
2. 동시에 Bob도 Transaction을 시작합니다. 이 때 Product의 quantity와 likes는 Alice, Bob에게 각각 7, 5 입니다.
3. Alice가 product의 quantity를 6으로 Update 합니다.
4. Bob은 product의 quantity를 10으로 Update 합니다.
5. Alice는 자신의 Update를 Commit 하여 DB에 반영합니다.
6. Bob 또한 자신의 Update를 Commit 하여 DB에 반영합니다. 
7. 결과적으로, DB에는 Bob의 Update 내역만 반영되게 됩니다.

이와 같은 업데이트된 데이터가 사라지는 현상을 Lost Update 현상이라고 합니다.

스케줄(Schedule)

여러 Transaction들이 동시에 실행될 때 각 Transaction에 속한 동작들의 실행 순서를 스케줄(Schedule)이라고 합니다.
스케줄에서 각 Transaction 내의 동작들의 순서는 바뀌지 않습니다.

스케줄에는 시리얼 스케줄과 넌시리얼 스케줄이 있습니다.

시리얼 스케줄(Serial Schedule)

• 시리얼 스케줄(Serial Schedule) 은 transaction들이 겹치지 않고 한 번에 하나씩 실행되는 스케줄입니다.
• 따라서 순차적이고 한 번에 하나의 트랜잭션 실행으로 이상한 데이터가 생길 가능성이 없습니다.
• 또한 시리얼 스케줄의 경우 DB transaction에서 IO 작업을 하는 동안에 CPU는 아무것도 하지 않습니다. 따라서 한 번에 하나씩
• transaction만 실행되기 때문에 좋은 성능을 낼 수 없고 현실적으로 사용할 수 없는 방식입니다.

넌시리얼 스케줄(Nonserial Schedule)

• 넌시리얼 스케줄(Nonserial Schedule)은 transaction들이 겹쳐서 실행되는 스케줄입니다.
• 넌시리얼 스케줄은 여러 트랜잭션을 동시에 처리가 가능하여 동시성을 통해 빠른 처리가 가능합니다.
• 하지만 transaction들이 어떤 형태로 겹쳐서 실행되는지에 따라 이상한 결과가 나올 수 있습니다.

넌시리얼 스케줄을 실행해도 이상한 결과가 나오지 않을 방법을 연구하기 위해 시리얼 스케줄과 동일한 넌시리얼 스케줄을 실행하면 되겠다는 아이디어가 나오게 됩니다. 이를 위해 스케줄이 동일하다는 의미를 재정의하기 시작합니다.

Conflict of two operations

다음 세 가지 조건을 모두 만족하면 Conflict라고 합니다.

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

Conflict operation은 순서가 바뀌면 결과도 바뀌기 때문에, Conflict를 피해야 합니다.

Conflict equivalent for two schedules

두 조건을 모두 만족하면 conflict equivalent라고 정의합니다.

1. 두 schedule은 모두 같은 transaction들을 가진다.
2. 어떤 conflicting operations의 순서도 양쪽 schedule 모두 동일하다.

Conflict Serializable

시리얼 스케줄과 넌시리얼 스케줄이 서로 conflict equivalent일 때 넌시리얼 스케줄을 Conflict Serializable 라고 합니다.

따라서 넌시리얼 스케줄은 정상적으로 동작합니다. 또한 Serializablility를 가진다고 합니다.

그러나 어떤 시리얼 스케줄과도 conflict equivalent하지 않다면, conflict serialziable 할 수 없습니다.

따라서 이 넌시리얼 스케줄은 정상적으로 동작할 수 없습니다.

넌시리얼 스케줄의 구현

여러 transaction이 실행될 때 마다 해당 schedule이 conflict serializable인지 확인하는 방법이 있겠지만, 실제로 많은 요청이 들어올 경우 매번 conflict serializable을 확인하는 것은 시간적 비용이 많이 들 수 있습니다.

따라서 여러 transaction을 동시에 실행해도 스케줄이 conflict serializable하도록 보장하는 프로토콜을 적용하는 구현 방법이 있습니다.

---

Rollback과 durability

Rollback은 트랜잭션이 실패하거나 데이터 무결성을 위협하는 경우 수행되는 작업입니다. Rollback은 트랜잭션이 수행한 모든 변경 사항을 되돌려 데이터베이스 상태를 이전 상태로 복원합니다.

 

Durability는 트랜잭션이 커밋된 후 데이터 손실 없이 영구적으로 저장된다는 것을 의미합니다. Durability는 시스템 오류, 하드웨어 장애, 소프트웨어 오류와 같은 예상치 못한 상황에서도 데이터 무결성을 보장합니다.

Unrecovery Schedule, Recoverable Schedule

Unrecoverable Schedule

Unrecoverable Schedule은 한 트랜잭션이 이미 커밋된 다른 트랜잭션의 작업을 롤백하게 만드는 스케줄입니다.

즉 Commit된 Transaction이 이전에 Rollback된 Transaction이 Write한 데이터를 Read 한 경우입니다.

이러한 상황은 데이터 무결성 위반으로 이어질 수 있으므로 Unrecoverable Schedule은 일반적으로 허용되지 않습니다.

 

Unrecoverable Schedule이 발생하는 일반적인 방법은 다음과 같습니다.

• Dependency Violation: 한 트랜잭션이 이미 커밋된 다른 트랜잭션이 읽거나 쓴 데이터에 의존하는 경우 Dependency Violation이 발생합니다. 이러한 경우, 롤백된 트랜잭션의 작업은 이미 커밋된 작업과 충돌하여 데이터 무결성을 위협할 수 있습니다.
• Lost Updates: 두 트랜잭션이 동일한 데이터 항목을 동시에 업데이트하는 경우 Lost Updates가 발생합니다. 이러한 경우, 롤백된 트랜잭션의 업데이트는 손실되고 커밋된 트랜잭션의 업데이트만 유지됩니다.

이는 rollback을 해도 이전 상태로 회복 불가능할 수 있기 때문에 이런 schedule은 DBMS가 허용하면 안됩니다.

따라서 어떤 Transaction이 의존하고 있는 Transaction이 Rollback이 발생할 경우, 같이 Rollback이 되어야합니다.

이를 Cascading rollback이라고 합니다.

 

Recoverable Schedule

스케줄 내에서 그 어떤 transaction도 자신이 읽은 데이터를 write한 transaction이 먼저 commit/rollback 전까지는 commit하지 않는 경우를 recoverable schedule이라고 합니다.

 

Recoverable Schedule은 어떤 트랜잭션도 다른 트랜잭션의 커밋된 작업을 롤백하지 않는 스케줄입니다. 이러한 스케줄은 데이터 무결성을 보장하기 때문에 동시성 제어 프로토콜에서 선호됩니다.

그리고 이러한 스케줄은 recoverablility를 가진다고 표현합니다.

 

Recoverable Schedule을 유지하는 데는 여러 가지 방법이 있습니다. 일반적인 방법으로는 다음과 같은 것들이 있습니다.

• Locking: Locking은 트랜잭션이 데이터 항목에 대한 독점적 액세스를 얻도록 하여 다른 트랜잭션이 해당 항목을 업데이트하는 것을 방지합니다.
• Timestamping: Timestamping은 트랜잭션에 타임스탬프를 할당하고, 타임스탬프 순서에 따라 트랜잭션을 실행합니다. 이를 통해 이전에 커밋된 트랜잭션보다 타임스탬프가 작은 트랜잭션이 롤백되는 것을 방지할 수 있습니다.

Cascadeless schedule

하지만 연쇄적으로 rollback을 하는 것은 시간적 리소스가 많이 듭니다.

따라서 데이터를 write한 transaction이 commit/rollback되고 나서 다음 transaction이 이어서 진행하도록 하는 스케줄만 허용하도록 하자는 아이디어가 등장합니다.

 

Cascadeless Schedule

스케줄 내에서 어떤 transaction도 commit 되지 않은 transaction들이 write한 데이터는 읽지 않는 경우를 cascadeless schedule이라고 합니다.
Cascadeless Schedule은 한 트랜잭션이 다른 트랜잭션의 실패로 인해 롤백되지 않는 스케줄입니다.

즉, 한 트랜잭션이 실패해도 다른 트랜잭션은 영향을 받지 않고 정상적으로 커밋될 수 있습니다.

 

Cascadeless Schedule은 다음과 같은 특징을 가집니다.

• 트랜잭션 독립성: 한 트랜잭션의 실패는 다른 트랜잭션에 영향을 미치지 않습니다.
• 비참존성(non-existence): 한 트랜잭션에서 읽은 데이터가 다른 트랜잭션에서 업데이트될 수 있습니다.
• 데이터 무결성 위험: 비참존성으로 인해 데이터 무결성 위험이 발생할 수 있습니다.

Strict schedule

스케줄 내에서 어떤 transaction도 commit 되지 않은 transaction들이 write한 데이터는 읽지도 않고 쓰지도 않는 스케줄을 strict schedule이라고 합니다.

Strict Schedule은 모든 트랜잭션이 성공적으로 커밋되거나 모두 롤백되는 스케줄입니다.

즉, 한 트랜잭션이 실패하면 다른 트랜잭션도 롤백되어야 합니다.

 

Strict Schedule은 다음과 같은 특징을 가집니다.

• 트랜잭션 원자성: 모든 트랜잭션은 하나의 작업 단위로 처리됩니다.
• 데이터 무결성 보장: 비참존성이 발생하지 않으므로 데이터 무결성이 보장됩니다.
• 성능 저하: 모든 트랜잭션이 서로 의존하기 때문에 성능 저하가 발생할 수 있습니다.

이 스케줄은 Rollback을 할 때 recovery가 쉽습니다. transaction 이전 상태로 돌려놓기만 하면 됩니다.

Concurrency control

Concurrency control은 serializability와 recoverablility를 보장합니다.
그리고 이와 관련된 Transaction의 속성이 Isolation 입니다.
Isolation이 엄격하면 동시성이 억제되어 성능이 떨어질 수 있기 때문에, Isolation을 단계적으로 완화시키는 것을 Isolation level이라고 합니다.

참고

• Google Gemini
• https://youtu.be/89TZbhmo8zk?si=MS9Nw6fSwvKZPM1P
• https://youtu.be/DwRN24nWbEc?si=eIk-eLiTVZ-DpIWA