Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

분산 데이터 저장 관계형 데이터 모델을 가정하자. 중복: 보다 빠른 검색과 고장에 대비해 시스템은 여러 사이트에 저장된 데이터의 여러 사본을 유지한다. 분할: 릴레이션은 여러 단편으로 분할되어 서로 다른 사이트에 저장된다. 중복과 분할: 릴레이션은 여러 단편으로 분할된다; 시스템은 그러한 각 단편의 동일한 여러 사본을 유지한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

데이터 중복(계속) 중복의 장점 가용성 : 중복이 존재한다면 릴레이션 r 을 내포하고 있는 사이트의 고장이 r의 사용에 영향을 주지 않는다 병렬화 : r 상의 질의가 여러 노드에서 병렬로 처리될 수 있다 데이터 전송의 감소 : r의 사본을 내포하고 있는 각 사이트에서 릴레이션 r 이 지역적으로 사용 가능하다. 중복의 단점 갱신 비용의 증가 : 릴레이션 r 의 각 사본이 갱신되어야 한다 동시성 제어의 복잡성 증가 : 특수한 동시성 제어 기법이 수행되지 않으면 상이한 사본에의 동시 갱신이 데이터의 불일치를 야기할 수 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

데이터 분할 릴레이션 r을 재구축하는데 충분한 정보를 내포한 단편 r1, r2, … rn으로 분할 수평 분할 : r의 각 튜플이 하나 이상의 단편에 배정된다. 수직 분할 : 릴레이션 r의 스키마가 여러 개의 작은 스키마로 분할된다. - 모든 스키마는 무손실 죠인 속성을 보장하도록 공통 후보 키 (또는 수퍼 키)를 내포해야 한다. - tuple-id라는 특수 애트리뷰트가 후보 키 역할을 하기 위해 각 스키마에 추가될 수 있다. 단편들은 임의의 깊이로 연속 분할될 수 있다. 수직 및 수평 분할이 혼합될 수 있다. 예 : 다음과 같은 스키마를 가진 릴레이션 account Account-schema = (branch-name, account-number, balance) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

account 릴레이션의 수평 분할 branch-name account-number balance Hillside A - 305 A - 226 A - 155 500 336 62 account 1 branch-name account-number balance Valleyview A- 177 A- 402 A- 408 A- 639 205 10000 1123 750 account 2 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

deposit 릴레이션의 수직 분할 branch-name customer-name tuple-id Hillside Valleyview Lowman Camp Kahn Green 1 2 3 4 5 6 7 deposit1 account-number balance tuple-id A-305 A-226 A-177 A-402 A-155 A-408 A-639 500 336 205 10000 62 1123 750 1 2 3 4 5 6 7 deposit2 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

분할의 장점 수평 : 릴레이션에 병렬 처리 허용 튜플들이 가장 빈번히 액세스되는 곳에 위치하도록 전역 테이블이 분리되도록 한다. 수직 : 정규화로 이루어질 수 있는 것보다 한층 더 분해한다 tuple-id 애트리뷰트는 수직 단편들의 효율적인 죠인을 허용한다. - 릴레이션에 병렬 처리 허용 - 튜플의 각 부분이 가장 빈번히 액세스되는 곳에 저장 되도록 튜플을 분리한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

네트워크 은폐 시스템 사용자들로 하여금 데이터 항목이 분산 시스템 내에 어떻게 어디에 저장되어 있는가에 대한 상세 사항을 알지 못하도록 하는 정도 릴레이션 내의 다음에 대한 은폐 문제를 고려해 보자 : - 데이터 항목의 명명 - 데이터 항목의 중복 - 데이터 항목의 분할 - 단편과 중복의 위치 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

데이터 항목의 명명 - 평가 기준 1. 각 데이터 항목은 시스템 전체에서 유일한 이름을 가져야 한다. 2.데이터 항목의 위치를 효율적으로 찾을 수 있어야 한다. 3. 데이터 항목의 위치를 드러나지 않게 변경할 수 있어야 한다. 4. 각 사이트는 새로운 데이터 항목을 자치적으로 생성할 수 있어야 한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

중앙 집중 기법- 이름 서버 구조 : - 이름 서버는 모든 이름을 배정한다. - 각 사이트는 지역 데이터 항목을 기록 유지한다. - 사이트에서는 비지역 데이터 항목을 찾기 위해 이름 서버에 문의한다. 장점 : - 명명 평가 기준 1~3 을 만족한다. 단점 : - 명명 평가 기준 4를 만족하지 않는다. - 이름 서버에 성능 병목의 가능성이 있다. - 이름 서버가 고장의 유일한 요소이다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

별명의 사용 중앙 집중 기법에의 대안 : 각 사이트는 자신이 생성한 어떠한 이름에 자신의 사이트 식별자를 붙인다 즉, site17.account처럼 - 유일한 식별자를 가지게 되고 중앙 집중과 관련한 문제가 해결된다. - 그러나, 네트워크 은폐 달성은 실패다. 해결책 : 데이터 항목에 대한 별명의 집합을 생성한다;각 사이트에 별명과 실제 이름과의 매핑을 저장한다. 사용자는 데이터 항목의 물리적 위치를 모를 수 있으며,데이터 항목의 한 사이트에서 다른 사이트로 이동되더라도 영향을 받지 않는다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

