[2주차, 3장] 시간 동기화 문제와 논리적 시계

[월간-CS][24년 5월] 핵심 이론부터 프로그래밍 실습까지, 분산 컴퓨팅

May 18, 2024

Contents

“학습 목표” 분석 “분산된 데이터베이스 병행 갱신” 소개 “시간 동기화 기법” 소개 크리스티안 알고리즘(Cristian’s Algorithm)버클리 알고리즘(Berkeley Algorithm)네트워크 시간 프로토콜(NTP, Network Time Protocol)“논리적 시계” 소개 램포트 시계(Lamport Clock)레슬리 램포트 시계(Leslie Lamport Clock)“램포트 시계를 활용한 비일관성 문제 해결” 소개 데이터베이스 복제 알고리즘(Database Replication Algorithm)분산 데이터베이스 병행 갱신 문제 해결 추가 참고 자료

이 문서는 [월간-CS][24년 5월] 핵심 이론부터 프로그래밍 실습까지, 분산컴퓨팅을 위해서 작성된 문서입니다. 이 문서에는 작성자(unchaptered)의 어떤 저작권이 포함되어 있지 않으며, 오직 도서 “분산 컴퓨팅”의 저작권만 포함될 수 있습니다.

“학습 목표” 분석

도서 “분산 컴퓨팅 3장 시간 동기화 문제와 논리적 시계”에서는 분산된 장치들 간의 시간을 동기화 해야 하는 이유와 방법들에 대해서 말하고 있습니다.

분산된 장치들(프로그램)들의 시간을 어떻게 동기화할 것인가?
어떻게 분산된 장치들이 서로 일관된 정보를 가지게 할 것인가?

“분산된 데이터베이스 병행 갱신” 소개

Alice는 K은행에 계좌를 가지고 있다.
K은행은 각각 서울과 부산에 다중 데이터베이스를 운영 중이다.
입금은 K은행-서울에서 받았지만 이자지급은 K은행-부산에서 이루어질 것이다. 이 경우 Alice가 이자 지급 시점에 K은행-서울에 1,000원을 입금하면 어떤 일이 일어날까?

이해를 돕기 위해 아래 예시를 포함하였다.

2024-05-18 15:00:00 서울 Alice 10,000원 보유 중
2024-05-18 15:00:00 부산 Alice 10,000원 보유 중
2024-05-18 15:01:00 부산 Alice 1% 이자 지급 결정
2024-05-18 15:01:01 서울 Alice 1,000원 입금

위 시나리오 대로면 11,100원을 가지게 될 것 같지만, 실제로는 서울과 부산의 시계의 오차로 인해 알 수 없다.

기댓값 : 10,000 + 10,000 × 0.01 + 1,000
현실 : 알 수 없음

만약 서울의 시간이 2초 느리게 흘러가고 있다면, 아래와 같을 것이다.

기댓값 : 10,000 + 10,000 × 0.01 + 1,000
조정값 : (10,000 + 1,000 ) × 1.01

“시간 동기화 기법” 소개

기준 시간을 알려주는 서버의 유무에 따라서 2가지 알고리즘이 존재한다.

존재할 경우 : 크리스티안 알고리즘(Cristian’s Algorithm)
존재하지 않을 경우 : 버클리 알고리즘(Berkeley Algorithm)

또한 별도의 프로토콜을 사용하는 방법으로 다음이 존재한다.

네트워크 시간 프로토콜(NTP, Network Time Protocol)

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

크리스티안 알고리즘 시간을 제어하는 1개의 중앙 서버가 분산된 장치들의 시간을 동기화하는 알고리즘입니다.

따라서 아래와 같은 가정을 가지고 있습니다.

시간 동기화가 필요한 장치를 클라이언트라고 한다.
시간 동기화를 해줄 중앙 장치를 서버라고 한다.
클라이언트가 서버로 요청을 보냈을 때, 두 시간의 차이를 δreq(델타 req)라고 부른다.
서버가 클라이언트로 응답을 보냈을 때, 두 시간의 차이를 δresp(델타 resp)라고 부른다.
(핵심) δreq == δresp로 가정한다.
(핵심) T4는 서버 입장에서 알 수 없으며, 가정 5번에 의해서 아래의 값으로 가정한다.
```
T4 = T3 + δreq|resp / 2
```

따라서 아래와 같은 한계를 가지고 있습니다.

