0. 장바구니에서 뺀 물건이 결제창에 다시 있다고?

"A typical example of a collapse operation is 'merging' different versions of a customer's shopping cart. Using this reconciliation mechanism, an 'add to cart' operation is never lost. However, deleted items can resurface."

충돌 병합의 대표적인 예는 고객 장바구니의 서로 다른 버전을 합치는 작업입니다. 이 조정 메커니즘을 사용하면 '장바구니에 담기' 작업은 절대 유실되지 않습니다. 하지만, 지운 물건이 다시 나타날 수는 있습니다.

- Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, 4.4 Data Versioning

이게 무슨 말일까요?

장바구니에서 분명히 삭제했던 물건이 결제하려고 보니 슬그머니 다시 들어와 있다는 말입니다. 그러니까, 시스템이 물건을 새로 '담은' 기록을 절대 잃어버리지 않으려다 보니 물건을 '지운' 사용자의 의도를 덮어버린 것이죠.

이 문장이 아마존 고객센터에 접수된 버그 리포트일까요?

아닙니다. 이 문장은 2007년 아마존(Amazon)이 운영체제 분야의 최고 권위 학회인 SOSP에 발표한 분산 시스템의 전설적인 원전, Dynamo: Amazon's Highly Available Key-value Store 논문 본문에 당당히 적혀 있는 내용입니다.

분산 시스템에서는 네트워크 단절로 인해 서버들끼리 통신하지 못하는 상황이 필연적으로 발생합니다. 이때 사용자가 장바구니에 물건을 담거나 지우면, 통신이 끊긴 서버마다 장바구니의 버전이 다르게 갈라집니다.

논문은 통신이 복구된 후 갈라진 버전들을 하나로 접는 작업을 '병합(Collapse operation)'이라 부르고, 그 대표적인 예로 장바구니 병합을 듭니다. 논문은 "an 'add to cart' operation is never lost"라고 명시하며, 담긴 기록을 잃지 않는 쪽으로 병합이 기울어지도록 설계했음을 밝힙니다. 그 결과로 "deleted items can resurface", 즉 지움의 흔적이 밀려나면서 지운 물건이 되살아나는 부작용을 설계의 의도로써 있는 그대로 실토합니다.

아마존은 이 결함을 명확히 알고도 시스템을 이렇게 만들었습니다. 나아가 설계자들은 이 약점을 훗날 애플리케이션 개발자들이 어떻게 다룰지 논문에 예언까지 해두었습니다.

그런데 무척 흥미로운 점이 있습니다.

15년 뒤에 발표된 2022년 DynamoDB 논문을 펴보면, 당시의 예언이 소름 돋게 맞아떨어졌음을 확인할 수 있다는 사실입니다.

1. 2004년 연말, 아마존이 낸 주문서

아마존은 왜 지운 물건이 되살아날 위험을 알면서도 기꺼이 감수했을까요?

기존 인프라가 맞닥뜨린 거대한 한계 때문이었습니다.

아마존 CTO 워너 보겔스(Werner Vogels)의 회고록을 보면 당시의 절박함이 생생하게 묻어납니다. 2004년 연말 쇼핑 시즌 절정기, 아마존이 요구하는 확장성과 트래픽 규모는 당시 상용 데이터베이스 제품들이 보장하는 기술적 사양을 아득히 초과해 버렸습니다. 남들이 쓰지 않는 가혹한 방식으로 데이터베이스를 쥐어짜야만 했습니다.

당시 아마존은 당대 최고의 RDBMS였던 오라클 엔터프라이즈 에디션을 클러스터링하여 사용했고 사내 최고 전문가들을 투입했지만, 기하급수적으로 폭증하는 트래픽의 가용성과 성능 요구를 기존 시스템으로는 더 이상 감당하기 어려웠습니다.

이 위기 속에서 아마존 엔지니어들은 자사의 데이터베이스 트래픽을 분석하다가 놀라운 사실을 발견합니다.

"전체 데이터베이스 연산의 70%가 오직 Primary Key 하나만 써서 단일 행을 찾아오는 단순 조회였다."

복잡한 조인이나 트랜잭션 기능을 꽉 꽉 채운 무거운 관계형 데이터베이스를 굳이 쓸 이유가 없었던 것입니다.

그렇게 2007년에 발표된 다이나모 논문은 완전히 새로운 시스템의 목표치를 명세서처럼 들이밉니다. 논문은 "시스템은 피크타임 초당 500건의 요청이 들어올 때, 99.9 백분위(99.9th percentile) 기준으로 300ms 이내에 응답해야 한다"고 선언합니다.

여기서 99.9 백분위라는 척도를 잠깐 짚고 넘어가 보겠습니다.

이는 전체 요청 1,000건 중 가장 느린 최악의 1건을 제외한, 나머지 999건이 모두 300ms 이내의 속도를 만족해야 한다는 뜻입니다. 그런데 그냥 '평균 응답 시간' 정도로 하면 안되었을까요? 왜 이토록 깐깐한 척도를 잡았을까요?

가장 돈을 많이 쓰는 충성 고객의 경험을 지키기 위해서입니다.

논문은 업계가 흔히 쓰는 평균이나 중앙값 기반 지표로는 모든 고객에게 좋은 경험을 제공할 수 없다고 지적합니다. 아마존처럼 개인화 추천이 많이 들어가는 서비스에서는, 구매 이력이 길고 장바구니에 담아둔 물건이 많은 고객일수록 시스템이 짊어져야 할 계산의 무게가 덩달아 무거워지기 때문이죠. 즉, 데이터베이스 응답 속도가 가장 느린 최상단 구간에 위치하는 사람들이 역설적이게도 아마존에게 가장 중요한 VIP 고객들이니까요.

논문은 평균이라는 뭉툭한 숫자로 이 중요한 고객들이 겪는 답답함을 덮어버리지 않겠다고 명시합니다.

"Industry standard relies on averages, variances and the like... At Amazon, SLAs are expressed and measured at the 99.9th percentile of the distribution. ... Furthermore, experience has shown that it is the customers with the longest history and the most data who are in the 99.9th percentile. These are often the most valuable customers."

업계의 표준은 평균이나 분산 같은 지표에 의존한다. ... 아마존에서 SLA는 분포의 99.9번째 백분위수(99.9th percentile)로 표현되고 측정된다. ... 더 나아가, 우리의 경험상 가장 긴 구매 이력과 가장 많은 데이터를 가진 고객들이 바로 이 99.9퍼센타일 구간에 속한다. 이들은 종종 아마존의 가장 가치 있는(VIP) 고객들이며, 시스템은 이들에게 훌륭한 경험을 보장하도록 최적화되어야 한다.

- Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, 2.2 Service Level Agreements (SLA)

저는 이 대목에서 다이나모 시스템의 설계가 단순한 '서버 튜닝'을 넘어섰다고 생각합니다. 인프라 엔지니어링이 비즈니스가 가장 지켜야 할 타겟이 누구인지 정확히 꿰뚫어 보고, 그에 맞춰 분산 시스템의 아키텍처를 조준한 셈입니다.

물론 현실적인 타협도 있었습니다.

논문은 99.99%나 99.999%처럼 완벽에 더 가까운 숫자를 목표로 삼지 않은 이유도 솔직하게 털어놓습니다. 지연 시간을 잡기 위해 99.9%에서 0.09%를 더 끌어올리는 순간, 스토리지나 네트워크 인프라에 쏟아부어야 하는 서버 비용이 눈덩이처럼 불어나기 때문입니다. 기술적 이상향과 비즈니스의 비용 편익 사이에서 가장 합리적인 선을 그은 것입니다.

그렇다면, 이토록 철저하게 비즈니스를 관통하여 설계된 새로운 인프라의 가장 중요한 절대 원칙은 무엇이었을까요?

'언제나 쓸 수 있다(Always Writeable)'입니다.

어떤 장애 상황에서도 시스템은 사용자의 쓰기 요청만큼은 무조건 받아내야 한다는 원칙입니다. 아마존에게 쓰기란 무엇일까요? 바로 고객이 장바구니에 물건을 담는 행위이자 곧바로 매출이 일어나는 순간입니다.

만약 서버 절반이 고장 나거나 데이터센터 간 랜선이 끊어지는 대형 장애가 터졌다고 가정해 봅시다. 이때 일시적으로 누군가의 장바구니 목록이 안 보일 수는 있습니다(읽기 실패). 하지만, 고객이 지금 당장 사겠다고 '장바구니 담기' 버튼을 누른 데이터마저 시스템이 뱉어내서는 안 됩니다.

삭제했던 물건이 나중에 결제창에 다시 나타나는 기이한 부작용이 생길지언정, 돈이 되는 '쓰기' 흔적만큼은 절대 땅에 떨어뜨리지 않겠다는 독한 결단. 이것이 아마존이 완벽한 데이터 일관성을 자랑하던 기존 관계형 데이터베이스를 버리고 다이나모라는 새로운 괴물을 만들어낸 진짜 이유였습니다.

2. 첫 번째 지불, 일관성

가용성을 위한 지불

그런데 이 '언제나 쓸 수 있다'는 공짜일까요? 그렇지 않겠죠. 세상의 모든 법칙처럼, 반드시 무언가를 얻게 되면 잃는 게 생깁니다. 그렇다면 다이나모가 쓰기 가용성을 얻기 위해 지불한 것은 무엇일까요?

일관성입니다.

아마존은 장바구니 쓰기 요청을 어떤 상황에서도 튕겨내지 않고 받아내기 위해, 모든 서버의 데이터 상태가 즉시 똑같이 유지되는 것을 포기했습니다.

저는 다이나모가 일관성을 내어준 것이 비즈니스 생존을 위해 불가피한 결단이었다는 생각이 듭니다. 분산 환경에서 완벽한 데이터 동기화를 기다리느라 장바구니 버튼이 먹통이 되는 것은, 곧장 고객의 이탈과 천문학적인 매출 하락으로 이어지니까요.

이 기막힌 교환을 정확히 이해하려면 분산 시스템의 뼈대가 되는 CAP 정리를 짚고 넘어가야 합니다.

CAP 정리가 진짜로 말하는 것

CAP 정리란, 일관성(Consistency), 가용성(Availability), 파티션 감내(Partition Tolerance)의 앞 글자를 딴, 분산 시스템은 이 세 가지를 동시에 완벽하게 가질 수 없다는 유명한 법칙입니다.

https://en.wikipedia.org/wiki/CAP_theorem

수백 대의 서버가 거미줄처럼 얽힌 데이터센터에서 네트워크 랜선이 끊어지거나 장비가 죽는 파티션 단절(P)은 개발자가 피할 수 없는 '상수'입니다.

결국 두 서버 간의 통신이 끊어지는 P 상황이 발생했을 때, 시스템은 잔인한 양자택일을 해야 합니다. 두 서버의 데이터가 어긋나는 것을 막기 위해 에러를 뱉으며 시스템을 멈춰 세울 것인가(C 선택), 아니면 양쪽의 데이터가 조금 틀어지더라도 일단 사용자에게 응답을 줄 것인가(A 선택).

다이나모는 고민 없이 후자(A)를 택하며 데이터가 찢어지는 상황을 받아들였습니다.

그런데 엄밀한 의미에서, CAP 정리에서 말하는 일관성(C)이 무엇을 의미하는지 좀 더 생각해볼 필요가 있습니다.

에릭 브루어(Eric Brewer)가 제안하고 2002년 길버트와 린치(Gilbert & Lynch)가 수학적으로 증명한 CAP 정리에서, C는 원자적 일관성(Atomic Consistency), 즉 선형화 가능성(Linearizable Consistency)을 의미합니다. 일상적인 대화에서 쓰는 "데이터의 값이 정확하다"는 뜻과는 조금 다른 의미 같습니다.

