제 19 장 데이터베이스에서 동시성 제어를 위한 프로토콜에 대한 개요

Slides:



Advertisements
Similar presentations
DB 후루룩 & ONE EYED JACK Collaboration_ ★. 다중 사용자 환경에서 둘 이상의 트랜잭션이 동시에 접속하여 해당 연산을 수행할 때, 문제 점이 전혀 발생하지 않도록 트랜잭션의 수행 을 적절히 제어해 주는 것을 말함. DBMS 예금 입출금 예금.
Advertisements

컴퓨터와 인터넷.
UNIX 운영 체제의 설계 - Chapter 4. 파일의 내부 표현
제 19장 트랜잭션 처리를 위한 개념 경북대학교 컴퓨터과학과 박 영철.
9장. 트랜잭션 트랜잭션(transaction) 항공기 예약, 은행, 신용 카드 처리, 대형 할인점 등에서는 대규모
2장. 프로그램의 기본 구성. 2장. 프로그램의 기본 구성 2-1"Hello, World!" 들여다 보기 /* Hello.c */ #include int main(void) { printf("Hello, World! \n"); return 0;
Java로 배우는 디자인패턴 입문 Chapter 5. Singleton 단 하나의 인스턴스
Chapter 14 Wireless LAN.
연결리스트(linked list).
제 9 장 구조체와 공용체.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
CUDA Setting : Install & Compile
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
Fundamentals of Database Systems R. A. Elmasri and S. B. Navathe
12장 데이터 읽기 일관성과 락.
Windows Server 장. 사고를 대비한 데이터 백업.
윤성우의 열혈 C 프로그래밍 윤성우 저 열혈강의 C 프로그래밍 개정판 Chapter 12. 포인터의 이해.
테이블 : 데이터베이스를 구성하는 요소로 같은 성격에 정보의 집합체. 레코드 : 하나의 정보를 가지고 있는 컬럼의 집합체
오브젝트 조합 회로 IT CookBook, VHDL을 이용한 디지털 회로 입문.
07 그룹 함수 그룹 함수의 개념 그룹 함수의 종류 데이터 그룹 생성 HAVING 절.
Fundamentals of Database Systems R. A. Elmasri and S. B. Navathe
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
제 6장 트랜잭션 트랙잭션 동시성 제어 복구.
                              데이터베이스 프로그래밍 (소프트웨어 개발 트랙)                               퍼스널 오라클 9i 인스톨.
10 장 데이터 링크 제어(Data Link Control)
Sungkyunkwan University OS Project Dongkun Shin
제 19 장 (Oracle) 오라클에서 동시성 제어 (MVCC)
사용자 함수 사용하기 함수 함수 정의 프로그램에서 특정한 기능을 수행하도록 만든 하나의 단위 작업
프로그래밍 개요
어서와 C언어는 처음이지 제14장.
7가지 방법 PowerPoint에서 공동 작업하는 다른 사용자와 함께 편집 작업 중인 사용자 보기
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
27장. 모듈화 프로그래밍.
8장. 상호 배타적 집합의 처리.
뇌를 자극하는 Windows Server 2012 R2
15장 컬렉션 프레임워크 Section 1 컬렉션 프레임워크의 개요 Section 2 리스트 Section 3 셋
USN(Ubiquitous Sensor Network)
3D 프린팅 프로그래밍 01 – 기본 명령어 강사: 김영준 목원대학교 겸임교수.
8장 쿠키와 세션 한빛미디어(주).
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
9장. 트랜잭션 트랜잭션(transaction) 항공기 예약, 은행, 신용 카드 처리, 대형 할인점 등에서는 대규모
Chapter 03. 관계 데이터베이스 설계.
20 장 네트워킹과 인터네트워킹 장치 20.1 리피터(Repeaters) 20.2 브리지(Bridges)
ARM Development Suite v1.2
10 장 데이터 링크 제어(Data Link Control)
10 장 데이터 링크 제어(Data Link Control)
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
Fundamentals of Database Systems R. A. Elmasri and S. B. Navathe
14강. 세션 세션이란? 세션 문법 Lecturer Kim Myoung-Ho Nickname 블스
CHAP 21. 전화, SMS, 주소록.
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
알고리즘 알고리즘이란 무엇인가?.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
제 8 장 ER-관계 사상에 의한 관계 데이타베이스 설계
01. 분산 파일 시스템의 개요 네트워크에 분산된 파일을 사용자가 쉽게 접근하고 관리할 수 있게 해준다.
JSP Programming with a Workbook
멀티미디어시스템 제 5 장. 멀티미디어 데이터베이스 개념 IT응용시스템공학과 김 형 진 교수.
함수, 모듈.
11장 배열 1. 배열이란? 1.1 배열의 개요 1.2 배열의 선언과 사용.
9 브라우저 객체 모델.
ER-관계 사상에 의한 관계데이터베이스 설계 충북대학교 구조시스템공학과 시스템공학연구실
제 4 장 Record.
10주 MariaDB에서 트랜잭션 지원 및 동시성 제어 기능
 6장. SQL 쿼리.
