고급분산시스템 기말고사 문제 샘플_이제민.hwp



 3. 분산 file system의 성능을 향상시키기 위한 방법으로 caching을 이용할 수 있다.

Client, server측에서 적용할 수 있는 caching 방식을 설명하시오.


(1) Client, server측에서 적용할 수 있는 caching 방식을 설명하시오.


Server Caching: 최근에 읽은 디스크 블럭을 서버에서 유지하고 있는 것을 말한다.

 

읽는것은 문제가 없다. 하지만 쓰기에서 문제가 발생한다. 따라서 두 개의 선택적인 동작이 가능 하다.

 

1) Write-through operation

서버가 현재 캐쉬에 데이터를 업데이트하고, 즉시 디스크에도 업데이트 하는 방식

 

2) Delayed-write

Write-through으로 인한 bottleneck을 해결하기 위한 방법이다.

서버는 단지 현재 캐쉬에 데이터를 업데이트 한다.

디스크에는 commit operation을 받았을 때 디스 에 저장 한다.

Client Caching: client 모듈은 read, write, getattr, lookup, readdir operation 결과를 캐쉬에 저장한다. 이를 통해서 서버에 전송하는 request의 수를 줄일 수 있다.


 

(2) Cachingfile service reliability와의 관계를 설명하시오.

-> Caching은 서버와 클라이언트의 작업 수행 속도를 줄일 수 있다는 큰 장점을 가지고 있다. 하지만 이러한 Cachingfile service reliability를 감소 시킨다. server의 경우 caching을 사용하는 경우 쓰기 작업을 수행하는 시간과 실제 디스크네 쓰는 시간이 다르기 때문에 디스크의 정보가 최근 정보가 아닐 수 있다. 또한 client의 경우도 각 클라이언트들이 cache에 저장한 값이 최근에 업데이트 된 값과 다를 수 있다.


(3) 둘 이상의 client가 한 fileupdate할 때의 문제점 및 해결방안을 서술하시오.

-> 둘 이상의 client가 한 fileupdate하면 자신이 update했기에 캐쉬에 저장했던 값이 다른 clientupdate로 인하여 실제 file 값과 달라지는 문제점이 발생한다. 따라서 이러한 문제점을 해결하기 위해서는 각 client들 서버의 데이터와 client 캐쉬의 데이터의 같은 지를 계속 폴링하며 확인해야 한다. 하지만 이런 polling 방식은 시간을 낭비한다는 문제점이 있다. 이러한 문제점을 해결한 방식이 callback promise. callback promiseclient가 파일을 업데이트를 하면 그 파일 캐쉬에 저장하고 있는 다른 clientcallback을 받게 되고 callback을 받았을 때만 자신의 캐쉬 값을 수정하면 된다


 

4. 다음은 Needham-Schroedersecret-key authentication protocol이다.

(1) 2번 과정을 설명하시오.


-> SA의 비밀 키로 암호화된 메시지를 A에게 보내다. 메시지 안에는 새로 만들어진 key KAB B의 비밀키로 암호화된 티켓이 들어 있다. 또한 nonce NA 를 넣어 이것이 A의 요청에 의해 반환된 메시지 인 것을 입증한다.


1번에서 A는 B와의 커뮤니케이션을 위해서 S에게 Key를 달라고 요청했다.


S는 A가 가지고 있는 비밀키를 이용해서 암호화된 메시지를 리턴 한다. 그 메시지의 내용은 다음과 같다. 이 메시지는 Kb로 암호화 되어있다. 그 암호화된 메시지에는 Kab와 A가 있다. 여기서 Kab는 A와 B의 통신을 위해서 S가 새롭게 생성해준 공유 키이다. 그리고 A는 중요한정보(ticket)이다. 


그리고 추가적으로 Na가 있다. 이것은 A->S를 할때 보낸 nonce 값이다. 따라서 이것을 S->A 메시지 않에 추가해서 넣어주면, A의 요청에 대한 S의 응답이라는것이 증명되는 것이다. 즉, 딴놈이 가짜로 응답한는것을 막을 수가 있다. 또한 S 만이 A의 비밀키를 알고 있기 때문에 이 메시지가 S에게서 보내졌다고 믿을 수 있다. 



 

(2) 5번 과정에서 {NB }KAB 를 보낼 경우, 이 방식이 안전하지 못하게 되는 이유를 설명하시오.

 

-> 만약 5번과전에서 {NB }KAB를 보내는 방식이라면 NB 의 값을 몰라도 4번 단계의 날아가는 메시지를 중간에 가로채서 B에게 보내게 되면 B는 메시지가 제대로 들어왔다고 생각하게 되어 보안이 뚫리게 된다하지만 {NB – 1}KAB 로 할 경우 NB 값을 알아야만 하므로 더 안전하다고 할 수 있다.




5. Message-oriented middleware remote procedure-call 기반 미들웨어의 특징을 각각 간단히 서술하고 장단점을 비교하시오.


. Message-oriented middleware

상이한 애플리케이션 간 통신으로 일반적으로 비동기 방식으로 지원하는 메시지 전달을 기반으로 한 것을 가리킨다. message queue를 이용하여 전달된 메시지가 활성화 될 때 까지 수집하고 저장한다.

 

- 동기식/비동기식 모두를 지원 (그러나 대부분 큐를 사용한 비동기적방식 사용)

