• 검색 결과가 없습니다.

제 18 장 분산 데이터베이스

N/A
N/A
Info
다운로드
Protected

Academic year: 2023

Share "제 18 장 분산 데이터베이스"

Copied!
82
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

제 18 장 분산 데이터베이스

분산 데이터 저장

네트워크 은폐

분산 질의 처리

분산 트랜잭션 모델

완료 규약

조정자 선택

동시성 제어

교착상태 처리

다중 데이터베이스 시스템

(2)

분산 데이터베이스 시스템

광역망 , 전화선 또는 근거리망 같은 매체를 통해 통 신하는 여러 컴퓨터에 데이터베이스가 저장된다 .

사용자에게는 단일 시스템으로 보인다 .

복잡한 질의를 처리한다 .

처리가 요청을 시작한 다른 사이트에서 이루어질 수 있다 .

트랜잭션 관리

자동으로 제공되는 질의 최적화

(3)

분산 데이터 저장

관계형 데이터 모델을 가정하자 .

중복 : 보다 빠른 검색과 고장에 대비해 시스템은 여 러 사이트에 저장된 데이터의 여러 사본을 유지한다 .

분할 : 릴레이션은 여러 단편으로 분할되어 서로 다 른 사이트에 저장된다 .

중복과 분할 : 릴레이션은 여러 단편으로 분할된다 ;

시스템은 그러한 각 단편의 동일한 여러 사본을 유지

한다 .

(4)

데이터 중복

릴레이션 또는 릴레이션의 단편이 두 개 이상의 사이 트에 저장되면 중복된다 .

릴레이션의 완전 중복은 릴레이션이 모든 사이트에 저장되는 경우이다 .

완전 중복 데이터베이스란 각 사이트에 데이터베이스

전체의 사본을 가지는 것이다 .

(5)

데이터 중복 ( 계속 )

중복의 장점 - 가용성 : 중복이 존재한다면 릴레이션 r 을 내 포하고 있는

사이트의 고장이 r 의 사용에 영향을 주지 않는다 . - 병렬화 : r 상의 질의가 여러 노드에서 병렬로 처리될 수 있다 . - 데 이터 전송의 감소 : r 의 사본을 내포하고 있는 각 사이트에서 릴레이션 r 이 지역적으로 사용 가능하다 .

중복의 단점 - 갱신 비용의 증가 : 릴레이션 r 의 각 사본이 갱신되어야 한다 . - 동시성 제어의 복잡성 증가 : 특수한 동시성 제 어 기법이

수행되지 않으면 상이한 사본에의 동시 갱신이 데이터의

불일치를 야기할 수 있다 .

(6)

데이터 분할

릴레이션 r 을 재구축하는데 충분한 정보를 내포한 단편 r

1

, r

2

, … r

n

으로 분 할

수평 분할 : r 의 각 튜플이 하나 이상의 단편에 배정된다 .

수직 분할 : 릴레이션 r 의 스키마가 여러 개의 작은 스키마로 분할된다 .

- 모든 스키마는 무손실 죠인 속성을 보장하도록 공통 후보 키 ( 또는 수퍼 키 ) 를 내포해야 한다 .

- tuple-id 라는 특수 애트리뷰트가 후보 키 역할을 하기 위해 각 스키마에 추가될 수 있다 .

단편들은 임의의 깊이로 연속 분할될 수 있다 . 수직 및 수평 분할이 혼합될 수 있다 .

예 : 다음과 같은 스키마를 가진 릴레이션 account Account-schema

(7)

account 릴레이션의 수평 분할

branch-name account-number balance Hillside

Hillside Hillside

A - 305 A - 226 A - 155

500 336 62 account 1

branch-name account-number balance Valleyview

Valleyview Valleyview Valleyview

A- 177 A- 402 A- 408 A- 639

205 10000 1123 750

(8)

deposit 릴레이션의 수직 분할

branch-name customer-name tuple-id

Hillside Hillside Valleyview Valleyview Hillside Valleyview Valleyview

Lowman Camp Camp Kahn Kahn Kahn Green

1 2 3 4 5 6 7

account-number balance tuple-id

A-305 A-226 A-177 A-402 A-155

500 336 205 10000 62

1 2 3 4 5

deposit1

(9)

분할의 장점

수평 : - 릴레이션에 병렬 처리 허용 - 튜플들 이 가장 빈번히 액세스되는 곳에 위치하도록

전역 테이블이 분리되도록 한다 .

수직 : - 정규화로 이루어질 수 있는 것보다 한층 더 분해한다 . - tuple-id 애트리뷰트는 수직 단편들의 효율적 인 죠인을

허용한다 .

- 릴레이션에 병렬 처리 허용

- 튜플의 각 부분이 가장 빈번히 액세스되는 곳에 저장 되도록 튜플을 분리한다 .

(10)

네트워크 은폐

시스템 사용자들로 하여금 데이터 항목이 분산 시스 템 내에 어떻게 어디에 저장되어 있는가에 대한 상세 사항을 알지 못하도록 하는 정도

릴레이션 내의 다음에 대한 은폐 문제를 고려해 보자 :

- 데이터 항목의 명명

- 데이터 항목의 중복

- 데이터 항목의 분할

- 단편과 중복의 위치

(11)

데이터 항목의 명명 - 평가 기 준

1. 각 데이터 항목은 시스템 전체에서 유일한 이름을 가져야 한다 .

2. 데이터 항목의 위치를 효율적으로 찾을 수 있어야 한다 .

3. 데이터 항목의 위치를 드러나지 않게 변경할 수 있어야 한다 .

4. 각 사이트는 새로운 데이터 항목을 자치적으

로 생성할 수 있어야 한다 .

(12)

중앙 집중 기법 - 이름 서버

구조 :

- 이름 서버는 모든 이름을 배정한다 .

- 각 사이트는 지역 데이터 항목을 기록 유지한다 .

- 사이트에서는 비지역 데이터 항목을 찾기 위해 이름 서버에 문의한다 .

장점 :

- 명명 평가 기준 1~3 을 만족한다 .

단점 :

- 명명 평가 기준 4 를 만족하지 않는다 .

- 이름 서버에 성능 병목의 가능성이 있다 .

- 이름 서버가 고장의 유일한 요소이다 .

(13)

별명의 사용

중앙 집중 기법에의 대안 : 각 사이트는 자신이 생성한 어떠 한 이름에 자신의 사이트 식별자를 붙인다 . 즉 , site1 7.account 처럼

- 유일한 식별자를 가지게 되고 중앙 집중과 관련한 문제가 해결된다 .

