언제나 쓸 수 있는 키-값 저장소 Dynamo (Dynamo, SOSP 2007)

출처

참고 이 페이지는 원문 번역이 아니라 한국어 해설이에요. 정확한 표현과 수치는 원문을 확인하세요.

한눈에

• 문제: Amazon 쇼핑몰의 장바구니 같은 서비스는 디스크가 고장 나고 네트워크가 끊겨도 "담기" 요청이 실패하면 곧바로 매출 손실이 됩니다.
• 제안: 강한 일관성 대신 "항상 쓸 수 있음" 을 택한 분산 키-값 저장소입니다. 충돌은 쓰기 때가 아니라 읽기 때 풀고, 필요하면 애플리케이션이 직접 합칩니다.
• 기술 조합: 일관 해싱으로 데이터를 나누고, 벡터 시계로 버전을 추적하고, 느슨한 쿼럼과 힌트 핸드오프로 장애를 견디고, 머클 트리로 복제본을 맞추고, 가십으로 멤버십을 퍼뜨립니다.
• 결과: 운영 기간 동안 요청의 99.9995% 가 성공 응답을 받았고 데이터 손실은 없었다고 보고합니다.
• 지금의 의미: 이 논문은 이후 NoSQL 설계의 교과서가 되었고, AWS 의 관리형 서비스 DynamoDB 는 이 경험을 바탕으로 다시 설계되었습니다.

왜 나왔나

2000년대 중반 Amazon 의 플랫폼은 수만 대의 서버와 수백 개의 서비스로 이루어져 있었습니다. 페이지 하나를 그리는 데 150개가 넘는 서비스가 호출되기도 했습니다. 이런 환경에서는 어딘가 늘 고장이 나 있다고 가정해야 합니다.

당시 많은 서비스는 기본 키로 값을 읽고 쓰는 단순한 접근만 필요했는데도 관계형 데이터베이스를 쓰고 있었습니다. 관계형 데이터베이스는 복잡한 질의 기능을 제공하지만, 확장이 어렵고 장애 시 가용성보다 일관성을 우선합니다. 장바구니처럼 쓰기를 거절하면 안 되는 서비스에는 맞지 않았습니다.

논문은 서비스 수준 협약(SLA) 을 평균이 아니라 99.9 백분위 지연 시간으로 정한다는 점도 강조합니다. 예를 들어 "초당 500건 최대 부하에서 요청의 99.9% 를 300ms 안에 응답" 같은 식입니다. 소수의 느린 요청이 바로 단골 고객의 경험이 되기 때문입니다. 이 기준이 Dynamo 의 여러 설계 결정을 이끌었습니다.

핵심 아이디어

요구 사항과 설계 원칙 (2절)

Dynamo 가 다루는 데이터는 키 하나로 식별되는 작은 바이너리 객체(보통 1MB 미만) 입니다. 여러 키를 묶는 트랜잭션이나 격리 수준은 제공하지 않습니다. 대신 "항상 쓸 수 있는(always writeable)" 저장소를 목표로 했고, 그 결과 충돌 해결이 읽기 시점으로 옮겨집니다. 설계 원칙으로는 점진적 확장, 모든 노드가 같은 역할을 하는 대칭성, 중앙 조정자가 없는 탈중앙화, 성능이 다른 서버를 섞어 쓰는 이질성을 꼽습니다.

일관 해싱으로 나누기 (4.2절)

키를 MD5 로 해싱해 128비트 값으로 만들고, 이 값을 원형 링 위에 놓습니다. 각 노드는 링 위의 위치를 맡고, 키는 링을 시계 방향으로 돌다 처음 만나는 노드에 저장됩니다(그림 2). 노드가 들어오거나 나가도 이웃 구간만 영향을 받습니다. 여기에 "가상 노드" 를 더해 물리 노드 하나가 링의 여러 위치를 맡게 했습니다. 덕분에 부하가 고르게 퍼지고, 성능 좋은 서버에 더 많은 가상 노드를 줄 수 있습니다.

복제와 버전 관리 (4.3, 4.4절)

키마다 담당 노드를 포함해 N 개 노드에 복제합니다. 이 N 개 노드의 목록을 "선호 목록" 이라 부르고, 같은 물리 노드가 중복되지 않게 고릅니다.

쓰기를 거절하지 않으려면 같은 키에 서로 다른 버전이 동시에 생길 수 있습니다. Dynamo 는 각 버전에 벡터 시계(노드와 카운터 쌍의 목록) 를 붙여 버전 사이의 인과 관계를 추적합니다. 한 버전이 다른 버전의 조상이면 오래된 쪽을 버리고, 서로 무관한 갈래라면 둘 다 클라이언트에 돌려줍니다. 그림 3 은 서로 다른 서버에서 갈라진 버전이 클라이언트의 병합으로 하나로 합쳐지는 과정을 보여줍니다. 장바구니라면 두 카트를 합치는 식입니다. 벡터 시계가 끝없이 길어지는 것을 막기 위해 항목이 10개를 넘으면 가장 오래된 것을 잘라냅니다.

쿼럼과 장애 대응 (4.5절에서 4.7절)

