레이블이 consensus algorithm인 게시물을 표시합니다. 모든 게시물 표시
레이블이 consensus algorithm인 게시물을 표시합니다. 모든 게시물 표시

2018-05-27

2018년 21번째 주 - Consensus algorithm

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다.
 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다.

회사에서 이런 거 하느라 바빠서 한동안 다른 글은 읽을 시간이 없네요. 발표는 몇 주 동안 계속할 거라서 당분간은 발표자료 만들면서 참고했던 자료들을 공유할 것 같습니다.


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라는 용어의 어원이 된 논문이다. 이 논문 이전 논문은 기껏해야 메시지가 드랍되는 omission failure 정도밖에 가정하지 않았다. 하지만 이 논문 이후로 악의적인 참여자에 의해 시스템이 공격당하는 경우도 고려하게 됐다.

Reaching Agreement in the Presence of Faults

어떤 시스템이 f개의 byzantine failure node가 있을 때 3f + 1개의 노드로 구성된 네트워크에서 byzantine fault tolerant(a.k.a. BFT)한 합의가 가능하다는 것을 증명한 논문이다. 3f + 1은 BFT 시스템을 구성하기 위한 최소한의 노드 수이기도 하다.

Practical Byzantine fault tolerance

위 논문은 BFT 시스템을 Network File System에서 적용했다. 내가 아는 한은 BFT 알고리즘을 인터넷 규모에서 실제로 사용하는 시스템에 적용한 최초의 논문이고, 여기서 사용된 알고리즘들이 현재 블록체인에 사용되는 BFT 계열 합의 알고리즘들의 근간이 됐다.

Blockchain Consensus Protocols in the Wild

블록체인에서 유명한 합의 알고리즘들을 partial synchronous model에서 safety와 liveness, 그리고 얼마나 많은 byzantine failure node를 버틸 수 있는지 분석했다.

Byzantine Consensus Algorithm

텐더민트에서 사용하는 합의 알고리즘에 대해서 설명한 위키 페이지다. 텐더민트는 BFT에 stake 개념을 섞어 블록체인에서 사용할 수 있도록 만들었다. 특히 여기서 말하는 Proof of Lock Change(a.k.a. PoLC) 개념은 잘 이해해두는 것이 좋다. 보통 BFT 계열 합의 알고리즘을 최적화하려는 사람들이 PoLC에서 문제가 생겨 safety와 liveness에 문제가 생긴다.

Casper the Friendly Finality Gadget

현재 이더리움에서 진행 중인 프로젝트 중 하나로 PoW로 생성된 블록체인에 safety, 블록체인 용어로는 finality를 보장하기 위한 프로토콜이다. 기본적인 방법은 텐더민트에서 사용된 개념과 유사하다. 하지만 충분한 투표를 모으지 못하면 새 블록이 생성되지 않는 텐더민트와는 다르게 캐스퍼는 finality를 보장하지 못 할뿐 블록은 계속 생성된다.

Hot-Stuff the Linear, Optimal-Resilience, One-Message BFT Devil

캐스퍼에 영향을 받아 쓰인 논문으로 캐스퍼를 더 일반화시켰다. 캐스퍼는 블록 생성과 투표와 완전 별개로 진행된다. 하지만 Hot-stuff에서는 블록의 헤더에 투표를 모은다. 다만 이 투표는 반드시 포함해야 하는 것이 아니고 투표가 없어도 블록은 생성된다.

2018-05-24

Safety & Liveness - FLP impossibility으로 보는 블록체인