임시테이블과 테이블변수 SQLWorld Study Group - 최명환 -.
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
7 생성자 함수.
6 객체.
ARP.
Presentation transcript:

제 19 장 데이터베이스에서 동시성 제어를 위한 프로토콜에 대한 개요 제 19 장 데이터베이스에서 동시성 제어를 위한 프로토콜에 대한 개요 Fundamentals of Database Systems R. A. Elmasri and S. B. Navathe

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

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

Fundamentals of Database Systems 19.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) 연산을 수행하지 않는다. Ch19 Fundamentals of Database Systems

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

19.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) 연산을 수행하지 않는다. Ch19 Fundamentals of Database Systems

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

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

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

Fundamentals of Database Systems 19.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) 그림 19.5 교착상태의 예. (a) 교착상태에 있는 T1′과 T2′의 부분 스케줄.   (b) (a)에 있는 부분 스케줄에 대한 대기 그래프. Ch19 Fundamentals of Database Systems

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

Fundamentals of Database Systems 19.1.3 교착상태와 기아현상의 처리 (cont.) 교착 상태 방지 프로토콜 (deadlock prevention protocol) 타임스탬프를 필요로 하지 않는 방법 비대기 (no waiting) 알고리즘 트랜잭션이 로크를 획득할 수 없을 경우에는 교착상태가 실제로 발생할 것인지 발생하지 않을 것인지 확인하지 않고 그 트랜잭션을 즉시 철회시키고 일정시간이 경과되면 재시작시킨다. 신중 대기 (cautious waiting) 알고리즘 트랜잭션 Ti가 항목 X에 로크를 걸려고 시도하는데 다른 트랜잭션 Tj가 상충되는 모드로 X에 이미 로크를 보유하고 있다고 하자. 신중 대기 규칙은 다음과 같이 동작한다. Tj가 블록(block)된 상태가 아니면 (로크된 다른 항목을 기다리지 않으면) Ti는 블록되고 대기한다. 그렇지 않으면 Ti를 철회시킨다. Ch19 Fundamentals of Database Systems

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

Fundamentals of Database Systems 19.2 타임스탬프 순서에 기반을 둔 동시성 제어 기법 19.2.1 타임스탬프(Timestamps) 19.2.2 타임스탬프 순서(Timestamp Ordering) 알고리즘 Ch19 Fundamentals of Database Systems

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