별명의 사용(계속) 데이터 항목의 각 사본과 단편은 유일한 이름을 가져야 한다. - 같은 데이터 항목의 사본들과 단편들을 결정하는데 후위 표기를 사용한다. - 같은 데이터 항목의 단편들 : “.f1”, “.f2”,…, “.fn” - 같은 데이터 항목의 사본들 : “.r1”, “.r2”,…, “.rn” site17.account.f3.r2 위는 account의 단편 3의 사본 2를 의미한다; 이 항목은 사이트 17에서 생성되었다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

이름 변환 알고리즘 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 return result; Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

이름 변환 기법의 예 Hillside 지점(사이트 S1)의 사용자는 account 릴레이션의 지역 단편 account.f1에 대해 local-account라는 별명을 사용한다. 이 사용자가 local-account 를 참조하면, 질의 처리 부 시스템은 별명 테이블에서 local-account를 찾아 S1.account.f1으로 대치한다. S1.account.f1이 중복되었으면, 시스템은 사본을 선택하기 위해 중복 테이블을 참조해야 한다. 이 사본이 분할되었으면, 시스템은 릴레이션을 재구축하는 방법을 알기 위해 분할 테이블을 검사해야 한다. 그러나, 일반적으로는 한 두개의 테이블만 참조하면 되므로, 알고리즘은 릴레이션의 어떤 조합의 연속적인 중복과 분할도 다룰 수 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

은폐와 갱신 데이터 항목의 모든 사본이 갱신되고 영향 받는 모든 단편이 갱신되도록 보장해야 한다. account 릴레이션에 다음 튜플의 삽입을 고려해 보자 : (“Valleyview”, A-733, 600) account 의 수평 분할 account1 = branch-name = “Hillside” (account) account2 = branch-name = “Valleyview” (account) - 술어 Pi는 i번째 단편과 관련된다. - 술어 Pi를 튜플 (“Valleyview”, A-733, 600)에 적용해 튜플이 i번째 단편에 삽입되어야 할지를 테스트한다. - 튜플은 account2에 삽입된다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

은폐와 갱신(계속) deposit 를 deposit1과 deposit2로 수직 분할 튜플 (“Valleyview”,A-733,”Jones”,600)은 두 개의 단편으로 분리되어야 한다: - 하나는 deposit1에 삽입되도록 - 하나는 deposit2에 삽입되도록 deposit가 중복되면, 튜플 (“Valleyview”,A-733, “Jones”,600)은 모든 사본에 삽입되어야 한다. 문제점 : deposit가 동시에 액세스되면, 한 사본이 다른 것 보다 먼저 갱신될 것이다(동시성 제어 참조). Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

예제 질의 account 릴레이션의 아래와 같은 수평 분할을 고려해 보자. account1 =  branch-name = “Hillside” (account) account2 =  branch-name = “Valleyview” (account) 질의  branch-name = “Hillside” (account)는 다음과 같이 된다.  branch-name = “Hillside” (account1 U account2) 이것은 아래와 같이 최적화 된다.  branch-name = “Hillside” (account1) U  branch-name = “Hillside” (account2) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

예제 질의 (계속) acount1에는 Hillside 지점에 속한 튜플만을 가지고 있으므로 선택 연산을 제거할 수 있다. account2의 정의를 적용해 다음을 얻는다.  branch-name = “Hillside” ( branch-name = “Valleyview” (account) ) 이 표현식은 account 릴레이션의 내용에 관계없이 공집합이다. 최종 전략은 질의의 결과로 Hillside 사이트에서 acount1을 돌려주는 것이다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

단순 죠인 처리 세개의 릴레이션이 중복되지도 않고 분할되지도 않은 관계형 대수 표현식을 고려해 보자. account depositor branch account는 사이트 S1에 저장되었다. depositor는 S2에 branch는 S3에 사이트 Sl에서 제기된 질의에 대해, 시스템은 Sl에 결과를 생성해야 한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

가능한 질의 처리 전략 세 릴레이션의 모든 사본을 사이트 Sl 에서 지역적으로 전체 질의를 처리하는 전략을 선택한다. account 릴레이션의 사본을 S2로 보내 S2에서 temp1 = account depositor를 계산한다. S2에서 temp1을 S3로 보내 S3에서 temp2 = temp branch를 계산한다. 결과 temp2를 Sl로 보낸다. S1, S2, S3의 역할을 바꾸어 유사한 전략을 세운다. 다음과 같은 요인을 고려해야 한다: - 보내는 데이터의 양 - 사이트간의 데이터 블록 전송 비용 - 각 사이트에서의 상대적인 처리 속도 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

