Dynamo: Amazon’s Highly Available Key-value Store — 요약

DeCandia et al. (Amazon, SOSP 2007) · DOI 10.1145/1294261.1294281
원본 레퍼런스: 02_Dynamo_원본 · 읽기리스트: 09_논문_읽기리스트 #2

1. 배경 — “장바구니는 절대 멈추면 안 된다”

아마존 규모에서는 항상 어딘가 장애가 나 있다(디스크·노드·네트워크 분할). 장애를 예외가 아니라 상시 상태로 전제.
핵심 요구: “Always writeable” — 쓰기(장바구니 담기)는 어떤 상황에서도 거부되면 안 됨. 가용성이 최우선.
그래서 CAP 중 AP(가용성 + 분할내성) 를 선택하고 강한 일관성(C)을 포기 → 대신 최종 일관성(Eventual Consistency).
대상 워크로드: 대부분 키 기반 단순 조회/저장(관계형 쿼리·조인 불필요). SLA를 평균이 아니라 99.9 백분위로 관리.

2. 설계 원칙

점진적 확장성(Incremental scalability) — 노드 한 대씩 추가/제거
대칭성·분산성(Symmetry, Decentralization) — 마스터 없음, 모든 노드 동등 → SPOF 제거
이질성(Heterogeneity) — 성능 다른 노드가 능력만큼 부하 분담

3. 핵심 기법 (문제 → 해법)

문제	해법
데이터 분산·확장	Consistent Hashing(링) + 가상 노드(virtual node)로 부하 균등·이질성 대응
고가용성 쓰기	복제(N개 노드) + 링에서 시계방향 N개에 저장
버전 충돌	Vector Clock(벡터 시계)로 인과관계 추적. 자동 병합 불가 시 충돌을 읽기 시점에 애플리케이션이 해결(예: 장바구니 합집합)
일관성 vs 지연	정족수 (N, R, W) — `R+W>N`이면 읽기가 최신 반영. 아마존은 흔히 N=3
일시 장애	Sloppy Quorum + Hinted Handoff — 원 노드가 죽으면 대신 받아뒀다가 복귀 시 넘겨줌(쓰기 계속 성공)
영구 장애·복제본 동기화	Merkle Tree로 anti-entropy(차이 나는 범위만 비교·동기화)
멤버십·장애 감지	Gossip 프로토콜(분산 전파)

4. 왜 중요한가 (아키텍처적 가치)

NoSQL·분산 스토리지 설계 패턴의 원류. Cassandra, Riak, Voldemort 등이 직접 계승.
“일관성을 애플리케이션에 위임한다”, “가용성을 위해 최종 일관성을 받아들인다”는 설계 철학의 전환점.
Consistent Hashing·Vector Clock·Quorum·Hinted Handoff·Merkle Tree·Gossip — 분산 시스템의 표준 도구상자를 한 논문에 집약.

5. 한계·트레이드오프

최종 일관성 → 읽기가 옛 값을 볼 수 있고, 충돌 해결 부담이 애플리케이션으로 넘어감.
키-값 모델 → 복잡한 질의·트랜잭션엔 부적합.
벡터 시계는 노드 수 많아지면 크기 관리(절삭) 필요.

연결

대비: 01_Raft_논문_요약 — Raft는 강한 일관성(CP) 지향. Dynamo는 정반대 축(AP).
CAP·최종일관성·Quorum → 학습 로드맵 03_DB_데이터엔지니어링 §2(NoSQL·분산 DB).
Consistent Hashing·Gossip → 07_백엔드_실시간시스템 분산 패턴.