# 분산 시스템(Distributed Systems) 이란? 분산 시스템은 공유하는 공동의 목표를 달성하기 위해 여러 개의 개별 컴퓨터 노드의 리소스를 활용하는 컴퓨터 프로그램의 모음입니다.

# 분산 시스템(Distributed Systems) 이란? 분산 시스템은 공유하는 공동의 목표를 달성하기 위해 여러 개의 개별 컴퓨터 노드의 리소스를 활용하는 컴퓨터 프로그램의 모음입니다. 이를 통해 단일 컴퓨터로는 감당하기 힘든 데이터의 처리나 저장등을 수행할 수 있고 SPOF(single point of failure) 를 제거할 수 있습니다. 대표적으로 하둡, spark, kafka, zookeeper 등과 같은 빅데이터 관련 솔루션들이 해당되며 RDBMS와 NoSQL 솔루션 중에도 분산 시스템으로 운영되는게 많이 있습니다. # 분산 시스템에서 리더를 선출하는 이유 각 노드의 리소스를 효율적으로 활용하려면 각 노드의 상태를 알고 상황에 맞게 각 노드에 데이터를 서빙하거나 잡을 할당해주기 위한 고민이 필요하다. 혹은 현재의 분산 시스템의 상태를 기록하거나 특정 작업에 대해 각 노드가 공유되야할 필요성이 있을 경우 이를 일관성있게 유지하기 위한 고민도 필요하다. 대부분의 분산 시스템에서 리더를 선출하는 방식을 택하여 이런 고민을 해결했고 이를 통해 분산 시스템의 효율성을 높이고 조정을 최소화하며 아키텍쳐를 단순화 시켰다. # 리더 선출 알고리즘의 분류 크게 동기식과 비동기식으로 나눈다. 동기식은 동시에 동기화가 진행되고 예측 가능한 시간과 순서로 메세지를 보낸다. 이로 인해 리더 선출 프로세스의 안정성(consistency)과 활성(liveness)을 모두 보장할 수 있다. 하지만 확장성이나 규모가 큰 시스템에 적용하기엔 한계가 있다. 비동기식은 이와 반대로 확장성이나 규모가 큰 시스템에도 적용이 가능하지만 동기화 진행이나 메세지가 전달되는 순서를 예측하기 힘들고 메세지가 유실될 수도 있다. 또한 리더 선출 프로세스의 안정성과 활성을 모두 보장할 수 없기 때문에 주로 안정성을 보장하는 방향으로 구현되는 경향이 있다. # 1. Bully 가장 간단한 동기식 알고리즘이다. 이 알고리즘은 각 노드에 고유한 숫자 ID 가 있어야 하고 각 노드가 클러스터로 묶인 모든 노드들의 ID 를 알고 있어야 한다. 리더 선출 프로세스는 매우 단순하다. 가장 높은 ID 값을 가진 노드가 리더가 된다.(나이가 깡패라는 말이 있듯이 ID 가 깡패(bully)인 알고리즘으로 이해) 단순한 만큼 사용하기 쉽지만 그만큼 단점도 있다. 가장 높은 ID 값을 가지고 있는 노드가 불안정하면 그만큼 리더 선출이 자주 발생하게 되고 이는 클러스터를 자주 다운시키는 결과를 발생하게 만든다. 또한 동기식 알고리즘의 특성상 클러스터가 커지고 물리적으로 분산될 경우 메세지 동기화를 유지 관리하기 힘들수 있다. # 2. Paxos 신뢰할 수 없는(실패하거나 네트워크 이슈가 있을 수 있다는 것을 가정) 서버 혹은 프로세서의 분산 시스템에서 복제본 일관성을 보장하는 합의 프로토콜로 비동기식 리더 선출에 사용된다. 여담으로 이 프로토콜이 처음 사용된 가상의 입법 합의 시스템이 그리스의 Paxos 라는 섬에서 사용되어 이 섬의 이름을 따왔다고 한다. Paxos 는 아래와 같은 2 Phase Commit 단계를 통해 합의를 도출해낸다. - 준비 단계(Prepare phase) : 제안자는 변경과 관련된 일련번호를 생성하고 이에 대한 메세지를 replica(다른 노드)에 전송한다. 메세지를 받은 노드는 해당 변경사항에 대해 이전에 받았던 번호보다 높으면 이를 수락한다. - 커밋 단계(Commit phase) : 모든 노드가 메세지를 수락하면 제안자는 모든 복제본에 Commit 요청을 보내고 변경 사항은 모든 노드에 비동기적으로 반영된다. Paxos 는 이론이 다른 알고리즘에 비해 어려워 구현이 까다롭지만 안정성 보장을 중요시하기 때문에 일반적으로 내구성이 요구되는 곳(예: 파일 또는 데이터베이스를 복제하는 곳)에 사용된다. # 3. Raft Raft는 이해하도록 쉽게 설계되어 상대적으로 이론이 어려운 Paxos 의 대안으로 비동기식 리더 선출에 사용되는 알고리즘이다. 현재 Kafka 에서 Zookeeper 와 헤어질 결심(?)을 하고 준비중인 KRaft 가 이 Raft 알고리즘을 내포하고 있다. Raft 상에서 서버 노드는 Follower, Candidate, Leader 로 정의된 상태 중 하나를 가지게 되고 아래와 같은 과정으로 Leader 가 선출된다. 1. 모든 노드는 Follower 상태에서 시작한다. 특정 Follower 에서 Election Timeout(Follower 가 Leader 로 부터 AppendEntry 를 오랫동안 받지 못했을 경우 발생하는 Timeout) 이 발생하면 해당 Follower 는 Candidate 상태가 되어 새로운 선거 기간(Term)을 시작한다. 2. Candidate 노드는 자신에게 투표하고 다른 Follower 들에게 자신에게 투표해줄것을 요청(RequestVotes RPC) 한다. 3. Follower 가 투표 요청에 정의된 선거기간(Term)에 투표한 적이 없다면 곧바로 Candidate 에게 응답(Vote)하여 투표를 행사합니다. 4. 과반수 이상의 투표 응답을 받은 Candidate 는 Leader가 된다. Raft 동작과 관련되어 좀더 자세하게 알고싶으신 분은 http://thesecretlivesofdata.com/raft/ 를 참고해주세요. # 4. ZAB ZAB(Zookeeper Atomic Broadcast)은 이름에 나와있듯이 Zookeeper 에서 사용하고 있는 비동기식 리더 선출을 위한 프로토콜이다. 리더 선출 뿐만 아니라 복제 순서 보장 및 노드 복구 관리에도 사용되기 때문에 지금의 Zookeeper 를 있게 한 장본인이라 해도 과언이 아니다. ZAB 프로토콜은 Zookeeper 에 특화되어 설계되었기 때문에 Zookeeper 외에 다른 솔루션에서 사용하고 있는 사례는 없는거로 알고 있다. ZAB 프로토콜을 통해 리더를 선출하는 방법은 의외로 간단하다. Leader 가 없는 상태가 되었을 경우 각 노드들은 특정 sequential 을 생성하여 모든 노드에게 자신의 sequential 을 전파한다. 이때 가장 낮은 sequential 을 생성한 노드가 Leader 로 선출되고 나머지 노드들은 Follower 가 된다.