복제(상): 흔히 쓰는 복제 모델과 분산 시스템의 어려움

메이퇀 기술 블로그에 仕禄이 쓴 “Replication（上）：常见复制模型&分布式系统挑战”(2021-08-25)를 절 순서대로 따라가며 정리했습니다. 仕禄의 글은 『데이터 중심 애플리케이션 설계』(DDIA)를 뼈대로 흔한 복제 모델 셋을 소개하고 분산 시스템이 왜 어려운지를 이야기한 뒤 Kafka의 동작에 대응시킵니다. 절 제목과 순서는 원문을 따랐습니다. 회사 사례와 PostgreSQL로 직접 잰 값은 해당하는 절 안에 넣었고 원문이 공식 문서나 실행 결과와 다른 곳은 그 자리에서 고쳤습니다.

원문의 결론은 이렇습니다.

1. 데이터를 여러 서버에 복제하는 이유는 확장성, 고가용성, 지역별로 같은 사용자 경험을 주는 것입니다. 복제의 목표는 복제본들의 데이터를 일치시키는 것인데 성능과 복잡성 때문에 얼마나 강하게 일치시킬지를 따로 정해야 합니다.
2. 흔한 복제 모델은 리더 한 대가 쓰기를 받는 주종, 다중 리더, 리더 없는 복제 셋이고 모델마다 쓰임새와 장단점이 다릅니다.
3. 복제 모델만으로는 일관성이 정해지지 않습니다. 분산 시스템에는 부분 실패, 믿을 수 없는 네트워크, 서로 다른 시계가 있고 이 문제는 다음 편의 트랜잭션, 합의, 일관성이 받아 줍니다.

직접 잰 값과 확인한 사실로 보탠 것은 다음과 같습니다.

• 복제 링크에 편도 5ms 지연을 두면 비동기 커밋은 0.26ms였고 팔로워(리더의 데이터를 받아 가는 복제본)를 기다리는 커밋은 12.7ms였습니다.
• 링크가 편도 5ms 늦을 때 비동기 팔로워에서 쓴 직후에 읽으면 6,000회 중 6,000회가 실패했습니다. 팔로워의 적용이 20ms 밀릴 때는 디스크까지 기다리는 수준도 전부 실패했고 적용까지 기다리는 수준만 0회였습니다.
• GitHub은 43초의 단절 뒤 자동 승격으로 양쪽에 서로 없는 쓰기가 생겨 24시간 11분 동안 서비스가 저하됐습니다. Meta는 승격을 복제 로그에 태우는 합의 알고리즘을 MySQL에 넣어 장애 조치를 20~40초에서 보통 2초 안으로 줄였습니다.
• 원문이 적은 쿼럼(성공으로 치려고 기다리는 최소 응답 수)의 고장 허용 식은 N이 홀수일 때만 맞고 4대는 3대와 같이 한 대만 견딥니다. 복제본 모두가 받아 간 위치(하이 워터마크)로 자르는 Kafka의 복구는 0.11.0부터 리더가 바뀔 때마다 올라가는 번호(리더 에포크) 기준으로 바뀌었습니다.

하편은 이 블로그의 복제(하): 트랜잭션, 일관성, 합의에 있습니다. 구현과 격리 수준은 아래 글에 있습니다.

소개

복제를 쓰는 목적

분산 시스템은 데이터를 여러 서버에 흩어 둡니다. 원문은 그 이유를 셋으로 듭니다.

• 확장성. 읽기와 쓰기 부하가 커서 한 대가 감당하지 못하면 데이터를 여러 대에 나눠 부하를 분산하고 수평으로 늘릴 수 있습니다.
• 내결함성과 고가용성. 서버 한 대가 고장 나는 일은 늘 일어나므로 그 뒤에도 시스템이 돌아가야 합니다. 데이터가 여러 대에 중복돼 있으면 고장 난 서버의 일을 다른 서버가 곧바로 이어받습니다.
• 일관된 사용자 경험. 클라이언트가 여러 지역에 흩어져 있으면 서비스를 여러 지역에 두어 사용자가 가까운 곳에서 필요한 데이터를 받게 합니다.

데이터를 여러 서버에 두는 방법은 둘입니다. 하나는 데이터를 조각내 서버마다 일부만 두는 분할이고 Kafka는 이 조각을 파티션, 다른 시스템은 샤드라고 부릅니다. 다른 하나는 같은 데이터를 통째로 여러 벌 두는 복제이고 그 한 벌을 Kafka에서는 레플리카라고 합니다. 실제 시스템은 두 방법을 함께 써서 한 서버에 서로 다른 조각의 복제본 여럿이 놓입니다. 이 글은 복제만 다루고 분할은 다루지 않습니다.

복제가 맞추려는 것은 복제본들의 데이터가 같은 상태입니다. 여기서 “같다”는 말의 뜻은 여럿입니다. 복제본마다 어느 순간에나 완전히 같다는 뜻일 수도 있고 클라이언트들이 어느 때에 읽어도 같은 값을 본다는 뜻일 수도 있습니다. 세기도 갈립니다. 언제나 모든 클라이언트가 최신 값을 읽어야 하는 경우가 있고 한동안 서로 다른 값을 보다가 시간이 지나면 같아지면 되는 경우가 있습니다. 원문은 일관성이라는 말을 다음 편에서 문맥별로 따로 풀겠다고 합니다.

그렇다면 복제본이 언제나 같도록 하면 되지 않느냐는 의문이 남습니다. 원문은 성능과 복잡성 두 가지로 답합니다. 성능 쪽 답은 이렇습니다. 복제의 목적에는 고가용성 말고도 지연 단축과 부하 분산이 있어서 일치만 고집하면 잃는 것이 얻는 것을 넘을 수 있습니다. 복잡성은 분산 시스템의 불확실성에서 나옵니다. 노드끼리는 믿기 어려운 네트워크로 통신하고 하나의 시스템 시간과 메모리 주소를 공유하지 못합니다(뒤의 분산 시스템의 어려움 절에서 자세히 다룹니다). 그래서 한 서버에서는 쉬운 일이 분산 시스템에서는 몹시 어려워지고 복제본의 데이터가 정말 일치할 수 있는지 의심이 들 정도입니다. 이 불확실성을 다루는 알고리즘은 다음 편에서 분석한다고 원문은 예고합니다.

시리즈 개요

원문은 시리즈를 상편과 하편으로 나눕니다. 상편은 흔한 복제 모델 셋을 소개한 뒤 분산 시스템의 어려움을 보여 주어 분산 시스템에서 일어나는 예상 밖의 고장을 감각으로 익히게 하는 글입니다. 하편은 상편에서 꺼낸 문제를 트랜잭션, 분산 합의 알고리즘, 일관성으로 풀고 셋의 관계를 설명한 뒤 분산 시스템에서 데이터의 일관성을 어떻게 지키는지 보이고 분산 알고리즘의 정확성을 검증하는 도구까지 소개한다고 예고합니다.

이 블로그의 하편도 원문 하편의 순서를 따르고 etcd의 선형 읽기와 리더 교체, PostgreSQL의 2PC, Kafka 트랜잭션은 직접 실행해 쟀습니다.

데이터 복제 모델

가장 흔한 복제 모델은 주종, 다중 리더, 리더 없는 복제 세 가지입니다.

가장 단순한 복제 모델: 주종 모델

소개

복제를 가장 직관적으로 하는 방법은 복제본에 역할을 나누는 것입니다. 한 복제본이 리더가 되어 데이터를 자기 로컬에 저장한 뒤 그 변경을 로그나 변경 스트림으로 나머지 복제본인 팔로워(원문은 노드라고도 부릅니다)에게 보냅니다. 이 모델에서 쓰기 요청은 전부 리더로 가고 읽기 요청은 리더가 받아도 팔로워가 받아도 됩니다. 읽기는 확장되고 부하도 나뉩니다. 데이터가 네트워크로 건너가는 시간을 무시할 수 없어서 클라이언트에게 보이는 일관성은 얼마간 양보해야 합니다.

리더가 쓴 뒤 팔로워에 닿기까지는 시간 창이 있고 이 창 안에서는 무슨 일이든 일어날 수 있습니다. 클라이언트에게 쓰기가 끝났다고 언제 답하느냐가 다른 클라이언트가 어떤 값을 읽을 수 있는지를 정합니다. 데이터에 리더 한 대와 팔로워 한 대가 있다고 해 봅니다. 리더가 저장하자마자 성공을 돌려주면 비동기 복제입니다. 데이터가 팔로워까지 가서 확인을 받은 뒤에 성공을 돌려주면 동기 복제입니다. 시스템이 정상으로 돌아가는 상황에서도 비동기이고 팔로워가 읽기를 맡으면 문제가 생깁니다. reader1과 reader2가 쓰기 성공을 받자마자 동시에 읽기를 보내면 두 reader가 서로 다른 값을 읽을 수 있습니다.

