DynamoDB의 시스템 디자인과 분산 트랜잭션 구현 원리

Published in

취미로 논문 읽는 그룹

35 min readSep 4, 2023

DynamoDB는 AWS 관리형 분산 키-밸류 저장소입니다. 만약 본인이 AWS 클라우드를 이용하고 있고 대규모 트래픽을 견뎌야 하는 키-밸류 NoSQL 데이터베이스가 필요하다면 DynamoDB를 검토하게 되실 겁니다.

AWS는 USENIX ATC학회에 2022년, 2023년에 각각 2개의 논문을 발표했습니다. 하나는 시스템 디자인에 대해, 또 하나는 분산 트랜잭션 구현 원리에 대해 소개합니다. 이번 글은 이 두개의 논문을 요약 정리했습니다.

Table of Contents

1장. 키-밸류 저장소를 글로벌 스케일로 확장하기
2장. DynamoDB 개요와 시스템 아키텍처
3장. 분산 트랜잭션 구현의 어려움
4장. DynamoDB에서 분산 트랜잭션을 구현한 방법
5장. 마무리

1장. 키-밸류 저장소를 글로벌 스케일로 확장하기

키-밸류 저장소는 단순하게 PutItem(key, value), GetItem(key)이 2개의 연산을 지원하는 데이터베이스라고 말할 수 있습니다. AWS엔지니어로 빙의해서 글로벌 트래픽을 견딜 수 있는 키-밸류 NoSQL 데이터베이스를 만들어야 한다면 어떻게 할 수 있을까요?

AWS DynamoDB는 피크 타임 기준 1초에 1000억건의 요청을 처리하고 있습니다. (논문에서 발췌), 이 정도는 되야 글로벌 스케일이라고 할 수 있군요

위 그림은 디렉토리-기반 아키텍처(Directory-Driven Architecture)라고 불리는 분산 키-밸류 시스템을 묘사합니다. 루트 노드는 키에 대응되는 스토리지 노드 정보를 맵핑해서 가지고 있고, 클라이언트가 루트 노드로 부터 정보를 받아 스토리지 노드에 직접 접근하면 트래픽과 디스크 I/O를 분산시키는 효과가 있습니다. 서버의 개수만 충분히 많이 준비한다면 글로벌 트래픽을 받기에 부족함이 없습니다.

벗(But), 이 시스템은 세 가지 문제가 있습니다. ① 서버의 개수가 고정되어 있어서 트래픽이 많지 않은 상황에서는 불필요한 리소스 낭비가 예상된다는 것, ② 노드에 장애가 발생하면 자칫 데이터가 유실될 위험이 있습니다. ③ 특정 키가 핫스팟인 경우 특정 서버에 과부하가 발생할 수 있습니다. 우리는 이런 문제를 해결하기 위해 일관성 해시(Consistent Hash)를 이용할 수 있습니다. 한 번, 저장된 데이터의 각 키들을 선형적인 선으로 길게 늘어놓고 양쪽 끝을 잡아 구부려서 원을 만든다고 상상해봅시다.

일관성 해시란 위와 같이 노드와 키를 가상의 링(Ring)으로 표현한 모습입니다. 이제 링(Ring)위에 키와 서버를 해시값을 이용해서 적절한 위치에 둡니다.

키가 저장될 서버는 원 위에서 각 개별 키들이 오른쪽 시계방향으로 흘러서 만나게 되는 첫번째 서버로 결정합니다. 그림 (A)를 보시면, {K1, K4}는 S1서버에 할당되고 {K2}는 S2에 할당되는 모습을 볼 수 있습니다. 만약 지금 {S1, S2, S3}로 구성된 클러스터에 S4 서버가 하나 더 추가된다면 다시 키를 어디에 저장할지 결정합니다. 간단하죠? 하지만 단순히 서버를 랜덤한 위치에 두는 것은 그림 (B)처럼 애매한 위치로 형성되면 파티션이 균등하게 형성되지 못해서 특정 서버에 부하가 몰리게 됩니다. 이 문제를 해결하기 위해 가상 노드라는 개념을 이용합니다.

가상노드란 동일한 서버를 랜덤하게 여러개 생성해서 링 위에 배치하는 방법입니다. 실제로는 서로 다른 해시 함수 N개를 준비하고 이 해시함수의 결과로 위치를 선정합니다. 위와 같은 방식을 따를 경우 서버가 추가되고 삭제되면서 재배치 되어야 하는 키의 총 개수는 k/N이 됩니다.

②번 문제는 데이터를 복제 저장해서 사용합니다. 원래의 일관성 해시 링은 키가 시계방향으로 가면서 만나는 첫 번째 서버에 저장하는 거라면, Dynamo에서는 시계방향으로 만나는 K개의 서버에 데이터를 중복 저장하는 방식으로 복제합니다. 이 방식을 Cassandra에서는 SimpleStrategy라고 부르구요. 그리고 Cassandra는 데이터 센터 화재 같은 사고도 고려해서 여러 데이터 센터에 걸쳐 복제할 수 있는 네트워크 토폴로지 전략도 지원하고 있씁니다.

이런 분산 키-밸류 시스템은 어디에 이용할까요?

소수의 생산자가 80%의 컨텐츠를 생산해내는 파레토의 법칙이 작용하는 서비스는 전통적인 관계형 DB(RDBMS)가 좋은 선택지가 될겁니다. RDBMS는 쓰기 노드는 한 대로 제한되며 다수의 복제 노드가 존재합니다. 데이터를 쓸 때는 쓰기 노드에 요청을 보내고 데이터를 읽을때는 읽기 노드에서 불러들이는게 일반적인 패턴입니다. 유저 트래픽이 증가해도 읽기 요청만 급격하게 늘어날 뿐 쓰기 요청은 안정적이기 때문에 트래픽의 증감에 대해 유연하게 대처할 수 있습니다.

