[AWS] Dynamo: Amazon’s Highly Available Key-value Store

 

DynamoDB의 근간은 2007년 AWS에서 내놓은 Dynamo 논문에 기반을 둔다.

 

해당 논문을 읽어보고 간략하게 내용을 정리해보고자 한다.

 

주의

개인 학습을 위해 러프하게 읽어본 내용이라서 중간에 잘못 해석한 내용이 있을 수 있습니다.

 

간략하게 1회독 한 것이라서 정확하지 않습니다. 요약을 차차 수정할 예정이니 내용을 파악하고 싶다면 논문을 직접 보시는 게 좋습니다.

 

---

 

1. 서론 
아마존은 전세계급 서비스를 운용
이 논문에서는 Dynamo라 불리는 고가용성의 키벨류 저장소 시스템을 다룸 
즉 always-on이 가능하게 하는 서비스임 

토네이도 때문에 데이터 센터가 날아가거나 혹은 네트워크 장애가 발생하더라도 언제나 가용한 저장소 기술에 대한 니즈는 항상 있다. 

RDB의 일반적인 패턴은 비효율성을 가져왔다. 

반면 Dynamo는 간단한 primary key만 가능한 인터페이스를 제공한다.

Dynamo 
데이터는 consistent hashing에 의해 파티션화되고 repllicate 된다. 
그리고 consistency는 object versioning 이란 기술에 의해 가능하다. 
그리고 업데이트 상황에서의 replica 간의 consistency는 Quorum-like 라는 기술과 분산된 replica 동기화 프로토콜에 의해 가능하다. 
Dynamo는 gossip 기반 분산 실패 감지와 멤버십 프로토콜을 채택했다. 
Dynamo는 철저한 분산 시스템이고 관리 비용도 적다. 

Dynamo는 수년간 아마존의 e-commerse플랫폼의 핵심 기술이었다.
eventually-consistent한 스토리지 시스템이 어떻게 프로덕션에서도 잘 쓰일 수 있는지 보인다. 

2장에서는 배경을 소개 
3장에서는 연관 연구를 소개 
4장에서는 시스템 디자인을 소개 
5장에서는 구현을 소개 
6장에서는 실제 프로덕션에서 Dynamo를 사용한 경험을 소개 
7장은 마무리 

해당 페이퍼는 아마존의 디테일한 비즈니스를 숨기기 위해 대략적인 수치만 제공할 예정이다. 

2. 배경 
전통적으로 프로덕션 시스템은 상태를 RDB에 저장한다. 
하지만 RDB는 이상과는 꽤 동떨어진 솔루션이다. 
대부분 RDBMS의 복잡한 기능과 쿼리를 필요로 하지 않고 primary key접근이 대부분이었다. 
이 점은 낭비다. 
추가로 가능한 replication 기술이 제한적이었고 가용성 대신 일관성을 우선 재택하는 방식이라 좋지 않았다. 
기술이 발전한 상태지만 로드 밸런싱을 위한 영리한 스키마 파티셔닝이나 스케일 아웃은 아직도 쉽지 않았다. 

Dynamo는 위 부족함을 해결할 수 있다. 
간단한 key value 방식이며 고 가용성에 자원 사용에도 효율적이며 데이터 사이즈나 요청 증폭에도 쉬운 스케일 아웃이 가능하다. 그리고 Dynamo를 사용하는 각 서비스는 고유의 Dynamo 인스턴스를 돌릴 수 있다. 

2.1 시스템 가정과 요구사항 
위 같은 서비스를 위해선 아래 요구사항들이 필요하다. 

쿼리 모델 
고유한 키에 의한 간단한 아이템 read write 
상태는 고유 키에 의해 binary 옵젝트로 저장한다. 
관계 스키마는 필요없다. 
이렇게 하는 이유는 아마존 서비스에를 살펴본 결과 간단한 쿼리만이 대부분을 차지했기 때문이다. 
그리고 Dynamo는 작은 아이템을 저장하는 어플리케이션을 타킷으로 한다. (1MB보다 작은)