- Non-blocking

- 큐를 이용하여 한쪽 에플리케이션으로부터 다른 쪽 에플리케이션으로 메시지 전송

- Message queue API 제공

- 베이스 스테이션 결함 허용

- 환경 설정 간단함

 

. remote procedure-call

하나의 프로그램이 네트워크에 연결되어있는 다른 컴퓨터에서 서브루틴이나 프로시저를 실행할 수 있도록 한 IPC(프로세스간의 통신)이라고 할 수 있다. 쉽게 말하면, 내 프로그램이 다른 컴퓨터에서 실행되고 있는 프로그램 내의 함수를 실행할 수 있도록 하는 것이다. 일종의 서버 클라이언트 개념이다.

 

- 동기식 방식

- senderreceiver 모두 동시에 on-line상태야 통신이 가능하다.

- 함수 처리결과가 올 때까지 blocking상태이다.

 

. /단점

RPC는 동기식 방식 통신으로 즉각적이고 빠른 통신이 필요한 경우에 적합하다. 은행 창구에서의 입금이나 출금 등과 같이 즉각적인 응답이 필요한 온라인 업무에서 필요하다. 하지만 분산환경에서 상이한 애플리케이션들은 항상 같은 시간에 동작하고 있지 않으며 네트워크 상황이나 서로다른 애플리케이션들의 변경상항들로 인하여 이기종간의 네트워크 분산화를 어렵게 만드는 요인이 된다.

MOM은 일반적으로 비동기적 방식 으로 사용한다. 즉각적인 응답을 원하는 경우가 아니라 다소 느리고 안정적인 응답을 필요로 하는 경우에 많이 사용된다. 여러 가지 일을 종합적으로 처리한 후에야 결과가 나오는 통계 작성 등에는 메시지 기반 미들웨어가 상당한 장점이 있다.

또한 프로그램들은 각각 다른 시간에 실행이 가능하며, 애플리케이션의 구조상에 별다른 제한이 없으며, many-to-one의 통신 형태로 서로 통신이 가능하다. 이기종간의 네트워크 분산화를 쉽게 구성할 수 있다


6. Web Service Description Language 에 대해 설명하시오.

 

1. 웹 서비스 기술 언어 WSDL(Web Service Description Language)

 

. WSDL의 정의

- 웹 서비스의 서식과 프로토콜을 표준 방식으로 기술하고 게시하기 위한 언어이다.

- 추상화/구체화 파트가 존재한다.

. WSDL의 역할

- 서비스 컴포넌트에서의 인터페이스 기술

- OpenXML 기반의 명세를 통하여 서비스를 이용하고자 하는 사용자의 참조

 

2. WSDL의 구조 및 구성요소

. 웹서비스를 위한 wsdl의 구조


-------------------------------요 위까지만 적으면 답일꺼 같습니다. 밑은 참고 자료----------------------

 

 

. WSDL의 구성요소


 

 

 

 

7. 프로세스나 객체들간 통신 시 marshalling 이 이용되어야 하는 (1) 필요성 (2) 그 역할을 설명하시오.

 

1) 필요성 : 분산화 환경을 쉽고 빠르게 구성하고 프로세서 간의 서비스(객체)를 사용하기 위해서 프로세서나 객체의 형태와는 관계없이 사용할 수 있는 방식이 필요하였다.

 

 

2) 역할 : 클라이언트에서 원격 객체를 호출하기 위해서 필요한 모든 정보를 묶어서 클라이언트에게 전송하여 클라이언트가 사용하고자 하는 객체의 형태에 관계없이 같은 방식으로 인터페이스 함수를 사용할 수 있게 해준다.


'Computer Science > 분산처리 시스템' 카테고리의 다른 글

Distributed Transactions  (0) 2013.06.03
Time  (0) 2013.06.03
Naming Server  (0) 2013.05.28

Distributed Transactions


0. Overview

이 장에서는 Distributed transaction들이 필요하다. 이것들은 하나 이상의 server에서 야기되어 지는 것을 말한다. 


Dirtributed transaction들은 flat이거나 nested인 것을 말한다.

2단게로 구성되어진 아토믹한 커밋 프로토콜을 배운다.

분산환경에서 어떻게 컨커런시를 컨트롤하는지를 배운다.

어떻게 분산황경에서의 데드락을 찾아내는지에 대한것을 다룬다. 이것을 찾아내는 알고리즘도 배운다.

서버가 실패 했을때 어떻게 복구하는지에 대해서도 배운다. 


1. Introduction


트렌젝션은 모두 원자성을 띄면서 처리가 되어져야 한다. 

이러한 것을 모두 달성하기 위해서, 서버들 중에 하나가 coordinator 규칙을 따라야 한다. 이 cordinator 룰을 반영하는 서버는 모든 서버들의 결과가 동일할것임을 보장하게 된다.

이러한 방법론은 프로토콜에 의존되어 진다.

현재 많이 알려진 프로토콜이 Two-Phase commit protocol이다.


14.2 Flat and nested distributed transactions


2개의 서로다른 구조가 존재한다. Flat과 nested이다.

