다이나모: 아마존의 고가용성 키-값 저장소

초록

아마존닷컴(Amazon.com)은 세계에서 가장 큰 이커머스 사업 중 하나로, 아마존닷컴이 당면한 과제 중 하나는 대규모의 신뢰성을 확보하는 것이다. 아주 작은 장애도 상당한 금전적 피해를 초래할 수 있으며, 고객의 신뢰에 영향을 미친다. 전세계의 수많은 웹 사이트에게 서비스를 제공하고 있는 아마존닷컴 플랫폼은 수만 대의 서버와 세계 곳곳에 위치한 데이터센터의 네트워크 컴포넌트로 이뤄진 인프라 위에 구현되어 있다. 이러한 규모에서는 크고 작은 구성요소들이 지속적으로 장애가 일으키기 때문에 장애에 대응해 영속적인 상태를 관리하는 방식으로 소프트웨어 시스템의 신뢰성과 확장성을 높일 수 있다.

이 논문은 다이나모(Dynamo)의 설계와 구현을 소개한다. 다이나모는 아마존의 핵심 서비스 중 일부가 ‘항상 켜져있는’(always-on) 경험을 제공하기 위해 사용하는 고가용성 키-값 저장소 시스템이다. 높은 수준의 가용성을 달성하기 위해 다이나모는 특정 장애 시나리오에서 일관성을 희생한다. 다이나모는 개발자가 사용할 수 있는 새로운 인터페이스를 제공하는 방식으로 객체 버전 관리 및 애플리케이션 지원 충돌 해결을 광범위하게 활용한다.

서론

아마존은 세계 곳곳에 위치한 데이터센터의 서버 수만 대를 이용해 수천만 명의 고객에게 서비스를 제공함으로써 전세계적인 이커머스 플랫폼을 운영한다. 아마존 플랫폼에는 성능 및 신뢰성, 효율성 측면에서 엄격한 운영 요구사항이 있으며, 지속적인 성장을 지원하기 위해 플랫폼의 확장성을 높이고자 한다. 아주 작은 장애도 상당한 금전적 피해를 초래하고, 고객의 신뢰에 영향을 미치기 때문에 신뢰성은 가장 중요한 요구 사항 중 하나다. 추가로, 지속적인 성장을 지원하려면 플랫폼의 확장성이 높아야 한다.

아마존 플랫폼을 운영하면서 우리가 얻은 교훈 중 하나는 시스템의 신뢰성과 확장성이 애플리케이션 상태를 어떻게 다루는지에 달려있다는 것이다. 아마존은 수백 개의 서비스로 이뤄져 있어 고도의 분산과 느슨한 결합, 서비스 지향 아키텍처를 사용하고 있다. 이러한 환경에서는 항상 사용 가능한 저장소 기술이 특히나 필요하다. 예를 들어, 고객은 디스크에 장애가 발생하거나, 네트워크 경로에 문제가 생기거나, 토네이도로 인해 데이터센터가 파괴된 경우에도 장바구니에 상품을 추가하고, 확인할 수 있어야 한다. 따라서 장바구니를 관리하는 서비스는 항상 데이터 저장소를 읽고 쓸 수 있어야 하며, 여러 데이터센터에서 그 데이터를 사용할 수 있어야 한다.

수백만 개의 컴포넌트로 구성된 인프라의 장애를 처리하는 것은 아마존의 표준적인 운영 상태다. 작지만 상당한 수의 서버와 네트워크 컴포넌트들이 시도때도 없이 장애를 일으키기 때문이다. 따라서 아마존의 소프트웨어 시스템은 장애 처리를 일반적인 상황으로 취급하면서도 가용성이나 성능에 영향을 주지 않도록 구축되어야 한다.

가용성 및 확장성 요구 사항을 충족하기 위해 아마존은 많은 저장소 기술을 개발했다. 그 중에서는 Simple Storage Service(아마존 외부에서도 사용할 수 있으며, 아마존 S3로도 알려져있다.)가 가장 유명할 것이다. 이 논문에서는 고가용성과 확장성을 갖춘 분산 데이터 저장소인 다이나모의 구현과 설계를 제시한다. 다이나모는 높은 신뢰성을 요구하는 동시에, 가용성과 일관성, 비용 효율성, 성능 간의 트레이드오프를 엄격히 조정해야 하는 서비스들의 상태를 관리하기 위해 사용한다. 아마존 플랫폼에는 저장소 요구 사항이 제각기 다른 매우 다양한 애플리케이션들이 있다. 애플리케이션은 설계자가 비용 효율성을 고려하는 상황에서 고가용성, 고성능을 달성하기 위한 트레이드오프에 기반해 데이터 저장소를 적절히 설정할 수 있도록 충분히 유연해야 한다.

아마존 플랫폼에는 데이터 저장소에 접근하는 데 기본 키(primary key)만 사용하는 것으로 충분한 서비스들이 많다. 베스트 셀러 목록이나 장바구니, 설정, 세션 관리, 판매 순위, 상품 카탈로그 등을 제공하는 서비스에서 관계형 데이터베이스의 일반적인 패턴을 사용하는 것은 효율적이지 않으며, 가용성과 확장성을 제한하게 된다. 다이나모는 이러한 애플리케이션들의 요구 사항을 충족하기 위해 단순한 기본 키 전용 인터페이스를 제공한다.

다이나모는 잘 알려진 기법들을 조합해 가용성과 확장성을 달성한다. 데이터는 파티셔닝되며, 안정 해싱[10](consistent hasing)으로 복제된다. 일관성은 객체 버저닝[12]으로 확보할 수 있다. 데이터 업데이트 중 레플리카(replicas) 사이의 일관성은 정족수(quorum) 기법과 분산 레플리카 동기화 프로토콜로 유지할 수 있다. 다이나모는 가십(gossip) 기반의 분산 장애 감지와 멤버십 프로토콜을 사용한다. 다이나모는 수동으로 관리할 필요 없이 완전히 분산된 시스템이다. 어떠한 수동 파티셔닝이나 재배포 없이 새 저장소 노드를 추가하거나, 기존 노드를 제거할 수 있다.

지난 1년간 다이나모는 아마존 이커머스 플랫폼의 수많은 핵심 서비스들을 떠받치는 저장소 기술이 되었다. 연휴 쇼핑 시즌 동안에도 서비스를 효율적으로 확장해 극한의 부하를 다운타임 없이 처리할 수 있었다. 예를 들어, 장바구니를 관리하는 서비스(장바구니 서비스)는 수천만 건의 요청을 처리해 하루에 300만 건 이상의 체크아웃을 소화했다. 또한 세션 상태를 관리하는 서비스는 수십만 건의 동시적인 활성 세션을 다뤘다.

이 연구는 다양한 기술들을 결합하여 하나의 고가용성 시스템을 제공하는 방법에 대해 제시함으로써 연구 커뮤니티에 기여한다. 이 연구는 최종 일관성(eventually-consistent) 저장소 시스템을 프로덕션의 애플리케이션에 사용할 수 있음을 보여준다. 또한 매우 엄격한 성능을 요구하는 프로덕션 시스템의 요구 사항을 충족하기 위해 각종 기법을 조정하는 방법에 대한 통찰도 제공한다.

이 논문은 다음과 같이 구성되어 있다. 섹션 2에서 배경에 대해 설명하고, 섹션 3에서는 관련 연구를 소개한다. 섹션 4에서는 시스템 설계를 제시하며, 섹션 5에서는 구현을 설명한다. 섹션 6에서는 프로덕션에서 다이나모를 운영하며 얻은 통찰과 경험에 대한 상세한 내용을 다루고, 섹션 7에서는 결론을 짓는다. 이 논문의 많은 부분에서 적절한 추가 정보를 제공하고 있지만, 아마존의 비즈니스 이익을 보호하기 위해 어느 정도 세부 사항을 줄인 부분도 있다. 이러한 이유로 섹션 6의 데이터센터 내외부의 레이턴시, 섹션 6.2의 절대적인 요청 규모, 섹션 6.3의 중단 기간 및 워크로드에 대한 내용은 세부 정보 대신 집계된 측정치를 통해 제공한다.

배경

아마존의 이커머스 플랫폼은 추천부터 주문 풀필먼트, 사기 탐지에 이르기까지, 다양한 기능을 제공하기 위해 협업하는 수백 개의 서비스로 구성되어 있다. 각 서비스는 잘 정의된 인터페이스로 노출되어 있으며, 네트워크를 통해 접근할 수 있다. 이러한 서비스들은 전세계 곳곳에 위치한 수만 대의 서버로 이뤄진 인프라를 통해 호스팅된다. 서비스 중 일부는 무상태(stateless, i.e., 다른 서비스로부터 응답을 받아 집계하는 서비스들)이며, 어떤 서비스들은 상태(stateful, i.e., 영속적 저장소에 있는 상태를 이용해 비즈니스 로직을 실행함으로써 자신의 응답을 만드는 서비스들)를 갖는다.

관례적으로 프로덕션 시스템은 자신의 상태를 관계형 데이터베이스에 저장한다. 영속적인 상태를 위해 일반적으로 많이 사용하는 패턴이지만, 관계형 데이터베이스가 이상적인 해결책은 아니다. 대부분의 서비스는 기본 키(primary key)로 데이터를 저장하거나 읽기만 하지, 복잡한 쿼리나 RDBMS가 제공하는 관리 기능을 필요로 하지 않는다. 이렇게 과도한 기능성은 비싼 하드웨어와 높은 숙련도를 요구하기 때문에 매우 비효율적인 해결책이다. 또한, 사용 가능한 데이터 복제 기술이 제한되며, 일반적으로 가용성보다는 일관성을 선택하게 된다. 최근 몇년 간 많은 발전이 있었음에도 불구하고, 여전히 로드밸런싱을 위해 스키마를 스마트 파티셔닝하거나 데이터베이스를 스케일 아웃하는 것은 쉬운 일이 아니다.

이 논문은 중요한 서비스들의 요구를 해결할 수 있는 고가용성 데이터 저장소 기술인 다이나모에 대해 설명한다. 다이나모는 단순한 키/값 인터페이스를 제공한다. 이러한 인터페이스는 일관성 윈도우가 명확히 정의되어 있어 가용성이 높고, 효율적으로 리소스를 사용할 수 있으며, 데이터셋 크기 또는 요청의 증가를 해결하기 위한 간단한 스케일 아웃 방식을 갖추고 있다. 다이나모를 사용하는 각 서비스들은 자신만의 다이나모 인스턴스를 운영한다.

시스템 요구 사항과 전제

저장소 시스템에는 다음과 같은 요구 사항들이 있다.

쿼리 모델: 키를 통해 유일하게 식별할 수 있는 데이터에 대한 간단한 읽기, 쓰기 명령. 상태는 유니크 키(unique key)로 식별할 수 있는 바이너리 객체(i.e., blobs)로 저장된다. 여러 개의 데이터에 대한 명령이나 관계형 스키마는 필요하지 않다. 이 요구 사항은 아마존 서비스의 상당한 부분이 간단한 쿼리 모델로 동작할 수 있으며, 관계형 스키마가 필요하지 않다는 관찰에 기반한다. 다이나모는 상대적으로 작은 크기의 객체(보통 1MB 미만)를 저장하려는 애플리케이션을 목표로 한다.

ACID 속성: ACID(원자성, 일관성, 고립성, 내구성, Atomicity, Consistency, Isolation, Durability)는 데이터베이스 시스템이 트랜잭션을 안정적으로 처리할 수 있음을 보장하는 속성들이다. 데이터베이스의 맥락에서, 데이터에 대한 하나의 논리적 동작을 트랜잭션이라고 부른다. 아마존에서의 경험으로는 ACID를 보장하는 데이터 저장소의 경우 가용성이 떨어지는 경향이 있다. 이러한 경향성은 업계와 학계 모두에게 널리 인정받고 있다[5]. 다이나모는 높은 가용성을 얻을 수 있다면 약한 일관성(consistency, ACID에서 “C”)을 허용할 수 있는 애플리케이션을 목표로 한다. 다이나모는 고립성을 보장하지 않으며, 단일 키 업데이트만 허용한다.

효율: 시스템은 유용한 하드웨어 인프라를 필요로 한다. 아마존 플랫폼의 경우 99.9 분위에서 측정하는 엄격한 레이턴시 요구 사항을 따른다. 서비스 운영에서 상태에 대한 접근이 중요한 역할을 하기 때문에 저장소 시스템은 이러한 엄격한 SLA(아래 섹션 2.2를 참고)를 충족할 수 있어야 한다. 서비스는 자신의 레이턴시와 처리량에 대한 요구 사항을 일관적으로 달성하기 위해 다이나모를 설정할 수 있어야 한다. 트레이드오프는 성능, 비용 효율성, 가용성, 내구성에 대한 보장이다.

나머지 전제: 다이나모는 아마존의 내부 서비스만을 위해 사용되었다. 다이나모의 운영 환경은 비적대적이며, 인증이나 권한과 같은 보안 관련 요구사항은 없다. 또한 각 서비스는 분리된 다이나모 인스턴스를 사용하기 때문에 초기 설계는 최대 수백 개 정도의 저장소 호스트를 대상으로 한다. 다이나모가 가진 확장성의 한계와 가능성에 대해서는 뒷부분에서 논의할 것이다.

서비스 수준 협약 (SLA)

