이번에 BOJ가 서비스 종료되면서, 어떻게 알고리즘 역량을 어필할 수 있을까 생각하다가, 이전부터 실력이 늘었을 때 보고싶던 PCCP가 적절할 것으로 판단해서 시도했다.

레벨 3도 안나올 것 같았는데, 체감 레벨은 마지막 문제를 제외하곤 2레벨 수준이었던 것 같았다.

좀 많이 아쉬운 점은 정말 조금만 더 잘했다면... 레벨 4가 되었을 것 같은데 아쉽게도 3레벨이 나온 점...

4문제에서 3솔을 정확히 하면 750점이 될 것 같았는데, 히든 케이스를 발견하지 못했던 것 아닐까 예상해본다...

RAFT

클러스터란?

RAFT에 설명하기에 앞서 클러스터 용어의 설명이 선행되어야 합니다. 클러스터(Cluster)는 여러 대의 서버(노드)가 하나의 시스템처럼 동작하도록 구성된 집합체입니다.

이를 통해 시스템은 장애 발생 시에도 서비스를 지속할 수 있는 고가용성(HA) 과 데이터 일관성을 보장할 수 있습니다.

RAFT 란?

RAFT(Raft Consensus Algorithm) 는 분산 시스템에서 여러 노드 간 데이터 일관성과 합의를 유지하기 위한 리더 선출 기반의 합의 알고리즘으로 리더 선출과 로그 복제를 통해 일관성을 확보합니다.

클러스터 내 노드는 리더(Leader)와 팔로워(Follower)로 구분되며, 리더는 주기적으로 하트비트(Heartbeat) 신호를 전송하여 팔로워의 상태를 모니터링하고 클러스터의 정상 동작을 유지합니다.

리더 선거

리더는 주기적으로 하트비트를 전송하여 팔로워의 상태를 점검합니다.

팔로워 노드는 리더로부터 일정 시간(ex: 150~300ms) 하트비트 메시지를 받지 못하면 리더 장애로 판단하고, 스스로 후보자(Candidate)로 전환한 뒤 새로운 리더를 선출하는 텀이 시행 됩니다.

텀은 리더 선출하는 임의의 기간으로, 각 후보 노드 중 과반수 표를 받으면 리더 선출이 완료됩니다.

리더 선출이 성공적으로 완료되면 새 리더가 조정하는 정상적인 운영을 진행합니다.

로그 복제

리더는 클라이언트의 요청을 로그 형태로 기록하고, 이를 모든 팔로워에게 복제합니다. 과반수의 팔로워가 로그를 수신·저장했다는 응답을 보내면 리더는 해당 로그를 커밋(Commit) 하며, 커밋된 로그는 모든 노드에 동일하게 적용되어 클러스터의 데이터 일관성을 유지합니다.

RAFT를 왜 사용하는가?

RAFT를 사용하면 다중 환경 시스템에서 클러스터 내의 고가용성을 보장하기 편리하기 때문입니다.

예를 들어 MongoDB의 Replica Set 구조에서는 데이터를 저장할 때 리더에 최초 저장, 이후 팔로워가 리더의 데이터를 참고해서 복제하는 방식으로 동작합니다. 이 때 팔로워는 복제(Replication)되었기 때문에 백업 서버로 활용될 수 있으며, 고가용성(High Availability)을 위한 교체 서버로 활용할 수 있기 때문입니다.

RAFT 합의 알고리즘 실 사용 사례

다양한 곳에서 RAFT 합의 알고리즘을 활용함

• IBM MQ
• MongoDB
• RabbitMQ
• Apache Kafka (KRaft)

데이터베이스 다중화

데이터베이스 다중화란?

데이터베이스 서버를 여러 대 배치해 다양한 목적을 달성하기 위한 방법입니다.

다중화 목적

• 고가용성(High Availability)
  • 사용 기법 : 클러스터링, 페일오버
• 데이터 백업
  • 사용 기법 : 리플리케이션
• 성능 확장(Scalability)
  • 사용 기법 : 스케일 아웃

따라서 상기 목적을 위해 데이터베이스는 어떻게 다중화 되는지 알아보겠습니다.

고가용성(High Availability)

고가용성이란, 장애가 발생하더라도 서비스가 끊기지 않도록 보장하는 것을 의미합니다.

데이터베이스에서 자주 거론되는 SPOF(Single Point of Failure, 단일 장애 지점) 문제도 결국 고가용성을 충족하지 못해 발생하는 문제입니다.