- 그러나 , 네트워크 은폐 달성은 실패다 .

해결책 : 데이터 항목에 대한 별명의 집합을 생성한다 ; 각 사이 트에 별명과 실제 이름과의 매핑을 저장한다 .

사용자는 데이터 항목의 물리적 위치를 모를 수 있으며 , 데이터

항목의 한 사이트에서 다른 사이트로 이동되더라도 영향을 받

지 않는다 .

(14)

별명의 사용 ( 계속 )

데이터 항목의 각 사본과 단편은 유일한 이름을 가져야 한 다 .

- 같은 데이터 항목의 사본들과 단편들을 결정하는데 후위 표기를 사용한다 .

- 같은 데이터 항목의 단편들 : “.f1”, “.f2”,…, “.fn”

- 같은 데이터 항목의 사본들 : “.r1”, “.r2”,…, “.rn”

site17.account.f3.r2

위는 account 의 단편 3 의 사본 2 를 의미한다 ; 이 항목은 사이트 17 에서 생성되었다 .

(15)

이름 변환 알고리즘

if name appears in the alias table then expression := map(name) else expression :=name;

function map(n)

if n appears in the replica table

then result :=name of replica of n;

if n appears in the fragment table

then begin result :=expression to construct fragment;

for each n in result do begin replace n in result with map(n);

end end

return result;

(16)

이름 변환 기법의 예

Hillside 지점 ( 사이트 S

1

) 의 사용자는 account 릴레이션의 지역 단편 account.f1 에 대해 local-account 라는 별명을 사용한다 .

이 사용자가 local-account 를 참조하면 , 질의 처리 부 시스템은 별명 테이블에서 local-account 를 찾아 S1.account.f1 으로 대치한 다 .

S1.account.f1 이 중복되었으면 , 시스템은 사본을 선택하기 위 해 중복 테이블을 참조해야 한다 .

이 사본이 분할되었으면 , 시스템은 릴레이션을 재구축하는 방법 을 알기 위해 분할 테이블을 검사해야 한다 .

그러나 , 일반적으로는 한 두개의 테이블만 참조하면 되므로 , 알

고리즘은 릴레이션의 어떤 조합의 연속적인 중복과 분할도 다룰

수 있다 .

(17)

은폐와 갱신

데이터 항목의 모든 사본이 갱신되고 영향 받는 모든 단편이 갱신되 도록 보장해야 한다 .

account 릴레이션에 다음 튜플의 삽입을 고려해 보자 : (“Valleyvie w”, A-733, 600)

account 의 수평 분할

account

1

= 

branch-name = “Hillside”

(account) account

2

= 

branch-name = “Valleyview”

(account)

- 술어 P

i

는 i 번째 단편과 관련된다 .

- 술어 P

i

를 튜플 (“Valleyview”, A-733, 600) 에 적용해 튜플이 i 번째 단편에 삽입되어야 할지를 테스트한다 .

- 튜플은 account

2

에 삽입된다 .

(18)

은폐와 갱신 ( 계속 )

deposit 를 deposit

1

과 deposit

2

로 수직 분할

튜플 (“Valleyview”,A-733,”Jones”,600) 은 두 개의 단편으로 분리되어야 한다 :

- 하나는 deposit

1

에 삽입되도록 - 하나는 deposit

2

에 삽입되도록

deposit 가 중복되면 , 튜플 (“Valleyview”,A-733, “Jones”,60 0) 은 모든 사본에 삽입되어야 한다 .

문제점 : deposit 가 동시에 액세스되면 , 한 사본이 다른 것

보다 먼저 갱신될 것이다 ( 동시성 제어 참조 ).

(19)

분산 질의 처리

중앙 집중시스템에서는 특정 전략의 비용 산정에 대한 주요 기준이 디스크 액세스의 수이다 .

분산 시스템에서는 다른 사항을 고려해야 한다 : - 네트워크를 통한 데이터 전송 비용

- 질의의 일부를 다른 사이트들이 병렬로 처리함으로써

얻는 성능 향상의 가능성

(20)

질의 변환

대수 질의를 단편상의 질의로 변환

- 단편들로부터 릴레이션 r 을 구축할 수 있어야 한다 .

- 릴레이션 r 을 단편들로부터 릴레이션 r 을 구축하 는 표현식으로 대치

질의 처리를 위한 사이트 선택

(21)

예제 질의

account 릴레이션의 아래와 같은 수평 분할을 고려해 보자 . account

1

=

branch-name = “Hillside” (account)

account

2

=

branch-name = “Valleyview” (account)

질의

branch-name = “Hillside” (account)

는 다음과 같이 된다 .

branch-name = “Hillside” (account1 U account2)

이것은 아래와 같이 최적화 된다 .

branch-name = “Hillside” (account1) U  branch-name = “Hillside” (account2)

(22)

예제 질의 ( 계속 )

acount

1

에는 Hillside 지점에 속한 튜플만을 가지고 있으므로 선택 연산을 제거할 수 있다 .

account

2

의 정의를 적용해 다음을 얻는다 .

branch-name = “Hillside”

(

branch-name = “Valleyview”

(account) )

이 표현식은 account 릴레이션의 내용에 관계없이 공 집합이다 .

최종 전략은 질의의 결과로 Hillside 사이트에서 acoun

t

1

을 돌려주는 것이다 .

(23)

단순 죠인 처리

세개의 릴레이션이 중복되지도 않고 분할되지도 않은 관계형 대수 표현식을 고려해 보자 .

account depositor branch

account 는 사이트 S

1

에 저장되었다 .

depositor 는 S

2

에

branch 는 S

3

에

사이트 S

l

에서 제기된 질의에 대해 , 시스템은 S

l

에 결과를 생성해

야 한다 .

(24)

가능한 질의 처리 전략

세 릴레이션의 모든 사본을 사이트 S

l

에서 지역적으로 전체 질의를 처리하는 전략을 선택한다 .

account 릴레이션의 사본을 S

2

로 보내 S

2

에서 temp

1

= account depositor 를 계산한다 .

S

2

에서 temp

1

을 S

3

로 보내 S

3

에서 temp

2

= temp

1

branch 를 계산 한다 . 결과 temp

2

를 S

l

로 보낸다 .

S

1

, S

2

, S

3

의 역할을 바꾸어 유사한 전략을 세운다 .

다음과 같은 요인을 고려해야 한다 : - 보내는 데이터의 양

- 사이트간의 데이터 블록 전송 비용

- 각 사이트에서의 상대적인 처리 속도

(25)