애플리케이션이 제한된 시간 내에 기능을 제공할 수 있도록 플랫폼의 모든 의존성은 더욱 엄격한 기준으로 기능을 제공해야 한다. 서비스와 클라이언트는 서비스 수준 협약(Service-Level Agreement, SLA)을 약속한다. SLA는 다양한 시스템 특성에 대해 클라이언트와 서비스가 맺은 정식 계약이며, 특정 API에 대한 클라이언트의 예상 요청량 분포와 이러한 조건에서의 서비스 레이턴시를 포함한다. 간단한 SLA 예시로는, 클라이언트가 초당 최대 500건의 요청을 전송할 때 서비스가 요청의 99.9%에 대해 300ms 이내에 응답할 것에 대한 보장이다.

아마존의 분산 서비스 지향 인프라에서 SLA는 중요한 역할을 한다. 예를 들어 이커머스 사이트 중 하나에 대한 페이지 요청은 일반적으로 렌더링 엔진이 150개 이상의 서비스에 요청을 보내 응답할 것을 요구한다. 이러한 서비스들은 주로 다른 서비스를 의존성으로 가지고 있기 때문에 애플리케이션의 호출 그래프가 둘 이상이 되는 것은 드문 일이 아니다. 페이지 렌더링 엔진이 페이지 제공에 대한 명확한 기준을 유지할 수 있도록 하기 위해 호출 흐름 내의 각 서비스는 성능 계약을 준수해야 한다.

그림 1. 아마존 플랫폼의 서비스 지향 아키텍처

그림 1은 아마존 플랫폼의 아키텍처에 대한 개략적인 모습을 보여준다. 아마존 플랫폼에서 동적 웹 콘텐츠는 페이지 렌더링 컴포넌트에 의해 생성되며, 이 컴포넌트는 다시 다른 서비스를 쿼리한다. 하나의 서비스는 자신의 상태를 관리하기 위해 다른 데이터 저장소를 사용할 수 있으며, 이 데이터 저장소는 오직 해당 서비스 영역 안에서만 접근할 수 있다. 어떤 서비스들은 다른 여러 서비스의 응답을 수집해 새로운 응답을 만들어낸다. 일반적으로 수집 서비스(aggregator services)는 무상태이며, 광범위한 캐시를 사용한다.

성능 지향 SLA를 만들기 위한 업계의 일반적인 접근법은 평균, 중앙값, 예상 분산을 사용해 SLA를 설명하는 것이다. 아마존에서는 대다수의 고객이 아닌 모든 고객에게 좋은 경험을 제공할 수 있는 시스템을 구축하는 것이 목표인 경우 이러한 지표가 충분하지 않다는 것을 발견했다. 예를 들어 광범위한 개인화 기법을 사용한다면, 서비스를 오래 사용한 고객일수록 더 많은 처리를 요구하기 때문에 성능 분포의 하이엔드에 영향을 미친다. 응답 시간에 대한 평균값이나 중앙값으로 명시한 SLA는 이렇게 중요한 고객 세그먼트의 성능을 담지 못한다. 아마존에서는 이러한 이슈를 해결하기 위해 SLA를 99.9 분위를 기준으로 측정, 표현한다. 훨씬 더 높은 백분위수가 아니라 99.9 분위를 선택한 이유는 비용 편익 분석에 근거한 것으로, 나머지 만큼의 성능을 개선하기 위한 비용이 더 크기 때문이다. 아마존 프로덕션 시스템에서의 경험은 이러한 접근법을 사용한 시스템이 평균이나 중앙값에 기초해 정의한 SLA를 충족하는 시스템에 비해 전반적으로 더 나은 경험을 제공한다는 것을 입증했다.

이 논문에서는 99.9 분위를 많이 언급하는데, 이는 고객 경험의 관점에서 성능에 대한 아마존 엔지니어들의 끊임없는 관심이 반영된 것이다. 많은 논문들이 평균값을 사용하기 때문에 비교 목적으로 타당한 경우에는 그런 논문들을 참고한다. 그럼에도 불구하고 아마존의 엔지니링과 최적화 노력은 평균에 집중하지 않는다. 쓰기 코디네이터의 로드밸런싱과 같은 몇 가지 기술들은 순수하게 99.9 분위에서의 성능 제어를 목표로 한다.

저장소 시스템은 종종 서비스의 SLA를 수립하는데 중요한 역할을 한다. 특히 많은 아마존 서비스들처럼 비즈니스 로직이 상대적으로 가벼울 때 그렇다. 상태 관리는 서비스 SLA의 주요 요소로 자리잡고 있다. 다이나모의 주요 설계 고려 사항 중 하나는 서비스들이 내구성이나 일관성과 같은 시스템 속성에 대한 제어를 제공하고, 서비스가 자체적으로 기능과 성능, 비용 효율성을 트레이드오프할 수 있도록 하는 것이다.

설계 고려 사항

상용 시스템에서 전통적으로 사용되는 데이터 복제 알고리즘은 동기식 복제를 수행함으로써 매우 일관된 데이터 접근 인터페이스를 제공한다. 높은 수준의 일관성을 달성하기 위해 알고리즘들은 특정 실패 시나리오에서 데이터의 가용성을 트레이드오프해야 한다. 가령, 데이터의 정확성에 대한 불확실성을 다루는 대신 데이터가 정확하다는 것이 절대적으로 확실해질 때까지 데이터를 사용할 수 없게 만든다. 복제 데이터베이스를 초기에 도입했을 때부터 네트워크 장애의 가능성 때문에 강력한 일관성과 높은 가용성을 동시에 달성할 수 없다는 것이 잘 알려져 왔다[2][11]. 따라서 시스템과 애플리케이션은 어떤 조건에 따라 어떤 속성을 달성할 수 있는지 알아야 한다.

서버 및 네트워크 장애가 발생하기 쉬운 시스템의 경우, 백그라운드에서 동시적으로 레플리카를 전파하거나, 연결이 끊긴 작업을 허용하는 낙관적 복제(optimistic replication) 기법을 사용해 가용성을 높일 수 있다. 이 접근법의 어려운 부분은 변경에 대한 충돌을 감지하고, 해결해야 할 수도 있다는 점이다. 충돌 해결 과정은 누가 충돌을 해결할지, 언제 충돌을 해결할지에 대한 문제를 불러온다. 다이나모는 최종 일관성 데이터 저장소로 설계되었으며, 업데이트 동작이 최종적으로 모든 레플리카에 도달하게 된다.

중요한 설계 고려 사항은 업데이트 충돌 해결 과정을 언제 수행할지 결정하는 것이다. 충돌은 읽기 또는 쓰기 동작 중에 해결되어야 한다. 많은 전통적인 데이터 저장소가 쓰기 중에 충돌을 해결함으로써 읽기 복잡도를 단순하게 만든다[7]. 이러한 시스템은 주어진 시간동안 모든(또는 대부분의) 레플리카에 도달할 수 없다면 쓰기 동작을 거부할 수 있다. 한편 다이나모는 ‘항상 쓰기 가능한’(always writeable) 데이터 저장소를 목표로 한다. (즉, 쓰기 동작에 대해 가용성이 높은 데이터 저장소인 것이다.) 많은 아마존 서비스가 고객의 업데이트 요청을 거부한다면 열악한 고객 경험으로 이어질 수 있다. 예를 들어, 장바구니 서비스는 서버나 네트워크 장애가 일어나는 중에도 고객이 자신의 장바구니에 상품을 추가하거나 제거할 수 있도록 해야한다. 이러한 요구 사항은 쓰기 동작이 절대로 거부되지 않도록 하기 위해 충돌 해결의 복잡성을 읽기 동작이 감당하도록 만든다.

다음으로는 누가 업데이트 충돌 해결 과정을 수행할지 결정해야 한다. 충돌 해결은 데이터 저장소가 할 수도 있고, 애플리케이션이 할 수도 있다. 만약 데이터 저장소가 충돌을 해결한다면 제한이 많아진다. 가령, 데이터 저장소는 “최종 쓰기 승리”[22](last write wins)와 같은 단순한 정책만으로 업데이트 충돌을 해결할 수 있다. 반면 애플리케이션은 데이터 스키마를 알고 있으므로, 최적의 클라이언트 경험을 위한 충돌 해결 방법을 결정할 수 있다. 예를 들어 장바구니를 관리하는 애플리케이션은 충돌 버전을 병합(merge)하여 하나의 통합된 장바구니를 제공하기로 결정할 수 있다. 이러한 유연성에도 불구하고, 일부 애플리케이션 개발자들은 자체적인 충돌 해결 메커니즘을 작성하길 원하지 않을 것이며, 데이터 저장소가 "최종 쓰기 승리"와 같은 간단한 정책을 사용하도록 결정할 수도 있다.

설계에 채택된 다른 주요 원칙은 다음과 같다.

점진적 확장성: 다이나모는 시스템 운영자와 시스템 자체에 미치는 영향을 최소화하면서 한 번에 하나의 저장소 호스트(이하 “노드”)를 확장할 수 있어야 한다.

대칭성: 다이나모의 모든 노드는 서로 동등한 책임을 가져야 한다. 특별한 역할을 맡거나 추가적인 책임을 부담하는 노드는 없어야 한다. 경험적으로, 대칭성은 시스템 프로비저닝과 유지 과정을 단순하게 만들어준다.

탈중앙성: 대칭성의 확장으로, 설계는 중앙화된 통제보다는 분산된 피어 대 피어(peer-to-peer) 기법을 따라야 한다. 과거 중앙집중식 통제로 인해 운영 중단이 발생한 적이 있으며, 이를 최대한 피하는 것이 목표가 되었다. 이 원칙은 시스템은 더욱 단순하게, 확장 가능하게, 가용성 높게 만들어준다.

이질성: 시스템은 자신이 실행되는 인프라의 이질성(heterogeneity)을 이용할 수 있어야 한다. 예를 들어, 작업 분배는 개별 서버의 용량에 비례해야 한다. 이 원칙은 모든 호스트를 한 번에 업그레이드하지 않고도 용량이 더 큰 새 노드를 추가하는 데 필수적이다.

관련 연구

피어 대 피어 시스템

많은 피어 대 피어(P2P) 시스템이 데이터 저장소와 배포에 대한 문제를 고민해왔다. Freenet, Gnutella^[1]와 같은 P2P 시스템의 첫 세대는 대개 파일 공유 시스템으로 사용되었다. 이들은 피어 간의 오버레이 링크가 임의로 설정된 비정형 P2P 네트워크의 사례였다. 이러한 네트워크에서 검색 쿼리는 보통 네트워크를 통해 흐르며 데이터를 공유하는 피어를 최대한 많이 찾는다. P2P 시스템은 정형 P2P 네트워크라고 널리 알려진 다음 세대로 진화했다. 이 네트워크는 필요한 데이터를 가진 일부 피어에 어떠한 노드든지 검색 쿼리를 효율적으로 라우팅할 수 있도록 전반적으로 일관된 프로토콜을 사용한다. Pastry[16]이나 Chord[20]과 같은 시스템들은 제한된 수의 홉(hop) 내에 쿼리에 응답할 수 있도록 라우팅 메커니즘을 사용한다. 멀티 홉 라우팅으로 인한 추가적인 레이턴시를 줄이기 위해 일부 P2P 시스템(e.g., [14])은 각 피어가 로컬에서 충분한 라우팅 정보를 관리하도록 함으로써 상수 개수의 홉 내에 데이터 접근에 대한 요청을 적절한 피어에게 보내는 O(1) 라우팅을 사용한다.

Oceanstore[9], PAST[17]과 같은 다양한 저장소 시스템은 이러한 라우팅 오버레이 위에 구축되었다. Oceanstore는 광범위한 복제 데이터에 대해 직렬화된(serialized) 업데이트를 지원하는 영속적 저장소 서비스를 제공한다. Oceanstore는 광범위한 락(lock)에 내재된 많은 문제를 방지하면서 동시 업데이트를 가능하게 하기 위해 충돌 해결에 기반한 업데이트 모델을 사용한다. 트랜잭션 건수를 줄이기 위한 충돌 해결은 [21]에서 소개되었다. Oceanstore는 일련의 업데이트를 원자적으로 반영함으로써 충돌을 해결한다. 신뢰할 수 없는 인프라에서 데이터가 복제되는 상황을 위해 구축된 것이다. 이에 비해, PAST는 영속적이고 불변적인 객체를 위해 Pastry의 최상단에 단순한 추상 레이어를 제공한다. 이는 애플리케이션이 그 위에 필요한 스토리지 시맨틱(가변적인 파일 등)을 구축할 수 있다고 가정한다.

분산 파일 시스템과 데이터베이스

파일 시스템 및 데이터베이스 시스템 커뮤니티는 성능과 가용성, 내구성을 위해 데이터를 분산하는 것에 대해 광범위하게 연구해왔다. 평면적인 네임스페이스만을 지원하는 P2P 저장소 시스템과 비교해 분산 파일 시스템은 보통 계층적인 네임스페이스를 지원한다. Ficus[15]나 Coda[19] 같은 시스템들은 일관성을 희생시키면서 높은 가용성을 확보하기 위해 파일을 복제해둔다. 업데이트 충돌은 보통 특수한 충돌 해결 절차를 통해 관리한다. Farsite 시스템[1]은 NFS와 같은 중앙집중식 서버를 전혀 사용하지 않는 분산 파일 시스템이다. Farsite는 복제를 통해 높은 가용성과 확장성을 달성한다. 또 다른 분산 파일 시스템인 Google File System[6]은 구글의 내부 애플리케이션을 호스팅하기 위해 구축되었다. GFS는 메타데이터 전체를 호스팅하기 위한 마스터 서버 하나로 단순하게 설계되었으며, 데이터는 청크 서버에 여러 덩어리(chunks)로 쪼개져 저장된다. Bayou는 연결이 끊긴 동작을 허용하는 분산 관계형 데이터베이스 시스템으로, 최종 일관성을 지원한다[21].