이를 피하는 길은 두 가지입니다. 첫째는 클라이언트가 리더에서만 읽는 것입니다. 정상일 때는 모든 클라이언트가 같은 값을 읽고 Kafka가 지금 이렇게 합니다. 둘째는 동기 복제입니다. 순수한 동기 복제에서는 복제본이 여럿일 때 어느 한 복제본의 노드만 고장 나도 쓰기가 막히고 쓰기마다 모든 노드의 확인을 기다려야 해서 복제본이 많으면 처리량이 크게 떨어집니다. 비동기 복제로 두고 리더만 읽게 하는 경우에도 리더가 고장 나 전환되면 같은 불일치가 생깁니다.

많은 시스템이 이 결정을 사용자에게 넘깁니다. Kafka는 클라이언트의 acks 설정으로 동기와 비동기의 의미를 고르게 하고 ISR(리더를 따라잡은 팔로워의 집합) 장치를 두어 ISR 안의 복제본만 확인하면 되게 했습니다. 여러 고장으로 ISR에서 빠진 노드는 클라이언트가 기다리지 않아도 되므로 시스템의 내결함성이 올라갑니다. 원문은 지금 Kafka가 팔로워에서 읽는 기능을 제공하지 않는다고 적었습니다. 실제로는 원문보다 먼저 나온 2.4.0에 KIP-392로 들어와 있습니다. 이 기능의 동기는 데이터센터를 넘나드는 비싼 트래픽을 줄여 가까운 복제본에서 읽게 하는 것입니다. 이렇게 일관성과 가용성의 균형을 사용자가 고를 수 있습니다.

쓰기 하나는 리더의 디스크에 쓰이고 네트워크를 건너 팔로워에 도착하고 팔로워의 디스크에 쓰이고 팔로워에 적용됩니다. 성공이라고 답하는 시점을 이 길의 어디에 두느냐가 위 설명의 선택입니다.

일찍 답하면 빠르지만 리더가 죽을 때 그 쓰기가 사라질 수 있습니다. 늦게 답하면 쓰기는 안전해도 팔로워가 느리거나 죽었을 때 쓰기가 함께 느려지거나 멈춥니다. 제품마다 이 지점을 고르는 설정이 있습니다.

편도 5ms 링크에서 팔로워를 기다리면 커밋 지연이 0.26ms에서 12.7ms가 됐습니다. PostgreSQL 16의 리더 한 대와 동기 팔로워 한 대로 쟀고 수준마다 커밋을 2,000번씩 세 차례 하여 커밋 지연의 중앙값을 적었습니다.

비동기(local)는 링크가 느려져도 0.3ms 안쪽입니다. 팔로워를 기다리는 세 수준은 12.6~12.7ms가 됐습니다. 링크의 왕복 10ms에 2ms 남짓이 더 붙은 값이고 더 붙은 몫이 어디서 왔는지는 가르지 않았습니다. 팔로워의 적용이 밀리면 적용까지 기다리는 remote_apply만 그 시간을 떠안습니다.

회사들은 업무마다 다른 지점을 골랐습니다. 메이퇀은 2017년 글에서 MySQL을 비동기 복제로 운영하며 핵심 업무 일부에만 반동기 복제를 쓴다고 적었습니다. 그렇게 해도 95% 이상의 상황에서 데이터를 잃지 않는 정도이고 극단적인 경우에는 강한 일관성을 보장하지 못한다고 덧붙였습니다.

텐센트의 TDSQL 논문은 반동기 복제가 금융 업무의 요구를 채우지 못했다고 설명합니다. 팔로워가 정해 둔 시간 안에 답하지 않으면 비동기로 내려가서 일관성 문제가 남고 데이터센터 사이의 지연과 흔들림이 크면 요청 지연도 튄다는 이유입니다. 그래서 과반의 확인을 기다리는 방식으로 바꿨는데 비동기에 견줘 처리량이 절반이 되는 경우가 많았다고 합니다. 논문은 스레드 구조를 고쳐 이 차이를 비동기에 견줄 만큼 줄였다고도 적었고 그 대목에 수치는 없습니다.

Kafka의 acks=all이 기다리는 것은 지금 동기화된 복제본 집합입니다. 공식 문서는 이 집합을 “the full set of in-sync replicas”라고 씁니다. 동기화된 집합이 리더 하나로 줄면 리더 혼자 쓴 것만으로 성공이라고 답합니다. 동기화된 집합이 몇 개까지 줄어도 쓰기를 받을지는 min.insync.replicas가 정합니다. 그래서 문서는 복제본 3개에 min.insync.replicas를 2로 두고 acks=all로 쓰는 구성을 예로 듭니다.

주종 모델에 필요한 능력

팔로워를 새로 늘리는 방법은 시스템마다 다릅니다. Kafka는 새 복제본을 할당하고 그 복제본이 리더에서 데이터를 따라잡으며 동기화합니다. 데이터베이스는 스냅숏과 증분을 조합합니다.

1. 어느 시점의 일관된 스냅숏을 만듭니다.
2. 스냅숏을 새 팔로워에 복사합니다.
3. 새 팔로워가 리더에 연결해 스냅숏 시점 이후에 생긴 변경 로그를 모두 요청합니다.
4. 받은 로그를 자기 복제본에 적용합니다. 이 과정을 따라잡기라고 합니다.
5. 필요하면 1~4를 여러 번 되풀이합니다.

팔로워의 실패는 복구가 단순해서 대개 따라잡기로 해결합니다. 데이터베이스의 팔로워는 죽기 전에 마지막으로 실행한 트랜잭션을 알고 있으므로 리더에 연결해 그 뒤의 변경을 전부 받아 로컬 기록에 적용하면 따라잡기가 끝납니다.

Kafka의 복구도 비슷합니다. Kafka는 실행 중에 체크포인트를 주기적으로 디스크 파일에 씁니다. 파일은 둘입니다. recovery-point-offset-checkpoint에는 디스크에 쓴 오프셋을 적고 replication-offset-checkpoint에는 하이 워터마크(HW, 동기화된 복제본 모두가 받아 간 위치)를 적으며 ReplicaManager가 씁니다. 다음에 복구할 때 브로커가 두 파일을 읽습니다. 로컬 디스크에 기록됐어도 커밋되지 않은 로그가 있을 수 있어서 원문은 먼저 HW가 가리키는 오프셋까지 잘라내고(Truncate) 그 오프셋부터 리더 복제본에서 가져와 리더를 따라잡으면 ISR 집합에 들어간다고 설명합니다.

원문의 이 설명은 지금의 Kafka와 다릅니다. 하이 워터마크 위치로 자르면 두 가지 문제가 있었습니다. 팔로워가 따라잡기 전에 리더가 되면 이미 커밋된 메시지가 잘려 사라질 수 있고 두 브로커가 함께 죽었다 올라오면 복제본끼리 다른 로그 계보를 가져 갈라질 수 있습니다. 그래서 KIP-101이 0.11.0에서 자를 지점을 리더 에포크(리더가 바뀔 때마다 올라가는 번호) 기준으로 바꿨습니다. 원문이 설명하는 HW 기준 복구는 그 이전의 방식입니다.

리더가 실패하면 조금 복잡하고 전환은 세 단계로 이뤄집니다.

첫째 단계는 리더의 실패를 확인하는 것입니다. 실패의 원인은 다양해서 대부분의 시스템은 타임아웃으로 판정합니다. 노드끼리 하트비트를 주고받다가 어떤 노드가 오랫동안 응답이 없으면 실패로 봅니다. Kafka는 ZooKeeper(ZK)와의 세션으로 하트비트를 유지합니다. 시작할 때 ZK에 임시 노드를 등록하고 이후 세션을 유지하다가 Kafka 노드가 고장 나(원문은 수동적 이탈, 곧 일부러 서비스를 내린 경우를 뺀 것이라고 한정합니다) 세션 하트비트가 시간 초과되면 ZK의 임시 노드가 사라집니다. 이를 컨트롤러가 감지해 노드 실패로 판정합니다. 이것은 2021년 글이 쓰던 Kafka의 설명입니다. 지금은 Kafka 자체의 메타데이터 쿼럼인 KRaft가 그 일을 맡습니다. KIP-833이 3.3.0에서 새 클러스터에 한해 KRaft를 프로덕션 준비 상태로 선언했고 2025년 3월의 Kafka 4.0은 ZooKeeper 없이만 동작하는 첫 주요 릴리스입니다.

둘째 단계는 새 리더를 뽑는 것입니다. 투표로 뽑을 수도 있고(보통 합의 알고리즘이 이 일을 합니다) 특정 컴포넌트가 한 노드를 새 리더로 지정할 수도 있습니다(Kafka의 컨트롤러). 뽑거나 지정할 때는 새 리더와 옛 리더의 차이를 가능한 한 작게 해야 데이터 유실 위험이 줄어듭니다. 모든 노드가 새 리더를 인정하게 하는 것은 대표적인 합의 문제입니다. 합의는 노드 몇 개가 하나의 안건에 의견을 모으는 일이고 다음 편에서 중점적으로 다룹니다.