Fundamentals of Database Systems 19.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를 성공적으로 기록한 가장 최근의 트랜잭션이다. Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.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) 중 큰 값으로 설정한다. Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.2.2 타임스탬프 순서 알고리즘 (cont.) 엄격한 타임스탬프 순서(Strict Timestamp Ordering) 트랜잭션 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) 중 큰 값으로 설정한다. Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.2.2 타임스탬프 순서 알고리즘 (cont.) Thomas의 쓰기 규칙 1. read_TS(X) > TS(T)이면 T를 철회하고 복귀시키고 그 연산을 거부한다. 2. write_TS(X) > TS(T)이면 쓰기 연산을 수행하지 않는다. 그러나,  트랜잭션 T의 수행은 계속한다. 3. 1과 2의 조건이 모두 만족되지 않으면 T의 write_item(X) 연산을 수행하고 write_TS(X) 를 TS(S)로 설정한다. 충돌 직렬가능성을 보장하지 않음 Ch19 Fundamentals of Database Systems

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

Fundamentals of Database Systems 19.3.1 타임스탬프 순서에 기반을 둔 다중버전 기법 각 데이터 항목 X에 대해 여러 버전 X1, X2, ..., Xk를 유지한다. 각 버전에 대해 버전 Xi의 값과 다음의 두 가지 타임스탬프를 유지한다. read_TS(Xi): Xi의 읽기 타임스탬프를 나타내며, 버전 Xi를 성공적으로 읽은 트랜잭션들의 타임스탬프 중 가장 큰 타임스탬프를 가진다. write_TS(Xi): Xi의 쓰기 타임스탬프를 나타내며, 버전 Xi의 값을 쓴 트랜잭션의 타임스탬프를 가진다. 직렬가능성을 보장하기 위해서 다음의 두 가지 규칙을 사용한다. 트랜잭션 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) 값 중 큰 값으로 설정한다. Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.3.2 보증 로크를 사용한 다중버전 2단계 로킹 항목에 대해 읽기(read), 쓰기(write), 보증(certify)의 3가지 로킹 모드 LOCK(X)의 상태 ‘읽기 로크(read locked)’, ‘쓰기 로크(write locked)’, ‘보증 로크(certify locked)’, ‘로크 해제(unlocked)’ READ WRITE CERTIFY READ WRITE CERTIFY yes yes no yes no no no no no 그림 19.6 로크 호환성 테이블들. Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.3.2 보증 로크를 사용한 다중버전 2단계 로킹(2) 각 항목은 x 에 대하여 두개의 버전을 둘 수 있다. 하나의 버전은 항상 완료된 트랜잭션이 쓰기를 수행한 것이어야 한다. 두번째 버전 X′은 어떤 트랜잭션 T가 항목 X에 대해 쓰기 로크를 획득할 때 생성된다. T가 쓰기 로크를 보유하고 있는 동안에도 다른 트랜잭션들은 완료된 버전 X를 계속 읽을 수 있다. 트랜잭션 T는 완료된 버전 X의 값에 영향을 미치지 않고 원하는 대로 X′의 값을 갱신할 수 있다. 트랜잭션 T가 완료할 준비가 되면 완료하기 전에 현재 쓰기 로크를 보유하고 있는 모든 항목들에 대하여 보증 로크를 획득해야 한다. 보증 로크는 읽기 로크와 호환성이 없다. 따라서, 트랜잭션 T가 보증 로크를 얻기 위해서는 T가 쓰기 로크를 보유하고 있는 항목들을 읽고 있는 다른 트랜잭션들의 로크가 해제될 때까지 트랜잭션 T의 완료가 지연되어야 한다. 보증 로크(이는 일종의 배타적 로크이다)를 획득하면 그 데이타 항목의 완료된 버전 X는 버전 X′의 값으로 설정되고 버전 X′은  폐기되며 그리고 나서 보증 로크가 해제된다. Ch19 Fundamentals of Database Systems

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

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

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

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

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