왜냐하면, 쓰기 작업이 완료되는 즉시 모든 후속 읽기 작업이 그 최신 데이터를 보장받아야 한다는, 마치 시스템 전체에 데이터 복제본이 단 하나만 존재하는 것처럼 동작하는 엄격한 상태를 뜻하기 때문이죠.

그렇다면 가용성(A)은 앞선 1장에서 말한 300ms 같은 빠른 응답 속도를 의미할까요?

생존성입니다.

우리는 흔히 가용성을 서비스가 얼마나 빠르고 안정적으로 응답하는지 측정하는 지표인 SLA로 이해합니다. 하지만 길버트와 린치는 2012년 회고 논문에서 가용성을 "장애가 나지 않은 노드에 요청을 보내면, 언젠가는 반드시 응답을 받는다"는 생존성(Liveness property)으로 정의했습니다.

우리가 앞선 1절에서 확인한 다이나모의 '99.9 백분위 300ms' SLA 목표와 CAP 증명이 말하는 가용성은, 따라서 전혀 다른 층위의 개념입니다.

다이나모는 이론적 수준의 가용성(언젠가는 응답한다)을 충족하는 것을 넘어, 비즈니스를 위해 엄격하게 제한된 시간 안에 반드시 빠르고 확실하게 응답해야 하는 극한의 시스템이었던 셈입니다.

15년 뒤의 자백

다시 논문으로 돌아와 보겠습니다.

쓰기를 잃어버리지 않기 위해 일관성을 포기하고 찢어진 장바구니 데이터를 감수했던 이 아키텍처는 끝까지 살아남았을까요?

15년 뒤에 발표된 다이나모DB 논문은 원전의 일관성 모델을 어떻게 평가했을까요?

사실상 버렸다고 고백합니다.

"We concluded that a better solution would combine the best parts of the original Dynamo design (incremental scalability and predictable high performance) with the best parts of SimpleDB (ease of administration of a cloud service, consistency, and a table-based data model that is richer than a pure key-value store)."

우리는 더 나은 해법이 원전 다이나모 설계의 가장 좋은 부분인 점진적 확장성과 예측 가능한 높은 성능을, 심플DB의 가장 좋은 부분인 클라우드 서비스로서의 관리 용이성과 일관성, 그리고 순수 키-값 저장소보다 풍부한 테이블 기반 데이터 모델과 결합하는 것이라고 결론지었다.

- Mostafa Elhemali et al., Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service, USENIX ATC 2022, 2 History

2022년 다이나모DB 논문의 2절에 등장하는 이 문장은 무척 흥미롭습니다. 아마존은 원전 다이나모에서는 무한한 트래픽을 감당하는 뼈대만 남기고, 가장 치열하게 고민했던 일관성 모델은 아마존의 또 다른 서비스였던 심플DB 쪽에서 통째로 가져왔다고 공식적으로 선언한 것입니다.

논문이 이 문장에서 일관성 모델의 출처를 심플DB라고 못 박은 것은, 원전 다이나모가 택했던 일관성 모델을 그대로 가져오지 않았다는 뜻입니다. 현재의 다이나모DB는 리더 노드를 도입하여 강한 일관성 읽기와 최종적 일관성 읽기를 개발자가 입맛에 맞게 선택할 수 있도록 모두 제공합니다.

2007년에는 오직 쓰기를 위해 일관성을 온전히 내주었지만, 15년의 세월이 흐르며 거대한 클라우드 인프라가 일관성과 가용성 두 가지를 모두 정교하게 통제할 수 있는 형태로 진화한 것입니다.

그런데 잠깐만요...! 여기서 근본적인 의문이 하나 생기죠.

CAP 정리에 따르면 네트워크 단절(P) 시 일관성(C)과 가용성(A)을 동시에 완벽하게 만족하는 것은 수학적으로 불가능합니다. 그런데 어떻게 2022년의 다이나모DB는 이 두 가지를 모두 제공하게 된 것일까요? 아마존이 분산 시스템의 절대 법칙을 깨부수기라도 한 걸까요?

아닙니다. 양자택일의 문제를 API 레벨의 '선택권'으로 풀고, 이론적으로 발생하는 가용성의 공백을 압도적인 인프라 복구 속도로 메워버렸습니다.

현대의 다이나모DB는 팩소스(Paxos) 알고리즘을 통해 단일 리더를 세워 강한 일관성을 보장합니다. 만약 네트워크가 끊어져 리더가 응답하지 못하면, 시스템은 찢어진 데이터를 반환하는 대신 새 리더를 뽑을 때까지 강한 일관성 읽기 및 쓰기 요청을 거절합니다. 이는 명백히 가용성(A)을 희생하는 CP 시스템의 동작 방식입니다.

https://www.scylladb.com/glossary/paxos-consensus-algorithm/

다만 그 공백의 길이를 극단적으로 줄여놓았습니다. 뒤에서 자세히 보겠지만, 복제본 하나가 죽었을 때 팩소스 정족수를 되살리는 데 걸리는 시간이 몇 초 수준입니다. 이론적으로는 가용성을 내려놓았지만, 비즈니스 체감상으로는 마치 끊김 없이 굴러가는 것처럼 보이게 만든 것입니다. 동시에, 당장 최신 데이터가 필요 없는 조회 요청에는 여전히 과거 다이나모처럼 최종적 일관성 읽기를 제공합니다.

"어떻게 그런 게 가능하지?" 이런 의문이 여전히 듭니다.

아마존은 개발자에게 상황에 맞는 일관성 선택권을 API로 쥐여주고, 백엔드의 장애 복구 속도를 극한으로 끌어올리는 방식으로 이 문제를 현실에서 풀어냈습니다.

현대 다이나모DB의 이 완성된 아키텍처를 온전히 이해하려면, 역설적이게도 그 뼈대가 된 2007년의 원형으로 돌아가야 합니다. 그래서 우리는 다시 2007년으로 돌아가 보려 합니다.

지금처럼 세련된 API 통제권도, 강력한 리더 노드도 없던 시절이었습니다. 오직 쓰기 가용성을 위해 일관성을 온전히 내어준 상황에서, 아마존 엔지니어들은 분산 시스템 안을 떠도는 이 '찢어진 데이터'가 유실되지 않도록 끝까지 추적해 내야만 했습니다. 그 아찔한 복잡성을 통제하기 위해 이들은 학계의 이론들을 현실로 끌고 와 4개의 핵심 장치를 만들어냅니다.

이제 그 첫 번째 장치, 데이터를 안정적으로 분산하고 가두는 거대한 원형 울타리 '안정 해시(Consistent Hashing)'를 만나볼 차례입니다.

3. 가두는 장치 하나, 안정 해시

웹 캐시에서 빌려온 무기

다이나모는 폭주하는 장바구니 트래픽을 감당하기 위해 수백 대의 서버를 띄웠습니다. 그렇다면 쉴 새 없이 쏟아지는 고객들의 장바구니 데이터는 이 수백 대의 서버 중 도대체 어디로 보내야 할까요?

가장 먼저 떠오르는 직관적인 해법은 해시 알고리즘을 이용해 데이터를 여러 서버에 골고루 쪼개어 담는 것입니다. 하지만 다이나모는 평범한 해시 알고리즘 대신 '안정 해시'라는 특수한 기술을 선택했습니다.

이 기술은 애초에 분산 데이터베이스를 위해 탄생한 것일까요?

아닙니다. 안정 해시가 처음 등장한 1997년 카거(Karger)의 원전 논문을 보면, 이 기술은 원래 월드 와이드 웹(WWW) 환경에서 특정 웹 서버에만 트래픽이 몰리는 캐시 핫스팟 부하를 완화할 목적으로 발명되었습니다.

"Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web"

안정 해시와 랜덤 트리: 월드 와이드 웹의 핫스팟을 완화하기 위한 분산 캐싱 프로토콜

- David Karger et al., STOC 1997

1997년 MIT의 데이비드 카거(David Karger) 연구팀이 발표한 원전 논문의 제목입니다. 초록의 첫 문장도 같은 곳을 가리킵니다.

"We describe a family of caching protocols for distributed networks that can be used to decrease or eliminate the occurrence of hot spots in the network."

우리는 네트워크에서 발생하는 핫스팟 현상을 줄이거나 제거하는 데 사용할 수 있는 분산 네트워크용 캐싱 프로토콜들을 설명한다.

- David Karger et al., Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, STOC 1997, Abstract

학계에 '안정 해시'라는 개념이 처음 등장한 이 순간, 연구의 타겟은 데이터베이스의 파티셔닝이 아니었습니다. 특정 유명 웹사이트(핫스팟)에 전 세계의 브라우저 트래픽이 일시에 몰려 서버가 마비되는 것을 막기 위해, 트래픽을 여러 대의 프록시 캐시 서버들에 안정적으로 흩뿌려주는 것이 본래의 임무였습니다.

아마존 엔지니어들은 웹 트래픽을 분산시키던 이 오래된 무기가, 자신들의 찢어진 데이터베이스 환경을 구원해 줄 완벽한 도구임을 꿰뚫어 본 것입니다.

해시 공간을 둥글게 말아 쥐다

그렇다면 기존의 단순한 해시 방식은 왜 다이나모에서 쓸 수 없었을까요?

나눗셈의 '분모'가 바뀌면 주소 체계가 통째로 무너지기 때문입니다.

구체적인 예를 들어보겠습니다. 서버가 3대(0번, 1번, 2번) 있고, '고객 10번'의 데이터가 들어왔습니다. 10을 전체 서버 대수인 3으로 나눈 나머지는 1이므로, 이 데이터는 1번 서버에 저장됩니다.

그런데 연말 쇼핑 시즌이 되어 트래픽이 몰리자 아마존이 서버 한 대를 긴급하게 추가했다고 가정해 보겠습니다. 서버는 총 4대가 되었습니다. 이제 다시 '고객 10번'의 데이터를 찾아야 합니다. 10을 4로 나누면 나머지는 2가 됩니다. 고객의 데이터는 가만히 있는데, 서버 대수(분모)가 바뀌었다는 이유만으로 데이터가 저장된 주소가 1번에서 2번으로 엉뚱하게 바뀌어버린 것입니다.

서버가 1대 추가되거나 죽었을 뿐인데, 기존 데이터들의 위치가 도미노처럼 어긋납니다. 서버를 늘릴수록 전체 데이터의 90%, 99%가 아무 의미 없이 다른 서버로 이사를 가야 하는 대재앙이 벌어집니다.

카거의 논문은 이 참사를 막기 위해 아주 우아한 해법을 제시합니다. 서버와 데이터를 모두 $[0, 1]$ 구간 위의 점으로 흩뿌린 뒤, 각 데이터를 자기와 가장 가까운 점을 가진 서버에 맡기는 방식입니다. 그리고 서버 하나를 이 구간 위의 점 하나로 두지 않고 여러 개의 점으로 복제해 흩뿌립니다. 뒤에서 다룰 가상 노드의 수학적 조상이 여기 있습니다.

흥미롭게도 우리가 흔히 아는 '해시 링'이라는 표현은 카거의 논문에는 나오지 않습니다. 원(circle)이나 시계 방향(clockwise)이라는 단어가 논문 전문에 단 한 번도 등장하지 않습니다. 선분을 둥글게 말아 링으로 그리는 익숙한 그림은 2007년 다이나모 논문이 카거의 이론을 자기 방식으로 옮기며 제시한 것입니다.

"In consistent hashing, the output range of a hash function is treated as a fixed circular space or 'ring' (i.e. the largest hash value wraps around to the smallest hash value). ... Each data item identified by a key is assigned to a node by hashing the data item's key to yield its position on the ring, and then walking the ring clockwise to find the first node with a position larger than the item's position."

