Massively Distributed Database Systems(Transaction Management)

Transaction management를 위한 4가지 속성(ACID Properties)

• Atomicity : Transaction이 부분적으로 끝나는 것 없이 끝나던지 아니면 실패했던지 둘 중에 하나로 동작하는 것. 좌석 예매시스템의 경우 Atomicity가 지켜지지 않으면 하나의 자리에 중복 예약이 될 수 있음
• Consistency : 서로 다른 데이터베이스 사이에 연관데이터들은 일관성을 유지해야 함
• Isolation : 여러 개의 Transaction이 동시에 수행되더라도 transaction사이에는 서로 영향을 주지 않아야 하며 수행이 끝난 뒤에도 consistency는 유지되어야 함
• Durability : 수행 중인 transaction이 전원이 나간다던지 에러가 발생한다고 해도 중간에 유실되지 않고 commit할 때까지 유지되고 있어야 함. 예를 들어, A가 B에게 100만원을 보냈는데 사용자에게는 100만원이 보냈다고 메시지가 갔는데 시스템상에서는 commit되지 않고 아직 버퍼상에 있는 상태에서 전원이 나갔을 경우 100만원을 보내는 state를 유지하고 있다가 commit해야 한다는 것임. 그렇지 않으면 사용자는 100만원을 보냈다고 알고 있지만 실제로는 수행되지 않았기 때문에 문제가 발생함

이러한 ACID 속성을 지키기 위해서는 Concurrency Control(Isolation, Consistency)과 Recovery(Atomicity, Durability)가 필요하다.

Concurrency Control preserves Isolation and Consistency

• Concurrency control을 위해서는 Serializability를 보장해야 함
• 스케줄이 Serializable한지 알기 위해서는 해당 스케줄을 실행한 결과와 그 스케줄을 serial하게 실행한 결과가 같아야 하는데, 좀 더 명확하게 아는 방법은 conflict graph에서 cycle이 발생하는지 여부를 체크하는 것임. Cycle이 발생하면 serializable하지 않은 것임
• Serializable하면 consistancy를 만족시키지만 역은 성립하지 않음
• 그렇다면 어떻게 해야 스케줄을 serializable하게 만들수 있는가? 두 가지 프로토콜이 있음. Two phase locking protocol과 Timestamp-based protocol
• Two phase protocol을 이해하기 위해서는 우선 Lock-based protocol을 이해할 필요가 있음. Concurrency를 위해서 데이터를 쓰거나 읽을 때 lock을 주는 프로토콜로, Exclusive (X)mode는 쓰기와 읽기 모두 lock을 거는 것이고 Shared (S)mode는 읽기만 lock을 거는 것임
• 이 transaction은 system으로부터 허가를 받아야 사용할 수 있는데, Distributed DBS에서는 주로 Majority Protocol을 사용해서 허가를 받음
• Majority Protocol은 해당 데이터가 여러 DB에 복제되어 있을 때 각 DB의 manager로부터 과반수 이상의 lock을 확보해야 최종적으로 이 transaction이 lock을 획득할 priority가 높아짐
• 다시 Two phase protocol로 돌아가서, two phase protocol은 growing phase와 shrinking phase로 구성됨
• Growing phase는 lock을 획득하는 단계고 shrinking phase는 lock을 푸는 단계임
• 그러니까 growing phase에서 priority에 따라 모든 lock을 다 걸고 transaction이 끝나면 차례대로 lock을 푸는 것임. 이 때 한꺼번에 lock을 동시에 풀어버릴 수도 있는데 이 때는 concurrency가 떨어질 수 있기 때문에 단계별로 lock을 푸는 것을 추천함

 

 

• 마냥 좋은 것 같지만, Deadlock의 위험이 있음. 이 프로토콜에서 Deadlock이 안생기도록 하지는 못하지만 detection은 할 수 있음
• Deadlock을 detection했을 때, centralized system이면 transaction 하나를 죽이면 그만이지만 distributed system에서는 cycle check가 어렵기 때문에 deadlock을 풀기가 좀 까다로움. Cycle을 찾는 알고리즘이 필요함

 

