Dynamo: Amazon’s Highly Available Key-value Store
논문 https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
아마존닷컴의 주요 과제중 하나는 대규모의 신뢰성을 확보하는것이다.
다이나모는 항상 켜져있는(always-on) 경험을 제공하기 위한 고가용성 키-값 저장소이다.
다이나모는 높은 신뢰성을 요구하는 동시에, 가용성, 일관성, 비용 효율성, 성능 간의 트레이드 오프를 엄격이 조정해야한다.
많은 서비스들은 기본키만으로도 충분히 서비스가 가능하다.
복잡한 쿼리나 RDBMS가 제공하는 관리 기능을 필요로 하지않으며 이는 높은 숙련도를 요구한다.
다이나모는 이러한 서비스의 요구 사항을 충족하기 위해 만들어진 단순한 기본 키 전용 인터페이스를 제공한다.
가용성과 확장성을 위해 데이터는 파티셔닝, 일관된 해싱(consistent hashing) 으로 복제되며,
일관성은 객체 버전을 으로 확보한다.
데이터 업데이트중의 레플리카 사이의 일관성은 정족수 기법과 분산 레플리카 동기화 프로토콜로 유지한다.
서비스 수준 협약 (Service Level Agreement)
초당 최대 500건의 요청을 99.9% 에 대해 300ms 이내에 응답할것을 보장.
이는 대다수의 고객이 아닌 모든 고객에게 좋은 경험을 제공하기 위함.
설계 주요 원칙
점진적 확장성 : 한번에 하나의 저장소 호소트를 확장할 수 있다.
대칭성 : 다이나모의 모든 노드는 서로 동등한 책임
탈중앙성 :분산된 피어 대 피어 기법 (Peer to Peer)
이질성 : 시스템은 자신이 실행되는 인프라의 이질성을 이용(Heterogeneity)
분산 파일 시스템과 데이터베이스
1. 항상 쓰기 가능한 데이터 저장소가 필요하다
2. 다이나모는 모든 노드를 신뢰할 수 있어야 한다.
3. 계층적 네임스페이스나 복잡한 관계형 스키마에 대한 지원을 필요로 하지 않는다
4. 수백 밀리초 안에 최소 99.9% 의 읽기 쓰기 명령을 처리할수 있어야한다.
시스템 인터데이스
get 과 put 두개의 명령어가 있다.
다이나모는 키에 MD5 해시를 적용해 128비트의 식별자를 생성.
일관된 해싱 알고리즘에는 우선적으로 랜던하게 배정하면 불균형한 부하 분산을 야기할수있다.
이를 해결하기위해 여러종류의 해싱을 사용하고, 가상노드라는 개념을 이용
가상노드의 장점
1. 장애 등에 의해 노드를 사용할수없으면, 해당 노드의 작업을 다른 노드에게 분산
2. 새로운 노드가 추가된다면 비슷한 양을 나눠받는다.
3. 담당하는 가상 노드의 수는 노드의 용량에 따라 결정
복제
높은 가용성과 내구성을 달성하기 위해 데이터는 N개의 호스트에 복제.
데이터 버저닝
PUT 명령은 모든 레플리카에게 업데이트가 반영되기전에 값을 반환한다.
GET 명령은 최신 업데이트가 안된 객체를 반환할수가있다.
이러한 이유때문에 객체를 버전으로 관리한다.
시스템에는 여러가지 버전이 존재할 수 있으며, 객체 버전이 충돌할 수 있다.
여러 분기를 다시 하나로 합치는 병합과정이 있으며, 이떄 제거한 데이터가 다시 나올 수 있다.
이러한 버전이 많아지면 효율이 나빠짐으로, 일정 수준의 버전을 가지고 있으며 해당 버전을 만들때
마지막 수정일자를 같이 넣는데, 임계치에 다달았을때는 가장 오래된 버전부터 삭제한다.
이는 비효율적일수도있으나, 프로덕션 환경에서 문제가 발생하지는 않았다.
모든 노드는 키에 대한 get, put 명령을 맏을수 있다.
이러한 노드를 선택하는 방법은 두가지 전략이 있다.
1. 부하 정보 기반으로 노드를 선택하여 로드밸런서를 통해 요청을 라우팅
장점 : 특정한 코드를 연결할 필요가 없다
2. 직접 라우팅하는 partition aware 라이브리러를 사용한다.
장점 : 더 낮은 레이턴시를 달성
읽기,쓰기 명령을 수행하는 노드를 코디네이터라고 한다. 일반적으로 선호 목록의 상위 N개 노드 중 첫번째 노드가
코디네이터로 선택된다. 링의 래덤한 노드에게 라우팅 되는데, 노드에 장애 또는 네트워크 파티션이 있는 경우 선호 목록에서 순위가 낮은 노드에게 접근한다.
레플리카의 일관성을 관리하기 위해 다이나모는 정족수 시스템과 유사한 일관성 프로토콜을 사용한다.
R(읽기) + W(쓰기) > N 을 정족수 시스템처럼 만들수있다.
get 또는 put 명령은 R 또는 W의 레플리카 중 가장 느린 레이턴시에 따른다.
키에 대한 put 요청을 받으면 새로운 버전을 위한 벡터 클럭을 생성ㄹ하며, N개의 도달 가능한 상위 노드에게 전송
W-1 개의 노드가 응답한다면 쓰기가 성공한것으로 간주.
get 또한 N개의 도달 가능한 상위 노드에게 모든 버전을 요청하고 R개의 노드 응답을 기다린뒤 결과를 반환
장애
노드 중 하나가 장애가 발생하면 해당 노드에 존재헀던 레플리카가 다른 노드에 전송.
복구가 된다면 다시 전달.
영구적으로 다운이 된다면, 해시값을 비교하여 리프 노드의 해시값을 계속 비교한다.
해시값 비교를 하면 빠르지만, 새 노드가 추가, 제거 될경우 다시 트리를 계산해야한다는 단점이 있다.
각 노드들은 랜덤한 다른 노드에 접근하며, 멤버십 변경 기록을 동기화.
일부 다이나모 노드는 시드의 역활을 맡는데, 시드는 모든 노드에게 알려져있는 노드이다.