분산 컴퓨팅 3. 시간 동기화 문제와 논리적 시계 (램포트 시계)

들어가기 전

• 이 글은 핵심 이론부터 프로그래밍 실습까지 분산 컴퓨팅을 읽고 정리한 글입니다. 
• 몇몇 참고 글도 있습니다.

---

요약

• 분산 시스템의 참여자들은 시간 동기화가 되어야 하는 경우가 많음.
• 분산 시스템에서 시간 동기화가 이루어지지 않는다면, Data Inconsistency가 발생할 수 있음.
• 분산 시스템의 완전한 시간 동기화는 '절대적 시간' 기준으로는 달성하기 어려움. 
• 분산 시스템의 시간 동기화는 '램포트 시계'를 기준으로 '논리적 시간'으로 동기화 할 수 있음.
• 시간 동기화가 되지 않아 발생하는 Data Inconsistency는 램포트 시계를 포함한 프로토콜로 해결할 수 있지만, 적절한 프로토콜이 수립되어야 의미가 있음. 

 

---

3.1 이중화 된 데이터베이스 문제 

분산 시스템에서 시간 동기화를 알아보기 위해 시나리오를 하나 도입한다. 도입된 시나리오와 환경은 다음과 같다. 

1. 서울 / 부산에는 분산된 DB가 실시간으로 동기화 되고 있음. 
   1. 이벤트를 수행하고, 자신이 받은 이벤트를 다른 지역의 DB로 보내주는 형태로 동기화. 
2. 서울 DB에 1000원 입급 이벤트 발생. 동시에 부산 DB에 1% 이자 지급 이벤트 발생 

만약 이렇게 동작하는 분산 시스템이 있다면, 아래 그림처럼 데이터의 일관성이 무너지는 문제가 발생할 수 있다.

위 그림에서 볼 수 있듯이 각 은행 DB에서 2개의 이벤트를 수행한 후, 서로 다른 계좌 잔고를 보여주는 것을 알 수 있다. 그리고 이것은 수신받은 이벤트의 실행 순서가 각각 달랐기 때문에 발생한 것이다. 이 문제는 분산 시스템에서 각각 수신받은 이벤트를 시간 동기화 없이 수행했기 때문에 발생했다. 따라서 이 문제는 분산 시스템의 시간 동기화를 통해서 해결할 수 있다. 

 

---

3.2 시간 동기화 기법 

시간 동기화가 되지 않은 채로 이벤트를 수행했기 때문에 앞선 문제가 발생했다. 그렇다면 분산 시스템에서는 어떻게 시간 동기화를 해볼 수 있을까? 

 

