벡터 클럭 (Vector Clock)

한 줄 정의: 여러 대의 컴퓨터가 동시에 작업할 때, 어떤 사건이 다른 사건보다 먼저 일어났는지를 물리적 시계 없이도 판단할 수 있게 해주는 논리적 시간 기록 방법입니다.

쉽게 풀면

여러 대의 서버가 각자 따로 작업을 진행하는 분산 시스템에서는, 각 서버의 시계가 정확히 똑같이 맞춰져 있지 않아서 "어느 사건이 먼저 일어났는가"를 단순히 시각으로만 비교하기 어렵습니다. 벡터 클럭은 각 서버마다 자신만의 숫자 카운터를 가지고, 사건이 하나 발생할 때마다 그 카운터를 올리는 방식입니다. 그리고 서버끼리 메시지를 주고받을 때는 서로의 카운터 값을 함께 전달해서, 나중에 두 사건의 카운터 목록(벡터)을 비교하면 "이 사건이 저 사건보다 먼저 일어났다" 또는 "두 사건은 순서를 알 수 없이 동시에 일어났다"를 판단할 수 있습니다.

왜 중요한가

분산 시스템에서는 물리적 시계의 오차나 네트워크 지연 때문에 여러 노드에서 발생한 사건들의 정확한 순서를 절대 시각만으로는 판단하기 어렵습니다. 벡터 클럭은 이러한 한계를 논리적 순서 관계로 대체해, 분산 데이터베이스의 동시 갱신 충돌 탐지, 분산 파일 시스템의 버전 관리, 분산 디버깅 등 여러 노드 간 인과관계 파악이 필요한 분산 시스템 연구 전반에서 기초 도구로 쓰입니다.

논문에서는 이렇게 쓰입니다

"분산 데이터베이스에서 동시 갱신으로 인한 충돌을 탐지하기 위해 각 복제본에 벡터 클럭(vector clock)을 부여하고, 인과 관계가 불분명한 갱신을 충돌로 표시하였다."

이 문장은 "여러 곳에서 동시에 데이터를 수정했을 때, 어느 수정이 먼저인지 알 수 없는 경우를 벡터 클럭으로 찾아내서 충돌로 처리했다"는 뜻입니다.

"분산 디버깅 도구는 각 프로세스의 메시지 송수신 이벤트에 벡터 클럭을 기록하여, 장애 발생 전 이벤트들의 인과적 선후 관계를 사후에 재구성할 수 있도록 하였다."

분산 시스템 디버깅 연구에서는 이처럼 이벤트 로그에 벡터 클럭을 함께 남겨, 장애의 원인이 된 사건들의 순서를 나중에 정확히 추적하는 데 활용합니다.

"협업 편집 시스템에서 사용자 간 동시 편집 충돌을 해결하기 위해 벡터 클럭 기반의 버전 벡터를 이용해 편집 연산들의 인과적 의존 관계를 판단하였다."

여러 사용자가 동시에 문서를 편집하는 협업 도구 연구에서도 벡터 클럭 개념을 응용해, 어떤 편집이 다른 편집보다 논리적으로 앞서는지를 판단하는 데 사용합니다.

조금 더 깊게 보면

벡터 클럭은 이벤트 사이의 인과관계를 "먼저 발생함(happens-before)"이라는 논리적 순서 개념으로 정의하는데, 두 사건의 벡터 클럭을 비교했을 때 한쪽이 다른 쪽을 모든 항목에서 앞서면 인과관계가 있는 것으로, 어느 쪽도 앞서지 못하면 동시 발생(concurrent)한 것으로 판단합니다. 이는 각 노드가 정수 하나만 증가시키는 더 단순한 논리적 시계(램포트 클럭)로는 구분할 수 없는 동시 발생 여부까지 판별할 수 있다는 점에서 차이가 있습니다. 다만 노드 수가 많아지면 벡터의 크기도 함께 커지는 확장성 문제가 있어, 실제 대규모 시스템에서는 압축된 형태의 버전 벡터나 다른 근사적 기법과 함께 절충해 쓰는 경우가 많습니다.

주의할 점

벡터 클럭은 서버(노드) 수가 늘어날수록 각 사건마다 저장해야 하는 카운터 목록의 크기도 함께 커지기 때문에, 노드가 매우 많은 대규모 시스템에서는 저장 공간과 전송 비용이 부담이 될 수 있습니다. 이런 이유로 실제 서비스에서는 합의 알고리즘이나 다른 단순화된 버전 관리 기법과 함께 절충해서 사용하기도 합니다.