ACID 
아마존은 ACID를 보장하는 데이터 소토어는 종종 낮은 가용성을 보이는 것을 확인했다. (이건 업계와 학계 둘다에서 보인 증상)
Dynamo는 가용성이 높다면 consistency을 일부 희생하는 방식을 택했다. 
Dynamo는 isolation보장을 제공하지 않고 단일 키 업데이트만 제공 
 
효율성
시스템은 일반 하드웨어 infra에서도 잘 돌아야 한다. 
Amazon은 엄격한 latency기준이 있다. 일반적으로 99.9퍼센트 수준의. 
Dynamo는 이런 스루풋, latency요구 사항을 충족하도록 구성되야한다. 

기타 
Dynamo는 아마존 내부에서 쓰인다,. 
보안과 같은 요구 사항은 없어도 됨 

2.2 서비스 수준 합의 
클라이언트와 서비스는 납득할 수준의 latency등 서비스 수준의 합읠를 한다. 
SLA가 평균값을 의미한다면 누군가는 아주 좋지 않은 사용자 경험을 하게 될 수 있다. 
아마존은 최적화에 있어서 평균을 묵표로 하지 않았다. 
일부 쓰기 작업은 99.9퍼센트를 달성했다. 

2.3 디자인 고려사항
 상업 시스템에서 쓰이는 데이터 replication알고리즘은 보통 강한 일관성을 보장하기 위해 동기 replica를 사용한다. 이를 위해 가용성을 포기하곤 한다. 
예를 들어 불확실함을 해결하기 위해 이 데이터가 정화갛ㄹ때까지 아예 이용을 못하게 한다. 
네트워크 장애와 강한 일관성, 가용성등은 동시에 달성할 수 없다는 것이 널리 알려진 사실이다. 
서버나 네트워크에 붙어있는 시스템은 optimistic replication기술로 가용성을 높일 수 있다. 변경은 뒤에서 replica에 전파되고 일부 끊어지는 작업은 용인되는 것이다. 하지만 변경사항의 충돌이라는 문제도 있다. 
이 충돌 해결은 다음 두 가지 문제가 있다. 
언제 병합할건지? 
누가 병합할건지? 
Dynamo는 결과론적 consistent데이터 스토어로 디자인되었다. 
모든 변경은 결국 모든 replica에 도달한다. 
디자인 이슈 중 중요한 것은 언제 변경 충돌을 해결할 것인가다. read일때인지, write때인지, 
기존 데이터 저장소는 주로 write때 하고 read를 간단하게 유지한다. 
그래서 그런 시스템에서는 모든 replica에 write가 쓰이지 않으면 write를 거부한다. 
반면 
Dynamo는 언제나 쓰기 가능한 데이터 스토어를 위해 디자인되었다. 
쓰기 거절은 아주 좋지 않은 사용자 경험으로 이어진다. 
그래서 write 거절이 절대 일어나지 않음을 보장하기 위해 이런 충돌 해결 복잡도는 read로 미루게 되었다 .
다음 문제는 누가 충돌 해결 과정을 맡을가이다. 
데이터 스토어에 의해서, 혹은 애플리케이션에 의해 가능하다. 
데이터 스토어는 단지 last write wins전략을 택할 수 도 있다. 
만약 application이 데이터 스키마를 알면 적합한 해결책을 사용할 수도 있다. 
그러나 대부분 개발자는 그냥 데이터 스토어에 last write wins를 사용하게 하곤 한다. (아마 로직 복잡하고 귀찮으니까 이렇게 하는 듯 싶다.)

Incremental scalability 
Dynamo는 다른 시스템에 영향 주지 않고 확장할 수 있어야 한다. 

Symmetry 
Dynamo의 모든 peer는 동일한 책임을 가져야한다. 
특별한 힘을 가지는 노드가 없어야 한다. 
이런 symmetry은 프로비저닝과 유지를 단순하게 만든다. 

