Amazon Dynamo 논문 핵심 기술: Partitioning부터 Hinted Handoff까지

이 글의 출발점은 Amazon의 2007년 논문 **“Dynamo: Amazon's Highly Available Key-value Store”**를 읽으며 적어 둔 핵심 기술과 용어다. 먼저 이름부터 분명히 해야 한다. 논문의 Dynamo는 Amazon 내부에서 운영한 분산 key-value store이고, 오늘날 AWS가 제공하는 완전관리형 서비스 Amazon DynamoDB와 동일한 제품이나 공개 구현 명세가 아니다.

따라서 consistent hashing, vector clock, sloppy quorum, hinted handoff를 현재 DynamoDB의 내부 구현이라고 단정해서는 안 된다. 이 글에서는 논문에 공개된 Dynamo의 설계를 설명하고, 마지막에 현재 DynamoDB에서 확인할 수 있는 공개 API 경계와 나눠 본다.

Dynamo가 풀려던 문제

쇼핑 카트처럼 쓰기를 거절하기 어려운 서비스에서는 일부 node나 network가 실패해도 요청을 계속 받아야 한다. Dynamo는 단순한 key-value interface, 점진적 scale-out, 낮은 latency, 높은 availability를 목표로 하고, 일부 failure scenario에서는 즉시 강한 consistency보다 availability를 선택했다.

이 선택을 가능하게 한 축은 다음 여섯 가지다.

1. partitioning: key space를 node에 나눈다.
2. replication: 한 key를 여러 node에 복제한다.
3. versioning: 동시에 갈라진 update의 인과관계를 추적한다.
4. membership: cluster에 참여하는 node와 token 정보를 공유한다.
5. failure handling: 일시 장애 중에도 요청을 받을 우회 경로를 둔다.
6. recovery와 scaling: 복제본 차이를 고치고 node 증감 시 범위를 재배치한다.

Consistent Hashing과 Virtual Node

Dynamo는 key를 hash ring의 위치로 보내고, ring을 시계 방향으로 돌며 만나는 node에 저장 책임을 부여하는 consistent hashing 계열 partitioning을 사용했다. 논문 구현에서는 MD5 결과의 128-bit space를 ring으로 보았다. MD5가 여기서 맡는 일은 password 보안이 아니라 key를 identifier space에 배치하는 hash다.

단순히 node 하나에 ring 위치 하나만 주면 장비 성능 차이와 node 증감에서 load imbalance가 커질 수 있다. Dynamo는 실제 node 하나가 여러 token, 즉 virtual node를 맡게 해 다음을 조절했다.

• node 추가·제거 시 여러 구간에서 load를 조금씩 옮긴다.
• 물리 node의 capacity 차이에 따라 token 수를 조절할 수 있다.
• failure와 recovery의 부하를 여러 node에 분산한다.

‘consistent hashing은 data 이동을 최소화한다’는 말은 완전히 이동이 없다는 뜻이 아니다. hash function, token 배치, replica 수, workload의 key 분포가 실제 균형을 좌우한다.

Replication과 Preference List

각 key는 coordinator만 갖지 않고 ring의 여러 node에 복제된다. 설정한 replication factor를 N이라고 할 때 coordinator는 failure domain까지 고려한 preference list에서 replica node를 선택한다.

읽기와 쓰기는 각각 R, W개의 response를 기다리는 방식으로 latency·availability·consistency trade-off를 조정할 수 있다. R+W>N 같은 quorum 조건은 version이 겹칠 가능성을 높이지만, network partition과 sloppy quorum, concurrent write가 있는 Dynamo를 단순한 ‘항상 최신값 보장’ 공식으로 바꾸지는 않는다. conflict를 어떻게 검출하고 합칠지가 함께 필요하다.

Vector Clock과 Read Reconciliation

Dynamo는 object version에 vector clock을 붙여 update 사이의 causal relationship을 판단했다.

• 한 version이 다른 version의 history를 포함하면 더 오래된 version을 버릴 수 있다.
• 서로 어느 쪽도 포함하지 않으면 concurrent branch로 남는다.
• 갈라진 version은 read 과정에서 함께 반환될 수 있고 application이 의미에 맞게 reconcile한다.

