슭의 개발 블로그

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. 회사에서 이런 거 하느라 바빠서 한동안 다른 글은 읽을 시간이 없네요. 발표는 몇 주 동안 계속할 거라서 당분간은 발표자료 만들면서 참고했던 자료들을 공유할 것 같습니다. Impossibility of distributed consensus with one faulty process 분산 환경에서 합의 알고리즘을 말할 때 빼놓을 수 없는 논문이다. 합의 알고리즘에 필요한 기본적인 속성은 크게 safety와 liveness가 있다. Safety는 잘못된 합의가 이루어지지 않는다 는 것이고, liveness는 언젠가는 합의가 반드시 이루어진다 는 것이다. 위 논문은 비동기 네트워크에서 하나의 fail-stop failure 노드만 있어도 이 합의가 이루어질 수 없다는 것을 보였다. 이를 FLP impossibility라고 부른다. Consensus in the presence of partial synchrony 첫 번째 논문이 비동기 네트워크에서 safety와 liveness를 보장하는 합의 알고리즘이 불가능하다는 FLP impossibility를 보였다. 그래서 이 논문은 partial synchronous model을 만들어 특정한 가정 아래서 safety와 liveness를 같이 보장하는 합의 알고리즘을 만들 수 있게 해줬다. Partial synchronous model은 메시지가 언젠가는 도착하는 것을 보장하지만 그 도착하는 시간이 언제인지 알 수 없는 모델이다. The Byzantine generals problem Byzantine failure라는 용어의 어원이 된 논문이다. 이...

블록체인이 유행하면서 블록체인의 수만큼 다양한 합의 알고리즘 이 나오고 있다. 이는 어째서일까? 애초에 왜 다양한 블록체인이 나오고 있는 것일까? 이는 근본적으로 합의 알고리즘이 무엇을 할 수 있고 무엇을 할 수 없는가에서 기인한다. 좋은 합의 알고리즘은 무엇을 보장해야 할까? FLP impossibility 우선 아무 문제 없는 두 노드가 서로 다른 값으로 합의하면 안 된다. 다른 값을 합의했다는 것은 블록체인 관점에서 보면 같은 높이에 서로 다른 블록이 생성됐다는 것이다. 이런 특성을 분산 시스템에서는 consensus의 safety라고 말한다. 또한, 합의가 언젠가는 이루어져야 한다. 분산 시스템에서 합의는 노드 간의 메시지를 주고받으며 각 노드의 상태를 변경시키며 이루어진다. 이때 문제없는 노드들은 무한 루프에 빠지지 않고 반드시 상태 변경이 종료돼야 한다. 모든 노드가 문제없이 합의를 할 수 있으면 이 시스템은 liveness가 보장된다고 말한다. 쉽게 풀어 말하면 safety는 "문제없는 노드 사이에서는 잘못된 합의가 이루어지지 않는다"라는 것이고, liveness는 "문제없는 노드들은 반드시 합의를 한다"라는 것이다. 문제는 byzantine failure가 아닌 fail-stop failure가 하나만 있어도 safety와 liveness를 둘 다 만족하는 합의 알고리즘이 존재할 수 없다 . 이를 FLP impossibility 혹은 FLP theorem이라고 한다. 따라서 합의 알고리즘을 선택한다는 것은 사실상 safety와 liveness 중 무엇을 선택하고 무엇을 버릴까 하는 문제이다. Liveness over Safety 비트코인 이 사용하는 합의 알고리즘은 사토시 나카모토가 처음 제안하였기 때문에 nakamoto consensus라고도 불린다. Nakamoto consensus는 언제나 더 어려운 문제를 푼 체인이 있으면 그 체인을 유효한 체인으로 판단한다. 즉, 지금 있는 체인보다 ...

