🧐 합의 알고리즘과 Raft 가 무엇인지 알아보자.

합의 알고리즘 ? Raft ?

Raft 는 합의 알고리즘 중 하나다. 합의 알고리즘은 분산 시스템 분야에서 자주 볼 수 있는 용어다. 우리가 일상에서 사용하는 그 '합의'의 의미가 맞다. 그럼 누가 합의를 한다는걸까? 바로 프로그램끼리 합의를 하는 것이다.

이게 무엇

분산 시스템은 하나의 목표를 달성하기 위해 여러개의 서버가 참여하는 시스템이다. 이 때의 목표는 '확장성 있고 안전한 DB가 되는 것', '대량 메세지를 유실하지 않고 보내는 것' 등이 된다. 그러니까 몽고DB, 레디스 등의 클러스터 모드, 카프카 클러스터 등 '클러스터'가 들어가는 시스템이나 쿠버네티스처럼 여러 대의 서버를 관리하는 시스템에서 합의 알고리즘이 사용된다. 이 분산 시스템에 참여하는 서버 하나하나를 노드라고 하자. 노드의 형태는 다양하다. 물리 서버가 될 수도 있고, 가상머신에 띄운 서버가 될 수도 있고, 쿠버네티스 pod 으로 띄운 서버가 될 수도 있다.

이걸 대체 어디다 쓰나요?

이제 누가 합의하는지는 알았다: 분산 시스템의 노드끼리! 그럼 무엇을 합의한다는걸까? 예시를 통해 알아보자.

노드 3개로 이루어진 데이터베이스 클러스터가 있다. 사용자가 보내는 읽기, 쓰기 요청은 모두 하나의 노드 - 리더 노드라고 하자 - 에서 처리한다. 나머지 두 개는 그 노드에 장애가 생겼을 때를 대비한 백업용으로, 데이터 복제만 수행한다. 사용자가 쓰기 요청을 보내면 리더 노드가 그 요청을 읽어들이고, 데이터를 수정한 다음 나머지 두 개 노드에게 복제 요청을 보낸다. 백업용 노드들은 복제 요청을 받아서 자신의 데이터를 수정한다. 그러다가 리더 노드에 문제가 생겨서 통신이 되지 않는 상황이라면 백업용 노드들은 남은 둘 중 누가 리더 노드의 역할을 임시로 맡을 것인지 결정해야 한다.

위 예시에서 노드 3개로 이루어진 데이터베이스 클러스터가 있다. 를 제외하고 모두 합의가 이루어진 상황이다. 즉, 사용자의 요청을 어떤 노드가 처리할 지, 리더 노드가 누구인지, 새 리더 노드는 어떻게 정할 것인지, 클러스터에 살아있는 노드 목록은 무엇인지 등 시스템이 멀쩡하게 잘 돌아가기 위해 여러 노드 간 관계에 대한 모든 것이 합의의 대상이라고 할 수 있다. 합의 알고리즘이 분산 네트워크 시스템의 무결성을 지켜준다.

Raft 특)

정렬 알고리즘에 종류가 많듯이 합의 알고리즘도 여러가지가 있다. 사용자의 요청을 어떤 노드가 처리할지에 대한 방법만 해도 어떤 합의 알고리즘에서는 클러스터의 모든 노드가 요청을 처리하기도 하고, 또 다른 알고리즘에서는 하나의 노드에서만 처리하는 방식을 쓴다.

Raft 논문 읽기 시리즈에서는 이 논문을 바탕으로 Raft 알고리즘을 정리해 나가려 한다.

In Search of an Understandable Consensus Algorithm
(Extended Version) - By. Diego Ongaro and John Ousterhout
Stanford University

컴퓨터공학 이론 하나를 배울 때 먼저 그 이론이 ‘어떠한 정신을 기반으로 만들어졌는지’를 살펴보면서 다른 이론과의 차이점을 배우곤 한다. Raft 는 어떤지 알아보자.

Understandability

We had several goals in designing Raft: it must provide a complete and practical foundation for system building, (…) But our most important goal—and most difficult challenge—was understandability.
- 4. Designing for understandability

Raft의 1순위 미션은 ‘이해하기 쉬운 합의 알고리즘을 만드는 것’이다. 실제로 Raft 가 어떤식으로 돌아가는지를 알아보면, 알고리즘이 너무 복잡해지는 것을 막기 위해 여러 선택지 중 가장 단순한 방법을 선택해 문제를 해결하는걸 볼 수 있다.