쇼핑 카트라면 두 branch의 item을 합치는 정책을 생각할 수 있지만, 삭제나 수량처럼 의미가 충돌하는 domain에서는 단순 union이 정답이 아니다. version vector는 conflict를 찾는 정보이지 business rule을 대신하는 자동 merge가 아니다.

Sloppy Quorum과 Hinted Handoff

정상 replica가 일시적으로 응답하지 않으면 strict한 preference list만 기다리는 대신, 접근 가능한 다른 node가 임시 replica 역할을 맡을 수 있다. 이때 원래 어느 node로 돌려줘야 하는지 hint를 함께 저장하고, 대상 node가 회복하면 data를 전달한다. 이것이 hinted handoff다.

이 방식은 일시 장애 중 write availability를 높이지만 공짜가 아니다.

• 임시 replica에 data가 얼마나 쌓였는지 관찰해야 한다.
• 장기 장애에서는 storage pressure와 recovery traffic이 커질 수 있다.
• 여러 version이 생기면 read repair나 application reconciliation이 필요하다.

Merkle Tree와 Anti-Entropy

replica는 장기간 서로 달라질 수 있다. 모든 object를 매번 전송해 비교하는 대신 key range의 hash를 tree로 요약한 Merkle tree를 사용하면, root에서 시작해 hash가 다른 branch만 내려가며 불일치 범위를 좁힐 수 있다.

Merkle tree가 data를 스스로 복구하는 것은 아니다. 어느 범위가 다른지 효율적으로 찾아 state transfer 대상을 줄이는 구조다. token assignment가 바뀌면 tree를 다시 계산해야 하는 비용도 논문에서 다룬다.

Gossip-based Membership과 Failure Detection

node들은 gossip protocol로 membership과 token 정보를 퍼뜨린다. 한 node의 관찰만으로 다른 node를 cluster에서 영구 제거하지 않고, 요청을 보낼 때 local failure detector의 판단을 사용했다. 일시적인 packet loss와 영구 membership change를 같은 사건으로 처리하지 않기 위한 선택이다.

이 구분은 운영에서도 중요하다. ‘응답이 늦다’, ‘현재 요청 경로에서 도달하지 않는다’, ‘cluster 구성에서 제거해야 한다’는 서로 다른 판단이다.

Dynamo 논문과 현재 DynamoDB를 섞지 않는 법

확인 대상	2007 Dynamo 논문	현재 DynamoDB 공개 문서
성격	Amazon 내부용 분산 key-value store 설계	AWS가 운영하는 serverless 완전관리형 NoSQL 서비스
partitioning	hash ring·token·virtual node 공개	partition key를 내부 hash function에 넣어 partition 결정
consistency	tunable N/R/W, version conflict와 reconciliation	API별 eventual·strong read와 transaction 제공
운영	service가 자체 Dynamo instance 운영	partition 관리·복제·장애 처리를 AWS가 관리

현재 DynamoDB 설계를 할 때는 논문의 내부 기법을 추측하기보다 access pattern, partition-key 분포, item size, consistency option, capacity·quota를 AWS 문서에서 확인해야 한다. 논문은 분산 시스템의 trade-off를 이해하는 자료이고, 서비스 문서는 실제 계약이다.

원문을 영어 문장과 함께 다시 읽을 때는 Amazon Dynamo 논문 영어 문맥 노트로 이어갈 수 있다.

다시 확인할 질문

Consistent hashing만 쓰면 hotspot이 사라지나

아니다. 특정 key에 traffic이 몰리면 hash space가 고르게 나뉘어도 hot key가 생긴다. key cardinality와 request distribution을 별도로 봐야 한다.

Vector clock이 conflict를 자동으로 해결하나

아니다. causal order를 비교해 sibling version을 식별하는 데 도움을 주지만, 어떤 값을 남길지는 application semantics가 결정한다.

DynamoDB도 vector clock과 hinted handoff를 쓰나

AWS가 공개한 현재 DynamoDB의 제품 계약과 내부 구현을 구분해야 한다. 공개 문서에 근거가 없는 내부 mechanism을 2007년 Dynamo 논문에서 그대로 추론하지 않는 것이 안전하다.

참고 자료

• Dynamo: Amazon's Highly Available Key-value Store
• Werner Vogels, Amazon's Dynamo
• AWS DynamoDB Core Components
• AWS DynamoDB Read and Write Operations