이러한 시스템 중 Bayou, Coda, Ficus는 연결이 끊긴 동작을 허용해 네트워크 파티션이나 중단과 같은 문제에 대해 회복 탄력성을 갖는다. 이 시스템들은 충돌 해결 절차에 따라 달라진다. 예를 들어 Coda와 Ficus는 시스템 수준에서 충돌을 해결하며, Bayou는 애플리케이션 수준에서 해결한다. 그러나 이 시스템들은 모두 최종 일관성을 보장한다. 이들처럼 다이나모는 네트워크 파티션 중에도 쓰기 동작을 계속 허용하며, 다른 충돌 해결 매커니즘을 이용해 업데이트 충돌을 해결한다. FAB[18]와 같은 분산 블록 저장소 시스템은 크기가 큰 객체를 여러 개의 작은 블록으로 쪼개어 각 블록을 가용성이 높은 방식으로 저장한다. 이렇게 여러 시스템들을 비교해보면, 키-값 저장소는 이러한 상황에 더욱 적합하다: (a) 이들은 비교적 작은 객체(1M 미만)를 저장하기 위한 것이고 (b) 키-값 저장소는 애플리케이션별로 구성하기가 더 쉽다. Antiquity는 여러 개의 서버 장애를 처리하도록 설계된 광역 분산 스토리지 시스템이다[24]. Antiquity는 보안 로그를 사용해 데이터 무결성을 관리하며, 내구성을 위해 각 로그를 여러 서버에 복제해둔다. 또한 Byzantine 내결함(fault tolerance) 프로토콜을 사용해 데이터 일관성을 보장한다. Antiquity와 다르게 다이나모는 신뢰할 수 있는 환경을 위해 설계되었기 때문에 데이터 무결성과 보안 문제에는 초점을 맞추지 않는다. Bigtable은 정형화된 데이터를 다루기 위한 분산 저장소 시스템이다. Bigtable은 소량의 다차원적으로 정렬된 맵을 관리하며, 애플리케이션이 여러 속성을 사용해 데이터에 접근할 수 있도록 한다[2]. Bigtable과 비교해 다이나모는 네트워크 파티션이나 서버 장애 발생 시에도 업데이트를 거부하지 않는 고가용성에 중점을 두고 키/값 접근만을 필요로하는 애플리케이션을 대상으로 한다.

전통적인 복제 관계형 데이터베이스 시스템은 복제된 데이터에 대한 강한 일관성을 보장하는 데 집중한다. 강한 일관성이 애플리케이션 작성자에게 편리한 프로그래밍 모델을 제공하기는 하지만, 이러한 시스템은 확장성과 가용성에 한계가 있다[7]. 이러한 시스템들은 일반적으로 강력한 일관성을 보장하기 때문에 네트워크 파티션을 처리할 수 없다.

논의

다이나모는 앞서 언급한 분산형 저장소 시스템들과는 목표하는 요구 사항 측면에서 차이가 있다. 첫 번째로, 다이나모가 주요 목표로 삼는 애플리케이션들은 장애나 동시적 쓰기에도 업데이트 동작을 거부하지 않는 “항상 쓰기 가능한” 데이터 저장소를 필요로 한다. 이는 많은 아마존 애플리케이션들의 결정적인 요구 사항이다. 두 번째로, 앞서 언급했듯이 다이나모는 모든 노드를 신뢰할 수 있다고 전제하는 단일 관리 도메인 내의 인프라를 위해 만들어졌다. 세 번째로, 다이나모를 사용하는 애플리케이션들은 계층적 네임스페이스(많은 파일 시스템의 표준)나 복잡한 관계형 스키마(전통적인 데이터베이스들이 지원)에 대한 지원을 필요로 하지 않는다. 네 번째로, 다이나모는 수백 밀리초 안에 최소 99.9%의 읽기, 쓰기 명령을 처리할 수 있을 정도로 레이턴시에 민감한 애플리케이션들을 위해 만들어졌다. 이러한 엄격한 레이턴시 요구 사항을 만족하기 위해서는 여러 노드를 통한 라우팅 요청(Chord와 Pastry와 같은 분산 해시 테이블 시스템이 채택한 일반적인 설계)를 피해야 했다. 멀티 홉 라우팅이 응답 시간의 가변성을 높여 더 높은 백분위수에서 레이턴시를 증가시키기 때문이다. 다이나모의 특징은 제로 홉 DHT라고 할 수 있으며, 각 노드는 요청을 적절한 노드로 직접 라우팅할 수 있는 충분한 라우팅 정보를 로컬에서 관리한다.

시스템 아키텍처

프로덕션 환경에서 운영해야 하는 저장소 시스템의 아키텍처는 복잡하다. 데이터 영속성 컴포넌트 외에도 시스템은 로드밸런싱, 멤버십 및 장애 감지, 장애 복구, 레플리카 동기화, 오버로드 관리, 상태 전송, 동시성과 작업 스케줄링, 요청 마샬링(marshalling), 요청 라우팅, 시스템 모니터링과 알림, 설정 관리 등에 대한 확장 가능하고 탄탄한 해결책을 가지고 있어야 한다. 각 요소에 대한 해결책을 상세히 설명하기는 어렵기 때문에 이 논문에서는 다이나모에 사용되는 핵심 분산 시스템 기술에 집중한다: 파티셔닝, 복제, 버저닝, 멤버십, 장애 관리, 확장이 그것이다.

표 1. 다이나모가 사용하는 기술과 그 장점에 대한 요약

표 1은 다이나모가 사용하는 기술 목록과 각 기술의 장점을 요약해 보여준다.

시스템 인터페이스

다이나모는 단순한 인터베이스를 통해 키와 결합된 객체를 저장한다. 인터페이스에는 get()과 put() 두 개의 명령이 있다. get(key) 명령은 저장소 시스템에서 키와 연결된 객체 레플리카를 찾고 충돌 버전의 단일 객체나 객체 목록을 컨텍스트와 함께 반환한다. put(key, context, object) 명령은 결합된 키를 기준으로 객체의 레플리카 위치를 결정하고, 디스크에 저장한다. 컨텍스트는 객체 버전처럼 호출자에게 공개되지 않는 객체에 대한 시스템 메타데이터를 인코딩한다. 컨텍스트 정보는 객체와 함께 저장되기 때문에 시스템은 put 요청에서 제공된 컨텍스트 객체의 유효성을 확인할 수 있다.

다이나모는 호출자로부터 받은 키와 객체를 모두 불투명한 바이트열로 취급한다. 다이나모는 키에 MD5 해시를 적용해 128비트 식별자를 생성하며, 이 식별자는 키 제공을 담당할 저장소 노드를 결정하는 데 사용된다.

파티셔닝 알고리즘

그림 2. 다이나모 링에서의 키 파티셔닝 및 복제

다이나모의 주요 설계 요구 사항 중 하나는 점진적으로 확장할 수 있어야 한다는 것이다. 그러기 위해서는 시스템의 노드들(ie., 저장소 호스트)이 데이터를 동적으로 파티셔닝하는 메커니즘이 필요하다. 다이나모의 파티셔닝 방식은 안정 해싱에 의존하여 여러 저장소 호스트들에게 부하를 분산시킬 수 있다. 안정 해싱[10]에서, 해시 함수의 반환 범위는 고정된 원형 공간 또는 “링”(ring, i.e. 가장 큰 해시 값과 가장 작은 해시 값이 연결된 고리 형태)로 취급된다. 시스템의 각 노드는 이 공간 안의 랜덤 값을 배정받으며, 이 값은 링 위에 놓인 “위치”(position)로 표현된다. 키로 식별되는 각 데이터는 자신의 키를 해싱하여 위치를 산출한 다음, 링을 시계 방향으로 돌며 자신의 위치보다 큰 위치에 있는 첫 번째 노드에 자신을 할당한다.

따라서 각 노드는 링 위의 이전 노드와 자기 자신 사이의 영역을 담당하게 된다. 안정 해싱의 주요 이점은 노드의 추가 또는 제거가 인접한 노드에게만 영향을 미치고, 다른 노드들에게는 영향을 미치지 않는다는 것이다.

기본적인 안정 해싱 알고리즘에는 몇가지 과제가 있다. 우선 링에 있는 각 노드의 위치를 랜덤하게 배정하면 불균형한 부하 분산을 야기할 수 있다. 또한, 기본적인 알고리즘은 노드의 성능을 신경쓰지 않는다. 이런 문제를 해결하기 위해 다이나모는 여러 종류의 안정 해싱([10, 20]에서 사용한 것과 유사한 것)을 사용한다. 단순히 원 위에 하나의 점으로 노드를 매핑하는 것이 아니라, 각 노드에 여러 개의 위치를 배정하는 것이다. 이를 위해 다이나모는 “가상 노드”(virtual nodes)라는 개념을 사용한다. 가상 노드는 시스템에서 하나의 노드처럼 보이지만, 각 노드가 하나 이상의 가상 노드를 담당할 수 있으며, 새로운 노드를 시스템에 추가할 때 링에서 여러 위치(이하 “토큰”)가 할당된다. 다이나모의 파티셔닝 방식을 조율하는 과정에 대해서는 섹션 6에서 논의한다.

가상 노드에는 다음과 같은 이점이 있다:

• 장애나 정기적인 유지보수로 인해 노드를 사용할 수 없게 되면, 해당 노드가 처리하던 부하를 나머지 사용 가능한 노드들에게 고르게 분산할 수 있다.
• 노드가 복구되거나 새로운 노드가 시스템에 추가 된다면, 새 노드는 다른 노드로부터 대략 비슷한 양의 부하를 나눠받을 수 있다.
• 하나의 노드가 담당하는 가상 노드의 수는 물리적 인프라의 이질성을 고려하여 노드의 용량에 따라 결정할 수 있다.

복제

높은 가용성과 내구성을 달성하기 위해, 다이나모는 데이터를 여러 호스트에 복제한다. 각 데이터는 N개의 호스트에 복제되며, 이때 N은 “인스턴스마다”(per-instance) 설정되는 매개 변수다. 각각의 키, k는 이후 섹션에서 설명할 코디네이터 노드에게 할당된다. 코디네이터는 자신의 범위에 해당하는 데이터의 복제를 담당한다. 코디네이터는 범위 내의 키를 로컬에 저장할 뿐만 아니라, 링의 시계 방향에 있는 다음 N-1번째 노드의 키도 복제한다. 이렇게 하면 각 노드가 자신과 N번째 이전 노드 사이의 링 영역을 책임지는 시스템이 만들어진다. 그림 2에서, 노드 B는 노드 C와 D의 키 k를 복제해 로컬에 저장한다. 노드 D는 자신의 영역 (A, B], (B, C], (C, D]에 포함되는 키를 저장할 것이다.

특정 키의 저장을 담당하는 노드 목록을 선호 목록(preference list)이라고 한다. 섹션 4.8에서 설명하겠지만, 이 시스템은 모든 노드가 특정 키에 대해 선호 목록에 포함되어야 하는 노드를 결정할 수 있도록 설계되었다. 노드 장애를 관리하기 위해 선호 목록은 N개의 노드보다 많은 노드를 담고있다. 가상 노드를 사용하면 N개 미만의 개별적인 물리 노드가 특정 키에 대한 첫 번째 N개 위치를 소유하는 것이 가능하다. (즉, 노드가 첫 번째 N개 위치 중 하나 이상을 가질 수 있다.) 이를 해결하기 위해, 키에 대한 선호 목록은 링에서 위치를 건너뛰어 선호 목록에 고유한 물리 노드만 포함되도록 구성된다.

데이터 버저닝

다이나모는 모든 레플리카에게 업데이트를 비동기적으로 전파할 수 있는 최종 일관성을 제공한다. put() 명령은 모든 레플리카에게 업데이트가 반영되기 전에 값을 반환하며, 이로 인해 이후 실행되는 get() 명령은 최신 업데이트가 반영되지 않은 객체를 반환하는 경우가 발생할 수 있다. 오류가 없다면 업데이트 전파에 걸리는 시간 때문에 일시적으로 그런 상황이 일어날 수 있다. 그러나 특정 오류 시나리오(e.g., 서버 중단이나 네트워크 파티션)에서는 오랜 시간 동안 다른 레플리카에게 업데이트가 도달하지 않을 수 있다.

아마존 플랫폼에는 이러한 불일치와 조건에서도 동작할 수 있는 종류의 애플리케이션들이 있다. 예를 들어, 장바구니 애플리케이션은 “장바구니에 추가” 동작을 절대 누락하거나 거부할 수 없다. 만약 가장 최근 상태의 장바구니를 사용할 수 없는 상황에서 사용자가 구버전의 장바구니를 변경한다고 해도, 변경 사항이 의미있게 보존되어야 한다. 그러나 이것이 현재 장바구니의 상태를 대체해서는 안 되며, 이 상태 자체에는 보존해야 할 변경 사항이 포함될 수 있다. “장바구니에 추가” 동작과 “장바구니에서 제거” 동작 모두 put 요청으로 변환되어 다이나모에게 전송된다. 고객이 장바구니에 상품을 추가(또는 제거)할 때 최신 버전을 사용할 수 없다면 상품은 구버전의 장바구니에 추가(또는 제거)되고, 차후 다양한 버전이 중재(reconciliation)된다.