가정 5번, δreq == δresp은 물리적으로 성립하기 어렵다.
가정 2번, 서버가 마비되면 전체 시스템이 마비되어 SPoF로 작동한다.

버클리 알고리즘(Berkeley Algorithm)

버클리 알고리즘은 별도 서버 없이 분산된 장치들이 가진 내부 시계만으로 동기화 문제를 해결합니다. 단 이 과정에서 중심이 되어줄 마스터 장치를 선택하고 이를 통해서 오차를 보정합니다.

따라서 아래와 같은 가정을 가지고 있습니다.

분산된 장치들은 서로 정확도가 비슷한 시계를 가진다.
분산된 장치 중에 1대는 마스터 장치로서 작동한다.
마스터 장치가 다른 장치로 요청을 보내서 각자의 장치에 도착한 시간들의 평균 시간을 연산한다.
평균 시간에 맞추기 위해서 모든 분산 장치에 적용할 조정값을 정한다.

따라서 아래와 같은 한계를 가지고 있습니다.

어떤 장치를 마스터로 선택해야 하는가?
메세지를 주고 받는 과정에서의 네트워크 시간을 알 수 없다.

도서에는 언급되어 있지 않지만, 마스터가 장애로 마비되었을 떄의 자동 복구 및 일관성 유지에 대한 복잡한 문제가 추가로 남는 것 같습니.

네트워크 시간 프로토콜(NTP, Network Time Protocol)

네트워크 시간 프로토콜은 여러 계층(Stratum)으로 구성되어 있어서 시간 동기화 문제를 크리스티안 알고리즘을 통해서 해결하고 있다.

계층	정의	예시
Stratum 0	가장 정확한 시간, 중앙 서버 역할	라디오 방송국, 인공위성
Stratum 1	기준 시간을 물어보는 클라이언트 역할
Stratum 2	기준 시간을 물어보는 클라이언트 역할

당연히 크리스티안 알고리즘이 가진 δreq == δresp 문제와 SPoF 문제를 모두 겪을 수 있다. 도서에서는 “시간 동기화는 너무 어렵고 이 부분에 너무 집착하지 않는 것이 분산 컴퓨팅의 해답이 될 수 있다”라고 안내하고 있다.

“논리적 시계” 소개

앞서 배운 크리스티안 알고리즘, 버클리 알고리즘, 네트워크 시간 프로토콜 등으로도 시간을 나노초(ns) 단위까지 정확하게 보장할 수 없다. 따라서 시간에 너무 집착하는 것은 좋지 않을 수도 있다.

중요한 것은 작업의 순서이므로 이 부분에 집중해서 아래의 내용들을 살펴보면 좋다.

램포트 시계(Lamport Clock)
레슬리 램포트 시계(Leslie Lamport Clock)

램포트 시계(Lamport Clock)

램포트 시계는 이벤트 간의 인과 관계를 정확하게 기록하기 위해서 사용된다.

따라서 다음과 같은 특징이 있다.

인과 관계를 정확하게 파악할 수 있다.
두 이벤트의 램포트 시간값(Cn)을 비교하여 순서를 판단할 수 있다.
동일한 램포트 시간값(Cn)을 가진 경우에는 램포트 시계 순서를 기준으로 판별한다.

이를 조금 더 시나리오 형태로 살펴보면 다음과 같다.

램포트 시계 P1, P2, P3가 있다.
모든 시계의 렘포트 시간값은 0에서 시작하며 즉 C1, C2, C3는 모두 0에서 시작한다.
특정한 렘포트 시계 n에 이벤트가 기록이 된다면 Cn은 1 증가한다. (Cn = Cn + 1)
1. 단, 서로 다른 램포트 시계라면 C현재 = C직전 + 1으로 변화한다.

조금 더 명확한 시나리오를 가정하고 이를 분석해보자

이벤트 발생 내역은 다음과 같다.
- P1에는 a, b 이벤트가 발생했다.
- P2에는 c 이벤트가 발생했다.
- P3에는 d 이벤트가 발생했다.
이벤트 a, b, c는 연속적으로 발생한 이벤트이다.

최초 시점에 C0, C1, C2는 모두 0이기 때문에 모두 같기 때문에, 가장 작은 렘포트 시계인 P1의 a번 이벤트가 최초에 발생한다.

[로그] P1.a
[값 기록]
P1, C1 = 1
P2, C2 = 0
P3, C3 = 0

a 이벤트 다음에 b 이벤트가 실행되었기 때문에 P1, C1이 다시 한 번 증가하여 2가 된다.