셋째 단계는 시스템을 재구성해 새 리더가 효력을 갖게 하는 것입니다. 클러스터의 메타데이터를 고쳐 바깥에 새 리더의 존재를 알리는 일로 이해하면 됩니다(Kafka는 컨트롤러가 메타데이터를 브로드캐스트합니다). 이후 옛 리더가 다시 떠도 자기를 리더로 여겨 쓰기를 받는 일이 없도록 해야 합니다.

세 단계가 분명해 보여도 실제로는 문제가 남습니다. 비동기 복제였다면 고장 전에 새 리더와 옛 리더의 데이터에 차이가 있습니다. 선출이 끝난 뒤 옛 리더가 곧 클러스터에 돌아오면 새 리더는 충돌하는 쓰기를 받을 수 있습니다. 이때는 셋째 단계를 아직 마치지 못해 옛 리더가 자기 역할이 바뀐 것을 모르고 새 리더에 데이터를 동기화하려 합니다. 보통은 옛 리더에서 복제를 마치지 못한 쓰기를 버리는데 이것이 데이터 유실이나 불일치를 낳을 수 있습니다. 원문의 예는 기본 키를 MySQL 자동 증가 ID로 쓰고 Redis를 캐시로 쓰는 구성입니다. 팔로워가 새 리더로 올라섰는데 그 팔로워의 자동 증가 카운터가 옛 리더보다 뒤처져 있으면 애플리케이션이 이미 쓴 ID를 다시 받을 수 있습니다. 그러면 Redis에서 같은 ID로 꺼내는 데이터와 어긋나서 다른 데이터가 노출되거나 사라집니다.

옛 리더가 어떤 고장으로 자기 역할이 바뀐 것을 영영 모르면 스플릿 브레인이 생깁니다. 두 노드가 동시에 데이터를 고치는데 충돌을 푸는 모듈이 설계에 없으면 데이터가 망가질 수 있습니다. 메이퇀의 2017년 글에 이런 사례가 있습니다. 서버 위의 스위치가 흔들려 리더에 닿지 못하자 승격 도구가 장애로 판정해 쓰기 주소를 새 리더로 옮겼습니다. 스위치가 돌아왔을 때 옛 리더에서 그 주소가 내려가지 않아 두 서버가 같은 주소를 가졌습니다. 메이퇀은 승격 도구가 같은 랙의 다른 서버들도 살펴보고 네트워크 고장인지 서버 고장인지 가르게 고쳤습니다.

타임아웃을 얼마로 잡을지도 어려운 문제입니다. 길면 서비스를 쓸 수 없는 시간이 늘고 짧으면 전환이 잦아집니다. 시스템이 이미 고부하인 상태에서 역할 전환이 잦으면 부하가 더 무거워집니다(원문은 팀 내부에서 Kafka 좀비 노드, 곧 서비스는 제 구실을 못 하는데 노드로는 남아 있는 브로커를 처리하는 로직을 이 경우로 듭니다).

2018년 10월 GitHub의 사후 분석에는 위 문제 가운데 데이터 격차와 타임아웃 판정의 어려움이 나옵니다. 광 장비 교체 작업으로 동부 데이터센터와 네트워크 허브 사이의 연결이 43초 동안 끊겼습니다. 승격을 맡은 도구는 동부를 볼 수 없게 되자 서부 데이터센터의 팔로워들을 리더로 올렸습니다.

동부에는 서부로 복제되지 못한 쓰기가 있었고 서부는 승격 뒤 새 쓰기를 받았습니다. GitHub은 이렇게 적었습니다.

Because the database clusters in both data centers now contained writes that were not present in the other data center, we were unable to fail the primary back over to the US East Coast data center safely.

가장 바쁜 클러스터 하나에서 서부로 복제되지 못한 쓰기는 954건이었습니다. GitHub은 복구 시간을 내주고 데이터를 맞추는 쪽을 택했고 서비스 저하는 24시간 11분 이어졌습니다. 뒤에 바꾼 것 가운데 하나로 승격 도구가 지역의 경계를 넘어 리더를 올리지 못하게 했습니다.

GitHub과 메이퇀의 사례에서는 데이터를 복제하는 경로와 승격을 결정하는 경로가 따로였습니다. Meta의 2023년 글이 이 구조를 직접 다룹니다. Meta의 MySQL은 반동기 복제로 데이터를 보냈고 승격과 장애 조치는 서버 밖의 Python 데몬들이 맡았습니다. 예외 상황을 덧대다 보니 이 자동화가 갈수록 복잡해졌다고 합니다. Meta는 승격과 구성원 변경을 데이터와 같은 복제 로그에 태우려고 Raft를 MySQL 안에 넣었습니다. 도입한 뒤 장애 조치가 20~40초에서 보통 2초 안으로 줄었고 쓰기 경로의 지연은 반동기 때와 같았습니다. 같은 글은 한계도 밝혔습니다.

while correctness was easier to reason with Raft, the Raft protocol in itself does not help much in the concern of availability.

Raft는 과반이 살아 있어야 쓰기를 받으므로 과반을 잃으면 멈춥니다.

메이퇀의 분산 키값 저장소 Cellar도 Raft로 옮겼습니다. 비동기 복제에서는 고장 난 노드를 뺄 때 아직 복제되지 못한 데이터를 잃었고 결제 같은 업무는 그 유실을 받아들일 수 없어서 Raft로 바꿨다고 밝혔습니다. 합의 알고리즘 가운데 Raft를 고른 이유로는 논문이 자세하고 성숙한 오픈소스 구현이 있어 개발 기간이 줄어든다는 점을 들었습니다.

Kafka도 앞에서 적은 대로 KRaft로 승격 결정을 자기 안의 합의로 옮겼습니다.

2020년 11월 Cloudflare의 장애에서 합의에 기댄 구조의 비용이 드러났습니다. 스위치 하나가 일부 패킷만 전달하는 상태가 되자 etcd 클러스터의 노드들이 서로 다른 것을 보게 됐고 리더 선출이 동률로 끝나기를 되풀이해 클러스터가 읽기 전용이 됐습니다. etcd에 건강 상태를 알리지 못한 데이터베이스 클러스터 둘에서 팔로워가 자동으로 승격됐습니다. 그 클러스터 관리 시스템에는 승격 뒤 팔로워를 전부 다시 만들어야 하는 결함이 있어서 읽기를 많이 받던 인증 데이터베이스의 리더가 부하를 혼자 떠안았고 API와 대시보드가 6시간 33분 동안 영향을 받았습니다.

메이퇀의 하편은 합의는 ZooKeeper나 etcd 같은 검증된 서비스에 맡기는 것이 가장 나을 수 있고 직접 만들어야 한다면 검증된 알고리즘을 쓰라고 권합니다. 맞는 권고이고 Cloudflare의 장애에서 보듯 맡긴 시스템이 멈출 때 무슨 일이 일어나는지도 설계에 들어가야 합니다.

합의로 리더를 뽑아도 물러난 줄 모르는 옛 리더가 읽기에 답할 수 있습니다. Raft 논문의 방법은 리더가 읽기에 답하기 전에 과반과 통신해 자기가 아직 리더인지 확인하는 것입니다. TiKV는 이 왕복을 줄이려고 리스를 씁니다. 리스는 정해 둔 시간 동안은 리더가 과반에 묻는 단계를 건너뛰고 읽기에 답해도 된다는 약속입니다. 선출 제한 시간이 10초이고 리스를 9초로 잡아서 다음 리더가 뽑힐 때에는 옛 리더의 리스가 끝나 있게 했습니다. 이 방식은 서버의 시계가 정해 둔 범위 안에서 흐른다는 가정에 기댑니다.

비동기 복제가 마주하는 주된 문제: 복제 지연

앞에서 보았듯 순수한 동기 복제는 한 대만 고장 나도 쓰기를 받지 못하고 노드가 많아질수록 처리량과 가용성이 크게 흔들립니다. 그래서 많은 시스템이 반동기나 비동기 복제로 가용성과 일관성 사이의 균형을 잡습니다.

비동기 복제에서는 쓰기가 리더에만 쓰이면 성공이 돌아갑니다. 데이터가 다른 복제본으로 퍼지는 동안 클라이언트가 읽으면 복제본마다 읽히는 값이 다를 수 있습니다. DDIA는 이 현상을 복제 지연(Replication Lag)이라고 부르고 이런 복제가 만드는 일관성을 통틀어 최종 일관성이라고 합니다. 일관성과 합의는 하편에서 중점적으로 다루고 아래 세 모양도 하편의 복제 지연 절에 다시 나옵니다. 원문은 미리 읽고 싶은 독자에게 DDIA의 “Problems with Replication Lag” 장을 권합니다.

