[25 Computer Papers] 2. Dynamo: Amazon’s Highly Available key-value Store

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

 

 

요약

• key-value 스토어가 필요해서 그냥 구현함 (조인 같은 기능이 필요없었음)
• 시스템은 분산되어야 하며 하드웨어에 제약을 받지 않으면서 영속성은 필요했음
• 해시링에 구현 전략 설명서
• 동시 업데이트시 데이터 충돌을 피하기 위해 낙관적락으로 구현

 

 

---

ABSTRACT

Amazon의 핵심 서비스 중 일부가 '상시 가동'을 제공하기 위해 사용하는 고가용성 키-값 스토리지 시스템인 Dynamo의 설계와 구현에 대해 설명한다. 이러한 수준의 가용성을 달성하기 위해 Dynamo는 특정 장애 시나리오에서 일관성을 희생한다.

 

 

1 introuduction

Amazon은 전 세계 여러 데이터 센터에 위치한 수만 대의 서버를 사용하여 피크 시간대에 수천만 명의 고객에게 서비스를 제공하는 전 세계적인 이커머스 플랫폼을 운영하고 있다.

안정성은 가장 중요한 요구 사항 중 하나로, 사소한 중단도 심각한 재정적 결과를 초래하고 고객 신뢰에 영향을 미친다.

Dynamo는 안정성 요구 사항이 매우 높고 가용성, 일관성, 비용 효율성, 성능 간의 절충점을 엄격하게 제어해야 하는 서비스의 상태를 관리하는 데 사용된다.

복제본 간의 일관성은 분산형 복제본 동기화 프로토콜을 통해 유지된다.

Dynamo는 가십 기반 분산 장애 감지 및 멤버십 프로토콜을 사용하며 수동 관리가 거의 필요 없는 완전히 분산된 시스템으로 스토리지 노드는 수동 파티셔닝이나 재분배 없이도 Dynamo에서 추가 및 제거할 수 있다.

 

 

2 background

Amazon 이커머스 플랫폼은 추천부터 주문 처리, 탐지까지 다양한 기능을 제공하기 위해 함께 작동하는 수백 개의 서비스로 구성되어 전 세계 여러 데이터 센터에 위치한 수만 대의 서버로 구성된 인프라에서 호스팅된다.

이러한 서비스 중 일부는 상태 비저장형(즉, 다른 서비스의 응답을 집계하는 서비스)이고 일부는 상태 저장형(즉, 영구 저장소에 저장된 상태에 대해 비즈니스 로직을 실행하여 응답을 생성하는 서비스)

전통적으로 프로덕션 시스템은 관계형 데이터베이스에 상태를 저장한다.

Amazon 서비스 대부분은 기본 키로만 데이터를 저장하고 검색하며 RDBMS가 제공하는 복잡한 쿼리 및 관리 기능을 필요로 하지 않는다.

 

 

2.3 고려사항

상용 시스템에서 사용되는 데이터 복제 알고리즘은 전통적으로 강력하게 일관된 데이터 액세스 인터페이스를 제공하기 위해 동기식 복제본 조정을 수행한다. 이러한 수준의 일관성을 달성하기 위해 이러한 알고리즘은 특정 장애 시나리오에서 데이터의 가용성을 절충해야 한다.

예를 들어, 응답이 불확실성을 처리하는 대신 응답이 확실할 때까지 데이터를 사용할 수 없도록 설정한다. 초기의 복제 데이터베이스 작업에서 네트워크 장애 가능성을 다룰 때 강력한 일관성과 높은 데이터 가용성을 동시에 달성할 수 없다는 것은 잘 알려져 있다.

데이터 저장소가 주어진 시간에 모든(또는 대다수의) 복제본에 도달할 수 없는 경우 쓰기가 거부될 수 있다. 반면, Dynamo는 “항상 쓰기 가능한” 데이터 저장소(즉, 쓰기 가용성이 높은 데이터 저장소)의 설계 공간을 목표로 한다

 

3 RELATED WORK

3.3 discussion

Dynamo는 기존 분산형 스토리지 시스템과 목표 요구 사항 측면에서 차이가 있다.

첫째, Dynamo는 주로 장애나 동시 쓰기로 인해 업데이트가 거부되지 않는 “항상 쓰기 가능한” 데이터 저장소가 필요한 애플리케이션을 대상으로 한다.

둘째, Dynamo는 모든 노드가 신뢰할 수 있다고 가정되는 단일 관리 도메인 내의 인프라를 위해 구축되었다