안정 해시에서는 해시 함수의 출력 범위를 고정된 원형 공간, 즉 '링'으로 다룬다. 가장 큰 해시값이 한 바퀴 돌아 가장 작은 해시값으로 이어진다는 뜻이다. ... 키로 식별되는 각 데이터 항목은 그 키를 해시하여 링 위의 위치를 얻고, 링을 시계 방향으로 걸어가 자기보다 큰 위치를 가진 첫 번째 노드를 만나 그곳에 할당된다.

- Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, 4.2 Partitioning Algorithm

0부터 시작해 특정 최댓값에서 끝나는 선형적인 해시 값의 양 끝을 이어 붙여, 무한히 순환하는 거대한 원형 트랙을 만들자는 아이디어입니다.

방식은 이렇습니다. 데이터의 해시값뿐만 아니라, 서버들의 IP 주소(식별자)도 똑같은 해시 함수에 넣어 이 거대한 링 위에 함께 흩뿌려 놓습니다. 이제 특정 장바구니 데이터가 어느 서버에 저장될지 찾으려면, 그 데이터의 위치에서 시계 방향으로 링을 따라 걷다가 '가장 먼저 만나는 서버'에 쏙 들어가면 됩니다.

구체적인 숫자로 그려보겠습니다. 해시 링의 둘레가 0부터 99까지라고 해봅시다. 해시 함수를 거친 결과 서버 A는 10번, 서버 B는 40번, 서버 C는 70번 위치에 배정되었습니다.

이때 해시값이 25인 '장바구니' 데이터가 들어오면 어떻게 될까요? 25에서 출발해 시계 방향으로 링을 돌면 가장 먼저 만나는 서버는 40번 위치의 서버 B입니다. 따라서 이 데이터는 서버 B에 저장됩니다. 만약 해시값이 80인 데이터가 들어오면 70번을 지나 99의 끝을 넘어 원을 한 바퀴 돈 뒤, 다시 0번을 거쳐 10번 위치에 있는 서버 A에 저장됩니다.

이렇게 하면 서버가 새로 하나 추가되거나 빠지더라도 주소 체계가 통째로 무너지지 않습니다.

예를 들어, 이런 시나리오들을 생각해봅시다. 먼저 '서버가 추가'되는 연말 쇼핑 시즌의 시나리오입니다.

트래픽이 폭주하여 아마존 엔지니어들이 25번 위치에 새로운 '서버 D'를 긴급하게 투입했다고 가정해 봅시다. 원래 11번부터 40번 사이의 데이터는 모두 40번 위치의 서버 B가 온전히 감당하고 있었습니다. 그런데 25번에 서버 D가 중간에 끼어들면서 구역이 나뉩니다. 이제 11번부터 25번까지의 데이터는 링을 돌다가 가장 먼저 만나는 서버 D에 안착합니다. 26번부터 40번까지의 데이터는 여전히 서버 B에 저장되죠.

결과적으로 서버 B가 들고 있던 데이터의 앞부분(11~25)만 짐을 싸서 새로운 서버 D로 건네주면 상황이 종료됩니다. 링 저편에 멀리 떨어져 있는 서버 A(10번)나 서버 C(70번) 안의 데이터들은 새 서버가 들어왔는지조차 모른 채 평화롭게 자기 자리를 지킵니다.

반대로 '서버가 죽는' 장애 시나리오는 어떨까요?

새벽 3시에 40번 위치의 서버 B가 전원 공급 장치 이상으로 링에서 돌연 사라졌다고 가정해 보겠습니다. 기존에는 11번부터 40번 사이의 장바구니 데이터가 모두 서버 B로 향했지만, 이제 B가 없으니 이 데이터들은 갈 곳을 잃고 링을 따라 계속 걸어갑니다. 그러다 다음 서버인 C(70번)를 만나 그곳으로 고스란히 흡수됩니다.

서버 B가 감당하던 트래픽만 이웃인 서버 C가 대신 떠안을 뿐, 이번에도 10번 위치의 서버 A는 아무런 타격을 받지 않고 하던 일을 계속합니다.

전통적인 모듈러 연산 방식에서 서버 대수가 하나 바뀌었다는 이유만으로 전체 데이터의 90%가 무의미하게 이삿짐을 싸야 했던 대참사가 완벽하게 해결된 것입니다. 기계가 추가되거나 고장 날 때 발생하는 데이터의 대이동을 수학적 최소치로 억제하는 이 원리를 논문에서는 '매끄러움(Smoothness)'이라고 부릅니다.

"First, there is a 'smoothness' property. When a machine is added to or removed from the set of caches, the expected fraction of objects that must be moved to a new cache is the minimum needed to maintain a balanced load across the caches."

첫째, '매끄러움' 성질이 있다. 캐시 집합에 기계가 추가되거나 제거될 때, 새 캐시로 옮겨야 하는 객체의 기대 비율은 캐시들 사이의 부하 균형을 유지하는 데 필요한 최소치이다.

- David Karger et al., Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, STOC 1997, 4 Consistent Hashing

앞선 예시에서 40번 위치의 서버 B가 갑자기 고장 나서 링에서 사라졌다고 가정해 봅시다. 기존에는 11번부터 40번 사이의 데이터가 모두 서버 B로 향했지만, 이제 B가 없으니 이 데이터들은 링을 따라 계속 걸어가 다음 서버인 C(70번)로 흡수됩니다. 오직 B가 가지고 있던 데이터만 C로 옮겨갈 뿐, 서버 A나 C가 원래 가지고 있던 데이터는 단 하나도 자리를 이동할 필요가 없습니다. 분모가 바뀌었다고 전체 주소가 어긋나던 참사가 완벽하게 해결된 것입니다.

어긋난 시야를 견디는 마법

데이터 이동을 최소화하는 것이 이 알고리즘이 가진 마법의 전부일까요?

카거의 원전 논문을 깊이 파고들어 보면, 다이나모가 이 기술을 첫 번째 무기로 쥘 수밖에 없었던 진짜 이유가 숨어있습니다.

바로 '어긋난 시야(Inconsistent views)'를 견디는 능력입니다.

"Consistent hashing solves this problem of different 'views.' We define a view to be the set of caches of which a particular client is aware. We assume that while views can be inconsistent, they are substantial: each machine is aware of a constant fraction of the currently operating caches."

안정 해시는 서로 다른 '시야' 문제를 해결한다. 우리는 시야를 특정 클라이언트가 알고 있는 캐시들의 집합으로 정의한다. 시야는 서로 어긋날 수 있지만 충분히 크다고 가정한다. 각 기계는 현재 작동 중인 캐시 중 일정 비율은 알고 있다는 뜻이다.

- David Karger et al., Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, STOC 1997, 4 Consistent Hashing

앞선 2장에서 우리는 다이나모가 네트워크가 끊어지는 파티션 단절 상황에서도 '언제나 쓰기'를 포기하지 않았다고 배웠습니다. 이런 가혹한 장애 상황에서는 노드 A가 보기엔 노드 C가 죽은 것 같은데, 노드 B가 보기엔 노드 C가 버젓이 살아있는 혼돈이 필연적으로 발생합니다. 분산된 서버들이 전체 시스템의 상태를 서로 다르게 파악하는 '어긋난 시야' 상태에 빠지는 것입니다.

전통적인 나눗셈 방식에서는 전체 서버 대수에 대한 합의(분모)가 단 1대라도 엇갈리는 순간 시스템 전체의 주소 체계가 박살 납니다. 하지만 안정 해시는 다릅니다. 원전 논문은 각 노드가 현재 작동 중인 전체 서버의 100%를 정확히 알지 못하고 그중 일부만 알고 있더라도, 확산과 부하의 한계치를 수학적으로 보장하며 데이터가 엉뚱한 곳으로 크게 쏠리거나 증발하지 않게 만들어 줍니다.

완벽한 시야가 확보되지 않은 아수라장 속에서도, 고객이 누른 장바구니 데이터가 허공으로 증발하지 않게 특정 서버 주변으로 묶어두는 강력한 둥근 울타리. 이것이 안정 해시가 다이나모의 멱살을 잡고 끌고 간 첫 번째 힘이었습니다.

가상 노드와 세 가지 진화 전략

다시 다이나모 논문으로 돌아와 보겠습니다.

다이나모는 이 해시 링 위에 데이터를 어떻게 복제하고 배치했을까요?

세 번에 걸쳐 전략을 뜯어고쳤습니다.

다이나모는 데이터 유실을 막기 위해 링 위에 데이터를 올린 뒤, 시계 방향으로 돌면서 만나는 '서로 다른 물리 노드' 3곳에 데이터를 복사합니다. 이것이 논문에 등장하는 노드 복제본 개수 $N=3$이라는 일반 설정입니다. 그리고 여기서 중요한 마법인 '가상 노드' 개념을 도입합니다. 하나의 물리 서버를 링 위의 수많은 조각으로 쪼개어 배치하는 기술입니다.

논문은 가상 노드의 이점을 세 가지로 정리합니다. 노드 하나가 장애로 빠지면 그 부하가 고르게 흩어지고, 노드가 새로 들어오면 다른 노드들로부터 부하를 고르게 뺏어오며, 물리 인프라의 하드웨어 성능 격차를 흡수할 수 있다는 것입니다.

구체적인 예를 들어보겠습니다. 물리 서버 1대를 링 위에 단 하나의 점으로만 찍어두면 어떤 일이 벌어질까요?

링 위에서 나란히 서 있던 서버 A가 돌연 죽었다고 가정해 봅시다. 그러면 서버 A가 감당하던 막대한 트래픽과 데이터는 링을 따라 걸어가다 고스란히 그 다음 순서인 서버 B에게 폭탄처럼 쏟아집니다. 서버 B는 순식간에 트래픽을 견디지 못하고 쓰러지며 연쇄 장애를 일으킬 것입니다.

하지만 가상 노드를 쓰면 이야기가 완전히 달라집니다. 물리 서버 A를 수백 개의 가상 노드(A1, A2, A3...)로 쪼개어 링 전체에 무작위로 흩뿌려 놓는 것입니다. 서버 B, C, D 역시 수백 개로 쪼개어 링 위에 마구 섞어둡니다. 이 상태에서 물리 서버 A가 죽으면 어떻게 될까요?

A1이 처리하던 짐은 바로 옆의 B1으로, A2의 짐은 C2로, A3의 짐은 D3로 흘러갑니다. 죽은 서버 A의 거대한 트래픽을 링 위에 살아남은 전체 서버들이 아주 조금씩 사이좋게 나눠 짊어지게 됩니다. 연쇄 장애를 막아내는 완벽한 충격 분산입니다. 서버가 새로 투입될 때도 마찬가지로 기존 서버들의 짐을 조금씩 떼어오기 때문에 시스템에 큰 충격이 없습니다.

세 번째 이점인 하드웨어 성능 격차 극복도 매우 직관적입니다.

데이터센터를 수년간 운영하다 보면 최신 고성능 서버와 오래된 구형 서버가 섞일 수밖에 없습니다. 이때 최신 서버에는 가상 노드를 200개 부여하여 링 위에 200개의 과녁을 만들고, 성능이 절반인 구형 서버에는 가상 노드를 100개만 쥐여주는 식입니다. 물리 인프라의 스펙이 제각각이어도 소프트웨어 설정 하나로 트래픽의 분배량을 정교하게 조율할 수 있게 된 것입니다.

그런데 논문은 이 훌륭한 가상 노드의 배치 방식을 전략 1, 전략 2, 전략 3으로 나누어 치열하게 비교하며 약점을 파고듭니다.

초기 모델인 전략 1은 물리 노드당 무작위 위치에 $T$개의 토큰(가상 노드)을 할당하는 방식이었습니다. 하지만 이 방식은 노드가 추가되거나 삭제될 때 엄청난 운영 부하를 일으켰습니다. 토큰의 위치가 완벽한 무작위이다 보니 각 파티션(노드와 노드 사이의 공간)의 크기가 제각각이었고, 노드가 죽어 데이터를 이웃에게 넘겨야 할 때마다 머클 트리를 뒤져가며 어떤 데이터를 주고받아야 하는지 계산하는 과정이 너무 복잡했습니다.