애플리케이션 성격에 따라 쓰기 비율이 높은 경우가 있습니다. 대표적인 예시로 채팅 서비스는 사용자 모두가 쓰기 요청을 발생시키는 생산자가 되고 준실시간으로 반응해야 합니다. 전통적인 데이터베이스는 읽기 성능을 위해 인덱스를 사용하는데요. 대규모 데이터가 쓰여지고 있는 상황에선 인덱스의 크기가 매우 크기 때문에 쓰기 속도가 시간을 따라 점차 느려집니다. 그래서 많은 채팅 서비스들은 분산 키-밸류 데이터베이스를 활용하고 있습니다. 대표적으로 Discord 에서 Cassandra를 사용하고 있는 것으로 잘 알려져 있습니다.

2장. DynamoDB 개요와 시스템 아키텍처

① DynamoDB의 역사

DynamoDB의 이름은 아마존이 2007년에 발표한 논문인 Dynamo: Amazon’s Highly Available Key-value Store 에서 유래되었습니다. 오늘날 인용수가 6000이 넘은 seminal-paper입니다. Dynamo는 일관성 해시를 채용한 분산 키-밸류 저장소인데요. 이름이 같아서 DynamoDB도 일관성 해시를 이용해서 개발되었다고 오해하는 경우가 있습니다.

USENIX ATC 22에서 발표된 Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service 논문에는 이 오해를 푸는 내용이 서술되어 있습니다. Dynamo는 원래 아마존에서 쇼핑 장바구니 데이터를 저장하기 위해 개발되었고 수평 확장성, 가용성, 영속성을 보장하는 데이터베이스입니다. 이 당시에는 클라우드 관리형 서비스는 아니었고 스스로 관리해야 하는 설치형 데이터베이스였는데요. 당시에는 글로벌 스케일에서 사용할 수 있는 유일한 데이터베이스였기 때문에 아마존 내에 많이 전파되었습니다.

하지만, 아마존 엔지니어들이 Dynamo를 직접 운영해야 했고 데이터베이스 전문가 수준의 지식을 요구했기 때문에 부담이 있었죠. 무엇보다 애플리케이션 서버가 데이터베이스 시스템에 직접 접근하는 방식이 커넥션 관리, 동시 처리, 스키마 업그레이드 등의 이유로 확장성있게 사용하는데에 병목이 있었습니다.

그리고 시간이 지나 Amazon S3와 Amazon SimpleDB가 런칭되었습니다. 이 시스템은 엔지니어가 스토리지 관리 부담없이 API만을 이용하는 시스템이었는데요. 아마존의 엔지니어들은 Dynamo가 더 좋은 성능과 기능을 갖추었음에도 S3와 SimpleDB를 적극 활용하기 시작합니다. 하지만 SimpleDB는 테이블당 용량과 초당 처리량(throughput)이 제한되어 있었는데요. 아마존 엔지니어들은 그래서 동일한 스키마를 갖춘 데이터를 여러 테이블로 쪼개는 편법으로 대응해왔습니다. 그리고 바로 이 페인포인트를 해결하고자 Amazon DynamoDB가 Dynamo와 SimpleDB의 특징들만 모아 2012년 AWS에 출시되었습니다.

② DynamoDB의 특징

DynamoDB의 최대 장점을 하나 뽑자면 일관된 레이턴시를 보장한다는 겁니다. 데이터베이스를 직접 운영한다면 트래픽이 급격히 늘어날 때 노드를 제때 증설하지 못해서 유저에게 안좋은 경험만 남길 수도 있고요. 데이터베이스에 데이터가 꾸준히 증가하면 어느 순간 쓰기/읽기 성능이 떨어지는 걸 경험할 수 있습니다. 각 상황마다 대응할 수 있는 방법은 존재하지만 DynamoDB를 사용한다면 이런 상황에도 항상 일관된 경험을 제공하기 때문에 개발자가 온전히 서비스 개발에 집중할 수 있습니다. 이 외에도 DynamoDB는 아래 6개의 특징을 가집니다.

완전 관리형 클라우드 서비스
DynamoDB는 개발자를 대신해 소프트웨어 업데이트, 하드웨어 관리, 클러스터 설정, 장애 복구, 데이터 암호화, 백업 등을 처리해주는 완전 관리형 서비스입니다.
멀티 테넌트 아키텍처
DynamoDB의 스토리지 노드는 서로 다른 고객의 데이터를 동일한 물리적 장비에 저장합니다. 이는 고객의 비용을 절감할 수 있게 해주고 아마존의 입장에서는 리소스를 필요한 곳에 적절히 사용할 수 있게 해줍니다.
테이블의 무제한 스케일
DynamoDB에서 하나의 데이터는 아이템이라고 불리고, 아이템은 테이블에 저장됩니다. DynamoDB의 테이블은 데이터를 무제한 저장할 수 있습니다. 시스템은 자동으로 테이블의 크기에 따라 작게는 2,3대의 서버로부터 많게는 수천대의 서버로 데이터를 분산해서 저장합니다.
예측가능한 성능 제공
GetItem, PutItem API는 항상 일관된 레이턴시를 제공합니다.
고가용성
데이터를 여러개의 데이터 센터(AZ)에 분산 복제하며, 노드에 장애가 발생하면 안전하게 새로운 노드에 데이터를 복제해서 영속성과 가용성을 보장합니다.
탄력적인 스키마
스키마를 강제하지 않습니다. 단순히 키/밸류 DB로 이용할 수도 있고 문서 형식의 데이터를 이용할 수도 있습니다.

