들어가며
실세계에서 완벽한 동기화란 없다. 아무리 짧은 시간을 주기로 동기화를 시도해도 결국 네트워크 지연이나 기타등등의 여러가지 이유로 아주 근소한 차이라도 오차는 있기 마련이다.
해서 나온것이 '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 알고리즘 이다. 이 알고리즘은 사건의 발생 순서를 수자로 나열할 수 있다는 개념에서 부터 출발하여 아래의 간단한 몇가지 룰을 따른다 :
- clock counter는 각 이벤트가 발생하기 전에 증가한다.
- 프로세스가 메시지를 보낼 때, 메시지에 clock counter 값을 같이 보낸다.
- 메시지가 도착하면 받은 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를 수정하는 것 뿐이다.
