[CS] 동기화(Syncronization)와 Clock

 

분산 시스템에서의 동기화(Synchronization)의 필요성

1. 일관성 유지: 여러 대의 컴퓨터가 네트워크를 통해 상호 작용하는 분산 시스템에서는 데이터의 일관성을 유지하는 것이 중요하다.
2. 트랜잭션 처리: 분산 데이터베이스나 분산 시스템에서 트랜잭션을 일관성 있게 처리하려면 서로 다른 노드 간에 동기화된 타임스탬프나 논리적인 순서가 필요하다.
3. 분산 시스템 성능 향상: 동기화를 통해 병렬처리를 효과적으로 수행함으로써 성능을 향상시킬 수 있다.
4. 상태 공유: 여러 컴퓨터가 상태를 공유하고 특정 이벤트에 대한 조율을 필요로 할 때 동기화를 통해 상태 일관성을 유지하게 한다. RPC나 Apache Kafka를 비롯한 Message Broker가 해당 역할을 할 수 있다. 
   • Message Broker은 메시지 기반의 비동기 통신을 제공하므로, 실시간성이나 데이터의 순서가 중요하지 않은 경우에 적합하다.

 

 

동기화와 Clock의 연관성

데이터의 순서가 중요한 경우 분산 시스템에서의 동기화와 Clock 간의 연관성은 매우 중요하다.

분산 시스템은 여러 대의 컴퓨터가 네트워크를 통해 상호 작용하는 환경이기 때문에 각 시스템이 동일한 시간 기준을 가져야 한다.

 

 

 

 

Clock

중앙 집중식 시스템에서의 동기화 : 모든 프로세스는 같은 Local Clock을 공유

 

분산 시스템에서의 동기화의 문제점 : No Same Physical Clock

• 분산 시스템은 여러 프로세스로 구성됨
• 각 프로세스는 상태를 변경하기 위한 명령이나, 통신 작업(이벤트 발생)을 수행함
• 각 프로세스에는 Local Clock이 있으며, Event에는 Timestamp가 할당되어 순서가 지정됨
• Process Clock은 분산 시스템에서 동기화되지 않음(다를 수 있음)
• Glocal Clock이 없기 때문에 Clock Synchronization이 어려움

 

 

 

---

 

Physical Clock

• 물리적 시간에 대한 정확한 값을 얻어내거나, 분산 시스템 전반에 걸쳐 물리적 시간 개념을 동기화시키는 측면으로 사용
• Clock Drift = Clock의 오차, 대부분의 Clock은 정확하지 않음.
• UTC : 시간 서버로 사용되는 협정 세계시
  • 동기화된 시계를 유지하려면, UTC에서 현재 시간에 엑세스하기 위한 Physical Time Server가 필요

 

 

 

Critian’s Algorithm

1. Centralized 방식. Physical Clock Sync의 방식.
   • UTC Receiver가 있을 때 사용(Time server)
   • Time server에서 현재 시간을 가져옴
2. 요청+응답시간의 추정치로 시간을 보정
   • Time server의 응답을 받을 때의 간극을 보정
   • Turn-around time의 추정치가 변동적(분산이 높음)
3. SPoF 및 Bottleneck의 문제점

 

 

Berkeley Algorithm

 

Centralized 방식. Physical Clock Sync의 방식.

Time Daemon이 Master 다른 머신은 Slave, Master은 Slave의 시간을 주기적으로 Polling

• Physical Clock Sync 방식
• 마스터가 슬레이브에게 시간을 물어봄(폴링), 응답이 오면 조정 방법 알려줌
• Communication Delay : 크리스티안처럼 보정

문제점

1. Centralized 알고리즘 문제 → 마스터가 죽으면 새 마스터 선택(정확성 X)
2. 예측할 수 없는 Internet Delay
3. Relativistic issues : 두 이벤트 T(a)와 T(b)가 시간상으로 매우 가까운 경우에도, 두 이벤트의 발생 순서가 관찰자의 상대적인 위치와 속도에 따라 달라질 수 있다는 문제

 

 

 

 