세미죠인 전략 r1을 사이트 S1에 저장된 스키마 R1을 가진 릴레이션이라 하자. r2를 사이트 S2에 저장된 스키마 R2를 가진 릴레이션이라 하자. r1 r2 를 평가해 결과는 S1에 생성한다. 1. S1에서 temp1  R1  R2(r1) 을 계산한다. 2. S1에서 S2로 temp1을 보낸다. 3. S2에서 temp2 r2 temp1을 계산한다. 4. S2에서 S1으로 temp2를 보낸다. 5. S1에서 r temp2를 계산한다. 이것이 r r2의 결과이다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

형식적 정의 r1과 r2의 세미죠인은 아래와 같이 표기한다. r1 r2 이것은 다음과 같이 정의된다:  R1 (r r2) 따라서, r r2 는 r r2에 기여한 r1의 튜플만을 선택한다. 앞장의 절차 3에서 temp2 = r2 r1이다. 여러 릴레이션의 죠인에 대해, 위의 전략은 일련의 세미죠인 절차로 확장될 수 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

병렬화를 사용하는 죠인 전략 릴레이션 ri가 사이트 Si에 저장된 r r r r4를 고려해 보자. 결과는 사이트 S1에 나타나야 한다. 파이프 라인 -죠인 전략 - r1을 S2로 보내 S2에서 r r2를 계산한다; 동시에 r3를 S4로 보내 S4에서 r r4를 계산한다. - S2는 (r r2)의 튜플이 생성되면 S1로 보낸다; S4는 (r r4)의 튜플을 S1로 보낸다. - (r r2) 와 (r r4)의 튜플들이 일단 S1에 도달하면, S2에서의 (r r2)계산과 S4에서의 (r r4)계산과 함께 (r r2) (r r4) 가 병렬로 계산된다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

분산 트랜잭션 모델 트랜잭션은 여러 사이트에서 데이터를 액세스할 수 있다. 각 사이트에는 다음과 같은 책임을 지는 지역 트랜잭션 매니저를 가진다; - 회복을 위한 로그의 유지 관리 - 해당 사이트에서 실행중인 트랜잭션의 동시 실행 조정에의 참여 각 사이트에는 다음과 같은 책임을 지는 트랜잭션 조정자를 가진다. - 해당 사이트에서 기동하는 트랜잭션의 실행 시작 - 실행을 위해 부 트랜잭션을 적절한 사이트로의 분배 - 트랜잭션이 모든 사이트에서 완료되거나 중단될 수 있는 해당 사이트에서 기동한 각 트랜잭션 종료의 조정 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

네트워크 위상(계속) 분할 시스템은 연결이 없는 둘 이상의 부 시스템으로 분리된다. 트리-구조 : 설치 및 통신 비용이 낮다; 단일 링크의 고장으로 네트워크가 분할될 수 있다. 링 : 분할이 발생하려면 적어도 두 개의 링크가 고장나야 한다. 성형: - 단일 링크의 고장이 네트워크 분할을 야기하지만, 분할들 중 하나는 단일 사이트만을 가지므로 단일 사이트 고장으로 취급 될 수 있다. - 통신 비용이 낮다. - 중앙 사이트의 고장은 시스템 내의 모든 사이트가 단절되는 결과를 가져온다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

견고성 견고한 시스템은 다음을 만족해야 한다: - 사이트 또는 링크 고장의 탐지 - 연산이 계속되도록 시스템의 재구성 - 처리기 또는 링크가 수리되면 회복 고장 유형의 처리 - 손실된 메시지의 재전송 - 확인 받지 않은 재전송은 링크 고장을 의미한다; 다른 우회로를 찾는다 - 다른 우회로를 찾는데 실패했다는 것은 네트워크 분할의 징후이다. 네트워크 링크 고장과 사이트 고장은 일반적으로 분간할 수 없다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

시스템 재구성 절차 중복된 데이터가 고장 난 사이트에 저장되었으면, 질의가 고장 난 사이트의 사본을 참조하지 못하도록 카타로그를 갱신한다. 고장 난 사이트의 활동 트랜잭션들은 중단시켜야 한다. 고장 난 사이트가 어떤 서브 시스템의 중앙 서버이면, 새로운 서버를 결정할 선거가 치러져야 한다. 재구성 기법은 네트워크 분할의 경우에 정확히 수행되어야 한다. 다음은 피해야 한다: - 서로 다른 분할에서 둘 이상의 중앙 서버 선출 - 두개 분할 이상에서의 중복 데이터 갱신 일련의 트랜잭션으로 회복 절차를 표현한다; 동시성 제어 부 시스템과 트랜잭션 관리 부 시스템이 적절한 재통합을 위해 서로 돕는다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

완료 규약 사이트에 걸쳐 원자성을 보장하기 위해 완료 규약이 사용된다. - 여러 사이트에서 실행되는 트랜잭션은 모든 사이트에서 완료되든지 중단되어야 한다. - 트랜잭션이 한 사이트에서는 완료되고 다른 사이트에서는 중단될 수 없다. 2단계 완료(2PC)규약이 널리 사용된다. 3단계 완료(3PC)규약은 보다 복잡하고 비용이 많이 들지만, 2PC의 단점을 보완한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

