분산시스템(Distributed System) - 2(Logical Clocks)

logical time 이란 위의 설명과 같이 이벤트가 일어난 순서대로 부여된 시간이다. 여러 노드에서 발생하는 이벤트들의 순서를 보장하기 위해 사용된다.

왜 필요할까?

각 노드들은 각자의 시간을 가질 수 있다. 하지만 이 시간들은 모두 오차를 가질 것이다. 중앙에서 시간을 받아온다 하더라고 물리적인 거리와 네트워크의 오류 등 여러 변수들이 존재하고 하나의 시스템 안에 있는 노드들이 오차를 가지지 않는 시간을 가진다는 것은 불가능하다.

여기서 보면 m1은 m2보다 먼저 전달이 되어야한다. 하지만 userB에서 m1을 받고 m2를 보내는 시간을 t2라 하자 그리고 최초로 m1이 userA에서 발생한 시간을 t1이라 하자. 그림이나 이미 메시지의 순서를 아는 우리가 보기에는 t1이 t2보다 빨라야 한다. 하지만 userB가 사용하는 노드의 시간이 userA가 사용하는 노드의 시간보다 느리고 t2의 시간이 t1보다 더 빠른 즉, 더 작은 timestamp일수 있다. 이런 경우 userC는 아무런 의심 없이 m2가 먼저 발생한 것이라 생각하고 이해할 수 없는 대화 내용을 받게 된다. 이런 경우 userC의 노드에서 버퍼를 이용하여 메시지를 담아두었다가 순서를 재정렬해서 보여준다 해도 이미 timestamp로 보면 m2의 timestamp가 더 작기 때문에 userC는 정확한 순서를 알 수가 없다.

 

그래서 분산시스템 안에서 이벤트의 순서를 기반으로 만들어진 logical time(logical clock)이라는 개념을 이용한다.

그중 두 가지

1. Lamport clocks
2. Vector clocks

 

이 두 가지에 대하여 공부를 하였다.

 

Lamport clock이란?

 

모든 노드가 하나의 양의 정수를 모든 노드가 가지고 카운팅을 하는 방식이다.

 

각 노드가 t = 0이라는 값을 가지며 초기화된다.

이벤트가 발생하면 t = t + 1

다른 노드로 요청을 보낼 때 t = t + 1을 해서 send(t, m)을 보낸다.

해당 receiving(t1, m) 리퀘스트를 받은 노드는 t = max(t, t1) + 1 

위의 알고리즘을 이용하여 ordering of messages의 경우를 생각해보자.

userA가 메시지를 보낼 때

t = 0

t = t + 1, send(1, m1) 

 

1. userB가 메시지를 받을 때

• userB의 t = 0이고, 전송된 메시지의 t1 = 1이다.
• receiving(t1, m1) t = max(0, 1) + 1 -> B의 t = 2

 

1. userB가 메시지를 보낸다. 

• t = 2 , t = t + 1, send(3, m2)

 

1. userC 가 메세지를 받을 때

• userC의 t = 0, userB에서 보낸 메시지가 먼저 도착한다.
• receiving(3, m2) 그리고 receiving(1, m1) 나중에 userA의 메세지가 도착한다.
• 이 둘이 가진 시간은 사건의 발생순서를 보장하기 때문에 정상적인 순서로 메시지를 정렬할 수 있다. 
• userC의 t = 4가 된다.

 

이렇게 순서를 보장할 수 있게 된다.

각 노드가 가진 t의 값은 같은 값을 가질 수가 없기 때문에 각 노드에서 발생한 이벤트들은 순서를 보장할 수 있다.

하지만 Lamport Clock은 happens before이 명확한 이벤트에 대해서만 설명할 수 있다. 위의 예제는 m1 이 userB에 전송되면 m2가 나오는 거라 적절한 예는 아니었지만 그와 무관하게 userC에서 메시지가 나왔다면 m1, m2, m3의 선후 관계는 lamport clock으로 따져 볼 수 있지만 이 메시지들이 어떤 관계를

가지는 지는 알 수가 없다. 즉 선후관계는 따질 수 있지만 이벤트의 causality(인과관계)는 알 수가 없다. 이런 경우 Vector clock을 이용할 수 있다.

 

두 번째인 Vector Clock이란?

 

Vector clock도 Lamport Clock과 비슷하다. 가장 큰 차이는 scalar와 vector의 차이다. Lamport clock이 하나의 양의 정수로 순서를 정했다면 Vector clock은 각 노드마다의 시간을 모든 노드가 가지고 있다.

 

노드의 수만큼 t를 초기화를 해준다

T = [0,0,0,0,0,…. 0]

 

i 번째의 노드에 이벤트가 생긴 경우

T[i] = T[i] + 1

 

i 번째의 노드에서 메시지 m을 보내는 경우

T[i] = T[i] + 1; send (T, m)

 

j 번째의 노드에서 메시지 m을 받는 경우

receiving(Ti, m); Tj = max(Tj[j], Ti[i]); T[i] = T[i] + 1(i노드의 메시지가 j노드에 전달되었기 때문에 이벤트 발생으로 T[i]시간 증가

 

벡터의 절댓값을 구하여 비교하면 순서를 알 수가 있다. 이로 인해 선후 관계를 판단할 수 있고, 각 벡터의 값을 이용해 각 이벤트의 causality를 파악할 수 있다.

두 가지의 logical clock에 대하여 정리를 해보았다. 여러 노드가 존재하는 분산시스템에서 메시지를 전달할 때 order와 causality를 보장해야 하는 경우 상황에 따라서 이두가지 시간을 이용할 수 있다.

포스트의 모든 이미지는

https://www.youtube.com/channel/UClB4KPy5LkJj1t3SgYVtMOQ/videos 와 Introduction to Reliable and Secure Distributed Second Edition에 있다.