셋째, Dynamo를 사용하는 애플리케이션은 계층적 네임스페이스(많은 파일 시스템의 표준)나 복잡한 관계형 스키마(기존 데이터베이스에서 지원)를 지원할 필요가 없다

넷째, Dynamo는 읽기 및 쓰기 작업의 99.9% 이상이 수백 밀리초 이내에 수행되어야 하는 지연 시간에 민감한 애플리케이션을 위해 구축되었다

 

4.1 system interfaxe

Dynamo는 간단한 인터페이스를 통해 키와 연결된 객체를 저장하며, get()과 put()이라는 두 가지 연산을 사용한다.

get(key) 연산은 스토리지 시스템에서 키와 연결된 객체 복제본을 찾아 컨텍스트와 함께 단일 객체 또는 충돌하는 버전이 있는 객체 목록을 반환.

put(키, 컨텍스트, 오브젝트) 작업은 연결된 키를 기준으로 오브젝트의 복제본을 배치할 위치를 결정하고 복제본을 디스크에 추가한다.

 

4.2 partitioning algorithm

dynamo의 점진적 확장을 위해 시스템의 노드 집합(즉, 스토리지 호스트)에 걸쳐 데이터를 동적으로 파티셔닝하는 메커니즘이 필요Dynamo의 파티셔닝 체계는 일관된 해싱을 사용해 여러 스토리지 호스트에 부하를 분산시킨다

일관된 해싱[10]에서 해시 함수의 출력 범위는 고정된 원형 공간 또는 “링”으로 취급(즉, 가장 큰 해시 값이 가장 작은 해시 값으로 감싸는 방식).

시스템의 각 노드에는 이 공간 내에서 임의의 값이 할당되며, 이는 링에서 해당 노드의 '위치'를 나타낸다.

가상 노드를 사용하면 다음과 같은 이점이 있다.

• 장애 또는 정기 유지 관리로 인해 노드를 사용할 수 없게 되면 이 노드에서 처리하는 부하가 나머지 사용 가능한 노드에 고르게 분산
• 노드를 다시 사용할 수 있게 되거나 시스템에 새 노드가 추가되면 새로 사용 가능한 노드는 다른 사용 가능한 노드로부터 거의 동일한 양의 부하를 받는다.

4.3 replication

높은 가용성과 내구성을 달성하기 위해 Dynamo는 데이터를 여러 호스트에 복제한다.

각 데이터 항목은 N개의 호스트에 복제되며, 여기서 N은 '인스턴스 단위'로 구성된 매개변수

각 키를 해당 범위 내에 로컬로 저장하는 것 외에도 링의 시계 방향 N-1 후속 노드에 이러한 키를 복제

그 결과 각 노드가 자신과 N번째 이전 노드 사이의 링 영역을 담당하는 시스템이 만들어진다. 위의 그림 2에서 노드 B는 키 k를 로컬에 저장하는 것 외에도 노드 C와 D에 복제한다. [노드 D는 [A, B], (B, C], (C, D] 범위에 속하는 키를 저장합니다.]

노드 장애를 고려하기 위해 기본 설정 목록에는 N개 이상의 노드가 필요하다.

 

 

4.4 Data Versioning

Dynamo는 업데이트가 모든 복제본에 비동기적으로 전파될 수 있도록 최종적인 일관성을 제공

put() 호출은 모든 복제본에 업데이트가 적용되기 전에 호출자에게 반환될 수 있으며, 이로 인해 후속 get() 작업이 최신 업데이트가 없는 객체를 반환할 수 있는 시나리오가 발생할 수 있다.

 

Dynamo는 벡터 시계(vector clock)를 사용하여 동일한 객체의 여러 버전 간의 인과 관계를 포착

vector clock은 사실상 (노드, 카운터) 쌍의 목록으로 하나의 vector clock는 모든 객체의 모든 버전과 연관된다.

한 객체의 두 버전이 평행한 가지에 있는지 또는 인과 관계가 있는지 여부는 벡터 시계를 살펴봄으로써 확인할 수 있다.

첫 번째 객체 시계의 카운터가 두 번째 시계의 모든 노드보다 작거나 같으면 첫 번째는 두 번째보다 오래된 객체가 된다.

4.5 Execution of get () and put () operations

읽기 또는 쓰기 작업을 처리하는 노드를 코디네이터라고 한다. 일반적으로 코디네이터는 기본 설정 목록의 상위 N개 노드 중 첫 번째 노드이다. 로드 밸런서를 통해 요청이 수신되는 경우 키 액세스 요청은 링의 임의의 노드로 라우팅될 수 있다. 이 시나리오에서는 요청을 받은 노드가 요청된 키의 기본 설정 목록의 상위 N개 노드에 속하지 않는 경우 요청을 조정하지 않다.