2단계 완료 규약 고장 - 중단 모델을 가정한다 - 고장난 사이트는 작업을 즉시 중단하고 다른 사이트에 잘못된 메시지를 보내는 것과 같은 위해를 야기하지 않는다. 규약의 실행은 트랜잭션의 마지막 절차가 도달한 후 조정자가 기동시킨다. 규약에는 트랜잭션을 실행하는 모든 지역 사이트가 내포된다. 사이트 Si에서 시작한 트랜잭션을 T라 하고, Si의 트랜잭션 조정자를 Ci라 하자. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

단계 1: 의사 결정 획득 조정자는 모든 참가자에게 트랜잭션 Ti 의 완료 준비를 요청한다. - Ci는 로그에 레코드 <prepare T>를 추가하고 안정 저장 장치에 로그를 강제 출력한다. - T를 실행한 모든 사이트에 prepare T 메시지를 보낸다. 메시지를 받으면, 해당 사이트의 트랜잭션 매니저는 트랜잭션을 완료할 수 있는가를 결정한다. - 할 수 없으면, 레코드 <no T>를 로그에 추가하고 Ci에 abort T 메시지를 보낸다. - 트랜잭션이 완료될 수 있으면, * 로그에 레코드 <ready T>추가 * T에 대한 모든 로그 레코드를 안정 저장 장치에 강제 출력 * Ci에 ready T 메시지를 전송 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

단계 2: 의사 결정 기록 Ci가 모든 참가 사이트로부터 ready T 메시지를 받으면, T는 완료 될 수 있다; 그렇지 않으면, T는 중단되어야 한다. 조정자는 의사 결정 레코드 <commit T>또는 <abort T>를 로그에 추가하고 안정 저장 장치에 로그를 출력한다 그 레코드가 안정 저장 장치에 일단 도달하면, 취소할 수 없다(고장이 발생한다 할지라도). 조정자는 각 참가자에게 의사 결정(완료 또는 중단)을 알리는 메시지를 보낸다. 참가자들은 지역적으로 적절한 행위를 취한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

고장 취급 - 사이트 고장 사이트 Sk가 회복될 때는, 고장 당시에 활동 트랜잭션들의 운명을 결정 하기 위해 자신의 로그를 검사한다. 로그에 <commit T>레코드를 포함한다: 사이트는 redo(T)를 실행한다. 로그에 <abort T>레코드를 포함한다: 사이트는 redo(T)를 실행한다. 로그에 <ready T>를 포함한다: 사이트는 Ci와 상의해 T의 운명을 결정해야 한다. - T가 완료되었으면, redo(T) - T가 중단되었으면, undo(T) 로그에 T에 관련한 제어 레코드를 포함하지 않는다: Ci로부터의 prepare T 메시지에 응답하기 전에 Sk가 고장 났음을 의미 - Sk가 고장나면, 그러한 응답을 할 수 없으므로 Ci는 T를 중단시켜야 한다. - Sk는 undo (T)를 실행해야 한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

고장 취급 - 조정자 고장 T의 완료 규약 실행 중 조정자가 고장 나면, 참가 사이트들이 T의 운명을 결정해야 한다: 어떤 활동 사이트가 자신의 로그에 <commit T>레코드를 내포하고 있으면, T는 완료되어야 한다. 어떤 활동 사이트가 자신의 로그에 <abort T>레코드를 내포하고 있으면, T는 중단되어야 한다. 어떤 활동 사이트가 자신의 로그에 <ready T>레코드를 내포하지 않으면, 고장난 조정자 Ci가 T를 완료하고자 결정할 수 없었던 것이다. 따라서, T를 중단시킬 수 있다. 위의 어느 경우도 아니면, 모든 활동 사이트는 자신의 로그에 <ready T>레코드를 가져야 하지만 별도의 제어 레코드는 없다. 이러한 경우에 활동 사이트들은 Ci가 회복할 때까지 기다려 결정을 찾아야 한다. 블록킹 문제 : 활동 사이트들이 고장난 조정자가 회복할 때까지 기다려야 한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

고장 취급 - 네트워크 분할 조정자와 모든 참가자가 한 분할에 있으면, 고장이 완료 규약에 어떤 영향도 미치지 못한다. 조정자와 참가자들이 여러 분할에 속하면: - 조정자를 내포하고 있는 분할에 없는 사이트들은 조정자가 고장 났다고 생각하고 조정자 고장을 다루기 위한 규약을 실행한다. * 아무런 해도 발생하지 않지만, 사이트들은 여전히 조정자로부터의 결정을 기다려야 한다. - 같은 분할에 있는 조정자와 사이트들은, 조정자가 다른 분할 에 있는 사이트들이 고장 났다고 생각하고 통상적인 완료 규약을 따른다. * 아무런 해도 발생하지 않는다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