DynamoDB의 데이터 스키마는 아래 그림과 같습니다. 데이터의 집합은 테이블 단위로 관리하며 한 건의 데이터를 아이템(Item)이라고 부릅니다. 아이템은 파티션 키, 정렬 키, 그리고 속성(Attribute)로 구성됩니다.

③ 시스템 아키텍처

DynamoDB는 데이터를 저장할 스토리지 노드를 선정할 때 해시함수를 이용하긴 하지만 네트워크 토폴로지나 시스템 구성이 일관성 해시와는 많이 다릅니다. 오히려 마이크로서비스의 집합이라고 보는게 좋을 것 같습니다. 위 그림은 DynamoDB의 시스템 구성도를 보여줍니다. 요청 라우터(Request Router)는 유저 요청의 인증/인가, 개별 요청을 알맞은 스토리지 서버로 라우팅 하는 책임을 가집니다. 요청 라우터는 모든 읽기/업데이트 요청을 받아 처리하고, 개별 요청의 목적지를 메타데이터 서비스로부터 조회해서 알맞은 서버로 할당합니다.

그림에는 나와있지 않지만, 다양한 마이크로서비스들이 시스템을 보조하고 있습니다. 대표적으로 AutoAdmin 서비스는 스토리지 장비들을 모니터링 하고 있다가 장애가 발생하면 새로운 장비로 교체하고 데이터를 복제하는 명령을 내리는 역할을 합니다. 이 외에도 point-in-time 복구, 온디맨드 백업, 업데이트 스트림, 글로벌 테이블, 글로벌 세컨더리 인덱스, 분산 트랜잭션 등을 수행하는 마이크로 서비스들이 존재합니다.

초기 Consistent Hash를 이용한 Dynamo는 Self-managed데이터베이스였습니다. 현재 AWS의 DynamoDB는 마이크로 서비스들의 집합이며 키-밸류 저장 기능을 제공하는 서비스의 모습을 하고 있습니다.

④ 스토리지 노드

스토리지 노드는 DynamoDB에서 실질적으로 데이터를 저장하는 인스턴스이며 여러 가용영역(AZ)에 걸쳐 3대의 노드로 클러스터를 이룬 상태복제머신입니다. Paxos 합의알고리즘을 이용하고 있으며 3대의 노드 중 하나가 리더로 선정됩니다. 오직 리더만 쓰기 요청을 수행할 수 있고 읽기 일관성을 제공합니다. 쓰기는 항상 정족수 이상의 노드에 WAL(write-ahead logs)에 기록되어야 합니다. 이 때, 복제노드(Follower)는 최종일관성(Eventual Consistency)를 제공하고 리더는 강한 일관성(Strong Consistency)을 제공합니다.

스토리지 노드는 키-밸류 데이터를 저장하는 역할을 하고 있는데요. DynamoDB는 LSI(Local Secondary Index)라는 파티션 내의 인덱싱을 지원하고 있어서 B-Tree 자료구조를 가지고 있습니다. 인덱스를 가진 스토리지 복제 노드 이외에 WAL 로그만 가지고 있는 로그 복제 노드(Log replica)도 있습니다. 이 노드의 역할은 정족수를 채울 수 없을 정도로 스토리지 노드에 장애가 발생하면 임시적으로 멤버로 참여할 수 있도록 대기하고 있습니다.

⑤ Bursting, Adaptive Capacity, GAC

여기서는 Bursting, Adaptive Capacity, GAC에 대해 설명합니다 :)
이번 장을 읽고 이 세 가지 단어를 설명할 수 있는지 유의하며 읽어주세요.

DynamoDB는 초당 처리량을 나타내는 Write Capacity Units(WCUs), Read Capacity Units(RCUs) 수치에 따라 돈($)을 지불해야 됩니다.

WCUs : 1KB 용량에 한해 1초에 1번의 쓰기 요청을 보낼 수 있음
RCUs: 4KB 용량에 한해 1초에 1번의 일관성 읽기를 제공함

현재 서울 리전을 사용하면 1000 WCU=$0.7049, 1000 RCU=$0.14098로 가격이 형성되어 있습니다. 1초에 1000건의 요청을 처리할 수 있는 키-밸류 저장소를 가진 셈입니다.

자, 이제 AWS 앤지니어에 빙의해서 생각해보자구요. 내가 3000 WCUs를 세팅했으면 반드시 1초에 3000건의 요청을 서비스가 받아줘야 합니다. 이건 돈과 신뢰의 문제입니다. 완벽할 순 없더라도 최대한의 노력으로(best-effort) 초당 3000건의 요청을 데이터 접근을 제공해야 합니다. 고객의 데이터량이 많지 않더라도 하나의 물리적 노드에 전부 집어넣으면 네트워크 대역폭, I/O 등으로 인해 요청을 전부 처리할 수 없습니다. 따라서, 파티션 키를 기준으로 데이터를 적절히 분할해서 각 파티션에 저장합니다.

초기 버전의 DynamoDB에서 파티셔닝은 테이블의 처리량(throughput)에 의해 결정됩니다. 클라우드 장비의 스펙이나 네트워크 대역폭을 고려해서 하나의 파티션이 최대 1000 WCUs 만큼만 처리 가능하다는 결론이 나왔다고 합시다. 만약 테이블이 3200 WCUs로 설정했으면 DynamoDB는 800WCUs씩 할당된 4개의 파티션을 생성합니다. 시간이 지나서, 고객이 6000 WCUs로 증가시키면 기존에 존재하는 파티션을 분할합니다. 다시 말하면, 1000 WCUs를 가진 6개의 파티션이 아닌, 750WCUs를 가진 8개의 파티션을 생성하게 됩니다. 여기엔 총 3가지 문제가 있습니다.