복제본에서 읽으면 리더의 부하가 줄지만 팔로워가 아직 받지 못한 쓰기는 보이지 않습니다. 메이퇀의 하편은 사용자에게 보이는 모양을 셋으로 나눕니다.

쓴 직후 읽기를 PostgreSQL에서 재 보았습니다. 앞의 커밋 지연 실측과 같은 구성에서 리더에 행 하나를 넣고 커밋이 돌아오자마자 팔로워에서 그 행을 읽었습니다. 아래 표는 수준마다 6,000번 가운데 읽지 못한 횟수이고 세 조건 모두에서 0회였던 수준은 적용까지 기다리는 remote_apply뿐입니다.

비동기는 링크가 5ms만 늦어도 매번 실패했고 그 행은 중앙값 5.8ms 뒤에 보였습니다. 같은 기계 안에서도 6,000번 중 25번 실패했습니다.

편도 5ms 조건에서 remote_write와 on의 실패가 0인 것은 보장이 아닙니다. 실행 전에는 이 두 수준에서도 실패가 나올 것이라고 적어 두었는데 0회였습니다. 확인 응답이 5ms 링크를 되돌아가는 동안 팔로워가 적용을 끝냈기 때문입니다. 커밋이 돌아온 시각과 팔로워에서 그 행이 보인 시각을 따로 재 보니 두 수준에서 3,000번씩 모두 행이 먼저 보였고 그 간격은 중앙값 5.3ms, 가장 짧을 때 1.9ms였습니다. 적용을 20ms 늦춘 조건에서는 두 수준이 6,000번 모두 실패했습니다. PostgreSQL 문서도 remote_apply만 팔로워가 그 커밋을 적용해 팔로워의 쿼리에 보일 때까지 기다린다고 설명합니다.

회사들이 푼 방법은 포기한 것이 서로 다릅니다.

GitHub의 이전 규칙은 마지막 쓰기 뒤 5초 동안은 리더에서 읽는 것이었습니다. 복제 지연이 보통 1초 안쪽인데 5초를 기다리고 있었으므로 실제 지연을 재서 그만큼만 기다리게 바꿨습니다.

Shopify는 더 강한 방식도 검토했습니다. 쓰기의 식별자를 들고 다니며 그 쓰기를 받은 복제본에서만 읽는 방식입니다. 복제본마다 현재 위치를 보고하는 소프트웨어가 필요했고 자기들의 쓰임새에는 그 수준의 보장이 필요하지 않다고 판단해 접었다고 합니다.

다중 리더 복제

앞의 주종 모델에는 큰 약점이 있습니다. 쓰기가 전부 리더를 거치고 리더가 하나뿐이어서 성능 문제가 쉽게 생깁니다. 팔로워가 내결함성을 위한 여분은 되지만 쓰기 요청에 대해서는 이 복제 방식이 확장성을 주지 못합니다.

클라이언트가 여러 지역에서 오면 지역마다 느끼는 응답 시간의 차이도 아주 커집니다. 그래서 일부 시스템은 전통적인 주종 복제를 확장해 여러 리더가 동시에 쓰기를 받게 합니다. 리더가 쓰기를 받아 자기 팔로워에 동기화하는 것은 같고 다른 점은 이 리더가 다른 노드의 팔로워이기도 할 수 있다는 것입니다. 리더가 둘이면 각 리더가 쓰기를 받아 같은 데이터센터의 팔로워에 복제하고 다른 데이터센터에 있는 노드와도 데이터를 계속 동기화합니다. 각 리더가 다른 리더의 데이터와 클라이언트가 쓴 데이터를 함께 처리하므로 모델에 충돌 처리 모듈이 더해져야 하고 리더에 최종으로 쓰이는 데이터는 충돌 해소를 거쳐야 합니다.

쓰임새

다중 리더 복제는 대개 다중 데이터센터 재해 대비나 클라이언트의 가까운 접근을 위해 씁니다(흔히 멀티 리전 액티브-액티브라고 부르는 구성입니다). 같은 지역 안에서 다중 리더를 쓰는 것은 의미가 크지 않고 여러 지역이나 데이터센터에 배치할 때 주종 모델 대비 이점이 있습니다.

• 성능. 처리량에서는 전통적인 주종 모델의 쓰기가 모두 리더를 지나므로 리더에서 데이터를 분할해 부하를 나눌 수 없으면 병목이 생깁니다. 다중 리더에서는 같은 데이터의 부하도 나눠 처리량을 높일 수 있습니다. 지연에서는 리더가 여러 지역에 있으므로 지역이 다른 클라이언트도 가까운 데이터센터의 리더에 요청을 보내 비슷한 지연으로 읽고 쓸 수 있습니다.
• 데이터센터 장애 허용. 주종 모델에서 리더가 있는 데이터센터에 네트워크 장애가 나면 노드 전환을 한 번 거쳐야 트래픽이 다른 데이터센터로 넘어갑니다. 다중 리더에서는 새 데이터센터로 끊김 없이 넘어갈 수 있어 서비스 전체의 가용성이 올라갑니다.

바이트댄스의 그래프 데이터베이스 논문은 주종과 다중 리더를 섞은 구성을 소개합니다. 같은 지역 안에서는 주종으로 복제하고 지역 사이에는 지역마다 쓰기를 받습니다. 물리 시계를 그대로 쓸 수 없어서 하이브리드 논리 시계로 충돌을 풀고 복제본 사이에는 최종 일관성만 보장한다고 적었습니다.

지역 문제 말고도 재미있는 쓰임새가 있습니다. 네트워크가 끊긴 오프라인에서도 계속 일하는 경우입니다. 노트북의 노트나 메모 앱이 그렇습니다. 네트워크가 끊겼다고 쓰지 못하게 하면 안 되므로 로컬에서 계속 편집합니다. 네트워크에 다시 연결되면 편집한 내용이 원격 노드에 동기화됩니다. 로컬 앱을 복제본의 하나로 보면 이 복제본이 로컬의 변경 요청을 받고 연결된 뒤에 원격 리더로 동기화하는 셈입니다.

오프라인 클라이언트의 확장으로 여럿이 한 문서를 동시에 편집하는 경우를 봅니다. 각자 웹 클라이언트에서 편집하는 문서를 하나의 리더로 볼 수 있습니다. 메이퇀 내부 위키 시스템인 쉐청(学城)이 예입니다. 문서를 편집하면 오른쪽 위에 “누구누구도 협업 편집 중”이라는 표시가 뜨고 저장하면 시스템이 데이터를 로컬에 저장한 뒤 다른 리더로 복제하며 각자 자기 쪽의 충돌을 처리합니다. 문서가 갱신되면 쉐청이 알려 주고 사용자가 직접 눌러 내 로컬 리더의 데이터를 갱신해야 합니다. DDIA는 협업 편집이 데이터베이스 복제와 같지는 않아도 닮은 점이 많고 충돌을 처리해야 하는 점도 같다고 설명합니다.

충돌 해결

다중 리더 모델의 가장 큰 과제는 충돌을 푸는 것입니다.

충돌 실례

두 웹 클라이언트가 같은 항목을 서로 다른 값으로 각자 다른 리더에 쓰는 경우를 봅니다. 다중 리더가 비동기로 복제하므로 사용자는 자기 페이지에 쓰자마자 성공을 받습니다. 이 값을 다른 리더로 복제하려 할 때 문제가 생깁니다. 리더가 CAS(지금 값이 기대한 값일 때만 바꾸는 연산) 같은 방식으로 갱신한다고 하면 기대한 값이 이미 달라져 있으므로 갱신을 거절합니다. DDIA는 이런 충돌에 흔한 해결 방향 몇 가지를 줍니다.

해결 방향

첫째는 충돌 피하기입니다. 문제를 푸는 가장 근본적인 방법은 아예 일어나지 않게 하는 것입니다. 특정 데이터에 대한 요청이 한 노드에서만 일어나도록 애플리케이션 계층에서 보장하면 쓰기 충돌이라는 것이 없습니다. 협업 문서라면 사람마다 이름이 적힌 표의 자기 행에서만 편집하게 하여 수정 범위가 겹치지 않도록 할 수 있습니다.

둘째는 일관된 상태로 수렴시키는 것입니다. 제목을 고치는 경우처럼 충돌을 피할 수 없을 때도 푸는 방법은 필요합니다. 리더가 하나인 모드에서는 같은 필드에 여러 번 쓰면 마지막에 쓴 것이 최신입니다. ZooKeeper, Kafka 컨트롤러, Kafka 레플리카에는 에포크 같은 방식으로 지난 쓰기를 막는 장치가 있고 쓰기가 모두 한 노드를 지나므로 순서가 절대적입니다. 다중 리더에는 절대 순서가 없으므로 상대적인 순서를 정해 충돌이 결국 한 값으로 모이게 해야 하고 원문은 방법 셋을 듭니다.

