분산 시스템의 기초 개론 – 2

이전 글에서 Write-Ahead-Log, Leader and Follower, Version Control, Majority Quorum, Generation Clock에 대해 언급 했다. 이번 글에서는 그 이후의 것을 알아본다.

이 글은 “Patterns of Distributed Systems” (Unmesh Joshi)의 책을 기초로 쓰였다.

몇 분 후에 A와 B 모두 살아났다. 복구 과정속에서 각자 Leader일 때 commit된 정보를 Follow에게 뿌리게 된다. 이때, [id123=567]와 [id123=888] 라는 상태가 공존하게 된다. B가 먼저 살아나서 [id123=888]이 적용 됐으나, A가 살아남에 따라 이전 상태인 [id123=567]로 데이터가 씌어질 수도 있다.

이 문제를 해결하기 위해서는 “Leader가 바뀔 때 마다” “세대(Generation) 번호“를 같이 기록해야 한다. 최초 A가 Leader일 때는 0세대이다. 그리고 B가 Leader로 변하자 1세대 라고 기록한다. 추후 복구 과정속에서 데이터가 겹친다면(Conflict) “더 높은 세대의 데이터“를 선택한다.

Generation Clock을 가지는 것은 또 다른 문제점을 해결할 수도 있다. A 서버가 죽은게 아니라 일시적으로 네트워크가 끊겼을 수도 있다. 이때, A 스스로는 Leader가 바뀌었다는것을 알아채지 못 할 수도 있다.

Generation Clock이 있으면 세대가 바뀌었음(=Leader가 바뀌었음)을 알아채고 스스로 Follower Mode로 전환할 수 있다.

기존에는 3개의 서버만 존재하고, 1개의 Leader만 있는 상황을 고려했다. 하지만 Majority Quorum에서는 이것이 단순한 문제가 아니게 된다. 전체 의사회(Quorum)의 반 이상이 승인(Accept)해야 하기 때문이다. A, B, C 3개 서버중, 본인을 포함해서 최소 2개 서버에서 승인을 받아야 된다.

각 구성원에게 어디까지 됐는지 알려주기 위해서는 요청에 번호를 붙여야만 한다. 다시 처음으로 돌아가서 요청에 번호를 붙여보자.

A는 14: [id333=666] 처럼 번호를 붙여서 B, C에게 데이터를 보낸다. B, C중 하나가 허가를 내주면 A는 최고점(High-Water Mark)=14 라고 기록하고 전파한다. High-Water Mark를 통해서 어디까지 처리가 됐는지를 각 서버들에게 알릴 수 있게 된다.

순서대로 번호를 붙여서 예시를 보자.

1. A가 id555=1111], [id333=666], [id123=444] 라는 요청을 수신
2. A가 들어온 순서대로 13: [id555=1111], 14: [id333=666], 15: [id123=444] 로 번호 붙이고, B와 C에게 허가 요청을 보냄
3. 13번을 C가 허가(응답)해줌.
4. (정족수가 넘었으므로, 작업이 어디까지 됐는지 기록하는 High-Water Mark = 13으로 수정)
5. 13번을 B도 허가해 줌
6. (이미 High-Water Mark가 13이므로 별다른 처리 없음 = 이미 13번 까지는 처리됐다고 알고 있음)
7. High-Water Mark = 13 이라는 상태를 각 구성요소에게 전파
8. ~~~~~ 계속해서 작업 진행 ~~~~~

14번도 마찬가지이다. 14번은 B가 먼저 응답한다. B가 응답하자 마자 현재 처리의 최고점=14 라는 상태를 가진다. C가 뒤늦게 14번 허가함을 보내도 이미 최고점이기 때문에 추가적인 반응이 없다.

High-Water Mark 전파는 실시간일 필요는 없음

High-Water Mark를 알리는 신호는 시간 단위로 (100ms 마다, 1초마다 등등) 보내도 되고, 매 Accept마다 보낼 수도 있다. 책에서는 서버가 정상 작동중인지 확인하는 Heart Beat에 포함할 것을 언급한다.