처리량 희석(throughput dilution)
위 예시에서 고객이 WCUs를 증가시켰지만 파티션 별로 할당된 WCUs는 800에서 750으로 감소했습니다.
핫 파티션(hot patition)
특정 아이템에 대한 트래픽이 몰리는 경우가 있습니다. 쇼핑몰에서 특정 제품이 할인율이 높아서 인기가 많다거나, 화제가 되는 인물의 인스타그램 팔로우 요청 등 많은 예시를 상상해 볼 수 있습니다. 이 경우, 파티셔닝을 하더라도 특정 파티션에 트래픽이 몰리게 되어서 파티션에 할당된 WCUs를 모두 소진하고 쓰로틀링(throttling)됩니다. (throttling을 표현하는 적절한 한국어를 모르겠네요 🤔)
균등하지 못한 접근 패턴 (non-uniform access)
서비스가 항상 균일한 트래픽을 발생시키는 건 아닙니다. 모바일 게임의 경우 출/퇴근 시간이나 새로운 이벤트 및 컨텐츠 출시가 있으면 트래픽이 증가합니다. 라인 메신저에선 새해에 트래픽이 급증하는 걸로 알려져 있습니다.

Provisioned WCUs를 작게 잡으면 요청 쓰로틀링이 발생하고, 높게 하자니 돈을 낭비하게 됩니다. 이 문제를 해결하기 위해, 현재의 DynamoDB는 Bursting 이라는 개념을 사용합니다. 기본적인 아이디어는 “과거 사용하지 않았던 WCU를 누적하고 있다가 필요할 때 소진한다 입니다”이며, 파티션에 할당된 WCU보다 더 많은 요청을 처리하도록 합니다.

DynamoDB는 대표적인 처리율 제한(Rate Limit) 알고리즘인 토큰 버킷을 사용합니다. 여기선, 1초 단위의 토큰 버킷이 아닌 5분 동안 토큰을 계속 쌓아두다가 필요할 때 사용하게 됩니다. 이 값은 전역 승인 제어(GAC : Global Admission Control) 서버가 관리하고 있다가 Request Router가 로컬의 토큰을 모두 소진하고 나면 GAC서버로 부터 요청하여 토큰을 얻어냅니다.

이것으로 처리량 희석과 short-lived spike문제는 어느 정도 대응할 수 있게 되었습니다. DynamoDB는 긴 시간에 걸쳐 반복적으로 발생하는 long lived spike에도 대응할 수 있게 사용자에게 Adaptive Capacity 기능을 제공합니다. AWS에선 테이블 단위로 토큰 소모량과 트래픽 양을 모니터링 하고 있다가 테이블에 쓰로틀링이 발생하면 용량을 늘리고, 남는 토큰이 있으면 용량을 줄입니다.

[출처 : AWS 블로그] 파티션 4에 Adaptive Capacity가 적용된 모습

논문에선 bursting과 마찬가지로 best-effort 접근법이고 단순하지만 99.99%의 throttling을 막는 효과가 있다고 표현했습니다. 현재 DynamoDB에서 기본값으로 테이블을 생성하면 5 WCUs/5 RCUs와 Adaptive Capacity가 적용된 걸 사용하게 됩니다. 물론, 아마도 우리가 내야 할 비용또한 고무줄 처럼 늘었다 줄었다 할겁니다. 하지만, 어차피 고객 경험을 위해 감내해야 할 트래픽이고 고정값을 사용하는 것 보다는 비용 절감 효과가 있을 겁니다.

3장. 분산 트랜잭션 구현의 어려움

애플리케이션 개발자들은 수십년 동안 장애 및 동시성 처리를 위해 데이터베이스가 제공하는 트랜잭션 기능에 의존해왔습니다. 트랜잭션 개념이 없는 어딘가의 평행우주에선 프로그래머들이 아래 문제점들을 해결하느라 매일 밤낮으로 일하고 있을 겁니다.

소프트웨어나 하드웨어는 언제나 실패할 수 있다
애플리케이션은 연산을 실행하다가 언제나 죽을 수 있다
네트워크는 어떤 이유에서라도 언제나 단절될 수 있다. 구글의 해저 케이블은 상어의 공격을 받아서 단절된 적이 있다.
여러 클라이언트가 동시에 쓰기를 실행해서 다른 클라이언트가 쓴 내용을 덮어 쓸 수 있다
클라이언트가 부분적으로만 갱신해서 비정상적인 데이터를 읽을 수 있다
클라이언트 사이의 경쟁조건은 예측하지 못한 버그를 발생한다

트랜잭션은 여러개의 읽기와 쓰기 연산을 하나의 논리적 단위로 묶어서 이런 문제들을 단순화 시킨 매커니즘입니다. 트랜잭션의 원자성(Atomicity)은 일련의 순차적인 연산들이 장애 상황에서 부분 결과를 만들지 않을 것을 보장하고, 고립성(Isolation)은 여러 트랜잭션이 경쟁적으로 실행되고 있는 상황에서 서로간의 연산이 간섭을 일으키지 않을 것을 보장합니다.

트랜잭션이 엄청난 편의 기능을 제공함에도 불구하고 NoSQL 생태계에서는 트랜잭션을 제공 하는 사례가 적습니다. 분산 키-밸류 데이터베이스는 무제한 수평 확장성, 자동 파티셔닝, 복제를 이용한 내결함성 등을 갖추기 위해 트랜잭션 기능을 희생하는 경우가 많습니다.

분산 데이터베이스에서 데이터는 여러 노드로 파티셔닝 되어 있는데, 신뢰할 수 없는 네트워크 위에서 여러 노드에 걸쳐 원자성을 보장해야 하는 분산 트랜잭션은 구현 및 실제 운영하기에 여러 어려움들이 있습니다. 이번장에서는 분산 트랜잭션에 대해 제가 아는 만큼만 소개해드리고자 합니다.