크리스티안 알고리즘 (Cristian's Algorithm)

크리스티안 알고리즘은 시간 쿼리에 응답하는 제 3의 서버를 두고, 분산 시스템의 참여자가 서버에 시간 쿼리를 보낸 후 시간을 동기화하는 방법이다. 이 방법은 일반 서버 - 시간 서버의 Latency가 낮을 경우에는 꽤 잘 동작하는 편이지만, 분산 시스템에서는 적합하지 않은 방법이기도 하다. 

Tclient = Tserver + (T1 - T0) / 2

여기서 (T1 - T0)는 RTT(Rounte Trip Time)이다. 현재 클라이언트의 시간은 타임 서버 시간에 RTT의 편도를 더한 값이라는 것이다. 일견 타당해 보일 수 있는 크리스티안 알고리즘이지만 사용하기에는 몇 가지 문제가 존재한다.

1. Request / Response의 Transmit 시간이 각각 다를 수 있음. 이것은 (T1 - T0)/2라는 전제를 깨뜨림.
2. 시간 서버는 1대만 존재함. SPOF가 될 수 있음. (시간 서버가 여러대인 경우, 시간 서버 클러스터의 동기화가 필요함)

특히 분산 시스템에서는 Network 문제가 많이 발생할 수 있는데, 이 때문에 Request, Response가 수신될 때 각각 서로 다른 네트워크 환경일 수 있다. 예를 들어 Request가 99초만에 전달되었는데, 응답은 1초만에 전달된 경우를 가정해보자. 이 때 (T1-T0)/2는 50초가 되는데, Tclient = Tserver + 50초는 틀린 가정이 된다. 왜냐하면 이 경우 Tserver + 1일 때만 정확하기 때문이다. 

이처럼 크리스티안 알고리즘을 통한 시간 동기화에는 문제점이 존재한다. 

 

버클리 알고리즘(Berkeley Algorithm)

버클리 알고리즘은 분산 장치들이 각각 시계를 가지고 있고, 분산 클러스터 내에서 시간을 동기화 하는 알고리즘이다.

1. 분산 클러스터 내에서 시간을 동기화는 Master가 존재한다.
2. Master는 분산 클러스터 참여자(Master 포함)의 시간을 취합해서 평균 시간을 계산한다. 
3. 평균 시간을 계산한 후, 각 참여자가 평균 시간에 맞추도록 명령한다.

위의 이미지에서 Master는 평균 시간을 계산하고, 결과는 3:05분이 된다. 그리고 Master는 분산 클러스터의 참여자들에게 각각 시간을 3:05분이 되도록 맞추라고 메세지를 보낸다.

• 참여자 A 3:10 : -5분
• 참여자 B 2:50 : + 15분
• 참여자 C 3:20 : - 15분

각 참여자에게 시간을 반영하라는 메세지를 보내는데, 이 메세지 자체도 네트워크 환경을 타고 전파된다. 이 말은 네트워크가 전송되는 시간에 영향을 받게 된다. RTT가 0인 경우, 위 알고리즘은 정확할 수 있다. 그렇지만 각 참여자에게 메세지 전달되는 시간이 다르다면(다를 가능성이 더 높음), Transmitted Time의 차이로 인해 시간 동기화는 Inconsistency가 발생한다. 따라서 버클리 알고리즘도 분산 시스템의 시간 동기화에는 적합하지 않다. 

 

---

3.3 논리적 시계 

위에서 시도했던 내용은 각 분산 참여자의 정확한 시간을 계산하기 위한 알고리즘이었다. 그런데 그 작업은 쉽지 않다는 것을 알 수 있었다. 한 가지 놓치고 있던 부분은 분산 시스템의 시간 동기화는 '정확한 시간'이 필요한 것이 아니라 '논리적 시간 순서'가 중요하다는 점이다. 

1% 이자 지급 / 1,000원 입금이라는 두 이벤트가 발생했을 때, 이벤트 간의 선후 관계를 '논리적 시간'에 따라 정의할 수 있다면, 위에서 발생했던 문제를 해결할 수 있다. '논리적 시간'의 구현체인 '램포트 시계'를 공부해보자. 

 

램포트 시계 

램포트 시계는 분산 참여자들 사이에서 논리적 시간을 동기화 해주는 시계다. 즉, 절대적인 시간이 어떤지는 관심 대상이 아니다. 

램포트 시계는 다음과 같이 이해할 수 있다.

1. 각 분산 참여자는 램포트 시계를 가진다. 
2. 각 분산 참여자는 ID를 가진다. 이 때, ID는 모든 분산 시스템에서 유일해야함.
3. 각 램포트 시계는 0으로 초기화 된다. 
4. 이벤트가 발생할 때 마다 램포트 시계는 1씩 증가한다.
5. 분산 참여자가 다른 분산 참여자에게 메세지를 전송할 때, 자신의 램포트 시계를 넣어서 보내준다. 
6. 분산 참여자가 메세지를 받았을 때, 자신의 램포트 시계를 다음과 같이 업데이트 한다.
   1. C(메세지) < C(자신) → C(자신) + 1
   2. C(메세지) = C(자신)
      1. ID(메세지) < ID(자신) → 무시함
      2. ID(메세지) = ID(자신) → 이런 경우는 없음
      3. ID(메세지) > ID(자신) → C(메세지) + 1로 업데이트 함. 
   3. C(메세지) > C(자신) → C(메세지) + 1

램포트 시계는 이런 식으로 동작한다. 

def update(c_msg, c_self):
	return max(c_msg, c_self) + 1
    
next_count = update(c_msg, c_self)

의사 코드로 작성해보면 다음과 같다. 

위 그림을 예시로 들어볼 수 있다.

1. P1, P2, P3의 램포트 시계는 모두 0으로 초기화.
2. A 이벤트 발생 → P1 램포트 시계 = 1
3. D 이벤트 발생 → P3 램포트 시계 = 1
4. B 이벤트 발생 → P1 램포트 시계 = 2
5. C 이벤트 발생 → P2 램포트 시계 = 3

여기서 시간 순서는 다음과 같이 정해진다. 

D > A > B > C

P1, P2는 서로 통긴했기 때문에 램포트 시간이 동기화 되어있고, 명확하게 A > B > C 램포트 시간대로 발생했다는 것을 알 수 있다. 

그러나 P3는 통신했던 적이 없기 때문에 램포트 시간이 동기화 되었다고 볼 수는 없고, A / D의 선후 관계만을 정의할 수 있다. 같은 램포트 시간 1을 가지고 있을 때는, 고유한 ID의 크기로 비교를 한다고 했다. 이 때, ID가 큰 쪽이 먼저라고 정의한다면 D > A의 순서가 정해진다.

따라서 D > A > B > C 순서가 정해진다. 여기서 알 수 있는 점은 분산 참여자 간의 정확한 시간 동기화가 없더라도, 램포트 시계를 통해 분산 참여자에게서 각각 발생한 이벤트를 순서대로 동기화 할 수 있다는 점이다. 

 

 

---

3.4 램포트 시계를 이용한 비일관성 문제 해결 

위 문제를 램포트 시계를 이용해서 해결하고자 한다. 당연한 이야기지만 램포트 시계를 쓴다고 바로 해결되는 것은 아니고, 몇 가지 규칙을 고려해야지 이벤트 발생 순서대로 작업을 진행할 수 있다. 

 

Case1

1. DB를 업데이트 해야 할 작업이 생기면, 자신과 다른 지점에 통지
2. 업데이트 할 작업을 다른 지점에서 수신하면
   1. 해당 작업을 일단 우선순위 큐에 저장 (우선순위는 램포트 시간만 고려)
   2. 해당 작업이 우선순위 큐의 가장 앞에 있는 경우에만 회신한다. 
3. 업데이트 할 일에 대한 수신 확인 메세지를 받으면, 해당 작업이 다른 지점에서도 확인되었음을 표시한다.
4. 확인된 작업은 큐에서 가장 첫 번째 자리에서 제거하고, 해당 작업을 수행한다. 

위 제한 사항에서는 이벤트가 항상 순서대로 처리된다.

설명을 보면 다음과 같다.

1. 이벤트 발생 시점의 램포트 시간을 LT로 표현했다. 
2. 우선순위 큐는 램포트 시간을 기준으로 배열한다.
3. 램포트 시간이 빠른 입금 요청이 먼저 우선순위 큐의 앞으로 가게 되어 ACK되고 먼저 실행된다. 

이 Case가 시사하는 바는 램포트 시간을 추가하면, 분산 시스템의 참여자들의 시간을 논리적으로 동기화해서 발생 순서대로 처리할 수 있다는 것이다. 그리고 그 결과 각 분산 참여자는 Consistency를 가지게 된다. 

 

 

Case2

1. DB를 업데이트 해야 할 작업이 생기면, 자신과 다른 지점에 통지
2. 업데이트 할 작업을 다른 지점에서 수신하면
   1. 해당 작업을 일단 우선순위 큐에 저장 (우선순위는 램포트 시간만 고려)
   2. 바로 수신 메세지에 대해 ACK.
3. 업데이트 할 일에 대한 수신 확인 메세지를 받으면, 해당 작업이 다른 지점에서도 확인되었음을 표시한다.
4. 확인된 작업은 큐에서 가장 첫 번째 자리에서 제거하고, 해당 작업을 수행한다. 

이전 케이스 에서는 우선순위 큐의 Head에 작업이 있을 때만 ACK를 전달했다. 그러나 이번에는 큐에 작업을 저장하고 바로 ACK 할 수 있다고 가정해보자. 이 때는 램포트 시계를 쓰더라도 분산 참여자끼리 서로 다른 순서로 이벤트를 실행한다. 결과적으로 Data Inconsistency가 발생한다.

위 그림에서 볼 수 있듯이 서울은 입금 → 이자지급 순으로 이벤트가 실행된다. 반면 부산은 이자지급 → 입금 순으로 이벤트가 실행된다. 

여기서 시사하는 바는 램포트 시계를 사용하더라도 적절한 프로토콜을 정의하지 않는 경우, 이벤트들의 논리적 선후 관계는 정의되지만 실행 순서는 다른 형태로 될 수 있음을 의미한다. 

 

---

참고

• https://m.blog.naver.com/stallon72/10030817453