DynamoDB Internals (1) - Dynamo
아마존은 지구 규모 스케일 서비스를 운영하면서 자신들의 요구와 가장 잘 들어맞는 범용적인 분산 스토리지 시스템을 만들어냈는데 이 시스템이 바로 Dynamo이다. 시스템을 만들고 운영한 경험을 논문으로 발표했고, 이 논문은 분산 스토리지 시스템 생태계에 큰 영향을 주었다. 이 논문에 영향을 받아 오픈소스에서는 Cassandra가 개발되었고 AWS 서비스의 SimpleDB, DynamoDB를 만드는 기초가 되었다. DynamoDB의 구조가 완전히 Dynamo와 같지는 않지만, 뿌리가 되는 Dynamo 시스템에 대해 먼저 알아보자.
RDB가 적절하지 않았던 이유
Dynamo는 아주 가용성 높은 키 값 스토어이다. 애초에 이러한 시스템을 구성하게 된 이유가 뭘까? 아마존은 Oracle이 제공하는 엔터프라이즈 데이터베이스 스케일을 넘어선 지구 단위의 글로벌 서비스로 성장했다. 이런 스케일을 감당하기 위해 아마존은 직접 DB를 설계하고 관리하기로 결정했다. 이를 위해 아마존은 그동안의 데이터베이스 사용 패턴에 대해 조사했고 다음과 같은 특징들을 확인할 수 있었다.
- 스케일아웃 처리를 위한
JOIN사용 제거 (JOIN을 사용하지 않음) - 인덱스를 통한 단일한 데이터 검색이 대부분
- 복수의 데이터를 가져오는 패턴도 있었지만, 이 경우 보통 하나의 테이블에서만 데이터를 가져옴
이런 특징들은 Key-Value 형태로 매칭되는 쿼리 조건으로 충분히 해결할 수 있고, RDB의 아주 강력한 쿼리들을 사용할 필요가 없었다. 즉, 규모있는 데이터 처리를 위해 RDB가 요구하는 컴퓨팅 리소스를 준비할 필요가 없다. 따라서 아마존에서는 RDB 사용이 데이터베이스 접근 패턴에 적합하지 않다고 판단했다.
아마존에서 필요한 데이터베이스는 일반적인 RDB와 다르게 다음과 같은 특징을 가져야 한다
간단한 쿼리 모델: 프라이머리 키를 통해 데이터를 정의하고 읽어올 수 있는 간단한 쿼리 모델이 필요하고, 관계형 스키마라든지, 복잡한 테이블 연결은 불필요하다.
느슨한 ACID: 트랜잭션의 ACID, 특히 일관성을 보장하는 것은 데이터 가용성 측면에서 좋지 않다. 약한 일관성을 가지고 동작하는 애플리케이션에 적합한 데이터베이스여야 한다.
효율성: 아마존 플랫폼의 엄격한 지연율 제한을 여러 서비스 도메인에서 충족할 수 있어야 한다. 아마존 플랫폼은 일반적으로 500TPS 기준으로 99.9% 백분위가 300ms 안에 처리되어야 한다는 지연율 기준이 있다. 서비스마다 읽기와 쓰기 비율이 다르기 때문에 데이터베이스의 설정을 통해 어떻게 분산 환경의 읽기 쓰기를 수행할지 결정할 수 있어야 한다.
효율성은 조금 모호한 단어같이 보일 수 있는데, 설정값을 통해 범용적으로 인프라에 도입할 수 있다는 측면에서의 효율성을 뜻하는 것 같다.
시스템 디자인 고민
위와 같은 목표를 달성하기 위해 필요한 몇 가지 고민이 있었다. 이 고민을 해결한다면 시스템 디자인의 목표를 달성할 수 있다.
전통적인 RDB의 데이터 복제 알고리즘은 강력한 일관성을 위해 동기적으로 데이터를 복제한다. 이 수준의 일관성을 얻기 위해서는 특정 시나리오에서 데이터 가용성을 포기해야 한다. 즉, 높은 수준의 일관성은 정확한 답을 공유하지 못하는 불확실한 상황일 때 차라리 데이터를 사용 불가능하게 만들어버린다. 분산 시스템에서 아주 유명한 이론인 CAP 이론에서 말하듯 일관성, 가용성, 그리고 네트워크 파티션 내구성 세 가지를 모두 충족시킬 수 없다. 네트워크 파티션 상황은 반드시 발생하게 되어있고, 데이터 일관성을 유지하기 위해서는 가용성을 포기해야 한다.
강력한 일관성을 유지하는 데이터 복제는 “전통적”이라고 표현했지만, 이 논문이 쓰이기 전의 상황인듯 싶다. 정확한 히스토리는 잘 모르지만, 최근 RDB에서 레플리카를 운영하는 방법이 꼭 완전한 일관성을 요구하지는 않았던 것 같다.
핵심 고민
Dynamo는 네트워크 장애가 무조건 발생한다는 가정 아래 가용성을 최대로 높이도록 디자인되었다. 이를 위해 데이터가 레플리카에 동기적으로 전파되도록 처리하지 않고, 비동기적으로 전파되도록 했다. 구체적으로 어떻게 전파되고, 어떤 상황에서 성공으로 판단하는지 등은 이후 후술한다. 아무튼 이러한 비동기 전파 상황에서는 데이터의 충돌 문제가 발생할 수 있다. 하나의 데이터를 수정한 값이 모종의 이유로 두 가지 이상의 버전으로 분기되는 것을 데이터 충돌 상황이라고 표현한다.
A 노드에 a → a'가 되도록 수정했는데 비동기 전파로 인해 다른 노드에 전파가 되기 전에 성공 응답을 보내고 A 노드에 네트워크 파티션이 발생했다고 가정해보자. 그다음 같은 데이터 a를 갖고 있던 B 노드에 a → a''로 수정을 가했다면 시스템은 두 가지 버전의 a 데이터를 갖게 되는 것이다.
이 상황을 해결하는 방법은 다음 두 가지 방향의 문제를 해결하는 것이다.
- 언제 해결할 것이냐? (쓰기 시점 or 읽기 시점)
- 누가 해결할 것이냐? (클라이언트 or 데이터베이스)
전통적으로는 쓰기 시점에 이 문제를 해결하며 읽기 작업의 복잡도를 단순하게 유지한다. 이런 시스템에서는 주어진 타임아웃 시간 내에 모든(혹은 특정 정족수) 데이터 저장소에 닿지 못하면 쓰기가 실패할 수 있다. Dynamo는 “항상 쓰기 가능한“ 데이터 스토어를 목표로 한다. 아마존의 많은 서비스에서 고객의 업데이트 작업을 거절하는 경우 고객 경험을 해치는 결과를 가져온다. 예를 들어서 쇼핑 카트는 반드시 소비자가 담거나 지운 아이템을 네트워크 파티션이 발생하더라도 반영할 수 있어야 한다. 따라서 쓰기 작업의 가용성을 위해 Dynamo는 읽기 작업에 이 충돌 해결 역할을 맡겼다.
쓰기 작업에서 이 문제를 해결한다면 버저닝이 발생하지 않도록 회피하는 형태로 문제를 해결한다고 볼 수 있고, 읽기 시점에서 해결한다면 문제 발견 후 복구하는 과정이 있다고 볼 수 있다.
그다음 “누가 해결할 것인지” 선택해야 한다. 데이터베이스에서 일관적으로 처리하도록 하는 방법은 굉장히 제한적이다. 예를 들어서 마지막 업데이트가 발생한 시점을 기준으로 데이터를 덮어씌우는 방법처럼 아주 간단하고 단순한 방법으로만 문제를 해결할 수 있다. 반대로 애플리케이션에서 이를 해결하도록 두면, 데이터가 어떻게 비즈니스 로직과 연결되는지 이해하고 있기 때문에 더 적절한 방법을 선택할 수 있다. 어떻게 버저닝 문제를 해결하는지 구체적인 내용은 후술한다.
기타 고려사항
위 가장 큰 두 가지 설계 고민 외에 다음과 같은 고민을 하며 시스템을 설계했다.
증분 확장성 (Incremental Scalability): 데이터 스토리지 노드를 추가 또는 삭제할 때 데이터베이스 운영 및 시스템에 최소한의 영향만 주면서 이를 수행해야 한다.
대칭성: 모든 스토리지 노드가 동일한 역할 수행해야 한다. 이유는 특수한 역할을 하는 노드를 지정하기 시작하면 프로비저닝 시스템의 복잡도가 증가하기 때문이다.
탈중앙성: 중앙에서 컨트롤하는 시스템보다 P2P를 통한 분산된 컨트롤이 더 선호되는 방향으로 시스템을 설계한다. 이에 대해서는 구체적인 이유보다는 과거에 중앙 시스템의 문제로 인한 운영 중단 사태가 발생한 적이 있기 때문에 이를 피하기 위해서 이러한 고민을 했다고 한다.
이질성 (Heterogeneity): 시스템에서 동작하는 노드들이 불균일하다는 특성을 이용할 수 있는 시스템이어야 한다. 예를 들어 작업 분배가 각 노드의 Capacity에 비례해 분배될 수 있는 시스템이어야 한다. 이를 통해 보다 효율적으로 작업 분배가 이뤄질 수 있다.
시스템 목표와 그 목표를 위한 고민이 잘 매칭되는지 확인해보자. 간단한 쿼리 모델은 Key-Value 스토리지라는 점, 느슨한 ACID는 비동기적 데이터 전파를 통해 가용성을 높인다는 점(그리고 데이터 충돌을 해결하기 위한 핵심 고민 두 가지), 효율성의 경우 여러 설정값으로 위 고민을 해결하도록 했다. 이 여러 설정값에 대해서는 나중에 더 자세히 다룬다.
시스템 아키텍처
위 고민을 어떻게 해결했는지 구체적으로 살펴보자. Dynamo는 독자적인 기술의 탄생이 아니고 그 전부터 논의되어온 분산 시스템을 구성하기 위한 기술들의 집합이다. 요약하자면 다음 방법들을 사용하고 있다.
| 문제 | 해결책 | 해결 목표 |
|---|---|---|
| 파티셔닝 (노드 추가 or 제거) | Consistency Hashing | 증분 확장성을 보장할 수 있음 |
| 쓰기 HA 구성 | vector clock 개념과 클라이언트에서 데이터 충돌 해결 | 쓰기 가용성이 증가 |
| 일시적 실패 | 쿼럼 (Quorum)과 Hinted Handoff | 범용적인 시스템을 위한 일시적인 실패와 복구 처리 방법 |
| 영구적 실패 | Merkle trees | 데이터 동기화를 위한 데이터 전송량을 최소화 |
| 멤버십, 실패 탐지 | 가십 기반 멤버십 프로토콜 | 노드 기능의 동일성을 유지하면서 탈중앙화 시스템을 유지할 수 있는 시스템 |
글에서는 고민을 해결하기 위해 핵심적이라고 생각되는 파티셔닝문제, 쓰기 HA, 일시적 실패에 대해 다룰 예정이다.
파티셔닝
데이터 또는 트랜잭션이 증가함에 따라 스토리지 노드가 감당해야 하는 트랜잭션이 점점 늘어나면 이를 처리하기 위한 스토리지 노드가 추가로 붙어야 한다. 즉, 동적인 파티셔닝을 위한 방법이 필요하다. Dynamo에서는 이를 위해 Consistent Hashing 방법을 사용하고 있다.
Consistent Hashing은 해시 함수의 결과 범위가 고정된 원형 공간(Ring) 안에서 다뤄진다. 링 형태라는 것은 가장 큰 해시값의 마지막이 가장 작은 해시값으로 연결된다는 것을 의미한다. 해당 시스템 안에서 각 스토리지 노드는 랜덤 값이 할당되고, 이 랜덤 값의 해시값을 가지고 링 위에 위치 시키는 방법이다. 스토리지 노드 안에 들어갈 데이터 역시 키를 해싱한 값을 기준으로 링 위에 배치된다. 이때 데이터의 위치에서 시계 방향으로 돌았을 때 처음 만나게 되는 스토리지 노드에 실제 데이터가 저장되게 된다.
일반적인 방법으로 데이터의 키를 해싱한 값으로 샤딩을 진행한 경우, 노드가 추가되거나 삭제될 때마다 데이터를 다시 해싱해야 하는 큰 비용이 있다. Consistent Hashing은 데이터를 균일하게 분산하면서도 노드가 추가되어도 이런 재해싱 과정 필요 없이 이웃한 노드에만 영향을 주는 방식으로 스토리지 노드를 추가한다.
동적인 스케일링을 위해 아주 적합한 방법이지만, 스토리지 노드의 이질성을 고려하지 않는다. 위에서 언급했던 “이질성“을 고려한 시스템을 위해 Dynamo는 하나의 물리적인 노드가 여러 개의 가상 노드(Virtual Node)와 매칭되며 가상 노드들이 링 위에 올라가도록 설계되었다. 각 가상 노드는 실제 물리 노드와 연결되고 가상 노드의 개수는 물리적 노드의 실제 성능에 맞게 조절된다.
즉, 성능이 좋은 스토리지 노드는 많은 가상 노드와 연결되어 링 위의 비교적 많은 영역을 담당한다. 반대의 경우 적은 수의 가상 노드와 연결되게 된다.
랜덤하게 배치된다는 점 역시 분산이 고르지 못하다는 단점이 있다. 운영하면서 몇 가지 버전을 거친 이후 링을 고르게 나눠 노드를 배치하는 방법으로 이 문제를 해결할 수 있었다고 한다. 이 글에서는 해당 내용에 대해 설명하고 있지 않다. 궁금하다면 이 링크에서 설명을 더 읽어보자.
HA(High Availability)
HA를 위해서는 복제 시스템이 필요하다. 즉, 데이터를 본래 저장해야 하는 스토리지 노드 외에 다른 스토리지 노드에도 저장할 수 있어야 한다. Dynamo는 몇 개의 호스트에 데이터를 복제할 것인지 설정 파라미터로 결정할 수 있도록 만들었다.
몇 개의 호스트에 복제하는지 결정하는 파라미터는 이 글에서
N으로 표기한다.
위 이미지에서 키 K를 가진 데이터는 (A, B] 사이에 위치하게 되고, B 노드에 기본적으로 저장된다. 그다음 데이터가 복제되어야 하는 노드는 N - 1 만큼 시계 방향으로 돌며 만나는 노드이다. N = 3 이라면, B 외 C, D도 이 데이터를 저장하는 대상이 된다.
이렇게 특정 데이터에 대해 저장할 책임이 있는 노드 리스트를 preference list라고 부른다. preference list 안에 가상 노드로 인해 물리 노드가 중복되어 들어가지 않도록 같은 물리 노드를 가리키는 가상 노드를 스킵하면서 리스트를 채운다.
데이터가 여러 노드에 전파되는 것은 비동기적으로 (아직 어떻게 비동기적으로 동작하는지 설명하지 않았다. 후술할 예정) 발생한다. 이러한 이유로 Dynamo는 결과적 일관성(Eventual Consistency) 특성을 갖게 된다. 결과적 일관성은 일시적으로 데이터가 일관적이지 않을 수 있지만 결국 같은 데이터를 보장한다는 뜻이다. 예를 들어 Put을 호출해 데이터를 쓰는 작업을 할 때, 필요한 모든 노드에 데이터가 복제되는 것을 기다렸다가 응답을 보내주지 않는다. 아직 몇 개의 노드는 데이터를 쓰기 전이지만 Put에 대한 성공 응답을 보낸다. 만약 이런 상황에서 연속적으로 Get 요청을 보내면 어떤 노드의 데이터를 읽느냐에 따라 최신 버전의 데이터를 가져오지 못할 수도 있다는 것을 뜻한다. 위에서 살짝 예시를 들었는데, 쓰기 상황에서 이렇게 최신 데이터가 아닌 오브젝트를 기반으로 업데이트를 진행하게 되면 데이터 버저닝(분기, 데이터 충돌)이 발생한다.
앞서 언급한 것처럼 분기된 데이터를 통합하기 위해서 두 가지 결정이 필요하다. 언제 통합할 것인지? 누가 통합할 것인지? 그리고 Dynamo에서는 읽기 시점에 클라이언트에서 해결한다고 설명한다.
데이터 버저닝과 이를 해결하는 방법을 설명하기 전에 먼저 간단하게 Dynamo의 시스템 인터페이스를 확인해보자. 데이터에 접근하기 위한 Get과 업데이트를 위한 Put이 있다. 각각은 다음과 같이 호출된다.
get(key): 스토리지 시스템에서 키와 연결된 오브젝트 복제본을 찾아 컨텍스트가 담긴 단일 오브젝트 또는 컨텍스트가 담긴 오브젝트 리스트를 반환한다.put(key, context, object): 오브젝트 복제본이 연관된 키에 의존해서 어디에 위치해야 하는지 결정하고,object를 디스크에 쓴다.
get의 결과를 “컨텍스트가 담긴 오브젝트“라고 표현하고 있다. 컨텍스트는 데이터의 버전 정보를 포함한 메타데이터를 의미한다. 복수가 될 수 있다는 것은 하나의 데이터에 대해 여러 갈래로 나눠진 데이터 버전이 있는 경우 해당 버전들을 모두 가져오기 때문이다. put의 인자에서 context를 통해 수정 대상인 오브젝트 컨텍스트를 전달하고 기존에 나뉘어있던 버전들을 마지막 put을 기준으로 통합하게 한다.
Dynamo의 쓰기 과정은 읽기 이후 쓰기를 수행하는 식으로 클라이언트에서 사용해야 하는 구조인 것으로 보인다.
Dynamo의 오브젝트 버전 관리는 vector clock을 사용한다. 이는 어떤 노드에 저장되어 있는지, 몇 번째 데이터 수정인지를 담고 있는지, 이렇게 두 가지를 갖는 튜플 리스트이다.
1 | vector clock = [(Node, Counter)...] |
컨텍스트 안의 vector clock을 비교해서 인과적인 순서(앞선 버전인지, 동시에 나눠진 버전인지)를 밝힐 수 있다. 많은 경우 새 버전이 과거 버전을 포함하고 있기 때문에 시스템 안에서 정규 버전(나눠진 두 버전을 조정한 새로운 버전)을 결정할 수 있다. 이렇게 시스템에서 버전을 조정하는 과정을 “syntactic reconciliation“이라고 한다. 그러나 동시 업데이트에 의한 분기는 클라이언트에 의해 조정이 된다. 위에서 언급했던 것처럼 get(key)를 통해 복수의 오브젝트 버전을 받으면 클라이언트에서 적절한 로직을 통해 이를 합치고 업데이트해 줘야 한다. 이렇게 클라이언트에 의해서 조정하는 것은 “semantic reconciliation“이라고 한다.
따라서 정확하게는 Dynamo는 데이터베이스에 의한 조정과 클라이언트에 의한 조정, 두 가지 방법 모두 사용하고 있다고 볼 수 있다.
일시적 실패
쓰기 동작 중 특정 노드의 장애로 인해 일시적인 실패가 발생할 수 있다. 이에 대한 처리를 Hinted Handoff라고 불리는 방식으로 해결하고 있다. 일단 이 설명을 하기 전에 먼저 “쓰기 실패 상황“ 또는 “읽기 실패 상황“을 정의해야 한다. 구체적으로 어떻게 비동기 복제를 하면서 응답을 전달해주는지 확인해보자.
Sloppy Quorum
쿼럼(Quorum)은 “정족수”라는 뜻이다. 조금 단순하게 설명하자면 읽기의 최소 성공 수를 R, 쓰기의 최소 성공 수를 W라는 변수를 사용해 시스템에서 읽기와 쓰기의 실패 여부를 확인하는 방법이다. Dynamo 시스템에서 Get과 Put 요청은 어떤 스토리지 노드든 받을 수 있다. Read 또는 Write 요청을 처음 받은 노드를 “coordinator“라고 부른다. 일반적으로 coordinator는 preference list를 만들 때 첫 번째 노드이다.
요청은 HTTP를 통해 전달되는데, 로드 밸런싱을 통해 앞단에서 요청을 관리한다면 coordinator는 맨 첫 번째 노드가 아닐 수도 있다. 로드 밸런서를 사용하지 않는 경우 Partition-Aware 클라이언트 라이브러리를 사용해 어떤 노드에 요청을 보내야 하는지 클라이언트에 의해 결정하도록 한다.
위 이미지처럼 복제해야 하는 노드 수만큼 preference list가 지정되고 coordinator는 이 리스트 안의 나머지 노드에 데이터를 전파한다. 그리고 정족수만큼의 정상 응답을 받으면 클라이언트에게 성공 응답을 보내준다. 예시에서는 W = 2로 설정되었기 때문에 위 이미지의 녹색 박스 노드에서 정상적으로 값을 저장했다면 이 요청은 성공한 요청이 된다.
이 방법은 “Strict Quorum” 시스템으로, 만약 복제되어야 하는 노드들 중에 최소 정족수만큼의 성공을 만들지 못하면 실패 처리 된다. 만약 preference list 안에 있는 N개의 노드 중 N - W - 1개만큼의 노드가 장애 상황이라면 쓰기 실패 상황이 발생한다. 그러나 아마존은 실패 처리를 극단으로 최소화하고 싶어 했다. 그래서 도입한 시스템이 “Sloppy Quorum”이다. 이름에서도 알 수 있듯 조금 느슨하게 쿼럼을 만족시키는 방식이다.
본래 preference list는 키를 해시한 다음 링 위에서 시계 방향으로 봤을 때 첫 번째로 만나는 노드를 포함해 상위 N개의 노드가 속하게 된다. 그런데 이 노드를 단순히 상위 N개가 아니라 “건강한 노드 상위 N개”로 만드는 것이다.
위 예시에서 설정 파라미터값이 N = 3, W = 3이고 만약 노드 D에 장애가 발생했다고 가정해보자. 그렇다면 preference list는 실제로 B, C, E 노드를 담고 있게 된다. 이런 방식에서 장점은 가용성을 높일 수 있다는 장점이 있지만, 문제는 약속과 다른 노드가 데이터를 저장할 수 있다. 레플리카의 범위는 노드 D까지인데, E에 데이터가 저장된 상황이다.
Hinted Handoff
이 문제를 해결하기 위해 Hinted Handoff라는 전략을 사용한다. E로 전달된 복제본 데이터는 메타 데이터 안에 원래 저장될 타겟 노드 정보를 포함하고 있다. 이 정보를 “힌트”라고 표현한 건데, 힌트가 박힌 복제본을 받으면 노드는 원래 저장소와 분리된 다른 로컬 임시 저장소에 해당 데이터를 저장한다. 본래 노드가 다시 복구되면 임시 저장소에 담긴 데이터를 보내주고 임시 저장소에서는 삭제한다.
이러한 Sloppy Quorum과 Hinted Handoff를 가지고 가용성을 크게 높일 수 있게 된다. 만약 W = 1이라면, 모든 노드가 장애 상태여야 쓰기가 실패한다. 하지만 이 방법은 일시적인 장애 상황에서 처리를 위한 방법이고, 영구적인 실패 이후 데이터 동기화 과정을 위해서는 다른 방법이 필요하다. 간단히 설명하자면, 가지고 있는 데이터를 머클 트리로 구성해 변경이 발생한 지점을 특정하고 변경된 부분만 데이터를 전송할 수 있게 해준다. 머클 트리로 두 노드의 데이터가 같은지 확인하는 케이스는 분산 시스템에서 자주 등장한다. 가장 유명해진 예시로는 블록체인이 있다. 이 링크에서 머클 트리에 대한 설명과 머클트리를 블록체인과 Dynamo에 적용한 유즈 케이스 설명을 확인할 수 있다.
실제 운영
Dynamo는 몇 가지 서비스에서 다양한 설정값으로 사용되고 있다. 각 서비스는 데이터 버전을 합의하는 로직을 독립적으로 구성하고, 서비스의 특성에 따라서 쿼럼 파라미터인 R, W값을 설정한다. 일관성이 중요하다면 W값을 높게 설정하고, 읽기(쓰기) 성능 자체가 더 중요하다면 R(W)값을 낮춘다. Dynamo의 일반적인 (N, R, W)는 (3, 2, 2)로 구성되어있다.
Reference
- https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
- https://en.wikipedia.org/wiki/CAP_theorem
- https://ko.wikipedia.org/wiki/%EC%9D%BC%EA%B4%80%EB%90%9C_%ED%95%B4%EC%8B%B1
- https://www.waitingforcode.com/general-big-data/dynamo-paper-consistent-hashing/read
- https://www.allthingsdistributed.com/2017/10/a-decade-of-dynamo.html
- https://jimdowney.net/2012/03/05/be-careful-with-sloppy-quorums/
- https://medium.com/coinmonks/merkle-trees-concepts-and-use-cases-5da873702318
DynamoDB Internals (1) - Dynamo