(1) 클라이언트에서 여러 노드로 트랜잭션 전송하기

클라이언트가 여러 데이터베이스로 트랜잭션을 전송하고 개별적으로 커밋/어보트를 결정하는 건 바람직하지 않습니다. 어떤 노드에선 제약 조건 위반으로 인해 실패할 수 있고, 네트워크 문제로 요청이 누락되었거나, 장애가 발생했을 수도 있습니다. 커밋시킨 후에 나중에 어보트로 소급적용하는 건 트랜잭션에선 허용되지 않습니다. 일단 커밋된 연산은 다른 트랜잭션이 읽을 수 있는 상태가 되고 어보트를 소급적용하려면 트랜잭션에 의존한 모든 연산을 어보트 해야 하기 때문입니다.

(2) Two Generals’ Problems

Ref. Distributed consensus: What do money transactions and attacking armies have in common?

두개의 군대가 계곡 아래의 성을 양쪽에서 포위하고 공격할 준비가 되어 있습니다. 군대의 각 장군은 전령을 보내 공격 시간을 합의해야 하는데, 전령이 이동하면서 붙잡힐 가능성이 있습니다. 만약, 하나의 군대가 단독으로 공격을 시도하면 대패할 것이기 때문에 반드시 공격 시간을 동의해야 합니다.

결론부터 말씀드리자면, 컴퓨터 과학자들은 이 문제는 절대 풀 수 없음을 증명했습니다. 우리는 복잡한 수학 계산 없이도 이를 직관적으로 이해할 수 있습니다.

장군 A가 먼저, 공격 시간을 합의하기 위해 메신저를 보냅니다. 여기서 메신저가 붙잡혀서 메시지가 도착하지 않을 수 있습니다. 그래서 장군 A는 장군 B로부터 확인(Acknowledgement) 메시지를 받아야 합니다. 반대로 장군 B도 똑같은 상황입니다. 본인이 전송한 확인 메시지가 유실 될 수 있기 때문에 장군 A로부터 ACK 메시지를 받아야 합니다. 이런 서로간의 모순이 영원히 발생하기 때문에 두 명의 장군은 시간을 합의할 수 없습니다. 이 문제는 2대의 노드가 서로 통신하여 트랜잭션을 커밋하도록 결정하는게 왜 불가능한지를 설명해줍니다,

원래 이 문제는 분산 합의에 대해 설명하는 문제입니다. 현대 분산 시스템들은 네트워크의 유실이 자주 발생하지 않는다고 가정하고, 3대 이상의 노드에서 다수결만큼은 합의할 수 있도록 하는 알고리즘을 연구하고 개발되어 왔습니다.

(3) Two-Phase Commit Protocol

현실적인 대안으로 많은 서비스들은 2단계 커밋 프로토콜을 이용해서 분산 트랜잭션을 구현합니다. 구현 원리는 단순해요. 코디네이터(Coordinator)라고 불리는 제 3자가 커밋과 어보트 메시지를 결정해서 각 데이터베이스에 전달합니다.

2PC 트랜잭션은 평상시처럼 데이터를 읽고, 쓰면서 시작합니다. 여기서 개별 데이터베이스 혹은 노드들은 참여자(participant) 라고 부릅니다. 참여자가 데이터를 모두 임시적으로 연산을 하고나면 코디네이터가 준비 단계에서 트랜잭션을 실제로 커밋할 수 있는지 물어봅니다. 만약, 참여자가 YES라고 답변한다면 이 트랜잭션은 무조건 커밋되어야 합니다. 나중에 디스크 공간이 모조라네, 제약조건을 제대로 체크하지 않았네 하는 변명으로 어보트 할 수 없습니다. 마지막으로 커밋 명령을 내려서 트랜잭션을 모든 노드에 커밋합니다.

이 프로토콜은 단순하지만 확실하게 원자성을 보장하는 것으로 알려져 있습니다. 그런데, 소프트웨어 엔지니어인 우리가 보기에 직관적으로 몇 가지 고려해야할 사항들이 떠오릅니다.

(1) 먼저, 코디네이터가 단일 장애 지점(SPoF)입니다. 코디네이터에서 장애가 나면 코디네이터가 복구될때까지 하염없이 기다릴 수 밖에 없습니다. 즉, 가용성이 다소 감소됩니다. Paxos/Raft 같은 분산 합의 알고리즘을 쓰면 이 문제를 다소 완화 할 수 있긴합니다.
(2) 데이터베이스가 장애가 발생하면 복구될때 까지 코디네이터는 무한히 재시도 해야 합니다. 데이터베이스가 복구 될때까지 참여자는 대기할 수 밖에 없습니다. 이런 상태에 있는 참여자의 트랜잭션을 불확실하다(uncertain)고 합니다.
(3) 원자성은 보장하지만 강한 일관성은 보장하지 않습니다. 2PC 프로토콜은 기본적으로 최종 일관성(Eventual Consistency)만을 보장합니다.
(4) 참여자들이 서로의 자원을 요구하는 경우, 교착상태(deadlock)에 빠집니다.
(5) 여러번의 동기식 네트워크 통신을 요구하기 때문에 성능이 매우 감소합니다. MySQL의 분산 트랜잭션은 10배 이상 느리다고 보고되었습니다.

위의 이유로 2단계 커밋에 대한 평가가 사람마다 엇갈립니다. 구글의 스패너: 구글의 전역 데이터베이스 논문에서는 트랜잭션 없이 코딩하는 것 보다 트랜잭션을 과하게 쓰고 있다가 성능 문제가 발생하면, 그 때 대응하는 것이 낫다 라고 주장하는 한편, 어떤 클라우드 서비스는 성능 문제가 너무 커서 분산 트랜잭션을 지원하지 않기도 합니다.

