DynamoDB의 뿌리인 “Dynamo: Amazon’s Highly Available Key-value Store”(2007)를 읽고 핵심만 정리했다. 이후의 수많은 분산 저장소(Cassandra, Riak 등)가 여기서 아이디어를 빌려왔다.
설계 철학: 가용성 우선
Dynamo는 “장바구니는 항상 담겨야 한다” 는 요구에서 출발한다. CAP에서 AP 를 택했다 — 네트워크 분할 상황에서도 항상 쓰기 가능(always writeable), 대신 일관성은 최종 일관성(eventual consistency) 으로 양보한다. 충돌은 나중에 해소한다.
일관된 해싱 + 가상 노드
데이터를 어느 노드에 둘지는 consistent hashing(링)으로 정한다.
- 노드 추가/제거 시 일부 키만 재배치 (전체 리해싱 회피)
- 노드마다 성능이 다르니 가상 노드(virtual node) 로 링에 여러 번 올려 부하를 고르게
복제와 preference list
각 키는 링에서 시계방향 N개 노드에 복제된다. 그 노드 목록이 preference list(장애 노드는 건너뛰어 물리적으로 서로 다른 노드로).
정족수 N / R / W
- N — 복제본 수
- R — 읽기 성공에 필요한 응답 수
- W — 쓰기 성공에 필요한 응답 수
- R + W > N 이면 읽기-쓰기 겹침이 보장(강한 일관성에 근접). 예: (3,2,2)
- W를 낮추면 쓰기 지연↓·가용성↑, R을 낮추면 읽기 지연↓
충돌: 벡터 클록
동시 쓰기로 버전이 갈리면 벡터 클록(vector clock) 으로 인과관계를 추적한다.
- 한쪽이 다른 쪽의 조상이면 자동 병합
- 진짜 동시(충돌)면 애플리케이션에 넘겨 화해(reconciliation) — 예: 장바구니 합집합
장애 대응
- Hinted handoff — 대상 노드가 죽으면 다른 노드가 대신 받아두고(hint), 복구되면 넘겨줌 → 쓰기 가용성 유지
- Merkle 트리 — 복제본 간 차이를 효율적으로 찾아 동기화(anti-entropy)
- 가십 프로토콜 — 멤버십·장애 정보를 노드끼리 전파(중앙 조정자 없음, 완전 분산)
정리
- AP + 최종 일관성, 항상 쓸 수 있게
- 일관된 해싱 + 가상 노드로 분산·확장
- N/R/W 정족수로 일관성-지연 트레이드오프 조절
- 충돌은 벡터 클록으로 추적, 화해는 앱이
- hinted handoff·Merkle·가십으로 장애를 견딘다
DynamoDB를 쓸 때 왜 그런 모델(파티션 키, 최종 일관 읽기 옵션 등)인지 이해하는 데 이 논문이 바탕이 된다.