[논문리뷰] Serializable Snapshot Isolation in PostgreSQL (VLDB '12)

MySQL, Oracle의 Locking 기법과는 좀 다른 Snapshot Isolation에 대해 간략하게 엿볼 수 있는 논문이다.

특히 Serializability에 대해 고민해볼 수 있는 좋은 논문이라 생각한다.

 

나는 Write Skew와 SSI의 구현을 중심적으로 읽고 정리하였다.
더 자세한 내용은 논문을 읽어보길 바란다. 논문이 잘 쓰여서 재밌게 읽을 수 있을 것 같다.

 

---

 

Snapshot Isolation (SI)

• Read가 트랜잭션 시작된 시점의 Committed Version 기준
• 트랜잭션이 시작된 이후의 변경 사항을 볼 수 없음
  • 한 트랜잭션 안에서는 일관성 보장
  • First-Writer-Wins
• PostgreSQL: MVCC 방식을 사용하여 구현
• Repeatable Read라 불림

 

장점

• Dirty Reads, Non-Repeatable Reads, Phantom Reads 해결

 

문제

1. Write Skew

• 두 동시 트랜잭션이 같은 데이터를 읽고, 겹치는 데이터를 수정했을 때 발생
• 하나의 트랜잭션 안에서는 문제X → 결과적으로 논리적인 Constraints 위반
• 예제

• 해결
  • 2PL: Select For Update (단점: 성능 하락, Deadlock)
  • SI: table 설계를 변경하여 FWW으로 방어 (단점: 설계가 어려움)

2. Batch Processing

• 예제

• T1은 T2의 INSERT를 보지 못함 → 데이터 불일치 발생
• 단순한 이해로는 Write Skew와 비슷한 개념으로 봐도 괜찮을듯 하다.

 

 

---

 

Serializable Snapshot Isolation (SSI)

• 기존 SI 기반 + 추가 검사 수행
• Serialization Graph 유지 → Cycle 발견 시 Abort
  • 추가적인 Blocking이 없다
  • Update Conflicts에서는 Abort
• VS 2PL: 충돌할 가능성이 있을 때만 Abort

 

Dependencies

• Adya et al.이 제안한 Multi-Version Serialization History Graph 상 종속성 유형

1. WR dependencies
   • W의 commit 후에 R 가능 (직렬 실행 보장)
2. WW dependencies
   • W1→W2 순서 (직렬 실행 보장)
3. RW dependencies
   • R2, W1
   • T2가 old version을 읽게 됨 → T2가 먼저 실행된 것처럼 보이지만, 실제로는 반대로 실행됐을 수도
     • RW-반종속성 (Read-Write Antidependency) (이하 RW라 부름)

⇒ Cycle 발생

• RW가 2개 이상 연결된 형태를 띄면 직렬성 유지X (Adya [1], Fekete et al [10])
  • Theorem1) T1→T2, T2→T3 두 개의 RW 존재, T3 먼저 commit
  • Corollary2) T1&T2, T2&T3 동시 실행, Write Skew에서는 T1==T3 일 수도 있음
• Cycle 존재 → 직렬성 보장X
  • 즉, SSI에서는 RW를 감지하여 직렬성을 보장

 

핵심

• Cycle을 직접 검사하지 않고, Dangerous Structure를 감지
  • 트랜잭션이 하나의 RW를 받아들이면서, 다른 트랜잭션과 RW인 경우(Incoming, Outgoing) → Abort
  • Theorem1에 따르면 이로써 직렬성 유지 가능, but 불필요한 abort 가능(False Positive Abort)
• vs. OCC, S2PL: rw를 일부 허용하되, Dangerous Structure일 때만 Abort

False Positive Abort in SSI

• 실제로는 직렬성이 유지될 수 있는 상황이었지만, SSI 알고리즘 상 직렬성이 위반되어 불필요한 Abort
• ex) Data: stock(10), Operation: stock--;
  • T1: R1(s:10), W1(s:9) T2: R2(s:10), W2(s:9)
  • RW 발생했지만, 직렬 실행 결과와 동일