Fundamentals of Database Systems 19.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의 로크를 해제할 수 있다. Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.6 인덱스에서 동시성 제어를 위하여 로크를 사용 인덱스 탐색을 실행할 때 (읽기 연산), 루트에서 하나의 리프에 이르는 트리 상의 경로를 통과한다. 일단 그 경로에서 하위 레벨의 노드를 접근하면, 그 경로에서 상위 레벨의 노드는 다시 사용되지 않을 것이다. 따라서, 자식 노드에 읽기 로크를 잡게 되면, 부모 노드에 대한 로크는 해제될 수 있다. 삽입을 위한 보수적인 접근 방식은 루트 노드에 배타적 모드로 로크를 거는 것이고 그리고 나서, 루트의 적절한 자식 노드를 접근하는 것이다. 만일 그 자식 노드가 가득 차지 않았다면 루트에 대한 로크는 해제될 수 있다. 보다 낙관적인 방법은 루트로부터 리프 노드 직전의 노드들에게는 공유 로크들을 요구하고 잡으며 리프 노드에는 배타적 로크를 잡는 것이다. 만일 삽입으로 인하여 리프가 분할되면 삽입은 상위 레벨의 노드들에게 전파될 것이다. 그러면, 상위 레벨의 노드들에 잡은 로크들은 배타적 모드로 상승될 수 있다. Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.7 기타 동시성 제어 쟁점 19.7.1 삽입, 삭제, 팬텀 레코드(phantom record) 19.7.2 대화식 트랜잭션 19.7.3 래취(Latch) Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.7.1 삽입, 삭제,팬텀 레코드 삽입 연산: 데이타 항목이 생성되고, 삽입 연산이 완료되기 전에는 다른 트랜잭션들이 그 데이타 항목을 접근할 수 없음 로킹 기법에서는 그 데이타 항목에 대한 로크가 생성되고 배타적(쓰기) 모드로 설정될 수 있다. 타임스탬프 기반을 둔 프로토콜에서는 새로운 데이타 항목의 읽기 타임스탬프와 쓰기 타임스탬프가 그 데이타 항목을 생성한 트랜잭션의 타임스탬프로 설정된다. 삭제 연산: 기존 데이타 항목에 대해 적용 로킹 프로토콜에서는 트랜잭션이 데이타 항목을 삭제하기 전에 그 데이타 항목에 대해 배타적(쓰기) 로크를 획득해야 한다. 타임스탬프 순서 프로토콜에서는 트랜잭션이 데이타 항목을 삭제하도록 허용하기 전에 그 트랜잭션보다 나중에 생성된 어떠한 트랜잭션도 그 데이타 항목을 읽거나 쓰지 않았음을 보장해야 한다. 팬텀 문제 어떤 트랜잭션 T가 삽입하고 있는 새로운 레코드가 다른 트랜잭션 T’에 의해 접근하는 레코드들의 집합이 만족시키는 조건을 만족할 때 발생 가능(인덱스 로킹, 프레디키트 로킹으로 해결) Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.7.2 대화식 트랜잭션 대화식 트랜잭션이 완료하기 전에 터미널 스크린과 같은 대화식 장치로부터 입력을 받고 결과를 출력할 때 문제 발생 트랜잭션이 완료할 때까지 트랜잭션이 스크린에 출력하는 것을 연기하는 것으로써 해결 Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.7.3 래취 짧은 기간동안 유지되는 로크를 보통 래취라고 한다 . 래취는 2단계 로킹과 같은 일반적인 동시성 제어 프로토콜을 따르지 않는다. 예를 들어, 버퍼에서 디스크로 페이지를 기록할 때 페이지의 물리적 무결성을 보장하기 위하여 래취를 사용할 수 있다. 페이지에 대한 래취를 획득한 뒤, 페이지를 디스크에 기록하고, 래취를 해제한다. Ch19 Fundamentals of Database Systems

Fundamentals of Database Systems 19.8 요 약 동시성 제어 기법 로킹 기법 타임스탬프 순서에 기반을 둔 동시성 제어 기법 다중버전 동시성 제어 기법 검증(낙관적) 동시성 제어 기법 데이타 항목의 단위크기와 다중 단위크기 로킹 필드, 레코드, 블록, 화일전체, 데이타베이스 전체 인덱스에서 동시성 제어를 위하여 로크를 사용 기타 동시성 제어 쟁점 대화식 트랜잭션과 래취 Ch19 Fundamentals of Database Systems