다이나모는 이러한 보장을 제공하기 위해 각 변경 사항의 결과를 데이터의 새로운 불변 버전으로 취급한다. 이는 시스템에 여러 버전의 객체가 동시에 존재할 수 있게 한다. 대부분의 경우 새 버전은 이전 버전을 포함하며, 시스템이 자체적으로 권위있는 버전을 결정할 수 있다. (신택틱 중재, syntatic reconciliation) 그러나 동시적인 업데이트를 포함한 장애가 발생하면 버전 분기가 일어나 객체 버전이 충돌할 수 있다. 이런 상황에서 시스템은 같은 객체에 대한 여러 버전을 중재할 수 없으며, 클라이언트가 데이터의 여러 분기를 다시 하나로 합치기(collapse) 위해 직접 중재를 수행해야 한다. (시맨틱 중재, semantic reconciliation) 데이터를 합치는 동작의 일반적인 예시로는 여러 버전의 장바구니를 “병합” 하는 방법이 있다. 이 중재 매커니즘을 사용하면 “장바구니에 추가” 동작이 절대로 누락되지 않는다. 그러나 장바구니에서 제거한 상품이 다시 노출될 수는 있다.

같은 데이터에 대해 여러 개의 버전을 만들게 되는 특정 장애를 이해하는 것이 중요하다. 네트워크 파티션이나 노드 장애 상황에서 업데이트를 수행하면 객체에 대한 부차적인 개별 버전 기록이 만들어지며, 시스템이 향후 이를 중재해야 한다. 어떠한 업데이트 동작도 누락하지 않기 위해, 같은 데이터에 대해 여러 버전이 존재할 가능성을 명시적으로 인식하는 애플리케이션을 설계해야 한다.

다이나모는 같은 객체의 여러 버전에 대한 인과성을 포착하기 위해 벡터 클럭[12]를 사용한다. 벡터 클럭은 효과적인 (노드, 카운터) 페어 목록이다. 하나의 벡터 클럭은 모든 객체의 모든 버전으로 이뤄진다. 벡터 클럭을 확인하면 객체의 두 버전이 평행한 브랜치에 있는지, 인과적인 순서를 가지고 있는지 알 수 있다. 만약 첫 번째 객체의 클럭에 있는 카운터 값이 두 번째 클럭에 있는 모든 노드의 카운터 값보다 작거나 같다면, 첫 번째 클럭이 두 번째 클럭의 이전 버전임을 알 수 있고, 지워질 수 있다. 그렇지 않다면, 두 가지 변경 사항이 충돌하는 것으로 간주해 중재가 필요해진다.

다이나모에서는 클라이언트가 객체를 업데이트하고자 할 때 어떤 버전을 업데이트할지 명시해야 한다. 이는 벡터 클럭 정보를 포함하는 이전 읽기 동작의 컨텍스트를 전달함으로써 수행된다. 읽기 요청을 수행할 때는, 만약 다이나모가 신택틱하게 중재할 수 없는 여러 개의 브랜치에 접근한다면 모든 객체를 그에 대응하는 컨텍스트 버전 정보와 함께 반환한다. 이 컨텍스트를 이용한 업데이트는 다양한 버전에 대한 중재가 필요한 것으로 고려되며, 브랜치는 하나의 새로운 버전으로 합쳐진다.

그림 3. 시간에 따른 객체의 버전 진화

벡터 클럭의 사용을 묘사하기 위해 그림 3을 예시로 볼 수 있다. 클라이언트가 새 객체를 추가한다. 이 키에 대한 쓰기를 다루는 노드(Sx)는 카운터를 증가시키고, 데이터의 벡터 클럭을 만드는 데 이를 사용한다. 이제 시스템에는 객체 D1과 여기에 연결된 클럭 [(Sx, 1)]이 생겼다. 이어서 클라이언트가 객체를 업데이트한다. 이에 대해 같은 노드가 요청을 다룬다고 가정하자. 이제 시스템에는 객체 D2와 여기에 연결된 클럭 [(Sx, 2)]이 생긴다. D2는 D1으로부터 비롯(descends)되었기 때문에 D1을 덮어씌우지만, 아직 D2를 보지 못해서 D1의 레플리카를 가진 노드가 있을 수 있다. 또 이어서 같은 클라이언트가 객체를 다시 업데이트하고, 다른 서버(Sy)가 이 요청을 다룬다고 가정해보자. 이제 시스템에는 객체 D3와 여기에 연결된 클럭 [(Sx, 2), (Sy, 1)]이 생긴다.

다음으로 다른 클라이언트가 D2를 읽고 이를 업데이트하려 한다. 이때 요청을 다루는 것은 또 다른 노드(Sz)라고 가정하자. 이제 시스템에는 D2로부터 비롯된 객체 D4와 여기에 연결된 클럭 [(Sx, 2), (Sz, 1)]이 생긴다. D1이나 D2를 인지하는 노드는 D4와 그 클럭을 받았을 때 D1과 D2를 새로운 데이터로 덮어씌우고, 가비지 컬렉팅하도록 결정할 수 있다. D3를 인지하고 D4를 받은 노드는 D3와 D4 사이에 인과적 관계가 없음을 알 수 있을 것이다. 즉, D3와 D4에는 서로의 내용을 반영하지 않은 변경 사항이 있다. 두 버전의 데이터는 시맨틱 중재를 위해 모두 유지해야 하며, 클라이언트가 객체를 읽을 때 보여줘야 한다.

이제 어떤 클라이언트가 D3와 D4를 모두 읽는다고 가정하자. (컨텍스트는 읽기 동작에 의해 발견되는 두 값을 모두 반영한다.) 읽기 동작의 컨텍스트는 D3와 D4에 연결된 클럭의 요약본이며, [(Sx, 2), (Sy, 1), (Sz, 1)]으로 명명된다. 이때 클라이언트가 중재를 수행하고, 노드 Sx가 중재로 인한 쓰기 동작을 다룬다면 Sx는 클럭의 카운터 숫자를 업데이트한다. 이렇게 만들어진 새로운 데이터 D5는 [(Sx, 3), (Sy, 1), (Sz, 1)] 클럭을 갖게 될 것이다.

벡터 클럭에서 일어날 수 있는 문제는, 많은 양의 서버가 객체에 대한 쓰기 동작을 다루면서 벡터 클럭의 크기가 증가할 수 있다는 것이다. 관습적으로는 보통 선호 목록의 상위 N개 노드 중 하나가 쓰기 동작을 다루기 때문에 쉽게 발생하는 문제는 아니다. 다만 네트워크 파티션이나 여러 서버가 장애를 일으킨 상황에서는 상위 N개 노드가 아닌 다른 노드들이 쓰기 동작을 처리하여 벡터 클럭의 크기가 커질 수 있다. 이런 시나리오에서는 벡터 클럭의 크기를 제한해야 한다. 따라서 다이나모는 클럭 절단(truncation) 방식을 사용한다. 다이나모는 각각의 (노드, 카운터) 페어와 함께, 데이터를 마지막으로 수정한 타임스탬프를 함께 저장한다. 벡터 클럭의 (노드, 카운터) 페어 개수가 임계치(가령 10개)에 다달았다면, 오래된 페어를 클럭에서 제거한다. 이러한 절단 방식에서는 후손 관계를 정확히 도출할 수 없기 때문에 분명히 중재의 비효율을 야기할 수 있다. 하지만 그런 문제는 프로덕션 환경에서 일어나지 않았고, 철저히 조사되지도 않았다.

get(), put() 명령의 실행

다이나모의 모든 저장소 노드는 키에 대한 get 또는 put 명령을 받을 수 있다. 이 섹션에서는 단순한 설명을 위해, 장애가 없는 환경에서 이러한 명령을 실행하는 방법에 대해 설명하고, 다음 섹션에서는 장애 발생 시 읽기 및 쓰기 명령을 실행하는 방법에 대해 설명한다.

get, put 명령은 모두 HTTP를 통한 아마존의 인프라별 요청 처리 프레임워크를 사용해 호출된다. 클라이언트가 노드를 선택하기 위해 사용할 수 있는 두 가지 전략이 있다: (1) 부하 정보에 기반해 노드를 선택하는 범용 로드밸런서를 통해 요청을 라우팅하거나, (2) 요청을 적절한 코디네이터 노드로 직접 라우팅하는 파티션 인식(partition-aware) 클라이언트 라이브러리를 사용한다. 첫 번째 접근법의 장점은 클라이언트가 애플리케이션에서 다이나모에 특정한 코드를 연결할 필요가 없다는 것이다. 두 번째 전략의 장점은 잠재적인 전달 단계를 건너뛰기 때문에 더 낮은 레이턴시를 달성할 수 있다는 점이다.

읽기나 쓰기 명령을 수행하는 노드를 코디네이터(coordinator)라고 한다. 일반적으로, 선호 목록의 상위 N개 노드 중 첫 번째 노드가 코디네이터로 선택된다. 로드밸런서를 통해 키에 접근하는 요청을 받으면, 링의 랜덤한 노드에게 라우팅될 것이다. 이 시나리오에서는 요청을 받은 노드가 선호 목록의 상위 N개에 포함되지 않는다면 요청을 처리하지 않는다. 대신 요청을 받은 노드가 선호 목록의 상위 N개 노드 중 첫 번째 노드에게 요청을 전달한다.

읽기, 쓰기 동작에는 선호 목록에 있는 N개의 정상 노드 중 첫 번째 노드가 관여하며, 중단되었거나 접근할 수 없는 노드는 건너뛴다. 모든 노드가 정상적일 때는 키의 선호 목록에 있는 상위 N개 노드에 접근한다. 노드 장애 또는 네트워크 파티션이 있는 경우에는 선호 목록에서 순위가 낮은 노드에 접근한다.

레플리카의 일관성을 관리하기 위해 다이나모는 정족수 시스템에서 사용되는 것과 유사한 일관성 프로토콜을 사용한다. 이 프로토콜은 두 개의 설정 가능한 키 R과 W를 가지고 있다. R은 성공적인 읽기 동작에 참여할 최소 노드 개수를 의미한다. W는 성공적인 쓰기 동작에 참여할 최소 노드 개수를 의미한다. R과 W 값을 설정함으로써 R + W > N을 정족수 시스템처럼 만들 수 있다. 이 모델에서 get(또는 put) 명령의 레이턴시는 R(또는 W)개의 레플리카 중 가장 느린 레이턴시에 따른다. 따라서 더 나은 레이턴시를 제공하기 위해 보통 R과 W는 N보다 작게 설정한다.

키에 대한 put() 요청을 받으면 코디네이터는 새로운 버전을 위한 벡터 클럭을 생성하며, 새 버전을 로컬에 저장해둔다. 이어서 코디네이터는 새 버전(새 벡터 클럭과 함께)을 N개의 도달 가능한 상위 노드들에게 전송한다. 만약 최소 W-1개의 노드가 응답한다면 쓰기가 성공한 것으로 간주한다.

get() 요청도 마찬가지로, 코디네이터가 선호 목록에 있는 N개의 도달 가능한 상위 노드들에게 키에 대응하는 데이터의 모든 버전을 요청하고, R개 노드의 응답을 기다린 뒤 그 결과를 클라이언트에게 반환한다. 코디네이터가 데이터의 여러 버전을 모으면, 인과관계가 없다고 취급되는 모든 버전을 반환한다. 이어서 다양한 버전이 중재되며, 현재 버전을 대체하는 중재된 버전이 다시 저장된다.

장애 다루기: 임시 위탁

다이나모가 전통적인 정족수 접근법을 사용했다면 서버 장애나 네트워크 파티션에 대응하지 못했을 것이며, 가장 단순한 장애 조건에서도 내구성이 저하되고 말았을 것이다. 이를 해결하기 위해 다이나모는 엄격한 정족수 멤버십을 강제하는 대신, “느슨한 정족수”(sloppy quorum)를 사용한다. 느슨한 정족수에서는 모든 읽기 및 쓰기 동작을 선호 목록의 정상적인 N개의 노드 중 첫 번째 노드가 수행한다. 다만 해싱 링을 순회하는 동안 만나는 노드가 항상 첫 번째 노드는 아닐 수 있다.

그림 2에서 다이나모에 설정된 N 값이 3이라고 생각해보자. 여기서 노드 A가 쓰기 동작 도중에 일시적으로 다운되거나 접근할 수 없게 된다면 A에 존재했던 레플리카가 노드 D로 전송된다. 이렇게 하면 가용성과 내구성을 보장할 수 있다. 노드 D로 보내진 레플리카는 메타데이터에 어떤 노드가 원래 수신자(여기서는 노드 A)였는지 암시하는 단서를 포함하고 있다. 임시 위탁된 레플리카를 수신하는 노드는 주기적으로 스캔되는 별도의 로컬 데이터베이스에 레플리카를 보관한다. 노드 A가 복구되었음을 감지하면, 노드 D는 레플리카를 노드 A에게 전달한다. 전송이 성공적으로 끝나면, 노드 D는 로컬 저장소에서 객체를 제거한다. 이때 시스템의 전체 레플리카 수는 줄어들지 않는다.

다이나모는 임시 위탁(hinted handoff)을 통해 노드나 네트워크의 일시적인 장애에도 읽기 및 쓰기 동작이 실패하지 않도록 한다. 높은 수준의 가용성을 필요로 하는 애플리케이션은 W 값을 1로 설정함으로써 시스템의 단일 노드가 로컬 저장소에 키를 쓸 수 있는 한 쓰기 동작을 허용할 수 있다. 따라서 쓰기 요청은 시스템의 모든 노드가 사용 불가능할 때만 거부된다. 그러나, 대부분의 아마존 서비스는 높은 수준의 내구성 요구를 충족하기 위해 더 높은 W 값을 설정한다. N, R, W 값의 설정에 대한 더 자세한 논의는 섹션 6에서 다룬다.