Flat transaction이란, 클라이언트가 요청을 하나 이상의 서버로 보내는것을 말한다. 17.1의 예제를 보면, 클라이언트에서 T 트렌젝션이 서버 X,Y,Z로 가는것을 볼 수 있다. 주목할것은, flat transaction은 순차적으로 완료된다는 것이다. 즉, 서버 X로 간 transaction이 완료되어야 서버 Y로 가게된다. 따라서 어떤 서버가 locking을 하고 있다면, 그것에 대한 트렌젝션은 그 오브젝트가 완료될때까지 대기하게된다.


Nested transcation이란, Top-level transaction은 서브 트렌젝션을 오픈 할 수 있다. 그리고 각각의 서브 트렌젝션은 자기보다 더 낮은 서브 트렌젝션을 오픈 할 수 있다. 17.1의 예제를 보면, 트렌젝션 T가 2개의 트렌젝션 t1,t2를 오픈하는것을 볼수 있다. 이 두 트렌젝션은 서버 X와 Y의 오브젝트들을 엑세스 하게 된다. 그 다음, T1,T2의 서브트렌젝션은  T11,T12,T21,T22에 대한 트렌젝션을 오픈하게 된다.그리고 이 새롭게 오픈된 서브 트렌젝션들은 다시 M N P 서버들의 오브젝트들을 접근하게 된다. 

이러한 네스티드 에서는 같은 레벨에서의 서브 트렌젝션들은 컨커런시 할 수 있다. 그리고 서로 다른 서버에서 각기다른 오브젝트를 접근한다.

즉, T1,T2가 동시성 발생, T11,T12,T21,T22가 동시성이 발생한다.



우리는 분산 트렌젝션을 다음과 같이 고려해 본다. 그림 17.2와 같이 10달러를 계좌 A와 C에 대해서 발생 시키고, 20달러를 B와 D에 대해서 발생 시킨다. 그리고 A와 B는 서로다른 서버이고 C,D는 같은 서버이다. 


위와 같은 작업을 하나의 셋으로 구성된 4개의 Nested 트렌젝션으로 구성하면그림 17.2와 같다.

여기서 주목할것은, 네스티드이기 떄문에 4개의 트렌젝션이 모두 컨커런트하게 실행되어 질수 있고 심플 트렌젝션보다 성능이 좋다는것이다. 왜냐하면 심플의 경우 4개의 오퍼레이션들이 모두 순차적으로 발생되어지기 때문이다.




14.2.1 The coordinator of a distributed transaction.


아래의 그림 17.3은 하나의 서버가 조정자가 되는것이다


뭔가 작업이 이뤄지는 서버들은 항상 조정자 서버와의 통신이 필요하다. 즉, 커밋을 할려면 항상 조정자 서버에게 허락을 받아야 하는것이다.


그림 17.3을 보면 우선 클라이언트는 조정자로 openTransaction을 요청 한다. 그다음 조정자는 트렌젝션 구분자를 리턴하게 된다. 이 트렌젝션 구분자는 분산 시스템에서 유일한 값을 가지는 것이다. 이것을 위해서 TID는 2가지 부분으로 구성되어질 수 있다. 1) Server identifier (for example, an IP address)와 2) 서버내에서 생선한 unique한 number를 조합해서 사용할 수 있다.


이렇게 조정자가 해당 트렌젝션을 오픈을 허가 했을경우에, 조정자는 앞으로 분산환경에서 발생하게될 해당 트렌젝션에 대한 커미팅과 어볼팅을 모두 책임지게 된다. 즉 반환받은 T를 이용해서 항상 클라이언트는 작업을 요청하게된다. 

participant: 이제 각각의 서버들은 트렌젝션에 참여를 할 것이다. 그리고 이 트렌젝션에 참여한 오브젝트들은 서버마다 각기 다를것이다. 이렇게 트렌젝션에 참여를한 오브젝트들의 집합을 participant라고 정의한다.

participant는 모든 recoverable object들에 대한 유지를 책임진다.

participant는 조정자가 커밋 프로토콜에서 케리아웃 하는것에 대한 협조를 책임진다.


트렌젝션이 진행되어지는 동안, 조정자는 기록 한다. 참조 리스트를 participant들로 가는 그리고 각각의 participant 기록들을 coordinator들에 대한 참조를.


조정자의 인터페이스는 아래와 같이 4개가 있다.

openTransaction() -> trans;

closeTransaction() -> (commit, abort);

abortTransaction()

join(Trans, reference to participant) // 새로운 participant가 transaction에 합류 했는지를 확인 한다.



그림 17.3에 대해서 설명을 한다.

본 구조는 flat banking 구조를 따른다. Branch X, Branch Y, Branch Z.는 각각의 서버를 나타낸다.


하나의 예로 클라이언트에서 b.withdraw를 하게된다면, 조정자에게 해당 작업을 요청한다. 이때 해당 트렌젝션에 필요로한 participant가 있다면 그냥 그걸 실행 하면 되고, 없다면 join을 발생시켜서 조정자가 해당 reference를 트렌젝션에 인가한다. 이렇게해서 작업을 모두 처리하고 나면, closeTransaction을 해서 모든 reference를 제거한다.

주목할 것은, abortTransaction을 이용해서 조정자는 participant를 transaction에서 제거 할 수 있다.




14.3 Atomic commit protocols.


분산환경에서의 transaction은 atomic 해야한다. 즉 모든 트렌젝션이 실행 되거나, 아니면 실행이 아에 안되야 한다. 그 사이의 상태는 있을수 없다.

