[Database] 12 Transaction Processing

intro

• DBMS에는 여러 종류가 있다.

single user vs multi-user DBMS

• single user DBMS : 1번에 1명의 사용자만 DBMS를 사용할 수 있다.
• multi-user DBMS : 동시에 여러명의 사용자가 DBMS을 사용하며, concurrent하게 사용한다.

• 오늘날 대부분의 DBMS는 multi-user이다.

multiprogramming의 관점

• multi-user 의 컴퓨터에서 database 접근은 multiprogramming의 관점에서 봐야한다.
• OS는 여러개의 프로세스의 PCB를 CPU에 빠른속도로 Dispatch하면서 프로그램을 concurrent하게 실행한다.

• single-cpu에서 프로세스의 concurrent execution은 실제로는 interleaved된다.
• interleaved concurrency라고 부른다.
  • 

• multiple-cpu에서는 pararrel processing이 가능하다.
• 

• 오늘날 DB의 병행성 제어 관련 이론은 interleaved concurrency의 관점에서 발전해왔다.

Trasaction

용어정의

• database 프로세싱의 프로그램 실행의 논리적인 단위를 구성한다.
• begin transaction과 end transaction(SQL COMMIT)으로 이루어진다.
• 읽기만하는 트랜젝션은 read-only transaction, 읽기와 쓰기를 동시에하는 트렌젝션은 read-write transaction이라고 불린다.
• 이런 트렌젝션들은 read_item, write_item과 같은 access operation으로 이뤄진다.

• read_item(X)
  • X를 가진 disk block의 주소를 찾는다.
  • main memory의 buffer로 disk block을 복사한다.
  • X를 프로그램 변수에 복사한다.

• write_item(X)
  • X를 가진 disk block의 주소를 찾는다.
  • main memory의 buffer로 disk block을 복사한다.
  • buffer에 프로그램 변수의 값을 작성한다.
  • buffer의 값을 disk의 값으로 저장한다.

• DBMS는 메인 메모리에 data buffer로 이뤄진 database cache를 유지한다.(속도를위해)
• 각 버퍼는 일반적으로 각 disk block을 들고있는데, 모든 buffer가 차지되면, buffer replacement policy를 통해 교체할 버퍼를 선택한다.
  • 일반적으로 사용되는 건 LRU(least recently used)를 사용한다.
• database cache의 각 버퍼가 dirty bit가 1로 되어있으면, 메인메모리에 올라온 이후에 수정되었다는 의미이므로, 보조저장장치인 HDD, SSD 등에 저장되어야한다는 것을 의미한다.

• 트랜젝션 T1과 T2가 있을때, 동시에 요청되었다고 생각해보자.
• 동시에 동일한 DB table을 접근하면 안되기때문에 순서를 보장해 처리할수도 있다고 생각할 수 있다.
• T1->T2, 혹은 T2->T1으로 순서를 보장해 serial scheduling을 하게되면, concurrency가 나쁘기 때문에,
  • interleaving concurrrency(병행성있게 처리하되 결과를 보정해주자)라는 아이디어가 생각나게된다
  • 그리고 DBMS는 이를 two-phase-locking을 통해 해결한다.

트랜젝션의 ACID 속성

• 트랜젝션의 이상적인 속성을 정의한다.

1. Atomicity
   • 트랜젝션은 프로세싱의 원자적인 단위이다.
   • All-or-Nothing으로 실행되어야한다.
   • Recovery Manager에 의해서 트랜젝션 도중 오류 발생 시, 트랜젝션의 원자성을 보장한다.

1. Consistency presevation
   • DB state의 consistency(일관성)을 유지해야한다.
   • 이는 프로그래머 혹은 recovery manager에 의해 수행된다.

1. isolation
   • 트랜젝션의 진행과정은 commit 전까지 다른 트렌젝션에게 보여서는 안된다.
   • 2PL과 같은 concurrency control에 의해 수행.

1. Durability(permanency)
   • 트랜젝션이 커밋되어 DB가 변경되면,
   • 이 변경사항은 이후의 오류에의해 잃어져서는 안된다.
   • recovery manager는 checkpoint에 모든 commit 사항을 DB에 작성한다.

mini-batch

• 아래와 같은 트랜젝션이 있다고 생각해보자.

EXEC SQL UPDATE ACCOUNTS 
set ACCOUNT_TOTAL = ACCOUNT_TOTAL * (1 + interest_rate);

• 위 트랜젝션은 1개이다.
• 1줄 이지만, 5000만개의 데이터를 처리한다고 가정했을때, 만약 중간에 오류가 나면 5000만개 중 진행됐던 모든 operation을 되돌려져야한다.
• 엄청 비효율적이므로, 대용량 데이터를 처리할때 다르게 처리해줘야한다.

mini-batch 예시