Raft가 이렇게 단순함을 중요하게 여기는 이유는 Paxos 라고 하는 기존 합의 알고리즘 때문이다. Paxos 는 너무나도 복잡하기 때문에 제대로 이해한 사람이 몇 없었다. ‘그게 왜 문제냐? 알고리즘은 항상 어렵다!!’ 라고 생각할 수도 있겠지만 이렇게 되면 그 알고리즘을 실제로 써먹을 수가 없다는 문제가 생긴다. 대부분의 Paxos 구현체는 처음엔 그 알고리즘을 착실히 잘 구현하다가 점점 삼천포로 빠져서 끝에는 완전히 다른 무언가를 만들어내는 경우가 많았다고 한다. 결국 알고리즘이 이론으로만 남지 않고 효용이 있으려면 그 구현체를 만드는 사람이 알아먹을 수 있어야 한다는 것이다.

그래서 Raft 의 궁극적인 목표는 ‘이해하기 쉬운 합의 알고리즘을 만들어서 실제 분산 시스템을 만드는 데에 활용될 수 있게 하자!’가 되었다. 실제로 이 목표를 달성했다는 사실을 논문 마지막 부분에서 실험 결과를 통해 보여준다.

논문의 구성

논문은 총 12개 섹션으로 나뉜다. 위대하신 챗 gpt 의 힘을 빌려서 17장짜리 논문을 12문장으로 요약해보자.

들어가며

1. 서론: Raft는 분산 시스템에서 복제 로그를 관리하기 위해 이해하기 쉬운 합의 알고리즘으로 설계되었습니다.
2. 합의 알고리즘 요구 사항: 합의 알고리즘은 분산 시스템에서 안전성, 활발성, 그리고 장애 내성을 보장해야 합니다.

본격적으로 알아보기

3. Raft 개요: Raft는 합의를 리더 선출, 로그 복제, 안전성으로 나누어 일관된 분산 로그를 유지합니다.
4. 리더 선출: Raft는 투표 과정을 통해 로그 복제를 관리하고 시스템 일관성을 유지할 리더를 선출합니다.
5. 로그 복제: 리더는 로그 항목을 팔로워에게 복제하고, 커밋된 항목이 시스템 전체에 일관되게 적용되도록 보장합니다.
6. 안전성: Raft는 엄격한 리더 및 로그 관리 규칙을 통해 충돌하는 결정을 방지하여 안전성을 보장합니다.
7. 로그 압축: 로그 압축은 상태를 스냅샷으로 저장하고 오래된 로그 항목을 삭제하여 로그 크기를 줄입니다.
8. 클라이언트 상호작용: 클라이언트는 리더에게 요청을 보내며, 리더는 요청이 일관되게 처리되도록 보장합니다.
9. 클러스터 구성원 변경: Raft는 노드 추가 또는 제거와 같은 클러스터 구성원 변경을 진행 중인 작업을 방해하지 않고 처리합니다.
10. 선거 제한: Raft의 선거 제한 메커니즘은 타임아웃 및 기타 제어를 통해 표 분산을 방지하고 안정적인 리더 선출을 보장합니다.

우리가 이렇게 쩌는 알고리즘을 만들었다!^^

11. 구현 및 성능: Raft는 간단하게 구현되었으며, 실제 응용에서 강력한 성능과 신뢰성을 입증합니다.
12. 결론: Raft는 이해하기 쉽고 성능을 갖춘 합의 알고리즘으로, 실용적인 분산 시스템에 적합합니다.

이 중 눈여겨 볼만한 장은 [3. Raft 개요, 4. 리더 선출, 5. 로그 복제, 7. 로그 압축, 9. 클러스터 구성원 변경, 10. 선거 제한] 정도다. 이 장에서 Raft 의 동작 방식을 구체적으로 알 수 있다. [6. 안전성] 장에서는 Raft 가 이렇게 간단하게 동작해도 여러 엣지케이스를 다 커버할 수 있다는 사실을 증명한다. 즉, Raft 알고리즘의 무결성을 뒷받침하기 위한 장으로 보면 된다. [8. 클라이언트 상호작용] 에서는 Raft 를 사용하는 분산 시스템에 대한 클라이언트가 어떤 역할을 해야 하는지 알려주고 있다.

앞으로

Raft 알고리즘이 분산 시스템을 제대로 유지하기 위해 어떤 문제를 어떻게 해결하는지 알아보자. 다음 포스팅에서는 raft 알고리즘의 개요와 리더 선출 과정을 다룰 것이다.