아마존은 이 복잡성을 덜어내기 위해 '파티션의 크기를 고정하는' 방향으로 진화합니다.

전략 2는 $T$개의 무작위 토큰을 쓰되 전체 해시 공간을 균등한 크기의 파티션으로 쪼개버렸고, 최종 형태인 전략 3은 노드당 $Q/S$개의 토큰을 배치하면서 파티션 크기까지 완벽하게 균등하게 맞추어 버립니다.

저는 논문이 전략 3으로 진화해 가는 과정에서 아마존 엔지니어들의 짙은 고뇌가 엿보입니다.

순수한 수학적 해시 링 이론(어긋난 시야와 매끄러움을 보장하는 무작위성)만으로는 실제 데이터센터의 운영 복잡도를 도저히 감당할 수 없었던 것입니다. 이론이 주는 무작위성을 어느 정도 통제하고 데이터 블록의 크기를 규격화함으로써, 서버 장애가 났을 때 데이터를 통째로 빠르게 복사해서 넘길 수 있는 실용적인 타협점을 찾아낸 셈입니다.

여기까지 우리는 쏟아지는 장바구니 데이터를 '어디에' 둘 것인가 하는 공간의 문제를 해결했습니다. 해시 링과 가상 노드 덕분에 데이터는 안전하게 3대의 서로 다른 서버(N=3)로 흩어졌습니다.

하지만 여기서 완전히 새로운 고민이 시작됩니다.

네트워크가 불안정한 분산 환경에서 3대의 서버에 '동시에' 똑같은 데이터를 써넣는 것은 불가능에 가깝습니다. 만약 3대 모두가 데이터를 온전히 기록할 때까지 고객을 기다리게 한다면, 쇼핑몰은 필연적으로 느려지고 '언제나 쓰기 가능해야 한다'는 다이나모의 절대 원칙이 무너집니다.

그렇다고 속도를 위해 단 1대에만 대충 기록하고 끝내자니, 하필 그 서버가 죽었을 때 장바구니 데이터가 통째로 날아갈 위험이 너무 큽니다.

안전하게 데이터를 지키면서도 번개처럼 빠르게 응답하려면, 아마존은 도대체 '몇 대'의 서버에 데이터를 쓰고 읽어야 했을까요?

다이나모는 이 딜레마를 두 번째 핵심 장치로 돌파합니다.

4. 장치 둘, 정족수

과반수라는 최소한의 안전장치

데이터를 몇 대의 서버에 쓰고, 몇 대에서 읽어와야 가장 안전하고 빠를까요?

정답은 '과반수'입니다.

2007년 다이나모 논문은 시스템의 쓰기와 읽기를 통제하는 기본 설정값으로 (N, R, W) = (3, 2, 2)를 사용한다고 명시합니다. 데이터를 3대의 노드에 복제(N=3)하고, 고객의 쓰기 요청이 들어왔을 때 최소 2대(W=2)가 성공했다고 응답하면 고객에게 "장바구니 담기가 완료되었습니다"라고 처리해 주는 것입니다. 나중에 데이터를 읽을 때도 2대(R=2)의 노드를 확인하여 최신 버전을 찾습니다.

이 수치들은 대충 감으로 때려잡은 경험칙이 아니라는 점에서 인사이트가 있다고 생각합니다. 분산 시스템에서 데이터의 일관성을 보장하는 '정족수(Quorum)'의 기본 수학 공식을 철저히 따른 결과입니다.

공식은 단순합니다. 읽는 노드 수(R)와 쓰는 노드 수(W)의 합이 전체 복제본 수(N)보다 커야 한다는 조건, 즉 W + R > N입니다.

다이나모의 기본 설정값에 대입해 보면 2 + 2 > 3이 되므로 이 조건을 만족합니다. 이 공식을 만족해야만 하는 아주 직관적인 이유가 있습니다. 우리가 데이터를 읽어오기 위해 찔러본 무리(R) 중에, 가장 최근에 데이터를 쓴 무리(W)가 교집합처럼 '최소한 한 대 이상' 무조건 포함되기 때문입니다.

다이나모는 이 정족수 공식을 활용해 쓰기 속도(가용성)와 읽기 정확성(일관성) 사이의 아슬아슬한 줄타기를 조율해 냈습니다.

"The common (N,R,W) configuration used by several instances of Dynamo is (3,2,2). These values are chosen to meet the necessary levels of performance, durability, consistency, and availability SLAs."

여러 다이나모 인스턴스에서 공통적으로 사용하는 (N, R, W) 설정은 (3, 2, 2)이다. 이 값들은 성능, 내구성, 일관성, 가용성 SLA에 요구되는 수준을 충족하기 위해 선택되었다.

- Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, 6 Experiences & Lessons Learned

논문의 6장 '경험과 교훈' 파트에 등장하는 이 문장은, 정족수 설정이 수학 이론 이상으로 현실의 비즈니스를 지켜내기 위한 치열한 계산의 결과임을 보여줍니다.

만약 모든 데이터가 3대의 서버에 완벽하게 쓰이기를 기다리는 W=3을 선택했다면 어땠을까요? 3대 중 단 1대만 네트워크 지연을 겪어도 전체 쓰기 속도가 느려집니다. 심지어 1대가 고장 나면 쓰기 자체가 실패해버리죠. '언제나 장바구니에 물건을 담을 수 있어야 한다'는 다이나모의 제1원칙이 무너지는 것입니다.

반대로 쓰기 속도를 극한으로 끌어올리기 위해 W=1을 선택하면 어떻게 될까요? 쓰기는 번개처럼 빠르겠지만, 해당 데이터를 받아낸 유일한 서버가 데이터를 다른 곳으로 복제하기도 전에 죽어버리면 고객의 장바구니 데이터는 영원히 증발해 버립니다. 내구성을 잃는 것입니다.

결국 아마존 엔지니어들이 도달한 결론은 이렇습니다. 전체 3대 중 서버 1대가 완전히 죽거나 네트워크가 단절되는 최악의 상황이 오더라도, 시스템은 멈추지 않고 쓰기(W=2)와 읽기(R=2) 요청을 처리해 냅니다. 동시에 과반수의 교집합을 이용해 항상 최신 데이터를 찾아냅니다.

서버의 물리적 장애를 일상으로 인정하면서도, 99.9%의 고객에게 끊김 없는 쇼핑 경험(성능과 가용성)을 제공하고 데이터 유실(내구성)을 막아내는 최적의 타협점이 바로 (3, 2, 2) 설정이었던 것입니다.

아무나 쓰던 시대의 종말

15년이라는 긴 시간이 흘러 발표된 2022년 다이나모DB 논문으로 시선을 옮겨보겠습니다.

과거 다이나모의 상징과도 같았던 이 '자유로운' 정족수 쓰기 방식은 현대에 와서 어떻게 변했을까요?

'리더 독점 체제'로 구조를 완전히 탈바꿈했습니다.

2022년 논문에 따르면, 현대 다이나모DB의 파티션 복제본들은 하나의 복제 그룹을 이루고 '멀티 팩소스(Multi-Paxos)'라는 합의 알고리즘을 통해 리더를 선출합니다. 2007년의 원전 다이나모에서는 3대의 노드 중 누구든 쓰기 요청을 받아도 무방했습니다. 하지만 현대의 아키텍처에서는 오직 선출된 단 한 명의 리더만이 쓰기 요청과 강한 일관성 읽기를 전담합니다.

이제 쓰기 요청이 들어오면 리더가 이를 통제합니다. 리더는 나머지 피어 노드들에게 "이 데이터를 쓰라"는 작업 지시서, 즉 쓰기 로그(Write-ahead log)를 전파합니다. 그리고 과반수의 피어가 자기 로컬의 쓰기 로그에 이를 안전하게 기록한 그 순간, 비로소 애플리케이션에 쓰기 성공 응답을 반환합니다. 단, 최신 데이터가 아니어도 괜찮은 '최종적 일관성 읽기'만큼은 굳이 리더를 거치지 않고 아무 복제본에서나 읽어갈 수 있도록 유연한 뒷문을 열어두었습니다.

악명 높은 알고리즘이 가져온 복선

아마존은 왜 노드들의 자율성을 보장하던 방식을 버리고 굳이 중앙 통제적인 리더를 세웠을까요?

데이터의 버전이 여러 갈래로 찢어지는 현상을 원천적으로 차단하기 위해서입니다.

아무 노드나 동시다발적으로 쓰기 요청을 받다 보면, 네트워크가 단절되었을 때 각 노드에 저장된 장바구니 데이터의 처리 순서가 뒤죽박죽 엉켜버립니다. 하지만 단 한 명의 리더가 쓰기를 독점하여 줄을 세우고 '순서'를 명확히 통제하면, 애초에 데이터 버전이 엇갈리고 충돌할 여지가 크게 줄어듭니다.

분산 시스템을 깊이 파고들다 보면 팩소스 알고리즘의 악명 높은 난이도에 좌절하곤 합니다. 오죽하면 2014년에 Raft 합의 알고리즘을 제안한 논문조차 "팩소스는 예외적으로 이해하기 어렵다. 전체 설명은 악명 높을 정도로 불투명하다"라고 꼬집었을 정도입니다. 아마존은 그 난해한 팩소스의 본질을 집요하게 구현해 내어, 거대한 클라우드 데이터베이스의 복제 그룹을 한 치의 오차 없이 통제하는 강인한 심장으로 이식해 냈습니다.

이제 다시 단일 리더가 존재하지 않던 2007년의 거친 환경으로 돌아와 보겠습니다.

앞서 우리는 다이나모가 (3, 2, 2) 정족수 설정을 통해 서버 1대가 죽어도 남은 2대가 쓰기를 받아주면 시스템이 정상적으로 굴러간다고 배웠습니다.

그런데 현실의 데이터센터에서는 종종 더 가혹한 일이 벌어집니다.

해시 링 위에서 데이터를 받아야 할 원래 담당 서버 3대 중, 하필 2대가 일시적인 네트워크 단절이나 재부팅으로 동시에 연락이 두절된다면 어떻게 될까요? 과반수인 2대의 응답을 얻어내지 못했으니, 고객에게 "지금은 장바구니를 사용할 수 없습니다"라고 에러를 뱉어야 할까요?

'언제나 장바구니에 담겨야 한다'는 원칙을 지상 과제로 삼았던 다이나모는 이 순간에도 쓰기를 포기하지 않았습니다. 진짜 담당자가 자리를 비웠다면, 링 위의 살아있는 다른 누군가가 억지로라도 짐을 대신 받아두도록 설계했습니다.

이 집요한 쓰기 가용성을 완성한 세 번째 장치를 만날 차례입니다.

5. 장치 셋, 힌티드 핸드오프

일시적 장애를 넘기는 방법

데이터를 받아야 할 노드가 일시적으로 죽어 있으면 쏟아지는 쓰기 요청은 어떻게 될까요?

원래 담당자가 아닌 다른 노드가 잠시 대신 맡아둡니다.

2007년 다이나모 논문은 쓰기 가용성을 극대화하기 위해 '힌티드 핸드오프(Hinted Handoff)'라는 기법을 도입했습니다. 데이터를 복제해야 하는 3대의 노드 중, 원래 데이터를 받아야 할 노드가 죽어 있는 상황을 논문은 이렇게 돌파합니다.

"In this example, if node A is temporarily down or unreachable during a write operation then a replica that would normally have lived on A will now be sent to node D. ... The replica sent to D will have a hint in its metadata that suggests which node was the intended recipient of the replica (in this case A)."

이 예시에서 쓰기 작업 중 노드 A가 일시적으로 다운되거나 연락이 두절되면, 원래 노드 A에 저장되었을 복제본이 이제 노드 D로 전송된다. ... D로 전송된 복제본의 메타데이터에는 원래 수신자가 어느 노드였는지, 이 경우에는 A였음을 알려주는 힌트가 담긴다.

- Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, 4.6 Handling Failures: Hinted Handoff

쉽게 말해 택배 배달과 같습니다. 고객(애플리케이션)이 보낸 장바구니 데이터를 노드 A의 집에 배송하려는데, A가 집을 비웠습니다. 시스템은 반송 처리(쓰기 실패)를 하는 대신, 옆집에 사는 노드 D에게 "이거 원래 A의 물건인데, A가 돌아오면 꼭 전해주라"는 쪽지(Hint)를 붙여 임시로 맡겨버립니다.

이후 노드 A가 재부팅되어 다시 살아나면, 쪽지를 쥐고 있던 D가 A에게 데이터를 건네주며 임시 보관했던 짐을 털어냅니다. 이 우회로 덕분에 다이나모는 일부 노드의 장애 속에서도 꿋꿋하게 쓰기 요청을 받아낼 수 있었습니다.

하지만 노드가 살아난 뒤에, 죽어있던 시간 동안 엇갈려버린 데이터의 차이는 어떻게 빠르게 찾아내어 맞춰갈까요?

다이나모는 복제본들 사이의 불일치를 찾아내기 위해 '머클 트리'라는 구조를 사용합니다.

https://en.wikipedia.org/wiki/Merkle_tree

두 서버가 가진 거대한 데이터베이스가 완벽히 똑같은지 확인한다고 상상해 보십시오. 가장 무식한 방법은 수백 GB의 데이터를 통째로 서로 전송해 가며 비교하는 것이지만, 이는 네트워크를 마비시킵니다.

이때 머클 트리는 데이터를 아주 잘게 쪼개어 해시값으로 만들고, 이를 나뭇가지처럼 엮어 올라가 하나의 거대한 '뿌리 해시(Root Hash)'를 만듭니다. 두 서버는 먼저 이 뿌리 해시값 하나만 서로 교환해 비교합니다. 뿌리가 같다면 두 서버의 데이터는 100% 일치하는 것이니 검사를 바로 끝냅니다. 만약 뿌리가 다르다면, 가지를 타고 한 단계씩 밑으로 내려가며 해시값이 다른 부분을 추적합니다.

마치 1,000페이지짜리 백과사전 두 권을 비교할 때 처음부터 끝까지 다 읽는 대신, 목차의 글자 수(뿌리)를 비교하고, 단원의 글자 수(가지)를 비교해 나가는 식입니다. 이 방식을 쓰면 네트워크를 거의 쓰지 않고도 어느 페이지의 어느 줄이 틀렸는지 족집게처럼 찾아내어 그 부분만 동기화할 수 있습니다.

15년 뒤의 진화, 로그 리플리카

15년 뒤에 발표된 2022년 다이나모DB 논문으로 넘어가 보겠습니다.

현대의 아키텍처는 노드의 일시적 장애를 어떻게 버텨낼까요?

수 초 안에 '로그 리플리카(Log Replica)'라는 경량화된 예비군을 새로 투입합니다.

2022년 논문에는 힌티드 핸드오프를 대신하여 장애에 대응하는 구체적인 사유와 방식이 적혀 있습니다. 물리적인 스토리지 복제본 하나가 죽었을 때, 이를 온전히 복구하려면 거대한 데이터베이스 트리(B-tree)와 쓰기 로그를 통째로 복사해야 하므로 수 분의 시간이 걸립니다. 논문은 이 시간 동안 전체 복제본이 3개에서 2개로 줄어드는 위험한 무방비 상태를 방치하지 않습니다.

"The process of healing a storage replica can take several minutes because the repair process involves copying the B-tree and write-ahead logs. Upon detecting an unhealthy storage replica, the leader of a replication group adds a log replica to ensure there is no impact on durability. Adding a log replica takes only a few seconds because the system has to copy only the recent write-ahead logs from a healthy replica to the new replica without the B-tree."

스토리지 복제본을 치유하는 과정은 수 분이 걸릴 수 있다. 복구 과정에서 B-트리와 쓰기 로그를 복사해야 하기 때문이다. 건강하지 않은 스토리지 복제본을 감지하면, 복제 그룹의 리더는 내구성에 영향이 없도록 로그 복제본을 추가한다. 로그 복제본 추가는 몇 초밖에 걸리지 않는다. 건강한 복제본에서 최근 쓰기 로그만 복사하고 B-트리는 가져오지 않기 때문이다.

- Mostafa Elhemali et al., Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service, USENIX ATC 2022, 5.1 Hardware failures

리더 노드는 기존 노드가 죽은 것을 감지하면, 즉시 복제 그룹에 이 '로그 리플리카'를 땜빵으로 끼워 넣습니다.

이 상황을 현실에 비유해 보겠습니다. 3명이 한 조로 일하는 관공서 민원 창구(복제 그룹)가 있습니다. 이들은 민원 내용을 수첩(쓰기 로그)에 먼저 받아 적고, 나중에 거대한 철제 캐비닛(B-트리 스토리지)에 차곡차곡 정리합니다. 그런데 직원 한 명이 쓰러졌습니다.

원래대로라면 캐비닛까지 완비된 정직원을 새로 뽑아서 투입해야 하지만, 서류를 인수인계하는 데 수 분이 걸립니다. 그래서 일단 당장 쏟아지는 민원을 쳐내기 위해, 무거운 캐비닛 없이 가벼운 수첩 하나만 달랑 들고 있는 아르바이트생(로그 리플리카)을 몇 초 만에 긴급 투입하는 것입니다.

이 로그 리플리카는 팩소스 합의 알고리즘에 참여하여 "나도 수첩에 기록했음!"이라고 손을 들어주는 수락자 역할만 수행합니다. 무거운 과거 데이터를 복사받을 필요가 없으니 투입 속도가 번개처럼 빠릅니다. 이 녀석이 3번째 복제본 역할을 임시로 대신해 주는 덕분에, 시스템은 원래의 스토리지가 수 분에 걸쳐 복구되는 동안에도 세 벌의 안전망을 굳건하게 유지할 수 있습니다.

저는 "일시적 장애를 어떻게 견딜 것인가"라는 똑같은 질문을 두고, 15년 간격으로 나온 두 해법이 나란히 놓이는 모습이 무척 흥미롭습니다.

힌티드 핸드오프와 로그 리플리카는 기술적 구현이 완전히 다릅니다. 하지만 두 방식 모두 "무겁고 완전한 복구는 나중으로 미루고, 지금 당장은 가벼운 장치를 덧대어 일단 가용성부터 지켜낸다"는 동일한 시스템 설계 철학을 관통하고 있으니까요.

그런데 여기까지 따라오셨다면 한 가지 근본적인 의문이 드실 겁니다.

앞서 힌티드 핸드오프 상황에서, 시스템은 노드 A가 죽었다는 사실을 알아채고 재빠르게 노드 D에게 짐을 맡겼습니다. 수백 대의 서버가 얽혀 있는 거대한 해시 링 위에서, 도대체 '누가' 노드 A가 죽었다는 사실을 파악하고 다른 노드들에게 알려준 걸까요?

현대의 다이나모DB라면 리더 노드나 중앙 제어 평면이 그 역할을 통제하겠지만, 2007년의 다이나모에는 전체 서버의 생사 여부나 해시 링의 상태를 감시하는 '중앙 관리자' 서버가 단 한 대도 없었습니다.

모두가 평등하지만 그 누구도 전체를 통제하지 않는 이 거대한 분산 환경에서, 다이나모는 네 번째 핵심 장치를 통해 기발하게 이 문제를 돌파합니다.

6. 장치 넷, 가십

중앙 통제가 없는 세계의 동기화

중앙 노드가 없는데 전체 서버의 상태는 어떻게 동기화할까요?

바로 소문을 퍼뜨리는 것입니다.

1987년 데머스(Demers)가 발표한 논문 Epidemic Algorithms for Replicated Database Maintenance는 제록스 PARC 사내 네트워크의 수많은 컴퓨터를 동기화하기 위해 기발한 아이디어를 냅니다. 현실 세계의 '전염병 확산 모델'을 시스템에 그대로 이식한 것이죠.

"This paper describes several randomized algorithms for distributing updates and driving the replicas toward consistency. ... Anti-entropy and rumor mongering are both examples of epidemic processes, and results from the theory of epidemics are applicable."

이 논문은 갱신을 분산시키고 복제본들을 일관된 상태로 이끄는 여러 무작위 알고리즘을 설명한다. ... 안티 엔트로피와 루머 몽거링은 둘 다 전염병 과정의 예이며, 전염병 이론의 결과를 그대로 적용할 수 있다.

- Alan Demers et al., Epidemic Algorithms for Replicated Database Maintenance, PODC 1987, Abstract, 1 Introduction

논문은 이 전염병 모델을 통해 정보를 전파하는 세 가지 방식을 비교합니다.

첫째, 새로운 갱신이 발생하면 모든 사이트에 즉시 편지를 쏘는 '다이렉트 메일'입니다. 가장 직관적이지만 네트워크가 조금만 붐비거나 불안정해도 편지가 유실되기 십상입니다.

둘째, '루머 몽거링(Rumor mongering, 소문 퍼뜨리기)'입니다. 마치 직장 휴게실에서 핫한 가십거리가 퍼지는 과정과 같습니다. 어떤 노드가 새로운 정보를 얻으면 '감염' 상태가 되어 무작위로 다른 노드를 찔러 소문을 전파합니다. 그러다 만나는 상대방마다 "어, 나 그거 이미 아는데?"라고 답하는 횟수가 늘어나면, 소문이 충분히 퍼졌다고 판단해 스스로 흥미를 잃고 전파를 멈춥니다(Removed 상태). 네트워크 자원을 아주 적게 쓰면서도 폭발적으로 퍼져나가지만, 100명 중 1~2명은 끝까지 소문을 듣지 못할 수 있다는 치명적인 맹점을 안고 있습니다.

셋째, '안티 엔트로피(Anti-entropy)'입니다. 시스템의 무질서도(엔트로피)를 낮춘다는 뜻의 이 방식은 무식하지만 확실합니다. 주기적으로 무작위 서버 하나를 골라, 각자 가진 데이터베이스 전체를 통째로 꺼내놓고 틀린 그림 찾기를 하듯 꼼꼼하게 차이를 맞춰봅니다.

원전 논문은 안티 엔트로피와 루머 몽거링의 장단점을 다음과 같이 이야기합니다.

"Anti-entropy is extremely reliable but requires examining the contents of the database and so cannot be used too frequently. ... Rumor cycles can be more frequent than anti-entropy cycles because they require fewer resources at each site, but there is some chance that an update will not reach all sites."

안티 엔트로피는 극도로 신뢰성이 높지만 데이터베이스 내용을 들여다봐야 하므로 너무 자주 돌릴 수 없다. ... 루머 사이클은 각 사이트에서 자원을 덜 쓰기 때문에 안티 엔트로피보다 자주 돌 수 있지만, 갱신이 모든 사이트에 도달하지 못할 가능성이 어느 정도 있다.

- Alan Demers et al., Epidemic Algorithms for Replicated Database Maintenance, PODC 1987, 1 Introduction

원전 다이나모가 전체 서버의 생사 여부와 링의 지도를 동기화하기 위해 택한 방식은 이 중 '안티 엔트로피' 계열에 가깝습니다. 다이나모 논문을 보면, 각 노드는 매 1초마다 무작위로 피어 하나를 골라 접촉하고, 두 노드가 각자 보관해 온 멤버십 변경 이력을 서로 맞춰 나갑니다.

중앙의 마스터 노드가 없어도, 노드들이 1초마다 서로의 상태를 묻고 답하며 릴레이를 하다 보면 최종적으로 수백 대의 서버가 똑같은 해시 링의 지도를 머릿속에 그리게 되는 우아한 구조입니다.