세미죠인 전략

r

1

을 사이트 S

1

에 저장된 스키마 R

1

을 가진 릴레이션이라 하자 . r

2

를 사이트 S

2

에 저장된 스키마 R

2

를 가진 릴레이션이라 하자 .

r

1

r

2

를 평가해 결과는 S

1

에 생성한다 .

1. S

1

에서 temp

1

R1

R2

(r

1

) 을 계산한다 . 2. S

1

에서 S

2

로 temp

1

을 보낸다 .

3. S

2

에서 temp

2

r

2

temp

1

을 계산한다 . 4. S

2

에서 S

1

으로 temp

2

를 보낸다 .

5. S

1

에서 r

1

temp

2

를 계산한다 . 이것이 r

1

r

2

의 결과이다 .

(26)

형식적 정의

r

1

과 r

2

의 세미죠인은 아래와 같이 표기한다 . r

1

r

2

이것은 다음과 같이 정의된다 :

R1

(r

1

r

2

)

따라서 , r

1

r

2

는 r

1

r

2

에 기여한 r

1

의 튜플만을 선택한다 .

앞장의 절차 3 에서 temp

2

= r

2

r

1

이다 .

여러 릴레이션의 죠인에 대해 , 위의 전략은 일련의 세

미죠인 절차로 확장될 수 있다 .

(27)

병렬화를 사용하는 죠인 전략

릴레이션 r

i

가 사이트 S

i

에 저장된 r

1

r

2

r

3

r

4

를 고려해 보 자 . 결과는 사이트 S

1

에 나타나야 한다 .

파이프 라인 - 죠인 전략

- r

1

을 S

2

로 보내 S

2

에서 r

1

r

2

를 계산한다 ; 동시에 r

3

를 S

4

로 보내 S

4

에서 r

3

r

4

를 계산한다 .

- S

2

는 (r

1

r

2

) 의 튜플이 생성되면 S

1

로 보낸다 ; S

4

는 (r

3

r

4

) 의 튜플을 S

1

로 보낸다 .

- (r

1

r

2

) 와 (r

3

r

4

) 의 튜플들이 일단 S

1

에 도달하면 ,

S

2

에서의 (r

1

r

2

) 계산과 S

4

에서의 (r

3

r

4

) 계산과

함께 (r

1

r

2

) (r

3

r

4

) 가 병렬로 계산된다 .

(28)

분산 트랜잭션 모델

트랜잭션은 여러 사이트에서 데이터를 액세스할 수 있다 .

각 사이트에는 다음과 같은 책임을 지는 지역 트랜잭션 매니저를 가 진다 ;

- 회복을 위한 로그의 유지 관리

- 해당 사이트에서 실행중인 트랜잭션의 동시 실행 조정에의 참여

각 사이트에는 다음과 같은 책임을 지는 트랜잭션 조정자를 가진다 . - 해당 사이트에서 기동하는 트랜잭션의 실행 시작

- 실행을 위해 부 트랜잭션을 적절한 사이트로의 분배

- 트랜잭션이 모든 사이트에서 완료되거나 중단될 수 있는 해당

사이트에서 기동한 각 트랜잭션 종료의 조정

(29)

트랜잭션 시스템 구조

TC

1

TM

1

TC

n

TM

n

트랜잭션 조정자

트랜잭션

매니저

(30)

시스템 고장 유형

분산 시스템에 유일한 고장 : - 사이트 고장

- 메시지 손실 - 통신선 고장 - 네트워크 분할

사이트가 물리적으로 어떻게 연결되는가의 구성은 다음 사 항으로 비교할 수 있다 :

- 설치 비용

- 통신 비용

- 가용도

(31)

시스템 고장 유형 ( 계속 )

부분적으로 연결된 네트워크는 모두가 아닌 일부 사이트 쌍 간에 직접 링크를 가진다 .

- 완전 연결 네트워크보다 설치 비용이 덜 든다 .

- 직접 연결되지 않은 두 사이트간에 메시지를

우회하는 통신 비용이 보다 높다 .

(32)

네트워크 위상

D F C

E A B

D F C

E A B A

B E D F C

A

B C

F D E

A

B

D F C

완전 연결 네트워크 부분 연결 네트워크

(33)

네트워크 위상 ( 계속 )

분할 시스템은 연결이 없는 둘 이상의 부 시스템으로 분리된다 .

트리 - 구조 : 설치 및 통신 비용이 낮다 ; 단일 링크의 고장으로 네트워크가 분할될 수 있다 .

링 : 분할이 발생하려면 적어도 두 개의 링크가 고장나야 한다 .

성형 :

- 단일 링크의 고장이 네트워크 분할을 야기하지만 , 분할들 중 하나는 단일 사이트만을 가지므로 단일 사이트 고장으로 취급 될 수 있다 .

- 통신 비용이 낮다 .

- 중앙 사이트의 고장은 시스템 내의 모든 사이트가 단절되는

결과를 가져온다 .

(34)

견고성

견고한 시스템은 다음을 만족해야 한다 : - 사이트 또는 링크 고장의 탐지

- 연산이 계속되도록 시스템의 재구성 - 처리기 또는 링크가 수리되면 회복

고장 유형의 처리

- 손실된 메시지의 재전송

- 확인 받지 않은 재전송은 링크 고장을 의미한다 ; 다른 우회로를 찾는다

- 다른 우회로를 찾는데 실패했다는 것은 네트워크 분할의 징후이다 .

네트워크 링크 고장과 사이트 고장은 일반적으로 분간할 수 없다 .

(35)

시스템 재구성 절차

중복된 데이터가 고장 난 사이트에 저장되었으면 , 질의가 고장 난 사이 트의 사본을 참조하지 못하도록 카타로그를 갱신한다 .

고장 난 사이트의 활동 트랜잭션들은 중단시켜야 한다 .

고장 난 사이트가 어떤 서브 시스템의 중앙 서버이면 , 새로운 서버를 결 정할 선거가 치러져야 한다 .

재구성 기법은 네트워크 분할의 경우에 정확히 수행되어야 한다 . 다음 은 피해야 한다 :

- 서로 다른 분할에서 둘 이상의 중앙 서버 선출 - 두개 분할 이상에서의 중복 데이터 갱신

일련의 트랜잭션으로 회복 절차를 표현한다 ; 동시성 제어 부 시

스템과 트랜잭션 관리 부 시스템이 적절한 재통합을 위해 서로 돕는다

.

(36)

완료 규약

사이트에 걸쳐 원자성을 보장하기 위해 완료 규약 이 사용된다 .

