Concurrency control & Serializability

Serializability / Serializable

설명 전

• Schedule
  • 여러 Transactions이 동시에 실행 될 때 각 Transaction에 속한
    operations 들의 실행 순서
• Operation
  • Schedule의 하나의 작업
  • e.g. 'r1(A)'

e.g.

A가 B에게 20 이체, B가 본인에게 30 이체
A_BALANCE = 100, B_BALANCE = 200

• schedule1
  • r1(A) - w1(A) - r1(B) - w1(B) - c1 - r2(B) - w2(B) - c2
• schedule2
  • r2(B) - w2(B) - c2 - r1(A) - w1(A) - r1(B) - w1(B) - c1
• schedule3
  • r1(A) - w1(A) - r2(B) - w2(B) - c2 - r1(B) - w1(B) - c1
• schedule4
  • r1(A) - w1(A) - r1(B) - r2(B) - w2(B) - c2 - w1(B) - c1

schedule4는 123과 다른 결과를 초래

• LostUpdate

  • 업데이트 유실
  • schedule4의 c2 ( w2(B) )

• Serial Schedule

  • Transaction들이 겹치지 않고 하나씩 실행되는 schedule
    (schedule1, schedule2)
  • 예상외의 결과를 초래하지는 않지만 직렬적으로 실행되기 때문에 고립성은 보장되지만 성능(동시성) 은 떨어져 현실적으로 사용할 수 없는 방식

• Non-Serial Schedule

  • 각 Transaction이 겹쳐서 실행
    (schedule3, schedule4..)
  • r2(B) - r1(A) - w2(B) - w1(A) - c2 - r1(B) - w1(B) - c1
  • 동시성이 높아져 같은시간동안 더 많은 transaction처리 가능하지만 schedule4 와같은 예상외의 결과를 초래(고립성 위반)

성능(동시성)과 고립성 모두 챙길 순 없을까?

serial schedule과 동일한(equivalent) nonserial schedule을 실행하면 되겠다!(라는 아이디어) -> schedule이 동일하기위한 정의가 필요.
어떨 때 원치않은 결과가 나올까? -> conflict operation은 순서가 바뀌면 결과도 바뀐다.

• Conflict (of two operations)
  • 두개의 operations 에대하여
    • 서로 다른 transaction 소속
    • 같은 데이터에 접근
    • 적어도 둘 중 하나는 write operation
  • 위 세가지 조건을 만족하면 이 두 operation은 conflict하다
    • read-write conflict
      (sched.3 의 r2(H) 와 w1(H), w2(H) 와 r1(H))
    • write-write conflict
      (sched.3 의 w2(H) 와 w1(H))

Conflict equivalent? 스케쥴이 동일하다는 의미를 정의하는 여러가지 방식(view equivalent...)이 있다 中 1

• Conflict equivalent (of two schedules)

  • 두개의 스케쥴 에 대하여
    • 두 schedule은 같은 transaction들을 가진다
    • 어떤 conflicting operations의 순서도 양쪽 schedule모두 동일하다
  • 위 두 조건 모두 만족하면 conflict equivalent (스케쥴이 동일) 하다
    • sched. 2 와 sched 3 는 conflict equivalent
      

• Conflict serializable

  • Serial Schedule 과 Conflict equivalent 할 때 Conflict serializable 이다

    • sched.2 는 serial schedule / sched.3 는 nonserial schedule
      nonserial schedule 인 sched.3 은 serial schedule인 2와 conflict equivalent 하다
    • 따라서 sched.3 은 nonserial schedule 이였음에도 정상적인 결과를 낼 수 있었던 것

  • 반면에

    • 트랜잭션 두개로 만들 수 있는 serial schedule은 1 과 2 두개뿐
    • 그러나 sched.4 는 1과 2 모두와 conflict equivalent 하지 않다.
    • 따라서 정상적이지 않은 결과가 나왔던 것
      

-> 성능때문에 여러 transaction들을 겹쳐서 실행할 수 있으면 좋겠다 (nonserial schedule)
-> 그러나 이상한 결과가 나오는 것은 싫다.
-> conflict serializable한 NonSerial schedule 을 허용 하자
-> 수많은 transaction이 실행 될 때마다 해당 schedule 이 conflict serializable 인지 확인해야함
-> 비용이 많이 들어 이 방법이 쓰이지는 않음
-> 그렇다면 schedule이 conflict serializable 하도록 보장하는 프로토콜을 적용하자

Concurrency Control

어떠한 스케쥴도 serializable하게 만들 수 있도록 하는 것
Isolation(고립성) 과 밀접한 관련 (Isolation level)