• 쓰기마다 고유 ID(타임스탬프, 난수, UUID, 해시)를 주고 ID가 가장 높은 것을 최신 쓰기로 삼습니다. 타임스탬프를 쓰면 최후 기록 우선(LWW, Last Write Wins)이라고 부릅니다. 단순하고 널리 쓰이지만 분산 시스템은 기계 사이에 하나의 시스템 시간을 공유하지 못해서 시계 어긋남으로 데이터를 잃을 수 있습니다.
• 복제본마다 고유 ID를 주고 ID가 높은 복제본의 쓰기가 낮은 쪽을 이깁니다. 이 방법도 데이터를 잃습니다.
• 값을 이어 붙이거나 미리 정한 형식으로 충돌 정보를 남겨 두고 사용자가 해결하게 합니다.

셋째는 사용자가 직접 처리하는 것입니다. 읽거나 쓰기 전에 사용자가 충돌을 풀게 맡기는 예는 흔하고 원문은 GitHub을 이 방식의 예로 듭니다.

여기서는 충돌의 예를 몇 가지만 들었습니다. 무엇을 충돌로 볼지는 미묘한 문제여서 DDIA 7장이 더 다루고 하편에서도 이 문제가 나옵니다.

처리 세부

DDIA는 복제 장을 마무리하면서 충돌 처리를 더 자세히 설명합니다. 충돌이 생기는 까닭은 두 사건의 선후를 모르는데 둘이 같은 대상을 다루기 때문입니다(둘 다 어떤 값을 설정하는 경우). 여기서 사건의 선후를 판단하는 방법이 두 가지 나옵니다.

첫째 방법은 사건의 순서를 직접 지정하는 것입니다. 가장 직관적인 생각은 두 요청 가운데 더 새 것을 취하는 것입니다. 이때 “최신”의 정의가 문제인데 가장 쉬운 방법은 타임스탬프이고 이 알고리즘이 LWW입니다.

그러나 분산 시스템에는 통일된 시스템 시계가 없어서 기계마다 찍힌 타임스탬프가 정확히 동기화된다고 보장할 수 없고 그러면 데이터를 잃을 수 있습니다. 덮어쓰기이기 때문에 중간 값이 남지 않을 수도 있어서 최종 상태가 일관되지 않거나 데이터가 사라지기도 합니다. 캐시 시스템에서는 덮어쓰기도 괜찮아 보이고 이 단순한 알고리즘으로 충돌을 한 값으로 모으면 됩니다. 데이터 일관성 요구가 높다면 위험이 따르며 데이터가 한 번 쓰이면 다시 바뀌지 않는 경우만 예외입니다.

둘째 방법은 사건 자체에서 인과와 동시성을 추정하는 것입니다. 순서를 직접 지정하는 방식은 지나치게 자의적입니다. 사건 사이에 인과 관계가 있다면 그것으로 순서를 알 수 있고 그래도 안 될 때 지정하면 되지 않을까요.

DDIA의 다중 리더 예를 봅니다. ClientA가 Leader1에 x=1을 넣는 데이터를 추가하고 Leader1이 비동기로 변경 로그를 다른 리더에 보냅니다. 복제 도중에 ClientB가 Leader3에 키 x의 값을 Value=Value+1로 바꾸는 갱신을 보냅니다. 이 예가 말하려는 것은 update 로그가 insert 로그보다 먼저 Leader2에 도착해서 갱신할 키가 없는 경우입니다. 두 사건은 서로 이어져 있고 DDIA는 이런 관계를 의존 관계 또는 happens-before라고 부릅니다.

JVM 메모리 모델(JMM)에서 이 말을 들어 본 독자도 있을 것입니다. JMM의 happens-before도 여러 스레드가 일하는 선후 관계를 나타냅니다. 스레드의 일과 클라이언트의 요청은 모두 데이터에 대한 작업이고 스레드와 클라이언트는 모두 실행 주체입니다. 다른 점은 한쪽이 로컬 메모리를, 다른 쪽이 네트워크 너머 원격의 메모리를 고친다는 것뿐이어서 두 happens-before는 본질적으로 하나입니다. 모두 사건의 선후를 설명하려고 만들어진 말입니다.

DDIA는 이런 사건을 탐지하는 알고리즘을 장바구니 예로 설명합니다. 원문은 식당 QR 주문으로 바꿔 이렇게 보여 줍니다. 두 클라이언트가 동시에 장바구니에 물건을 넣고 데이터베이스에는 복제본이 하나뿐이라고 가정한 것입니다.

이 예에서 사건의 인과를 사건 자체로 정하는 과정을 보았습니다. 책은 이를 더 추상화해 세 단계로 정리합니다.

• 서버는 키마다 버전 번호를 두고 새 값이 쓰일 때마다 버전을 올려 새 버전과 쓴 값을 함께 저장합니다.
• 클라이언트가 키를 쓸 때 쓰기 요청에 앞서 읽은 버전 번호를 넣고 보내는 값은 앞서 읽은 값과 새 값의 조합입니다. 쓰기의 응답도 현재 모든 값을 돌려주므로 한 단계씩 이어 붙일 수 있습니다.
• 서버가 특정 버전 번호가 달린 쓰기를 받으면 그 버전 번호 이하의 값을 모두 덮어쓰고 요청의 버전 번호보다 높은 값은 현재 쓰기와 동시에 일어난 것이므로 남깁니다.

하편은 이 장바구니 예를 되짚으며 이런 방식이 버전 벡터와 비슷하다고 봅니다. 이 알고리즘으로 인과가 있는 사건과 동시 사건을 가려낼 수 있습니다. 동시 사건은 위에서 말한 원칙대로 합쳐야 하고 LWW를 쓰면 여전히 데이터를 잃을 수 있습니다. 그래서 서버 프로그램의 병합 로직에서 따로 해 줄 일이 있습니다.

장바구니라면 새 값과 옛 값을 합치는 것이 합리적이고 최종 값은 [우유, 계란, 밀가루, 햄, 베이컨]이 됩니다. 문제는 사용자가 한 항목을 지웠을 때입니다. 합집합을 하면 지운 항목이 결과에 다시 나타나 기대와 어긋납니다. 그래서 삭제를 표시하는 표지를 두어 합칠 때 그 항목을 걷어 낼 수 있게 하고 책은 이 표지를 묘비(Tombstone)라고 부릅니다. Dynamo가 같은 문제를 장바구니에서 풀어 낸 방식은 리더 없는 복제 절에 적었습니다.

리더 없는 복제

앞의 복제 모델은 모두 리더와 팔로워의 역할이 분명했습니다. 리더가 데이터를 팔로워로 복제하고 모든 쓰기의 순서를 리더가 통제했습니다. 어떤 시스템은 이 생각을 아예 버리고 리더를 없앴습니다. 복제본 어느 것이나 클라이언트의 쓰기를 직접 받을 수 있고 시스템에 따라서는 코디네이터가 클라이언트를 대신해 씁니다(Group Commit이 예입니다. 한 스레드가 모든 클라이언트의 요청을 모아 한꺼번에 보냅니다). 다중 리더와 달리 코디네이터는 쓰기 순서를 통제하지 않고 이 제약의 차이가 시스템을 쓰는 방식에 곧바로 영향을 줍니다.

Dynamo는 쓰기를 언제나 받는 저장소를 목표로 리더 없는 방식을 골랐습니다. 논문은 장바구니에 담기를 거절하면 고객 경험이 나빠진다는 이유를 들었고 이 목표를 “always writeable”이라고 불렀습니다. 그 대가로 충돌은 읽을 때 풀고 장바구니에서는 갈라진 판들을 합칩니다. 논문은 이렇게 합치면 담은 물건은 사라지지 않고 지운 물건이 되살아날 수 있다고 적었습니다.

노드 실패 처리

복제본이 셋인 데이터 시스템에서 하나가 쓸 수 없게 됐다고 해 봅니다. 주종 모델에서는 그 하나가 마침 리더이면 노드 전환을 해야 서비스를 이어 가지만 리더 없는 모델에는 이 단계가 없습니다. 복제본 셋 가운데 Replica3이 어느 순간 서비스를 못 하게 되고 사용자는 나머지 두 복제본에서 쓰기 성공 확인을 받으면 성공으로 봅니다. 쓸 수 없는 복제본은 무시해도 됩니다. 실패했던 노드가 돌아와 다시 읽기와 쓰기를 받으면 이 복제본에서 읽는 클라이언트는 낡은 값을 받습니다.

이를 풀려고 클라이언트는 세 복제본 모두에 요청합니다. 응답이 서로 다를 수 있고 앞에서 본 동시 쓰기 탐지 방식처럼 버전 번호 비슷한 것으로 값의 신구를 구분합니다. 복구된 복제본이 계속 다른 복제본보다 뒤처져 있어서는 안 됩니다. 일관성의 의미가 깨지기 때문이고 그래서 장치가 필요합니다. 방법은 두 가지입니다.