- 여러 사이트에서 실행되는 트랜잭션은 모든 사이 트에서 완료되든지 중단되어야 한다 .

- 트랜잭션이 한 사이트에서는 완료되고 다른 사이 트에서는 중단될 수 없다 .

2 단계 완료 (2PC) 규약이 널리 사용된다 .

3 단계 완료 (3PC) 규약은 보다 복잡하고 비용이 많

이 들지만 , 2PC 의 단점을 보완한다 .

(37)

2 단계 완료 규약

고장 - 중단 모델을 가정한다 - 고장난 사이트는 작업을 즉시 중단하고 다른 사이트에 잘못된 메시지를 보내는 것과 같은 위해를 야기하지 않는다 .

규약의 실행은 트랜잭션의 마지막 절차가 도달한 후 조정 자가 기동시킨다 .

규약에는 트랜잭션을 실행하는 모든 지역 사이트가 내 포된다 .

사이트 S

i

에서 시작한 트랜잭션을 T 라 하고 , S

i

의 트랜잭

션 조정자를 C

i

라 하자 .

(38)

단계 1: 의사 결정 획득

조정자는 모든 참가자에게 트랜잭션 Ti 의 완료 준비를 요청한다 . - Ci는 로그에 레코드 <prepare T> 를 추가하고 안정 저장 장치에 로그를 강제 출력한다 .

- T 를 실행한 모든 사이트에 prepare T 메시지를 보낸다 .

메시지를 받으면 , 해당 사이트의 트랜잭션 매니저는 트랜잭션을 완료할 수 있는가를 결정한다 .

- 할 수 없으면 , 레코드 <no T> 를 로그에 추가하고 Ci에 abort T 메시지를 보낸다 .

- 트랜잭션이 완료될 수 있으면 ,

* 로그에 레코드 <ready T> 추가

* T 에 대한 모든 로그 레코드를 안정 저장 장치에 강제 출력

(39)

단계 2: 의사 결정 기록

C

i

가 모든 참가 사이트로부터 ready T 메시지를 받으면 , T 는 완료 될 수 있다 ; 그렇지 않으면 , T 는 중단되어야 한다 .

조정자는 의사 결정 레코드 <commit T> 또는 <abort T> 를 로그에 추가하고 안정 저장 장치에 로그를 출력한다 . 그 레코드가 안정 저장 장치에 일단 도달하면 , 취소할 수 없다 ( 고장이 발생한다 할지라도 ).

조정자는 각 참가자에게 의사 결정 ( 완료 또는 중단 ) 을 알리는 메시지를 보낸다 .

참가자들은 지역적으로 적절한 행위를 취한다 .

(40)

고장 취급 - 사이트 고장

사이트 S

k

가 회복될 때는 , 고장 당시에 활동 트랜잭션들의 운명을 결정 하기 위해 자신의 로그를 검사한다 .

로그에 <commit T> 레코드를 포함한다 : 사이트는 redo(T) 를 실행한다 .

로그에 <abort T> 레코드를 포함한다 : 사이트는 redo(T) 를 실행한다 .

로그에 <ready T> 를 포함한다 : 사이트는 C

i

와 상의해 T 의 운명을 결정해야 한다 . - T 가 완료되었으면 , redo(T)

- T 가 중단되었으면 , undo(T)

로그에 T 에 관련한 제어 레코드를 포함하지 않는다 : C

i

로부터의 prepare T 메시지 에 응답하기 전에 S

k

가 고장 났음을 의미

- S

k

가 고장나면 , 그러한 응답을 할 수 없으므로 C

i

는 T 를 중단시켜야 한다 .

- S

k

는 undo (T) 를 실행해야 한다 .

(41)

고장 취급 - 조정자 고장

T 의 완료 규약 실행 중 조정자가 고장 나면 , 참가 사이트들이 T 의 운명을 결정해야 한다 :

어떤 활동 사이트가 자신의 로그에 <commit T> 레코드를 내포하고 있으면 , T 는 완료되어야 한다 .

어떤 활동 사이트가 자신의 로그에 <abort T> 레코드를 내포하고 있으면 , T 는 중 단되어야 한다 .

어떤 활동 사이트가 자신의 로그에 <ready T> 레코드를 내포하지 않으면 , 고 장난 조정자 C

i

가 T 를 완료하고자 결정할 수 없었던 것이다 . 따라서 , T 를 중 단시킬 수 있다 .

위의 어느 경우도 아니면 , 모든 활동 사이트는 자신의 로그에 <ready T> 레코드 를 가져야 하지만 별도의 제어 레코드는 없다 . 이러한 경우에 활동 사이트들은 C

i

가 회복할 때까지 기다려 결정을 찾아야 한다 .

블록킹 문제 : 활동 사이트들이 고장난 조정자가 회복할 때까지 기다려야 한다 .

(42)

고장 취급 - 네트워크 분할

조정자와 모든 참가자가 한 분할에 있으면 , 고장이 완료 규약에 어떤 영향도 미치지 못한다 .

조정자와 참가자들이 여러 분할에 속하면 :

- 조정자를 내포하고 있는 분할에 없는 사이트들은 조정자가 고장 났다고 생각하고 조정자 고장을 다루기 위한 규약을 실행한다 . * 아무런 해도 발생하지 않지만 , 사이트들은 여전히 조정자로부 터의 결정을 기다려야 한다 .

- 같은 분할에 있는 조정자와 사이트들은 , 조정자가 다른 분할 에 있는 사이트들이 고장 났다고 생각하고 통상적인 완료 규약을 따른다 .

* 아무런 해도 발생하지 않는다 .

(43)

회복과 동시성 제어

의심스런 트랜잭션은 <ready T> 를 가지지만 , <commit T> 또는 <ab

ort T>

어느 로그 레코드도 갖지 않는다 .

회복중인 사이트는 다른 사이트와 접촉해 그러한 트랜잭션의 완료 - 중단 상태를 결정해야 한다 ; 이것은 회복을 더디게 하고 블록의 가능 성이 있다 .

회복 알고리즘은 로그 내에 로그 정보를 기록할 수 있다 .

- <ready T> 대신에 <ready T,L> 을 기록한다 . L 은 로그가 기록될 때 T 가 가진 로크 리스트이다 ( 읽기 블록은 생략될 수 있다 ).

- 모든 의심스러운 트랜잭션 T 에 대해 , <ready T,L> 로그 레코드에 기록된 모든 로크가 다시 얻어진다 .

로크 재획득 후에 , 트랜잭션 처리가 재개될 수 있다 ; 의심스런 트랜

