[DBMS] Transactions에서 ACID를 유지하는 방법 logging, Locking

Atomicity

• TXNs가 모두 실행되거나 실행되지 않는 것을 뜻함
• abort나 crash가 발생해도 TXNs에 영향을 끼치지 않음

Durability

• transaction이 성공적으로 완료된 후에 데이터의 변경 내용이 영구적으로 유지됨
• Disk장애가 발생해도 데이터베이스는 복구되어 일관된 상태를 유지해야 함

---

---

Log

• List에 commit을 정보를 저장하여 DBMS가 중단될 때 되돌릴 수 있음
• log는 이중화되고 안정적인 storage에 저장함

---

Basic Idea

• 로그에 순차적으로 기록함
• 최소한의 정보만 기록함 -> <XID, location, old data, new data>  
  • 이를 통해 현재 한 동작에 대한 취소를 할 수 있게 됨

---

필요한 이유

• TXNs이 중단될 때 원자성을 유지하기 위해 필요함
• TXNs가 길어지면 Memory constraints, Time constraints이 발생하기 때문에 Disk에 저장해야 함
• 그렇기 때문에 Disk에 partial results를 기록해야 함

---

Write-Ahead Logging(WAL)

어떤 동작을 수행하기 전에 log를 남기는 것이다.

Commit process

1. log에 commit을 기록함
2. TXN의 최신의 update까지 모든 log가 기록됨
3. commit

incorrect commit protocol (1)

모든 데이터를 disk에 기록하지 않아서 commit 중에 crash가 발생하면 A = 1의 정보(T)가 다 사라짐

---

incorrect commit protocol (2)

Data는 Disk에 잘 들어간 상태에서(T는 recode 됨) Log commit 중 crash가 발생하면 Data on Disk의 A와 Log on Disk의 A 값이 다르기 때문에 신뢰할 수 없는 데이터가 된다.

---

correct commit protocol

log가 crash 하지 않고 commit 되었을 때 Data를 update 하는 것이 안전하고 옳은 방법임

 

WAL를 통해 Atomicity과 Durability를 만족할 수 있다.

---

Isolation

• system을 혼자 사용하는 거 같은 느낌을 줌
• transaction을 실행하는 동안 다른 transaction에 의한 영향을 받지 않음
• 여러 개의 transaction이 동시에 실행될 때 데이터의 일관성과 정확성을 유지하기 위해 필요한 요소

---

Consistency

•  데이터베이스의 제약 조건을 준수하고 데이터의 일관성을 유지하는 것
• 데이터베이스에는 여러 개의 테이블과 관계가 존재하며, 이 들의 관계를 유지하고 데이터의 무결성을 보장하기 위해 필요함

---

T1: START TRANSACTION
		UPDATE Accounts
		SET Amt = Amt + 100
		WHERE Name = ‘A’
        
		UPDATE Accounts
		SET Amt = Amt - 100
		WHERE Name = ‘B’
COMMIT

T2: START TRANSACTION
		UPDATE Accounts
		SET Amt = Amt * 1.06
COMMIT

위와 같은 SQL 명령이 있을 때 Serial 시키면 아래와 같다.

serial (1)

serial (2)

위의 2개의 serial은 순서에 따라 A와 B의 값이 다르게 나오며 이를 통해 TXNs에 순서가 필요한 것을 알 수 있다.

---

interleave

DBMS 내에서 동시에 실행되는 여러 txns 간의 작업이 교차되어 실행되는 방식이다. 동시성을 활용하여 system의 성능을 향상하는 역할을 한다.

 

isolation, consistency을 만족하는 interleaving or schedule을 구축해야 함(txn가 serial로 실행된 것과 같아야 함)

interleave

하지만 위와 같이 interleave 할 경우 interleave 순서에 따라 결과가 바뀔 수 있으며 Isolation을 유지하며 실행해야 한다.

---

 

결과가 같기 때문에 위의 Interleaved schedule은 적합하다고 볼 수 있다.

---

결과가 다르기 때문에 위의 Interleaved schedule는 적합하지 않다고 볼 수 있다.

---

Scheduling Definitions

• A serial schedule
  • txn가 순차적으로 실행되는 schedule을 의미함
  • 하나의 txn이 완전히 종료되어야 다음 txn이 실행됨
  • 동시성이 없으며, txn끼리 완전히 격리되어 실행됨
  • 일관성과 격리를 보장하지만 동시성 처리량 측면에서 제약이 있음
• equivalent schedules
  • 동일한 결과를 생성하는 서로 다른 schedule을 의미함
  • txns들이 서로 다른 순서로 실행되거나 교차 순서가 다르지만 전부 동일한 결과를 얻음