특히 OLTP(Online Transaction Processing) 환경에서는 매 순간 사용자 요청이 발생하기 때문에 데이터베이스가 단 한번이라도 멈추면 서비스 전체에 심각한 영향을 끼칩니다. 이 문제를 방지하기 위해 다음과 같은 방식이 활용됩니다.

• 클러스터링(Clustering) : 여러 대의 서버를 하나의 그룹처럼 묶어 운영하여, 특정 노드가 장애를 일으키더라도 다른 노드가 역할을 이어받도록 하는 방식
• 페일오버(Failover) : 마스터 서버가 장애를 일으켰을 때 자동으로 대기 서버를 마스터로 승격시켜 서비스 연속성을 유지하는 방식

실 사용 예시 : PostgreSQL Patroni, MySQL InnoDB Cluster

데이터 백업 리플리케이션(Replication)

데이터를 안전하게 보관하고, 동시에 읽기 부하를 분산하기 위해 리플리케이션(Replication) 기법이 활용됩니다. 리플리케이션은 한 서버에 기록된 데이터를 다른 서버로 복제하는 방법입니다.

리플리케이션의 주요 형태는 다음과 같습니다.

• Master-Slave Replication: 하나의 마스터 서버가 쓰기 연산을 처리하고, 복제된 슬레이브 서버들이 읽기 연산을 담당합니다. 읽기 성능 확장에 유리합니다.
• Master-Master Replication: 두 개 이상의 서버가 동시에 쓰기를 처리할 수 있는 구조입니다. 하지만 충돌 관리가 필요하기 때문에 구현이 까다롭습니다.

또한 리플리케이션은 데이터 동기화 방식에 따라 나뉩니다.

• 동기(Synchronous): 모든 Replica에 데이터가 반영될 때까지 트랜잭션 완료를 기다림 → 데이터 일관성 ↑, 성능 ↓
• 비동기(Asynchronous): Master에만 쓰기를 완료한 뒤 Replica는 나중에 반영 → 성능 ↑, 데이터 손실 위험 존재

이러한 특성 때문에 리플리케이션은 단순 백업 목적뿐 아니라, 읽기 전용 트래픽 분산과 재해 복구(Disaster Recovery) 에도 널리 활용됩니다.

실 사용 예시 : MySQL Replication, MongoDB Replica Set

성능 확장(Scalability): 샤딩과 스케일 아웃

서비스 사용자가 늘어나면 데이터베이스에 저장되는 데이터 양과 요청 처리량도 함께 증가합니다. 이를 해결하기 위해 데이터베이스는 수직 확장(Scale Up) 또는 수평 확장(Scale Out) 을 필요로 하며, 수평 확장의 가장 대표적인 방법이 샤딩(Sharding) 입니다.

• 수직 확장(Scale Up): 데이터베이스 서버의 하드웨어 장비를 더 좋은 장비로 교체하는 방법이므로 다중화와는 관련 없습니다. 또한, 수직 확장에는 한계가 있기에, 수평 확장이 도입된 것으로 볼 수 있습니다.
• 수평 확장(Scale Out): 기존 서버의 성능을 높이는 대신, 여러 대의 서버를 추가해 병렬로 운영하는 확장 방식입니다. 샤딩은 스케일 아웃의 구체적인 구현이라고 볼 수 있습니다.
• 샤딩(Sharding): 데이터를 특정 기준(예: 사용자 ID, 지역 등)에 따라 여러 서버에 분산 저장하는 기법입니다. 각 샤드는 전체 데이터의 일부만을 담당하므로, 개별 서버의 부하를 크게 줄일 수 있습니다.

실 사용 예시 : MongoDB Sharding, Cassandra

마무리

데이터베이스 다중화의 목적에 따른 특성을 요약했을 때

• 장애 대응을 위해서는 고가용성
• 안전한 데이터 보관과 읽기 성능 향상을 위해서는 리플리케이션
• 대규모 트래픽과 데이터 처리를 위해서는 샤딩

위와 같은 목적에 따른 기법이 생기는데, 무조건 데이터베이스 다중화 방식을 채용하는 것은 잘못하면, 오버 엔지니어링이 될 수 있습니다.

따라서 데이터베이스 다중화는 운영중인 서비스에 알맞는 스케일의 아키텍처를 설계하는 것이 가장 좋을 것으로 생각됩니다.