블록체인이 유행하면서 블록체인의 수만큼 다양한 합의 알고리즘이 나오고 있다. 이는 어째서일까? 애초에 왜 다양한 블록체인이 나오고 있는 것일까? 이는 근본적으로 합의 알고리즘이 무엇을 할 수 있고 무엇을 할 수 없는가에서 기인한다. 좋은 합의 알고리즘은 무엇을 보장해야 할까?

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는 언제나 더 어려운 문제를 푼 체인이 있으면 그 체인을 유효한 체인으로 판단한다. 즉, 지금 있는 체인보다 더 긴 체인을 만들 해시 파워만 있으면 언제든지 현재 합의된 블록을 다른 블록으로 대체할 수 있다. 이런 방식을 블록체인에서는 finality가 보장되지 않는다고 말하고 FLP impossibility에서는 liveness를 위해서 safety를 포기했다고 말한다.

Liveness를 중시하는 nakamoto consensus에서 출발한 합의 알고리즘들은 한정적인 상황에서 safety를 보장할 방법을 추가하는 방식으로 발전해갔다. 이더리움에서 구현되고 있는 Casper the Friendly Finality Gadget이 대표적이다. Casper는 기존의 PoW로 liveness를 보장하며 블록을 생성하지만 50 블록마다 투표하여 safety가 보장되는 지점을 만든다.

Safety over Liveness

이와 반대로 safety를 중시하는 합의 알고리즘도 있다. 전통적으로 분산 시스템에서 연구되던 PBFT에 기반한 BFT 계열 합의 알고리즘들이 이쪽에 속한다. Cosmos에서 사용하는 Tendermint가 대표적인 safety를 보장하는 BFT 알고리즘이다.

Tendermint는 하나의 라운드가 propose, prevote, precommit 3개의 단계로 나누어진다. 이 중 prevote와 precommit 스텝에서 각각 2/3+1개 이상 모아야 합의가 이루어진다. 합의에 2/3+1개 이상의 동의가 필요하기 때문에 어떤 상황에서도 서로 다른 두 블록이 동시에 생성되는 일은 없다. 하지만 전송한 메시지가 시간 안에 도달하는 것을 보장하지 못 하는 비동기 네트워크에서는 합의가 이루어지지 않아 블록이 생성되지 않을 수 있다. 따라서 liveness는 보장되지 않는다.

FLP impossibility가 증명했듯이 safety가 보장되는 경우 어떤 방법을 사용해도 비동기 네트워크에서 liveness를 보장할 수 없다. 그래서 BFT 계열에서는 다른 네트워크 모델에서 liveness가 보장됨을 증명한다.

비동기 네트워크 모델에서는 메시지가 전송되는 것이 보장되는 시간이 없다. 이는 메시지가 무한한 시간 후에 도착하는 것도 가정해야 하고 다시 말해서 전송한 메시지가 도착하지 않는 것을 가정해야 한다. 그렇다고 해서 정해진 시간 안에 메시지 전달이 보장되는 동기 네트워크 모델을 사용할 수는 없다. 이는 인터넷 규모의 네트워크에서는 비현실적인 가정이고, 이런 가정에서 liveness를 증명하는 것은 아무 의미 없기 때문이다. 그래서 tendermint는 정해진 시간 안에 메시지가 도달하는 것이 보장되지만 그 정해진 시간을 알 수 없다는 partial synchronous network model을 사용한다.

Partial synchronous network는 정해진 시간 내에 메시지가 도착하는 것이 보장되는 모델이다. 다만 이 정해진 시간이 무엇인지 노드는 알지 못한다. 이는 꽤나 현실적인 모델이다. 현실의 네트워크도 omission failure가 발생하지 않는 한 언젠가는 메시지가 도착하기 때문이다.

BFT 계열의 합의 알고리즘은 블록 생성을 위해 2번의 투표를 모아야 한다. 비록 partial synchronous network model에서는 언젠가 합의될 것이 보장되지만, 최악의 경우 몇번의 라운드 동안 새 블록이 생성되지 않는 경우도 생긴다. 이는 TPS 저하를 초래한다.