대신, 해당 노드는 기본 설정 목록의 상위 N개 노드 중 첫 번째 노드에 요청을 전달된다. 읽기 및 쓰기 작업에는 기본 설정 목록의 첫 번째 정상 노드가 포함되며, 다운되었거나 액세스할 수 없는 노드는 건너뛴다.

모든 노드가 정상인 경우, 키의 환경설정 목록에서 상위 N개의 노드에 액세스한다. 노드 장애 또는 네트워크 파티션이 있는 경우 기본 설정 목록에서 순위가 낮은 노드에 액세스한다.

 

R : 성공적인 읽기 작업에 참여해야 하는 최소 노드 수

W: 성공적인 쓰기 작업에 참여해야 하는 최소 노드 수

R + W > N이 되도록 R과 W를 설정하면 쿼럼과 유사한 시스템이 만들어진다.

 

키에 대한 put() 요청을 받으면 코디네이터는 새 버전의 벡터 클럭을 생성하고 새 버전을 로컬에 기록한다.

그런 다음 코디네이터는 새 버전(새 벡터 시계와 함께)을 도달 가능한 가장 높은 순위의 N 노드에 보낸다. 최소 W-1 노드가 응답하면 쓰기가 성공한 것으로 간주한다

 

마찬가지로, get() 요청의 경우 코디네이터는 해당 키에 대한 기본 설정 목록에서 가장 높은 순위의 도달 가능한 N 노드로부터 해당 키에 대한 모든 기존 버전의 데이터를 요청하고, 그 결과를 클라이언트에 반환하기 전에 R 응답을 기다린다.

• W,R 이 몇 개 안되는 경우 응답 레이턴시는 매우 빠를 것이다. 대신 데이터 일관성은 잠깐 일치하지 않을 수 있다.
• W,R 이 전체 개수와 비슷하다면 응답 레이턴시는 느릴 것이다. 하지만 데이터 일관성은 언제나 같을 것이다.

6.2 Ensuring Uniform Load distribution

위의 그림은 N=3에 대한 이 전략을 보여준다. 예에서는 키 k1이 포함된 파티션의 끝에서 노드 A, B, C를 만나게 됩니다. 이 전략의 주요 장점은 다음과 같다: (i) 파티셔닝과 파티션 배치의 분리, (ii) 런타임에 배치 체계를 변경할 수 있다는 점이다.

 

전략 1: 토큰 값에 따라 노드 및 파티션당 무작위 토큰을 할당: 이는 프로덕션 환경에서 처음 배포된 전략이다.

문제점:

• 새 노드가 시스템에 가입할 때 다른 노드로부터 키 범위를 '훔쳐야' 한다.
• 노드가 시스템에 가입/탈퇴하면 많은 노드에서 처리하는 키 범위가 변경되고 새로운 범위에 대한 트리를 다시 계산해야 하는데, 이는 프로덕션 시스템에서 수행하기에는 결코 간단한 작업이 아니다.
• 키 범위의 무작위성으로 인해 전체 키 공간의 스냅샷을 찍을 수 있는 쉬운 방법이 없음

전략 2: 노드당 T개의 무작위 토큰과 동일한 크기의 파티션: 이 전략에서는 해시 공간을 동일한 크기의 파티션/범위 Q로 나누고 각 노드에 무작위 토큰 T개를 할당한다.

 

전략 3: 노드당 Q/S 토큰, 동일한 크기의 파티션: 이 전략은 전략 2와 마찬가지로 해시 공간을 동일한 크기의 파티션 Q로 나누고 파티션의 배치는 파티셔닝 체계에서 분리된다.

또한 각 노드에는 Q/S 토큰이 할당되며, 여기서 S는 시스템 내 노드 수.

노드가 시스템을 떠나면 해당 토큰은 이러한 속성이 유지되도록 나머지 노드에 무작위로 분배된다.

마찬가지로 노드가 시스템에 합류하면 이러한 속성을 보존하는 방식으로 시스템 내 노드에서 토큰을 “훔친다”.

 

각 노드에서 유지되는 메타데이터의 양이 동일한 30개의 노드와 N=3인 시스템에 대한 다양한 전략의 부하 분산 효율성 비교.

 

전략 1에서는 토큰이 무작위로 선택되며, Dynamo에 저장된 데이터를 보관하려면 개별 노드에서 키를 별도로 검색해야 하므로 일반적으로 비효율적이고 느리다. 전략 3의 단점은 노드 멤버십을 변경할 때 할당에 필요한 속성을 유지하기 위해 조율이 필요하다