고가용성 저장소 시스템은 모든 데이터 센터의 장애를 다룰 수 있어야 한다. 데이터 센터 장애는 정전이나 냉각 문제, 네트워크 장애, 자연 재해로 인해 발생할 수 있다. 다이나모는 여러 데이터 센터에 걸쳐 객체를 복제한다. 본질적으로 키에 대한 선호 목록은 저장소 노드가 여러 데이터 센터에 분산되도록 만들어진다. 이 데이터센터들은 빠른 속도의 네트워크 링크를 통해 연결된다. 이렇게 여러 데이터센터에 레플리카를 분산하면 데이터 단절없이 전체 데이터 센터 장애를 처리할 수 있다.

영구적인 장애 다루기: 레플리카 동기화

임시 위탁은 시스템 멤버십 전환율이 낮고, 노드 장애가 일시적일 때 가장 잘 작동한다. 임시 위탁한 레플리카가 원본 레플리카 노드에게 값을 반환하기 전에 사용할 수 없는 상태가 되는 경우가 있다. 내구성에 대한 이러한 위협을 처리하기 위해 다이나모는 레플리카 동기화를 유지하는 안티 엔트로피(레플리카 동기화) 프로토콜을 구현한다.

레플리카 사이의 불일치를 빠르게 감지하기 위해, 그리고 전송 데이터의 양을 최소화하기 위해 다이나모는 머클 트리[13]를 사용한다. 머클 트리는 리프 노드가 개별 키에 대한 값의 해시인 해시 트리이다. 이때 부모 노드는 각 자식 노드의 해시다. 머클 트리의 이점은 노드가 전체 데이터셋이나 전체 트리를 다운로드하지 않고 독립적으로 트리의 각 브랜치를 확인할 수 있다는 점이다. 뿐만 아니라, 머클 트리는 레플리카 간의 불일치를 확인하기 위해 필요한 데이터 전송량을 줄이는 데도 도움이 된다. 예를 들어, 두 트리의 루트 노드 해시 값이 같다면, 리프 노드도 같을 것이기 때문에 동기화가 필요하지 않다. 그렇지 않다면 일부 레플리카의 값이 다르다는 의미다. 이런 경우에 노드는 자식 노드의 해시 값을 교체하고, 트리의 리프 노드에 도달할 때까지 해시를 비교하며 어떤 키가 동기화되지 않았는지 알 수 있다. 머클 트리는 동기화에 필요한 데이터 전송량과 안티 엔트로피 과정 중 일어나는 디스크 읽기 횟수를 줄여준다.

다이나모는 안티 엔트로피를 위해 머틀 트리를 사용한다. 각 노드는 호스트의 키 범위(가상 노드의 범위에 있는 키 집합)에 따라 분리된 머클 트리를 관리한다. 이렇게 하면 노드가 키 범위 내에 있는 키들이 최신(up-to-date)인지 비교할 수 있다. 이때 두 노드는 공통적으로 호스팅되는 키 범위에 해당하는 머클 트리의 루트 노드를 교환한다. 이어서, 노드들은 앞서 설명한 트리 순회 방식을 통해 차이가 있는지 확인하고 절절한 동기화 작업을 수행한다. 이 방식의 단점은 새 노드를 시스템에 추가하거나, 기존 노드를 제거할 때 많은 키 범위가 변경되므로 트리를 다시 계산해야 한다는 점이다. 그러나 이 문제는 섹션 6.2에 설명할 정제된(refined) 파티셔닝 방식으로 해결할 수 있다.

멤버십과 장애 감지

링 멤버십

아마존 환경에서 장애 또는 유지보수 작업으로 인한 노드 중단은 대체로 일시적이지만, 지속 기간이 연장될 수도 있다. 노드 중단이 노드의 영구적인 제거를 의미하는 경우는 거의 없기 때문에 파티션 할당의 재조정이나 도달 불가능한 레플리카의 복구로 이어져서는 안 된다. 비슷하게, 수동 오류는 의도치 않은 새 다이나모 노드를 시작하게 만들 수 있다. 이러한 이유로 다이나모 링에서 노드의 추가 및 제거를 초기화하기 위해 명시적인 메커니즘을 사용하는 것이 적절하다고 여겨졌다. 관리자는 새 노드를 추가하거나 기존 노드를 제거하기 위해 멤버십 변경을 시도하며, 커맨드라인 도구나 브라우저를 이용하여 다이나모 노드에 접속할 수 있다.

쓰기 요청을 처리하는 노드는 멤버십 변경을 수행하며, 변경 시간을 영속적 저장소에 저장해둔다. 노드가 여러차례 제거되거나 다시 추가될 수 있기 때문에 멤버십 변경은 히스토리를 만들게 된다. 가십 기반 프로토콜은 멤버십 변경을 전파하고, 멤버십의 측면에서 최종 일관성을 유지한다. 각 노드는 매 초마다 랜덤한 다른 노드에 접근하며, 두 노드는 지속적으로 멤버십 변경 기록을 동기화한다.

노드가 처음 시작될 때, 토큰 집합(안정 해시 공간의 가상 노드들)을 선택하고 노드를 그에 대응하는 토큰 집합에 매핑한다. 매핑은 디스크에 기록되며, 처음에는 로컬 노드와 토큰 집합만 기록된다. 다른 다이나모 노드에 저장된 매핑은 통신을 통해 중재된다. 따라서 파티셔닝과 위치 정보는 가십 기반 프로토콜을 통해 전파되며, 각 저장소 노드는 다른 노드가 처리하는 토큰 범위를 알게 된다. 이를 통해 각 노드는 키의 읽기, 쓰기 작업을 올바른 노드들에게 직접 전달할 수 있다.

외부 발견

위에서 설명한 메커니즘은 일시적으로 다이나모 링을 논리적 분단 상태로 만들 수 있다. 예를 들어, 관리자가 노드 A를 링에 추가하기 위해 A에 접근하고, 노드 B를 링에 추가하기 위해 B에도 접근한다고 생각해보자. 이 시나리오에서 노드 A와 B는 각자가 링의 멤버라고 생각하겠지만, 둘 다 서로를 즉시 인식하지는 못한다. 논리적 분단을 방지하기 위해 일부 다이나모 노드는 시드(seed)의 역할을 맡는다. 시드는 외부 메커니즘을 통해 발견되며, 모든 노드에게 알려져 있는 노드다. 모든 노드가 최종적으로 시드를 통해 자신의 멤버십을 확인하기 때문에 논리적 분단을 거의 일어나지 않는다. 시드는 정적인 설정으로 정할 수도 있고, 설정 서비스를 통해 정할 수도 있다. 일반적으로 시드는 다이나모 링에서 완전하게 동작할 수 있는 노드이다.

장애 감지

다이나모에서의 장애 감지는 get()이나 put() 명령 실행 중, 또는 파티션 및 임시 위탁된 레플리카를 전송할 때 사용 불가능한 노드와 통신하지 않기 위해 사용한다. 통신 실패를 방지하기 위한 목적으로는, 순수하게 국소적인 장애 감지 개념만으로도 충분하다. 가령 노드 A는 노드 B가 노드 A의 메시지에 응답하지 않으면(노드 B가 노드 C에게 응답했다고 해도) 노드 B에 장애가 발생한 것으로 취급한다. 다이나모 링에서 노드 간 통신을 일으키는 클라이언트 요청이 일정하게 있는 경우, 노드 A는 노드 B가 응답할 수 없는 상태라는 것을 빠르게 발견할 수 있다. 이후 노드 A는 대체 노드를 통해 노드 B의 파티션에 매핑되는 요청을 처리한다. 노드A는 주기적으로 노드 B에게 요청을 보내 복구를 확인한다. 두 노드 간의 트래픽을 일으키는 클라이언트 요청이 없는 경우에는 두 노드 모두 서로가 응답할 수 있는 상태인지 확인할 필요가 없다.

분산된 장애 감지 프로토콜은 단순한 가십 스타일 프로토콜을 사용한다. 가십 프로토콜은 시스템의 각 도느가 다른 노드의 추가 또는 제거를 서로 알 수 있게 해준다. 분산 장애 감지와 정확도에 영향을 미치는 인자에 대한 자세한 내용은 [8]을 참조한다. 다이나모의 초기 설계에서는 전체적으로 일관된 장애 상태를 관리하기 위해 분산 장애 감지를 사용했다. 나중에는 노드의 명시적인 추가 및 제거 방식이 장애 상태에 대한 전역적인 감지의 필요성을 없앤다는 것이 밝혀졌다. 노드의 명시적인 추가 및 삭제 방식으로 노드들이 알림을 받고, 요청을 전달하는 동안 다른 노드와 통신하지 못할 때 개별 노드가 일시적인 노드 장애를 감지하기 때문이다.

저장소 노드 추가 및 제거

시스템에 새로운 노드(X)가 추가될 때, 링 위에 랜덤하게 흩어진 토큰들이 배정된다. 노드 X에게 배정된 모든 키 범위에 대해, 이미 같은 범위를 담당하는 여러 노드(N 이하의 수)가 있을 수 있다. 키 범위가 노드 X에게 할당되기 때문에, 일부 기존 노드는 더 이상 자신의 키를 유지할 필요가 없어지며, 일부 키를 노드 X에게 전송한다. 그림 2의 링에 있는 노드 A와 B 사이에 노드 X가 새롭게 추가되는 간단한 부트스트래핑 시나리오를 생각해보자. 노드 X가 시스템에 추가되면, 키 범위 (F, G], (G, A], (A, X]를 책임지게 된다. 동시에 노드 B, C, D는 더 이상 이 범위의 키를 저장할 필요가 없어진다. 따라서 노드 B, C, D는 노드 X의 확인에 따라 적절한 키들을 전송한다. 시스템에서 노드를 제거하면 이 과정의 역순으로 키가 재할당된다.

실제 운영 경험에 따르면, 이 접근 방식은 빠른 부트스트래핑을 보장하는 데 중요한 레이턴시 요구사항을 총족하고 키 배포에 따른 부하를 저장소 노드에 균일하게 분산시켜준다. 마지막으로 소스 노드와 대상 노드 사이에 확인 절차를 추가하여 대상 노드가 지정된 키 범위에 대해 중복 전송을 받지 않도록 한다.

구현

다이나모의 각 저장소 노드에는 세 가지 중요한 소프트웨어 컴포넌트가 있다: 요청 처리, 멤버십, 장애 감지, 로컬 영속성 엔진이 그것이다. 이 모든 컴포넌트가 자바로 구현되어 있다.

다이나모의 로컬 영속성 컴포넌트는 다른 저장소 엔진을 플러그인으로 적용할 수 있게 해준다. 이때 엔진은 Berkeley Database(BDB) Transactional Data Store^[2], BDB Java Edition, MySQL, 영속적 저장소와 함께 사용하는 인메모리 버퍼다. 플러그인 사용 가능한(pluggable) 영속적 컴포넌트를 설계한 주요 이유는 애플리케이션의 접근 패턴에 따라 최적의 저장소 엔진을 고를 수 있게 하기 위함이다. 예를 들어, BDB는 수십 킬로바이트 단위로 객체를 처리할 수 있는 반면 MySQL은 더 큰 크기의 객체를 처리할 수 있다. 애플리케이션은 객체 크기 분포에 따라 다이나모의 로컬 영속성 엔진을 선택한다. 프로덕션 환경의 다이나모 인스턴스는 주로 BDB Transactional Data Store를 사용한다.

요청 처리 컴포넌트는 SEDA 아키텍처[24]처럼 여러 단계로 나뉜 메시지 처리 파이프라인의 이벤트 주도(event-driven) 메시징 서브트레이트(subtrate) 위에 구축되어 있다. 모든 통신은 자바 NIO 채널을 이용해 구현된다. 코디네이터는 하나 이상의 노드에서 데이터를 얻거나(읽기), 하나 이상의 노드에 데이터를 저장하여(쓰기) 클라이언트 대신 쓰기 및 읽기 요청을 실행한다. 각각의 클라이언트 요청은 요청을 받은 노드에 상태 기계(state machine)을 생성한다. 상태 기계는 키 담당 노드 식별, 요청 전송, 응답 대기, 잠재적인 재시도, 응답 처리, 클라이언트로의 패키징에 대한 모든 논리를 포함하고 있다. 각 상계 기계 인스턴스는 하나의 클라이언트 요청을 처리한다. 예를 들어, 읽기 동작은 다음과 같은 상태 기계를 구현한다: (i) 노드에게 읽기 요청을 전송한다, (ii) 최소한의 응답을 대기한다, (iii) 정해진 시간 안에 너무 적은 응답을 받았다면 요청을 실패 처리 한다, (iv) 아니라면 모든 데이터 버전을 모으고, 반환할 하나를 정한다, (v) 만약 버저닝이 활성화되어 있다면, 신택틱 중재를 수행하고 모든 버전에 대한 벡터 클럭을 포함하는 쓰기 컨텍스트를 생성한다. 간결한 설명을 위해 장애 처리와 재시도 상태는 생략했다.