BFT 계열 알고리즘은 이런 문제를 해결하기 위한 방향으로 발전해왔다. 2018년 3월에 발표된 Hot-stuff이라는 프로토콜이 대표적이다. Hot-stuff에서 블록은 validator들의 투표를 포함한다. 이 투표를 commit-certificate(a.k.a. CC)이라고 한다. Hot-stuff은 기존의 BFT 계열의 알고리즘과 다르게 CC가 없는 블록도 생성될 수 있다. 그저 이 블록들은 finality가 보장되지 않을 뿐이다. 이 CC가 없는 블록들은 뒤에 CC가 있는 블록의 finality가 보장되면 그때 finality가 보장된다. 시간 당 블록 생성량을 올리기 위해서 safety를 어느 정도 포기하는 것이다.

마치며

이상으로 liveness의 극단에 있는 nakamoto consensus에서부터 safety에 극단에 있는 tendermint까지 블록체인에서 사용되는 다양한 합의 알고리즘을 알아봤다. 중요한 것은 safety와 liveness는 trade-off이지 둘 중 누군가가 더 우월한 특성은 아니라는 것이다. 자신이 구현하려는 서비스의 종류에 따라 safety와 liveness가 어느 정도 필요한지를 판단하여 알맞은 합의 알고리즘을 사용하는 블록체인을 선택해야 한다.

2018-02-21

Diffie-Hellman Key Exchange - 공개된 정보만으로 secret key 만들기

 네트워크상의 두 노드가 암호화된 통신을 하기 위해선 먼저 두 노드가 어떤 암호화 방식으로 어떤 키를 이용해서 암호화할지 합의해야 한다. 보통 암호화 방식은 사용하는 애플리케이션에 따라 고정된 방식을 사용하거나 두 노드가 처음 통신을 시작할 때 암호화하지 않은 패킷을 이용해 합의하거나 한다. 이후 패킷은 양쪽 노드밖에 모르는 암호키를 이용해 암호화할 것이기 때문에 암호화 방식은 암호화되지 않은 방식으로 합의를 해도 안전하다. 하지만 어떤 키를 사용할지는 암호화되지 않은 방식으로 합의해선 안 된다. 키가 공개되면, 이 비밀키를 이용해서 제삼자가 패킷을 위조할 수 있기 때문이다. 그렇다면 이 비밀키는 어떻게 안전하게 교환할 수 있을까?
 이에 대한 해답으로 나온 것 중 하나가 Diffie-Hellman key exchange(a.k.a. DH)다. 사실 이외에도 다른 방법들이 많이 있지만, 개인적으로 생각하기에 가장 범용적으로 안전하게 사용할 수 있는 것은 DH라고 생각한다. 또한, 이후 이것에 대해 많은 변종이 나왔지만, DH만 이해하면 나머지는 이해하는 데 별문제 되지 않는다. 그렇다면 DH는 어떻게 동작할까?

 우선 DH가 성립하기 위해서는 특별한 수학적 성질을 만족하는 generator가 필요하다. 이 generator는 하나의 입력을 받아 하나의 출력을 내뱉는다. 이 generator가 g라고 하고, 입력 x에 대해서 출력 Y를 내뱉는 Y=g(x)가 있을 때, x로부터 Y를 가지고 오는 것은 빠르고 쉽게 계산할 수 있지만, Y로부터 x를 가지고 오는 것은 어려운 일이어야 한다. 즉, 수학적으로는 역함수가 없는 함수여야 하고, 결괏값의 스페이스가 매우 커서 brute-force로 찾는 것이 매우 힘들어야 한다. 사실 이외에도 만족해야 할 수학적 성질이 여러 개 있지만 이번 포스팅에서는 그에 대한 설명은 생략하고 넘어가겠다.

 DH가 처음으로 제시한 방법은 generator로 modular exponentiation을 사용했다. modular exponentiation에서는 입력을 x라고 했을 때, 출력 Y를 다음과 같이 계산한다. Y:=bxmodm. 이때 bm은 적절한 수학적 성질을 만족하는 값으로, bm의 pair가 generator g가 된다.
 이후 여러 변종이 나왔고, 요새 많이 사용되는 것은 elliptic curve를 이용하는 Elliptic-curve Diffie–Hellman(a.k.a. ECDH)이다. 이 경우 사용하는 곡선의 종류가 generator g가 된다.

 어떤 generator를 사용할지 결정되고 나면 DH는 다음의 과정을 거쳐서 진행된다.


