이중화된 데이터베이스 문제
어떤 큰 대형은행이 있다.
이 은행은 서울에 데이터베이스가 하나 있고, 부산에 데이터베이스가 하나 있다.
이 은행의 어떤 계좌에는 잔액이 10,000원 들어있다.
그리고 서울에 살고 있는 이 계좌의 주인이 계좌에 1,000원을 입금했다.
그런데 부산에서는 모든 계좌에 이자를 지급할 시점이 되어 현재 계좌의 잔고를 기준으로 1%의 이자를 지급하였다.
그래서 서울에 있는 데이터베이스의 잔액은 11,000원이 되었고, 부산에 있는 데이터베이스의 잔액은 10,100원이 되었다.
그리고 이 두 데이터베이스는 상대방의 상태를 알지 못한 채
서울에 있는 데이터베이스는 부산에 있는 데이터베이스에게 잔액을 1,000원 늘리라고 지시하고
부산에 있는 데이터베이스는 서울에 있는 데이터베이스에게 잔액을 1% 늘리라고 지시한다.
결과적으로 서울에 있는 데이터베이스 잔액은 11,110원이 되고, 부산에 있는 데이터베이스의 잔액은 11,100원이 되었다.
두 데이터베이스에 적용된 동작의 순서가 서로 달라서 최종 결과가 다르게 나타난 것이다.
따라서 이 문제를 해결하려면 서로가 수행하려는 2개의 동작을 어떤 것부터 적용할 지 합의를 봐야 한다.
크리스티안 알고리즘
이 문제를 해결하는 방법으로 가장 자연스럽게 떠오르는 것은 각각의 동작을 수행한 시각을 기록해서 시각을 비교하고 맞춰보는 것이다.
그런데 어떤 2개의 동작이 일어난 시각이 정말 거의 동시에 일어나서 ms 단위로 밖에 차이가 나지 않는다고 해보자.
과연 2개의 데이터베이스는 이 상황에서도 동작을 수행하는 순서에 대해 합의를 볼 수 있을까?
안타깝게도 합의를 보장할 수 없다.
왜냐하면 두 데이터베이스가 바라보고 있는 서로의 '시계'가 완전히 똑같다는 것을 보장할 수 없기 때문이다.
그러면 제 3자인 인공위성에 있는 시계를 기준으로 두고,
두 데이터베이스가 인공위성에게 물어봐서 들은 시각을 가지고 우선순위를 정하면 어떨까?
하지만 이것도 고려해야 할 점들이 있다.
클라이언트가 서버에게 현재 시각을 물어보고 그 결과로 오후 2:50 이라는 답을 얻었다고 해보자.
그러면 클라이언트는 이 응답을 받은 현재 시각이 2:50 이라고 생각하면 될까?
그럴 수는 없다.
왜냐하면 클라이언트의 질의가 서버에 도착하기까지 걸린 시간, 서버의 응답이 클라이언트에게 도착하기까지 걸린 시간을 고려해야 하기 때문이다.
이를 그림으로 조금 더 세분화해서 나타내면 위와 같이 나타낼 수 있다.
클라이언트가 T1 시점에 요청을 보냈을 때, T2 시점에 서버에 요청이 도착했다.
서버는 요청을 받아서 짧은 시간동안 현재 시간을 체크하고, 현재 시간의 응답을 T3 시점에 보낸다.
클라이언트는 T4 시점에 그 응답을 받는다.
위와 같은 상황에서 어떻게 해야 왔다갔다하는데 걸린 시간을 보정해서 정확한 시각을 계산할 수 있을까?
위 상황에서의 문제점은 T3 시점에 클라이언트가 알려준 시각을 T4에 받으면, T3와 T4 사이의 오차만큼 시간이 다르다는 것이 문제점이다. 따라서 T3 - T4 사이의 시간 간격을 알아내는 것이 중요하다.
이를 위해 클라이언트는 요청을 보낸 시각 T1 을 기록한다.
서버는 요청을 수신한 시각 T2를 기록해두었다가 T3에 시각을 전송할 때, T2도 같이 전송한다.
클라이언트는 이를 T4 시각에 받는다.
T1, T4 와 T2, T3 사이에는 서로 생각하고 있는 절대시간이 다를 수 있기 때문에, 이들 사이에는 연산을 할 수 없다.
하지만 T1 - T4, T2-T3 사이라면 연산을 할 수 있다.
우선 T4 - T1 을 해서 클라이언트 입장에서 요청을 보내고 응답을 받기까지 걸린 시간을 계산한다.
다음으로 T3 - T2 를 해서 서버 입장에서 요청을 처리하는데 걸린 시간을 계산한다.
그리고 (T4 - T1) - (T3 - T2) 를 계산한다.
이 값은 순수하게 서버의 요청 처리 시간을 제외한, 요청과 응답이 한 번 왕복하는데 걸린 시간을 나타낸다.
하지만 우리가 원하는 값은 '응답이 오는데 걸린 시간' 이다.
따라서 이 값을 구하기 위해 '요청을 보내는데 걸린 시간' 과 '응답이 오는데 걸린 시간' 이 동일하다고 가정한다.
그리고 왕복에 걸린 시간을 2로 나누어 응답이 오는데 걸린 시간을 추측한다.
이 값을 서버가 알려준 T3 시각에 더해서 T4 시각을 역산하면 클라이언트 입장에서의 시각을 추론할 수 있다.
다만 이 방법은 요청 전송 시각와 응답 전송 시각이 동일하다는 가정이 필요하기 때문에 불완전한 점이 있다.
버클리 알고리즘
버클리 알고리즘은 시계가 3개 있을 때, 하나의 기준 시계를 정하고,
모든 시계를 기준 시계를 기준으로 한 시각 오차의 평균으로 보정하여 맞추는 방법이다.
예를 들어 위와 같이 3개의 시계가 있다고 해보자.
3개의 시계 중 3시를 가리키는 시계를 기준 시계로 하여, 시각 오차 값을 계산한다.
2:50 - 3:00 = - 0:10
3:25 - 3:00 = 0:25
3:00 - 3:00 = 0:00
따라서 오차의 평균은 0:15 / 3 = 0:05 이다.
따라서 기준 시계를 3:00 + 0:05 = 3:05 로 맞추고,
나머지 시계들도 기준 시계의 시각인 3:05 로 보정한다.
물론 이때도 시계와 시계 사이의 데이터를 주고 받는데 걸리는 시간을 고려하여 보정해야 한다.
NTP (Network Time Protocol)
기준 시계로 동작하는 Stratum 0 계층
기준 시계를 기준으로 자신의 시계를 맞춰둔 Stratum 1 계층
stratum 1 계층을 기준으로 맞춰둔 stratum 2 계층
....
이렇게 계층마다 자신의 상위 계층을 기준으로 시계를 맞추는 방식이다.
이 방식은 계층이 기준 시계로부터 멀어질수록 오차가 점점 커지는 특징을 갖고 있다.
이때 어떤 계층의 장치가 자신의 시계를 맞출 기준 시계를 선정할 때는 자신의 윗 계층에 있는 모든 장비에 대해 k번씩 시간 질의를 보내고, k번의 질의로부터 온 응답의 편차가 제일 작은 장치를 자신의 기준 시계로 삼는다.
물론 이때도 시간을 계산하는 과정에서는 왕복시간을 고려하여 오차를 보정한다.
램포트 논리 시계
그런데 반전은, 분산 시스템에서 사실 위와 같이 힘들게 절대 시각을 계산해서 구할 필요가 없다.
맨 처음에 논의했던 이중화된 데이터베이스 문제는 사실 절대 시각을 구하지 못해서 발생한 문제가 아니다.
어떤 두 연산의 순서에 대한 합의를 이루지 못해서 발생한 문제다.
그리고 어떤 두 연산의 '순서' 합의를 이루기 위해서 절대 시계가 꼭 필요한 것은 아니다.
정확한 시각을 몰라도 선후관계만 알 수 있으면 충분하기 때문이다.
이와 관련된 시계 개념으로 램포트 논리 시계가 있다.
램포트 시계는 모든 장치가 각자 자신의 램포트 논리 시계 Ci 를 갖는다고 가정한다.
이 값은 각 장치가 시작할 때 0으로 초기화 되며, 램포트 논리 시계의 값은 정수 값으로 각 장치가 특별한 이벤트를 실행하기 전에 자신의 시각을 1 증가시킨다.
만약 한 장치가 다른 장치로 메세지를 보내는 경우,
메세지를 보내는 장치는 자신의 램포트 시각을 함께 전송한다.
메세지를 받는 장치는 자신의 램포트 시각과 메세지를 수신할 때 받은 상대방의 램포트 시각을 비교하여 더 큰 램포트 시각값에 1을 더해서 자신의 수신 이벤트에 대한 시각으로 간주한다.
어떤 두 이벤트에 대해, 두 이벤트의 선후관계가 명확하면 A → B 로 표기한다.
만약 두 이벤트에 대해, 선후관계가 명확하지 않다면 A || B 로 표기한다.
예시로 위와 같은 상황을 생각해보자.
P1 에서 a 라는 이벤트가 발생했다.
P1 의 램포트 시계 C1 은 1 증가한 1 이 되며, a 이벤트가 발생한 시각 C(a) = 1 이다.
다음으로 P1 에서 P2 로 메세지를 보내는 b 이벤트가 발생했다.
P1 의 램포트 시계 C1 은 1 증가한 2 가 되며, b 이벤트가 발생한 시각 C(b) = 2 이다.
그리고 메세지에는 2 라는 시각을 함께 포함하여 P2로 전송한다.
메세지를 수신한 P2 는 메세지를 수신하는 이벤트가 발생했을 때, 자신의 현재 램포트 시각인 C2 = 0 과 메세지에 들어있는 시각 C(m) = 2 를 비교하고, 더 큰 값인 2를 기준으로 +1을 해서 수신 이벤트 C(c)의 시각을 3으로 결정한다.
P3 입장에서는 자신의 독자적인 이벤트 d 가 발생하면서 자신의 램포트 시계를 1 증가시킨다.
이때 d 가 발생한 시각 C(d) = 1 이다.
이제 이렇게 구한 램포트 시계를 이용해서 이벤트의 선후 관계를 판별해보자.
이벤트의 선후 관계를 판별하는 방법하는 다음과 같다.
1. 램포트 시각이 더 큰 이벤트가 나중에 발생한 이벤트이다.
2. 램포트 시각이 같다면 장치의 프로세스 아이디가 더 큰 이벤트가 나중에 발생한 이벤트이다.
이를 통해 각 이벤트가 발생한 선후 관계를 위에서 정의한 기호로 나타내면 다음과 같다.
( C(a) || C(d) ) → C(b) → C(c)
이를 해석하면
a, d 이벤트는 선후 관계를 파악할 수 없지만,
b, c 이벤트는 a, d 이벤트 이후에 일어났다고 간주한다.
데이터베이스 복제 알고리즘
이제 위에서 논의한 램포트 논리 시계를 활용해서 이중화된 데이터베이스 문제를 해결해보자.
데이터베이스 복제 알고리즘은 다음과 같이 동작한다.
1. 데이터베이스를 업데이트해야 하는 작업이 발생하면, 해당 작업을 자신과 다른 DB로 전송한다.
2. 작업을 다른 DB로부터 수신했다면 해당 작업을 큐에 저장하는데, 큐에는 반드시 램포트 시각 순으로 저장한다. 또한 이때 해당 작업이 큐의 맨 앞에 있다면 수신 확인 메세지를 회신한다.
3. 업데이트 할 일에 대해 수신 확인 메세지를 받으면, 해당 작업이 다른 지점에서도 확인되었다고 체크한다.
4. 체크한 작업은 큐의 가장 첫 번째 자리에서 제거하고, 해당 작업을 수행한다.
은행 예시에 대해서 위 알고리즘을 적용해보자.
서울에 있는 데이터베이스는 1000원을 입금하는 작업을 자신과 부산에 있는 DB로 전송한다. (프로세스 1, 이벤트 시각 1)
부산에 있는 데이터베이스는 이자를 지급하는 작업을 자신과 서울에 있는 DB로 전송한다. (프로세스 2, 이벤트 시각 1)
서울에 있는 DB는 이 이벤트를 수신했을 때 이벤트 시각이 같으므로, 프로세스 번호가 낮은 자신의 작업의 우선순위를 더 높게 판단한다.
부산에 있는 DB는 서울 DB가 보낸 이 벤트를 수신했을 때 이벤트 시각이 같으므로, 프로세스 번호가 낮은 서울 DB의 작업의 우선순위를 더 높게 판단하고 큐의 앞에 넣는다. 따라서 큐의 맨 앞에 있는 서울 DB의 작업에 대해 수신 확인 메세지를 전송하고, 큐에서 제거한다.
수신 확인 메세지를 수신한 서울 DB 는 부산에서 수신 확인한 것을 보고 체크한다.
서울 DB는 체크한 작업을 큐에서 제거하고, 자신의 DB에 반영한다.
다음으로 서울 디비는 큐의 맨 앞으로 오게 된 부산 DB의 작업을 큐에서 제거하고 수신 확인 메세지를 부산 디비로 보낸다.
수신 확인 메세지를 받은 부산 DB 는 해당 작업을 자신의 DB에 반영한다.
만약 서울 DB 가 보낸 작업이 네트워크 통신 문제로 아주 늦게 부산 DB로 도착했다고 해보자.
하지만 그렇다고 하더라도 위 그림과 같이 동작하지는 않는다.
램포트 시계 상으로는 엄밀히 1.1 작업이 1.2 작업보다 우선순위가 높기 때문이다.
언제나 수신 확인을 보내는 것은 큐의 맨 앞에 있을 때 이다!
하지만 이 알고리즘도 완벽하지는 않다.
메세지가 전송 중 유실되는 케이스, 중간에 서버가 죽는 케이스, 메세지가 위변조된 케이스 등 다양한 장애 상황을 고려하지 않았기 때문이다.
'CS > 분산시스템특론' 카테고리의 다른 글
| [분산시스템특론] 5. CAP 이론 & FLP 정리 (0) | 2025.10.22 |
|---|---|
| [분산시스템특론] 3. 2단계 커밋 프로토콜 (1) | 2025.10.21 |
| [분산시스템특론] 2. 두 장군 이야기 (3) | 2025.10.20 |
| [분산시스템특론] 1. AI Agents vs. Agentic AI (0) | 2025.10.20 |