잭션의 완료 또는 복귀가 새로운 트랜잭션의 실행과 동시에 수행된다 .

(44)

3 단계 완료 규약

가정 :

- 네트워크 분할은 없다 .

- 어떤 시점에서 적어도 하나의 사이트는 활동해야 한다 .

- 기껏해야 K 사이트 ( 조정자와 참가자 포함 ) 가 고장 날 수 있다 .

단계 1 : 예비 의사 결정 획득 : 2PC 의 단계 1 과 동일

- 모든 사이트는 그렇게 하라는 통지를 받으면 완료할 준비를 한다 . - 2PC 하에서 각 사이트는 조정자로부터의 결정을 기다릴 의무가 있다 .

- 3PC 하에서 조정자의 고장에도 불구하고 예비 완료 결정의 지식이

완료하는데 사용될 수 있다 .

(45)

단계 2: 예비 결정의 기록

조정자는 자신의 로그에 결정 레코드 <abort T> 또는 <p

recommit T>

를 추가하고 안정 저장 장치에 출력한다 .

조정자는 각 참가자에게 결정 사항을 알리는 메시지를 보 낸다 .

참가자는 자신의 로그에 결정을 기록한다 .

- 중단 결정을 받으면 참가자는 지역적으로 중단한다 .

- 예비 완료 결정을 받으면 참가자는 <acknowledge T> 로

응답한다 .

(46)

단계 3: 데이터베이스에 결정 기 록

단계 2 에서 예비 완료일 때만 실행된다 .

조정자는 확인 응답을 수집한다 . K 개의 확인 응답을 받으면 조정자는 참가자들에게 <commit T> 메시지를 보 낸다 .

조정자는 자신의 로그에 <commit T> 레코드를 추가하고 안정 저장 장치에 레코드를 출력한다 .

조정자는 각 참가자에게 <commit T> 메시지를 보낸다 .

참가자들은 지역적으로 적절한 행위를 취한다 .

(47)

사이트 고장 취급

사이트 고장 . 회복시 참가하는 사이트는 자신의 로그를 검사해 다음을 수행한다 :

로그에 <commit T> 레코드를 포함한다 : 사이트는 redo(T) 를 실행한다 .

로그에 <abort T> 레코드를 포함한다 : 사이트는 undo(T) 를 실행한다 .

로그에 <ready T> 레코드를 포함하지만 , <abort T> 또는 <precommit T> 레코드가 없다 .

- Ci가 T 의 중단으로 응답하면 , 사이트는 undo(T) 를 실행 ( 그리고 <commit T> 레코드를 기록 ).

- Ci가 T 의 완료로 응답하면 , 사이트는 redo(T) 를 실행 ( 그리고 <commit T> 레코드를 기록 ).

- Ci가 T 의 사전 완료로 응답하면 , 사이트는 precommit T 메시지를 수령함으로부터 규약을 재개한다 ( 따라서 , 로그에 <precommit T> 를 기록하고 조정자에게 acknowledge T 메시지를 보낸다 ).

(48)

사이트 고장 취급 ( 계속 )

로그에 <precommit T> 레코드를 포함하지만 , <abort T>

또는 <commit T > 레코드는 없다 : 사이트는 Ci와 상의해 트랜잭션 T 의 운명을 결정한다 .

- Ci가 T 의 중단으로 응답하면 , 사이트는 undo(T) 를 실행 - Ci가 T 의 완료로 응답하면 , 사이트는 redo(T) 를 실행 - Ci 가 T 의 사건 완료로 응답하면 , 사이트는 이 시점에서 규약을 재개한다 .

로그에 트랜잭션 T 에 대한 <ready T> 레코드를 포함하지 않는다 : 사이트는 undo(T) 를 실행하고 <abort T>

레코드를 기록한다 .

(49)

조정자 고장 규약

1. 활동중인 참가 사이트들이 새로운 조정자 C

new

를 선택한다 . 2. C

new

는 각 참가 사이트로부터 T 의 지역 상태를 요청한다 . 3. C

new

를 포함해 각 참가 사이트는 T 의 지역 상태를 결정한다 .

완료 . 로그에 <commit T> 레코드를 내포

중단 . 로그에 <abort T> 레코드를 내포

준비 . 로그에 <ready T> 레코드는 내포하지만 , <abort T> 또는 <precommit T> 레코드가 없다 .

사전완료 . 로그에 <precommit T> 레코드는 내포하지만 , <abort T> 또는 <c ommit T> 레코드가 없다 .

비준비 . 로그에 <ready T> 도 <abort T> 레코드도 없다 .

고장이 나서 회복한 사이트는 자신의 상태를 결정할 때 자신의 로그 내 어떠 한 precommit 레코드도 무시해야 한다 .

4. 각 참가 사이트는 자신의 지역 상태를 C

new

에 보낸다 .

(50)

조정자 고장 규약 ( 계속 )

5. C

new

는 T 를 완료 또는 중단하든지 또는 3 단계 완료 규약을 재시 작할 것인지를 결정한다 :

참가 사이트 중 하나라도 완료 상태 => 완료

참가 사이트 중 하나라도 중단 상태 => 중단

참가 사이트 중 하나라도 사전 완료 상태이고 위의 두 가지 경우 를 가지고 있지 않음 => 불확정 상태에 있는 참가 사이트에 pre

commit

메시지를 보내고 , 그 시점에서 규약이 재개된다 .

모든 활동사이트가 불확정 상태 => 중단 . 적어도 n-k 개의 사

이트는 활동하므로 , 모든 참가자가 불확정 상태에 있다는 사실은

조정자가 <commit T> 메시지를 보내지 못해 어떤 사이트도 T

를 완료하지 못했음을 의미한다 .

(51)

조정자 선택

예비 조정자

- 실제 조정자가 고장 나면 , 조정자 역할을 할 지역적으로 충분한 정보를 유지하는 사이트

- 실제 조정자와 같은 알고리즘을 실행하고 같은 내부 상태 정보를 유지한다 .

- 조정자 고장으로부터 신속한 회복을 허용하지만 , 정상 처리 중 비용 부담이 있다 .

선거 알고리즘

- 고장시 새로운 조정자를 뽑는데 사용된다 .

- 예 : 골목대장 알고리즘 - 각 사이트가 다른 각 사이트에 메시지를

보낼 수 있는 시스템에 적용 가능

(52)

골목대장 알고리즘

사이트 S

i

가 요청한 후 시간 간격 T 내에 조정자로부터 응답이 없으면 , 조정자가 고장 난 것으로 가정한다 ; S