이것을 구현하기위한 간단한 방법은, 조정자가 커밋과 어볼트를 모든 참여자에 대해서 처리하는 것이다. 이러한 방법을 on-phase atomic commit protocol. 이라고 한다


단점: 이 방법은 서버 스스로 트렌젝션에 대한 어보트와 커밋을 결정할 수 없기 때문에 문제가 된다. 왜냐하면, 리소스에대한 락킹 매커니즘을 사용했을때, 데드락이 발생할 수 있고, 그경우 서버는 클라이언트가 인지하지 못하는 상태에서도, 스스로가 트렌젝션을 어보트 해야한다. 하지만 이 방법은 서버 스스로가 어보트를 시킬수 없기 때문에 데드락을 해결할 수가 없다. 이것을 조정자가 처리해주기에는 조정자는 가각의 서버들이 언제 크래쉬 되었는지를 알아내기 어렵다.



Two-phase commit protocol.

이 개념이 나온 이유는, participant 스스로가 트렌젝션의 일부분을 abort 시키기 위함이다. 이렇게해야 데드락 문제를 발생 시키지 않는다. 하지만 트렌젝션은 atomic해야 하기 때문에 트렌젝션의 일부분이 어보트 되더라도 트렌젝션 전체가 다시 롤백해야한다. 이 문제를 다시 해결 해야한다.


첫 번째 phase에서는, 각각의 participant가 트렌젝션에 대해서 commit인지 abort인지를 투표하게 된다. 일단 하나의 participant라도 commit을 투표한다면, 절대로 abort 되어질 수 없다. 따라서 참여자의 커밋은 신중해야하며, 궁극적으론 어떠한 문제조 발생 시키지 않는다는것을 보장해야 한다. 

그리고 이것을 위해서 준비단계에서 모든 오브젝트를 트로지에 저장하게 된다.


두 번째 phase에서는, 모든 참여자들은 joint decision을 싱행하게 된다. 만약 어떤 하나의 참여자가 어보트를 투표하게 된다면, 그때 반드시 트렌젝션 전체가 어보트 되어저여햔다. 

모든 참여자가 커밋을 요청 했을 때마 트렌젝션은 커밋 되어 질수 있다. 


문제점: 모든 참여자들의 투표를 검증하는 것이 문제이다. 즉 실패해대한 처리가 어렵다.



14.3.1 The two-phase commit protocol


결국 핵심 알고리즘은 17.5와 같다.

2개의 Phase는 voting과 vote 결과에 따르는 완료로 구성되어진다.


2단계 끝 부분에서, 조정자와 모든 참여자들은 Yes를 투표하면 즉시 영송적인 저장 장치에 해당 트렌젝션을 저장해서 커밋을 위한 준비를 한다. 만약 No라고 하면 즉시 버린다.


3을 보면 조정자는 투표들을 수집하게 된다.

3-a) 모든 투표가 Yes 라면. 조정자는 커밋을 결정한다. 그리고 doCommit 요청을 각각의 참여자들에게 보낸다.

3-b) 달느 한편으로, 조정자는 트렌젝션의 어보트와 doAbort 요청을 투표시 yes를한 모든 참여자들에게 보낸다. No라고 한 참여자들은 스스로 알아서 어보트 했기 때문에 보낼 필요가 없다.


4에서는 yes를 투표한 참여자들은 조정자로부터 doCommit 또는 doAbort 요청 메시지를 받을때 까지 기다리게 된다. 만약 참여자가 이 두 메시지중 1개를 받는다면, 그것에따라서 동작하게 된다. 그리고 만약 commit의 경우 haveCommitted를 호출해서 조정자에게 정상저으로 커밋 했다는것을 최종적으로 알리게 된다.





14.3.2 Two-phase commit protocol for nested transactions


가장 바깥쪽의 transaction T가 서브 트렌젝션은 t1,t2,t11,t12,t21,t22는 서브트렌젝션.

각각의 서브 트렌젝션은 그것의 부모 이후에 시작하게 된다. 그리고 그것 이전에 끝나게 된다.

따라서, t11과 t12가 t1 이후에 시작하게대고, 끝나는것은 t1 이전에 끝나게 된다.


서브트렌젹센이 완료되었을때, 그것은 독립적으로 결정하게 된다. 일시적인 커밋과 abort를 

일시적인 commit은 prepared commit과는 다르다. 그것은 permanent storage에 back-up하는것과는 다르다.

만약 서버가 커밋이후에 crash되어 진다면, 커밋 교체는 가능하지 않다. 왜냐면 영속적인 저장 장치에 백업을 하지 않았기 때문이다. 

따라서 Two-phase commit 프로토콜을 사용해서 nested transaction을 수행하는것이 올바르다.


서브 트렌젝션을 위한 조정자는 서브 트렌젝션을 오픈하는 operation을 제공한다. 그것은 Top-level 트렌젝션을 위한 구분자를 리턴한다. 클라이언트는 서브 트렌젝션을 시작한다. openSubTransaction 오퍼레인션을 실행 시켜서, 이것에 대한 동의는 부모 트렌젝션이 승인하게 된다. 새로운 서브트렌젝션들은 자동으로 parent 트렌젝션들에게로 조인하게 된다 그리고 서브트렌젝션을 위한 트렌젝션 구분자들은 리턴된다.