호출자에게 읽기 응답이 반환된 뒤에는, 상태 기계가 아직 처리되지 않은(outstanding) 응답을 받기 위해 짧은 시간 동안 대기한다. 오래된 버전이 응답된 경우 코디네이터는 해당 노드들을 최신 버전으로 업데이트한다. 이 과정을 읽기 복구라고 부르는데, 이는 기회가 주어진 시점에 최근 업데이트를 놓친 레플리카를 복구함으로써, 안티 엔트로피 프로토콜을 수행할 필요가 없도록 하기 때문이다.

앞서 언급했듯이, 쓰기 요청은 선호 목록의 상위 N개 노드 중 하나가 처리한다. 항상 상위 N개 노드 중 첫 번째 노드가 쓰기 동작을 처리하여 모든 쓰기 동작을 단일 지점에서 직렬화하는 것이 바람직하지만, 이 접근 방식은 부하 분산이 불균일하게 이뤄지게 함으로써 SLA 위반을 초래한다. 요청 부하가 여러 객체에 고르게 분포하지 않기 때문이다. 이 문제에 대응하기 위해, 선호 목록의 상위 N개 노드가 모두 쓰기 동작을 처리할 수 있도록 한다. 특히 쓰기 동작은 보통 읽기 명령 직후 일어나기 때문에, 쓰기를 처리하는 코디네이터는 요청의 컨텍스트 정보에 담긴 이전 읽기 동작에 대해 가장 빨리 응답한 노드로 선택된다. 이러한 최적화를 통해 이전 읽기 동작에서 읽은 데이터가 있는 노드를 선택할 수 있으므로, “쓰기 후 읽기”(read-your-writes) 일관성을 얻을 가능성이 높아진다. 또한 요청 처리 성능의 변동성을 줄여 99.9 분위에서 성능을 향상시킬 수 있다.

경험 및 교훈

다이나모는 다양한 서비스에서 각자의 설정에 따라 사용되었다. 다이나모 인스턴스에 따라 버전 중재 로직이나 읽기/쓰기 정족수 특성이 다르다. 다음은 다이나모가 사용되는 주요 패턴이다:

• 비즈니스 로직에 따른 중재: 자주 사용되는 패턴이다. 각 데이터 오브젝트는 여러 노드에 걸쳐 복제되며, 클라이언트 애플리케이션이 자신의 중재 로직으로 다양한 버전을 중재한다. 앞서 논의한 장바구니 서비스는 이 분류의 주요 예시다. 여기서 비즈니스 로직은 고객 장바구니의 여러 버전을 병합하는 방식으로 중재한다.
• 타임스탬프 기반 중재: 위의 패턴에서 중재 메커니즘만 다른 패턴이다. 다이나모가 다양한 버전에 대해 단순한 타임스탬프 기반 중재 로직을 수행하여 "최종 쓰기 승리"를 적용한다. 즉, 가장 큰 타임스탬프 값을 가진 객체가 올바른 버전으로 선택되는 것이다. 고객 세션 정보를 관리하는 서비스가 이 분류의 좋은 예시다.
• 고성능 읽기 엔진: 다이나모가 “항상 쓰기 가능한” 데이터 저장소로 구축되었지만, 일부 서비스들은 정족수 특성을 조정해 다이나모를 고성능 읽기 엔진으로 사용한다. 이런 서비스들은 보통 대량의 읽기 요청을 받으며, 업데이트 요청은 적은 양만 받는다. R 값은 주로 1로 설정하며, W 값은 N 값과 동일하게 설정한다. 다이나모는 이러한 서비스들에게 파티셔닝과 여러 노드로의 레플리카 분산을 지원하므로써 확장성을 높여준다. 인스턴스 중 일부는 더 무거운 백업 저장소에 있는 데이터에 대한 권위있는 영속성 캐시로 동작한다. 상품 카탈로그나 프로모션 상품을 관리하는 서비스가 이 분류에 적합하다.

다이나모의 주요 장점은 클라이언트 애플리케이션이 자신의 성능, 가용성, 내구성 요구 수준에 맞는 N, R, W 값을 설정할 수 있다는 점이다. 가령 N 값은 각 객체의 내구성을 결정한다. 일반적으로 다이나모 사용자들은 N 값을 3으로 설정한다.

W와 R 값은 객체의 가용성과 내구성, 일관성에 영향을 미친다. 예를 들어 W 값을 1로 설정하면 시스템은 최소 하나의 노드가 쓰기 동작을 성공적으로 처리할 수 있을 때까지 최대한 쓰기 요청을 거부하지 않을 것이다. 그러나 W나 R 값을 낮게 설정하면 대다수의 레플리카가 요청을 처리하지 않았음에도 요청을 성공한 것으로 간주하여 클라이언트에게 응답을 보내게 되므로, 불일치 위험이 증가할 수 있다. 이는 적은 수의 노드에서만 쓰기 동작이 처리됐음에도 불구하고 클라이언트에게는 요청이 성공한 것으로 응답하여 취약점 윈도우를 야기할 수 있다.

전통적인 지혜에 따르면 내구성과 가용성은 밀접하게 연관되어 있다. 하지만 여기서는 그것이 항상 사실은 아니다. 내구성에 대한 취약점 윈도우는 W 값을 높임으로써 낮출 수 있다. 다만 이렇게 하면 더 많은 저장소 호스트가 쓰기 요청을 처리하기 위해 정상적인 상태를 유지해야 하므로, 요청을 거부할 가능성이 높아질 수 있다. (따라서 가용성이 낮아진다.)

(N, R, W) 설정은 많은 다이나모 인스턴스에서 일반적으로 (3, 2, 2)으로 사용된다. 이 값은 SLA에서 요구하는 수준의 성능, 내구성, 일관성, 가용성을 충족하기 위한 것이다.

이 섹션에 나오는 모든 측정치는 동종(homogenous) 하드웨어 구성으로 수백 개의 노드를 실행하는 라이브 시스템에서 얻어진 것이며, 이 시스템은 (3, 2, 2) 구성으로 작동한다. 앞서 언급했듯이 각각의 다이나모 인스턴스에는 다양한 데이터센터에 위치한 노드들이 포함되어 있다. 이 데이터센터들은 보통 고속 네트워크 링크로 연결되어 있다. 성공적인 get (또는 put) 응답을 만들기 위해 R(또는 W) 노드들이 코디네이터에게 응답해야 한다는 점을 상기하자. 데이터센터 사이의 네트워크 레이턴시는 응답 시간에 영향을 미치며, 노드(그리고 해당 데이터센터의 위치)는 애플리케이션이 목표하는 SLA를 충족하도록 선택된다.

성능과 내구성의 균형

다이나모의 설계 원칙이 고가용성 데이터 저장소지만, 아마존 플랫폼에서는 성능 역시 똑같이 중요한 기준이다. 일관된 고객 경험을 제공하기 위해 아마존 서비스는 성능 목표를 높은 백분위수(99.9 또는 99.99 분위)로 설정한다. 다이나모를 사용하는 서비스의 일반적인 SLA는 99.9%의 읽기, 쓰기 요청을 300ms 안에 처리해야 한다.

그림 4. 2006년 12월 피크 시즌 중 일어난 읽기, 쓰기 요청에 대한 99.9 분위 및 평균 레이턴시. x축의 연속된 눈금 사이 간격은 12시간에 해당한다. 레이턴시는 요청 규모에 비례하는 패턴을 따르며, 99.9 분위의 레이턴시는 평균보다 더 높다.

다이나모는 하이엔드 엔터프라이즈 서버보다 I/O 처리량이 훨씬 적은 표준 범용 하드웨어 컴포넌트 위에서 동작하기 때문에 읽기, 쓰기 작업에 일관되게 높은 성능을 제공하는 것은 쉬운 작업이 아니다. 심지어 여러 스토리지 노드가 읽기, 쓰기 동작을 수행하면 가장 느린 R 또는 W 레플리카에게 성능이 제한되기 때문에 더욱 어려워진다. 그림 4는 30일간 다이나모에서 일어난 읽기, 쓰기 동작에 대한 99.9 분위 및 평균 레이턴시를 보여준다. 그림에서 볼 수 있듯이 레이턴시는 들어오는 요청 규모와 같은 패턴을 이룬다. (따라서 낮과 밤 사이의 요청 규모에 유의미한 차이가 있다.) 더 나아가, 쓰기 동작은 항상 디스크 접근을 필요로 하기 때문에 쓰기 레이턴시가 읽기 레이턴시보다 확실히 높게 나타난다. 또한 99.9 분위 레이턴시는 약 200ms로 평균보다 10배 이상 높다. 이는 99.9 분위의 레이턴시가 요청 부하와 객체 크기, 지역성 패턴의 변동성과 같은 여러 요인에 의해 영향을 받기 때문이다.

대부분의 서비스들이 이 정도 성능 수준을 허용할 수 있지만, 일부 고객 대면 서비스들은 더 높은 기준의 성능 수준을 요한다. 이러한 서비스를 위해 다이나모는 내구성 보장을 성능과 트레이드오프할 수 있는 기능을 제공한다. 최적화에서 각각의 저장소 노드는 메인 메모리에 객체 버퍼를 관리한다. 각 쓰기 동작은 버퍼에 저장되며, 쓰기 스레드(writer thread)가 이를 주기적으로 저장소에 기록한다. 이 방식에서 읽기 동작은 우선 요청된 키가 버퍼에 있는지 확인한다. 만약 버퍼에 키가 있다면, 저장소 엔진이 아닌 버퍼에서 객체를 읽는다.

그림 5. 99.9 분위에서 24시간 동안 버퍼가 있는 쓰기 동작과 버퍼가 없는 쓰기 동작사이의 성능 비교. x축의 연속된 눈금 사이 간격은 1시간에 해당한다.

이러한 최적화 덕분에 1천개 객체의 매우 작은 버퍼로도 피크 트래픽 중에 99.9 분위에서 레이턴시를 5배 낮출 수 있었다. (그림 5 참고) 또한 그림에서 볼 수 있듯이, 쓰기 버퍼링은 높은 백분위수에서 레이턴시를 완화한다. 이 방식은 내구성을 성능과 맞바꾸기 때문에 서버 장애가 발생하면 버퍼에 큐된 쓰기 명령이 유실될 수 있다. 내구성 위험을 줄이기 위해 코디네이터는 N개의 레플리카 중에서 하나를 선택해 “내구성 쓰기”(durable write)를 수행하도록 쓰기 동작을 처리한다. 이때 코디네이터는 W개의 응답만을 기다리기 때문에 쓰기 동작의 성능은 하나의 레플리카에서 이뤄지는 내구성 쓰기의 성능에 영향받지 않는다.

균일한 부하 분산 보장

다이나모는 안정 해싱을 사용해 레플리카 간에 키 공간을 파티셔닝하고, 균일한 부하 분산을 보장한다. 균일한 키 분포은 키에 대한 접근 분포가 크게 왜곡(skewed)되지 않았다고 가정할 때 균일한 부하 분포를 달성하는 데 도움을 줄 수 있다. 특히 다이나모의 설계는 접근 분포에 상당한 왜곡이 있는 상황에서도 인기있는 키가 충분히 분산되어 있다고 가정하므로, 키를 처리하는 부하가 파티셔닝을 통해 여러 노드에 균일하게 분산될 수 있다. 이 섹션에서는 다이나모에서 볼 수 있는 부하 불균형 및 다양한 파티셔닝 전략이 부하 분포에 미치는 영향에 대해 설명한다.

그림 6. 불균형 상태 노드(시스템 평균 부하에서 특정 임계치를 초과하는 요청 부하를 받는 노드)와 이에 대응하는 요청 부하의 비율. x축의 연속된 눈금 사이 간격은 30분에 해당한다.

부하 불균형과 요청 부하와의 상관관계를 연구하기 위해 각 노드가 받은 총 요청 수를 24시간 측정해 30분 간격으로 분석했다. 주어진 시간 윈도우에서, 만약 노드의 요청 부하가 특정 임계치(여기서는 15%)보다 낮은 값만큼만 평균 부하에서 벗어났다면 해당 노드를 “균형 상태”(in-balance)로 간주한다. 그렇지 않은 노드는 “불균형 상태”(out-of-balance)로 취급한다. 그림 6은 "불균형 상태"인 노드의 비율(이하 “불균형 비율”)을 보여준다. 참고로, 이 기간 동안 전체 시스템이 받은 요청 부하도 보여준다. 그림에서 볼 수 있듯이, 불균형 비율은 부하가 증감함에 따라 감소한다. 예를 들어 낮은 부하에서는 불균형 비율이 20%까지 높아졌고, 높은 부하에서는 10%에 가까워졌다. 직관적으로, 이는 높은 부하에서 많은 수의 인기 있는 키에 접근이 일어나며, 키의 균일한 분배 덕분에 부하가 고르게 분산된다고 볼 수 있다. 그러나 낮은 부하 상황(피크에서 측정된 부하의 1/8)에서는 인기있는 키에 더 적은 접근이 발생하며, 높은 부하 불균형으로 이어진다.

이 섹션에서는 시간이 지남에 따라 다이나모가 스키마를 어떻게 파티셔닝하는지, 또 부하 분포에는 어떤 영향을 미치는지 설명한다.

그림 7. 세 전략에서의 키 배치와 파티셔닝. A, B, C는 안정 해싱 링(N=3)에서 키 k1에 대한 선호 목록을 형성하는 세 개의 고유한 노드를 의미한다. 빗금 영역은 선호 목록의 노드 A, B, C가 담당하는 키 범위를 나타낸다. 어두운 화살표는 다양한 노드에 대한 토큰 위치를 가리킨다.