AliceBobEve
1GGG
2ab
3A=G(a)B=G(b)
4BAA, B
5s=B(a)s=A(b)

 우선 위의 표를 설명하자면, AliceBob은 서로 통신하기 원하는 사용자고, EveAliceBob 사이에 무슨 내용을 통신하는지 알기 원하는 도청자다. AliceBob은 공개된 공간에 있기 때문에 둘 사이의 통신하는 내용은 제삼자인 Eve도 알 수 있다. 그리고 위의 표에서 푸른색으로 표시된 문자는 자신이 생성한 데이터고, 붉은색으로 표시된 문자는 다른 사람이 생성하여 통신을 통해서 듣게 된 데이터다. 또한, 대문자와 소문자도 다른 의미를 가지는데, 대문자는 외부에 공개해도 되는 public 한 데이터고, 소문자는 자신만 알고 있어야 하는 private 한 데이터다. 따라서 붉은색 데이터는 모두 Eve도 알게 되고, 붉은색 데이터와 푸른색 데이터를 조합하여 AliceBob은 알지만, Eve는 모르는 데이터를 만드는 것이 DH의 목적이다.

1GGG

 우선 첫 단계는 어떤 generator를 사용할지 결정하는 단계다. generator를 결정하는 단계도 여러 방법으로 구현할 수 있지만 그다지 중요한 내용은 없으니 이번 포스트에서는 결정됐다고 가정하고 넘어가도록 하겠다.

2ab

 다음 단계에서 AliceBob은 각자 private key를 만든다. 이 private key를 어떻게 만드는가는 DH에서 중요한 요소가 아니지만, replay 공격을 막기 위해 private key는 랜덤하게 생성하는 것이 좋다.

3A=G(a)B=G(b)

 그리고 AliceBob은 generator G를 이용해서 각자 public key를 생성한다. 여기까지 진행되면 AliceBob은 자신의 private key와 public key만 알고 있고, Eve는 아무 키도 모르고 있는 상태가 된다.

4BAA, B

 다음 단계는 AliceBob이 각자 자신의 public key를 말하는 단계다. 이 단계를 지나면 AliceBob의 public key 두 개는 Eve를 포함한 모든 사람이 알고 있는 정보가 된다.

5s=B(a)s=A(b)

 다음 단계에서 AliceBob의 public key를 기반으로 generator를 만들어 자신의 private key를 사용하여 secret key를 만들고, BobAlice의 public key를 기반으로 generator를 만들어 자신의 private key를 사용하여 secret key를 만든다. 이때 public key를 사용해서 generator를 만드는 것은 어떤 generator를 사용하는가에 따라 다르다. modular exponentiation을 사용하는 경우 m는 기존의 generator의 m을 그대로 사용하고, 새로 받은 public key를 b로 사용한다. elliptic curve를 사용하는 경우 타원 곡선은 그대로 사용하고, public key를 시작점으로 계산한다.
 어쨌든 전달받은 public key를 기반으로 generator를 만들어 자신의 private key를 input으로 만들면, 그 결과 나온 secret key는 놀랍게도 AliceBob이 같은 값을 가지게 된다. 이는 아까 설명을 생략했던 generator의 몇 가지 수학적 성질 중 하나 덕분에 가능한 것이다. 이 secret key s를 알기 위해서는 최소 한 개의 private key가 필요하므로 Eve는 secret key s를 알 수 없다. 이제 AliceBob은 공유하지만, Eve는 모르는 값이 생겼으니, 이후 메시지는 전부 secret key s를 이용해서 암호화하면 된다.

 이상이 Diffie-Hellman Key Exchange를 이용하여 두 노드가 안전하게 비밀키를 만들어 공유하는 방법을 설명하였다. 사실 DH를 직접 구현해야 할 경우는 거의 없다. 하지만 네트워크 통신의 기본이 되는 내용이고, 많은 프로토콜이 컨넥션을 시작하는 단계에서 DH를 사용하기 때문에 서버 프로그래머라면 알아 두는 것이 좋다.