회복과 동시성 제어 의심스런 트랜잭션은 <ready T>를 가지지만, <commit T> 또는 <abort T>어느 로그 레코드도 갖지 않는다. 회복중인 사이트는 다른 사이트와 접촉해 그러한 트랜잭션의 완료 - 중단 상태를 결정해야 한다; 이것은 회복을 더디게 하고 블록의 가능성이 있다. 회복 알고리즘은 로그 내에 로그 정보를 기록할 수 있다. - <ready T>대신에 <ready T,L>을 기록한다. L은 로그가 기록될 때 T가 가진 로크 리스트이다(읽기 블록은 생략될 수 있다). - 모든 의심스러운 트랜잭션 T에 대해, <ready T,L>로그 레코드에 기록된 모든 로크가 다시 얻어진다. 로크 재획득 후에, 트랜잭션 처리가 재개될 수 있다; 의심스런 트랜잭션의 완료 또는 복귀가 새로운 트랜잭션의 실행과 동시에 수행된다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

3단계 완료 규약 가정 : - 네트워크 분할은 없다. - 어떤 시점에서 적어도 하나의 사이트는 활동해야 한다. - 기껏해야 K 사이트(조정자와 참가자 포함)가 고장 날 수 있다. 단계 1 : 예비 의사 결정 획득 : 2PC 의 단계 1과 동일 - 모든 사이트는 그렇게 하라는 통지를 받으면 완료할 준비를 한다. - 2PC하에서 각 사이트는 조정자로부터의 결정을 기다릴 의무가 있다. - 3PC하에서 조정자의 고장에도 불구하고 예비 완료 결정의 지식이 완료하는데 사용될 수 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

단계 2: 예비 결정의 기록 조정자는 자신의 로그에 결정 레코드 <abort T> 또는 <precommit T>를 추가하고 안정 저장 장치에 출력한다. 조정자는 각 참가자에게 결정 사항을 알리는 메시지를 보낸다. 참가자는 자신의 로그에 결정을 기록한다. - 중단 결정을 받으면 참가자는 지역적으로 중단한다. - 예비 완료 결정을 받으면 참가자는 <acknowledge T>로 응답한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

단계3:데이터베이스에 결정 기록 단계 2에서 예비 완료일 때만 실행된다. 조정자는 확인 응답을 수집한다. K개의 확인 응답을 받으면 조정자는 참가자들에게 <commit T>메시지를 보낸다. 조정자는 자신의 로그에 <commit T>레코드를 추가하고 안정 저장 장치에 레코드를 출력한다. 조정자는 각 참가자에게 <commit T>메시지를 보낸다. 참가자들은 지역적으로 적절한 행위를 취한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

사이트 고장 취급 사이트 고장. 회복시 참가하는 사이트는 자신의 로그를 검사해 다음을 수행한다: 로그에 <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 메시지를 보낸다). Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

사이트 고장 취급(계속) 로그에 <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> 레코드를 기록한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

조정자 고장 규약 1. 활동중인 참가 사이트들이 새로운 조정자 Cnew를 선택한다. 2. Cnew는 각 참가 사이트로부터 T의 지역 상태를 요청한다. 3. Cnew를 포함해 각 참가 사이트는 T의 지역 상태를 결정한다. 완료. 로그에 <commit T> 레코드를 내포 중단. 로그에 <abort T> 레코드를 내포 준비. 로그에 <ready T> 레코드는 내포하지만, <abort T> 또는<precommit T> 레코드가 없다. 사전완료. 로그에 <precommit T> 레코드는 내포하지만, <abort T> 또는 <commit T> 레코드가 없다. 비준비. 로그에 <ready T> 도 <abort T> 레코드도 없다. 고장이 나서 회복한 사이트는 자신의 상태를 결정할 때 자신의 로그 내 어떠한 precommit 레코드도 무시해야 한다. 4. 각 참가 사이트는 자신의 지역 상태를 Cnew에 보낸다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

조정자 고장 규약(계속) 5. Cnew는 T를 완료 또는 중단하든지 또는 3단계 완료 규약을 재시작할 것인지를 결정한다 : 참가 사이트 중 하나라도 완료 상태 => 완료 참가 사이트 중 하나라도 중단 상태 => 중단 참가 사이트 중 하나라도 사전 완료 상태이고 위의 두 가지 경우를 가지고 있지 않음 => 불확정 상태에 있는 참가 사이트에 precommit 메시지를 보내고, 그 시점에서 규약이 재개된다. 모든 활동사이트가 불확정 상태 => 중단. 적어도 n-k개의 사이트는 활동하므로, 모든 참가자가 불확정 상태에 있다는 사실은 조정자가 <commit T> 메시지를 보내지 못해 어떤 사이트도 T를 완료하지 못했음을 의미한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

조정자 선택 예비 조정자 - 실제 조정자가 고장 나면, 조정자 역할을 할 지역적으로 충분한 정보를 유지하는 사이트 - 실제 조정자와 같은 알고리즘을 실행하고 같은 내부 상태 정보를 유지한다. - 조정자 고장으로부터 신속한 회복을 허용하지만, 정상 처리 중 비용 부담이 있다. 선거 알고리즘 - 고장시 새로운 조정자를 뽑는데 사용된다. - 예 : 골목대장 알고리즘 - 각 사이트가 다른 각 사이트에 메시지를 보낼 수 있는 시스템에 적용 가능 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