읽기는 R 개, 쓰기는 W 개 노드의 응답을 기다리고, R + W > N 이 되도록 설정하면 쿼럼과 비슷하게 동작합니다. 가장 흔한 설정은 (N, R, W) = (3, 2, 2) 입니다. 애플리케이션은 이 세 값을 조절해 성능, 내구성, 일관성 사이의 균형을 직접 고릅니다.

엄격한 쿼럼은 담당 노드가 죽으면 쓰기를 못 합니다. Dynamo 는 "느슨한 쿼럼(sloppy quorum)" 을 씁니다. 선호 목록에서 살아 있는 앞쪽 N 개 노드에 쓰고, 원래 주인 대신 받은 노드는 "이 데이터는 원래 누구 것" 이라는 힌트를 달아 보관하다가 주인이 돌아오면 넘겨줍니다. 이것이 힌트 핸드오프입니다. 오래 지속되는 장애로 복제본이 어긋나면, 키 범위마다 머클 트리를 만들어 서로 비교하고 다른 부분만 동기화합니다.

멤버십과 장애 감지 (4.8, 4.9절)

노드 추가와 제거는 관리자가 명시적으로 지시합니다. 바뀐 멤버십은 가십 프로토콜로 퍼집니다. 각 노드는 매초 무작위로 고른 다른 노드와 멤버십 정보를 교환합니다. 장애 감지는 전역 합의 없이 각 노드가 지역적으로 판단합니다.

구현 (5절)

Java 로 작성되었고, 로컬 저장 엔진은 교체할 수 있게 만들었습니다. 운영 인스턴스 대부분은 Berkeley DB Transactional Data Store 를 썼습니다. 읽기 후에는 오래된 복제본을 고쳐 주는 "읽기 수리" 를 하고, 직전 읽기에 가장 빨리 응답한 노드가 다음 쓰기를 조정하도록 해 자신이 쓴 값을 바로 읽을 가능성을 높였습니다.

실험과 결과

6절은 실제 운영에서 얻은 수치를 보여줍니다.

• 지연 시간 (그림 4): 30일간 측정한 결과 99.9 백분위 지연은 약 200ms 수준이었고 평균보다 한 자릿수 정도 컸습니다. 쓰기는 디스크 접근 때문에 읽기보다 느렸고, 하루 주기의 패턴이 뚜렷했습니다.
• 쓰기 버퍼 (그림 5): 메모리에 객체 1,000개를 담는 쓰기 버퍼를 두자, 최대 부하 시간대 99.9 백분위 지연이 5배 줄었습니다. 대신 내구성이 약해지므로, 복제본 가운데 하나는 디스크에 바로 쓰도록 보완했습니다.
• 부하 분산 (그림 6, 그림 8): 부하가 낮을 때는 불균형 노드 비율이 약 20%, 높을 때는 약 10% 였습니다. 세 가지 파티셔닝 전략을 비교한 결과, 링을 같은 크기의 파티션 Q 개로 나누고 노드마다 Q/S 개 토큰을 주는 전략 3이 가장 효율적이었고, 멤버십 메타데이터도 전략 1 보다 세 자릿수 줄었습니다.
• 버전 분기 (6.3절): 장바구니 서비스를 24시간 관찰했을 때 요청의 99.94% 가 버전 하나만 보았습니다. 두 버전은 0.00057%, 세 버전은 0.00047%, 네 버전은 0.00009% 였습니다. 분기의 주원인은 장애보다 자동화된 클라이언트의 동시 쓰기였습니다.
• 클라이언트 조정 (표 2): 클라이언트가 멤버십을 직접 알고 요청을 조정하게 하자, 99.9 백분위 읽기 지연이 68.9ms 에서 30.4ms 로, 평균 읽기 지연이 3.9ms 에서 1.55ms 로 줄었습니다.

논문은 Dynamo 가 요청의 99.9995% 에 성공 응답을 주었고 그때까지 데이터 손실이 없었다고 밝힙니다. 다만 모든 노드가 전체 멤버십을 들고 가십하는 방식은 수백 대 규모에서는 괜찮지만 수만 대로는 그대로 확장되기 어렵다는 한계도 인정합니다.

지금 AWS 에서는

Dynamo 자체는 Amazon 내부 시스템이었고, 고객이 직접 쓰는 서비스로 공개된 적은 없습니다. 2012년 출시된 Amazon DynamoDB 는 Dynamo 의 경험을 이어받았지만 구조는 많이 다릅니다. DynamoDB 논문(2022) 에 따르면 Dynamo 는 팀마다 직접 설치하고 운영해야 하는 단일 테넌트 시스템이라 운영 부담이 컸고, DynamoDB 는 이를 완전 관리형 다중 테넌트 서비스로 바꾸었습니다. 또한 DynamoDB 의 복제는 느슨한 쿼럼과 벡터 시계가 아니라 파티션별 Multi-Paxos 와 리더 기반 복제를 씁니다. 해시 기반 파티셔닝, 가용 영역에 걸친 복제, 읽기 일관성을 고르는 선택권 같은 생각은 이어졌다고 볼 수 있습니다.

함께 읽기

• DynamoDB 와 ElastiCache: 이 사이트의 기능 문서
• DynamoDB 논문 해설: Dynamo 이후 15년의 변화
• Physalia 논문 해설: 가용성과 강한 일관성을 함께 얻는 다른 접근
• Werner Vogels 의 블로그 글 "Amazon's Dynamo"