'Lamport'에 해당되는 글 2건

  1. 2010.08.13 Totally Ordered Multicasting
  2. 2008.05.02 Logical clock (2)
이전에 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

댓글을 달아 주세요

Logical clock

진리는어디에 2008. 5. 2. 18:15

실세계에서 완벽한 동기화란 없다. 아무리 짧은 시간을 주기로 동기화를 시도해도 결국 네트워크 지연이나 기타등등의 여러가지 이유로 아주 근소한 차이라도 오차는 있기 마련이다.
해서 나온것이 'Logical clock'라는 개념이다. Locgical clock에서 중요하게 생각하는 것은 각 이벤트 간의 인과관계다. 즉 사건 A가 사건 B보다 먼저 발생했다는 것만이 중요한 것이지, 사건 A가 B보다 얼마나 빨리 발생 했느냐 같은 것은 고려 대상이 아니다.
예를 들어서 프로세스 P1가 메시지를 보내고 프로세스 P2가 그 메시지를 받았다고 가정하자. P1가 1이라는 시간에 메시지를 보냈다면 P2가 메시지를 받는 시간은 어쨋거나 1보다만 크면 된다. 2가 됐든 100이 됐든 그것은 중요한 것이 아니라 1의 시간 보다 뒤에 발생 했다는 사실만 증명 할 수 있다면 그것으로 OK다.

위에서 Logical clock이란 인과관계에만 관심을 가진다고 이야기 했다. 그렇다면 아무런 관련이 없는 경우라는 것은 무엇인가 설명 해보도록 하겠다. 두 개의 프로세스 P1, P2가 존재하긴 하지만 서로 아무런 메시지도 교환하지 않고 묵묵히 자기와 관련된 이벤트들만 발생시키고, 수행한다고 가정하자. Logical clock관점에서는 이런 아무런 상관관계가 없는 이벤트들을 'concurrent'하다고 한다. 이런 이벤트들은 동기화 대상이 아니라 그냥 자기 갈길 가도록 내버려 두면 된다. 아무런 메시지 교환도 없는데 굳이 거기다가 동기화를 맞춰줄 필요는 없는 것이다.

지금까지 다소 길게 Logical clock라는 것의 개념에 대해서 설명했다. 그럼 지금부터는 어떻게 하면 이런 logical clock를 구현 할 수 있는지 살펴보도록 하자.

Lamport timestamp
Lamport 알고리즘은 Lesile Lamport라는 사람에 의해 발명된 간단한 logical clock 알고리즘 이다. 이 알고리즘은 사건의 발생 순서를 수자로 나열할 수 있다는 개념에서 부터 출발하여 아래의 간단한 몇가지 룰을 따른다 :
  1. clock counter는 각 이벤트가 발생하기 전에 증가한다.
  2. 프로세스가 메시지를 보낼 때, 메시지에 clock counter 값을 같이 보낸다.
  3. 메시지가 도착하면 받은 clock counter와 자신이 가지고 있던 clock counter를 비교하여 자신이 가진 것이 크다면 그대로 유지하고, 새로 도착한 것이 더 크다면 새로운 clock counter에 1을 증가시킨 것을 자신의 clock couter로 셋팅한다.
참고적으로 하나의 프로세스에서 동일한 시간에 두개의 이벤트가 발생헤서는 안된다. 그래서 아래와 같은 조치가 필요하다 :
  • 하나의 프로세스에서 두 개의 사건이 발생하는 간격이 tick이 터지는 간격보다 더 빠르다면, 시간 구분을 할 수 없고 인과관계가 엉망이 된다. Tick의 발생 주기는 이벤트의 발생 주기보다 짧아야 한다.
  • 두개의 프로세스에서 동일한 시간에 이벤트를 발생 시켜버린다면 역시 시간 구분을 할 수 없고 인과관계가 엉망이 되어버린다. 그래서 모든 시간의 소수점 이하로 프로세스의 번호를 붙여 다른 프로세스에서 같은 시간을 발생 시킬 수 없도록 한다.

백문이 불여일견이라고 자잘한 설명을 나열하는 것 보다 그림과 함께 하는 예제를 한번 보도록 하자 :

사용자 삽입 이미지

왼쪽 부터 프로세스 0, 1, 2라고 생각하자. 각 프로세스는 서로 다른 머신에서 돌아가고 있고 서로 다른 tick 주기를 가지고 있다. 뭐 거의 비슷하긴 하겠지만 조금 다르다고 생각하자.

프로세스 0번에서 6에 프로세스 1번으로 메시지를 보냈다. 프로세스1번이 메시지를 받은 시간은 16이므로 총 10이라는 시간이 걸렸다. 하지만 시간이 얼마나 걸리건 우리가 관심있어하는 것은 그것이 아니고 그저 메시지를 받는 행동이 보내는 행동보다 더 늦게 일어났다는 것에 주목하자.
위와 비슷하게 프로세스1번은 프로세스2번에게 메시지를 보낸다. 24에 보냈고 40에 도착했다. 여기까지는 아주 정상적인 과정이다. 일찍 보냈고 그 보다 늦게 받았다.

지만 세 번째 메시지에서 문제가 발생하는데 프로세스2번에서 60에 전송된 메시지가 프로세스1번에 56에 도착했다. 이전에 발생한 이벤트의 시간이 이 후에 발생한 이벤트의 시간보다 크다. 논리적으로 뭔가가 잘 못된 것이다.
이 때 동기화(synchronization)과정이 일어난다. 동기화 과정이라고 해서 크게 어려운건 아니다. 도착한 메시지의 clock counter가 자신이 가진 것 보다 더 크다면, 도착한 clock counter에 1을 더한값을 자신의 clock counter를 수정하는 것 뿐이다.

Link :
 - Lamport 알고리즘을 이용한 Total Ordered Multicasting : http://kukuta.tistory.com/143

'진리는어디에' 카테고리의 다른 글

Reference list  (0) 2008.05.16
Generation reference counting  (0) 2008.05.15
Logical clock  (2) 2008.05.02
BTree  (8) 2008.03.26
Python embedding 1 - Overview  (6) 2008.03.13
파이썬으로 utf-8 문서 읽기  (1) 2008.02.22
Posted by kukuta

댓글을 달아 주세요

  1. Favicon of http://blog.naver.com/stallon72 BlogIcon 홍성봉 2008.05.14 17:34  댓글주소  수정/삭제  댓글쓰기

    정리를 잘 해놓으셔서 내용 퍼갑니다. 대단히 감사합니다.