골목대장 알고리즘 사이트 Si가 요청한 후 시간 간격 T내에 조정자로부터 응답이 없으면, 조정자가 고장 난 것으로 가정한다 ; Si는 자신이 새로운 조정자로 선출되고자 한다. Si는 자신보다 큰 식별 번호를 가진 모든 사이트에 선거 메시지를 보내고, Si는 시간 T내에 이들 사이트로부터 응답을 기다린다 시간 T내에 응답이 없으면, i보다 큰 번호를 가진 모든 사이트가 고장 난 것으로 가정한다; Si는 자신을 새로운 조정자로 선출한다. 응답이 오면, Si는 자기보다 큰 식별 번호를 가진 사이트가 선출되었다는 메시지를 받을 때까지 시간 간격 T 동안 기다리기 시작한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

골목대장 알고리즘(계속) 어떤 메시지도 T내에 없으면, 높은 번호를 가진 사이트가 고장 났다고 가정해 Si는 알고리즘을 재가동한다. 고장 난 사이트는 회복 후, 즉시 같은 알고리즘을 실행 시킨다. 높은 번호를 가진 활동 사이트가 없으면, 현재 작은 번호를 가진 활동 조정자가 있다 하더라도 회복된 사이트는 자신이 조정자 사이트가 되었음을 작은 번호를 가진 모든 사이트에게 통보한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

단일 로크 매니저 방법 시스템은 선택된 단일 사이트 (Si)에 있는 단일 로크 매니저를 유지한다. 트랜잭션에서 데이터 항목의 로크를 필요로 하면, Si에 로크 요청을 보내고 로크 매니저는 로크를 즉시 허용할 것인가를 결정한다. - 허용하면, 로크 매니저는 요청한 사이트에 메시지를 보낸다. - 허용되지 않으면, 메시지가 요청한 사이트에 보내져 허용될 수 있을 때까지 요청은 지연된다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

단일 로크 매니저 방법(계속) 트랜잭션은 데이터 항목의 사본이 있는 사이트 중 어느 곳으로부터도 데이터 항목을 읽을 수 있다. 출력하는 경우는, 데이터 항목의 사본을 가진 모든 사이트에 이루어져야 한다. 이 기법의 장점 : - 단순 구현 - 단순한 교착상태 처리 이 기법의 단점 : - 병목 : 로크 매니저 사이트가 병목이 된다. - 취약성 : 로크 매니저 사이트가 고장 나는 경우의 취약성이 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

다수 규약 각 사이트의 지역 로크 매니저가 해당 사이트에 저장된 데이터 항목에 대한 로크와 해제 요청을 관리한다. 트랜잭션에서 사이트 Si에 있는 비중복 데이터 항목 Q에 로크를 원하면, Si의 로크 매니저에 메시지를 보낸다. Q가 양립할 수 없는 유형으로 로크 되었으면, 요청은 허용될 때까지 지연된다. 로크 요청이 허용 될 때, 로크 매니저는 요청이 허용되었다는 메시지를 요청자에게 보낸다. 로크와 해제가 더 이상 단일 사이트에서 이루어지지 않으므로 구현이 더욱 복잡해지고 교착상태 처리가 복잡해진다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

다수 규약(계속) 중복 데이터인 경우, 앞의 기법보다 더욱 복잡해진다. - Q가 n개 사이트에 중복되면, Q가 저장된 n/2+1개의 사이트에 로크 요청 메시지를 보내야 한다. - Q의 사본 중의 다수에 로크를 얻지 못하면, 트랜잭션은 Q에 연산할 수 없다. - 데이터 항목을 출력할 때, 트랜잭션은 모든 사본에 출력을 수행한다. 로크 요청 처리에 2(n/2+1) 메시지가 필요하고, 해제 요청 처리에 (n/2+1) 메시지가 필요하다. 단일 항목에서 조차 교착상태의 가능성이 있다 예를 들어, 두 트랜잭션 각각이 어떤 데이터 항목 사본 중에 1/2씩 로크를 가질 수 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

편파 규약 다수 규약에서와 마찬가지의 각 사이트의 지역 로크 매니저는 그러나, 공유 로크 요청을 배타 로크 요청과는 달리 처리한다. - 공유 로크. 트랜잭션에서 데이터 항목 Q에 로크를 필요로 할 때, Q의 사본을 가지고 있는 한 사이트의 로크 매니저로부터 로크를 요청한다. - 배타 로크. 트랜잭션에서 데이터 항목 Q에 로크를 필요로 할 때, Q의 사본을 가지고 있는 모든 사이트의 로크 매니저로 부터 로크를 요청한다. 장점 - read 연산에는 비용이 적게 든다. 단점 - 출력에는 추가 비용이 들고 교착상태 처리가 복잡하다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

주 사본 하나의 사본을 정확히 한 사이트(Q의 주 사이트)에만 있어야 하는 주 사본으로 선택한다. 트랜잭션에서 데이터 항목 Q에 로크를 필요로 할 때, Q의 주 사이트에 로크를 요청한다. 중복 데이터에 대한 동시성 제어가 비중복 데이터와 유사하게 처리된다 - 구현이 단순하다. Q의 주 사이트가 고장 나면, 사본을 내포하고 있는 다른 사이트가 활동중이라도 Q를 액세스할 수 없다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