• 읽기 복구. 클라이언트가 여러 복제본을 병렬로 읽다가 낡은 값을 발견하면 새 값을 낡은 복제본에 써서 따라잡게 합니다.
• 반엔트로피 질의. 일부 시스템은 복제본이 시작된 뒤 백그라운드에서 복제본 사이의 차이를 계속 찾아 자기 복제본에 씁니다. 주종 복제와 달리 쓰기 순서는 보장되지 않으며 눈에 띄는 복제 지연이 생길 수 있습니다.

읽기와 쓰기 쿼럼

위 예에서 보듯 이 복제 방식에서는 복제본 하나만 읽어서는 최신 값을 읽는다고 보장할 수 없습니다. 그렇다면 쓸 때 몇 개에 쓰고 읽을 때 몇 개를 읽어야 할까요. 핵심은 쓴 복제본과 읽은 복제본이 겹치게 하는 것이고 그러면 새 값을 읽는다고 보장할 수 있습니다.

공식은 W + R > N입니다. N은 복제본의 수이고 W는 한 번에 병렬로 쓰는 노드의 수, R은 한 번에 읽는 노드의 수입니다. 쓰기에 w개, 읽기에 r개의 응답을 기다린다고 할 때 읽은 집합과 쓴 집합이 적어도 하나 겹친다는 뜻이고 이 최소 응답 수를 쿼럼이라고 합니다. Dynamo 논문의 문장으로는 “Setting R and W such that R + W > N yields a quorum-like system”입니다. 공식은 단순해 보여도 설계에 대한 생각이 담겨 있습니다.

• 일반적인 설정은 w = r = ⌈(N+1)/2⌉, 곧 과반입니다.
• w, r, N의 관계가 몇 개의 노드 실패까지 견디는지를 정합니다. N=3, w=2, r=2이면 1개의 노드 고장을 견딥니다. N=5, w=3, r=3이면 2개를 견딥니다.
• 실제 구현에서는 보통 데이터를 모든 노드에 보내고 모든 노드에서 읽으며 w와 r은 몇 개 노드의 쓰기 확인 또는 읽기 확인을 기다릴지를 정합니다.

원문은 과반 쿼럼에서 N개의 노드가 ⌈(N+1)/2⌉−1개의 고장을 견딘다고 일반식으로 적었는데 이 식은 N이 홀수일 때만 맞습니다.

견디는 고장 수는 N에서 과반을 뺀 값, 곧 ⌊(N−1)/2⌋입니다. 4대는 w=r=3이어서 두 대가 죽으면 남은 둘로 쓰기도 읽기도 3개를 채울 수 없고 3대와 똑같이 한 대의 고장만 견딥니다.

서버 수만 세면 같은 가용 영역의 서버들이 함께 죽는다는 사실을 놓칩니다. Aurora 논문은 가용 영역 하나가 죽은 상태에서 다른 서버 한 대만 더 죽어도 쿼럼을 잃기 때문에 3벌에 과반 2로는 모자란다고 봤습니다. 그래서 가용 영역 셋에 두 벌씩 6벌을 두고 쓰기는 4, 읽기는 3의 응답을 기다립니다. 가용 영역 하나와 서버 한 대를 더 잃어도 읽을 수 있고 아무 두 대를 잃어도 쓸 수 있습니다.

견디는 고장 수를 말하는 수치에는 어떤 고장을 가정했는지가 따라붙고 OceanBase 논문도 그렇습니다. 복구 시점 목표 0과 복구 시간 목표 30초 미만은 소수의 노드가 고장 났을 때의 값입니다.

쿼럼 일관성의 한계

• 쿼럼이 반드시 과반일 필요는 없습니다. 필요한 것은 읽는 복제본과 쓰는 복제본이 겹치는 것이고 읽기와 쓰기의 가용성 요구에 맞춰 설정을 고를 수 있습니다.
• 강한 일관성이 필요 없는 시스템은 w + r ≤ N으로 설정할 수 있습니다. 더 적은 노드만 기다려도 반환되므로 낡은 값을 읽을 수 있는 만큼 가용성이 크게 올라갑니다. 네트워크에 큰 장애가 났을 때 쿼럼을 못 채워 오류를 돌려주는 경우가 줄고 시스템이 계속 돌 가능성이 커집니다.
• w + r > N이어도 경계 문제 때문에 일관성 문제가 생깁니다.
  • 느슨한 쿼럼(Sloppy Quorum)에서는 쓰는 w와 읽는 r이 전혀 겹치지 않을 수 있어 최신 데이터를 보장하지 못합니다. Dynamo가 이렇게 합니다. 원래 맡기로 한 노드가 죽어 있으면 살아 있는 다른 노드가 대신 받았다가 나중에 넘겨줍니다.
  • 두 쓰기가 동시에 일어나면 충돌이 그대로 있고 합칠 때 LWW를 쓰면 데이터를 잃을 수 있습니다. 어느 쪽이 남을지를 따로 정해야 합니다.
  • 쓰기와 읽기가 동시에 일어나면 읽기가 새 값을 받는다고 보장할 수 없습니다. 복제에는 지연이 있기 때문입니다(앞의 복제 창).
  • 일부 복제본에서는 쓰기가 성공하고 다른 복제본에서는 실패하며(디스크가 가득 찬 경우) 성공한 수가 w에 못 미치면 성공한 복제본의 데이터는 롤백되지 않습니다. 쓰기가 실패로 끝났어도 뒤에 새 값이 읽힐 수 있다는 뜻입니다.

쿼럼 복제는 새 값을 읽게 해 줄 것처럼 보여도 최종 일관성에 그칠 수 있고 여전히 합의 알고리즘의 도움이 필요합니다.

이 장의 소결

여기까지 흔한 복제 모델을 모두 보았고 모델마다 쓰임새와 장단점이 있습니다. 쓰기를 받는 곳의 수로 정리하면 다음과 같습니다.

복제 모델만으로는 데이터 일관성에 한참 못 미친다는 점도 분명합니다. 분산 시스템에는 불확실성이 너무 많아서 이런 예상 밖의 문제와 맞서려면 뒤에 나올 트랜잭션과 합의 알고리즘의 도움이 필요합니다.

그 문제가 구체적으로 무엇이고 단일 서버와 비교해 어떤 점이 특이한지는 다음 장에서 분산 시스템의 대표적인 어려움(Trouble)으로 먼저 봅니다. 원문은 독자가 잠시 작은 “절망”을 느끼게 한 뒤 답은 다음 편에서 밝히겠다고 합니다.

분산 시스템의 어려움

이 장은 단순해 보이는 문제가 분산 시스템에서 왜 아주 복잡해지는지 보여 줍니다. 원문은 이 장이 이상한 현상을 모은 것이고 복잡한 추론이나 증명이 없어서 가볍게 읽을 수 있기를 바란다고 적었습니다.

부분 실패

부분 실패는 분산 시스템에만 있는 말입니다. 현실의 예부터 봅니다. 사장이 서류 한 묶음을 처리해야 하는데 한 사람이 하면 열흘이 걸립니다. 사장은 느리다고 생각해 열 사람에게 맡기면 하루에 끝나리라 계산하고 상사에게 하루 안에 끝내겠다고 장담합니다. 열 사람을 불러 일을 나눠 주고 단체 채팅방을 만들어 한 시간마다 진행 상황을 보고하게 하며 저녁 5시 전에 이메일로 최종 결과를 내라고 강조합니다. 사장은 차를 마시러 갔는데 현실은 기대와 달랐습니다.

한 사람은 집의 신호가 아주 나빠서 세 시간 치 진행 보고만 겨우 올렸고 사장이 채팅방에서 물어도 답이 없었으며 결과도 제출하지 못했습니다. 다른 한 사람은 집의 시계가 오래 배터리를 갈지 않아 오후 4시에 멈춰 있었습니다. 시계를 두 번 봐도 4시라서 급할 것이 없다고 여기고 중간에 영화까지 보면서 일을 끝내 제출했습니다. 한 시간 일찍 냈으니 칭찬받겠다고 생각했지만 실제로는 이미 저녁 8시였습니다. 또 한 사람은 전날 잠을 못 자서 효율이 아주 낮았고 강도 높은 일을 더 할 수도 없었습니다. 저녁 5시가 되었을 때 맡은 일을 끝낸 사람은 일곱 명뿐이었습니다.

원문은 이 예가 딱 맞지는 않아도 분산 시스템 특유의 문제를 대체로 설명한다고 봅니다. 분산 시스템에서는 온갖 예상 밖의 고장을 만납니다. 집에 신호가 없는 것은 네트워크 고장이고 아무리 불러도 대답이 없거나 끊겼다 이어졌다 하며 대답합니다. 각자 자기 집 시계를 보므로 “5시까지 제출”이라는 기준 시각이 사람마다 달라집니다. 그래서 예의 “사장”처럼 한 사람이 열흘 걸리는 일이니 열 사람에게 맡기면 하루에 끝난다고 자신해서는 안 됩니다.

