Fundamentals of Database Systems R. A. Elmasri and S. B. Navathe 제 15 장 동시성 제어 기법 Fundamentals of Database Systems R. A. Elmasri and S. B. Navathe © 2005 황규영 홍의경 음두헌 박영철 김진호 조완섭

Fundamentals of Database Systems 목 차 본 장에서는 동시에 수행되는 트랜잭션들의 고립성을 보장하기 위해서 사용되는 여러 가지 동시성 제어 기법을 논의한다. 이 기법들의 대부분은 직렬가능성을 보장하는 프로토콜(즉 규칙들의 집합)을 사용하여 스케줄들의 직렬가능성을 보장한다. 15.1 동시성 제어를 위한 2단계 로킹(Two-Phase Locking) 기법 15.2 타임스탬프 순서에 기반을 둔 동시성 제어 기법 15.3 다중버전 동시성 제어 기법 15.4 검증(낙관적) 동시성 제어 기법 15.5 데이타 항목의 단위크기와 다중 단위크기 로킹 15.6 인덱스에서 동시성 제어를 위하여 로크를 사용 15.7 기타 동시성 제어 쟁점 15.8 요약 Ch15 Fundamentals of Database Systems

2단계 로킹(Two-Phase Locking) 기법 15.1 동시성 제어를 위한 2단계 로킹(Two-Phase Locking) 기법 로크 하나의 로크(lock)는 데이타베이스 내에서 하나의 데이타 항목과 연관된 변수이고, 항목에 적용될 수 있는 가능한 연산들에 대해서 그 항목의 상태를 나타낸다. 일반적으로 데이타베이스 내의 각 데이타 항목마다 하나의 로크가 있으며, 이런 로크는 동시에 수행되는 트랜잭션들이 데이타베이스 내의 항목들을 접근하는 것을 동기화시키기 위한 수단으로 사용된다. 15.1.1 로크의 유형과 시스템 로크 테이블 15.1.2 2단계 로킹에 의한 직렬가능성 보장 15.1.3 교착상태와 기아현상의 처리 Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.1.1 로크의 유형과 시스템 로크 테이블 이진로크 (Binary Lock) 항목 X에 연관된 로크의 상태: LOCK(X) 로크가 걸린 상태(locked) 로크가 해제된 상태(unlocked) 로크 연산 Lock_item(X) Unlock_item(X) 시스템 로크 테이블 각 엔트리: <데이타 항목이름, LOCK, 로크 보유 트랜잭션, 로크 대기 트랜잭션들> 모든 트랜잭션들은 아래의 규칙들을 준수해야 한다. 트랜잭션 T는 read_item(X) 또는 write_item(X) 연산을 수행하기 전에 반드시 lock_item(X) 연산을 수행해야 한다. 트랜잭션 T는 모든 read_item(X)와 write_item(X)연산을 끝낸 다음 unlock_item(X) 연산을 수행해야 한다. 트랜잭션 T가 이미 항목 X에 로크를 보유하고 있으면, lock_item(X) 연산을 수행하지 않는다. 트랜잭션 T가 항목 X에 로크를 보유하고 있지 않으면, unlock_item(X) 연산을 수행하지 않는다. Ch15 Fundamentals of Database Systems

15.1.1 로크의 유형과 시스템 로크 테이블(cont.) 공유 로크와 배타적 로크 항목 X에 연관된 로크의 상태: LOCK(X) 읽기 로크(read_locked) : 공유 로크(shared_lock) 쓰기 로크(write_locked) : 배타적 로크(exclusive_lock) 로크 해제(unlocked) 로크 연산 Read_lock(X) Write_lock(X) Unlock(X) 시스템 로크 테이블 각 엔트리: <데이타 항목이름, LOCK, 로크 보유 트랜잭션 수, 로크 보유 트랜잭션들, 로크 대기 트랜잭션들> Ch15 Fundamentals of Database Systems

15.1.1 로크의 유형과 시스템 로크 테이블(cont.) 모든 트랜잭션들은 아래의 규칙들을 준수해야 함 트랜잭션 T는 read_item(X) 연산을 수행하기 전에 반드시 read_lock(X) 또는 write_lock(X) 연산을 수행해야 한다. 트랜잭션 T는 write_item(X) 연산을 수행하기 전에, 반드시 write_lock(X) 연산을 수행해야 한다. 트랜잭션 T는 모든 read_item(X) 연산과 write_item(X) 연산을 끝낸 후에 반드시 unlock(X) 연산을 수행해야 한다. 트랜잭션 T가 항목 X에 대해 이미 읽기(공유) 로크나 쓰기(배타적) 로크를 보유하고 있으면, T는 read_lock(X) 연산을 수행하지 않는다. 이 규칙은 완화될 수 있다. 트랜잭션 T가 항목 X에 대해 이미 쓰기(배타적) 로크를 보유하고 있으면, T는 write_lock(X) 연산을 수행하지 않는다. 이 규칙은 완화될 수 있다. 트랜잭션 T가 항목 X에 대해 읽기(공유) 로크나 기록(배타적) 로크를 보유하고 있지 않다면, T는 unlock(X) 연산을 수행하지 않는다. Ch15 Fundamentals of Database Systems