[로그] P1.a → P1.b
[값기록]
P1, C1 = 2
P2, C2 = 0
P3, C3 = 0

이후 P2의 c 이벤트와 P3의 d 이벤트는 모두 렘포트 시간값이 0으로 동일하기 때문에 더 작은 시계 번호인 P2가 먼저 실행되었을 것이다. 따라서 C2 = C1 + 1 하여 총 3으로 변화한다.

[로그] P1.a → P1.b → P2.c
[값기록]
P1, C1 = 2
P2, C2 = 3
P3, C3 = 0

마지막으로 P3의 d 이벤트의 경우 a, b, c와 독립적으로 일어난 이벤트이다.

따라서 다른 이벤트들과의 연속성을 비교할 필요가 있다.

a 이벤트와 d 이벤트
- C1, C3 = 0으로 동일하기 때문에 가장 작은 램포트 시계인 a가 먼저 시작되었다.
b 이벤트와 d 이벤트
- C1 = 1, C3 = 0으로 P1가 크기 때문에 d가 먼저 시작되었다.

이를 통해서 조정된 로그는 다음과 같습니다.

[로그] P1.a → P3.d → P1.b → P2.c
[값기록]
P1, C1 = 3
P2, C2 = 4
P3, C3 = 2

레슬리 램포트 시계(Leslie Lamport Clock)

일반적인 멀티 스레드 환경에서는 다수의 스레드가 동일한 리소스에 동시에 엑세스하는 경우가 일반적입니다.

이런 경우에는 데이터 손상(Data Corruption)이 발생할 수 있습니다. 따라서 뮤텍스(Mutex, Mutual Algorihtm)를 통해서 다수의 스레드가 동일한 리소스에 동시에 엑세스하는 경우를 방지하도록 하는 상호 배제 전략을 선택하였습니다.

Java의 AtomicIntegerArray Class는 여러 스레드가 동시에 배열 요소를 수정하더라도 배열 요소의 값을 정확하게 유지할 수 있도록 설계되어 있습니다.

import java.utils.concurrent.atomic.AtomicIntegerArray;

public class Example {

    public static void main(String[] args) {
        AtomicIntegerArray atomicArray = new AtomicIntegerArray(5);

        atomicArray.set(0, 10);

        int oldValue = atomicArray.getAndIncrement(0);


        System.out.println("Out Value : " + oldValue);
        System.out.println("New Value : " + atomicArray.get(0));
    }

}

“램포트 시계를 활용한 비일관성 문제 해결” 소개

앞서 “분산된 데이터베이스 병행 갱신” 소개에서 우리는 분산 데이터베이스에서 작업의 순서를 결정해야 했습니다. 우리는 “논리적 시계” 소개 - 렘포트 시계(Lamport Clock)을 활용하여 K은행-서울이 K은행-부산에게 수행해야 할 작업을 담은 메세지와 램포트 시간을 같이 전달한다. 그리고 이 메세지는 각 지점이 자체적으로 가지고 있는 큐(Queue)에 기록되며, 이런 메세지는 렘포트 시간(Lamport Time)을 기준으로 정렬된다.

조금 더 세부적인 예시를 보면 다음과 같습니다.

데이터베이스 복제 알고리즘
분산 데이터베이스 병행 갱신 문제 해결

데이터베이스 복제 알고리즘(Database Replication Algorithm)

위에서 언급한 성질을 통해서 데이터베이스 복제 알고리즘을 설계할 수 있다.

데이터베이스 업데이트 사항은 자신과 다른 지점에 메세지로 통지된다.
업데이트 사항을 다른 지점에서 수신하면
1. 해당 작업을 일단 큐(Queue)에 저장한다.
2. 자신과 다른 지점에 대한 수신 확인 메세지를 전송한다.
  단, 해당 업데이트 작업이 큐의 가장 앞에 있을 경우에만 회신한다.
업데이트할 일에 대한 수신 확인 메세지를 받으면 , 해당 작업이 다른 지점에서도 확인되었음을 표시한다.
확인된 작업은 큐에서 가장 첫 번째 자리에서 제거하고, 해당 작업을 수행한다.

전체적으로 2단계 커밋 프로토콜(Two Phase Commit Protocol)에서 배운 선제적 메세지 기록과 비슷한 논리가 어느 정도 적용되어 있는 것 같습니다.

중요한 부분은 메세지를 보내기 전에 기록하고 합의가 완료되면 작업이 진행된다는 점입니다.