• serializable schedule
  • A Serial shedule과 동등한 결과를 생성하는 schedule로 여러 txns이 동시에 실행되지만 외부에서는 직렬적으로 실행된 것처럼 보임
  • 여러 개의 schedule 중 하나라도 A Serial shedule의 결과와 같으면 됨

A serial schedule	A	B
T1, T2	1.06*(A+100)	1.06*(B-100)
T2, T1	1.06*A+100	1.06*B-100

A	B
1.06*(A+100)	1.06*(B-100)

A serial schedule 중 T1, T2와 결과 값이 같기 때문에 위의 순서는 serializable schedule이라고 할 수 있다.

---

A	B
1.06*(A+100)	1.06*B-100

A serial schedule의 결괏값 중 어느 것도 같은 게 없어 serializable schedule이라고 할 수 없다.

---

Conflict 

Interleave을 진행하면 conflict가 생기며 conflict의 종류를 파악하기 위해서는  Write(W)의 위치를 파악하는 것이 중요하다.

 

 Read-Write conflicts (RW)

T1에서 A항목을 읽고 T1의 작업이 완료되기도 전에 T2에서 A 항목 쓰기를 시도했기 때문에 RW conflict가 발생한다.

 

이는 동시에 실행되는 TXNs의 충동을 의미하고 한 TXN이 데이터를 읽으려고 할 때 다른 TXN이 동시에 해당 데이터를 쓰는 경우이다.

---

 Write-Read conflicts (WR)

Dirty read라고도 불린다.

 

T1에서 A 항목 쓰기를 시도하고 A값이 변경된 상태에서 T2에서 A항목 쓰기를 시도한다.

그 과정에서 T1에 abort가 발생하여 Rollback되면 T1에서 변경된 값을 T2에서 사용한 것이기 때문에 잘못된 값을 저장하게 된다.

---

 Write-Write conflicts (WW)

T1에서 A항목은 T2전에 변경되었고 T2에서 변경된 A와 변경되지 않은 B의 연산이 일어난 후 T1에서 B항목을 변경한다.

이는 Partially-loss update로 T2의 A항목은 T2가 마지막 실행인 것처럼 실행되고 B항목은 T1이 마지막 실핸인것처럼 실행돼서 발생하는 문제이다.

---

Conflict serializability

충돌의 현상을 똑같이 하여 Isolation과 consistency를 유지할 수 있는 schedules을 만드는 것이다.

Bad Schedules

Good Schdules

Conflict serializable는 serializable될 수 있고 그렇다면 Isolation과 consistency유지가 가능한다.

---

Serial Schedule

Interleaved Schedules

---

Conflict Graph

node와 edge로 구성된 그래프로 Txns의 Conflict관계를 간단하게 나타낸다.

---

Conflict serializability의 사진을 다음과 같이 그래프로 표현할 수 있다. 그리고 그래프에는 acyclic이 생기면 안 되기 때문에 아래의 그래프의 schedules은 사용하면 안 된다.

---

Locking

Conflict 문제를 해결하기 위해 고안된 것으로 TXNs 간 상호작용을 제어하는 데 사용된다.

 

Lock은 txn의 데이터 항목에 대한 상태를 나타내며 txn을 읽거나 수정할 때 사용한다. txn이 완료될 때까지 lock이 유지된다. 이를 통해 다른 txn가 해당 데이터 항목에 접근하는 것을 제한하고 충돌을 방지한다.

 

R Lock과 WLock이 있으며 R은 Shared lock이라고도 불리며 W는 Exclusice lock이라고도 불린다.

 

2-phase Locking(2PL)

txn의 직렬 가능성을 보장하기 위해 lock과 unlokk 연산의 수행 시점에 새로운 규약을 추가한 기법이다.

---

Deadlock

위와 같이 T2는 A에 W를 위해 Exclusice lock 걸기 위해서는 T1이 commit 되길 기다려야 하고 T1에서는 B에 W를 위해 Exclusice lock 걸기 위해서는 T2의 commit을 기다려야 한다.

다음과 같이 그래프에 사이클이 생기는 것을 deadlock이라고 한다.

---

이를 해결하기 위해 wait graph를 만들어 deadlock을 인지하고 둘 중 하나의 연결을 해지하거나 처음부터 발생하기 않게 구조를 작성해야 한다.

---

Interleave은 Isolation과 consistency를 유지하면서 TXNs을 병행 처리하하는 것으로 늘 serializablilty 하게 schedule을 작성해야 한다.

 

Inerleave는 Conflict를 동반하는데 serial과 같은 Conflict를 가지게 설계하는 Conflict serializability를 유지하는 것이 중요하며 이를 위해서는 2pc를 이해해야 한다.