Decentralization: 
symmetry의 확장이다. 
디자인은 중앙 컨트롤 대신 분산 p2p 기술을 지향해야 한다. 
이전에 중앙 컨트롤은 정전을 유발했고 이걸 최대한 피해야한다. 

Heterogeneity: 
작접 분배는 서버 능력에 따라 적절히 분배되어야한다. 


3. 관련된 연구 
3.1 p2p 시스템 

p2p시스템의 첫 세대는 freenet과 gnetella다. 
Unstructured p2p 
임의의 대상과의 연결
서치 쿼리가 네트워크 전체로 퍼져나감
  
Structured p2p 
원하는 데이터가 있는 대상에게 서치 쿼리를 날림 

Pastry, Chord같은 시스템은 
라우팅 메커니즘을사용해서 몇 hops내 쿼리가 응답하도록 했다,.. 

또다른 p2p는 다중 라우팅 hop으로 인한 latency를 줄이기 위해 O(1) hop만을 허용한다. 대신 각 peer가 라우팅 정보를 충분히 local에 들고 있다. 

그래서 OceanStore, PAST같은 스토리지 시스템은 이런 라우팅위에 세워졌다. 


3.2 분산 파일 시스템과 데이터베이스 
성능, 가용성, 지속성을 위한 데이터 분산은 파일 시스템과 DB시스템에서 폭넓게 연구되었다.
p2p는 평면의 namespace만 제공하지만 분산 파일 시스템은 계층적 namespace를 제공한다. 
여러 논문이 존재한다. 
Dynamo는 신뢰할. 수 있는 네트워크에서 사용하기 때문에 security에 대해서는 자유로웠다. 
다양한 시스템과 비교해서 Dynamo는 아이템 사이즈가 작은 key value로 접근할 수 있는 간단한 애플리케이션을 위해 만들어졌다. 서버 fail에도 절대 update가 실패하지 않도록 고가용성에 모든 초점을 맞췄다. 
 

3.3 논의 
Dynamo는 always writeable에 초점을 맞췄다. 
Dynamo는 신뢰할 수 있는 도메인 위에 세워졌다 (AWS 네트워크를 말하는 것 같다. Managed service니까)
Dynamo를 사용하는 어플리케이션은 계층 namespae와 복잡한 쿼리를 필요로 하지 않는다. 
Dynamo는 수백 밀리sec내에서 99.9퍼센트의 read, write를 보장한다.
hop이 많으면 response time이 제각각이다. 그래서  
Dynamo는 0 hop DHT이다. 각 노드가 필요한 라우팅 info를 갖고 있다. 즉각 해당노드에 request하는 것이다. 



4. 시스템 아키텍쳐 
아래 주제에 대해 다룰 예정이다. 
파티셔닝
Replication
Versioning 
Membership 
Fail handleing 
그리고 스케일링
 
표 캡쳐하기 !! 

4.1 
Dynamo는 key에 MD5 hash를 적용해서 128비트 식별자를 만들고, 어느 storage노드가 담당할지 결정하게끔 사용한다. 

4.2 partitioning algorithm 
Dynamo는 증분확장해야하는 요구사항이 있다. 
그래서 동적으로 data를 파티션해야한다. 
여러 storage host의 로드를 분산하기 위해서 consistent hashing을 사용한다. 
Consistent hashing에서 출력은 ring이라는 circular space에 제한된다. 
무넺도 있다. 랜덤한 포지션 선정은 data가 고르게 들어가지 못할 수도 있다. 
둘째는 알고리즘이 노드 성능의 서로 다름을 신경쓰지 않는다. 

각 노드는 ring에서 하나가 아니라 여러 포인트에 할당된다. 이걸 위해 virtual node개념을 쓴다. 
각 노드는 하나 이상의 virtual node는 담당한다.
 