서브트렌젝션을 위한 구분자는 반드시 부모 트렌젝션의 TID를 확장해서 만들어 져야한다. 즉, 모든 시스템에서 유니크한 정보를 담고 있어야한다. 클라이언트는 최종적으로 트렌젝션을 완료하게 되면, closeTransaction 또는 abortTransaction탑 레벨 트렌젝션 조정자에서 실행 시켜서 끝내게 된다.


nested transaction들이 그것의 오퍼레이션들에 의해서 실행되어 지게 된다. 그리고 그것들이 완료 되었을 때, 서버는 서브트렌젝션들이 일시적으로 committed 되었는지 아니면 aborted 되었는지를 기록하게 된다. 

주목할것은, 만약 부모의 트렌젝션이 abort되었다면 반드시 서브트렌젝션들은 강제로 abort 되어야 한다.



탑 레벨 트렌젝션 T와 그곳의 서브트렌젝션은 그림 17.8과 같다. 이 그림은 17.1을 기반으로 새롭게 작성한것이다. 각각의 서브트렌젝션들은 임시적으로 committed 또는 aborted를 실행하게 된다. 예를들면, T12는 임시적으로 커밋을 수행 했다. 그리고 T11은 abort를 실행 했다. 

T12는 부모 트렌젝션인 T1에 의해서 자신의 운명이 결정되어지며, 궁극적으로 top-level 트렌젝션 T에 의해서 모든 서브트렌젝션들이 결정되어 진다. 

즉, T21T22가 둘다 잠정적으로 커밋했더라도 T2가 어보트 할경우 이 두개는 반드시 어보트 되어진다. 

(분산 트렌젝션의 원자성의 원리에 근거해서)

T는 비록 T2가 aborted이지만 커밋일 수 있다. 또한 T1은 커밋을 결정할 수 있다 비록 T11이 어보트일지라도.


최상위 레벨 트렌젝션이 완료되었을 때, 그것의 조정자는 Two-phase commit protocol을 실행하게 된다.  

오직한가지 이유가 있다. 참여자의 서브트렌젝션이 완료되어지지 못하는 경우는, 만약 crashed되어지는 시점이 임시 커밋이 이뤄진다음일 경우이다.

조정자는 parent와 서브 트렌젝션들에대한 모든 상태들을 알고 있어야 한다. 모든 서브트렌젝션은 어보트할경우 부모 트렌젝션에게 반드시 이를 보고한다. 따라서 최상위 수준의 트렌젝션은 모두 하위 서브트렌젝션의 상태에 대해서 알 수 있다. 그리고 조정자는 이 최상위 수준의 트렌젝션이 가지고 있는 정보만 참조하면 되는 것이다.




17.8을 기반으로 각각의 조정자가 가지고 있는 정보를 표현한 것이 그림 17.9이다. 

주목할것은, T12,T21은 조정자의 정보를 공유한것이다. 왜냐하면 같은 서버 N에서 동작하기 때문이다.

서브트렌젝션 T2가 어보트 되었을때, 그 사실은 부모인 T 트렌젝션에게로 보고 된다. 하지만 T21, T22 서브트렌젝션들에 대한 정보는 전달하지 않는다. 왜냐하면 T2가 어보트했기때문에 그 자식인 두 서브트렌젝션의 정보는 무엇이 되었는 상관이 없기 때문이다.

서브트렌젝션의 고아현상(orphan)은 다음과 같다.만약 조상중에 하나가 어보트 되었거나, 그것의 조정자가 crash 되었기 때문이다. 

우리의 예제에서는, T21과 T22가 고아이다. 왜냐하면, 그들의 부모가 탑 레벨 트렌젝션에 자신들의 정보를 넘기지않고 어버트 되어졌기 때문이다. 하지만 조정자는 그들의 parent의 상태를 조사하게된다. getStatus operation을 사용해서. T21T22는 모두 provisionally committed 이지만 그냥 aborted 되어 진다. 최상위 레벨 트렌젝션이 커밋 되어지더라고 상관없이, 왜냐하면 자신의 부모가 어보트 되어졌기 때문이다.


이제 TPC(Two phase commit)을 수행한다. 투표를 하게될 참여자 들은 T, T1, T12 이다. 다른것들은 모두 어보트 되었거나 고아이기 때문에 투표를 하지 않는다. 

phase 1: 커밋을 투표한다면, 반드시 그들의 트렌젝션 내용은 영속적인 저장장치에 저장이 되어야 한다.

phase 2: 조정자는 투표결과를 수집하고 참여자들의 결과에 대해서 확인 한다.

이때 phase2에서의 동작방식은 non nested case일때와 동일하다.

그렇게 해서 최종적으로 참여자들의 투표 결과에 따라 aborted 인지 커밋인지를 결정한다.


이제 TPC protocol을 2가지 방식으로 수행한다. hierarchic or flat 방법이다.


Hierarchic two-phase commit protocol: 

이 접근법은, two-phase commit protocol은 멀티레벨 네스티드 프로토콜이 된다. 

최상위 레벨 트렌젝션 조정자는 서브 트렌젝션 조정자와 통신을 한다. 이렇게 연결된 각각의 조정자들은 canCommit?이라는 메시지를 보내서 확인을 한다. 이것은 트리구조로써 점점 하위로가면서 처리가 되어지는 형태이다. 각각의 참여자들은 그들의 부모에게 보고하기전에 자손들의 응답을 모두 받은다음에 부모에게 최종적으로 응답하게 된다. 

