버클리 알고리즘이란?
버클리 알고리즘(Berkeley's Algorithm)은 분산 시스템(distributed system)에서 여러 노드의 시계를 동기화하기 위해 사용되는 대표적인 알고리즘입니다. 이 알고리즘은 분산 네트워크를 구성하는 일부 또는 전체 시스템이 다음과 같은 문제를 가지고 있을 때 특히 유용하게 활용됩니다.
- 머신에 정확한 시간 소스(time source)가 없는 경우
- 네트워크나 머신에 UTC 서버가 존재하지 않는 경우
분산 시스템은 물리적으로 떨어져 있지만 네트워크를 통해 서로 연결된 여러 개의 노드(node)로 구성됩니다. 각 노드는 독립적인 하드웨어 클록을 가지고 있으며, 클록마다 진행 속도가 조금씩 다르기 때문에 시간이 지날수록 노드 간 시간 오차가 점점 벌어지게 됩니다. 버클리 알고리즘은 바로 이러한 오차를 줄이기 위한 해결책입니다.
버클리 알고리즘의 동작 원리
이 알고리즘에서는 시스템이 노드 풀(pool) 중 하나를 마스터(master)/리더(leader) 노드로 선출하고, 나머지 노드들은 팔로워(follower) 역할을 수행합니다. 전체 알고리즘의 흐름은 다음과 같습니다.
- 마스터 노드 선출: 선거(election) 과정을 통해 서버 내 노드 중 하나가 마스터 노드로 선택됩니다.
- 주기적 시간 폴링(polling): 리더는 주기적으로 팔로워 노드들에게 시간을 요청하며, 각 노드는 크리스천 알고리즘(Cristian's Algorithm)과 유사한 방식으로 자신의 현재 시간을 응답합니다.
- 평균 시간 계산 및 보정값 전송: 리더는 수집한 시간 값들을 종합하여 전역 시계(global clock) 기준이 될 평균 시간을 계산합니다. 이때 심하게 벗어난 비정상적인 클록 값은 평균 계산에서 제외할 수 있습니다. 이후 각 노드가 얼마나 조정해야 하는지에 대한 상대적인 보정값(correction)을 계산해 각 노드에 전송합니다.
여기서 중요한 점은, 버클리 알고리즘은 실제 시각 그 자체보다 노드 간의 상대적인 시간 차이에 초점을 맞춘다는 것입니다. 따라서 UTC 서버가 없는 환경에서도 내부적으로 일관된 시간 체계를 유지할 수 있습니다.
예제로 살펴보는 시계 동기화 과정
버클리 알고리즘을 사용해 시계를 동기화하는 전체 단계를 예제와 함께 정리해 보겠습니다. 분산 시스템의 각 노드는 다음과 같은 시계 값을 가지고 있다고 가정합니다.
N1 -> 14:00 (마스터 노드) N2 -> 13:46 N3 -> 14:20
1단계 – 리더 선출: 선거 과정을 거쳐 노드 N1이 시스템의 마스터 노드로 선택됩니다.
2단계 – 시간 요청: 리더(N1)가 모든 노드에게 현재 시간을 요청하고, 각 노드는 자신의 시간을 응답합니다.
N1 -> 시간 : 14:00 N2 -> 시간 : 13:46 N3 -> 시간 : 14:20
3단계 – 평균 계산 및 보정값 전송: 리더는 세 노드의 시간 평균인 14:02를 기준 시간으로 계산하고, 각 노드에 맞는 보정값을 되돌려 보냅니다.
N1 -> 보정된 시간 14:02 (+2) N2 -> 보정된 시간 14:02 (+16) N3 -> 보정된 시간 14:02 (-18)
즉, N1은 시계를 2분 앞당기고(+2), N2는 16분 앞당기며(+16), N3는 18분 늦추면(-18) 세 노드 모두 14:02로 동기화됩니다. 이처럼 버클리 알고리즘은 마스터 노드를 중심으로 시간을 수집·평균화하고 보정값을 배포하는 방식으로, 분산 시스템 전체 노드의 시계를 효과적으로 동기화합니다.