그런데 이 대목에서 다이나모 논문이 툭 던지듯 적어둔 문장 하나가 강렬하게 눈에 걸립니다.

"Early designs of Dynamo used a decentralized failure detector to maintain a globally consistent view of failure state. ... Later it was determined that the explicit node join and leave methods obviates the need for a global view of failure state."

다이나모의 초기 설계는 장애 상태에 대한 전역적으로 일관된 시야를 유지하기 위해 탈중앙화된 장애 감지기를 썼다. 하지만 나중에 노드의 합류와 이탈을 명시적으로 알리는 방식을 두자, 장애 상태에 대한 전역 시야가 더 이상 필요 없어졌다는 결론에 이르렀다.

- Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, 4.8.3 Failure Detection

순수한 탈중앙화 가십 프로토콜만으로 완벽한 전역 상태를 유지하는 것은, 아마존의 거대한 인프라에서도 지나치게 무겁고 예측하기 까다로웠던 것입니다. 결국 서버가 새로 링에 합류하거나 영구적으로 이탈할 때는 사람이(관리자 노드가) 직접 명시적으로 명령을 내려주는 실용적인 타협을 택했습니다.

가십 알고리즘의 한계와 탈중앙화의 후퇴는, 15년 뒤 다이나모DB가 팩소스라는 중앙 통제형 리더를 세우면서 갑자기 시작된 것이 아닙니다. 그 거대한 변화의 징조는 이미 2007년 원전 논문 안에서 싹트고 있었던 셈입니다.

15년 뒤, 사라진 소문들

그렇다면 2007년에 이미 싹트고 있던 이 변화의 징조는, 15년 뒤 다이나모DB 아키텍처에서 어떤 결과로 나타났을까요? 가십 프로토콜은 얼마나 더 정교하게 진화했을까요?

놀랍게도 2022년 논문에서 'Gossip'이라는 단어는 단 한 번도 등장하지 않습니다. 전염병도, 안티 엔트로피도 마찬가지입니다.

대신 그 자리를 'MemDS'라는 이름의 거대한 중앙 인메모리 서비스가 꿰찼습니다.

과거에는 수백 대의 노드가 1초마다 무작위로 서로를 찔러보며 소문을 퍼뜨려 링의 전체 지도를 그렸습니다. 하지만 현대의 다이나모DB에서는 파티션의 위치와 노드들의 상태 정보(메타데이터)를 MemDS라는 초고속 '중앙 명부'에 모조리 올려버립니다. 클라이언트의 쓰기/읽기 요청을 받아 길을 안내하는 라우터 서버들은, 이제 굳이 소문이 퍼지기를 기다릴 필요 없이 이 중앙 명부를 쓱 훑어보고 즉시 가장 정확한 최신 목적지로 요청을 꽂아 넣습니다.

팩소스 알고리즘으로 선출된 리더 노드들 역시, 피어 노드들과 서로 소문을 주고받는 대신 일정 시간 리더 권한을 '임대'하는 방식으로 지위를 갱신하며 철저하게 중앙화된 규칙을 따릅니다.

무작위로 소문을 주고받으며 아등바등 시야를 맞추던 자율적인 노드들이, 이제는 거대한 중앙의 명부를 일사불란하게 조회하는 구조로 완전히 탈바꿈한 것입니다.

물론 2022년 다이나모DB 논문에 단어가 없다고 해서 아마존의 모든 거대 인프라에서 소문 퍼뜨리기 기술이 완전히 폐기되었다고 단정할 수는 없습니다. 하지만 아키텍처의 뼈대와 무게 중심이 이동한 것만은 명확합니다.

저는 이 거대한 구조적 회귀가 무척 아이러니하면서도 흥미롭습니다.

2007년의 다이나모는 특정 서버에 부하가 몰리는 '중앙 병목'을 피하기 위해 완벽한 탈중앙화와 가십 프로토콜을 도입했습니다. 하지만 클라우드 규모의 거대한 트래픽과 수백만 개의 파티션을 한 치의 오차 없이 통제해야 하는 15년 뒤의 현실 앞에서는, 역설적으로 지연 없는 완벽한 시야를 제공하는 '강력한 중앙 제어 서비스'로 되돌아간 셈이니까요.

리더가 없는 2007년의 거친 탈중앙화 환경이 낳은 가장 골치 아픈 부작용은 상태 정보의 지연만이 아니었습니다. 누구나 쓰기 요청을 받아줄 수 있다 보니 필연적으로 발생하는 '데이터의 충돌'이 진짜 문제였습니다.

네트워크가 끊어진 사이 노드 A에는 '운동화'가 담기고, 노드 B에는 '양말'이 담기며 장바구니 데이터의 평행세계가 열렸다면, 나중에 네트워크가 복구되었을 때 이 두 갈래의 버전을 어떻게 하나로 합쳐야 할까요?

이제 다이나모가 남겨둔 마지막 봉인, 찢어진 데이터를 하나로 꿰매는 장치를 열어볼 차례입니다.

7. 봉인의 열쇠를 누구에게 줬나, 벡터 시계

논문에 적힌 기묘한 예언

데이터 버전이 여러 갈래로 찢어졌을 때, 충돌을 해결하여 진짜 데이터를 결정하는 책임은 누구에게 있을까요?

정답은 데이터베이스 엔지니어가 아니라 '애플리케이션 개발자'입니다.

2007년 논문의 2.3절 '설계 고려사항(Design Considerations)'은 갈라진 장바구니 버전을 하나로 병합하는 무거운 짐을 데이터베이스(다이나모)가 아닌, 다이나모를 가져다 쓰는 애플리케이션 계층에 과감하게 떠넘겼다고 명시합니다. 데이터베이스는 비즈니스 로직(운동화와 양말을 모두 장바구니에 살릴지, 하나만 살릴지)을 알지 못하기 때문입니다. 데이터베이스가 자체적으로 충돌을 해결하려 들면, 시간상 가장 마지막에 들어온 요청만 덮어쓰고 나머지는 날려버리는 '마지막 쓰기 승리'라는 무식한 정책밖에 쓸 수 없다는 것이 아마존의 논리였습니다.

이때 다이나모는 개발자가 충돌을 정교하게 병합할 수 있도록 찢어진 데이터의 족보를 달아주는데, 이 장치가 바로 '벡터 시계(Vector Clock)'입니다.

이 기술은 1978년 분산 시스템의 대부 레슬리 램포트(Leslie Lamport)가 쓴 전설적인 논문 Time, Clocks, and the Ordering of Events in a Distributed System에 이론적 뿌리를 둡니다. 램포트는 이 논문의 서두에서 분산 환경이 가진 시간의 근본적인 한계를 다음과 같이 정의합니다.

"The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events."

분산 시스템에서 한 사건이 다른 사건보다 먼저 일어난다는 개념을 살펴보고, 그것이 사건들의 부분 순서를 정의함을 보인다. 그리고 사건 전체에 순서를 매기는 데 쓸 수 있는 논리적 시계 시스템을 동기화하는 분산 알고리즘을 제시한다.

- Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, CACM 1978, Abstract

램포트의 통찰처럼, 물리적인 시간이 다르게 흐르는 분산 환경에서는 어떤 사건이 먼저 일어났는지 전체 시스템의 완벽한 순서(Total order)를 매길 수 없고 오직 '부분적인 순서'만 파악할 수 있습니다. 이 한계를 극복하기 위해, 데이터에 '어떤 노드가, 언제 수정했는지'를 배열 형태로 꼬리표처럼 달아 버전들의 인과관계와 족보를 정교하게 추적하는 것이 벡터 시계의 핵심입니다.

그런데 다이나모 설계자들은 이 복잡하고 정교한 충돌 해결의 열쇠를 개발자들에게 넘겨주면서도, 논문의 같은 문단에 매우 기묘한 예언을 남깁니다.

"Despite this flexibility, some application developers may not want to write their own conflict resolution mechanisms and choose to push it down to the data store, which in turn chooses a simple policy such as 'last write wins'."

이러한 유연성에도 불구하고, 일부 애플리케이션 개발자는 자체적인 충돌 해결 로직을 짜고 싶어 하지 않을 수 있다. 이들은 책임을 데이터 저장소로 떠넘기려 할 것이고, 그러면 데이터 저장소는 결국 '마지막 쓰기 승리(Last write wins)' 같은 단순한 정책을 택하게 될 것이다.

- Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, 2.3 Design Considerations

시스템이 아무리 정교한 벡터 시계를 쥐여주고 비즈니스 로직에 맞게 충돌을 해결할 유연성을 열어주어도, 정작 애플리케이션 개발자들은 귀찮아서 직접 병합 로직을 짜기 싫어할 것이라는 냉소적인 예측이었습니다.

그래서 결국 개발자들은 다시 데이터베이스에게 "네가 알아서 시간상 가장 마지막에 들어온 요청 기준으로 덮어써 줘(Last write wins)"라며 책임을 다시 던져버릴 것이라는 뼈아픈 문장입니다.

99.94퍼센트의 역설

그런데 한번 생각해봅시다. 저 역시도 수많은 트랜잭션이 쏟아지는 결제 시스템 백엔드 현장의 경험을 돌이켜볼 때, 복잡한 비즈니스 로직의 정합성을 맞추는 것만으로도 개발자들은 늘 벅찹니다. 그런데 데이터베이스 인프라가 마땅히 감당해야 할 데이터 충돌 병합 로직까지 애플리케이션 코드 안에서 직접 구현하고 테스트하라는 것은 현장에 엄청난 짐을 떠안기는 셈입니다.

그렇다면 실제 운영 환경에서 이러한 애플리케이션의 충돌은 얼마나 자주 일어났을까요?

원전 논문이 24시간 동안 실측한 결과에 따르면, 99.94%의 요청이 정확히 단 하나의 버전만 보았습니다.

"During this period, 99.94% of requests saw exactly one version; 0.00057% of requests saw 2 versions; 0.00047% of requests saw 3 versions and 0.00009% of requests saw 4 versions. This shows that divergent versions are created rarely."

이 기간 동안 99.94%의 요청은 정확히 하나의 버전만 보았다. 2개의 버전을 본 요청은 0.00057%, 3개를 본 요청은 0.00047%, 4개를 본 요청은 0.00009%였다. 이는 발산된 버전이 극히 드물게 생성됨을 보여준다.

- Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007, 6.3 Divergent Versions: When and How Many?

논문은 이 압도적인 단일 버전 비율을 내세우며 '발산 버전은 극히 드물게 생긴다'는 긍정적인 근거로 활용합니다.

하지만 저는 이 수치를 완전히 다르게 읽어야 한다는 생각이 듭니다.

저 수치는 1만 번에 단 여섯 번 일어나는 희박한 오류를 방어하기 위해, 모든 애플리케이션 개발자가 복잡한 분산 브랜치 병합 로직을 직접 짜야 했다는 뜻이니까요. 실무를 하는 개발자 입장에서, 그렇게 드물게 발현되는 문제의 복잡성을 애플리케이션 레벨에서 온전히 껴안고 통제하는 건 조금 넌센스에 가깝다는 생각이 듭니다.

개발자들의 도망과 15년 뒤의 논문

다이나모의 철학을 계승했던 다른 분산 데이터베이스들이 이 대목에서 어떤 선택을 했는지 보면 흥미롭습니다. 둘의 경로가 정반대인데 결론은 같습니다.

카산드라는 애초에 이 열쇠를 받지 않았습니다. 카산드라 공식 문서는 자신들의 선택을 원전과 대놓고 대비시킵니다.

"Unlike in the original Dynamo paper where deterministic versions and vector clocks were used to reconcile concurrent updates to a key, Cassandra uses a simpler last-write-wins model where every mutation is timestamped (including deletes) and then the latest version of data is the 'winning' value."

