합의(Consensus)
분산 컴퓨팅의 가장 어려운 과제 가운데 하나가, 바로 여러 대의 컴퓨터가 동시에 똑같은 결론에 도달하는 합의(consensus)를 이끌어내는 것이다.
Consensus에 대한 이야기는 나중에 하도록 하고.. 이를 실제적으로 구현한 알고리즘 가운데 가장 유명한 것이 Paxos 이다. 다만 Paxos의 경우에는 하나의 리더만이 값을 제안할 수 있기 때문에 효율성이 좀 떨어진다.
Mencius는 이러한 Paxos의 단점을 개량한 것이라고 할 수 있다. 이번 학기 기말 프로젝트 구현 과제이기도 하다. 그럼 Mencius-technical paper에서 나온 핵심적인 내용들을 요약해 보았다.
단일 합의(Simple consensus) 및 조정된 Paxos(Coordinated Paxos - CP)
Paxos에서는 리더만이 value를 제안할 수 있다. 하지만 좀 더 생각하면 이것은 꽤 비효율적이다. 연속적인 여러 개의 value가 commit 된다고 해 보자.. 하나의 리더만이 이것을 담당하는 것 보다 여러 개의 리더가 돌아가면서 이 value commit 을 처리하면 되지 않을까?
그래서 Mencius 에서는 여러 리더가 돌아가면서 propose를 담당한다. 이것을 효율적으로 달성하기 위해서, fail 혹은 false suspicion이 없다면 값을 제안할 때 특별히 딴지를 걸지 않는다.
Simple Consensus(SC)는 합의의 한 형태인데, 특히 서버의 종류에 따라 제안할 수 있는 값의 종류를 제한시켜두었다.
No-op : 이는 state machine command로서, 현재 상태를 그대로 놔두고 따라서 어떠한 응답을 요구하지 않는다.
아니, 아무것도 안하는 명령어라고? 그럼 어디다 써먹을까? 아이디어의 핵심은 조정자(coordinator)라고 불리는 특별한 서버만이 모든 명령어(no-op도)를 제안할 수 있고, 그 외의 서버들은 오직 no-op만을 제안할 수 있게 하는 것이다. 이를 하나의 SC로 보자. Mencius의 핵심은 이러한 SC를 "동시에 여러 개"운영하는 것에 있다. 그렇다면, instance 1에 대해서는 서버1이 Coordinator가 되고, instance 2에 대해서는 서버2가 coordinator 가 되게 된다. 하나의 머신이 여러 개의 인스턴스를 거느릴 수 있으므로, parallelization 효과가 나오게 되어 성능이 향상되는 것이다.
여하튼 하나의 인스턴스에 하나의 서버가 coordinator가 되고, 이의 선정은 다른 모든 server에게도 알려진다. 모든 서버가 value를 propose 할 수 있도록 다음의 조건들을 만족하자.
(1) 모든 서버는 무제한의 인스턴스들에 대한 coordinator 이다.
(2) 모든 서버 p에 대해, p가 제어하는 연속적인 인스턴스들 사이사이에 다른 서버들에게 인스턴스들이 할당된다. 근데 그 숫자는 제한된다. 즉,
p x x x x x p x x x x x p 이런 식인데 x의 숫자가 제한되어 있다고 보면 됨..
쉽게 말하면, cn + p 인스턴스가 서버 p에 할당된다고 보면 된다. 이 때 c는 상수이며, p ∈ {0, …, n-1} 이다.
SC를 사용하는 장점은 서버들이 스킵된 no-op들을 학습함으로서 대다수의 서버들이 이에 대해 합의할 필요가 없다는 것이다. 결과적으로, SKIP 메시지들은 단방향 메시지 딜레이의 학습 레이턴시만을 가지게 된다! 여기에 몇 가지 optimization 테크닉들을 추가하면 서버들이 제안하는 no-op을 매우 적은 비용으로 가능하게 한다. 이를 통해 클라이언트들의 다이나믹한 노드 및 네트워크 대역폭에 빠르게 적응할 수 있게 된다.
SC의 또 다른 장점은 비중재자가 제안하는 값을 제안함으로서, Mencius의 레이턴시를 제안하는 유연한 커밋 케터니즘을 구현할 수 있다는 것이다.
Paxos는 위의 SC를 구현한다. 뭐, SC가 Paxos의 간단화된 버전이니 이는 자명함..
그런데 Paxos를 통째로 쓰면 안되고, Coordinated Paxos(CP)라고 부르는 간략화된 버전을 쓰도록 하자. 각 인스턴스들은 CP를 운영하며, 모든 서버들은 중재자가 기본 리더인 것에 동의한다. 그리고 중재자가 일부 초기 round r 에서 Phase1을 수행하는 것에서부터 시작한다. 그리고 그 상태에서는, r보다 적은 round에서 받아들인 값에 대해서는 accept 하지 않기로 약속한다. (Liveness.. To make progress!)
Suggest : 중재자는 r 라운드에서 payload v를 담은 PROPOSE 메시지를 보내서 v를 제안할 수 있다. Fig 2에서 보면 Instance 0 이 그것이라고 할 수 있다.
Skip : 중재자는 r 라운드에서 PROPOSE 메시지에 no-op를 담아 자신의 턴을 skip 할 수 있다. Fig 2 의 Instance 1이 그것. 이 특별한 PROPOSE 메시지를 SKIP이라고 부른다.
이 때 모든 다른 서버들이 no-op만을 제안할 수 있기 떄문에, 중재자가 no-op를 제안하면 중재자로부터 SKIP 메시지를 받자마자 서버들은 no-op를 선택(chose) 할 수 있다. (Paxos에서는 이 단계에 이르기까지 합의하는데 여러 단계가 걸림을 명시하자. SC에서는 no-op 에 한해서 단번에 끝남.)
Revoke : 중재자가 실패했다고 의심이 갈 때, 일부 서버는 새로운 리더로 등극하게 되고 중재자가 value를 propose 할 권한을 가져오게 된다. 새로운 리더는 예전 중재자가 관리하던 SC를 종료시키기 위해 노력한다. 이 때, Paxos에서와 마찬가지로 새로운 중재자는 예전에 실패한 round r 보다는 큰 r' 로 새로 시작한다. (r'>r)
만약 Phase 1에서 값이 선택되지 않았다면, 새로운 리더는 Phase 2에서 no-op를 제안한다. 아니라면, Phase1에 의해 선택된 값을 제안하도록 한다. (즉 가급적 예전 값을 복구한다는 의미..)
이러한 suggest, skip, revoke는 Paxos에서 이미 존재하는 것들을 좀 더 특별화 시킨 것이다. 하지만 이렇게 함으로서 더 나은 구현을 가능하게 한다.
이를 구현한 중간 버전이 Protocol P 이다. 논문에서는 이에 대해 설명하고 있으며, 여기에 몇 가지 최적화 버전을 더 추가시킨 것이 Mencius 이다.
… 나머지 내용은 다음 시간에.. ^^
Posted by Sunghwan