B, C 입장에서는 Leader인 A와 연결이 끊겼다고 판단하고, 자기들끼리 처리를 이어 나간다. B가 다음 Leader가 됐고, 복구의 책임을 가졌다고 하자. B는 B, C의 Uncommitted 로그를 전부 확인한다. 그러면 15번 작업이 Quorum에 의해 정족수 이상의 승인을 받았음을 확인 할 수 있다. 이것을 통해 데이터를 최고점=15라는 정보를 확보 할 수 있다.

멱등성 처리는 일반 DBMS에서도 중요하다. 멱등성을 가진다는 말은 같은 작업을 수차례 반복해도 동일한 값을 가진다는 의미이다. 예를 들어, 첫번째 코드는 멱등성을 가지지만 두번째는 그렇지 않다. 첫번째 줄은 100번을 실행해도 id333에 10이 저장된다. 그러나 두번째 코드는 100번 실행하면 2000이라는 숫자가 저장될 것이다. 한번 더 저장하면 2020이 될 것이다.

[id333] = 10
[id333] = [id333] + 20

조금 복잡한 시나리오를 생각해 보자. 여기서도 A, B, C 라는 구성요소 3개가 등장한다. 마찬가지로 A가 Leader이다.

ESM이라는 사람이 A에게 “10이라는 데이터를 미국에 보내줘” 라고 요청한다. 슬프게도 요청 중간에 A가 죽어버렸다. ESM은 처리 결과를 알지 못한다. 하지만 이 시스템은 발송 여부를 반드시 알려줘야 한다. 발송 여부를 알 수 없으면 안된다는 제약이 있다.

이 문제를 해결하기 위해서 각 요청에 ID를 발급하고 알려준다. 이제 ESM은 A에 REQ-10: 10이라는 데이터를 미국에 전송 이라고 보낸다. A는 결과 정보를 저장해 둔다. 결과 목록에 REQ-10 을 항목을 만들고, 그곳에 “성공” 또는 “실패”를 저장한다.

만약 ESM이 요청을 보내고 TCP-ACK를 받기 전에 네트워크가 손상됐다고 하자. 네트워크가 복구되자 마자 ESM은 이 요청의 결과를 알고 싶어한다. 그러면 REQ-10: 10이라는 데이터를 미국에 전송이라는 요청을 한번 더 보내면 된다. 이미 정상 접수된 항목이라면 결과 목록의 결과가 즉시 응답될 것이다. 접수가 안됐다면 처리가 이루어 질 것이다.

결과 정보를 여러 서버에 복제하면 효과가 더 크다. Quorum에 요청을 보낼때 요청 ID도 같이 보낸다고 하자. Leader인 A가 정족수 과반의 허가를 받았다. 처리를 다 하고 나서 Quorum에 결과를 공유하자 마자 서버가 죽었다. 그렇다면 ESM은 옆의 구성요소에 REQ-10의 작업 결과를 물어보면 된다.

허가를 받자마자 A가 죽어버렸다 해도 된다. B가 다음 Leader가 되어 복구를 담당한다고 하자. B는 Quorum의 데이터를 모아서 Uncommitted Transaction을 복구한다. (멱등성을 통해) 로그를 Replay를 하고, 이 결과를 Quorum에 공유하면 ESM은 다른 구성요소에서라도 결과를 알아 낼 수 있다. REQ-10이 어디에서도 발견되지 않았다면 짜피 Accept 되지 않은 요청이므로 실행하면 된다.

분산 시스템에서는 “일의 순서”가 중요하다. 1개의 서버에서만 동작한다면 쉽게 문제를 해결 할 수 있다. 모든 요청마다 번호를 붙이면 된다. 그러면 Total Order가 가능하다.

그러나 여러 개의 서버가 등장하면 순서 보장이 어려워 진다. 현재 시간으로 동기화 하는 것은 불가능 하다. 모든 서버가 완전히 정확한 시간을 동기화 하는 것은 이상 세계에서나 가능하기 때문이다. 10ms라도 차이나면 일의 순서가 바뀔 수 있다.

Lamport Clock은 가상의 논리적 시계로서, 시스템 시간과 상관 없이 독립적인 순서 보장을 가능하게 한다.