우리의 예제를 통해서 설명을 하면 다음과 같다.

T는 canCommit? 이라는 메시지를 조정자 T1에게 보낸다. 그리고 T1은 canCommit? 이라는 메시지를 T1의 자식인 T12에게 전송한다. T2는 어보트 했기 때문에 투표에 참여하지 않는다.


canCommit의 아규먼트에 대해서 알아보자.

첫 번 째 아규먼트인 TID는 최상위 레벨 트렌젝션의 것이다. 이것은 데이터를 준비할때 사용한다.

두번째 아규먼트는 참여자에 대한 TID이다. 이 두번쨰 아규먼트를 통해서 호출에 대한 결과값 구분을 하게 된다.

예를들어서 조정자 T12와 T21은 서로 같다. 왜냐하면 이것은 같은 서버에서 동작하는 서브 트렌젝션이기 때문이다. 하지만 canCommit? 콜에대한 리턴을 받을때, 두번째 아규먼트는 T1 이고 그것은 T12로 다뤄 질 것이다.

canCommit? (trans,subTrans) -> Yes/No



Flat two-phase commit protocol: 

canCommit? (trans,abortList) -> Yes/No


조종자가 모든 임시적으로 커밋을한 참여자들에 대해서 투표를 요청하게 된다. 그러면 참여자들은 Yes/No를 투표하게 된다.


이것의 핵심은 최상위 레벨 조정자가 canCommit을 보낸다는 것이다. 모든 provisional list에 있는 서브트렌젝션의 조정자들에게 말이다.


 

3. Concurrency Control in Distributed Transactions


컨커런시한 트렌젝션이 실행 될수 있으므로, 각각의 서버들은 이것을 메니지 해줘야한다.

즉, 트렌젝션 U와 T가 같은 서버에서 실행되고 공통의 자원에 대해서 엑세스를 한다면, 그것의 순서를 반드시 메니지 해줘야 한다는 것이다.


14.4.1 Locking


락은 같은 서버에서 지역적으로만 유지가 된다.

로컬 락의 매니지먼트 방법은 다음과 같다.

락의 승인을 요청허가나 그것이 안되면 문제가 발생한 트렌젝션이 끝날때가지 기다려야한다.


분산에서 데드락이 발생하는 상황은 아래와 같다.




이 문제는 트렌젝션의 어보트를 통해서 해결할 수 있다. 결국 이래서 TPC를 사용해야 하는것이다.


14.4.2 Timestamp Ordering Concurrency Control


싱글 서버 트렌젝션은 유니크한 타임스템프를 가진다.



14.5 Distributed deadlocks


분산에서는 wait-for graph을 그려서 찾을 수가 있다. 분산환경에서의 데드락을


Wait-for graph

1) Node: transactions and data item

2) Edges: a data item that held or waited by a transaction 




위 그림 17.2는 분산 데드락이 있는 트렌젝션들이다.

우선 트렌젝션은 U,V,W가 있다 이 3개는 상호 작용을 하면서 동작을 한다.

오브젝트 A는 서버 X

오브젝트 B는 서버 Y

오브젝트 C와 D는 서버 Z


위 관계를 wait-for graph으로 그린것은 그림 17.3과 같다.

그림 (a)는 모든 에지들로 구성된 데드락 사이클을 보여준다. 트렌젝션 때문에 기다리는 오브젝트와 그리고 트렌젝션을 유지하고 있는 오브젝트를 나타내고 있다. 단순히 기다리고 있는 오브젝트들에 대해서만 그림을 그린것이 (b)이다.



결국 이러한 분산 데드락을 발견해 내기 위해서는, local wait for graph을 그려야한다. 이것을 각각의 서버에 대해서 생성을 하면 아래와 같다.


Server Y: U-> V (added when U requests b.withdraw(30))

Server Z: V->W (added when V requests c.withdraw(20))

Server C: W->U (added when W.requests a.withdraw(2))


그리고 위와 같은 local deadlock을 합쳐서 global wait for graph을 생성하면 된다.



Centralized deadlock detection 

이러한 deadlock을 찾아내는 간단한 솔루션은  Centralized deadlock detection 기술이다.


각각의 서버들이 자신들의 local-wait-graph을 중앙서버로 전송을 하고, 그것을 합병해서 global wait-for graph을 생성하게 된다. 그 다음, global deadlock detector는 각각의 사이클을 체크해서 분산 데드락을 찾게 된다.

데드락을 찾으면 해당 서버에게 트렌젝션을 어보트 시켜서 해결을 할것인지를 확인하게 된다.


단점: 

하지만 이것은 좋은 생각이 아니다. 이러한 방식은 싱글서버로 전달해야하는 문제점이 있다.

이러한 문제점은 다음과 같은 단점을 야기 시킨다,.

1) 접근성이 떨어진다.

2) 고장 허용이 약해진다.

3) 확장성이 떨어진다.

4) 주기적으로 local wait for graphs를 전송하는것은 비용이 많이 든다. 주기를 떨어 틀이면 데드락 디텍션 시간이 길어지기 때문에 주기를 마냥 길게할 수도 없다.