int done = 0; 
int max_account = 50000000;

while (done < max_account) 
{
	EXEC SQL BEGIN TRANSACTION; //1개 transaction 시작
		set account_total = account_total * (1 + interest_rate);
		where account_no between done + 1 to done + :stepsize;
	exec SQL UPDATE BATCH //어디까지 진행했는지 저장하는 변수, DISK에 물리적 저장.
		set done = done + :stepsize;
	exec sql commit;//transaction 1개 완료
	done = done + stepsize;
}

• 중간에 실패하더라도, exec sql commit이 된 곳까지는 실행을 보장한다.
• BATCH라는 디스크에 저장하는 변수를 통해 DBMS가 꺼져도 어디까지 진행했는지 데이터를 남게한다.

UNDO transaction 예시

EXEC SQL WHENEVER SQLERROR goto UNDO:
	EXEC SQL SET TRANSACTION
		read write
		diagnotic size 5
		isolation level serializable;
	EXEC SQL INSERT INTO EMPLOYEE(fname, lname, ssn, dno, salary)
		values('robert', 'smith', '991004321', 2, 35000);
	EXEC SQL UPDATE EMPLOYEE
		set salary = salary * 1.1 where dno = 2;
	EXEC SQL COMMIT;
	goto THE_END:
	UNDO:exec sql rollback;
	THE_END:......;

• 트랜젝션 수행 도중에 발생한 에러에 대해 goto UNDO를 통해 rollback을 수행하도록한다.

Concurrency Control

• 위와같은 트랜젝션 T1, T2가 있다고 가정하자.
• 각 트랜젝션은 atomic하게 처리되어야한다.
• 각 트랜젝션은 BEGIN SQL TRANSACTION으로 시작해 SQL COMMIT으로 끝난다.
• 여러개의 트랜젝션이 수행될때, concurrently하게 수행되면서 무결성을 보장하고, 처리량을 극대화해야한다.
• 그런데, 각 read, write operation을 critical section문제를 제외하고 생각했을때, concurrently수행에서 여러 문제가 발생한다.

concorruncy problems

lost update problem

• 두 트랜젝션이 동일한 데이터베이스 데이터에 interleaved된 방식으로 접근하려할때 문제가 발생한다.

• 

• 이 문제는 각 operation의 결과가 바로 disk에 반영되지 않음으로써 발생한다.
• T1과 T2 모두 80이라는 동일한 값을 불러온다는 문제가 있다.
• T1의 트랜젝션으로 X가 Update되었어야하지만, 그렇지 않았다.(lost update)
• T1의 트랜젝션은 T2의 것으로 overwritten되어버렸다.

temporary update problem

• Dirty read라고도 불린다.

• 

• 이 문제는 트랜젝션 도중에 실패할 경우에 발생한다.
• T1의 read-write operation이 종료되어 X의 값이 수정되고, T2는 수정된값으로 처리하는데,
• T1의 트랜젝션이 실패하면, 기존에 수정했던 X값이 모두 roll-back되어야하므로, T2의 트랜젝션은 틀린결과를 갖게된다.
• 이때 T2가 가진 X값을 temporarlity old value라고한다.

Two-Phase_Locking(2PL)

정의

• concurrency를 활용할때, 병행성을 이용해 처리량을 극대화하며 결과를 보장하기위한 알고리즘이다.
• 2PL의 구성요소
  1. multiple-mode locks
  2. serializability guaranting protocol

1. multiple-mode locks
   • binary lock이 최대 1개의 트랜젝션만 lock을 가질 수 있는데에 반해
   • 이 락은 read 목적의 락을 몇몇 트랜젝션이 가지도록할 수 있다.
   • read&write locks, shared/exclusive locks라고도 불린다.

1. serializability guaranting protocol
   • locking operation은 항상 unlocking operation에 앞서서 이뤄진다.
   • expanding phase : 모든 lock을 획득한다.
   • shrinking phase : 모든 lock을 unlock

필요한 이유

2PL이 아닌 트랜젝션들

1. 

• 위 그림은 트랜젝션이 T1->T2 혹은 T2->T1순으로 수행될때 결과를 말해준다.
• 순서에따라 다른 결과를 낳는 것을 볼 수 있다.

1. 

• 일정한 순서 없이 interleaved concurrency에 따라 트랜젝션을 수행한다.
• 2PL이 아니며, nonserialize하다.

2PL 트랜젝션 예시

• 위의 각 트랜젝션은 2PL이다.
• 스케쥴 상의 모든 트랜젝션이 2PL을 따르면 serializability를 보장한다.
• 단, 2PL의 경우에는 데드락 발생의 위험이 있어 이를 방지하는 프로토콜이 필요하다.
• 이런 프로토콜의 종류로는 deadlock prevention protocol과 deadlock detection등이 있다.