2017년에 이어 올해 2018년까지 블록체인은 정말 시대의 대세가 됐다. 결국, 개발자 외에도 많은 사람이 블록체인을 이야기하고 있다. 그 사람들에게 블록체인이 어려운 이유를 말하라고 하면 대부분 블록체인은 단순한 기술을 넘어서 화폐이기 때문에 어렵다고 말한다. 하지만 이건 사실이 아니다. 가장 유명한 블록체인 시스템인 비트코인 이 대표적인 암호화폐 이기 때문에 사람들이 흔하게 하는 착각이다. 하지만 기술적으로 블록체인이 화폐일 이유는 없다. 블록체인을 조금 더 공부한 사람에게 물어보면 블록체인은 incentive model을 설계해야 해서 어렵다고 말한다. 블록체인에서는 사용자들의 자발적 참여를 유도하기 위한 incentive model을 설계해야 하고, 이는 결국 사람 심리의 영역이기 때문에 어렵다는 것이다. 하지만 이것도 블록체인이 어려운 근본적인 이유는 아니다. 블록체인이 어려운 이유는 블록체인이 분산환경에서 풀어야 하는 가장 어려운 문제를 풀기 때문이다. 분산 시스템은 여러 개의 노드 사이에서 메시지를 주고받으며 상태를 변화시킨다. 이때 모든 노드가 정상적인 경우만 가정할 수는 없다. 이런 시스템은 단일 노드에서 처리되는 시스템보다 문제가 발생할 확률이 늘어나기 때문이다. 하지만 현실적으로 모든 에러를 처리할 수는 없다. 그래서 일반적으로 분산 시스템은 자신이 감당할 수 있는 에러를 정의하고, 그 이외의 에러가 발생할 경우는 동작을 보장하지 않도록 설계된다. 이때 감당할 수 있는 에러의 종류를 시스템의 Failure Model이라고 부른다. 전통적으로 분산 시스템에서 Failure Model은 6개로 분류된다. 이 6 분류는 계층을 가지고 있기 때문에 더 큰 부류는 작은 부류를 포함한다. 분산 시스템은 목표로 하는 Failure Model을 설정하고 그보다 큰 부류의 failure가 발생했을 때는 처리를 포기한다. 가장 처리하기 쉬운 문제는 Fail-stop Failure Model이다. Fail-stop Failure Model...

Two Phase Commit (a.k.a. 2PC)은 distributed system에서 atomic commit 을 보장하는 프로토콜이다. 2PC는 나름 많은 에러 상황을 버티고, 괜찮은 성능을 보이기 때문에 많이 사용된다. 2PC에서 노드는 한 개의 coordinator와 여러 개의 cohort로 나누어진다. Coordinator는 commit 할 transaction을 만드는 노드고, cohort들은 coordinator가 보낸 transaction을 commit 하거나 revert 한다. 2PC는 이때 fail 하지 않은 모든 cohort가 같은 상태를 유지하도록 하는 것이다. 즉, fail 하지 않은 모든 노드는 다 같이 commit 하거나 revert 한다. 이때 coordinator를 어떻게 선정할지는 2PC의 영역이 아니다. 고정된 coordinator를 계속 사용할 수도 있고, 차례대로 돌아가면서 coordinator가 될 수도 있고, 별도의 leader election을 사용하여 coordinator를 선정할 수도 있다. 2PC는 어떻게든 coordinator가 선정된 뒤의 일이다. 2PC는 이름 그대로 2가지 phase로 나누어져 있다. 첫 번째 phase는 voting phase라고 부르고, 두 번째 phase는 commit phase라고 불린다. 각 phase의 시작은 coordinator가 보내는 메시지로 시작한다. Voting phase에서 coordinator는 commit 하고 싶은 transaction을 commit 할지 말지 투표하는 요청을 cohort에게 보낸다. VOTE 메시지를 받은 cohort들은 이 transaction을 바로 commit 하지 않는다. 해당 transaction을 커밋할 수 있으면 YES 메시지를, 없으면 NO 메시지를 coordinator에게 보낸다. Voting phase에서 coordinator가 quorum 이상의 YES 메시지나 NO 메시지를 모으면 commi...