Virtual node장점
1. 노드 하나가 fail되면, 이 노드에 의해 관리되던 부하는 나머지 노드에 고르게 분산된다. 
2. 노드가 다시 가용해지면 혹은 새 노드가 추가디ㅗ면 , 
노드는 다른 노드들과 거의 비슷한 부하를 수용한다. 
3. 노드가 수용가능한 virtual node 개수는 
물리 인프라 머신의 용량에 따라. 다르게 할 수 있다. 


4.3 Replication 
Dynamo는 여러 곳에 replicate한다. 
coordinator라는 개념은 키를 N-1 노드에 시계 방향으로 복ㅈ한다. Node B는 키를 C, D에 복제하고 동시에 자신도 local에 저장한다.  

키를 담당하는 노드의 리스트를 preference list를 사용한다. 

4.4 data versioning 
Dynamo는 eventual consistency를 사용한다. 
update가 모든 replicat에 적용되지 않았더라도 응답을 반환한다. 
쇼핑 카트에 최신 리스트가 불가용하고 과거 버젼에 아이템을 담는다면 여러 버젼이 생기고 이걸 나중에 통합한다. 
이런걸 보장하기 ㅜ이해서 모든 수정을 불변인 버젼으로 만든다. 
여러 버젼의 object가 동시에 나타나는 걸 허용한다. 
대부분의 경우 새 버젼이 이전 버전을 포함하곤 한다. 
그래서 시스템은 그걸 가장 확고한 버젼으로 여긴다,. 
(Syntactic reconciliation)

그러나
 버전 분기는 실패 속 동시 업데이트 속에 있을 수도 있다. Object 버젼의 충돌을 만든다. 이 경우 시스템은 동일 object에 대한 여러 버젼을 통합할 수 없다. 그래서 클라가 여러 브랜치를 통합해야한다. (Semantic reconciliation)

Dynamo는 같은 오브젝트에 대한 다른 버젼을 해결하기 이ㅜ해 vector clock을 사용한다. 
(Node, counter)페어의 list다. -> vector clock 
하나의 벡터 클락은 오브젝트의 모든 버전과 연관되어있다. 

분기되면 두 개의 vector clock버젼이 생긴다. 
이때 이걸 합치게 되면 두 분기의 수정사항 모두가 추가된 vector clock이 할당된다. 
그러면 계속 네트워크 fail나면 이 vector clock list가 엄청 길어지는 거 아닐까 ? 
그래서 마지막으로 노드가 아이템을 업데이트한 시간을 timestamp로 기록한다. 그리고 만약 vector clock list가 일정 크기를 넘어서면 가장 오래된 clock을 삭제한다. 그런데 이게 조상 관계를 정확히 유추하지 못할 수도 있다록 하는데, 프로덕션 환경에서는 문제가 없어서 철저하게 조사되지는 않았다고 한다. 


4.5 get() put() 동작 
Read, write를 담당하는 노드는 coordinator라 부른다. 
Read, write는 첫 N개의 건강한 노드가 담당한다. 
시스템 consiostency를 위해 
Quorum system에 있는 consistency protocol을 사용한다. 
 R -> 성공적인 read에 가담해야할 최소 node 수 
W  -> 성공적인 write에 가담해야할 최소 node 수 

Quorum-like system = R + W > N 인 시스템 이다. 
이 모델에서 get은 가장 느린 R개의 replica에 의해 latency가 결정된다. 그래서 R, W는 주로 N보다 작게 잡는다. 
put때는 vector clock이 생성되고 로컬에 저장된다,. 그리고 새 버젼을 N개의 근접한 node에 보낸다. 만약 적어도 W-1개의 노드가 응답하면 write는 성공이다. 

똑같이 get은 preference list에 있는 인접 N개의 노드에 모든 존재하는 버전을 요구한다. 

4.6 실패 관리 : Hinted Handoff 
Dynamo는 강력한 quorum membershipo을 강요하진 않는다. 대신 sloppy quorum을 사용한다. 