15.1.1 로크의 유형과 시스템 로크 테이블(cont.) 로크 전환 (conversion of locks) 항목 X에 보유하고 있는 로크를 하나의 로크 상태로부터 다른 로크 상태로 전환하는 것 로크 상승(lock upgrade) 예: 트랜잭션 T가 read_lock(X) 연산을 수행하고 나서 나중에 write_lock(X) 연산을 수행 로크 하강(lock downgrade) 로크의 상승과 하강을 사용하려면 로크 테이블은 해당 항목에 대해 로크를 보유하고 있는 트랜잭션에 대한 정보를 저장하기 위해서 각 로크를 위한 레코드 구조에 트랜잭션 식별자를 포함시켜야 함 Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.1.2 2단계 로킹에 의한 직렬가능성 보장 2 단계 로킹 (Two-Phase Locking, 2PL) 프로토콜 확장단계(growing phase) 항목들에 대한 새로운 로크를 획득할 수 있지만 해제할 수 없다. 수축단계(shrinking phase) 이미 보유하고 있는 로크들을 해제할 수 있지만 어떤 새로운 로크를 획득할 수 없다. Note. 로크의 하강을 허용할 경우, 모든 로크의 하강이 수축단계에서 수행되어야 한다 스케줄에 있는 모든 트랜잭션들이 2단계 로킹 프로토콜을 준수하면, 그 스케줄은 직렬가능함이 보장되고 더 이상 스케줄의 직렬성을 검사할 필요가 없어짐 Ch15 Fundamentals of Database Systems