i

는 자신이 새로운 조정자로 선출되고자 한다 .

S

i

는 자신보다 큰 식별 번호를 가진 모든 사이트에 선거 메시지를 보내고 , S

i

는 시간 T 내에 이들 사이트로부터 응답을 기다린다

시간 T 내에 응답이 없으면 , i 보다 큰 번호를 가진 모든 사이트가 고장 난 것으로 가정한다 ; S

i

는 자신을 새로운 조정자로 선출한다 .

응답이 오면 , S

i

는 자기보다 큰 식별 번호를 가진 사이트가 선출되 었다는 메시지를 받을 때까지 시간 간격 T

동안 기다리기 시작한다 .

(53)

골목대장 알고리즘 ( 계속 )

어떤 메시지도 T 내에 없으면 , 높은 번호를 가진 사이트가 고장 났다고 가정해 S

i

는 알고리즘을 재가동한다 .

고장 난 사이트는 회복 후 , 즉시 같은 알고리즘을 실행 시킨다 .

높은 번호를 가진 활동 사이트가 없으면 , 현재 작은 번호를

가진 활동 조정자가 있다 하더라도 회복된 사이트는 자신이

조정자 사이트가 되었음을 작은 번호를 가진 모든 사이트에

게 통보한다 .

(54)

동시성 제어

분산 환경에서 사용하도록 동시성 제어 기법을 수 정한다 .

전역 트랜잭션의 원자성을 보장하기 위해 각

사이트가 완료 규약의 실행에 참여한다고 가정한

다 .

(55)

단일 로크 매니저 방법

시스템은 선택된 단일 사이트 (S

i

) 에 있는 단일 로크 매 니저를 유지한다 .

트랜잭션에서 데이터 항목의 로크를 필요로 하면 , S

i

에 로크 요청을 보내고 로크 매니저는 로크를 즉시 허용할 것인가를 결정한다 .

- 허용하면 , 로크 매니저는 요청한 사이트에 메시지를 보낸다 .

- 허용되지 않으면 , 메시지가 요청한 사이트에 보내져

허용될 수 있을 때까지 요청은 지연된다 .

(56)

단일 로크 매니저 방법 ( 계속 )

트랜잭션은 데이터 항목의 사본이 있는 사이트 중 어느 곳으로 부터도 데이터 항목을 읽을 수 있다 .

출력하는 경우는 , 데이터 항목의 사본을 가진 모든 사이트에 이루 어져야 한다 .

이 기법의 장점 : - 단순 구현

- 단순한 교착상태 처리

이 기법의 단점 :

- 병목 : 로크 매니저 사이트가 병목이 된다 .

- 취약성 : 로크 매니저 사이트가 고장 나는 경우의 취약성이 있다

.

(57)

다수 규약

각 사이트의 지역 로크 매니저가 해당 사이트에 저장된 데이터 항 목에 대한 로크와 해제 요청을 관리한다 .

트랜잭션에서 사이트 S

i

에 있는 비중복 데이터 항목 Q 에 로크를 원하면 , S

i

의 로크 매니저에 메시지를 보낸다 .

Q 가 양립할 수 없는 유형으로 로크 되었으면 , 요청은 허용될 때 까지 지연된다 .

로크 요청이 허용 될 때 , 로크 매니저는 요청이 허용되었다는 메 시지를 요청자에게 보낸다 .

로크와 해제가 더 이상 단일 사이트에서 이루어지지 않으므로 구

현이 더욱 복잡해지고 교착상태 처리가 복잡해진다 .

(58)

다수 규약 ( 계속 )

중복 데이터인 경우 , 앞의 기법보다 더욱 복잡해진다 .

- Q 가 n 개 사이트에 중복되면 , Q 가 저장된 n/2+1 개의 사이트에 로크 요청 메시지를 보내야 한다 .

- Q 의 사본 중의 다수에 로크를 얻지 못하면 , 트랜잭션은 Q 에 연산할 수 없다 .

- 데이터 항목을 출력할 때 , 트랜잭션은 모든 사본에 출력을 수행한다 .

로크 요청 처리에 2(n/2+1) 메시지가 필요하고 , 해제 요청 처리에 (n /2+1) 메시지가 필요하다 .

단일 항목에서 조차 교착상태의 가능성이 있다 . - 예를 들어 , 두 트랜잭션 각각이 어떤 데이터 항목 사본

중에 1/2 씩 로크를 가질 수 있다 .

(59)

편파 규약

다수 규약에서와 마찬가지의 각 사이트의 지역 로크 매니저는 그 러나 , 공유 로크 요청을 배타 로크 요청과는 달리 처리한다 .

- 공유 로크 . 트랜잭션에서 데이터 항목 Q 에 로크를 필요로 할 때 , Q 의 사본을 가지고 있는 한 사이트의 로크 매니저로부터 로크를 요청한다 .

- 배타 로크 . 트랜잭션에서 데이터 항목 Q 에 로크를 필요로 할 때 , Q 의 사본을 가지고 있는 모든 사이트의 로크 매니저로 부 터 로크를 요청한다 .

장점 - read 연산에는 비용이 적게 든다 .

단점 - 출력에는 추가 비용이 들고 교착상태 처리가 복잡하다 .

(60)

주 사본

하나의 사본을 정확히 한 사이트 (Q 의 주 사이트 ) 에만 있어 야 하는 주 사본으로 선택한다 .

트랜잭션에서 데이터 항목 Q 에 로크를 필요로 할 때 , Q 의 주 사이트에 로크를 요청한다 .

중복 데이터에 대한 동시성 제어가 비중복 데이터와 유사하게 처 리된다 - 구현이 단순하다 .

Q 의 주 사이트가 고장 나면 , 사본을 내포하고 있는 다른 사이

트가 활동중이라도 Q 를 액세스할 수 없다 .

(61)

타임스탬핑

각 사이트는 논리 계수기 또는 지역 시계를 사용해 유일 한 지역 타임스탬프를 생성한다 .

유일한 전역 타임스탬프는 유일한 지역 타임스탬프와 유 일한 사이트 식별자를 연결해 얻는다 .

유일한 지역 타임스탬프

유일한 전역

사이트 식별자

(62)

타임스탬핑 ( 계속 )

느린 시계를 가진 사이트는 적은 타임스탬프가 배정될 것 이다 => 트랜잭션이 손해를 본다 .

각 사이트 S

i

내에 유일한 지역 타임스탬프를 생성하는 논 리 시계 (LC

i

) 를 정의한다 .

타임스탬프 <x,y> 를 가진 트랜잭션 T