2017-12-20

Raft - electionTimeout

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이란, 한 노드에서 네트워크 안의 다른 모든 노드로 보낸 요청이 처리되어 응답이 오기까지 걸린 시간의 평균을 의미한다. 이 또한 MTBF와 마찬가지로 시스템의 고유한 속성이다. 하지만 숙련된 개발자나 비싼 하드웨어를 사용하여 올릴 수 있는 MTBF와는 다르게 broadcastTime은 물리적으로 최솟값이 정해진다.
 만약 electionTimeout을 잘못 설정하여 broadcastTime보다 작게 설정한다면, follower들이 leader의 heartbeat을 듣지 못하고 자신을 candidate으로 만들어 requestVote 메시지만 전송하고 아무도 leader로 선택되지 못 하고 시간만 허비하게 된다.

 Raft paper는 broadcastTime를 0.5 ms에서 20 ms 사이의 시간이 될 것을 가정하고 쓰여 있다. 따라서 다른 지역에 존재하는 서버 사이의 consensus가 아닌 한 지역에 존재하는 서버들 사이에서의 consensus를 위한 것이다. 만약 broadcastTime이 이보다 더 긴 네트워크를 구성했다면, electionTimeout도 더 길게 선택해야 한다.
 예를 들어 AWS를 사용할 때, 서울과 오레곤 사이의 latency는 평균 120 ms정도 걸린다. 따라서 서울 지역과 오레곤 지역에 양쪽에 설치된 서버 사이의 consensus를 위해서는 electionTimeout을 120 ms보다 더 크게 설정해야 한다.

2017-12-13

Raft - consistency

 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에 커밋 된 로그를 가지지 않은 노드가 leader가 되면 어떻게 될까? 다행히도 raft에서는 이런 일이 발생하지 않는다. RequestVote 메시지에는 candidate이 가지는 최신 로그의 index와 그 index가 생성된 term이 저장돼 있다. 이 index가 자신이 알고 있는 로그의 최신 index보다 작으면 이 RequestVote 요청은 거절된다. 즉, 가장 최신 로그를 가지고 있는 노드만 리더가 될 수 있고, 이 최신 로그에는 최소한 leader에 커밋 된 로그를 포함된다.

 그렇다면 leader를 포함하여 커밋 된 로그를 가진 노드가 모두 죽으면 어떻게 될까? Leader가 어떤 로그를 커밋했다는 것은 최소 과반의 노드가 이 로그를 가지고 있다는 것이다. 이 노드가 모두 죽었다는 것은 네트워크에 남은 노드가 절반이 되지 않는다는 것이고 새 candidate을 지지하는 노드가 절반 이하가 되기 때문에 새 leader를 선출할 수 없고 이후로 네트워크는 상태를 변경할 수 없다. 만약 네트워크에 과반의 노드가 살아있다고 하면, 이는 비둘기집 원리에 따라 커밋 된 로그를 가지고 있는 노드가 최소한 한 개 존재한다는 것이고, 이 노드가 leader가 되면서 consistency를 유지된다.

2017-12-08