전략 1: 토큰 값에 따른 파티션과 노드별 T개의 랜덤 토큰: 이는 프로덕션에 배포된 초기 전략이었다. (그리고 섹션 4.2에 설명한 전략이기도 하다.) 이 방식에서 각 노드에는 T개의 토큰이 배정된다. (해시 공간에서 균일하게 랜덤 선택된다.) 모든 노드의 토큰은 해시 공간에 있는 각자의 값에 따라 정렬되며, 두 개의 연속된 토큰은 범위를 정의한다. 마지막 토큰과 첫 번재 토큰은 해시 공간에서 가장 높은 값부터 가장 낮은 값까지를 포괄하는 범위를 형성한다. 토큰들이 랜덤하게 선택되기 때문에 범위의 크기는 다양해진다. 시스템에 노드가 들어오고 나가며 토큰 셋이 변경되고, 결과적으로 범위가 변경된다. 각 노드의 멤버십을 유지하는 데 필요한 공간은 시스템의 노드 수에 따라 선형적으로 증가한다.

이 전략에는 다음과 같은 문제들을 직면할 수 있다. 먼저 새로운 노드가 시스템에 추가될 때, 새 노드는 다른 노드로부터 키 범위를 "훔쳐야"한다. 그러나 자신의 키 범위를 새 노드에게 넘겨주는 노드들은 적절한 데이터셋을 찾기 위해 자신의 로컬 저장소를 스캔해야 한다. 스캔은 리소스를 크게 소모하는 동작이기 때문에 노드가 프로덕션 환경에서 스캔 동작을 수행하는 것은 곤란한 일이다. 고객 성능에 영향을 미치지 않으려면 백그라운드에서 스캔을 수행해야 하는데, 이를 위해서는 부트스트래핑 작업의 우선순위를 낮춰야만 한다. 스캔은 부트스트래핑 과정에 상당한 속도 저하를 일으키며, 노드들이 하루에 수백만 개의 요청을 처리하는 바쁜 쇼핑 시즌에는 부트스트래핑을 마치는 데 거의 하루가 걸렸다. 두 번째로, 노드가 시스템에 추가, 제거될 때 노드들이 관리하는 키 범위에 대해 많은 변경이 발생하며, 새로운 범위에 대한 머클 트리를 다시 연산해야 한다. 프로덕션 환경에서 이러한 연산은 사소하지 않다. 마지막으로, 키 범위의 랜덤성 때문에 전체 키 공간에 대한 스냅샷을 얻는 것이 쉽지 않으며, 이로 인해 기록 과정이 복잡해진다. 이 방식에서 전체 키 공간을 기록하려면 각각의 노드에 대해 키를 순회해야 하는데, 이는 굉장히 비효율적인 작업이다.

이 전략의 기초적인 문제는 스키마에 대한 데이터 파티셔닝과 데이터의 배치가 뒤섞인다는 점이다. 예를 들어, 요청 부하의 증가를 처리하기 위해 더 많은 노드를 시스템에 추가하려는 경우가 있다. 하지만 이 시나리오에서 데이터 파티셔닝에 영향을 주지 않고 노드를 추가하는 것은 불가능하다. 이상적으로는 파티셔닝과 배치에 대한 독립적인 방식을 사용해야 한다. 따라서 다음과 같은 전략을 평가해볼 수 있다.

전략 2: 같은 크기의 파티션과 노드별 T개의 랜덤 토큰: 이 전략에서 해시 공간은 똑같은 크기의 파티션 또는 범위 Q개로 나뉘고, 각 노드에는 T개의 랜덤 토큰이 배정된다. Q는 보통 Q >> N 그리고 Q >> S*T로 설정되며, 여기서 S는 시스템에 있는 노드의 개수를 의미한다. 이 전략에서 토큰은 해시 공간을 노드의 정렬된 목록으로 매핑하는 함수를 만들기 위해서만 사용하고, 파티셔닝을 결정하는 데 사용하지는 않는다. 파티션은 안정 해싱 링을 파티션 끝에서부터 시계 방향으로 순회하는 동안 처음 만나는 N개의 고유한 노드에 배치된다. 그림 7은 N=3일 때 이 전략의 모습을 보여준다. 이 예시에서 키 k1을 가진 파티션의 끝에서부터 링을 순회하던 중 노드 A, B, C를 마주치게 된다. 이 전략의 주요 이점은: (i) 파티셔닝과 파티션 배치를 분리할 수 있고, (ii) 런타임에 배치 방식을 변경할 수 있다.

전략 3: 같은 크기의 파티션과 노드별 Q/S개의 토큰: 전략 2와 유사하게, 이 전략은 해시 공간을 똑같은 크기의 파티션 Q개로 나누고, 파티션의 배치를 파티셔닝 방식으로부터 분리한다. 더 나아가, 각 노드에는 Q/S개의 토큰이 할당되며, 이때 S는 시스템에 있는 노드의 개수를 의미한다. 노드를 시스템에서 제거할 때는 이러한 속성이 유지되도록 남은 노드들에게 토큰을 랜덤하게 분산한다. 노드를 시스템에 추가할 때도 다른 노드들로부터 토큰을 "훔침"으로써 이 속성을 유지한다.

그림 8. 노드 30개, N=3 시스템에서 각 노드가 동일한 양의 메타데이터를 관리하는 경우 서로 다른 전략 간의 부하 분산 효율성 비교. 시스템 크기 값과 레플리카의 개수는 아마존 대부분의 서비스에 설정된 일반적인 구성을 기반으로 한다.

세 전략의 효율성은 S=30, N=3 시스템에서 평가되었다. 다만, 세 전략에는 효율성을 위한 각자만의 설정이 있기 때문에 서로를 공정하게 비교하는 것은 어렵다. 예를 들어, 전략 1의 부하 분산 속성은 토큰의 개수(i.e., T)에 의존적인 반면, 전략 3은 파티션의 개수(i.e., Q)에 의존적이다. 이러한 전략들을 비교하는 하나의 공정한 방법은 모든 전략이 멤버십 정보를 유지하기 위해 동일한 크기의 공간을 사용하는 동안 부하 분산의 왜곡을 평가하는 것이다. 전략 1에서 각 노드는 링에 있는 모든 노드의 토큰 위치를 관리해야 하며, 노드 3에서 각 노드는 각 노드에 할당된 파티션에 대한 정보를 관리해야 한다.

다음 실험에서, 이러한 전략들은 다양한 관련 인자(T, Q)에 의해 평가되었다. 각 전략의 로드밸런싱 효율성은 각 노드에서 관리해야 하는 다양한 크기의 멤버십 정보에 대해 측정했다. 여기서 로드밸런싱 효율성(Load balancing efficiency)는 각 노드가 처리하는 평균 요청 수와 가장 많은 요청을 받는(hottest) 노드의 최대 요청 처리 수의 비율로 정의된다.

결과는 그림 8에 나와있다. 그림에서 볼 수 있듯이, 전략 3이 최고의 로드밸런싱 효율성을 달성했으며, 전략 2는 최악의 로드밸런싱 효율성을 달성했다. 전략 2는 다이나모 인스턴스를 전략 1에서 전략 3으로 전환하는 과정에서 임시 설정 역할을 했다. 전략 1과 비교해 전략 3은 더 나은 효율성을 달성했으며, 각 노드가 관리하는 멤버십 정보의 크기를 3배까지 줄일 수 있었다. 저장소가 중요한 문제는 아니지만, 노드들이 주기적으로 멤버십 정보를 주고받기 때문에 이 정보를 최대한 압축해서 유지하는 것이 바람직하다. 추가적으로, 전략 3은 다음과 같은 이유로 유리하고, 배포하기 단순하다: (i) 빠른 부트스트래핑 및 복구: 파티션 범위가 고정되어 있기 때문에 분리된 파일로 저장할 수 있으며, 이는 단순히 파일을 전송함으로써 파티션을 재배치할 수 있다는 의미이다. (특정 항목을 찾는 데 임의 접근이 필요하지 않다.) 이렇게 하면 부트스트래핑과 복구 과정을 단순하게 만들 수 있다. (ii) 기록의 용이함: 데이터셋의 주기적인 기록은 아마존 저장소 서비스의 대부분이 요구하는 필수 사항이다. 전략 3에서는 파티션 파일을 분리해서 보관할 수 있기 때문에 다이나모로 저장된 전체 데이터셋 기록이 단순해진다. 반면 전략 1에서는 토큰이 랜덤하게 선택되고, 다이나모에 저장된 데이터를 기록하기 위해 개별 노드에 대해 키를 순회해야 한다. 이는 대체로 비효율적이며, 느린 작업이다. 전략 3의 단점은 노드 멤버십을 변경할 때 할당에 필요한 속성을 보존하기 위해 조정이 필요하다는 것이다.

버전 분기: 언제, 그리고 얼마나?

앞서 언급했듯이, 다이나모는 가용성을 위해 일관성을 희생하도록 설계되었다. 일관성으로 발생하는 여러 장애의 정확한 영향을 이해하기 위해, 중단 길이, 장애의 종류, 컴포넌트 신뢰성, 워크로드 등 다양한 요인에 대한 상세 데이터가 필요하다. 이러한 상세를 다루는 것은 이 논문의 범위를 벗어나지만, 이 섹션에서는 좋은 요약 지표인 프로덕션 환경에서 애플리케이션이 볼 수 있는 버전 분기(divergent versions) 개수에 대해 논의 한다.

데이터의 버전 분기는 두 개의 시나리오에서 발생한다. 첫 번째는 노드 장애, 데이터센터 장애, 네트워크 파티션과 같이 시스템이 장애 시나리오를 맞딱뜨릴 때다. 두 번째는 시스템이 하나의 데이터에 대해 대량의 동시 쓰기 동작을 수행하고, 여러 노드가 동시에 업데이트를 다룰 때다. 사용성이나 효율성 측면에서 봤을 때, 버전 분기는 최대한 낮게 유지하는 것이 좋다. 만약 여러 버전에 대해 벡터 클럭만으로 신택틱 중재할 수 없다면, 시맨틱 중재를 위한 비즈니스 로직으로 넘어가야 한다. 시맨틱 중재는 서비스에 추가적인 부하를 일으키기 때문에 최소화해야 한다.

다음 실험에서, 장바구니 서비스에 반환된 버전의 개수는 24시간 동안 집계되었다. 이 기간 동안 요청의 99.94%는 단 하나의 버전을 응답받았다. 요청의 0.00057%는 두 개의 버전을 받았고, 요청의 0.00047%는 3개 버전, 요청의 0.00009%는 4개 버전을 받았다. 이는 버전 분기가 거의 일어나지 않음을 보여준다.

실험은 버전 분기의 수가 장애가 아닌 동시적 쓰기 동작에 의해 증가함을 시사한다. 동시적 쓰기 동작의 증가는 보통 봇(자동화된 클라이언트 프로그램)에 의해 일어나며, 인간에 의해 일어나는 경우는 드물다. 이 문제는 이야기의 민감한 성격 때문에 자세히 논의하지 않는다.

클라이언트 또는 서버 주도

섹션 5에서 언급했듯이, 다이나모에는 들어오는 요청을 처리하기 위해 상태 기계를 사용하는 요청 처리 컴포넌트가 있다. 클라이언트가 보낸 요청은 로드밸런서에 의해 링 위의 여러 노드들에게 골고루 할당된다. 읽기 요청에 대해서는 어떤 다이나모 노드든 코디네이터로 역할할 수 있다. 반면 쓰기 요청에 대해서는 키의 현재 선호 목록에 있는 노드만 코디네이터로 역할하게 된다. 이 제약은 선호 노드가 새 버전 스탬프를 만들어야 하는 추가적 책임이 있기 때문에 만들어졌으며, 이때 새 버전 스탬프는 쓰기 요청으로 업데이트된 버전을 포함한다. 다이나모의 버저닝 방식이 물리적 타임스탬프에 기반하고 있다면, 모든 노드가 쓰기 요청을 처리할 수 있다.

요청을 처리하기 위핸 또 다른 접근법은 상태 기계를 클라이언트 노드로 옮기는 것이다. 이 방식에서 클라이언트 애플리케이션은 로컬에서 요청을 처리하기 위한 라이프러리를 사용한다. 클라이언트는 주기적으로 랜덤한 다이나모 노드를 고르고, 다이나모 멤버십 상태의 현재 모습을 다운로드한다. 이 정보를 이용해 주어진 키에 대해 어떤 노드들이 선호 목록을 형성하고 있는지 알 수 있다. 읽기 요청은 클라이언트 노드에서 처리할 수 있기 때문에, 로드밸런서에 의해 요청이 랜덤한 다이나모 노드에 할당될 때 발생하는 추가적인 네트워크 홉을 피할 수 있다. 쓰기 동작은 키의 선호 목록에 있는 노드로 전달할 수도 있고, 다이나모가 타임스탬프 기반 버저닝을 사용하는 경우 로컬에서 처리할 수도 있다.

클라이언트 주도(client-driven) 처리 방식의 중요한 이점은 더 이상 클라이언트의 부하를 균일하게 분산하기 위한 로드밸런서가 필요하지 않다는 점이다. 타당한 부하 분산은 키 할당이 저장소 노드에 거의 균일하게 이뤄짐으로써 암묵적으로 보장된다. 이 방식의 효율성은 클라이언트에 얼마나 최신의 멤버십 정보가 있는지에 따라 달라진다. 현재는 클라이언트가 랜덤 다이나모 노드에게 10초에 한 번씩 멤버십 업데이트를 폴링(polling)한다. 풀(pull) 기반 접근법은 푸시 기반 접근법보다 많이 선택되었는데, 전자는 많은 수의 클라이언트에서 더 잘 확장되며, 서버에서 클라이언트에 대한 상태를 유지할 필요가 거의 없기 때문이다. 그러나 최악의 경우, 클라이언트가 10초 동안 오래된 멤버십 정보를 참조할 수도 있다. 클라이언트가 멤버십 테이블이 오래되었음을 감지한다면(가령 일부 멤버에 접근이 안되는 경우), 즉시 새로운 멤버십 정보로 업데이트할 것이다.