Phantom deadlocks: 데드락을 찾았지만 실제 데드락이 아닌것을 부르는 말이다. 

즉, 데드락을 찾기위해서 정보를 병합하는 과정에 데드락이 이미 해결되었는데, 그 정보가 제대로 반영이 되지 않았을 경우에 발생하는 문제이다.


잘이해가 안가니 예제를 들어서 설명하도록 하겠다.

X와 Y로 부터 Local wait for graph를 받았다고 치자. 

T->U (at X)

V->T (at Y)

이상태인대 이제 T->U이게 바뀌여서 U->V를 한다고 치자.

그럼 U->V->T가 된다.

그런데 여기서 global detector가 서버 X에 대한 local wait for graph을 갱신받지 않았다면,

T->U는 이미 존재하지도 않은 트렌젝션이지만 이걸 반영해서

T->U->V->T 라는 global wait for graph을 생성하게 되어서, deadlock이 있다고 판단해 버린다. 이러한 경우를 팬텀 데드락이라고 한다. 


Edge chasing (Path Pushing)


이방법은 global wait for graph를 구성하지 않는다. 각각의 서버들은 그것의 edge들에 대해서 알고 있는 지식을들 전송한다. 서버들은 사이클들을 찾으려고 노력한다. 서로 probe을 전송하면서, 

probe는 분산 시스템 전반에 걸친 edge들에 대한 내용이다. 

prob 메시지는  트레젠셕의 관계들로 구성되어 진다.

즉 이것은 서버들의 전체적인 에지를 말하게된다.




첫번째 질문: 서버는 언제 probe를 전송 하는가?


이 알고리즘은 3가지 스탭을 가진다.

initiation, detection and resolution


initiation: 서버 T 트렌젝션이 시작하자마자 다른 트렌젝션 U 때문에 웨이팅 되어지는 것을 인지하게 된다. 이러한 관계를 초기에 발견하고 edge를 생성하게 된다 그것이 T->U 이다. 그리고 U는 블럭 되어져 있는 상태이다. 



detection

이 단계는 probes의 receiving과 deadlock 발생의 구분, probe의 포워드로 구성된다.


예를들어서, 서버는 probe <T->U>를 받았다고 치자. <T->U>는 T는 트린젝션 U에 대해서 기다리고 있는 것을 나타낸다. 왜냐하면 U는 local object를 홀드하고 있기 때문이다.

그곳은 U 또한 기다리고 있는 상태인지를 체크하게 된다. 만약 그 U 트렌젝션 또한 V 라는 트렌젝션에 의해서 대기중이라면, probe를 추가한다. ( making it <T->U->V>


이렇게하여서, global wait for graph의 path들을 통과하는 하나의 edge가 생성되게 되어진다. 



resolution

사이클을 찾아냈을떄 사이클 내의 트렌젝션을 오버트해서 데드락을 제거한다.



그림 17.5의 예제를 들어서 Edge chasing 방법을 설명하도록 하겠다.


  • 서버 X는 초기 발견을 해서 probe< W->U >을 B의 서버(Server Y)로 전송 한다.

  • 서버 Y는  probe< W->U >을 받는다. 주목할것은 B는 트렌젝션 V에 의해서 홀드되어지고 있다. 따라서 V는  probe< W->U >에 추가되어지고  probe< W->U->V >가 되어진다. 그리고 V가 기다리고 있는 C의 서버 Z에게 이 probe를 포워드 한다.

  • 서버 Z은 probe< W->U->V >을 받는다. 그리고 Z는 자신의 객체 C가 트렌젝션 W에 의해서 홀드되어져 있기 때문에 이것은 현재 전송받은 probe에 추가한다. 최종적으로 probe< W->U->V ->W >가 생성 된다.










'Computer Science > 분산처리 시스템' 카테고리의 다른 글

샘플 문제 풀기  (0) 2013.06.04
Time  (0) 2013.06.03
Naming Server  (0) 2013.05.28

11.3.2 Cristian's method for synchronizing clocks


간단하게 계산하면 프로세스 P의 지연 시간은





11.3.4 The Network Time Protocol


Cristian's method나 Berkeley algorithm은 인트라넷을 위한 것이다. 


이장에서 다룰 Network Time protocol은 순전히 인터넷위에서의 타임 서비스와 분산환경에서의 타임 프로토콜을 위한 아키텍쳐이다.


NTP의 중요한 디자인 이념은 다음을 따른다.


인터넷 전반에 걸쳐서 클라이언트 서비스가 정확히 동기화되게 가능하도록 지원한다.

비록 인터넷 환경은 딜레이가 있지만, NTP는 통계적인 기술들을 이용해서 타이밍 데이터를 필터링하고 타이밍 데이터를 서로다른 서버들로부터 그 퀄리티를 식별해 내게 된다.





11.4 Logical time and logical clocks


어떤 이벤트가 발생했고 이러한 이벤트들의 쌍들에 대해서 정확하게 그 인과관계를 알아내는것은 어렵다. 이것을 지원하기 위한 매커니즘이다.


아래의 직관적인 두가지 포인트에 기반해서 이러한 인과관계를 파악하게 된다.

1) 같은 프로세스에서라면 이벤트들의 순서를 정할 수 있다.

