'Total ordered multicasting'에 해당되는 글 1건

  1. 2010.08.13 Totally Ordered Multicasting
이전에 Lamport algoritim(http://kukuta.tistory.com/105)과 알고리즘에 사용되는 개념에 대해 알아 본적이 있다. 오늘은 좀 더 심화된 과정으로써 Lamport 알고리즘을 이용하는 Totally Ordered Multicasting에 대해서 알아보도록 하겠다.

Totally Ordered Multicasting이란?
Totally Ordered Multicasting이란 "모든 프로세스가 바라 보는 모든 메시지(이벤트)의 순서가 동일함을 보장"하는 멀티캐스팅 방법이다. 그리고 여기에 우리가 이전에 공부했던 Lamport 알고리즘이 사용될 수 있다.

왜 필요 한가?
먼저 왜 이런 멀티 캐스팅이 필요한지 예를 살펴 보자 :

전국에 걸친 지점을 가진 어떤 은행이 있다. 전국에 여러 개의 DB를 설치 해두고 각 지점은 가장 가까운 DB를 이용하여 업무를 처리한다. 각 DB는 업데이트 될 때마다 다른 지역에 있는 DB에 업데이트 이벤트를 복사해 데이터 동일성을 유지하고 있다. 이 때,

고객이 서울지점에서 1000원이 들어 있는 자신의 계좌에 100원을 입금하려 하고, 부산에 있는 은행 본점은 이 계좌에 1%의 이자를 주려고 했다.

서울 지점 은행은 1000원에 100원을 입금 한 후 1%이자 지급 메시지를 받아 1111원의 잔고를 가지게 되었다.
부산 본점 은행은 1000원에 1%이자를 지급한 후 100원을 입급했다는 메시지를 받아 1110원의 잔고를 가지게 되었다.

위의 예에서 처럼 순서가 꼬이면 서로 다른 결과를 가지게 되는 일이 종종 있다. 하지만 여기서 한가지 또 주목 할 것은 실제 시간에서 어떤 이벤트가 먼저 일어 났는지는 그렇게 중요하지 않다는 것이다. 고객의 입금이 먼저 처리 되든, 은행의 이자 지급이 먼저 처리 되든, 양쪽에서 동일한 순서로 처리 되면 되는 것이지 입금이 먼저 처리 되어야 한다, 이자 지급이 먼저 처리 되어야 한다라는 이슈는 없는 것이다(실제 은행 입장에서 보면 이자를 먼저 지급하는게 더 이익일 수 있지만 그런 문제는 은행장이 되면 생각 하도록 하자).

위와 같은 예에서 해답으로 사용 할 수 있는 것이 바로 Totally Ordered Multicasting 이며, 그 것을 구현하기 위해 이용 될 수 있는 것이 Lamport algoritim 이다.

어떻게 구현 되는가?
기본적으로 Totally Ordered Multicasting 은 멀티캐스팅이다. 그래서 아래와 같은 속성을 갖는다 :
  1) 모든 프로세스는 멀티캐스팅 그룹에 있는 다른 모든 프로세스의 존재를 알아야 한다.
  2) 송신자가 전송하는 메시지는 송신자 자신에게도 전달 되어야 한다.

그리고 추가적으로 메시지는 전송 중에 순서가 꼬이지 않는 것을 보장해야만 한다(그래서 보통 TCP를 사용한다).

Totally Ordered Multicasting에서 송신자는 :
  1) 모든 메시지에 timestamp를 찍어서 전송한다.

수신자는 :
  1) 메시지가 수신되면 local queue에 메시지를 저장한다(timestamp에 따른 순서로 정렬 되어야 한다).
  2) 저장 후 멀티캐스팅 그룹 내에 있는 모든 프로세스들에게 ack를 리턴해야 한다(자기 자신도 포함).
  3) 단, ack 메시지에도 timestamp가 찍혀야 하며, 송신자가 보낸 timestamp보다 커야 한다(Lamport 알고리즘에 따라 clock도 앞으로 당겨 주어야 한다).

위와 같은 과정을 거쳐 모든 프로세스들로 부터 ack를 받고 queue에 가장 앞에 있는 메시지라면 현재 그룹 내에서 돌아 다니는 메시지 중에서 가장 timestamp가 빠른 메시지 임이 보장 된다.

아래 그림을 보면서 과정을 정리 해 보도록하자(괄호안의 숫자는 타임 스탬프를 의미한다).

[그림 1] Totall Ordered Multicasting

[그림 1] Totall Ordered Multicasting


  1. 1번에서 프로세스 A는 타임 스탬프가 10일 때 프로세스 B에게 메시지(Msg A)를 보낸다. 
     (기본 개념은 자기 자신에게도 동일한 메시지를 보내고, 그것을 수신하여 로컬 큐에 저장하는 것이지만,  편의상 보내면 받은 것으로 생각하고 바로 로컬 큐에 넣도록 하자)

    이렇게 되면 프로세스 A의 로컬 큐에는 Msg A(t:10) 가 아직 아무런 ACK도 받지 못한 상태로 저장 되게 된다. 다시 한번 말하지만 로컬 큐에서 빠져 나가기 위해서는 큐의 가장 앞에 있을 것이며, 모든 프로세스들로 부터 ACK를 받아야 만한다.
  2. 2번에서 프로세스 A는 자기 자신에게 ACK를 보낸다. 이로써 프로세스 A의 로컬 큐에는 Msg A(t:10) 가 A로 부터 ACK를 받은 상태로 저장 된다.
  3. 지금 부터 중요하다. 3, 4, 5 번 같이 보도록 하자. 3번은 Totally Ordered Multicasting이 실패 하는 경우를 가정 하고 있다. 

    프로세스 B가 보낸 Ack A가 3번과 같이 Msg B보다 순서가 꼬여 먼저 도착하는 것은 애초에 멀티캐스팅의 제약 조건에 걸린다. 저런식으로 메시지가 꼬일 수 있다면 뭘 해도 안된다.

    5번과 같이 Msg B 보다 늦게 도착 한다면, 로컬 큐의 가장 앞에는 Msg B가 자리 잡고 있기 때문에, 프로세스 A의 Ack가 완료 되더라고 큐에서 빠져 나가지 못하고 Msg B가 완료 될 때 까지 대기 상태가 된다.

    만일 Ack A가 Msg B 보다 먼저 도착하려면 프로세스 B에서 Msg B보다 먼저 보내야 하는데 Ack A 이후에 보내진다는 것은 프로세스 A의 타임스탬프에의해 프로세스 B의 로컬 타임스탬프가 이미 조정 되었음을 의미하므로 큐에 저장될 때 Msg A는 Msg B보다 앞에 정렬 되게 된다.

이런 식으로 각 프로세스는 도착하는 메시지들을 정렬하며, 모든 프로세스가 처리하는 메시지의 순서는 같아지게 된다.

Ref :
 - Distributed Systems - priciples and paradigms(Andrew S. Tanenbaum, Maarten van Steen)
 - [진리는어디에] - Logical clock

Posted by kukuta

댓글을 달아 주세요