타임스탬핑(계속) 느린 시계를 가진 사이트는 적은 타임스탬프가 배정될 것이다 => 트랜잭션이 손해를 본다. 각 사이트 Si내에 유일한 지역 타임스탬프를 생성하는 논리 시계 (LCi)를 정의한다. 타임스탬프 <x,y>를 가진 트랜잭션 Ti가 해당 사이트에 도달할 때마다 Si는 자신의 논리 시계를 증가시켜 x가 LCi의 현재 값보다 더 크게 할 필요가 있다. 이 경우, 사이트 Si는 자신의 논리 시계를 x + 1로 증가 시킨다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

교착상태 처리 다음의 두 트랜잭션과 이력 사항을 고려해 보자. T1 :write(X) T2: write(Y) write(Y) write(X) T T2 X-lock on X write(X) wait for X-lock on Y X-lock on Y write(Y) wait for X-lock on X 교착상태 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

중앙 집중 방법 단일 사이트에 전역 대기 그래프를 구축하고 관리한다 : 교착 상태 탐지 조정자 - 실제 그래프 : 알지는 못하지만 시스템의 실제 상태 - 구축 그래프 : 알고리즘 실행 중 제어기가 생성한 근사 그래프 전역 대기 그래프는 아래의 경우 구축될 수 있다 : - 새로운 간선이 지역 대기 그래프에 삽입되거나 삭제될 때 - 지역 대기 그래프에 많은 변화가 발생했을 때 - 조정자가 순환 탐지를 호출할 필요가 있을 때 조정자가 순환을 찾으면, 희생자를 선정해 모든 사이트에 알린다. 사이트들은 희생 트랜잭션을 복귀시킨다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

거짓 순환(계속) 앞 장의 그림에서 보인 상태로부터 시작한다 가정하자. 1. T2가 S1에서 자원을 해제한다 (그 결과, S1의 트랜잭션 매니저에서 조정자로 delete T1  T2 메시지가 전송된다).그리고, 2. 사이트 S2에서 T3 가 가진 자원을 T2가 요청한다 (그 결과, S2에서 조정자에게 insert T2  T3 메시지를 보낸다). delete 메시지 전에 insert 메시지가 먼저 도착했다고 가정하자. 조정자는 아래와 같은 거짓 순환을 발견할 것이다. T1  T2  T3  T1 위의 거짓 순환은 실제로는 결코 존재하지 않는 것이다. 거짓 순환은 2단계 로킹을 사용하면 발생할 수 없다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

완전 분산 방법(계속) 시스템 모델 : 트랜잭션은 한 사이트에서 실행되고, 비지역 데이터를 액세스하기 위해 다른 사이트에 요청한다. 각 사이트는 정상적인 유형으로 자신의 지역 대기 그래프를 유지한다: 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에서 지역이며, 외부 사이트로부터 온 데이터를 액세스했다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

완전 분산 방법(계속) 중앙 집중 교착상태 탐지 - 중앙 교착상태 탐지기에 보내진 모든 그래프 간선 분산 교착상태 탐지 - “경로 보내기” 알고리즘 어떤 사이트에서 교착상태의 가능성을 나타내는 Tex를 내포한 지역 순환을 탐지하면 “경로 보내기” 알고리즘이 시작된다. 사이트 Si에 다음과 같은 순환이 있다고 하자. Tex Ti Tj …. Tn Tex 그리고 사이트 Sj의 어떤 트랜잭션을 Tn이 기다리고 있다 하자.그러면 Si는 Sj로 순환에 관한 정보를 보낸다. 최적화 : Si는 i>n일 때에만 정보를 보낸다. Sj는 새로운 정보로 자신의 그래프를 갱신하고, 순환을 발견 하면 위의 절차를 반복한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

완전 분산 방법:예 Site 1 EX(3) T T T EX(2) Site 2 EX(1) T T T EX(3) Site 3 EX(2) T T EX(1) EX(i) : Tex를 나타내며, 다른 사이트의 트랜잭션이 사이트 i의 트랜잭션을 기다리거나 사이트 i의 트랜잭션이 다른 사이트의 트랜잭션을 기다린다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

완전 분산 방법:예(계속) 사이트는 그래프내의 경로를 따라 대기 정보를 보낸다. - EX(j) Ti … Tn EX(k)를 사이트 m에서의 지역 대기 그래프내의 경로라 하자. - 사이트 m은 i>n 인 경우에만 사이트 k로 경로 정보를 보낸다. 예: - 사이트 1은 정보를 보내지 않는다 : 1 < 3 - 사이트 2는 정보를 보내지 않는다 : 3 < 5 - 사이트 3은 아래와 같은 이유 때문에 사이트 1로 (T5,T1)을 보낸다. * 5 > 1 * T1은 사이트 1의 데이터 항목을 기다리고 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