2) 언제든지 발생된 이벤트들에대한 정보를 다른 프로세스들에게로 전송 할 수 있다.


Lamport called the partial ordering obtained by generalizing these two relationships the happened-before the vent of receiving the message



이러한 원리들에 대해서 그림을 보며 이해를 하자.



그림 11.5를 보면 3개의 프로세스들이 정의가 되어 있다. 


여기서 핵심은 모든 이벤트들이 관계가 명확히 파악 되어지는것은 아니다. 

즉, a -> e 인지는 알 수 없다. 왜냐하면 서로 다른 프로세스에서 실행 되어졌기 때문이다. 그리고 그것들 사이에 어떠한 메시지 체인도 없기 때문에 더더욱 알 수가 없다.

우리는 이러한 이벤트들을 순서를 정할 수 없다고 하며 이것을 concurrent 하다고 한다.

그리고 그것을 a || e 라고 기술 한다.


Logical clock:


Lamport는 간단한 numerically에 기반한 이벤트 상관 관계를 기록하는 매커니즘을 개발 했다.

결국, Lamport logical clock은 단조 증가하는 소프트웨어 카운터이다. Lamport logical clock는 physical clock에 대한 정보를 가지고 있을 필요가 없다. 각각의 프로세스 pi들은 그것들이 소유하는 logical clock을 유지하고 있다. Li라고 그것을 부르며, 이것은 Lamport timestamp들에 의해서 적용되어 진다. 

우리는 프로세스 pi에서의 이벤트 e의 타임스탬프를 Li(e) 와 L(e)로 표현한다. 우리의 이 표식은 이벤트 e가 어떤 프로세스에서도 발생할수 있음을 뜻한다.






상관 관게를 기록하기 위해서, 프로세스들은 그들의 logical clock들을 갱신하고 메시지에서의 그들의 logical clock들의 값을 전송 한다. 다음과 같이.


LC1: Li는 증가 되어진다. 각각의 이벤트 이전에 그것들이 pi에 의해서 이슈화되기 이전에

Li = Li + 1


LC2: (a) 프로세스 Pi가 메시지 m을 전송 했을 때, 그것은 메시지 m에 올라타서 값이 전송되어 진다.

t = Li

(b) (m,t)를 받고, 


비록 클락이 1씩 증가할지라도, 우리는 선택해 왔다 어떤 positive 값을. 그것은 어떤 이벤트들의 순서 관계에 의한 유도가 쉽게 파악될 수 있다. 

즉,  event e와 e'이 e-> e' => L(e) < L(e') 이다.


주목할 것은, 위 명제의 convers는 참이 아니다. 즉, L(e) < L(e')라고 해서, 우리는 e->e'라고 추론 할수는 없다. 

위 그림은 이전의 그림에 대한 logical clock들에 대한 그림으로 전환한 것이다. 

각각의 프로세스들 p1,p2,p3들은 초기 0의 logical clock을 가지게 된다.

The clock values given are those immediately after the event to which they are adjacent.

주목할것은, L(b) > L(e)  but b || e.


Totally ordered logical clocks





모든 페어들에 대해서 구별 가능하게 한다. 프로세스 구분자를 사용해서

즉, local Time stamp는 T이다.

(T1,p1) < (T2,p2) if either T1 < T2 or T1 = T2 and p1 < p2



Vector clocks ◇


vector clock은 Lamport timestamp가 가지는 단점을 극복하기 위해서 개발 되어 졌다.

이 단점이란 다음과 같다. 

의 경우 우리는 e와 e'의 관게를 결정 할 수 없다.

왜냐하면, 논리적인 클란은 물리적인 클락과 관계가없고 서로다른 프로세스에서 어떠한 상관 관계도 알 수 없기 때문이다.


N개의 프로세스에서의 벡터 클락은 N integer들의 array 이다. 각각의 프로세스들은 그것들의 vector clock Vi를 유지하게 된다. 이것은 local event들의 타임스탬프를 사용한다. Lamport 타임스탬프와 같이, 프로세스들은 벡터 타임스탬프들을 메시지위에 실어서 다른 프로세스로 보내게 된다. 그리고 다음과 같은 규칙에 의해서 그것을 갱신하게 된다.





아래의 그림14,7을 해석하면 아래와 같다.

V(a) < V(f)를 나타냄을 알 수 있다. 이것은 a->f라는것을 유도해 낼 수 있다. 비슷하게 우리는 2개의 이벤트가 concurrent할때 2개의 타임스탬프를 비교해서 이것을 구분해 낼 수 있다.

For example, that c ||e can be seen from the facts that neither V(c) <=  V(e) nor V(e) <= V(c).




벡터 타임 스탬프의 단점은 , 프로세스의 수 N에 비례해서 storage의 크기와 message payload가 늘어난다는 점이다.





'Computer Science > 분산처리 시스템' 카테고리의 다른 글

샘플 문제 풀기  (0) 2013.06.04
Distributed Transactions  (0) 2013.06.03
Naming Server  (0) 2013.05.28

non-recursive server-controlled navigation 아래에서는 어떠한 named server가 클라이언트에 의해서 선택 되어 진다. 

'Computer Science > 분산처리 시스템' 카테고리의 다른 글

샘플 문제 풀기  (0) 2013.06.04
Distributed Transactions  (0) 2013.06.03
Time  (0) 2013.06.03

+ Recent posts