회사에서 발표한 자료를 공유합니다.

원제목: SSI Concurrency Control Algorithm

• 시간 관계상, isolation level 에 대해 기본적인 개념은 설명하지 않습니다.

들어가며

• postgreSQL 은 serializable 격리 수준을 lock이 아닌 serializable snapshot isolation(ssi) 을 통해 지원합니다.
• 기본이 된 격리수준인 si 를 간단하게 살펴보고, ssi 의 기본 원리와 구현방식을 살펴봅시다.
• 또한, 이번 공유로 인해 회사에서 필요한 순간에 맞춰서 적절한 격리수준을 사용하게 되길 바랍니다.

Snapshot Isolation (SI) 와 Write Skew

SI (Snapshot Isolation)

• SI은 read 와 write 간의 delay 가 없는 매우 성능이 좋은 isolation level 입니다.
  • Repeatable Read 라고 불립니다.
• 한 트랜젝션 안에서는 consistency 가 보장된 읽음을 보장합니다.
  • 실행 timestamp보다 낮거나 같은 것만 보게 됩니다. 따라서 실행 이후 업데이트는 보지 않습니다.
  • transaction 실행 이후 생기는 버전은 읽지 않습니다.
• psql은 이를 하나의 item 에 대해서 여러 version 을 가지고 있는 mvcc (multi version concurrency control) 를 이용하여 구현합니다.
• first write win (fww) 규칙을 이용하여 transaction에서 consistency 를 방어 합니다.
  • 같은 row 를 두 트랜잭션이 동시에 바꾸는 것은 불가능합니다.
• PostgreSQL 과 MySQL 에서는 Repeatable Read 라고 불리고, Oracle DB 에서는 Serializable 라고 불립니다.
• 하지만 SI 는 Write Skew 현상이 일어납니다

Write Skew

• Write Skew 현상은 하나의 트랜잭션 안에서는 문제가 없지만 결과적으로는 제약을 위반하는 결과들이 초래하는 것을 말합니다.
• 예시) 두 개발자 당직 문제 (두 의사 문제)
  • 설날에서는 많은 트래픽 때문에 백엔드 팀에서 당직을 서는 개발자가 항상 한명 이상 있어야 한다고 합시다.
  • 이때 Jaquan 과 Giri 가 동시에 자신을 당직에서 제거하는 transaction 을 si isolation 에서 발생한다고 합시다.

    name	당직
    jaquan	true
    giri	true
    koil	false
    clasn	false
    dugi	false

  • 자신이 당직을 해도 되는지는 아래와 같은 쿼리로 수행됩니다.

    • 모든 개발자 리스트를 읽어서, 당직하는 사람이 1 이상이면 자신의 당직을 오프합니다.

      transaction begin;
      count= select count(*) from backends where 당직 is true
      if count >=2 {
      	update backends set 당직 = true where name = {요청한 이름}
      }
      transaction commit;

  • 동시에 giri 와 jaquan 2개의 transaction 이 실행 될 수 있습니다.
    • jaquan 의 transaction 이 실행될때, count가 2개 잡히기 때문에 id: jaquan, 당직: off 로 설정합니다.
    • giri 의 transaction 이 실행될때, count가 2개 잡히기 때문에 id: giri, 당직: off 로 설정합니다.
  • 두개의 transaction 은 각각 실행되고, fww 으로도 막아지지 않습니다. 하지만 실제로는 당직이 없어진 날이 생깁니다.

Write Skew 방어 방식

1. 2PL 방식에서는 Lock 으로 방어 할 수 있습니다.

   • record 들, 혹은 gap 에 대해서 lock 을 걸어서 read 를 못하게 해서 방어 할 수 있습니다.
   • 예를 들어서 아래와 같은 쿼리가 될 것 입니다.

     transaction begin;
     count= select count(*) from backends where 당직 is true **for update**
     if count >=2 {
     	update backends set 당직 = true where name = {요청한 이름}
     }
     transaction commit;

   • giri 혹은 jaquan 중에 먼저 for update 로 select 를 한 순간 다른 transaction 은 기다리기 때문에 방어할 수 있습니다.
   • 단점
     • 단 lock 을 이용하여서 성능 이슈가 있을 수 있으며, deadlock 이 발생할 수 있습니다.

2. SI 에서는 table 설계를 변경하여 방어 할 수 있습니다.

   date	당직 서는 사람
   2023-02-01	giri,jaquan

   • fww으로 방어할 수 있습니다.
   • 단점
     • 설계시 고려되어야 합니다.
     • 실수하기 쉽습니다.

• 이런 이유로 psql 에서는 그럴듯한 방안이 없어서 SI 까지만 지원하였습니다.

  For this reason, PostgreSQL historically did not even provide serializability, instead offering snapshot isolation as its highest isolation level.

• Serializable 을 지원하기 위해 나온 Serializable Snapshot Isolation 을 살펴봅시다.
  • 9.1 부터 지원하기 시작했습니다!

Serializable Snapshot Isolation (SSI)

• SI 의 성능과 같지만 2PL 의 보장과 동일한 SSI 에 대해서 소개합니다

Serializable