일을 나눠 맡기는 데서 오는 불확실성에 대응하는 조치가 필요합니다. 분산 시스템으로 돌아오면 부분 실패는 반드시 일어납니다. 설계한 시스템이 이를 견뎌야 하고 단일 서버에는 없는 복잡성이 여기서 나옵니다.

분산 시스템 특유의 고장

신뢰할 수 없는 네트워크

순수한 분산 시스템의 구조는 대부분 비공유(Shared Nothing)입니다. 계산과 저장을 분리해 저장소를 공유하는 것처럼 보이는 구조도 그 밑의 저장소는 비공유 문제를 풀어야 합니다. 원문은 이것을 Nothing but Network라고 부르는 쪽을 택하는데 네트워크가 서로 다른 노드가 정보를 나누는 유일한 길이기 때문입니다. 데이터는 주로 이더넷으로 전송되고 이것은 비동기 네트워크입니다. 보낸 패킷이 반드시 받아진다는 것도 언제 받아진다는 것도 네트워크가 보장하지 않습니다. 요청 하나가 겪을 수 있는 일은 다음과 같습니다.

• 요청이 사라짐
• 요청이 어떤 큐에서 기다리는 중
• 원격 노드가 이미 실패함
• 원격 노드가 응답하지 못함
• 원격 노드가 요청을 처리했지만 ack를 보내다 패킷이 사라짐
• 원격 수신 노드가 요청을 처리했지만 응답이 느림

원문은 네트워크가 믿을 수 없어지는 원인에 이더넷과 IP 패킷 외에 애플리케이션의 이상도 든다고 봅니다. 노드 사이의 전송 프로토콜은 대개 TCP이고 TCP는 끝에서 끝까지 이어지는 프로토콜이어서 송신 쪽과 수신 쪽의 커널이 연결을 유지할 자료구조를 명시적으로 관리해야 합니다. 응용 계층에서 아래의 문제가 생기면 네트워크 패킷이 커널의 소켓 버퍼에서 처리되지 못하고 기다리거나 응답이 처리되지 못합니다.

• 애플리케이션의 GC
• 처리 노드의 무거운 디스크 I/O로 CPU가 인터럽트에서 빠져나오지 못해 네트워크 요청을 처리하지 못함
• 메모리 페이징으로 인한 스래싱

이 문제들이 네트워크 자체의 불안정성과 겹쳐 바깥에서 보면 네트워크가 더 믿기 어려워 보입니다. 이 불안정은 앞 장의 복제 지연을 크게 키워 갖가지 일관성 문제로 이어집니다.

대응 방법

네트워크 이상은 단일 서버의 오류와 달리 응답 상태가 하나 더 있습니다. 지연이고 그 시간은 전혀 예측할 수 없습니다. 이 때문에 프로그램을 짜기가 아주 골치 아프고 앞 장의 문제에서도 노드가 실패했는지 알 길이 없을 수 있습니다. 보낸 요청에 아무도 응답하지 않을 수 있기 때문입니다. 그래서 이 불확실한 상태를 확정된 결과로 바꿔야 하고 그 수단이 타임아웃입니다. 여기서 두 질문이 나옵니다.

첫째 질문은 실패를 탐지한 뒤 어떻게 대응하느냐입니다.

• 로드 밸런서는 실패한 노드로 데이터를 보내지 않아야 합니다(서비스 디스커버리 모듈의 헬스 체크).
• 주종 복제에서 리더가 실패하면 선출을 일으켜야 합니다(Kafka에서 임시 노드가 사라지면 컨트롤러가 변경을 감지해 새 선출을 일으키고 컨트롤러 자신의 선출 방식도 있습니다).
• 서비스 프로세스가 죽었는데 운영 체제는 정상이면 스크립트로 다른 노드에 알려 새 노드가 이어받게 할 수 있습니다(Kafka의 좀비 노드 탐지는 강제로 임시 노드를 내립니다).
• 라우터가 목적 노드에 도달할 수 없다고 확인하면 ICMP 도달 불가를 돌려줍니다(ping이 안 되면 내리는 경로).

둘째 질문은 타임아웃을 얼마로 잡느냐이고 원문의 답은 트레이드오프입니다. 짧은 타임아웃은 고장을 더 빨리 찾지만 오판 위험이 같이 커집니다. 네트워크가 정상이라고 가정하고 끝에서 끝까지의 ping 시간이 d, 처리 시간이 r이면 요청은 대체로 2d + r 안에 끝납니다. 하지만 현실에서는 비동기 네트워크의 구체적인 지연을 가정할 수 없고 실제 상황은 더 복잡합니다. 그래서 경험에 크게 기대는 일입니다.

신뢰할 수 없는 시계

신호의 문제를 보았으니 이제 집집마다의 “시계”입니다. 시계는 주로 두 가지에 쓰입니다.

• 현재의 절대 시각을 나타냅니다.
• 어떤 일이 지속된 시간을 나타냅니다.

DDIA는 두 용도에 시계 두 종류를 줍니다. 하나는 벽시계로 현재 날짜와 시각을 돌려줍니다. clock_gettime(CLOCK_REALTIME)이나 System.currentTimeMillis가 예입니다. 이 API는 정확한 시각을 반영하지만 시계 동기화 때문에 시각이 뒤로 가는 일이 생깁니다. 그래서 지속 시간을 재는 데는 보통 단조 시계를 씁니다. clock_gettime(CLOCK_MONOTONIC)이나 System.nanoTime이 예입니다. 원문은 이후 버전의 Kafka가 요청 응답 지연 계산을 모두 이 API로 바꾼 것도 이 이유일 것이라고 짐작합니다.

시계 동기화의 구체적인 원리와 시계가 부정확해지는 까닭은 원문이 다루지 않고 책을 읽어 보라고 권합니다. 이어서 타임스탬프로 사건 순서를 기술하는 사례를 보이고 시계 문제 때문에 순서 판단이 어긋나는 것을 보여 줍니다. 원문의 예에서 Node1의 시계는 Node3보다 빠릅니다. 두 노드가 로컬 요청을 처리한 뒤 Node2에 쓰려는 순간 문제가 생깁니다. 원래 ClientB의 쓰기가 ClientA의 쓰기보다 분명히 나중인데 결과적으로 Node1의 타임스탬프가 더 커서 남겨야 할 x+=1이 버려집니다. 그래서 LWW를 쓰면 데이터가 기대와 어긋나는 문제가 반드시 생깁니다. 시계가 3초 빠른 노드에서 쓰기 세 개의 순서가 어떻게 뒤집히는지는 하편에서 손으로 따져 보았습니다.

시계가 정확하지 않기 때문에 통계의 신뢰 구간이라는 개념이 들어옵니다. 지금 시각이 어느 범위에 있는지를 말하는 것인데 일반적인 API는 이런 정보를 돌려주지 않습니다. Google의 TrueTime API는 정확히 이것을 돌려줍니다. 호출 결과가 구간이고 이런 API가 있으면 이 구간에 기대는 일을 할 수 있습니다. 원문은 Google의 Spanner가 TrueTime으로 스냅숏 격리를 구현한다고 적었습니다. 시계 문제를 다루는 길은 순서만 세는 논리 시계를 쓰는 것과 시계의 오차를 드러내는 것 둘이고 TrueTime은 뒤쪽입니다. TrueTime은 현재 시각을 가장 이른 값과 가장 늦은 값의 구간으로 돌려줍니다. Spanner 논문은 이 불확실성이 대개 10ms 미만이라고 했고 Spanner는 커밋할 때 그 구간이 지나가기를 기다립니다.

이 어려운 환경에서 시스템을 설계하는 법

여기까지 읽으면 꽤 “절망스럽습니다”. 지금 시각이 틀렸을 수 있고 측정이 부정확할 수 있으며 요청이 아무 응답도 받지 못할 수 있고 상대가 아직 살아 있는지도 모릅니다. 이런 환경에서 분산 시스템을 설계하는 일은 백 명으로 이뤄진 큰 부서에서 일을 조율하는 것처럼 작업량이 어마어마하고 복잡합니다.

그래도 할 수 있는 일이 있습니다. 조율을 예로 들면 우리는 한 사람의 의견만으로 정하지 않습니다. 학창 시절 반장을 뽑던 때를 떠올려 봅니다. 투표하고 개표해서 표를 가장 많이 받은 사람이 당선되었고 때로는 과반을 넘어야 한다는 조건이 붙었습니다.