키에 대한 동시 갱신을 조정하기 위해 결정적 버전과 벡터 시계를 사용했던 원전 다이나모 논문과 달리, 카산드라는 더 단순한 마지막 쓰기 승리 모델을 쓴다. 모든 변경에 타임스탬프를 찍고, 삭제까지 포함해서, 가장 최신 버전의 데이터를 승자로 삼는 방식이다.

- Apache Cassandra 공식 문서, Dynamo (cassandra.apache.org)

동시 갱신을 조정하기 위해 결정적 버전과 벡터 시계를 썼던 원전 다이나모 논문과 달리, 카산드라는 모든 변경에 타임스탬프를 찍고 가장 최신 버전을 승자로 삼는 더 단순한 방식을 쓴다고 명시합니다. 삭제까지 포함해서 말이죠. 2010년 첫 논문부터 이 방식이었으니 벡터 시계를 쓰다가 버린 것이 아니라 처음부터 들지 않은 셈입니다. 다만 이 방식은 서버 시계의 정확도에 시스템의 정합성이 걸리게 되므로, 문서는 NTP 같은 시각 동기화를 반드시 돌리라고 경고합니다.

리악은 열쇠를 받았다가 결국 대신 들어줄 도구를 만들었습니다. 리악 공식 문서를 보면 이렇게 적혀 있습니다.

"In versions of Riak prior to 1.4, Riak used vector clocks as the sole means of tracking the history of object updates. ... If you are using Riak version 2.0 or later, we strongly recommend using dotted version vectors instead of vector clocks, as DVVs are far better at limiting the number of siblings produced in a cluster, which can prevent a wide variety of potential issues."

1.4 이전 버전의 리악은 객체 갱신 이력을 추적하는 유일한 수단으로 벡터 시계를 사용했다. ... 리악 2.0 이상을 쓰고 있다면 벡터 시계 대신 점 찍힌 버전 벡터를 쓰기를 강력히 권장한다. 클러스터에서 생성되는 형제의 개수를 제한하는 데 훨씬 뛰어나고, 그 덕분에 다양한 잠재적 문제를 예방할 수 있기 때문이다.

- Riak KV 공식 문서, Causal Context (docs.riak.com)

충돌이 생기면 리악은 형제라는 여러 버전을 그대로 남겨두고 애플리케이션이 직접 고르게 합니다. 그런데 같은 문서가 스스로 충돌 해결 전략을 만드는 일이 까다롭다고 인정하면서, 데이터를 리악이 제공하는 데이터 타입으로 모델링할 수 있다면 그쪽을 권장한다고 적었습니다.

그 데이터 타입들은 CRDT 기반이라 충돌 해결이 내장되어 있어서, 애플리케이션이 충돌 해결에 관여할 필요를 완전히 덜어준다는 이유에서입니다.

2007년 논문이 예언한 문장을 다시 읽어보면, 리악 문서의 이 권고가 바로 그 예언의 실현 보고서처럼 읽힙니다. 애초에 받지 않은 쪽과 받았다가 내려놓은 쪽이 서로 다른 길을 걸어 같은 곳에 도착했습니다.

다시 15년 뒤의 논문으로 돌아와 보겠습니다.

2022년 다이나모DB 논문에서 벡터 시계와 충돌 해결은 몇 번이나 언급될까요?

한 번도 등장하지 않습니다.

6절의 가십이 그랬듯, Vector clock도 Conflict resolution도 논문 전문을 뒤져봐도 나오지 않습니다. 단어가 없다는 것만으로 기술의 완전한 폐기를 단정할 수는 없습니다. 다만 이번에는 사라진 이유를 논문 안에서 직접 찾을 수 있습니다.

현대의 다이나모DB는 앞서 확인했듯 팩소스 기반의 리더를 세웠습니다. 리더가 쓰기를 독점함으로써 애초에 데이터 버전이 갈라지고 충돌하는 발산 자체를 구조적으로 없애버린 것입니다. 논문의 예언대로 개발자들은 도망쳤고, 시스템은 다시금 일관성의 고삐를 데이터베이스 쪽으로 강하게 쥐는 방향으로 진화했습니다.

그래서 무엇이 남고 무엇이 바뀌었나

여기까지 오면 질문이 한꺼번에 쏟아집니다. 그래서 다이나모는 '언제나 쓸 수 있다'를 버린 걸까요? 팩소스는 대체 무엇을 달성한 걸까요? 최종적 일관성은 폐기된 걸까요? 개발자에게 넘겼던 짐은 결국 어떻게 된 걸까요?

하나씩 짚고 가겠습니다.

'언제나 쓸 수 있다'는 버려진 것이 아니라 값이 매겨졌습니다. 2007년에는 아무 노드나 쓰기를 받았기 때문에 문자 그대로 거절이 없었습니다. 2022년에는 리더만 쓰기를 받으므로, 리더가 죽으면 새 리더를 뽑는 동안 쓰기가 거절됩니다. 이론적으로는 명백한 후퇴입니다. 다만 그 공백을 몇 초 단위로 줄여놓았습니다. 절대 거절하지 않겠다는 약속을, 아주 짧게만 거절하겠다는 약속으로 바꾼 셈입니다.

팩소스가 달성한 것은 성능이 아니라 순서입니다. 쓰기를 리더 한 곳으로 모으면 모든 갱신에 하나의 순서가 생깁니다. 순서가 하나면 버전이 갈라질 수 없습니다. 버전이 갈라지지 않으면 벡터 시계로 족보를 추적할 일도, 애플리케이션이 병합할 일도 없습니다. 팩소스는 충돌을 잘 푸는 기술이 아니라, 충돌이 생길 자격 자체를 없애는 기술이었습니다.

최종적 일관성은 폐기되지 않았습니다. 현재 다이나모DB는 강한 일관성 읽기와 최종적 일관성 읽기를 둘 다 제공합니다. 최신 데이터가 꼭 필요한 조회는 리더를 거치고, 조금 낡아도 되는 조회는 아무 복제본에서나 가져옵니다. 2007년에 시스템 전체의 성격이었던 것이 2022년에는 요청 하나하나의 옵션이 되었습니다.

개발자에게 넘겼던 짐은 회수되었습니다. 다만 개발자가 아무것도 결정하지 않게 된 것은 아닙니다. 넘겨받은 것이 바뀌었을 뿐입니다. 예전에는 "갈라진 장바구니를 어떻게 합칠 것인가"라는 구현을 떠안았고, 지금은 "이 조회에 강한 일관성이 필요한가"라는 판단을 떠안습니다. 앞의 것은 틀리면 데이터가 조용히 망가지고, 뒤의 것은 틀려도 조금 낡은 값을 보거나 비용을 조금 더 낼 뿐입니다.

책임의 크기가 아니라 책임의 종류가 바뀐 것입니다. 인프라가 감당할 수 있는 것을 가져가고, 도메인을 아는 쪽만 답할 수 있는 것을 남겼습니다.

여섯 개의 결정 중 형태를 그대로 유지한 것은 안정 해시 하나뿐입니다. 나머지 다섯은 전부 다른 것으로 대체되었습니다.

8. 닫는 글: 복잡성 보존의 법칙

'언제나 쓸 수 있다'는 환상의 대가

다이나모가 15년에 걸친 진화 과정에서 최종적으로 내려놓은 이상은 무엇일까요?

'언제나 쓸 수 있다'는 무결한 약속입니다.

2007년의 원전 논문은 어떤 장애 상황에서도 고객이 장바구니에 물건을 담을 수 있어야 한다고 선언했습니다. 데이터 일관성을 조금 희생하더라도 시스템의 가용성을 극대화하는 위대한 아키텍처적 결단이었습니다.

하지만 그 마법 같은 가용성의 청구서는 결국 애플리케이션 계층으로 날아왔습니다. 네트워크 단절과 어긋난 시야 속에서 파생된 데이터 충돌과 발산의 책임을 비즈니스 로직을 짜는 개발자들이 오롯이 짊어져야 했으니까요.

문제는 되살아나는 물건이 아니었습니다

이 글의 처음으로 돌아가 봅니다.

장바구니에서 지운 물건이 되살아나는 현상, 그것이 이 이야기의 핵심 문제였을까요?

아닙니다.

되살아나는 물건은 증상이었습니다. 아마존은 그 증상을 이미 알고 있었고 논문에 적어두기까지 했습니다. 알고도 감수한 결함은 문제가 아니라 청구서에 적힌 금액입니다.

정작 문제는 그 청구서를 누가 받을지 정한 한 문장에 있었습니다.

충돌 해결은 애플리케이션이 하면 된다는 문장 말입니다.

2007년 논문 2.3절의 이 결정은 얼핏 흠잡을 데가 없어 보입니다. 데이터베이스는 비즈니스 로직을 모르고 애플리케이션은 압니다. 아는 쪽이 판단하는 것이 옳습니다. 논리에 빈틈이 없습니다.

그런데 아마존은 바로 그 다음 문장에서 개발자들이 그 판단을 하지 않을 것이라고 적었습니다. 빈틈없는 논리와, 그 논리가 현실에서 작동하지 않으리라는 예감이 한 문단 안에 나란히 놓여 있습니다.

저는 이 대목이 두 논문을 통틀어 가장 서늘한 부분이라는 생각이 듭니다.

책임을 넘기는 쪽은 대개 그 책임이 실제로 수행될지를 이미 짐작합니다. 그러면서도 넘깁니다. 넘기는 순간 설계는 완결되고, 넘겨받은 쪽에서 그것이 방치되는지는 설계도에 기록되지 않으니까요. 게다가 1만 번에 여섯 번 발현되는 문제라면 더욱 그렇습니다. 드물게 터지는 결함은 아무도 급하게 처리하지 않습니다.

15년 뒤 카산드라와 리악과 다이나모DB는 각자 다른 길로 갔습니다. 타임스탬프로 덮어썼고, CRDT를 붙였고, 리더를 세웠습니다. 방법은 셋 다 달랐지만 한 가지는 같았습니다. 셋 다 개발자에게 넘겼던 그 문장을 도로 회수했습니다.

15년 만에 되돌아온 시계추

이 거대한 시스템의 변화가 현대의 우리에게 남기는 교훈은 무엇일까요?

복잡성은 결코 사라지지 않고 계층 사이를 이동할 뿐이라는 사실입니다.

2022년의 다이나모DB는 악명 높은 팩소스 합의 알고리즘을 데이터베이스 엔진 깊숙이 심고, 단일 리더 노드에게 쓰기 권한을 독점시켰습니다. 분산 환경에서 필연적으로 발생하는 데이터 충돌의 책임을 개발자에게 미루는 대신, 인프라스트럭처가 압도적인 엔지니어링 역량으로 그 통제 불가능한 복잡성을 스스로 껴안는 길을 선택했습니다.

저는 이 15년의 간격을 두고 발표된 두 편의 논문이 단순한 기술 명세서를 넘어선다는 생각이 듭니다.

이론적 이상향을 현실의 거대한 트래픽과 운영 복잡도에 맞춰 끊임없이 타협하고 깎아내려간 치열한 아키텍처의 진화 기록입니다.

학계의 아름다운 논문들(안정 해시, 정족수, 전염병 모델, 벡터 시계)을 가져와 현실의 진흙탕 속에서 뒹굴게 하며 아마존이 얻어낸 결론이 이것이라 저는 확신할 수 있었습니다.

완벽한 분산 시스템은 없으며, 오직 그 시대의 비즈니스가 감당할 수 있는 최적의 Trade-off만이 존재할 뿐이라는, 오래된 진실 말이죠.

부록: 몇가지 질문들 - Q&A

글을 쓰면서 궁금한 점이 있었는데, 본문에 편입하기보다는 질문과 답변 형식으로 정리하는 것이 나을 것 같아 Q&A 형식으로 정리했습니다.

1. 리더 한 대가 쓰기를 전부 받는다면, 그게 병목 아닌가