• 그럼 Serializable 이란 뭘까요?
  • 순차적으로 하나씩만 돌리면 Serializable 라고 할 수 있습니다. (싱글 쓰레드인 redis 는 이렇게 지원합니다)
  • 혹은 개별로 실행하지만, 다 순차적으로 실행한 것과 결과가 같아도 Serializable 이라고 합니다.
  • 단순하게 생각하면 동시에 수행되는 다른 transaction 이 존재 하지 않고 수행된 것과 같은 상태를 이야기합니다.

요구조건

• 개발자의 설계와 무관하게 serializable 을 지원해야합니다.
• SI 와 가까운 정도의 성능을 내고, 2PL 보다 성능이 좋아야합니다.
  • read와 write operation 은 서로를 느리게 만들지 않아야 합니다.(optimistic locking)

핵심 아이디어

• serializable 에 위험할 수 있는 상황이 생기면 바로 해당 transaction 을 abort 시킵니다.
• 위험한 상황에 대한 것은 serialization graph (SG) 으로 판단합니다.

SG (serialization graph)

• 두개의 같은 item 을 읽은 transaction 은 3가지의 관계를 가질 수 있습니다.
  

1. wr-dependency
   • 먼저 수행된 T1 이 commit 완료한 후, 후에 실행된 T2가 그 값을 읽는 경우를 말합니다.
2. ww-dependency
   • 먼저 수행된 T1 이 commit 을 완료한 후, 후에 실행된 T2 그 값을 대체하는 경우를 말합니다.
3. rw-antidependency
   • 먼저 수행된 T1이 어떤 객체의 버전을 쓰고 커밋하기 전, T2가 해당 객체의 이전 버전을 읽는 경우, T2가 해당 업데이트를 보지 못하는 경우를 말합니다.
   • 이는 rw 충돌이라고 부르며, ssi 의 핵심입니다.

Dependency Cycle

• write skew 가 일어나는 상황을 SG 로 표현해보면 아래와 같습니다.

• 다시 말해서 rw cycle 생기는 경우를 serializability violation 이 일어났다고 볼 수있 습니다.
• 자세하게 다루진 않지만, Adya의 논문 에서 rw cycle이 있다면 serializable 하지 않다는 것을 증명하였습니다.
• 정리를 하자면 SI 에서 write skew가 일어나는 상황은 RW dependency cycle이 있을 상황이라는 것입니다.

SSI 의 전략

• 앞서 본것 처럼 serializable 을 유지하기 위해 rw-cycle을 발견할때 제거하면 되지만, SSI 는 그렇게 하지 않았습니다. 이유는 다음과 같습니다.
  • cycle detection 은 비용이 큽니다.
  • commit 마다 cycle을 매번 확인하려면 많은 것을 관리해야합니다.
  • 동시성 문제를 방어하기 위해 여러 graph 들에 Lock 으로 관리해야합니다.
  • 하지만 이는 위의 성능상의 이슈로 요구 조건을 만족하지 못합니다.
• SSI 는 cycle detection 이 아니라 전략을 취했습니다.
  • RW dependency 가 생기면 아래와 같이 처리합니다.
  • 한 transaction 기준으로 2개의 bool 값을 가집니다.
    1. inConflict : 다른 transaction 이 읽은 item 을 변경 여부
       • 다른 transaction 은 outConflict 가 true
    2. outConflcit : 자신이 읽은 item 을 다른 transactoin이 변경
       • 다른 transaction 은 inConflict 가 true
    3. 두개의 bool 이 모두 true가 설정되는 시점이 되면 “가능성이 있는 위험한 트랜잭션” 으로 판단하고 해당 transaction 을 abort 시킨다.
• 자세한 구현은 다음과 같습니다.
  • item 에 대해서 SIREAD 와 WRITE 을 기록해둔다.
  • 단, 두 lock mode는 서로를 방해하지 않지만, transaction 의 flag 를 세우기 위해 존재한다.
    • 2PL 처럼 서로를 방해하지 않기 때문에 성능상 이슈가 있지 않다.
  • SIREAD 를 해둔 transaction 은 outConflict ,write 를 해둔 transaction 은 inConflict 가 true 가 된다
• 단점 0
  • False Positive 가 생길 수 있습니다.
    • 실제로는 cycle 이 생기지 않을 수 있지만, abort 되는 더 큰 범위를 보호합니다.

성능

• short transaction 일때 S2PL 보다 훨씬 높고 SI 와 근접한 정도의 성능을 보여줬습니다.
  

• row size 가 많은수록 강력한 포퍼먼스를 보여줍니다.

• long transaction 일때도 si와 비슷한 성능을 보여줬습니다.
  

마무리 하며

결론

• SSI 는 사용자(개발자) 가 동시성 문제를 무시할 수 있게 함으로 개발을 더 편하게, 문제 없이 할 수 있습니다.
  • 특히 현대의 고도로 동시적인 시스템에서 중요합니다.
• 기존의 2PL에서는 과한 비용문제가 있었고, 그 문제는 SSI 로 해결하였습니다.
  • 단, 단점인 false positive 인 경우가 있습니다.
• psql을 쓰는 채널톡에서는 lock 을 걸일이 있다면, isolation level을 올려서 사용하는 것을 고려해보면 좋겠습니다.
  • 이 발표로 힘을 얻으시길 바랍니다.

참조

• cockroachDB-writskew
• Serializable Isolation for Snapshot Databases
• Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions
• Serializable Snapshot Isolation in PostgreSQL

수도 코드