Serializability
Serializable
A (possibly concurrent) schedule is serializable if it is equivalent to serial schedule.
순차적인 스케줄과 실행 결과가 같은 (equivalent한) 스케줄을 serializable 하다고 함.
Equivalent
S1 is equivalent to S2 if for every possible instance of DB execution of S1 results in the same DB state as the execution os S2.
✅ 실행 결과가 같으면 equivalent 하다는 말.
한 번에 기억하면 좋고, 안 되면 뒤에 읽다가 다시 꼭 돌아와서 읽어볼 것(!)
Conflict Serializability
Conflict
💡[중요]
conflict발생 조건: 둘 중 하나라도write(data)가 있으면conflict가 난다!
이걸 왜 기억해야 하냐면,, 뒤에 문제 풀 때 (precedence graph 그릴 때) 필요하니깐..
아 애초에 conflict를 왜 생각하냐면, read랑 write랑 순서가 바뀌어버리면 실행 결과도 달라지니깐 뭐 그런 상황을 생각하는 거
Conflict Equivalent
Schedules S and S' are conflict equivalent
if S can be transformed into S'
by series of swap of non-conflicting instructions
S의 non-conflicting instruction을 swap 해서 S'으로 만들 수 있다면, S와 S'은 conflict equivalent 하다는 말.
non-conflicting 예시: read(Q) & read(Q) or write(Q) & write(X) 조합 등. 같은 데이터면 read 끼리만 가능, 다른 데이터면 read, write 상관 없음.
swap 할 때, Transaction 내부의 instruction 순서를 바꾸는 게 아니라, Transaction들이 concurrent 하게 수행될 때 각각의 instruction 실행 순서를 바꾸는 거. (누가 헷갈릴까 싶지만) 혼동하지 말라고 하심.
뭐 결국 실행결과가 바뀌지 않음을 보장하면서 (non-conflicting만 건드니깐) S'와 동일하게 S가 바뀐다면 S와 S'은 equivalent 하다(S와 S'의 실행 결과가 같다)고 할 수 있겠다. 그 중에서도 conflict equivalent 한 거지.
Precedence Graph
Conflict 가 나는 경우, 배치 순서를 지켜주어야 함. 그래서 Transaction 간의 실행 순서가 정해지게 되는데, 그걸 그래프로 나타낸 것.
write 끼리만 conflict 나는 게 아니라는 점을 주의하자..
그리고 얘네가 유향그래프이고 사이클이 없으면 topological sort가 가능하다!
Conflict Serializable
A schedule is conflict serializable if and only if its precedence graph is acyclic.
cycle detection algorithm: 추후 정리 예정. 나중에 탐구해보면 좋겠다!🤩
Recoverability
DBMS must ensure that schedules are recoverable.
dbms는 serializable한 schedule만 수행하도록 관리해야 한다. conflict serializable을 의무화 해야 한다.
Recoverable Schedule
Recoverable이 아닌 예시.
Recoverable Schedule: if a transaction Tj reads a data item previously written by Ti, the commit of Ti appear before the commit of Tj.
위의 예시에서는,T9 가 T8 에서 쓰여진 item A 를 읽었다면, T8 에서의 커밋은 T9 커밋 이전에 수행되어야 한다.
아무튼 내가 읽어오려는 데이터가 다른 트랜젝션에서 쓰여졌으면 현재 트랜젝션의 커밋 순서보다 그쪽 트랜젝션의 커밋이 더 빨라야 복구 가능하다는 말.
💎 커밋 시점이 읽기 바로 전일 필요는 없음 :)
cascadeless schedule일 때는 그래야 하는데, 왜냐면 정의 상read(x)전에 다른 트랜젝션에서write(X)가 있으면dirty read를 방지하기 위해write(X)다음에 무조건commit을 해줘야 하기 때문. (커밋되지 않은 건 읽지도 않음)
아무튼 단순recoverable일때는commit그 자체에 있어서, 데이터를 읽는 나보다 데이터를 미리 쓴 상대 트랜젝션이 먼저commit하기만 하면 된다~ 조금 더 널널쓰(!)
왜냐? commit 이라는 건, 이제 다시는 돌아올 수 없는 강을 건넌 것과 같음..🤔
그래서 T8 이 수행되다가 갑자기 abort 나게 되면 roll back 을 해야하는데 T9는 이미 commit 나서 roll back이 안 됨..
그럼 데이터가 달라지니깐 문제가 생기겠지, 그러니깐 recoverable 하지 않다는 거.
[질문] Is this schedule recoverable? 🤔
정답: No. 위의 사례도 recoverable 하지 않은 예시다. T2가 T1에서 written 된 데이터 A와 B를 read 하는데, T2가 T1 보다 먼저 commit을 해서 정의에 위배됨. 그리고 상식적으로도 복구 못함.
아니, 분명 문제를 풀다보면 순서가 겁나 헷갈릴텐데 (그럴 수도 있을듯), 그럼 그냥 가장 Strict 하게 생각하고 적용하면 된다.
Cascading Rollback
하나의 트랜젝션이 커밋하지 않은 상태로 abort 되면 커밋되지 않은 데이터와 관련된 다른 트랜젝션들도 싹 다 roll back 하는 게 싫어요.. -> 이런 일이 일어나지 않았으면 좋겠다!
Cascadeless Schedule
dirty read를 애초에 하지 않겠다.
그게 뭐냐? 애초에 commit 되지 않은 데이터는 읽지도 않겠다.
부연 설명하자면, Tj는 Ti가 commit 하기 전까지 수행되지 않고 기다리다가, Tj 가 읽는 값은 최소한 abort 될 수 없는 것만 읽겠다!
Every cascadeless schedule is also recoverable.
It is desirable to restrict the schedules to those that are cascadeless,
🍯 cascadeless schedule 만들기 꿀팁은 그냥 read(X) 전에 write(X) 된 거 있으면 무조건 commit을 해주는 거.
대충 말했지만, 당연히 다른 transaction 에서 written 된 걸 read 할 경우라는 걸!
Proof.
Every cascadeless schedule is also recoverable.
대충 말해서, cascadeless에서 Ti는 Tj가 커밋한 후 데이터를 읽어옴. 이는 Tj가 Ti 커밋 전에 커밋 됨을 의미함. 즉, recoverable 조건을 만족함. 따라서 모든 cascadeless 는 recoverable 함.
언제나 정의를 생각하자.
(💝 recap.)
cascadeless schedule: if Ti reads a data item x written by Tj, then Tj must have already committed before Ti reads x.
recoverable schedule: if Ti reads x from Tj, then Tj must commit before Ti commits.
위의 영어로 된 정의가 진짜 잘 정리된 거 같다.
이쯤되면, 앞서 설명했던 equivalent의 개념이나, conflict serializable, 이런 건 아무래도 까먹었을 것 같다. 그러니깐 recoverable이나 cascadeless 여기서 잠시 빠져나와서 앞에 개념들을 한 번 더 보면 좋겠다~