Raft - log replication

 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는 AppendEntries에는 새로 추가할 log 이외에도 이미 follower가 저장했을 거라고 생각하는 prevLogIndex와 prevLogTerm을 같이 보낸다. Follower는 해당하는 index의 로그가 prevLogTerm일 경우 이 로그는 저장할 수 있는 로그다. 만약 prevLogIndex에 해당하는 log가 존재하지 않거나, prevLogTerm에 생성된 로그가 아니면 이 로그는 현재 leader가 가지고 있는 로그가 아니므로 유효하지 않다. 이 경우 prevLogIndex를 포함한 그 이후 모든 로그를 지우고 leader에게 저장할 수 없었다고 알린다. 그러면 leader는 전에 보냈던 index보다 작은 index의 로그를 포함하는 새 AppendEntries를 보낸다.

 Log를 저장할 수 있는 경우. 즉, prevLogIndex에 해당하는 로그를 가지고 있고, 이 로그가 prevLogTerm에 생성된 경우. follower는 leader가 보낸 로그를 저장하고 저장했다는 사실을 leader에게 알린다. 이때 follower가 이미 prevLogIndex 이후의 로그를 가지고 있었다면, 이 로그를 전부 지우고 leader가 보낸 로그로 덮어쓴다. 모든 state 관리를 leader에게 맡기고, leader의 state를 그대로 따르기 위해서다.
 Raft의 log replication은 leader가 commit 한 로그는 다음 term이 되어도 롤백 되지 않는 것을 보장한다. Term의 변경은 네트워크에 문제가 생겼을 때 발생하므로, 쉽게 말해 Raft는 CAP theorem에서 말하는 CP category에 분류된다. 이에 관해서는 다음 글에서 자세히 설명하도록 하겠다.

2017-12-05

Raft - leader election

 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이 더 최신인지 아닌지는 term과 lastLogIndex를 보고 결정한다.

 Term은 leader의 재임 기간이다. Leader가 바뀌면 term이 바뀐다. 하지만 모든 term에 leader가 존재하지는 않는다. Term은 단조 증가하는 숫자로 서버별로 자신의 term을 저장하고 있다. Raft에서 메시지를 보낼 때는 언제나 자신이 생각하는 term을 함께 보내고, 메시지를 받은 노드는 메시지에 들어있는 term과 자신의 term 중 더 큰 값을 자신의 term으로 만든다. 혹은 RequestVote를 보낼 때도 term을 증가시키고 보낸다.

 Message에 들어있는 term이 자신의 term보다 크다는 것은 candidate이 자신보다 더 최신의 상태라는 것이다. 따라서 자신의 상태를 바로 follower로 바꾸고 candidate을 지지한다는 응답을 보낸다. 이것은 자신이 leader였을 때도 마찬가지다. 이런 경우 네트워크 등의 문제로 다른 노드가 자신의 heartbeat을 듣지 못했다는 것이고, 이 경우 다른 노드들이 이미 state를 진행했을 수 있기 때문에 새 leader의 상태를 따른다. 반대로 요청의 term이 자신의 term보다 낮다면, 이 요청은 그냥 무시하면 된다.

 자신과 같은 term의 RequestVote 메시지가 메시지에 있는 lastLogIndex를 본다. lastLogIndex가 자신의 log index보다 작다면 이 candidate은 지지하지 않는다. 이는 partition 상황에서도 consistency를 유지하기 위함이다. 이는 다음에 log replication을 설명하며 자세히 설명하도록 하겠다.

2017-11-29

Raft - 이해하기 쉬운 consensus algorithm

 분산 시스템을 구축할 때, 모든 노드가 독립적으로 돌아가는 시스템을 설계한 것이 아니라면, 공유된 상태를 합의하기 위한 모종의 방법이 필요하다. 이런 식으로 분산 환경에서 상태를 공유하는 알고리즘을 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는 리더를 선출하여 모든 결정을 리더에게 위임하는 방법을 택했다. 이를 strong leader라고 하는데 덕분에 리더가 결정되고 나면 log replication은 매우 단순하게 진행된다. 이 leader election이 어떻게 되는지 다음 글에서 자세히 다뤄보도록 하겠다.