15.1.2 2단계 로킹에 의한 직렬가능성 보장(cont.) 2 단계 로킹의 변형 : 기본적(basic) 2PL의 변형 보수적(conservative) 2PL 또는 정적 (static) 2PL 트랜잭션이 수행을 시작하기 전에 그 트랜잭션의 읽기 집합(read set)과 쓰기 집합(write set)을 미리 선언함으로써 그 트랜잭션이 접근하려는 모든 항목들에 로크를 획득하도록 한다. 교착상태가 발생하지 않는 프로토콜이다. 엄격한(strict) 2PL 트랜잭션 T가 완료되거나 철회될 때까지 T가 보유한 배타적(쓰기) 로크들 중 어떠한 로크도 해제하지 않는다. 가장 널리 사용되는 프로토콜이다. 엄중한(rigorous) 2PL 트랜잭션이 완료되거나 철회될 때까지 그 트랜잭션의 어떠한 로크(배타적 로크이든지 혹은 공유 로크이든지)도 해제하지 않는다. Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.1.3 교착상태와 기아현상의 처리 교착 상태 두 개 이상의 트랜잭션들로 구성된 집합 안에 있는 각 트랜잭션 T가 그 집합 안에 있는 다른 트랜잭션 T′에 의해 로크된 어떤 항목을 기다릴 때 발생한다. read_lock(Y); Read_item(Y); write_lock(X); read_lock(X); Read_item(X); write_lock(Y); T1’ T2’ 시간 (a) (b) 그림 15.5 교착상태의 예. (a) 교착상태에 있는 T1′과 T2′의 부분 스케줄.   (b) (a)에 있는 부분 스케줄에 대한 대기 그래프. Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.1.3 교착상태와 기아현상의 처리 (cont.) 교착상태 방지 프로토콜 (deadlock prevention protocol) 보수적 2단계 로킹 방지 프로토콜에 의해 각 트랜잭션에게 필요한 로크를 미리 잡는 방법 데이타베이스에 있는 모든 항목들에 대해 미리 순서를 정해 두고, 여러 항목을 필요로 하는 트랜잭션은 미리 정의된 순서에 따라 로크를 획득하는 방법 타임스탬프 TS(T) 를 이용하는 방법 wait-die 알고리즘. TS(Ti) ＜ TS(Tj)이면(Ti가 Tj보다 먼저 시작되었다면) Ti는 대기한다. 그렇지 않으면(Ti가 Tj보다 나중에 시작되었다면) Ti가 철회되고 나중에 동일한 타임스탬프를 사용하여 Ti를 재시작시킨다. wound-die 알고리즘. TS(Ti) ＜ TS(Tj)이면(Ti가 Tj보다 먼저 시작되었다면) Tj를 철회시키고, 나중에 동일한 타임스탬프를 사용하여 Tj를 재시작시킨다. 그렇지 않으면 Ti는 대기한다. Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.1.3 교착상태와 지속로크의 처리(cont.) 교착상태 검출 (deadlock detection) 트랜잭션들이 동시에 동일한 항목을 접근하는 일이 거의 없을 경우에 좋은 해결책 대기 그래프를 구성한 후, 사이클의 존재 유무로 교착상태를 탐지함 희생자 선택(victim selection) 교착상태를 야기한 트랜잭션들 중 철회할 트랙잭션을 선택하는 것 순환적 재시작(cyclic restart) 철회된 트랜잭션이 재시작하면서 다시 교착상태에 빠지는 것 시간초과 (timeout) 시스템에서 정의한 시간초과보다 트랜잭션이 더 오래 대기하면 시스템은 그 트랜잭션이 교착상태에 빠져있다고 가정하고, 교착상태가 실제로 존재하는지 검사하지 않고 그 트랜잭션을 철회시킨다. 기아현상(starvation) 이 현상은 어떤 하나의 트랜잭션이 무한정 수행되지 않는 반면 시스템에 있는 다른 트랜잭션들은 정상적으로 수행될 때 발생한다. 방지법 : 공평한 대기 방식(fair waiting scheme)을 사용하는 것이다. 선착 선처리(first-come first-serve) 큐를 사용 Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.2 타임스탬프 순서에 기반을 둔 동시성 제어 기법 15.2.1 타임스탬프(Timestamps) 15.2.2 타임스탬프 순서(Timestamp Ordering) 알고리즘 Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.2.1 타임스탬프 타임스탬프 트랜잭션을 식별하기 위해 DBMS가 부여한다. 일반적으로, 타임스탬프 값은 트랜잭션들이 시스템에 들어온 순서대로 할당된다. 따라서, 타임스탬프를 트랜잭션의 시작 시간(transaction start time)으로 간주할 수 있다. 타임스탬프에 기반을 둔 동시성 제어기법은 로크를 사용하지 않으므로 교착상태를 발생시키지 않는다. Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.2.2 타임스탬프 순서 알고리즘 타임스탬프 순서(timestamp ordering, TO) 트랜잭션의 수행순서는 각 트랜잭션의 타임스탬프에 기반을 둠 타임스탬프 순서 알고리즘 타임스탬프 순서 기법에서는 스케줄이 트랜잭션들의 타임스탬프의 순서에 해당하는 특정 직렬 순서와 동치이다. 각 데이타베이스 항목 X에 대해 두 개의 타임스탬프 값들을 연관시킨다. read_TS(X): 항목 X의 읽기 타임스탬프(read timestamp)로서 항목 X를 성공적으로 읽은 트랜잭션들의 타임스탬프 중 가장 큰 값이다. 즉, read_TS(X) = TS(T)이고 여기서 T는 X를 성공적으로 읽은 가장 최근의(youngest) 트랜잭션이다. write_TS(X): 항목 X의 쓰기 타임스탬프(write timestamp)로서 항목 X를 성공적으로 기록한 트랜잭션들의 타임스탬프 중 가장 큰 값이다.  즉, write_TS(X) = TS(T)이고 여기서 T는 X를 성공적으로 기록한 가장 최근의 트랜잭션이다. Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.2.2 타임스탬프 순서 알고리즘 (cont.) 기본적 타임스탬프 순서(Basic Timestamp Ordering) 트랜잭션 T가 write_item(X) 연산을 수행하려고 할 경우: a. read_TS(X) > TS(T) 또는 write_TS(X) > TS(T)이면 T를 철회하고 복귀시키고 그 연산을 거부(reject)한다. b. a의 조건이 발생하지 않으면 T는 write_item(X) 연산을 수행하고 write_TS(X)를 TS(T)로 설정한다. 트랜잭션 T 가 read_item(X) 연산을 수행하려고 할 경우: a. write_TS(X) > TS(T)이면 T를 철회하고 복귀시키고 그 연산을 거부한다. b. write_TS(X) ≤ TS(T)이면 T의 read_item(X) 연산을 수행하고 read_TS(X)를 TS(T)와 현재의 read_TS(X) 중 큰 값으로 설정한다. Cascade rollback이 발생할 수 있음 Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.2.2 타임스탬프 순서 알고리즘 (cont.) 엄격한 타임스탬프 순서(Strict Timestamp Ordering) - skip 트랜잭션 T가 write_item(X) 연산을 수행하려고 할 경우: a. write_TS(X) < TS(T)이면 항목 X에 기록한 트랜잭션 T′(따라서 TS(T′) = write_TS(X))이 완료되거나 철회될 때까지 연기(delay)된다. b. a의 조건이 발생하지 않고 read_TS(X) > TS(T) 또는 write_TS(X) > TS(T)이면 T를 철회하고 복귀시키고 그 연산을 거부(reject)한다. c. a와 b의 조건이 발생하지 않으면 T는 write_item(X) 연산을 수행하고 write_TS(X)를 TS(T)로 설정한다. 트랜잭션 T 가 read_item(X) 연산을 수행하려고 할 경우: b. write_TS(X) > TS(T)이면 T를 철회하고 복귀시키고 그 연산을 거부한다. c. a와 b의 조건이 발생하지 않으면 T의 read_item(X) 연산을 수행하고 read_TS(X)를 TS(T)와 현재의 read_TS(X) 중 큰 값으로 설정한다. Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.3 다중버전 동시성 제어 기법 동시성 제어를 위한 어떤 프로토콜에서는 한 데이타 항목이 변경될 때 그 데이타 항목의 이전값을 보존한다. 이 방법들은 한 데이타 항목에 대해 여러 개의 버전, 즉 값들을 유지하기 때문에 다중버전 동시성 제어(multiversion concurrency control) 기법이라고 한다. 한 트랜잭션이 어떤 항목에 대한 접근을 요구할 때 가능하면 현재 수행 중인 스케줄의 직렬가능성을 유지하기 위해 적절한 버전이 선택되도록 한다. 이 기법의 아이디어는 다른 기법들에서는 거부될 일부 읽기 연산들이 직렬가능성을 유지하기 위해 항목의 이전 버전(older version)을 읽도록 함으로써 허용될 수 있다는 것이다. 트랜잭션이 어떤 항목에 쓰기 연산을 수행할 경우, 트랜잭션은 새로운 버전에 쓰기를 하고 그 항목의 이전 버전은 계속 보존한다. 15.3.1 타임스탬프 순서에 기반을 둔 다중버전 기법 15.3.2 보증 로크를 사용한 다중버전 2단계 로킹 Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.3.1 타임스탬프 순서에 기반을 둔 다중버전 기법 각 데이터 항목 X에 대해 여러 버전 X1, X2, ..., Xk를 유지한다. 각 버전에 대해 버전 Xi의 값과 다음의 두 가지 타임스탬프를 유지한다. read_TS(Xi): Xi의 읽기 타임스탬프를 나타내며, 버전 Xi를 성공적으로 읽은 트랜잭션들의 타임스탬프 중 가장 큰 타임스탬프를 가진다. write_TS(Xi): Xi의 쓰기 타임스탬프를 나타내며, 버전 Xi의 값을 쓴 트랜잭션의 타임스탬프를 가진다. 직렬가능성을 보장하기 위해서 다음의 두 가지 규칙을 사용한다. - skip 트랜잭션 T가 write_item(X) 연산을 수행하려 할 경우 X의 버전 i가 X의 모든 버전들 중 가장 큰 write_TS(Xi)를 가지고, write_TS(Xi)가 TS(T)보다 작거나 같고, read_TS(Xi) > TS(T)이면, 트랜잭션 T를 철회하고 복귀시킨다. 그렇지 않으면, X의 새로운 버전 Xj를 만들고 read_TS(Xj) = write_TS(Xj) = TS(T)로 설정한다. 트랜잭션 T가 read_item(X) 연산을 수행하려 할 경우, X의 모든 버전들 중 가장 큰 write_TS(Xi)를 가지면서, write_TS(Xi)가 TS(T)보다 작거나 같은 X의 버전 i를 찾는다. 그리고 나서, 트랜잭션 T에게 Xi의 값을 반환하고 read_TS(Xi)의 값을 TS(T)와 현재의 read_TS(Xi) 값 중 큰 값으로 설정한다. Ch15 Fundamentals of Database Systems