완전 분산 방법(계속) 이동이 있은 후 사이트 1만이 새로운 간선을 갖는다 > 3이고 T3이 사이트 2의 데이터 항목을 기다리고 있으므로, 사이트 1은 사이트 2로 (T5,T1,T2,T3)을 보낸다. 지역 대기 그래프의 새로운 상태 Site1 EX(2) T T T T EX(2) Site2 T T T T T4 교착상태 탐지 Site 3 EX(2) T T EX(1) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

다중 데이터베이스 시스템 이질적인 데이터베이스 내의 정보를 다루는데 필요한 기존 데이터베이스 시스템 상단의 소프트웨어 층 데이터 모델은 다를 수 있다 (계층,관계형 등) 트랜잭션 완료 규약이 양립하지 않을 수도 있다. 동시성 제어가 서로 다른 기법에 기반을 둘 수 있다 (로킹 , 타임스탬핑 등). 시스템 층의 상세 사항은 거의 전부 양립하지 않는다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

트랜잭션 관리 지역 트랜잭션은 MDBS 제어 밖의 각 지역 DBMS에 의해 실행된다. 전역 트랜잭션은 MDBS 제어하에 실행된다. 지역 자치성 - 지역 DBMS는 전역 트랜잭션 실행의 동기화를 위해 직접 통신할 수 없고 MDBS는 지역 트랜잭션 실행에 제어권이 없다. - DBMS의 스케쥴이 직렬 가능하도록 보장하기 위해 지역 동시성 제어 기법이 요구된다. - 로킹의 경우, DBMS는 지역 교착상태를 대비해야만 한다. - 전역 직렬성을 보장하기 위한 추가의 기법이 요구된다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

2단계 직렬성 DBMS는 전역 트랜잭션의 일부를 내포하고 있는 지역 트랜잭션 간의 지역 직렬성을 보장한다. MDBS는 전역 트랜잭션 간의 직렬성만 보장한다 지역 트랜잭션에 위해 유발된 순서는 무시한다. 2LSR은 전역 직렬성을 보장하지는 않지만, 정확성을 위한 요구 사항은 충족할 수 있다. 1. 제약 조건의 집합으로 지정한 일관성 보존 2. 각 트랜잭션이 읽은 데이터 항목의 집합이 일관성 있도록 보장 전역 읽기 규약 : 전역 트랜잭션은 지역 데이터 항목을 읽을 수는 있지만 갱신할 수 없다; 지역 트랜잭션은 전역 데이터에 액세스하지 못한다. 지역 및 전역 데이터 항목간에 일관성 제약 조건은 없다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

2단계 직렬성(계속) 지역 읽기 규약 : 지역 트랜잭션은 전역 데이터를 읽을 수 있다; 전역 트랜잭션의 지역 데이터에 대한 모든 액세스는 금지한다. - 한 사이트에 있는 데이터 항목의 쓰기가 다른 사이트에 있는 데이터 항목에서 읽은 값에 의존하면 트랜잭션은 값 종속을 갖는다. - 강한 정확성을 위해 : 어떤 트랜잭션도 값 종속을 가져서는 안 된다. 전역 읽기/지역 읽기 규약 : 지역 트랜잭션은 전역 데이터를 읽을 수 있다; 전역 트랜잭션은 모든 데이터를 읽고 쓸 수 있다. - 지역과 전역 데이터 항목간에 어떠한 일관성 제약 조건도 없다. - 어떤 트랜잭션도 값 종속을 가질 수 없다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

전역 직렬성 전역 2PL - 각 지역 사이트는 정확한 2PL을 사용한다 (로크는 끝에서 해제된다); 전역 트랜잭션의 결과로 설정된 로크는 그 트랜잭션이 끝에 이를 때에만 해제 된다. 다양한 지역 동시성 제어 기법의 구조에 관련해 사용 가능한 정보가 없다 하더라도, 직렬성을 보장하는 매우 제한적인 규약이 사용 가능하다. - 트랜잭션 그래프 : 전역 트랜잭션명과 사이트명을 나타내는 정점을 가진 그래프. Ti가 사이트 Sk에서 활동중이면, 무방향 간선 (Ti, Sk)가 존재한다. - 트랜잭션에 무방향 비순환을 포함하면 전역 직렬성은 보장된다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

전역 직렬성의 보장 각 사이트 Si에 티켓이라는 특수한 데이터 항목을 갖는다. 사이트 Sk에서 실행되는 각 트랜잭션 Tj는 사이트 Si의 티켓에 쓴다. 지역 동시성 제어 기법이 지역 직렬성을 보장하는 한 그 방법에 관계없이 전역 트랜잭션들은 각 사이트에서 직렬화 됨을 보장한다. 전역 트랜잭션 매니저는 티켓을 액세스한 순서를 제어함으로써 전역 트랜잭션들의 직렬 순서를 결정한다. 그러나,위의 규약은 전역 트랜잭션 간에 낮은 동시성을 야기한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Similar presentations

Presentation on theme: "Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수"— Presentation transcript:

Similar presentations

About project

지원

로그인

Auth with social network:

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Similar presentations

Presentation on theme: "Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수"— Presentation transcript:

Similar presentations

About project

지원