4장. DynamoDB의 분산 트랜잭션

트랜잭션은 애플리케이션 개발자들이 장애 및 동시성에 대한 고민을 덜어주고 생산성을 높여줍니다. 만약 클라우드 서비스가 트랜잭션 기능을 지원해주면 개발자들의 업무 효율을 많이 높여줄 수 있겠죠? 이런 이유로 DynamoDB는 트랜잭션 기능을 지원하기로 합니다.

Amazon 엔지니어들은 ACID 특징을 제공하면서도 성능, 가용성, 확장성을 희생하지 않으려 했습니다. 자 이제, 트랜잭션을 지원하기로 했으니 기획부터 해야겠죠? USENIX ATC 2023에 발표된 논문에서 Amazon 엔지니어들은 트랜잭션이 다음의 특징을 가지도록 설계했다고 밝혔습니다.

Transactions are submitted as single request
전통적인 RDBMS는 커넥션을 미리 맺어두고 BEGIN, COMMIT, ROLLBACK 메시지를 여러번 교환해서 트랜잭션을 완성합니다. 이런 방식의 추상화는 트랜잭션의 생명주기가 너무 길어지면 성능에 악영향을 미치고요. DynamoDB는 멀티 테넌트 서비스이기 때문에 이런 긴 주기를 가진 세션을 살려두기가 어려웠습니다. DynamoDB의 트랜잭션은 일련의 동작을 하나의 API로 전부 전송하도록 합니다.
Transactions rely on a transaction coordinator while non-transaction operations bypass the two-phase coordination
DynamoDB의 트랜잭션 요청은 트랜잭션 코디네이터 서비스를 거쳐서 2단계 커밋(2PC) 프로토콜을 이용해 원자성을 보장합니다. (이제는 익숙한 내용이시죠?)
Transactions update items in place.
MySQL InnoDB, PostgreSQL은 트랜잭션들이 마지막으로 커밋된 버전을 접근해서 읽어가는 방식인 MVCC를 이용합니다. 하지만, 이런 스냅샷 격리는 추가적인 저장 공간을 요구하는데요. DynamoDB에서 이를 구현하려면 매우 많은 변경이 필요했고, 버전 리텐션 정책이나 기타 스토리지 비용이 증가하기 때문에 단일 버전의 데이터만을 다룹니다. 즉, 데이터를 변경하고자 하면 그 즉시 변경이 반영됩니다.
Transactions do not acquire locks.
병렬로 실행되는 트랜잭션들이 동일한 데이터에 읽기/쓰기를 수행할 때 충돌로 인한 문제를 해소하기 위해 전통적으로 2단계 잠금(Two-Phase Locking)을 쓰기도 합니다. 하지만, 트랜잭션 실패시 락을 해제(releasing) 하는 것과 데드락 상황을 방지하는 등 여러가지 노력이 필요합니다. DynamoDB는 설계를 단순화 하기 위해 낙관적 동시성을 이용합니다.
⭐ Transactions are serially ordered using timestamps.
스토리지 노드에 동시에 들어오는 트랜잭션 요청들에 대해서 직렬성을 보장하기 위해 Timestamp Ordering을 이용합니다. 이건 MVCC도 사용할 수 없고 2PL도 사옹할 수 없었기 때문에 그나마 최선의 대안으로 채택한 느낌이 있습니다. (필자 피셜)

(1) DynamoDB의 분산 트랜잭션

DynamoDB에서 트랜잭션은 TransactGetItems, TransactWriteItems 이 두 가지 API에 의해 제공됩니다. 이 트랜잭션은 Blocking없이 동작을 수행하며 성공/실패에 대한 응답을 줍니다. 만약, 동시 트랜잭션에 의해 충돌이 일어나면 DynamoDB는 트랜잭션을 거부(Reject)합니다. 예를 들어, TransactGetItems를 이용할 때, 동시에 동일한 데이터를 수정하고 있는 트랜잭션이 있다면 해당 요청은 거부됩니다.

//Check if customer exists
Check checkItem = new Check().
  withTableName("Customers").
  withKey("CustomerUniqueId").
  withConditionExpression ("attribute_exists(CustomerId)");

//Update status of the item in Products
Update updateItem = new Update().
  withTableName ("Products").
  withKey (" BookUniqueId ").
  withConditionExpression (" expected_status " = "IN_STOCK").
  withUpdateExpression ("SET ProductStatus = SOLD");

//Insert the order item in the orders table
Put putItem = new Put ().
  withTableName ("Orders").
  withItem ("{"OrderId": " OrderUniqueId ", "ProductId" :" BookUniqueId ", "CustomerId"
 " CustomerUniqueId ", " OrderStatus":"CONFIRMED","OrderCost": 100}").
 withConditionExpression(" attribute_not_exists (OrderId)");

TransactWriteItemsRequest twiReq = new TransactWriteItemsRequest ().
  withTransactItems ([ checkItem , putItem , updateItem ]) ;

DynamoDBclient.transactWriteItems(twiReq);

위 코드는 DynamoDB에서 트랜잭션을 발생하는 예시 코드 입니다. checkItem, updateItem, putItem 이 세 가지 연산을 생성한 다음에 트랜잭션 객체를 생성할 때 배열로 연속적인 연산을 지정하고 네트워크를 통해 DynamoDB로 전송됩니다. 코드를 잘보면 withConditionExpression 을 이용해 제약 조건을 검사하는 코드가 있습니다. 이런 일련의 연산을 정의함으로써 우리는 원자성과 무결성을 챙길 수 있습니다.

(2) DynamoDB 트랜잭션 코디네이터

