[Hyperleder Fabric ] Leader election in RAFT, Gossip

사실 Leader election 은 가장 단순하게는 주변 노드들의 이름을 리스트로 가지고 있다가, 이름 순으로 그 다음 노드가 그냥 리더가 되는 느낌으로 구현하면 매우 단순하긴 한데, (Distributed Systems 책들에 소개되는 수준의 Bully algorithm, Ring algorithm 등은 실용적으로 사용하기에는 다소 심플하다.) Split brain 때문에 Term(epoch) 단위 동안에 가장 다수의 투표를 받은 노드가 선출되는등의 기술(?) 이 들어가며 복잡해지곤 하며...문제를 완벽히 해결하기가 쉽지는 않다. 아래 글에서는 하이퍼레저 패브릭상에서 발생되는 2가지 주요 분산합의 상황에서의 리더 선출에 관해 대략적으로 끄젹 꺼려 보겠다. 

* 이 문서는 앞으로 실제 패브릭 구현 상에서의 알고리즘으로 꾸준하게 수정 될 예정이다.

Gossip Protocol 

(gossip protocol 은 주변에 랜덤하게 자신이 가진 최신 정보를 뿌려주고, 랜덤으로 선택된 피어에게 최신 정보를 요청하는 주로 push-pull 모델을 이용하여 전체 네트워크의 상태를 일치시키는 알고리즘이다. 이때 최신정보는 항상 리더로 부터 시작된다. 리드 선출에 관해 공개된 상세한 정보는 없으며, 코드를 봐야 이해 할 수 있다. 공식문서에는 그냥 static으로 설정하거나 dynamic으로 설정 할 수 있다 정도~)

- 상태는 Leader , Follower 2가지이다.
- ID 문자열의 사전상 순서로 우선순위를 가진다. 
- term id , epoch id 란 개념이 없다. 
- 하나의 membership view에서는 하나의 리더를 가진다.
- 네트워크가 분리되면 분리 된 수 만큼 리더를 가지며, (각자 orderer에게 블록 요청) 합쳐지면 하나로 돌아 온다.
- Leadership declaration (내가 리더다) 와 Proposal (내가 리더가 되고 싶어) 메세지가 있다. 
- Leadership declaration (내가 리더다) 를 주기적으로 보내며, 이것을 못받은 Follower는 리더선출에 돌입하며, 이렇게 네트워크는 분리된다..나중에 더 낮은 ID를 가진 노드에서 Leadership declaration 받게되면 리더 자리를 물러나게 되며 자연스럽게 네트워크는 합쳐진다.

 Startup():
 	wait for membership view to stabilize, or for a leadership declaration is received
      or the startup timeout expires.
	goto SteadyState()

// 3 possible ways to stabilize
//   - After a period of time, check whether the number of peer lists before and after is consistent.
//     if they are consistent, it indicates stability.
//   - If a leader is elected, it's also stable
//   - Otherwise if timeout, consider it stable and vote for new leader from proposal set


 SteadyState():
 	while true:
		If leaderKnown is false:
 			LeaderElection()
		If you are the leader:
			Broadcast leadership declaration
			If a leadership declaration was received from
 			a peer with a lower ID,
			become a follower
		Else, you're a follower:
			If haven't received a leadership declaration within
 			a time threshold:
				set leaderKnown to false

 LeaderElection():
 	Gossip leadership proposal message
	Collect messages from other peers sent within a time period
	If received a leadership declaration:
		return
	Iterate over all proposal messages collected.
 	If a proposal message from a peer with an ID lower
 	than yourself was received, return.
	Else, declare yourself a leader

 

RAFT

RAFT도 위와 조금 비슷하긴 한데 차이점은 우선순위(ID문자열 기준)가 없고, Term (epoch) 이라는 1씩 증가하는 공통적으로 공유하는 상태가 있으며 Candidate 상태가 추가 되었다. 특히 RAFT은 Gossip에 비해 split brain 문제를 방어하기 위해서 좀 더 복잡 한 면이 있으며, 리드선출 기간이 피어마다 랜덤하게 설정되서 먼저 자기를 투표해 달라고 하는 놈이 있으면 그 놈에게 그냥 투표해 주기 때문에 결국 그 피어가 리더가 될 확률이 높아진다. 과반수로 부터 표를 받으면 자기가 리더인것을 확정짓고 리더로써의 하트비트를 날려 주게 된다. 만약 운이 안좋아서 비슷한 시간에 2개의 피어가 후보자가 될 경우, 표를 과반 수 이상 못받으면 다음 Term으로 넘어간다. 즉 split brain이 발생하지 않는다. (비잔틴은 없다라고 가정한다) 

두가지 타임아웃이 있다:  heartbeat timeout (리더), election timeout (팔로워) heartbeat타임아웃은 election timeout보다 주기가 짧아야한다. election timeout은 그보다 큰 제한하에  각 노드별로 랜덤값 

1. When is it started 

     - 리더로 부터 정해진 시간안에
       정식 메세지 , 하트비트 ,  candidate 로 부터의 vote 메세지중 아무것도 못받은 경우   

2. How to elect leader 

     -  리더로 부터 아무것도 못받은 각 못받은 노드는 자신의 election timeout (노드별 랜덤) 이 발생하면 상태를 candidate로 변경하고 term + 1하고 스스로에게 투표한후 나머지 follower들에게 투표를 요청 한다.
     -  election timeout  이 발생되지 않은 follow 노드는 투표를 해 준다. ( 동일 term에 한해 1표, Candidate는 다른 Candidate에게 투표 안함) 
     - follower는 투표해주고 election timeout을 리셋한다. (term도 갱신된다) 
     - 과반수의 투표를 받으면 상태를 leader로 바꾸고 리더 역할을 한다. 
     - 과반수를 못받으면 다시 투표를 요청한다.
     - election timeout이 거의 비슷한 노드가 동시에 candidate 되었을 경우 발생 할 수 있는 split brain 에서 과반수를 받은 candidate가 없어서 leader가 선출이 안됬을 경우, re election을 진행해서 랜덤하게 새로 정해진 (term 마다 항상 새로 선정됨) election timeout을 기반으로 다시 leader 선출을 진행한다. 이때 follower 중 하나가 election timeout이 빨리 도달하면, 기존 candidate를 재치고 term+1을 통해 리더가 될 수도 있다. 
     - term이 높은 메세지가 오면 follower로 돌아간다. 

http://thesecretlivesofdata.com/raft/
 
리더 선출에 대한 간단히 표로 정리 해보았다.

 

 

페이스북 :  엔터프라이즈 블록체인 그룹