분산 시스템에서 장애는 예외가 아니라 일상이다. 디스크가 고장 나고, 네트워크가 끊기고, 서버가 재시작된다.
Amazon Dynamo는 2007년에 발표된 분산 key-value 저장소로, “항상 쓰기 가능(Always Writeable)“을 핵심 원칙으로 삼는다. 데이터는 안정 해싱(Consistent Hashing)을 통해 링 구조로 배치된 노드들에 분산되며, 각 키는 N개 노드에 복제된다. 이 N개 노드 목록을 선호 목록(Preference List)이라 한다. 읽기/쓰기 성공에 필요한 최소 응답 수를 각각 R, W로 정의한다.
이 글에서는 Dynamo가 노드 장애 상황에서도 서비스를 멈추지 않기 위해 사용하는 기법들을 다룬다.
먼저 생각해볼 것
3대의 서버에 데이터를 복제하고 있는데(N=3), 1대가 죽었다. 쓰기를 실패시켜야 할까?
전통적인 접근에서는 “정해진 멤버가 응답해야 한다"고 본다. 하지만 Dynamo는 다르게 생각한다. “노드 하나가 죽었다고 쓰기를 실패시키는 건 과하다.”
전통적 정족수(Quorum)와 한계
분산 시스템에서 정족수(Quorum)란, 읽기/쓰기가 성공하려면 최소 몇 개의 노드가 응답해야 하는가를 정의하는 것이다.
N=3, W=2 (쓰기에 2개 노드 응답 필요)
선호 목록: [A, B, C]
노드 A가 다운이면? B와 C에만 쓸 수 있다. C까지 느리면 W=2를 충족하지 못해 쓰기가 실패할 수 있다.
전통적 quorum은 정해진 멤버에게만 써야 하므로, 멤버가 죽으면 가용성이 떨어진다.
Sloppy Quorum: 살아있는 노드에 대신 쓰기
Dynamo의 핵심 아이디어다. 선호 목록의 노드가 죽었으면, 링을 따라 살아있는 다음 노드에 대신 써서 W를 맞춘다.
예제
Dynamo의 노드들은 해시 링 위에 배치되어 있다. 키를 해싱하면 링 위의 한 지점이 나오고, 시계 방향으로 가장 먼저 만나는 N개 노드가 그 키를 담당한다.
N=3, W=2, R=2
링: A → B → C → D → E → F → (다시 A)
키 cart#123의 선호 목록: [A, B, C]
A가 다운이면?
- 전통적 quorum: B, C에만 쓸 수 있다. C까지 느리면 실패 가능성이 높아진다.
- Sloppy quorum: 링을 더 돌아서 D에 대신 쓴다. 쓰기 성공.
전통적 quorum: Sloppy quorum:
A(죽음) B C A(죽음) B C D
X ✓ ? X ✓ ? ✓ (대리)
→ W=2 위험 → W=2 충족!
A와 C가 동시에 죽었을 때도 마찬가지다. 전통적 quorum에서는 W=2를 맞출 수 없어 무조건 실패지만, Sloppy quorum에서는 B + D(또는 E)에 써서 성공시킨다.
Hinted Handoff: 임시 위탁과 복구
Sloppy quorum으로 D에 “대신 저장"할 때의 문제가 있다. D는 원래 이 키의 레플리카가 아닌데, 나중에 A가 살아나면 어떻게 할까?
D에 데이터를 저장할 때 힌트(hint)를 같이 붙인다.
D에 저장되는 레코드:
- 값: {apple, banana}
- 버전: [A:3, B:2]
- hint: "원래 수신자 = A" ← 이것이 핵심
A가 복구되면?
- D가 주기적으로 A의 상태를 확인한다
- A가 살아났으면 D에서 A로 데이터를 전송한다
- 전송 성공 후 D에서 hinted copy를 삭제한다
임시로 맡아두었다가 원래 자리로 돌려놓는 것이다. Hinted handoff가 끝나면 데이터는 최종적으로 원래 선호 목록인 [A, B, C]에만 존재하고, D의 임시 복사본은 사라진다.
영구 장애 해결: Anti-Entropy
Hinted Handoff만으로는 부족한 경우가 있다.
- A가 오랫동안 다운되거나
- D가 A보다 먼저 죽어버리거나
- 일부 업데이트가 일부 노드에만 반영되거나
이런 영구 장애 상황에서는 레플리카 간 데이터를 직접 비교해서 동기화해야 한다. 이것이 Anti-Entropy(반엔트로피)이고, 이를 효율적으로 하기 위해 Merkle Tree를 사용한다.
Merkle Tree 구조와 동기화
두 노드 A, B가 같은 키 범위를 들고 있을 때, 데이터가 일치하는지 확인하려면?
단순한 방법: A의 모든 키-값을 B에 보내서 비교한다. 데이터가 많으면 네트워크 비용이 폭발한다.
Merkle Tree: 해시 트리를 만들어서 루트 해시만 비교하면 전체가 같은지 즉시 판단할 수 있다. 다르면 트리를 내려가며 다른 부분만 찾는다.
트리 구조
키가 8개 있다고 하자.
ROOT
/ \
H1234 H5678
/ \ / \
H12 H34 H56 H78
/ \ / \ / \ / \
h1 h2 h3 h4 h5 h6 h7 h8
각 리프(h1~h8)는 키 값의 해시다. 부모 노드는 자식 해시들을 합쳐서 다시 해시한 값이다.
H12 = hash(h1 + h2)
H1234 = hash(H12 + H34)
ROOT = hash(H1234 + H5678)
동기화 과정
- A의 ROOT와 B의 ROOT를 비교한다
- 같으면 완전히 동일하다. 끝.
- 다르면 한 단계 내려가서 왼쪽/오른쪽 중 어느 가지가 다른지 찾는다
- 반복해서 내려가면 결국 다른 리프(키)만 찾아서 그 키의 데이터만 전송한다
전체를 보내지 않고, 다른 부분만 고친다. 비교 횟수는 O(log N) 수준이므로 데이터가 아무리 많아도 효율적이다.
동기화 예시:
노드 A의 트리 노드 B의 트리
[abc123] [abc123] ← ROOT 같음 → 동기화 불필요!
노드 A의 트리 노드 B의 트리
[abc123] [xyz789] ← ROOT 다름
/ \ / \
[aaa] [bbb] [aaa] [ccc] ← 오른쪽이 다름
/ \
→ 이 가지만 내려가서 비교
멤버십 관리: 가십 프로토콜
Dynamo는 노드 추가/제거를 관리자가 명시적으로 수행한다. 하지만 모든 노드가 현재 멤버십 상태를 알아야 요청을 올바른 노드로 라우팅할 수 있다.
이 정보를 전파하는 방법이 가십 프로토콜이다.
- 매 초마다 랜덤 노드를 골라 멤버십 정보를 교환한다
- 시간이 지나면 모든 노드가 같은 상태로 수렴한다
관리자가 X를 추가
→ X: "나 추가됐어"
→ X가 Y에게 전달
→ Y가 Z에게 전달
→ ... 결국 전체가 알게 됨
즉시 전파되지는 않는다. 시간이 지나면 결국(eventually) 전체가 알게 된다. 이것 역시 최종 일관성 철학이다.
노드 추가 시
새 노드 X가 추가되면 링 위의 토큰(위치)을 배정받고, 해당 키 범위를 기존 노드들이 X에게 전송한다. 안정 해싱(Consistent Hashing)의 장점으로, 전체 키가 아니라 X가 맡게 될 일부 키만 이동한다.
장애 감지: 글로벌 합의 없이 로컬 관점으로
Dynamo는 글로벌 합의 기반 장애 감지를 하지 않는다.
- A가 보기에: B가 내 요청에 응답하지 않으면 “내게 죽음"이다
- 다른 노드가 B와 잘 통신하고 있어도 상관없다
- 목적이 “요청 라우팅"이기 때문이다
글로벌 합의(모든 노드가 “B는 죽었다"에 동의)는 통신 비용이 크고, 네트워크 파티션 상황에서 합의 자체가 불가능할 수 있다. Dynamo의 탈중앙 철학에도 맞지 않는다. 그래서 로컬 관점으로 충분하다고 판단한 것이다.
장애 처리 종합 테이블
| 장애 유형 | 기법 | 동작 방식 | 특징 |
|---|---|---|---|
| 일시적 장애 | Sloppy Quorum + Hinted Handoff | 살아있는 다음 노드에 대신 저장, 복구 시 원래 노드로 전송 | 쓰기 가용성 유지 |
| 영구적 장애 | Anti-Entropy + Merkle Tree | 레플리카 간 해시 트리를 비교해 다른 키만 동기화 | O(log N) 비교, 네트워크 효율적 |
| 멤버십 변경 | 가십 프로토콜 | 매 초 랜덤 노드와 정보 교환, 전체가 eventually 수렴 | 중앙 서버 불필요 |
| 노드 장애 감지 | 로컬 관점 감지 | 내 요청에 응답하지 않으면 “내게 죽음” | 글로벌 합의 비용 없음 |
모든 기법의 공통점은 중앙 집중 없이 동작한다는 것이다. Dynamo의 탈중앙 설계 원칙이 장애 처리에도 일관되게 적용되어 있다.