표 2. 클라이언트 주도 처리와 서버 주도 처리의 성능

표 2는 24시간 동안 클라이언트 주도 접근법을 서버 주도(server-driven) 접근법과 비교했을 때, 99.9 분위 및 평균 레이턴시가 개선되었음을 보여준다. 표에서 볼 수 있듯이, 클라이언트 주도 접근법은 레이턴시를 99.9 분위에서 최소 30 밀리초 줄이고, 평균에서 3~4 밀리초 줄일 수 있다. 클라이언트 주도 접근법은 로드밸런서의 오버헤드(overhead)와 요청을 랜덤 노드에 할당할 때 일어날 수 있는 추가적인 네트워크 홉을 제거함으로써 레이턴시를 개선한다. 표에서 평균 레이턴시는 99.9 분위 레이턴시에 비해 굉장히 낮은 것을 볼 수 있다. 이는 다이나모 저장소 엔진이 캐시를 사용하며, 쓰기 버퍼가 좋은 히트율(hit ratios)를 보이기 때문이다. 또한 로드밸런서와 네트워크는 응답 시간에 추가적인 가변성을 만들기 때문에, 99.9 분위의 응답 시간 개선은 평균보다 더 높다.

백그라운드와 포그라운드 작업의 균형

각 노드는 일반적인 포크라운드 읽기, 쓰기 동작 외에도 레플리카 동기화 및 데이터 위탁(노드 암시나 추가, 제거에 의한 위탁)을 위한 다양한 종류의 백드그라운드 작업을 수행한다. 프로덕션에서 이러한 백그라운드 작업은 리소스 문제를 일으켰고, 일반적인 읽기, 쓰기 동작의 성능에도 영향을 미쳤다. 따라서 정기적인 주요 작업에 큰 영향을 미치지 않는 경우에만 백그라운드 작업이 실행되도록 할 필요가 있었다. 이를 위해 백그라운드 작업을 승인 제어(admission control) 메커니즘과 통합했다. 각 백그라운드 작업은 이 컨트롤러를 사용해 모든 백그라운드 작업에게 공유되는 리소스(e.g. 데이터베이스)의 런타임 슬라이스(slices)를 예약한다. 포그라운드 작업의 모니터링된 성능을 기반으로 한 피드백 메커니즘은 백그라운드 작업이 사용할 수 있는 슬라이스의 개수를 조절한다.

승인 컨트롤러는 포그라운드 읽기, 쓰기 동작을 실행하는 동안 리소스 접근 동작을 지속적으로 모니터링한다. 모니터링되는 항목에는 디스크 작업 레이턴시, 락 경합 및 트랜잭션 타임아웃으로 인한 데이터베이스 접근 실패, 요청 큐 대기 시간 등이 있다. 이러한 정보는 주어진 시간 윈도우에서 레이턴시(또는 실패)의 백분위수를 집계하고, 이 지표가 원하는 임계치에 가까운지 확인하기 위해 사용한다. 예를 들어, 백그라운드 컨트롤러는 99 분위에서 데이터베이스 읽기 레이턴시(지난 60초 동안의 레이턴시)가 미리 정해둔 임계치(50ms)에 얼마나 가까운지 확인한다. 컨트롤러는 이러한 비교를 통해 포그라운드 동작을 위한 리소스가 얼마나 있는지 가늠한다. 이후, 백그라운드 작업에 사용할 수 있는 시간 슬라이스 개수를 결정하고 피드백 루프를 사용하여 백그라운드 활동의 침입을 제한한다. 백그라운드 작업을 관리할 때 발생하는 비슷한 문제에 대해서는 [4]에서 연구되었다.

논의

이 섹션에서는 다이나모의 유지보수와 구현 과정에서 얻은 경험들을 요약한다. 많은 아마존 내부 서비스들이 지난 2년간 다이나모를 사용해왔고, 다이나모는 애플리케이션에게 상당한 수준의 가용성을 제공했다. 특히 애플리케이션은 요청의 99.9995%에 대해 성공적인 응답(타임아웃 제외)을 받았으며, 현재까지 데이터 유실은 발생하지 않았다.

뿐만 아니라, 다이나모의 주요 장점은 (N, R, W) 세 파라미터를 통해 필요에 따라 인스턴스를 조정할 수 있다는 것이다. 인기있는 상용 데이터 저장소와 달리 다이나모는 데이터 일관성과 중재 로직의 문제를 개발자에게 공개한다. 처음에는 애플리케이션 로직이 복잡해질 것이라고 생각할 수도 있다. 그러나 아마존 플랫폼은 고가용성을 위해 만들어졌고, 많은 애플리케이션들이 서로 다른 장애와 비일관성을 다루도록 설계되었다. 따라서 이러한 애플리케이션들이 다이나모를 사용하도록 포팅하는 것은 상대적으로 쉬운 일이었다. 다이나모 사용을 원하는 새 애플리케이션에 대해서는, 초기 개발 단계에 비즈니스 요구를 적절히 충족하기 위한 올바른 충돌 해결 메커니즘을 고르는 분석만이 필요하다. 마지막으로, 다이나모는 각 노드가 다른 노드의 데이터를 인식하는 완전한 멤버십 모델을 채택했다. 이를 위해 각 노드는 시스템의 다른 노드와 함께 전체 라우팅 테이블을 적극적으로 주고 받는다. 이 모델은 수백 개의 노드로 구성된 시스템에서 잘 동작한다. 하지만 라우팅 테이블을 유지하기 위한 오버헤드는 시스템 크기에 따라 증가하기 때문에 수만 개의 노드로 구성된 시스템에서도 잘 동작하도록 설계를 확장하는 일은 간단치 않다. 이러한 한계는 다이나모에 계층적 확장을 도입함으로써 극복할 수 있다. 또한 이 문제는 O(1) DHT 시스템(e.g., [14])을 통해 적극적으로 해결할 수도 있다.

결론

이 논문은 높은 가용성과 확장성을 갖춘 데이터 저장소인 다이나모에 대해 설명했다. 아마존닷컴의 이커머스 플랫폼은 수많은 핵심 서비스들의 상태를 저장하기 위해 다이나모를 사용한다. 다이나모는 요구되는 수준의 가용성과 성능을 제공할 수 있고, 서버나 데이터센터의 장애, 네트워크 파티셔닝을 다루는 데 있어 성공을 거뒀다. 다이나모는 점진적으로 확장이 가능하며, 서비스가 받고 있는 부하에 따라 스케일 업 또는 스케일 다운 할 수 있다. 또한 다이나모는 N, R, W 파라미터를 조정함으로써 저장소 시스템이 요구하는 성능과 내구성, 일관성을 충족할 수 있도록 해준다.

지난 1년간 프로덕션에서 다이나모를 사용한 사례는 분산된 기술들을 결합하여 하나의 고가용성 시스템을 제공할 수 있음을 시사한다. 가장 까다로운 애플리케이션 환경 중 하나에서 성공을 거둔 것은 최종 일관성 저장소 시스템이 고가용성 애플리케이션의 기본 요소가 될 수 있음을 보여준다.

감사의 말

초기 다이나모 설계에 기여한 팻 헬란드(Pat Helland)에게 감사를 전합니다. 또한 의견을 제시해준 마빈 테이머(Marvin Theimer)와 로버트 반 레네세(Robert van Renesse)에게 감사합니다. 논문의 품질을 크게 향상시키는 카메라 레디 버전을 준비하는 동안 상세한 의견을 준 우리의 안내자, 제프 모굴(Jeff Mogul)에게도 감사합니다.

참고문헌

• [1] Adya, A., Bolosky, W. J., Castro, M., Cermak, G., Chaiken, R., Douceur, J. R., Howell, J., Lorch, J. R., Theimer, M., and Wattenhofer, R. P. 2002. Farsite: federated, available, and reliable storage for an incompletely trusted environment. SIGOPS Oper. Syst. Rev. 36, SI (Dec. 2002), 1-14.
• [2] Bernstein, P.A., and Goodman, N. An algorithm for concurrency control and recovery in replicated distributed databases. ACM Trans. on Database Systems, 9(4):596-615, December 1984
• [3] Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A., and Gruber, R. E. 2006. Bigtable: a distributed storage system for structured data. In Proceedings of the 7th Conference on USENIX Symposium on Operating Systems Design and Implementation - Volume 7 (Seattle, WA, November 06 - 08, 2006). USENIX Association, Berkeley, CA, 15-15.
• [4] Douceur, J. R. and Bolosky, W. J. 2000. Process-based regulation of low-importance processes. SIGOPS Oper. Syst. Rev. 34, 2 (Apr. 2000), 26-27.
• [5] Fox, A., Gribble, S. D., Chawathe, Y., Brewer, E. A., and Gauthier, P. 1997. Cluster-based scalable network services. In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles (Saint Malo, France, October 05 - 08, 1997). W. M. Waite, Ed. SOSP '97. ACM Press, New York, NY, 78-91.
• [6] Ghemawat, S., Gobioff, H., and Leung, S. 2003. The Google file system. In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (Bolton Landing, NY, USA, October 19 - 22, 2003). SOSP '03. ACM Press, New York, NY, 29-43.
• [7] Gray, J., Helland, P., O’Neil, P., and Shasha, D. 1996. The dangers of replication and a solution. In Proceedings of the 1996 ACM SIGMOD international Conference on Management of Data (Montreal, Quebec, Canada, June 04 - 06, 1996). J. Widom, Ed. SIGMOD '96. ACM Press, New York, NY, 173-182.
• [8] Gupta, I., Chandra, T. D., and Goldszmidt, G. S. 2001. On scalable and efficient distributed failure detectors. In Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing (Newport, Rhode Island, United States). PODC '01. ACM Press, New York, NY, 170-179.
• [9] Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Wells, C., and Zhao, B. 2000. OceanStore: an architecture for global-scale persistent storage. SIGARCH Comput. Archit. News 28, 5 (Dec. 2000), 190-201.
• [10] Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., and Lewin, D. 1997. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the Twenty-Ninth Annual ACM Symposium on theory of Computing (El Paso, Texas, United States, May 04 - 06, 1997). STOC '97. ACM Press, New York, NY, 654-663.
• [11] Lindsay, B.G., et. al., “Notes on Distributed Databases”, Research Report RJ2571(33471), IBM Research, July 1979
• [12] Lamport, L. Time, clocks, and the ordering of events in a distributed system. ACM Communications, 21(7), pp. 558- 565, 1978.
• [13] Merkle, R. A digital signature based on a conventional encryption function. Proceedings of CRYPTO, pages 369– 378. Springer-Verlag, 1988.
• [14] Ramasubramanian, V., and Sirer, E. G. Beehive: O(1)lookup performance for power-law query distributions in peer-to- peer overlays. In Proceedings of the 1st Conference on Symposium on Networked Systems Design and Implementation, San Francisco, CA, March 29 - 31, 2004.
• [15] Reiher, P., Heidemann, J., Ratner, D., Skinner, G., and Popek, G. 1994. Resolving file conflicts in the Ficus file system. In Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference - Volume 1 (Boston, Massachusetts, June 06 - 10, 1994). USENIX Association, Berkeley, CA, 12-12…
• [16] Rowstron, A., and Druschel, P. Pastry: Scalable, decentralized object location and routing for large-scale peer- to-peer systems. Proceedings of Middleware, pages 329-350, November, 2001.
• [17] Rowstron, A., and Druschel, P. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. Proceedings of Symposium on Operating Systems Principles, October 2001.
• [18] Saito, Y., Frølund, S., Veitch, A., Merchant, A., and Spence, S. 2004. FAB: building distributed enterprise disk arrays from commodity components. SIGOPS Oper. Syst. Rev. 38, 5 (Dec. 2004), 48-58.
• [19] Satyanarayanan, M., Kistler, J.J., Siegel, E.H. Coda: A Resilient Distributed File System. IEEE Workshop on Workstation Operating Systems, Nov. 1987.
• [20] Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and Balakrishnan, H. 2001. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols For Computer Communications (San Diego, California, United States). SIGCOMM '01. ACM Press, New York, NY, 149-160.
• [21] Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., Spreitzer, M. J., and Hauser, C. H. 1995. Managing update conflicts in Bayou, a weakly connected replicated storage system. In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (Copper Mountain, Colorado, United States, December 03 - 06, 1995). M. B. Jones, Ed. SOSP '95. ACM Press, New York, NY, 172-182.
• [22] Thomas, R. H. A majority consensus approach to concurrency control for multiple copy databases. ACM Transactions on Database Systems 4 (2): 180-209, 1979.
• [23] Weatherspoon, H., Eaton, P., Chun, B., and Kubiatowicz, J. 2007. Antiquity: exploiting a secure log for wide-area distributed storage. SIGOPS Oper. Syst. Rev. 41, 3 (Jun. 2007), 371-384.
• [24] Welsh, M., Culler, D., and Brewer, E. 2001. SEDA: an architecture for well-conditioned, scalable internet services. In Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles (Banff, Alberta, Canada, October 21 - 24, 2001). SOSP '01. ACM Press, New York, NY, 230-243.