분산환경 시스템에서는 다른 노드가 보낸 메시지가 정상적이라고 보장할 수 없다. 이때 잘못된 노드가 모두에게 틀린 메시지를 보낸다면 문제가 쉽게 풀린다. 틀린 메시지를 보내는 노드를 차단하면 된다. 하지만 일부 노드에게는 잘못된 메시지를 보내고, 일부 노드에게는 제대로 된 메시지를 보내는 경우는 문제 상황을 찾기 힘들다. 분산 시스템에서 각 노드는 다른 노드의 상태를 모르기 때문이다. 이런 식으로 일부 노드에게만 틀린 메시지를 보내는 노드를 가정하는 모델을 byzantine failure model이라고 부른다. Byzantine failure model은 네트워크에서 가장 풀기 어려운 모델임과 동시에 실제 네트워크에서 반드시 해결해야 하는 문제다. 특히 다른 노드를 신뢰할 수 없는 p2p에서는 반드시 Byzantine failure model을 가정하고 예외 상황을 처리해야 한다. 그렇다고 인증된 노드만으로 구성된 분산 시스템이라고 byzantine failure model을 가정하지 않아도 된다는 것은 아니다. 노드 자체는 신뢰할 수 있는 사람이 관리하더라도 해킹당했을 수도 있고, 버그로 잘못된 메시지를 보낼 수도 있고, 하드웨어에 문제가 발생할 수도 있다. Byzantine failure model에서도 정상적으로 돌아가는 시스템을 byzantine fault tolerance (a.k.a. BFT)라고 말한다. 당연히 BFT라고 해도 무한히 많은 faulty 노드에 대해서 동작하지는 않는다. 그래서 보통 어떤 시스템이 BFT라고 말할 때 전체 노드 중 몇 개의 노드에 문제가 있을 때까지 동작하는지를 같이 말한다. 예를 들어 N = 5f라고 말하면, 전체 노드 중 1/5가 byzantine failure일 때 정상 동작하는 시스템이고 N = 3 f + 1이라고 말하면, 전체 노드 중 1/3이 byzantine failure일 때까지는 문제없이 돌아가는 시스템을 말한다. 같은 BFT라고 한다면, 감당할 수 있는 faulty 노드의 비...

CAP theorem 은 분산 스토리지는 consistency(a.k.a. C ), availability(a.k.a A ), partition tolerance(a.k.a. P )를 동시에 만족시킬 수 없다는 것이다. 여기서 C , A , P 는 각자 일반적으로 사용되는 용어와 다른 용어로 사용되기 때문에 CAP theorem을 이해하려면 각자가 정의하는 것을 이해하는 것이 중요하다. C 는 모든 read operation이 최신 데이터를 받는 것을 보장하는 것이다. C 를 보장하는 시스템은 만약 최신 데이터를 돌려줄 것을 보장하지 못한다면 에러를 돌려줘야 한다. 개인적으로 분산 스토리지를 구현할 때 C , A , P 중 가장 구현하기 어려운 특성은 C 라고 생각한다. A 는 모든 operation이 에러가 아닌 데이터를 돌려주는 것이다. 이때 돌려주는 값은 최신 값이 아니어도 상관없다. 심지어 eventual consistency 와 A 를 보장하는 시스템에서는 실제로 존재할 수 없는 데이터 조합이 생길 수도 있다. P 는 partition 상황에서도 시스템이 정상 동작해야 한다는 것이다. 여기서 시스템이 정상 동작한다는 것이 언제나 최신 데이터를 보장하거나 에러가 아닌 값을 준다는 것이 아니다. 그것은 C 와 A 가 보장하는 것이고 partition 상황에서도 partition이 아닌 상황과 같은 것을 보장하면 P를 보장한다고 할 수 있다. 근데 여기서 partition은 정말 네트워크 레이어에 문제가 생겨 물리적으로 다른 망이 구성되는 상황을 말하는 것이 아니다. partition은 일부 메시지가 전달되지 않는 상황도 포함된다. 이는 분산환경에서 매우 흔히 발생하는 일이고 P 를 포기한다는 것은 결국, 분산 환경을 포기한다는 말이 되기 때문에 분산 데이터 스토리지를 만들 때는 결국 CP 와 AP 중 하나를 선택해야 한다. 개인적으로 생각하기에 CP 와 AP 중 구현하기 더 어려운 것은 CP 라고 생각된다. 모든 노드가 언제나 같은...

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는 리더를 ...