• 해결 기법
  1. Commit Ordering Optimization: 모든 트랜잭션이 직렬화 되지는 않아 완벽히 해결X
  2. Precisely SSI: 전체 Graph를 검사하여 실제로 직렬성이 위반되는 경우에만 Abort
     • 메모리 사용량이 크고, 실제 벤치마크 상 Abort 비율이 낮아 이점이 크지 않다고 판단

 

---

 

PostgreSQL 상의 SSI 구현

New Lock - ‘SIREAD’

• PostgreSQL은 기존에 S2PL을 지원X
  • SSI는 SI 기반이므로 Postgre에서 쉽게 구현될 것이라 예상하였으나, 실제로 어렵게 되어 결국 S2PL과 유사한 Lock Manager가 필요하게 됨
  • MySQL 등은 기존의 Read Lock을 사용할 수 있으나 Postgre는 그럴 수 없다
• 트랜잭션이 데이터를 읽을 때 SIREAD를 설정
  • 쓰기 연산 허용(Blocking X, RW 허용) → Deadlock이 발생할 가능성이 없으므로 별도의 Deadlock Detection이 필요하지 않다
  • 쓰기 시도 → RW 감지
• RW는 동시 트랜잭션에서 발생 → 모든 트랜잭션이 끝날 때까지 유지 → 커밋한 후에도 Lock 유지 필요

 

Conflict Detection

1. Write가 먼저 발생한 경우
   • MVCC로 데이터 Visibility 확인
   • 데이터가 트랜잭션의 Snapshot에 보이지 않으면 RW-conflict 발생한 것으로 판단
     • old version을 읽은 것이므로 Read가 앞서야 함 → 직렬성이 깨질 가능성 존재
2. Read가 먼저 발생한 경우
   • MVCC 데이터만으로는 불가능 → SIREAD Lock 사용 필요

Safe Retry

• Abort 후 retry해도 직렬화 보장할 수 있도록. 즉 victim을 누구로 설정할지 결정하는 작업.
• ex) T1→T2→T3 (rw)
  1. T3 먼저 commit (Therem1)
  2. 가능하면 T2를 abort
     • T3는 이미 커밋되었으므로 abort 불가능
  3. T2도 커밋되었을 경우 T1을 abort
• 즉, 트랜잭션이 커밋할 때까지 기다렸다가 Abort
  • Delayed Abort의 이점
    • 트랜잭션의 연산이 무효화되므로 리소스 낭비 발생? → 아닌 경우도 있음
    • 이유: 동일한 트랜잭션이 다시 실행되었을 때도 동일한 문제로 Abort될 가능성이 높음
    • 즉, Commit Order가 결정된 후 Abort하면 같은 문제가 반복될 가능성이 줄어듦 (최적의 순간에 Abort)
    " In fact, the delayed resolution is less wasteful because it may ultimately not be necessary to abort transactions at all, depending on the order in which they commit. "

 

 

---

결국 Locking을 도입하게 되었다는 슬픈 사실...
Write Skew를 풀려고한 노력을 중점적으로 보기에 좋았다.

 

---

참고

https://velog.io/@jaquan1227/PSQL-%EC%97%90%EC%84%9C-Serializable-%EA%B2%A9%EB%A6%AC%EC%88%98%EC%A4%80%EC%9D%84-%EC%93%B0%EA%B8%B0-%EB%AC%B4%EC%84%9C%EC%9A%B0%EC%8B%A0%EA%B0%80%EC%9A%94

[논문 대신 읽기] PSQL 에서 Serializable 격리수준을 쓰기 무서우신가요?

https://dl.acm.org/doi/10.14778/2367502.2367523

Serializable snapshot isolation in PostgreSQL | Proceedings of the VLDB Endowment