• Timestamp-based protocol은 간단히 말하면 transaction이 생길 때마다 timestamp를 부여하고, 스케줄이 serializable하도록 transaction을 abort한 후 다른 transaction이 끝나면 timestamp를 이용하여 복귀해서 수행하는 것. 음..아직 명확하지 않다.
• 우선 W-timestamp(Q)는 write를 하기 위한 가장 큰 timestamp이고 R-timestamp(Q)는 read를 하기 위한 가장 큰 timestamp라는 것을 알아야 함
• Read를 할 때는 transaction이 발행한 timestamp T를 W-timestamp(Q)와 비교를 해서 현재 쓰기가 진행되는지 아닌지를 체크해야 하는데, T가 W-timestamp(Q)보다 작으면 쓰기가 진행되고 있다고 인식을 하고 T는 W-timestamp(Q)의 값으로 대체한 후 rollback 함
• T가 W-timestamp(Q)보다 크면 read를 수행하고 R-timestamp(Q)를 갱신함
• Write를 할 때는 W-timestamp(Q)와 R-timestamp(Q)와 모두 비교를 해서 R보다 작으면 현재 읽기가 진행되고 있기 때문에 읽기 시간을 보장하기 위해서 시스템은 T를 더 이상 생성하지 않고 rollback함. W보다 작으면 W값을 저장한 후 rollback함. W보다 크면 write를 수행하고 W를 갱신함

 

• Timestamp를 쓰기 위해서는 clock이 중요한데, logical clock과 global physical clock이 있는데 logical clock를 주로 씀
• Logical clock은 정확한 시간은 아니지만 초기 시간과 순서를 알 수 있게 함

 

• 마지막으로, Distributed System에서 concurrency를 구현하기 위해서는 TM(Transaction Manager), Scheduler, DM(Data Manager)를 구현해야 하는데, TM은 Atomicity를 보장하고 Scheduler는 lock을 걸던지 timestamp를 발행하던지 하고, DM은 읽기/쓰기를 수행함

 

Recovery preserves Atomicity and Durability

• Transaction을 수행하다가 실패를 할 경우에는, 처음으로 되돌리던지 아니면 끝까지 수행을 하도록 만들어야 함
• 처음으로 되돌릴 때 Recovery를 사용함. Transaction을 처음으로 되돌리는 경우는 transaction 자체 에러나 deadlock과 같은 system 에러가 있을 수 있고, 전원이 나가던지 하드웨어 또는 소프트웨어 문제인 system crash가 있을 수 있고 disk 자체의 문제일 수 있음
• Recovery 알고리즘은 transaction이 진행되는 동안 log를 기록하여 recovery를 준비하고 만약 failure가 발생하면 log기록에 따라 recovery를 수행함
• Recovery에서 Atomicity를 보장하려면 Log-based recovery가 필요함.
  • <T_i, Start>, and <T_i, Commit>
  • < T_i, X, V₁, V₂ >
• 두 가지 방법론이 있는데, 모든 modification을 로그로 기록하고 commit이 되면 한꺼번에 업데이트하는 Deferred database modification이 있고 즉각즉각 업데이트하는 immediate database modification이 있음
• Deferred database modification에서 failure가 발생하면 <T_i, Start> 지점으로 찾아가서 다시 실행하고 해당 transaction log는 삭제함
• Stable storage에서 failure이 발생하면 다른 액션을 취할 필요 없이 transaction이 commit 되는 순간 자동으로 redo가 실행되기 때문에 걱정할 필요 없음
• Immediate Database Modification에서는 transaction이 일어난 순서대로 undo를 실행하여 원래 값을 복원하고 redo를 실행하여 transaction을 재 실행함
• 그런데 만약 롤백을 할 때 용량이 큰 경우 commit 포인트를 찾는데 시간이 오래걸리기 때문에 중간중간 check point를 삽입함
• 그리고 이 operation은 Idempotent하게 수행되어야 함