각 구성 요소는 각자의 카운터를 가진다. 그리고 단위 작업이 있을 때 마다 각자의 숫자를 +1 한다. 이 숫자는 다른 서버에 요청을 보낼 때 같이 보낸다. 그러면 해당 숫자를 받은쪽에서 본인의 카운터와 상대방에게서 받은 숫자중 더 큰 숫자 + 1 Counter에 저장한다

구성 요소간 통신을 할 수도 있지만, 사용자가 통신하면서도 사용할 수 있다. 아까 예시를 다시 보자. [id111=333], [id555=777] 상태에서 ESM이 A: [id111=333] → B: [id555=777] 요청을 했다. 이때, 단순히 시간 값을 사용하면 순서가 엉킨다. 하지만 사용자를 통해서 A의 Lamport Clock을 B에게 넘긴다면 최소한 B는 A보다 큰 clock을 가지게 된다. (순서가 유지된다)

그러나 Lamport Clock가 제대로 동작하기 위해서는 “연관된 작업”이어야 한다. 만약 A와 B가 계속 독립적으로 운영된다면 각자의 숫자를 가지게 될 것이다. 그리고 그 동안에는 숫자가 더 크다고 해서 “최신 상태”이다는 보장을 할 수 없다. A가 요청을 더 많이 받았다면 A의 Lamport Clock이 당연히 클 것이다. 그러므로 연관된 작업 순서 사이에서만 순서가 보장된다. Lamport Clock을 이용한 버전 값 자체는 Partial Order이다.

Lamport Clock은 순서를 알려주기에는 좋다. 그러나 처리 했을때의 시간을 알 수는 없다. 일반 사용자는 실제 처리된 시간을 알기 원한다. 또한, 조금은 틀리더라도 전체적인 순서 보장이 필요하다. Timestamp가 들어가면 조금의 오차는 있더라도 전체적인 순서를 알 수 있다. 그러므로 서버의 Timestamp를 섞어 쓰는 방법이 필요하다. 이게 Hybrid Clock이다.

Hybrid Clock = (Server Timestamp, Lamport Clock) 이다. 각 구성요소간 메세지를 보낼때 Hybrid Clock을 포함해서 보낸다. 메세지를 수신 하는 서버는 Hybrid Clock = (Max(메세지 내의 Timestamp, 내 서버의 Timestamp), Max(메세지 내의 Lamport Clock, 내 서버의 Lamport Clock) + 1) 을 사용한다. 시간 값이 있으므로 “동일한 시간 값의 Lamport Clock”을 사용하면 된다.:

시간 차이는 계속해서 저장되진 않는다. 대신, Timestamp의 최대값을 저장한다. “+5분을 해야한다” 처럼 보정 값을 가지는 대신에 “현재 알려진 최대의 Timestamp”를 저장하고, max(시스템 Timestamp, 알려진 최대 Timestamp)를 사용한다. 덕분에 서버 시간이 미래일 경우 그냥 과거로 돌리면 된다. 그러면 서버의 Timestamp가 아까의 미래 시간이 될 때 까지 알려진 최대 Timestamp가 쓰일 것이며, Lamport Clock의 숫자가 늘 것이다.

그러나, 이 경우 “최대 시간 차이”만큼 기다려야 한다는 문제가 생긴다. 20초에 Update요청을 넣었어도 25초 까지는 적용되지 않는다. 다른 사용자들이 22초, 24초에 읽기 시도를 해도 과거 값이 보인다. 또한, 쓰기 작업도 대기가 발생한다. 그로 인해 쓰기 처리량도 줄어든다.

때문에, 일반적으로 200ms ~ 500ms의 시간 차이를 가정하고 분산 프로그램을 만든다고 한다. 이 숫자는 여러 데이터센터 속의 서버 시간을 비교했을 때, 주기적으로 NTP 시간 동기화를 하는 서버들 간의 최대 시간 차이라고 한다.

만약 미래의 시간이 수신된다면, Client 측에서 해당 시간차이 만큼을 대기하여 Clock을 일치 시킨다. 미래의 값이 존재한다면 논리적 오류가 발생할 수 있기 때문이다. Client에서 절대 미래의 값을 다루진 않기 위해, Client에서 sleep(해당 레코드의 최신 시간 - 현재 시간)을 한 뒤에 다시 읽기 시도를 한다고 한다.