만약 특정 노드가 죽으면 다른 노드에게 replica가 가고, 해당 노드가 다시 살아나면 그곳으로 다시 간다. 
Hinted handoff 덕분에 Dynamo는 read ,write가 ㅇ리시 장에에도 동작함을 보장한다. 


고가용성이 보장되야 하는 application은 W를 1로 하면 된다. 1개에만 저장되면 바로 응답하는 것이다. 

4.7 Handling permanent failures: Replica synchronization 
replica사이에 불일치를 빠르게 확인하기 위해 merkle tree를 사용한다. 머클 트리는 잎이 각 키의 해쉬 value인 해시 트리이다. 부모는 자식의 해시이다. 머클 트리는 replicar간에 비일관성을 체크하기 위해 전송해야하는 데이터 사이즈를 줄인다. 
이 시스템의 단점은 새 노드가 들어왔다 나갔을때 모두 재 계산되야한다는 점이다. 
하지만 이 문제도 6.2절의 refined partitioning에 의해 해결되었다. 

4.8 membership and failure datection 
4.8,1 Ring membership 
Gossip based protocol은 멤버십 변화를 전파한다. 

4.8.2 External Discovery 
4.8.3 Failure Detection 
4.9 Adding / Removing Storage Nodes 
노드에 X가 추가되면 조정된 노드 담당 범위에 따라서 키가 다시 분배된다. 

5. IMPLEMENTATION 
Dynamo에서 각 스토리지 노드는 세 구성요소로 되어있ㄷ. 
Request coordination, membership and failure detection, local persistence engined 

Dynamo local persistence컴포넌트는 berkeley database transactional Data Store를 쓴다. 

Java NIO채널로 모든 communication이 구현되었다. 
State machine이라는게 내부에 있게 이게 req, res주기 받기, 재시도, 클라에 응답 주기, 등을 한다. 
각 state machine은 정확히 하나의 client request를 담당한다. 

Resul가 맞지 않으면 최신으로수정하고 그걸 read repair라고 부른다. 

쓰기 요청은 탑 Nnode에 의해 조정된다, 

6. 경험과 배운점 
아래 경우에 Dynamo가 쓰인다. 
Business logic specific reconciliation 
분기가 발생하면 클라 애플리케이션이 자신만의 로직을 ㅗ해결한다. (소핑카트)
Timestamp based reconciliation 
다양한 분기 버젼이 있으면, 시간 기반 reconciliation을 진행한다. 즉 last write wins이다.
고객의 세션 정보가 가장 좋은 사용 사례이다. 
High performance read engine 
고성능 읽기가 가능하다. 
R을 1,W를 N으로 잡을 수도 있다. 

Dynamo는 주로 N값으로 3을 사용하곤 한다. 
W가 1이면 노드가적어도 1개가 가용하더라도 항상 성공한다. 

주로 지속성과 가용성을 같은 맥락에 잇다. 
(N, R, W)는 (3, 2, 2)가 가장 일반적이다. SLA에 맞는 숫자다. 
각 Dynamo단위는 다중 데이터센터에 있는 노드를 포함한다. 


6.1 Balancing Performance and Durability 
최적화를 위해서 write를 할때 버퍼를 둔다. 그리고 writer thread가 그걸 주기적으로 읽어서 스토리지에 쓴다. 
그래서 읽기의 경우 버퍼에 있는지 확인하고 있으면 그걸 읽는다. 

이 버퍼 사용으로 5배나 지연 시간을 줄일 수 있엇다고 한다. 
하지만 서버 크래시에서 큐 내 내용을 잃을 수도 있다. 
이 지속성 리스크를 줄이기 위해, 


6.2 Ensuring Uniform Load distribution 
부하가 크면 ...

 

---

좋은 논문을 제공해주셔서 감사합니다.

재밌게 읽었습니다.

 

https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf