슭의 개발 블로그

broadcastTime ≪ electionTimeout ≪ MTBF Raft가 정상적으로 동작하기 위해서는 반드시 위의 조건을 만족해야 한다. electionTimeout은 leader election에서 설명한 random 한 timeout의 최대치를 의미한다. 사실 broadcastTime, electionTimeout, MTBF 중에서 사용자가 설정할 수 있는 것은 electionTimeout 뿐이다. 따라서 위의 조건을 만족시킨다는 것은 적절한 electionTimeout을 선택한다는 것이다. MTBF 는 평균 무고장 시간(Mean time between failures)의 약자로, 한 서버가 시작한 뒤 죽기 전까지의 평균 시간을 의미한다. 보통 MTBF가 길면 availability가 높지만, availability와 일치하지는 않는다. MTBF가 길더라도 MTTR (Mean time to repair)가 길면 availability은 떨어질 수 있다. MTBF는 시스템의 고유한 속성이다. MTBF는 보통 노드가 하는 일의 종류와 개발자의 숙련도, 얼마나 비싼 하드웨어를 사용하는지에 따라 결정된다. Raft paper 는 electionTimeout을 MTBF보다 작게 할 것을 권장한다. 실질적으로 MTBF는 최소 몇 주에서 몇 개월 정도 되기 때문에 electionTimeout을 이보다 더 크게 설정하는 것은 쉽지 않다. 이는 그냥 electionTimeout을 너무 크게 설정하지 말라는 정도로 받아들여도 된다. 리더가 죽은 뒤 electionTimeout 동안 client의 요청을 전혀 처리 못 하니 네트워크 전체의 availability를 올리기 위해서 가능하면 작은 electionTimeout을 설정해야 한다. 하지만 electionTimeout을 너무 작게 설정하면 안 된다. electionTimeout은 아무리 작아도 broadcastTime보다 커야 한다. broadcastTime이란, 한 노드에서 네트워크 안의 다른 모든...

Raft는 모든 결정을 leader가 맡아서 한다. 따라서 term이 변경되기 전에는 leader의 결정을 따르면 된다. 문제는 leader에 문제가 생기거나 네트워크 파티션으로 인해 leader가 변경되고 다음 term으로 진행된 경우다. Consistency를 위해 가장 이상적인 것은 모든 노드가 하나의 leader만 따르도록 하는 것이다. 하지만 이는 사실상 불가능하다. 이게 가능하면 애초에 합의에 도달한 것이다. 그래서 Raft에서는 특정 시간에 2개 이상의 리더가 존재할 수 있다. 단, state를 변경시킬 수 있는 리더는 1개 밖에 있을 수 없다. 이 두 말은 별 차이 없는 것 같지만, 이 차이가 분산 환경에서 구현 가능한 시스템이 되도록 만들어준다. Raft에서는 leader에 커밋 된 로그만이 state를 변경시킨다. Leader가 커밋하기 위해서는 네트워크에 참여하는 노드 과반의 동의가 필요하다. 새 leader가 선출되면 과거의 leader는 절반 이상의 지지를 받지 못한다. 모든 요청에 요청하는 노드의 term이 담겨있고, 요청받은 쪽은 자신의 term보다 작은 term인 노드가 보낸 요청은 모두 거절한다. 새 leader가 선출됐다는 것은 이미 절반 이상의 노드가 다음 term으로 넘어갔다는 것이고 과거의 leader를 지지하는 노드는 절반이 되지 않기 때문에 과거 leader는 더 이상 상태를 변경시킬 수 없다. 따라서 같은 시간에 두 개의 노드가 상태를 변경시키는 것은 불가능하다. 물론 leader가 아닌 노드들이 가지고 있는 상태는 consistent 하지 않다. 새 RequestVote를 받기 전에 과거의 leader가 보낸 AppendEntries 메시지를 받고 자신의 상태를 변경시킬 수 있기 때문이다. 하지만 네트워크의 상태는 리더에 커밋 된 로그를 기준으로 만들어지기 때문에 각 노드의 inconsitecy는 클라이언트가 보는 네트워크 상태에 영향을 주지 않는다. 그렇다면 leader에 커밋 된 로그를 가지지 않은...

Raft가 가장 중요하게 생각하는 요소는 이해할 수 있는 알고리즘을 만드는 것이다. 이해할 수 있고 구현하기 쉬운 알고리즘이 Raft의 가장 중요한 요소이기 때문에 Raft는 로그를 누적시킬 수는 있지만 지울 수는 없는 append only 정책을 사용한다. Append only 정책을 사용하기 때문에 Raft의 state를 바꾸는 명령은 AppendEntries 밖에 존재하지 않는다. 사실 Raft가 정의하는 필수 RPC( Remote procedure call )은 지난번 글에서 설명한 RequestVote와 이번에 설명할 AppendEntries 뿐이다. leader가 보내는 heartbeat은 빈 entry를 추가하는 AppendEntries 메시지이다. Client가 state를 변경하자고 leader에게 요청하면, leader는 새로운 로그를 만든다. 하지만 이 로그는 아직 state를 변경시킨 것은 아니다. Leader는 새 entry를 커밋하라고 follower들에게 AppendEntries 메시지를 보낸다. follower는 AppendEntries 메시지를 받으면 각자의 스토리지에 받은 로그를 커밋하고 leader에게 답변을 보낸다. Leader는 과반의 follower가 로그를 커밋했다는 메시지를 받으면, 자신도 로그를 커밋한다. 이렇게 leader에 log가 커밋된 뒤에야 state가 성공적으로 변경된 것이고, 클라이언트에게 요청이 처리됐다고 응답을 보낸다. AppendEntries 메시지는 follower가 가져야 할 로그들을 담고 있다. follower는 각자 저장하고 있는 로그의 상태가 다르기 때문에 follower들에게 보내야 할 로그의 양도 전부 다르다. 이는 leader가 nextIndex라는 이름으로 각 follower에 어떤 로그를 보낼지 저장하고 있다가 메시지를 보낼 때 사용된다. Follower가 할 일은 leader가 보낸 로그를 저장할 수 있는지 보고 leader에게 응답을 보내준다. Follower는 Ap...

Raft에서는 모든 결정을 leader가 한다. 클라이언트의 모든 요청은 리더를 통해서만 가능하고, 새로운 로그를 추가하는 것도 새로운 노드가 추가되거나 기존의 노드를 지우는 것도 리더를 통해서 결정된다. leader의 명령을 따르는 노드들은 follower라고 하는데 follower들은 leader의 명령을 그대로 따른다. Follower는 leader가 보낸 명령에 따라 자신의 상태를 변경하고, 새로운 클라이언트가 접속하면, 클라이언트에게 어떤 노드가 리더인지 알려준다. Raft에서는 의도적으로 follower가 할 수 있는 일이 별로 없도록 만들었고 덕분에 프로토콜을 단순하게 만들 수 있었다. Leader인 노드는 일정 주기로 follower들에 heartbeat을 보낸다. follower들은 leader의 heartbeat을 듣고 있다가 일정 시간 동안 heartbeat을 듣지 못하면 leader가 죽었다고 생각하고 자신을 후보로 추천하며 다른 노드들에 자신을 leader로 뽑아달라고 RequestVote 요청을 보낸다. 이렇게 자신을 RequestVote 요청을 받은 노드를 candidate이라고 부른다. RequestVote를 받은 노드는 현재 자신의 상태를 보고 candidate이 더 최신 상태라면 새 leader를 지지하는 응답을 보내고, 그렇지 않으면 거절하는 응답을 보낸다. 반 이상의 노드가 자신을 지지한다고 응답하면 이 candidate은 leader가 된다. RequestVote를 보내고 일정 시간 동안 leader가 되지 못한 candidate은 다시 한번 모든 노드에게 RequestVote를 보낸다. 이때 얼마 만에 다시 RequestVote를 보낼지는 특정 범위 내에서 랜덤하게 결정된다. 랜덤한 timeout을 사용한다는 것은 Raft를 효율적으로 동작하게 하는데 매우 중요하다. 만약 고정된 시간을 사용한다면 모든 후보가 자기 자신에게 투표하라고 주장하며 선거가 끝나지 않을 수 있다. Candidate이 더 최신인지 아닌지는 te...

분산 시스템을 구축할 때, 모든 노드가 독립적으로 돌아가는 시스템을 설계한 것이 아니라면, 공유된 상태를 합의하기 위한 모종의 방법이 필요하다. 이런 식으로 분산 환경에서 상태를 공유하는 알고리즘을 consensus algorithm 이라고 한다. consensus algorithm 중에서 가장 유명한 알고리즘은 Paxos 다. 하지만 Paxos는 구현은커녕 이해하는 것 자체가 어렵기 때문에, Paxos를 구현한 라이브러리가 거의 없었고, 일부 분산 시스템들이 내부적으로 사용하는 정도였다. 그래서 분산 시스템을 구축할 때 현실적으로 사용할 수 있는 방법은 Zab algorithm을 사용하는 Zookeeper 를 이용하는 것이었다. Zookeeper는 매우 훌륭하다. 사실 지금까지도 분산 환경에서 consensus를 위해 사용할 수 있는 검증 된 거의 유일한 라이브러리라고 말할 수도 있을 정도다. 하지만 Zookeeper는 메시지의 순서가 보장돼야 하기 때문에 반드시 TCP를 사용해야만 한다. 또한, Zab algorithm이 Zookeeper의 구현과 긴밀하게 엮여 있기 때문에 다른 구현을 만들기 힘들어 반드시 JVM을 띄워야 하는 문제가 있다. Raft 는 구현체를 만들기 어렵다는 기존 consensus algorithm의 문제를 해결하기 위해 이해하기 쉬운 것을 최우선으로 설계된 consensus algorithm이다. Raft에서는 노드 간 공유될 state를 append-only state machine으로 본다. 따라서 노드 간에 상태가 합의됐다는 것은 이 state machine을 변경시키는 append command가 같은 순서로 적용됐다는 것을 의미한다. append command를 추가하는 것을 로그를 추가한다고 하고, 모든 노드가 같은 state를 가지게 하는 것을 log replication이라고 한다. 이때 어떤 append command를 추가할 것인지를 모든 노드가 일치한 정보를 가지는 것이 중요한데, Raft는 리더를 ...

C++의 const_cast 는 레퍼런싱하는 object의 cv-qualifier를 제거하는 캐스팅이다. cv-qualifier는 타입에 constness와 volatility 를 더해주는 한정자이므로 const_cast 는 constness뿐 아니라 volatility도 제거할 수 있다. constness를 제거하면 수정할 수 없었던 object를 수정할 수 있게 해주고, volatility를 제거하면 해당 object에 접근하는 코드가 최적화되어 사라질 수 있게 해준다. 따라서 const_cast 는 실제 존재하는 object가 별도로 있고, 그것에 접근하는 방법을 변경한다. 문제는 volatile object의 레퍼런스를 const_cast 로 volatility를 없앤 뒤 이 object에 접근하는 것이나, const object의 레퍼런스를 const_cast 로 constness를 없앤 뒤 이 object를 수정할 경우 이 코드가 어떻게 동작할지는 undefined behavior 라는 것이다. 즉 아래와 같은 코드들은 전부 undefined behavior이다. 그렇다면 const_cast 는 언제 사용하는 것일까? 사실 const_cast 를 사용해야만 하는 경우는 없다. 무언가를 하기 위해 반드시 const_cast 가 필요하다고 느껴진다면 디자인에 무언가 문제가 있는 것이다. 그래서 C++ Core Guidelines 에서는 const_cast를 사용하지 않는 것 을 권장한다. 흔히 const_cast 를 사용하는 패턴을 정리하면 아래의 3가지 패턴으로 분류할 수 있다. 이제부터 그 3가지 패턴이 왜 사용하면 안 되는지 설명할 것이다. 첫 번째 용례는 어떤 object의 cv-qualifier를 cv 1 이고, 이 object를 레퍼런싱하는 cv 1 보다 더 cv-qualified 된 cv 2 를 가지는 변수를 가지고 있을 때, cv 1 보다 높고, cv 2 보다는 낮은 레벨의 cv-qualifier를 갖도록 하는 것이다. 즉, i...

as-if rule 이란, 프로그램의 실행 결과가 변하지 않는다면 소스에 적혀있는 것이 아닌 다른 방법으로 실행하는 것을 허용하는 규칙을 말한다. 이러한 규칙을 as-if rule이라는 이름으로 부르는 것은 C++에서만 찾을 수 있지만, C를 비롯한 다른 언어에서도 이러한 부류의 최적화를 허용한다. as-if rule을 허용하는 이유는 크게 두 가지로 보인다. 우선 컴파일러의 최적화를 방해하지 않기 위함이다. 만약, 표준 문서에서 적용할 수 있는 최적화 방법을 화이트 리스트로 관리한다면, 새로운 최적화 기법이 나왔을 때, 컴파일러가 이를 적용하기 위해서는 표준을 수정해야 한다. 하지만 표준에서 허용하지 않는 동작만 기술해두면 컴파일러 구현체에서 새로운 최적화를 구현하는데 조금 더 자유로울 수 있다. 두 번째 이유는 C++이 가정하는 abstract machine이 엄밀하게 정의되지 않았기 때문이다. 일반적으로 C++의 실행 타깃은 native processor다. 이 프로세서는 제조사에 따라서, 혹은 칩 아키텍처에 따라서 다른 특성을 가질 수 있는데, C++ 표준은 이때 실행할 프로세서의 종류나 특성을 한정 짓지 않는다. 두 번째 이유는 C++이 가정하는 abstract machine이 실행 타깃에 의존하는 형태로 정의되었기 때문이다. 이를 parameterized nondeterministic abstract machine이라고 한다. 구현체는 이 parameter를 정해 실제 abstract machine을 완성한다. C++이 abstract machine을 이렇게 복잡한 방식으로 정의하는 이유는 C++의 실행 타깃이 가상 머신이 아닌 native processor이기 때문이다. 이 프로세서는 아키텍처에 따라서 다른 특성을 가질 수 있다. 다양한 아키텍처를 지원하기 위해 C++ 표준은 실행할 프로세서의 특성을 한정 짓지 않는다. CPU 별로 메모리 오더, 레지스터 크기, 레지스터 개수 등이 전부 다르므로 가능한 최적화도 전부 다르다. 따라서 표준에...