크리스티안 알고리즘, 버클리 알고리즘, NTP 등으로도 시간을 나노초 단위까지 정확하게 보장하기는 힘들다. 따라서 시간에 너무 집착하는 것은 좋지 않을 수도 있다.
다시 생각해보자 결과적으로 우리가 중요하게 생각하는 것은 작업의 순서를 보장하는 것이다.
이 부분에 집중해서 아래의 내용들을 살펴 보겠다.
- 램포트 시계(Lamport Clock)
- 레슬리 램포트 시계(Leslie Lamport Clock)
램포트 시계는 이벤트 간의 인과 관계를 정확하게 기록하기 위해서 사용된다.
따라서 다음과 같은 특징이 있을 수 있다.
- 인과 관계를 정확하게 파악할 수 있다.
- 두 이벤트 렘포트 시간값(Cn)을 비교해 순서를 판단할 수 있다.
- 동일한 램포트 시간값(Cn)을 가진 경우에는 램포트 시계 순서를 기준으로 판별한다.
이를 조금 더 시나리오 형태로 살펴보면 다음과 같다.
- 램포트 시계 p1, p2, p3가 존재한다.
- 모든 시계의 램포트 시간값은 0에서 시작하며, 즉 c1, c2, c3는 모두 0에서 시작한다.
- 특정한 램포트 시계 n에 이벤트가 기록이 된다면 cn은 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 이벤트와 p3 이벤트는 모두 렘포트 시간 값이 0으로 동일하기 때문에 더 작은 시계 번호인 p2가 먼저 실행이 되었을 것이다. 따라서 c2 = c1 + 1 (직전 값 + 1)하여 총 3으로 변화한다.
* [로그] P1.a -> P1.b -> P2.c
[값 기록]
P1, C1 = 2
P2, C2 = 3
P3, C3 = 0
마지막의 p3 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
램포트 시계는 한마디로 각 독립적인 프로세스가 카운터를 유지해 이벤트가 발생할 때마다 서로 카운터 값을 증가시키며 조정해 순서를 유지하게 된다. 그렇게 되면 멀티 스레드 환경에서 같은 자원에 대해 동시성을 핸들링 해야하는 것도 꼭 적용해야한다.
램포트 시계를 활용해 애플리케이션에서 수행해야할 작업들은 메시지와 램포트 시간을 같이 전달한다. 그리고 이 메시지는 각 지점이 자체적으로 가지고있는 큐에 기록되며, 이런 메시지는 램포트 시간을 기준으로 정렬된다.
그럼 이제 다음과 같은 점에서도 사용될 수 있다고 생각할 수 있다.
- 데이터베이스 복제 알고리즘
- 분산 데이터 베이스 병행 갱신 문제 해결
위에서 언급한 성질을 통해 복제 알고리즘을 설계해보자.
- 데이터베이스 업데이트 사항은 자신과 다른 지점에 메시지로 통지
- 업데이트 사항을 다른 지점에서 수신하면 해당 작업을 일단 큐에 저장
- 자신과 다른 지점에 대한 수신 확인 메시지를 전송, 단 해당 업데이트 작업이 큐의 가장 앞에 있을 경우에만 회신
- 업데이트할 일에 대한 수신 확인 메시지를 받으면, 해당 작업이 다른 지점에도 확인되었음을 표시
- 확인된 작업은 큐에서 가장 첫 번재 자리에서 제거하고, 해당 작업을 수행한다.
전체적으로 2단계 커밋 프로토콜에서 선제적 메시지 기록과 비슷한 논리가 어느정도 적용되어 있는 것 같다.
중요한 부분은 메시지를 보내기 전에 기록하고 합의가 완료되면 작업이 진행된다는 점이다.
지난 글에서 살펴본 은행 예제를 해결해보자.
- 서울 은행은 p1, c1 = 0
- 부산 은행은 p2, c2 = 0 으로 정의한다.
즉, p1의 입금 이벤트와 p2의 이자 이벤트의 경우 램포트 시간값이 동일하므로 p1의 카운터가 먼저 증가될 것이다. 즉 서울 이벤트가 먼저 발행이 된다.
그렇기에 다음과 같이 실행될 것이다.
- 10,000원 보유 → 1,000원 입금 → 예치금에 1% 이자 지급
- (10,000원 + 1,000원) × 1.01 = 11,110원
즉 기댓값이 아니라 조정값에 해당하는 금액이 계좌에 남아있어야 한다. 또한 이 과정에서 그 어떤 절대 시간도 필요하지 않는다.
램포트 시계와 다르게 벡터 시계라는 개념도 존재하는데 벡터 시계는 램포트와 달리 각 노드에 대한 타임스탬프가 단일 변수가 아니라 벡터로 표현된다. 그냥 가장 큰 차이는 scalar, vector의 차이인 것 같다. 이벤트의 순서를 보장하기 위함이란 것은 다름 없음