i

가 해당 사이트에 도달할 때마다 S

i

는 자신의 논리 시계를 증가시켜 x 가 LC

i

의 현재 값보다 더 크게 할 필요가 있다 .

이 경우 , 사이트 S

i

는 자신의 논리 시계를 x + 1 로 증가

시킨다 .

(63)

교착상태 처리

다음의 두 트랜잭션과 이력 사항을 고려해 보자 . T1 :write(X) T2: write(Y)

write(Y) write(X)

T

1

T

2

X-lock on X

write(X)

wait for X-lock on Y

X-lock on Y write(Y)

wait for X-lock on X

(64)

중앙 집중 방법

단일 사이트에 전역 대기 그래프를 구축하고 관리한다 : 교착 상 태 탐지 조정자

- 실제 그래프 : 알지는 못하지만 시스템의 실제 상태

- 구축 그래프 : 알고리즘 실행 중 제어기가 생성한 근사 그래프

전역 대기 그래프는 아래의 경우 구축될 수 있다 :

- 새로운 간선이 지역 대기 그래프에 삽입되거나 삭제될 때 - 지역 대기 그래프에 많은 변화가 발생했을 때

- 조정자가 순환 탐지를 호출할 필요가 있을 때

조정자가 순환을 찾으면 , 희생자를 선정해 모든 사이트에 알린다 .

사이트들은 희생 트랜잭션을 복귀시킨다 .

(65)

중앙 집중 방법 ( 계속 )

교착상태가 실제로 발생해 희생자를 선정하는 동안에 트랜 잭션중의 하나가 교착상태와는 관계없이 중단되어 불필요 한 복귀가 야기될 수 있다 .

불필요한 복귀는 전역 대기 그래프 내의 거짓 순환으로 부터 기인할 수 있다 ; 그러나 , 거짓 순환의 발생 가능성은 낮다 .

(66)

거짓 순환

T

1

T

2

T

1

T

3

T

1

T T

S1 S2

(67)

거짓 순환 ( 계속 )

앞 장의 그림에서 보인 상태로부터 시작한다 가정하자 .

1. T

2

가 S

1

에서 자원을 해제한다 ( 그 결과 , S

1

의 트랜잭션 매니 저에서 조정자로 delete T

1

T

2

메시지가 전송된다 ). 그리고 , 2. 사이트 S

2

에서 T

3

가 가진 자원을 T

2

가 요청한다 . ( 그 결과 , S

2

에서 조정자에게 insert T

2

 T

3

메시지를 보낸다 ).

delete

메시지 전에 insert 메시지가 먼저 도착했다고 가정하자 . 조정자는 아래와 같은 거짓 순환을 발견할 것이다 .

T

1

T

2

T

3

 T

1

위의 거짓 순환은 실제로는 결코 존재하지 않는 것이다 .

거짓 순환은 2 단계 로킹을 사용하면 발생할 수 없다 .

(68)

완전 분산 방법

각 사이트에는 지역 대기 그래프를 갖는다 : 시스템은 이들 그래프를 결합해 교착상태를 탐지한다 .

지역 대기 그래프

 전역 대기 그래프

Site 1

T

1

 T

2

 T

3

Site 2

T

3

 T

4

 T

5

Site 3

T

5

 T

1

(69)

완전 분산 방법 ( 계속 )

시스템 모델 : 트랜잭션은 한 사이트에서 실행되고 , 비지역 데이터를 액세스하기 위해 다른 사이트에 요청한다 .

각 사이트는 정상적인 유형으로 자신의 지역 대기 그래프를 유지한다 : Tj가 가진 자 원에 Ti가 로크를 기다리고 있으면 간선 Ti Tj가 존재한다 ( 유의 : Ti와 Tj는 비 지역일 수 있다 ).

추가로 , 아래와 같은 경우 사이트 Sk의 그래프에 Ti Tex가 존재한다 . (a) Ti가 사이트 Sk에서 실행 중이며 , 다른 사이트에서 이루어진 요청에 대한 응답을 기다리고 있다 .

(b) Ti는 사이트 Sk에서 비지역이며 , Sk에서 로크가 Ti에 허용되었다 .

이와 유사하게 , 아래와 같은 경우 사이트 Sk의 그래프 내에 Tex Ti가 존재한다 . (a) Ti가 사이트 Sk에서 비지역이며 , 사이트 Sk에 있는 데이터에 로크를

기다리고 있다 .

(b) Ti가 Sk에서 지역이며 , 외부 사이트로부터 온 데이터를 액세스했다 .

(70)

완전 분산 방법 ( 계속 )

중앙 집중 교착상태 탐지 - 중앙 교착상태 탐지기에 보내진 모든 그래 프 간선

분산 교착상태 탐지 - “ 경로 보내기” 알고리즘

어떤 사이트에서 교착상태의 가능성을 나타내는 T

ex

를 내포한 지역 순환 을 탐지하면 “경로 보내기” 알고리즘이 시작된다 .

사이트 S

i

에 다음과 같은 순환이 있다고 하자 . T

ex

T

i

T

j

…. T

n

T

ex

그리고 사이트 S

j

의 어떤 트랜잭션을 T

n

이 기다리고 있다 하자 . 그러면 S

i

는 S

j

로 순환에 관한 정보를 보낸다 .

최적화 : S

i

는 i>n 일 때에만 정보를 보낸다 .

S

j

는 새로운 정보로 자신의 그래프를 갱신하고 , 순환을 발견 하면 위의

절차를 반복한다 .

(71)

완전 분산 방법 : 예

EX(i) : Tex 를 나타내며 , 다른 사이트의 트랜잭션이 사이트 i 의 트랜잭션을 기다리거나 사이트 i 의 트랜잭션이

Site 1

EX(3) T

1

T

2

T

3

EX(2) Site 2

EX(1) T

3

T

4

T

5

EX(3) Site 3

EX(2) T

5

T

1

EX(1)

(72)

완전 분산 방법 : 예 ( 계속 )

사이트는 그래프내의 경로를 따라 대기 정보를 보낸다 .

- EX(j) T

i

…

T

n

EX(k) 를 사이트 m 에서의 지역 대기 그래프내의 경로라 하자 .

- 사이트 m 은 i>n 인 경우에만 사이트 k 로 경로 정보를 보낸다 .

예 :

- 사이트 1 은 정보를 보내지 않는다 : 1 < 3 - 사이트 2 는 정보를 보내지 않는다 : 3 < 5

- 사이트 3 은 아래와 같은 이유 때문에 사이트 1 로 (T

5

,T

1

) 을 보낸다 .