논문의 문장을 보면 이렇게 되어 있습니다.

"Only the leader replica can serve write and strongly consistent read requests."

오직 리더 복제본만이 쓰기와 강한 일관성 읽기 요청을 처리할 수 있다.

- Mostafa Elhemali et al., Amazon DynamoDB, USENIX ATC 2022, 3 Architecture

그렇다면 이 리더가 무엇의 리더인가입니다. 데이터베이스 전체의 리더도, 테이블의 리더도 아닙니다. 파티션 하나의 리더입니다.

다이나모DB는 테이블을 파티션 단위로 쪼개고, 파티션마다 복제본 세 개가 복제 그룹을 이룹니다. 팩소스는 이 세 대 안에서만 돕니다.

"The replication group uses Multi-Paxos for leader election and consensus."

복제 그룹은 리더 선출과 합의에 멀티 팩소스를 사용한다.

- 같은 논문, 3 Architecture

그러니 테이블이 파티션 1만 개로 쪼개져 있으면 쓰기를 받는 리더도 1만 대입니다. 요청 라우터가 파티션 키를 보고 해당 파티션의 리더에게 넘깁니다. 병목이 생길 만한 크기로 리더의 지배 범위를 잘라둔 것입니다.

5장에서 봤던 정족수는 없어진 게 아니라 이 세 대 안으로 들어왔습니다.

"A healthy write quorum in the case of DynamoDB consists of two out of the three replicas from different AZs."

다이나모DB에서 건강한 쓰기 정족수는 서로 다른 가용 영역에 있는 세 복제본 중 둘로 구성된다.

- 같은 논문, 6.1 Write and consistent read availability

2007년의 W+R>N이 클러스터 전체를 상대로 돌던 것과 달리, 2022년의 정족수는 파티션 하나에 딸린 세 대의 문제입니다.

같은 장치를 훨씬 작은 상자 안에 다시 넣은 셈입니다.

2. 리더가 수만 대라면, 그들끼리 맞추는 비용은 어디로 갔나

없습니다. 애초에 맞출 일이 없기 때문입니다.

파티션 키가 해시로 어느 파티션에 속할지를 결정하고, 한 키의 데이터는 언제나 한 파티션에만 있습니다. 7,402번 파티션의 리더는 3번 파티션의 리더가 무엇을 쓰든 알 필요가 없습니다. 동기화는 자기 복제 그룹의 두 대와만 합니다. 1만 대의 거대한 합의가 아니라 세 대짜리 합의가 1만 개 나란히 도는 구조입니다.

DynamoDb 를 보면... 파티션키를 ... 하는 부분이 중요한데, 이것이 바로 ㅇㅇㅇ한 이유인 것이었죠.

부하가 몰리면 리더를 여러 대로 묶는 대신 파티션을 쪼갭니다.

Once the consumed throughput of a partition crosses a certain threshold, the partition is split for consumption.

파티션의 소비 처리량이 특정 임계치를 넘으면 그 파티션은 소비량 기준으로 분할된다.

출처: 같은 논문, 4.4 Splitting for consumption

여기서 논문이 굳이 한 문장을 더 쓴 대목이 흥미롭습니다. 어디서 자르는지에 대한 것입니다.

"The split point in the key range is chosen based on key distribution the partition has observed. The observed key distribution serves as a proxy for the application’s access pattern and is more effective than splitting the key range in the middle."

키 범위의 분할 지점은 해당 파티션이 관찰한 키 분포를 기준으로 선택된다. 관찰된 키 분포는 애플리케이션 접근 패턴의 대리 지표 역할을 하며, 키 범위를 가운데서 자르는 것보다 효과적이다.

- 같은 논문, 4.4 Splitting for consumption

가운데를 자르면 안 됩니다. 트래픽이 한쪽에 쏠려 있는데 키 범위만 반으로 가르면 뜨거운 쪽은 그대로 뜨겁고, 오히려 그 조각에 배정된 처리량만 줄어듭니다. 그래서 관찰한 접근 패턴을 보고 자릅니다. 그리고 이 작업은 즉시 끝나지 않습니다. 논문은 분할이 보통 몇 분 걸린다고 적었습니다.

더 정직한 대목은 그다음입니다. 쪼개기로 풀리지 않는 경우를 논문이 스스로 적어둡니다.

"a partition receiving high traffic to a single item or a partition where the key range is accessed sequentially will not benefit from split. DynamoDB detects such access patterns and avoids splitting the partition."

단일 항목에 높은 트래픽이 몰리는 파티션이나 키 범위가 순차적으로 접근되는 파티션은 분할의 이득을 얻지 못한다. 다이나모DB는 그런 접근 패턴을 감지해 해당 파티션을 분할하지 않는다.

- 같은 논문, 4.4 Splitting for consumption

항목 하나에 트래픽이 쏠리면 그 항목은 더 쪼갤 수 없습니다. 수평 확장에도 바닥이 있고, 그 바닥은 데이터 모델이 정합니다. 파티션 키를 어떻게 잡을지가 왜 다이나모DB에서 그토록 중요한 결정인지가 여기서 나옵니다. 인프라가 대신 져준 복잡성의 끝에, 개발자가 여전히 들고 있어야 하는 몫이 남아 있습니다.

3. 리더가 죽으면 누가 알아채고, 그동안 쓰기는 어떻게 되나

리더는 리더십을 임대 형태로 들고 있습니다. 주기적으로 갱신하지 않으면 잃습니다. 팔로워가 리더의 신호를 못 받으면 새 선출을 제안할 수 있습니다.

그런데 이 순진한 그림이 실제로 문제를 일으켰다고 논문은 적습니다. 리더가 멀쩡히 살아 있는데 특정 팔로워와의 경로만 끊긴 회색 장애에서, 그 팔로워가 혼자 리더가 죽었다고 판단하고 선출을 시작해버립니다. 멀쩡한 리더를 끌어내리는 헛선출이 가용성을 깎았습니다. 그래서 한 단계를 덧붙였습니다.

"a follower that wants to trigger a failover sends a message to other replicas in the replication group asking if they can communicate with the leader. If replicas respond with a healthy leader message, the follower drops its attempt to trigger a leader election."

장애 조치를 일으키려는 팔로워는 복제 그룹의 다른 복제본들에게 리더와 통신이 되는지 묻는 메시지를 보낸다. 복제본들이 리더가 건강하다고 응답하면, 그 팔로워는 리더 선출 시도를 포기한다.

- 같은 논문, 6.2 Failure detection

"나만 안 되는 건가"를 먼저 물어보게 만든 것입니다. 6장에서 다이나모가 가십 기반 분산 장애 감지에서 후퇴했던 것과 같은 방향입니다. 각자 판단하게 두면 판단이 갈리고, 갈린 판단이 시스템을 흔듭니다.

수습은 둘로 나뉩니다. 급한 쪽은 복제 그룹이 자체적으로 처리합니다. 남은 복제본들이 팩소스를 돌려 새 리더를 세웁니다. 그다음 전체를 관리하는 오토어드민이 죽은 노드를 걷어내고 건강한 노드를 채워 세 대를 복구합니다. 즉시성이 필요한 결정은 데이터 평면이, 사후 정리는 제어 평면이 맡는 분업입니다.

그래서 그동안 쓰기는 어떻게 되느냐.

"The new leader won’t serve any writes or consistent reads until the previous leader’s lease expires."

새 리더는 이전 리더의 임대가 만료될 때까지 어떤 쓰기도 일관된 읽기도 처리하지 않는다.

- 같은 논문, 3 Architecture

아주 선명한 대목입니다. 복잡성 보존의 법칙을 관통하는 철학.

새 리더가 뽑혀도 곧바로 일하지 않습니다. 이전 리더의 임대가 끝날 때까지 기다립니다. 옛 리더가 어딘가에서 아직 자기가 리더라고 믿으며 쓰기를 받고 있을 수 있기 때문입니다. 두 리더가 동시에 존재하는 순간을 만들지 않겠다는 것이고, 그 대가로 해당 파티션은 그동안 쓰기를 받지 못합니다.

2007년의 다이나모라면 이 상황에서 힌티드 핸드오프를 썼을 겁니다. 리더가 없으면 옆 노드에 일단 쓰고 나중에 정리하는 방식입니다. 그 대가가 4장부터 7장까지 따라다닌 발산이었습니다.

2022년의 선택은 반대입니다. 잠깐 못 쓰게 만들고, 재시도는 클라이언트에게 넘깁니다. AWS SDK가 지수 백오프 재시도를 기본으로 넣어둔 이유가 여기 있습니다. 영향 범위가 해당 파티션 하나로 갇혀 있기 때문에 가능한 선택이기도 합니다.

다이나모 논문에서 한 문장을 꼽으라면 저는 이 문장을 꼽을 것 같습니다.

참고 자료

원전 논문

Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007. 이 글이 가장 많이 인용한 원전. 2.3 설계 고려사항, 4.2 파티셔닝, 4.4 데이터 버저닝, 4.6 힌티드 핸드오프, 4.8.3 장애 감지, 6장 경험과 교훈을 다뤘습니다.
Mostafa Elhemali et al., Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service, USENIX ATC 2022. 15년 뒤의 다이나모DB. 2장 히스토리와 5.1 하드웨어 장애를 인용했고, 부록에서 3장 아키텍처, 4.4 소비량 기준 분할, 6.1 쓰기 가용성, 6.2 장애 감지를 다뤘습니다.
David Karger et al., Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, STOC 1997. 안정 해시의 원전. 이 논문에는 원이나 시계 방향이라는 표현이 나오지 않습니다.
Alan Demers et al., Epidemic Algorithms for Replicated Database Maintenance, PODC 1987. 가십의 원류. 다이렉트 메일, 안티 엔트로피, 루머 몽거링의 비교가 여기 있습니다.
Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, CACM 1978. 벡터 시계의 이론적 뿌리인 논리적 시계와 부분 순서.
Ralph Merkle, A Digital Signature Based on a Conventional Encryption Function, CRYPTO 1987. 다이나모가 복제본 간 차이를 찾을 때 쓰는 머클 트리의 원전.

공식 문서

Apache Cassandra, Dynamo. 벡터 시계 대신 타임스탬프 기반 마지막 쓰기 승리를 택했다고 원전과 직접 대비시킨 문서.
Riak KV, Causal Context. 1.4 이전의 벡터 시계와 2.0의 점 찍힌 버전 벡터.
Riak KV, Conflict Resolution. 충돌 해결 전략을 직접 짜는 일이 까다롭다고 인정하며 CRDT 데이터 타입을 권장하는 대목.

회고와 배경

Werner Vogels, Amazon DynamoDB: a Fast and Scalable NoSQL Database Service Designed for Internet Scale Applications, 2012. 2004년 연말 쇼핑 시즌 장애를 직접 언급한 글.
Werner Vogels, A Decade of Dynamo, 2017. 오라클 엔터프라이즈 에디션의 한계와 연산의 70퍼센트가 키-값 조회였다는 발견.

시스템 설계 - 레이트 리미터 Ep.1 알고리즘 해부

A Note on Graphics

이 글에 사용된 모든 다이어그램과 일러스트 이미지는 개념의 시각화를 위해 생성형 AI 도구를 활용해 제작되었습니다.

저작자표시 비영리 변경금지 (새창열림)

'시스템 디자인' 카테고리의 다른 글

[시스템 설계 - 레이트 리미터] Ep.2 방패의 설계도: 트래픽 폭주 속에서 무엇을, 어디서 막을 것인가 (0)	2026.07.28
[시스템 설계 - 레이트 리미터] Ep.1 여섯 개 알고리즘 해부: Redis 명령어까지 내려가서 다 뜯어보기 (0)	2026.07.28

[시스템 설계 - DynamoDB] Ep.3 지운 물건이 되살아납니다: 다이나모 아키텍처 15년과 복잡성 보존의 법칙