15.3.2 보증 로크를 사용한 다중버전 2단계 로킹 - skip Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.4 검증 (낙관적) 동시성 제어 기법 트랜잭션이 수행되고 있는 동안 어떠한 검사도 하지 않는다.  높은 동시성 제공 동시성 제어 프로토콜을 위한 세 가지 단계가 있다. 읽기 단계(read phase): 트랜잭션은 데이타베이스로부터 완료된 데이타 항목들의 값을 읽을 수 있다. 그러나, 갱신은 트랜잭션의 작업공간에 유지되는 데이타 항목들의 지역 사본(local copy)에 대해서만 적용된다. 검증 단계(validation phase): 트랜잭션 실행의 마지막에, 트랜잭션의 갱신들이 데이타베이스에 반영되더라도 직렬가능성이 위반되지 않는다는 것을 보장하기 위해 검사를 수행한다. 쓰기 단계(write phase): 검증 단계가 성공하면 트랜잭션의 갱신들이 데이타베이스에 반영되고, 그렇지 않으면 갱신들을 폐기하고 트랜잭션을 재시작한다. Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.5 데이타 항목의 단위크기와 다중 단위크기 로킹 데이타베이스 항목 데이타베이스 레코드 데이타베이스 레코드의 필드값 디스크 블록 화일 전체 데이타베이스 전체 단위크기는 동시성 제어 및 회복의 성능에 영향을 줄 수 있다. 이 절의 구성 15.5.1 로킹에서 단위크기의 고찰 (fine granularity vs. coarse granularity) 15.5.2 다중 단위크기(multiple granularity) 로킹 Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.5.1 로킹에서 단위크기의 고찰 데이타 항목의 크기가 커질수록 동시성의 정도는 낮아진다. 데이타 항목의 크기가 작을수록 더 많은 데이타 항목들이 존재한다. 로크 관리자(lock manager)가 다루어야 하는 활성(active) 로크가 많아진다. 높은 오버헤드(overhead) : 로크 테이블을 위한 많은 양의 저장공간이 필요하다. 최적의 데이타 항목의 크기 관련된 트랜잭션들의 유형에 의존 Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.5.2 다중 단위크기 로킹 그림 15.7. 다중 단위크기 로킹을 예시하는 단위크기 계층도(granularity hierarchy). db f1 f2 p11 p12 … p1n p21 p22 … p2n r111 … r11j r121 … r12j … r1n1 … r1nj r211 … r21k r221 … r22k … r2m1 … r2mk Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.5.2 다중 단위크기 로킹 (cont.) 그림 15.8 다중 단위크기 로킹을 위한 로크 호환성 행렬 IS IX S SIX X IS yes yes yes yes no IX yes yes yes yes no S yes yes yes yes no SIX yes yes yes yes no X yes yes yes yes no Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.5.2 다중 단위크기 단계 로킹 (cont.) 의도 로크(Intention Locks)에는 세 가지 형태가 있다. 의도-공유(IS) 로크. 이 로크는 공유 로크를 몇몇 후손 노드(들)에게 요구할 것이라는 것을 나타낸다. 의도-배타적(IX) 로크. 이 로크는 배타적 로크를 몇몇 후손 노드(들)에게 요구할 것이라는 것을 나타낸다. 공유-의도-배타적(SIX) 로크. 이 로크는 현재 노드가 공유 모드로 로크가 걸려 있으며 배타적 로크를 몇몇 후손 노드(들)에게 요구할 것이라는 것을 나타낸다. 다중 단위크기 로킹(MGL) 프로토콜은 아래의 규칙들로 구성된다. 로크 호환성(그림 15.8에 근거)을 준수하여야 한다. 어떤 모드이든지 간에 트리의 루트가 가장 먼저 로크되어야 한다. 트랜잭션 T는 노드 N의 부모 노드를 IS 혹은 IX 모드로 로크를 걸어 놓은 상태에서만, 노드 N에 S 혹은 IS 모드로 로크를 걸 수 있다. 트랜잭션 T는 N의 부모 노드를 IX 혹은 SIX 모드로 로크를 걸어 놓은 상태에서만, 노드 N에 X, IX, 혹은 SIX 모드로 로크를 걸 수 있다. 트랜잭션 T는 어떠한 노드의 로크도 해제하지 않는 경우에만 어떤 노드에 로크를 걸 수 있다(2PL 프로토콜을 준수하기 위함임). 트랜잭션 T는 노드 N의 어떠한 자식 노드들에 대해서도 로크를 잡고있지 않은 경우에 한하여 노드 N의 로크를 해제할 수 있다. Ch15 Fundamentals of Database Systems

Fundamentals of Database Systems 15.8 요 약 동시성 제어 기법 로킹 기법 타임스탬프 순서에 기반을 둔 동시성 제어 기법 다중버전 동시성 제어 기법 검증(낙관적) 동시성 제어 기법 데이타 항목의 단위크기와 다중 단위크기 로킹 필드, 레코드, 블록, 화일전체, 데이타베이스 전체 Ch15 Fundamentals of Database Systems