---

Logical Clock

 

Physical Clock

• 분산 시스템에서 이벤트의 순서를 정의하기 어려움 → 발생 순서가 상대적으로 달라짐

Logical Clock

• Happend-before Relationship
  • Lamport가 발표. 사전 관계로 정의
  • Define a logical relation *Happens-Before (*→) among events:
    • On the same process: a → b, if time(a) < time(b)
    • If p1 sends m to p2: send(m) → receive(m)
    • If a → b and b → c then a → c (Transitivity)
  • 이벤트 x와 y가 메세지를 교환하지 않는 서로 다른 프로세스에서 발생하는 경우 → Concurrent(동시)
    • 전후 관계를 따지지 않음!
• Clock synchronization을 상대적으로 함 → 절대적인 시간은 중요하지 않음
• 프로세스는 이벤트가 발생한 시간보다 이벤트가 발생하는 순서에 초점을 맞춤

 

 

 

Lamport Algorithm

 

 

다음과 같이 세 개의 프로세스는 각각 자체 Clock을 가짐. Clock은 다른 속도로 작동하고 있다.

Lamport Algorithm은 각각의 Clock을 Happend-Before Relation을 통해 Corrects시킬 수 있다.

 

 

 

 

between a and b: a → b

between b and f : b → f

between e and k: e // k

between c and h: c // h

between k and h: k → h

(→ : Happend-before, // : Concurrent)

 

 

 

장점 : 프로세스는 이벤트가 발생한 시간보다 이벤트가 발생하는 순서에 초점을 맞추어 이벤트의 순서를 정의함

 

문제점: Reverse is not True, 타임스탬프(C)를 비교하는 것 만으로는 이벤트의 우선순위를 비교할 수 없음

• a → b, b → c, d →f But b // e
• C(b) > C(e) but b // e

 

 

 

Vector Logical Clock

 

 

Timestamp를 Vector로 표현하는 방법이다.

 

이벤트 A와 B의 Timestamp 비교 시 B Vector의 모든 Element가 A보다 크거나 같으면 Happend-Before 관계 성립한다.

Vector Clock은 Logical Clock에 비해서 아래와 같은 장단점을 가진다.

• 장점 : 타임스탬프로 이벤트의 우선순위를 비교할 수 있음
• 단점 : Scalable하지 못함 → Storage와 Message Overhead 발생

 

 

---

 

Clock 동기화 알고리즘 비교

 

Cristian Alg	• Time Server에서 Request & Response로 시간을 가져옴 + 이의 평균으로 시간을 보정함		• 예측할 수 없는 Network Latency • 보정 시간의 분산이 높음 • SPoF, Bottleneck
Berkely Alg	• Time Daemon(마스터)와 Slave로 노드가 구성됨. 마스터는 Slave의 시간을 주기적으로 동기화		• Master가 Crash되면 보장할 수 없는 새로운 Master 선출. • Internet Delay • 가까운 이벤트들의 발생 순서가 관측자의 위치(거리, 속도..)에 따라 다르게 측정될 수 있음
Lamport Alg	• Happens-before / Concurrent 관계를 통해 Event의 발생 순서를 상대적 관계에 의해서 정의함	• 정확한 이벤트의 시간보다, 관계로 파악 → 이벤트 우선순위를 정의	• Timestamp를 통해서는 이벤트의 우선순서를 파악할 수 없음
Vector clock	• 타임스탬프를 Vector(a,b,c)로 표현하여 이벤트의 우선순위를 파악할 수 있음	• Timestamp 파악을 통해서 이벤트의 우선순위 파악 가능	• No-Scalabe : 벡터의 내용이 커지면 Message overhead 발생

 

 

 

 

 

 

---

Content / Image Reference 

 

Tannenbaum and Van Steen :: Distributed Systems: Principles and Paradigms (PDF)