* 5 > 1

* T 은 사이트 1 의 데이터 항목을 기다리고 있다 .

(73)

완전 분산 방법 ( 계속 )

경로 EX(2) T

5

T

1

EX(1) 을 사이트 1 로 보낸 후 다음을 얻는다 :

Site1

EX(2) T

5

T

1

T

2

T

3

EX(2) Site2

EX(1) T

3

T

4

T

5

EX(3) Site 3

EX(2) T T EX(1)

(74)

완전 분산 방법 ( 계속 )

Site1

EX(2) T

5

T

1

T

2

T

3

EX(2)

이동이 있은 후 사이트 1 만이 새로운 간선을 갖는다 . 5 > 3 이고 T3이 사이트 2 의 데이터 항목을 기다리고 있으므로 , 사이트 1 은 사이트 2 로 (T5,T1,T2,T3) 을 보낸다 .

지역 대기 그래프의 새로운 상태

Site2

T

5

T

1

T

2

T

3

T

4

Site 3

교착상태 탐지

(75)

다중 데이터베이스 시스템

이질적인 데이터베이스 내의 정보를 다루는데 필요한 기 존 데이터베이스 시스템 상단의 소프트웨어 층

데이터 모델은 다를 수 있다 ( 계층 , 관계형 등 )

트랜잭션 완료 규약이 양립하지 않을 수도 있다 .

동시성 제어가 서로 다른 기법에 기반을 둘 수 있다 ( 로킹 , 타임스탬핑 등 ).

시스템 층의 상세 사항은 거의 전부 양립하지 않는다 .

(76)

장점

기존 투자의 보존 - 하드웨어

- 시스템 소프트웨어 - 어플리케이션

지역 자치성과 행정적 제어

특수 목적 DBMS 사용이 가능

통합된 동질 DBMS 로 향하는 과정

(77)

데이터의 통합된 뷰

공통 데이터 모델에 동의

공통 개념 스키마에 동의

공유 데이터의 단일 표현에 동의 ( 여러 DBMS 에 저장될 수 있다 )

도량형 단위에 동의

전역 트랜잭션 내에 한정된 기능을 기꺼이

수용하기

(78)

트랜잭션 관리

지역 트랜잭션은 MDBS 제어 밖의 각 지역 DBMS 에 의해 실행된 다 .

전역 트랜잭션은 MDBS 제어하에 실행된다 .

지역 자치성 - 지역 DBMS 는 전역 트랜잭션 실행의 동기화를 위해 직접 통신할 수 없고 MDBS 는 지역 트랜잭션 실행에 제어권이 없 다 .

- DBMS 의 스케쥴이 직렬 가능하도록 보장하기 위해 지역 동시성 제어 기법이 요구된다 .

- 로킹의 경우 , DBMS 는 지역 교착상태를 대비해야만 한다 .

- 전역 직렬성을 보장하기 위한 추가의 기법이 요구된다 .

(79)

2 단계 직렬성

DBMS 는 전역 트랜잭션의 일부를 내포하고 있는 지역 트랜잭션 간의 지역 직렬성을 보장한다 .

MDBS 는 전역 트랜잭션 간의 직렬성만 보장한다 . - 지역 트랜잭션에 위해 유발된 순서는 무시한다 .

2LSR 은 전역 직렬성을 보장하지는 않지만 , 정확성을 위한 요구 사 항은 충족할 수 있다 .

1. 제약 조건의 집합으로 지정한 일관성 보존

2. 각 트랜잭션이 읽은 데이터 항목의 집합이 일관성 있도록 보장

전역 읽기 규약 : 전역 트랜잭션은 지역 데이터 항목을 읽을 수는 있 지만 갱신할 수 없다 ; 지역 트랜잭션은 전역 데이터에 액세스하지 못한다 . 지역 및 전역 데이터 항목간에 일관성 제약 조건은

없다 .

(80)

2 단계 직렬성 ( 계속 )

지역 읽기 규약 : 지역 트랜잭션은 전역 데이터를 읽을 수 있다 ; 전역 트랜잭션의 지역 데이터에 대한 모든 액세스는 금지한다 .

- 한 사이트에 있는 데이터 항목의 쓰기가 다른 사이트에 있는 데이터 항목에서 읽은 값에 의존하면 트랜잭션은 값 종속을 갖는다 .

- 강한 정확성을 위해 : 어떤 트랜잭션도 값 종속을 가져서는 안 된다 .

전역 읽기 / 지역 읽기 규약 : 지역 트랜잭션은 전역 데이터를 읽을 수 있 다 ; 전역 트랜잭션은 모든 데이터를 읽고 쓸 수 있다 .

- 지역과 전역 데이터 항목간에 어떠한 일관성 제약 조건도 없다 .

- 어떤 트랜잭션도 값 종속을 가질 수 없다 .

(81)

전역 직렬성

전역 2PL - 각 지역 사이트는 정확한 2PL 을 사용한다 ( 로크는 끝에서 해제된다 ); 전역 트랜잭션의 결과로 설 정된 로크는 그 트랜잭션이 끝에 이를 때에만 해제 된다 .

다양한 지역 동시성 제어 기법의 구조에 관련해 사용 가능 한 정보가 없다 하더라도 , 직렬성을 보장하는 매우 제한적인 규약이 사용 가능하다 .

-

트랜잭션 그래프 : 전역 트랜잭션명과 사이트명을 나타내는

정점을 가진 그래프 . T

i

가 사이트 S

k

에서 활동중이면 , 무방향 간선 (T

i

, S

k

) 가 존재한다 .

- 트랜잭션에 무방향 비순환을 포함하면 전역 직렬성은 보장된다 .

(82)

전역 직렬성의 보장

각 사이트 S

i

에 티켓이라는 특수한 데이터 항목을 갖는다 .

사이트 S

k

에서 실행되는 각 트랜잭션 T

j

는 사이트 S

i

의 티켓에 쓴다 .

지역 동시성 제어 기법이 지역 직렬성을 보장하는 한 그 방법에 관계없 이 전역 트랜잭션들은 각 사이트에서 직렬화 됨을 보장한다 .

전역 트랜잭션 매니저는 티켓을 액세스한 순서를 제어함으로써 전역 트 랜잭션들의 직렬 순서를 결정한다 .

그러나 , 위의 규약은 전역 트랜잭션 간에 낮은 동시성을 야기한다 .

참조

지금 다운로드하기 ( PPT - 82 페이지 - 212.00 KB )

Outline

의사 결정 기록

관련 문서