분산 시스템도 마찬가지입니다. 어느 노드의 정보도 쉽게 믿을 수 없는 까닭은 불확실한 요소가 너무 많기 때문입니다. 그래서 어떤 일에 합의가 필요할 때 선거나 의회처럼 협상하고 투표하고 중재해 하나의 안건에 모으고 진실은 다수가 의논해 정합니다. 이것이 뒤에서 소개할 분산 합의 프로토콜입니다. 이 프로토콜은 일부 노드의 부분 실패나 영문 모를 고장이 낳는 문제를 견뎌 시스템이 정상으로 돌아가게 하고 요청해서 받은 데이터를 믿을 수 있게 합니다.

분산 알고리즘의 이론 모델은 지연을 어떻게 가정하느냐에 따라 셋으로 나뉩니다.

1. 동기 모델. 네트워크 지연에 상한이 있다고 가정합니다. 지연의 상한과 하한을 분명히 알 수 있고 어떤 상황에서도 이 범위를 넘지 않습니다.
2. 부분 동기 모델(원문은 半同步 모델이라 쓰며 대부분의 모델이 이 가정에 기댑니다). 앞에서 본 반동기 복제와 이름만 같고 네트워크 지연에 대한 가정을 가리키는 말입니다. 대부분의 경우 네트워크와 지연이 정상이지만 이 가정이 깨질 때는 편차가 매우 클 수 있다고 봅니다.
3. 비동기 모델. 지연에 아무 가정도 하지 않고 타임아웃도 없습니다.

노드 실패를 다루는 모델도 셋이 있고 악의적으로 거짓말을 하는 비잔틴 모델은 여기서 제외하여 둘이 남습니다.

1. 크래시-중단(Crash-Stop). 노드가 한 가지 방식, 곧 크래시로만 고장 난다고 가정합니다. 어느 때든 응답을 멈출 수 있고 그 뒤로 영영 돌아오지 못합니다.
2. 크래시-복구. 노드가 어느 때든 크래시할 수 있고 한참 뒤 복구해서 다시 응답할 수 있습니다. 이 모델에서는 영속 저장소의 데이터는 남고 메모리의 데이터는 사라진다고 가정합니다.

대부분의 알고리즘은 부분 동기 모델과 크래시-복구 모델의 조합을 바탕으로 설계됩니다.

안전성과 활성

분산 알고리즘을 설계할 때 이 두 말이 아주 중요한 구실을 합니다. 안전성(Safety)은 의도하지 않은 일이 일어나지 않는다는 뜻입니다. 안전성을 어겼다면 그것이 일어난 시점을 반드시 짚을 수 있고 한 번 어기면 되돌릴 수 없습니다. 활성(Liveness)은 기대한 일이 결국 일어난다는 뜻입니다. 정확한 시점은 알 수 없어도 미래의 어느 때에는 요건이 채워지기를 기대합니다.

분산 알고리즘을 설계할 때는 보통 안전성을 반드시 만족시켜야 하고 활성은 일정한 전제가 있어야 만족시킬 수 있습니다.

총결

원문의 정리를 따라가면 이렇습니다. 원문은 복제의 세 가지 흔한 모델인 주종 복제, 다중 리더 복제, 리더 없는 복제를 소개하고 세 모델의 특징, 쓰임새, 장단점을 보았습니다. 이어서 현실의 예로 분산 시스템의 두 가지 특유한 문제인 노드의 부분 실패와 시스템 시계를 공유하지 못하는 문제를 보았습니다. 두 문제는 분산 시스템을 설계하는 데 큰 어려움을 줍니다. 설계에 특정한 대책이 없으면 우리가 만든 분산 시스템은 설계 취지를 제대로 채우지 못하고 사용자도 분산 시스템으로 원하는 일을 끝내지 못합니다.

이 문제들을 하편 “Replication（下）：事务，一致性与共识”가 하나씩 풀고 트랜잭션, 일관성, 합의라는 세 열쇳말이 분산 시스템을 설계할 때 길잡이가 된다고 원문은 말합니다. 직접 재 보면 주종 모델에서 응답을 기다리는 지점의 선택이 숫자로 나타납니다. 응답을 기다리는 지점에 따라 커밋 지연이 0.26ms에서 12.7ms로 갈렸고 쓴 직후 읽기는 같은 6,000번에서 0회와 6,000회로 갈렸습니다.

실행한 조건과 한계

• PostgreSQL 16.15의 리더 한 대와 동기 팔로워 한 대를 같은 가상 머신(CPU 6, 메모리 8GiB)의 컨테이너로 띄웠습니다. 데이터 디렉터리는 메모리 파일 시스템에 두었으므로 디스크에 내려쓰는 비용은 실제보다 작습니다.
• 클라이언트 하나가 차례로 실행했습니다. 동시에 여러 클라이언트가 쓸 때의 값은 재지 않았습니다.
• 링크 지연은 복제 연결만 지나는 프록시에 편도 5ms를 넣어 만들었습니다. 실제 데이터센터 사이의 지연과 흔들림은 이보다 큽니다.
• 적용 지연은 팔로워의 recovery_min_apply_delay를 20ms로 두어 만들었습니다. 실제로 적용이 밀리는 원인(팔로워의 긴 쿼리, 무거운 쓰기)을 재현한 것은 아닙니다.
• 측정 동안 같은 기계에서 다른 작업이 돌고 있었습니다. 앞의 두 조건을 잰 5분 동안 1분 부하 평균은 2.9~4.1이었고 적용 지연 조건을 잰 9분 동안은 2.5에서 8.5까지 올랐습니다. 그래서 중앙값만 적었고 0.1ms 단위의 차이는 이 측정으로 가릴 수 없습니다.
• 커밋이 돌아온 시각과 팔로워에서 행이 보인 시각의 간격은 다음 날(2026-10-12) 같은 구성을 다시 띄워 수준마다 1,000번씩 세 차례 쟀습니다. 팔로워를 계속 조회해 행이 보인 응답의 시각을 썼으므로 분해능은 0.4ms 안팎입니다. 적용까지 기다리는 remote_apply도 지연 없는 조건에서는 31~38%가 음수로 나왔고 그래서 지연 없는 조건의 선후는 이 방법으로 가르지 못합니다. 이 실행에서 편도 5ms 조건의 커밋 중앙값은 11.5~11.7ms로 첫 측정보다 1ms쯤 작았습니다.
• 회사 사례의 수치는 각 회사가 공개한 글과 논문의 값이고 제가 재현한 것이 아닙니다.
• Spanner가 TrueTime으로 스냅숏 격리를 구현한다는 서술은 원문의 것이고 이 글에서 논문과 따로 대조하지 않았습니다. 논문에서 확인한 것은 TrueTime의 구간 반환과 커밋 대기입니다.
• 원문의 Kafka 단조 시계 서술(이후 버전이 응답 지연 계산을 nanoTime으로 바꾼 것)과 쉐청의 동작은 원문의 서술 그대로 옮겼고 확인하지 않았습니다.

참고

따라간 글

• Replication（上）：常见复制模型&分布式系统挑战 (美团技术团队, 2021-08-25)
• Replication（下）：事务，一致性与共识 (美团技术团队, 2021-08-25)

회사 사례

• GitHub, October 21 post-incident analysis (2018)
• GitHub, Mitigating replication lag and reducing read load with freno (2017)
• Shopify, Read Consistency with Database Replicas (2021)
• Meta, Building and deploying MySQL Raft at Meta (2023)
• Cloudflare, A Byzantine failure in the real world (2020)
• 美团, 美团数据库高可用架构的演进与设想 (2017)
• 美团, 美团万亿级 KV 存储架构与实践 (2020)
• TiKV, How TiKV Uses “Lease Read” to Guarantee High Performances, Strong Consistency and Linearizability, TiDB, Follower Read

논문

• Amazon, Dynamo: Amazon’s Highly Available Key-value Store (2007)
• Amazon, Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases (2017)
• Google, Spanner: Google’s Globally-Distributed Database (2012)
• Tencent, TDSQL: Tencent Distributed Database System (VLDB 2024)
• OceanBase: A 707 Million tpmC Distributed Relational Database System (VLDB 2022)
• ByteDance, ByteGraph: A High-Performance Distributed Graph Database in ByteDance (VLDB 2022)
• Ongaro & Ousterhout, In Search of an Understandable Consensus Algorithm (Raft)

공식 문서와 분석

• PostgreSQL 16, synchronous_commit
• MySQL 8.4, Semisynchronous Replication
• Apache Kafka, Producer Configs (acks), Topic Configs (min.insync.replicas)
• Apache Kafka 4.0.0 Release Announcement (2025)
• KIP-101: Alter Replication Protocol to use Leader Epoch rather than High Watermark for Truncation
• KIP-392: Allow consumers to fetch from closest replica
• KIP-833: Mark KRaft as Production Ready
• Jepsen, Consistency Models
• Jepsen, Kafka (2013)
• Jepsen, Redpanda 21.10.1 (2022), Jepsen, Bufstream 0.1.0 (2024)