Ref. DynamoDB 트랜잭션 하이-레벨 아키텍처 | USENIX ATC 2023 | AWS 논문

트랜잭션 요청은 요청 라우터를 거쳐서 트랜잭션 코디네이터로 전달됩니다. 만약, 트랜잭션이 아닌 일반 Get/Put 요청의 경우에는 요청 라우터 단에서 처리됩니다. 코디네이터라.. 이름이 익숙하죠? DynamoDB는 여러 스토리지 노드에 걸쳐 원자성을 보장하기 위해 2단계 커밋(2PC) 프로토콜을 사용합니다.

Ref. DynamoDB / Transaction Coordinator, two phase commit protocol

트랜잭션 코디네이터는 여러 스토리지 노드로 1. 준비 단계에서 데이터를 쓸 수 있는지 물어봅니다. 만약 데이터를 커밋할 수 있다면 트랜잭션 코디네이터는 커밋 메시지를 보내고 참여자 노드는 본인의 로컬 데이터를 수정하면서 마지막으로 수정한 날짜(last write timestamp)를 기록합니다. 이 모든 단계가 끝나야 트랜잭션 코디네이터는 그제서야 성공/실패 유무를 요청 라우터한테 전달하고, 요청 라우터는 클라이언트로 응답을 포워딩 합니다.

여기서 last write timestamp 가 이후에 설명할 Timestamp Ordering 에서 트랜잭션에 직렬성을 부여할 때 사용되는데요. 만약, 데이터를 삭제한 상황이라면 이 값이 존재할 수 없겠죠. DynamoDB는 툼스톤(Tombstones)을 남기는 대신에 파티션 별로 가장 높은 수정 날짜를 기록하는 것으로 삭제된 데이터의 timestamp까지 기록합니다.

💡 툼스톤(Tombstone) 이란?
분산 복제 환경에서 데이터를 바로 삭제하는게 애매한 케이스가 있습니다. 예를 들면, 장바구니가 최대 개수만큼 차서 가장 오래된 상품을 제거한다고 해봅시다. 만약 복제 노드가 딱 이 데이터를 삭제하다가 장애가 발생하고 다시 복구되면 오래된 상품을 제거하는 연산을 2번 수행할 수 있습니다. 그래서 카산드라 같은 분산 DB는 데이터를 바로 삭제하지 않고 툼스톤 레코드를 남기고 아주 나중에 삭제하는 전략을 사용합니다.

(3) Timestamp Ordering Protocol

DynamoDB는 분산 환경에서 원자성을 보장하는데는 2PC를 이용하고 스토리지 노드 내에서의 원자성과 무결성을 보장하는데는 Timestamp Ordering 프로토콜을 키-밸류 시맨틱에 맞게 변형해서 사용하고 있습니다. 이 내용을 더 잘 이해할 수 있게 먼저, 가장 기본적인 모습의 Timestamp Ordering(TO) 부터 살펴봅시다.

각 트랜잭션에는 타임스탬프가 부여됩니다. 임의의 두 트랜잭션 A, B의 타임스탬프가 각각 TS(A), TS(B) 이고 TS(A) < TS(B)의 관계를 가진다면 TO는 A가 먼저실행되고 B가 이후에 실행됨을 보장됩니다.
모든 데이터는 읽은 시간(R-TS)과 쓴 시간(W-TS)를 기록하고있습니다. 만약, 트랜잭션 A가 데이터 X를 수정하려고 하는데 R-TS(X) > TS(A) 혹은 W-TS(X) > TS(A)의 관계를 가진다면 트랜잭션을 어보트 합니다. 다시 말하면,현재 트랜잭션의 타임스탬프 시간 상 미래의 데이터를 읽으려고 하면 트랜잭션을 어보트 합니다.
만약, 트랜잭션 A가 데이터 X를 읽으려고 할때, W-TS(X) > TS(A) 라면 트랜잭션을 어보트 하고요. 아니라면 데이터를 읽은 뒤 데이터 X에대한 읽은 시간을 max(R-TS(X), TS(A))로 교체합니다.

규칙이 매우 간단하죠? 이 알고리즘은 실행된 트랜잭션을 일렬로 세웠을 때 임의의 두 트랜잭션 i, j such that (T_i < T_j)를 선정했을 때 타임스탬프가 TS(T_i) < TS(T_j)의 관계가 성립함을 보장합니다. 즉, DynamoDB의 트랜잭션 코디네이터가 트랜잭션에 단조 증가 시계로 타임스탬프를 제대로 부여하고 네트워크 상에서 스토리지 노드에게 차례대로 전송되기만 한다면 나름 괜찮은 동시성 제어 알고리즘이라고 할 수 있습니다. TO에 대한 더 자세한 내용은 조지아 공과대학의 분산 시스템 강의자료에서 확인하실 수 있습니다.

단순하고 강력한 매커니즘이지만 단점도 있습니다. 불필요하게 트랜잭션을 어보트 할수도 있고 무엇보다 실행 시간이 긴 트랜잭션(long running tx)의 경우 너무 쉽게 어보트 된다는 겁니다. 그럼에도 DynamoDB가 TO를 채택한 이유를 고객들과 같이 커뮤니케이션 하다보니 long running tx 까지는 지원할 필요가 없었다고 합니다. (논문의 결론을 읽으시면 됩니다)

(4) DynamoDB의 Timestamp Ordering Protocol

