Consensus Algorithm
개요
Consensus Algorithm은 Distributed System을 구축할 때 사용하는 알고리즘이다.
Distributed System에서는 여러 노드들 간의 상태를 공유하기 위해서 합의하는 과정이 필요한데 이 때 사용되는 알고리즘이 바로 Consensus Alogrithm이다.
본 글은 Consensus Alogrithm에 대해서 알아보는 글이지만, 여기에 앞서 Distributed System의 정의에 대해서 확실히 하고 가는 것이 좋을 것 같다.
Distributed System
위키피디아에 Distributed System를 검색하면 다음과 같이 정의하고 있다.
분산 컴퓨팅(distributed computing)은 분산 시스템(distributed systems)을 연구하는 컴퓨터 과학의 한 분야로,
인터넷에 연결된 여러 컴퓨터들의 처리 능력을 이용하여 메시지를 하나에서 다른 하나로 보냄(message passing)으로써 거대한 계산 문제를 해결하려는 분산처리 모델이다.
출처 : 위키피디아
a,b는 분산 시스템 모델이며 c는 병렬시스템 모델이다.
차이는 c의 경우 shared memory를 통해 프로세서들이 정보를 공유하지만 a,b는 메시지를 통해 정보를 공유한다.
Distributed System과 MSA
최근 유행하는 MSA(Micro Service Architecture)는 Distributed System의 특정 종류의 한 예라고 할 수 있다.
MSA는 현대 소프트웨어 아키텍처이며 많은 기업들이 자신들의 시스템을 모놀리틱에서 MSA로의 전환을 시도하고 있다.
그렇다고 오해는 말자.
많은 기업들이 MSA로 전환하는 이유에는 여러 이유가 있지만 반드시 MSA가 모든 경우에서 합당한 정답이라는 것을 의미하지는 않는다.
지금도 전 세계 기업들에서 몇몇은 MSA를 도입했다가 다시 모놀리틱 서비스로 돌아오는 회사들도 더러 존재한다. (이 부분에 대해서도 나중에 포스팅할 기회가 있으면 하도록 하겠다.)
public 클라우드의 발전(AWS,GCP,Azure)과 맞물려서 도커,쿠버네티스같은 도구들이 등장했고 결과적으로 MSA가 유행하게 되었다.
Distributed System은 이러한 MSA의 근간이 되는 개념이며 많은 현대의 소프트웨어 아키텍처들이 이러한 분산 시스템을 적용하였다.
Distributed System의 문제점
Distributed System은 복잡한 연산을 여러대의 컴퓨터가 나누어 수행할 수 있기 때문에 다수의 컴퓨팅 파워를 이용해서 문제를 빠르게 해결할 수 있다.
그러나 Distributed System은 결국 여러 노드들이 하나의 상태를 가져야하는데, 이를 어떻게 합의할 것인지에 대한 문제가 발생한다.
이러한 문제를 해결하기 위해 분산 환경에서 상태를 공유하는 알고리즘이 등장했으니 이것을 Consensus Algorithm이라고 부른다.
Consensus Algorithm
Consensus Algorithm 중 가장 유명한 알고리즘은 Paxos이다.
하지만 Paxos는 구현은 커녕 이해하는 것 자체가 어렵기 때문에 이를 구현한 라이브러리가 거의 없었고 일부 분산 시스템들만 내부적으로 사용하는 정도라고 한다.
그나마 분산 시스템을 구축할 때 현실적으로 사용할 수 있는 방법이 Zab Algorithm정도 이다.
Zab Algorithm을 사용하는 대표적인 오픈소스가 바로 아파치 재단의 Zookeeper이다.
그러나 Zab Algorithm는 메시지의 순서가 보장되야하기 때문에 반드시 TCP를 사용해야한다는 점과 Zab Algorithm 자체가 Zookeeper의 구현과 엮여있다는 점에서 다른 구현을 만들기가 어려워 반드시 JVM을 띄워야한다는 문제가 있다.
Zookeeper
Zookeeper에 대해서 모르는 사람들을 위해 간략히 설명하자면, 아파치 재단의 프로젝트 중 하나이며 대용량 분산 시스템을 위해 사용하는 오픈소스이다.
Kafka라는 분산 스트리밍 플랫폼에서 Kafka Cluster를 구성할 때 이 Zookeeper를 사용한다.
그러면 Zookeeper는 어떻게 분산 시스템에서의 상태를 공유할까?
이때 아주 재밌는 방법을 사용하는데 곧 바로 뒤에서 언급할 Raft 알고리즘과 마찬가지로 Leader Election 과정을 수행한다.
Leader Election은 리더를 선출하는 과정을 의미하는데,
Zookeeper는 모든 노드들이 sequential을 생성하고 그 중 가장 작은 번호로 만들어진 노드가 Leader 노드가 되며 나머지 노드들은 Follower 노드가 된다.
선출된 리더는 다른 노드들을 관리하고 상태를 일관되게 유지하는 역할을 부여받게 된다.
당연히 리더 노드가 장애가 발생해서 죽으면, 다시 Leader Election을 통해 새로운 리더를 선출한다.
Raft Algorithm
구현체를 만들기 어려운 기존 Consensus Algorithm의 문제를 해결하기 위해 이해하기 쉬운 것을 최우선으로 설계된 Consensus Algorithm이다.
Raft Algorithm을 가장 쉽게 이해하는 방법은 아래의 링크를 보면 그림과 함께 Raft Algorithm에 대한 설명이 잘나와있다.
http://thesecretlivesofdata.com/raft/
귀찮은 사람들을 위해 간략하게 Raft Algorithm에 대해서 소개와 요약을 해보자면,
Raft 알고리즘은 분산 시스템에서 모든 노드들이 공통의 상태를 어떻게 쉽게 유지할 수 있는가?에 대한 고민을 쉽게 풀기 위해 등장한 프로토콜이다.
노드의 역할
Raft에서 노드들은 세 가지 상태를 갖는다. Leader와 Follwer 그리고 Candidate.
Leader와 Follwer는 주키퍼에서도 동일하게 봐왔지만 Candidate는 조금 색다르게 느낄 지도 모른다. 그러나 절대 어려운 개념은 아니다. Raft는 이해하기 쉬운 프로토콜을 지향하고 있으니까 말이다.
리더 선출 ( Leader Election )
우선 모든 노드들은 Follwer 상태로 시작한다.
만약 어떤 Follwer가 리더로부터 어떠한 요청도 듣지 않으면 그 노드의 상태는 Candidate 노드가 된다.
Candidate (후보자)는 다른 노드들에게 투표를 요청한다.
그리고 노드들은 그들의 표를 Candidate 노드에게 반환해준다.
과반수 이상의 표를 받은 Candidate 노드는 Leader 노드로 승격된다.
위와 같은 과정을 우리는 Leader Election이라고 부른다.
이것이 Raft의 리더 선출 과정이다.
로그 복제 ( Log Replication )
리더가 선출되면 모든 시스템 변경 사항은 리더를 통해 진행된다.
클라이언트가 리더의 상태를 변경하면, 리더는 해당 변경 사항을 노드의 Log Entry에 추가한다.
Log Entry는 커밋되지 않으면 노드 값을 업데이트하지 않는다.
Entry를 커밋하기 위해 노드는 먼저 Entry를 Follwer node들에게 복제한다.
그리고 나서 리더는 노드가 Entry를 쓸 때까지 기다리고 리더 노드에는 먼저 Entry가 커밋된다.
그 후 리더는 Follwer node에게 Entry가 커밋됐어 얘들아!라고 알리고 Follwer node 역시 Entry를 커밋한다.
이러한 과정을 거쳐 클러스터는 클라이언트의 응답에 일관된 상태를 갖게되며
Raft에서는 이것을 Log Replication이라고 부른다.
조금 더 구체적인 과정
그러면 조금 더 깊게 어떻게 위의 과정이 진행되는지 궁금한 사람은 http://thesecretlivesofdata.com/raft/ 이 강의를 꼭 보기를 바란다.
Reference
위키피디아 - Distributed System
https://blog.seulgi.kim/2017/11/raft-consensus-algorithm.html