////
Search

More Transaction Manager

Concurrency control & recovery

logging 시스템은 crash에서 recover가 되지만, serializability를 support하고자 하진 않는다.
비슷하게 serializable schedule은 logging policy violation을 야기할 수도 있다.
•
Dirty data
◦
커밋되지 않았지만, transaction에 의해 바뀐 것이 dirty data이다.
◦
dirty data를 읽어들여서 처리를 하는 것이 일단 문제이다.
◦
따라서 rollback을 할 때는 관련되어있는 transaction 또한 다 같이 cascading 되어야한다.
◦
이런 cascading rollback은 validation based schedule에서는 안 생기는데 왜냐하면 validation-based scheduling은 기본적으로 serializable한 걸 가정한 상태에서 abort 되는 케이스들을 찾는 방식으로 진행되서 그렇네. locking도 없고.
•
Recoverable schedule
◦
recover을 하더라도 consistent였으면 좋겠다.
◦
recoverable한 것은 각 트랜잭션 그것이 읽은 트랜잭션들이 커밋되고 나서 커밋되야 recoverable한 것이다. → 즉 커밋의 순서가 dirty read를 읽은 애가 반영이 안 되게끔 해야함
•
Avoiding cascading rollback schedule
◦
cascading rollback이 없어도 되게끔 한다.
◦
사실 어떻게 하냐 dirty data를 읽지 않게끔 하면 됨.
◦
트랜잭션은 오직 커밋된 값만 읽게끔 하면 된다.
•
Strict locking
◦
스케쥴러가 락 기반이라면, strict locking이라면 x-lock을 트랜잭션이 커밋되거나 취소되기 전까지 놓아주지 않는 것이다.
◦
이러면 ACR을 무조건 지키게 된다.
◦
모든 strict locking은 serializable해야함.
•
ACR 중에서 serializable이 아닌 것도 있다.
◦
어떤 케이스일까…
•
lockable DB element가 블럭 단위인 경우
◦
uncommit transaction으로 쓰여진 경우 main memory에 Pineed 되고 disk에 안 쓰게끔 해야함
◦
롤백할 때는 간단하게 A를 무시하면 된다.
•
만약 튜플 같이 fraction of block인 경우, 몇 가지 옵션이 있다.
◦
disk에서 원래 값을 읽어서 buffer에 값을 수정하거나
◦
log가 undo이거나 undo/redo 이라면 log에서 값을 얻어라.
◦
트랜잭션에 의해 변경된 값을 따로 로그로 기록해놔야한다.

Deadlocks

Detection

•
Wais for graph
◦
어떤 트랜잭션이 어떤 자원을 기다리고, 이 자원이 누구에 의해 잡혀있는지를 확인
◦
사이클이 있다면 데드락이 있는거임
◦
데드락 예방하려면 롤백해야한다.
•
방지하는 방법
◦
데이터베이스를 전부 순서를 매기면 된다.
◦
만약 모든 트랜잭션이 아이템에 대해 순서대로 락을 요청한다면 데드락이 없다.
◦
모든 사람이 A→B로 락을 걸 것이기 때문.
◦
realistic 하지 않다.
•
timeout
◦
타임아웃 시간을 정해야하는데 정하기가 쉽지 않다.
•
Timestamps
◦
각 트랜잭션을 timestamp와 엮는것이다.
◦
wait-die scheme
▪
ts(T) < ts(U)면 T가 U를 기다린다.
▪
아니라면 T는 죽는다.
▪
즉 요청했을 때, 기다려야하는 놈이 어리면 죽는 구조
▪
롤백하고 다시 시작하면 같은 timestamp를 가지고 시작함
▪
결국 old enough가 되면 기아 상태가 해결이 되고 complete 될 것임.
◦
wound-wait scheme
▪
Ts(T) < Ts(U)라면 T가 U를 해친다.
▪
주로 wound는 치명적이지만 U는 rollback이 되고, 락을 준다.
▪
만약에 wound되는 시점에 끝났다면 아무것도 하지 않음
▪
T가 더 늙었다면 그냥 기다린다.
▪
즉 요청하는 놈이 어리면 해쳐서 빼앗고, 아니라면 그냥 기다림
◦
비교
▪
wait-die vs wound-wait
•
wait-die: 롤백이 자주 일어남, 하지만 transaction은 덜 일한 상태일 거임
◦
젊은 트랜잭션이 요청하면 죽으니까, 비용이 적게 들고, 더 많이 일어남
•
wound-wait: 롤백이 자주 일어나진 않지만, 그래도 뭔가 일은 더 한 상태일것
◦
늙은 트랜잭션이 젊은 걸 abort함. 다친 트랜잭션이 많이 일한 상태일 수 있음
▪
이런 방식과 waits for graph
•
일단 이런 방식이 구현하기가 더 쉽지만, wait for graph가 더 정확하게 deadlock을 탐지한다.

Prevention