위에서 아키텍처를 설명하면서 DynamoDB에서 트랜잭션은 트랜잭션 코디네이터를 통해 실행된다고 했었죠. 이 코디네이터가 트랜잭션에 타임스탬프를 부여합니다. 그리고 물론, 대규모 트래픽을 받기 위해서 코디네이터 또한 복수개의 인스터스로 구성되어 있습니다. 그리고, 그림을 잘 보시면 Ledger 라는 별개의 저장공간이 부여되어 있는데요. 이는 코디네이터 장애 발생시 다른 코디네이터가 이어서 처리 할 수 있도록 중간 상태를 기록하는 테이블이고 이 정보도 DynamoDB에 저장되어 있습니다.

DynamoDB는 Timestamp Ordering을 키-밸류 저장 시맨틱에 맞춰서 몇 가지 규칙을 수정해서 이용하고 있습니다. 아래는 논문의 4장. Adapting timestamp ordering for keyvalue operations 을 정리한 내용입니다.

Reads to individual items can always be performed successfully even if there is a prepared transaction that is attempting to write that item.
단순 데이터 한 개를 읽는 연산은 다른 트랜잭션이 준비 단계에 있어도 바로 실행해서 결과값을 주어도 Timestamp Ordering의 제약 조건에 위배되지 않습니다. 생각해보면 직관적으로 이해할 수 있습니다. 이 트랜잭션의 타임스탬프는 이미 데이터의 마지막 쓴 시간과 스토리지 노드에서 대기중인 트랜잭션보다 과거 시간을 받게 됩니다.
Writes to individual items can be performed immediately and serialized before any prepared transactions in many cases
DynamoDB에서 트랜잭션이 아닌 단순 요청은 바로 스토리지 노드로 라우팅 됩니다. 스토리지 노드는 이 요청에 대해 자신이 가지고 있는 모든 트랜잭션보다 더 과거의 타임스탬프를 부여합니다. 이렇게 하면 단순 쓰기 요청도 바로 실행할 수 있고 전체 요청의 직렬성을 보장하게 됩니다. 즉, 유저의 요청이 대기 상태로 있지 않고 바로 연산을 실행됩니다.
Writes to individual items can be performed immediately or delayed and serialized after any prepared transactions in other cases
(2)를 바로 적용하기 힘든 경우도 있습니다. 예를 들면, 내 잔액이 $100 이상인가? 와 같은 조건을 검사하는 트랜잭션이 준비 단계에 있다면 내 요청이 이 조건을 위배되게 만듭니다. 이 경우 요청을 거부(Reject)해도 되지만, DynamoDB에서는 요청을 큐에 넣어뒀다가 트랜잭션이 처리되면 그 때 타임스탬프를 새로 부여하고 연산을 실행합니다.
Write transactions can be accepted even with an old timestamp.
우리가 DynamoDB의 분산 트랜잭션에 대해 이야기 하고 있다는 컨텍스트를 잊으시면 안됩니다. 겨우 하나의 트랜잭션이 여러 대의 스토리지 노드에 요청을 전달할 수 있습니다. 만약, 너무 잦은 어보트가 발생하면 트랜잭션 기능이 있어도 사용성이 매우 떨어지겠죠. 그래서 왠만하면 통과되는게 좋습니다. 그래서 어떤 일을 하냐면 스토리지 노드에 도착한 쓰기 연산이 트랜잭션의 일부이고 너무 과거의 타임스탬프를 가지고 있다고 하더라도 트랜잭션을 취소시키지 않는다는 겁니다. 어차피 미래의 타임스탬프에 의해 덮어쓰여질 값이기 때문에 그냥 무시합니다. (기본적인 Timestamp Ordering에선 이 트랜잭션은 취소될 겁니다)
Read transactions can be executed in a single round rather than using a two-phase protocol
데이터를 읽기만 하는 트랜잭션이라면 단일 페이즈로 끝날수도 있습니다. 트랜잭션 코디네이터는 개별 스토리지 노드로 요청을 보낼 때 읽기 시간을 동봉해서 전송합니다. 스토리지 노드는 읽기 시간 보다 데이터의 시간이 더 현재와 가깝다면 어보트 하고 아니라면 결과값을 반환합니다. 코디네이터는 모든 결과를 종합했을 때 모두 정상 응답을 주었을 때 클라이언트에게 결과값을 반환합니다. 이게 단일 페이즈가 가능한 이유는 아이템의 읽기 시간은 데이터로 기록하지 않기 때문입니다.
Transactions that write multiple items in a single partition can be executed in a single round rather than using a two-phase protocol.
쓰기 트랜잭션도 단일 페이즈로 가능한 경우가 있습니다. 트랜잭션이 참조하는 모든 데이터가 하나의 스토리지 노드에 존재하는 경우죠. 따로 준비/커밋 단계를 할 필요없이 바로 커밋해버리면 됩니다.

논문에서는 트랜잭션과 트랜잭션이 아닌 것, 트랜잭션의 read-set(=참조하는 데이터 집합)크기가 증가함에 따라 레이턴시가 얼마나 증가하는 지 등 다양한 측면에서 성능 평가 결과를 소개 자세히 소개하고 있습니다.

저는 여기선 성능 평가 내용은 생략하려고 합니다. 다시 원점으로 돌아와서 이 논문의 취지를 다시 생각해보면 DynamoDB의 예측 가능한 성능을 제공한다는 것, 무한 수평 확장 가능하다는 특색을 지키면서 쓸만한 수준의 트랜잭션 기능을 제공하는 것이었잖아요? 아마도 성능 평가 항목에는 이 주장을 뒷받침 할 수 있는 근거들이 있을겁니다.

5장. 마무리

오늘 우리는 AWS 엔지니어들이 USENIX ATC 학회에 보고한 두개의 논문을 리뷰했습니다. 하나는 시스템 디자인에 대해, 다른 하나는 분산 트랜잭션에 대해 다루었습니다.

오늘도 내용이 많이 길었네요,
긴 글 읽어주셔서 감사드리며 다음에 다시 뵙겠습니다.