복제(하): 트랜잭션, 일관성, 합의

메이퇀 기술 블로그에 仕禄이 쓴 “Replication（下）：事务，一致性与共识”(2021-08-25)를 절 순서대로 따라가며 정리했습니다. 仕禄은 『데이터 중심 애플리케이션 설계』(DDIA)를 길잡이로 삼아 트랜잭션과 내부 일관성과 합의를 풀고 Kafka의 복제 설계를 그 개념으로 다시 읽은 뒤 분산 알고리즘을 검증하는 도구로 글을 맺습니다. 상편은 복제(상): 흔히 쓰는 복제 모델과 분산 시스템의 어려움에 있습니다.

원문의 설명이 공식 문서와 논문과 직접 실행한 결과와 다른 곳은 그 자리에서 고쳐 적었고 맨 끝에 한 번 더 모았습니다. 원문에 없는 실행 결과와 회사 사례는 해당 절 안에 넣었습니다.

원문의 결론은 네 가지입니다.

• 트랜잭션은 ACID로 오류 처리의 일부를 대신 맡아 주고 격리 수준마다 막는 현상과 드는 비용이 다릅니다.
• 복제본 사이의 일관성(원문 표기 내부 일관성) 가운데 가장 강한 선형 일관성에서는 순서를 정하는 일이 핵심입니다. 인과 관계의 포착에서 Lamport 타임스탬프와 모든 노드에 같은 순서로 메시지를 전하는 전순서 브로드캐스트를 거쳐 합의에 이릅니다.
• 합의를 직접 구현하는 비용은 클 수 있습니다. ZooKeeper와 etcd 같은 검증된 시스템에 맡기고 직접 구현해야 하면 검증된 알고리즘을 씁니다.
• Kafka의 복제 설계에도 같은 개념이 그대로 들어 있고 알고리즘과 구현은 TLA+와 Jepsen으로 검증합니다.

원문에 없는 것으로 보탠 다섯 가지는 해당 절에 조건과 함께 실었습니다. 2번은 손으로 계산한 예시와 사례에서 옮긴 설명이고 나머지는 실행해서 잰 결과입니다.

1. 복제본이 하나인 것처럼 최신 값을 읽는 선형 읽기에는 노드 사이 왕복만큼의 시간이 듭니다. 노드 사이에 편도 5ms의 지연을 넣은 etcd 세 대에서 물어본 노드가 가진 값을 바로 돌려주는 읽기는 0.2~0.3ms였습니다. 선형 읽기는 리더에서 11.7~12.6ms, 팔로워에서 24.2~26.3ms로 쓰기와 겹치는 범위였습니다. 한 대를 나머지와 끊자 그 노드는 25초 뒤에도 옛 값을 돌려줬고 선형 읽기는 7초 뒤 실패했습니다.
2. 순서는 하나씩 올라가는 번호로 정합니다. 시계가 3초 빠른 노드가 있을 때 시각이 큰 쓰기를 남기면 그 3초 안에 다른 노드에 쓴 나중 값이 버려집니다. 번호는 물러난 리더와 잠금을 잃은 클라이언트의 쓰기를 거절하는 데도 쓰입니다.
3. 리더를 두는 합의에서는 리더가 바뀌는 동안 쓰기를 받지 못합니다. etcd의 리더를 끊자 쓰기가 영향받은 구간은 1.1~1.6초였고 이 구간에 남은 노드로 보낸 쓰기 66건 가운데 65건이 약 7초 뒤 실패하고 1건은 1.2초 뒤 성공했습니다. 새 리더가 쓰기를 다시 받기까지는 1.2~1.7초였고 그 뒤에 보낸 쓰기는 평소처럼 끝났습니다.
4. 2PC는 조정자가 멈추면 참가자가 잠금을 쥔 채 기다립니다. PostgreSQL에서 조정자가 2초, 5초, 10초 자리를 비우자 같은 행을 고치려던 쓰기가 2,000ms, 4,993ms, 9,996ms 막혔고 서버를 재시작해도 잠금이 남았습니다.
5. Kafka 트랜잭션은 읽는 쪽의 격리 수준까지 맞춰야 합니다. 트랜잭션을 5초 열어 두자 커밋된 것만 읽는 컨슈머는 트랜잭션과 무관한 메시지까지 5초 뒤에 받았습니다. 기본 설정의 컨슈머는 중단된 트랜잭션의 메시지를 1ms 안에 받았습니다.

합의 알고리즘의 구현과 격리 수준은 이 블로그의 다른 글에 있습니다.

앞 글 되짚기

앞 글은 분산 시스템에서 흔히 쓰는 복제 모델 셋을 장단점과 쓰임새로 나누어 풀었습니다. 한 노드가 쓰기를 받고 나머지가 따라 복제하는 단일 리더 모델(상편의 주종 모델)과 여러 노드가 쓰기를 받는 다중 리더 모델과 리더가 없는 모델입니다. 단일 리더 모델에서 쓰기를 받는 노드가 리더이고 따르는 노드가 팔로워입니다. 클라이언트에게 응답하는 시점으로는 동기 복제와 비동기 복제로 나눕니다. 비동기 복제는 복제본이 뒤처질 수 있어서 데이터가 어긋나고 그 어긋남이 여러 문제를 낳습니다.

앞 글은 분산 시스템에만 있는 어려움도 사장이 직원에게 일을 시키는 비유로 보였습니다. 일부만 고장 나는 부분 실패와 믿을 수 없는 시계입니다. 아무 장치 없는 단순한 분산 시스템은 아무 일도 하지 못하는 것처럼 보입니다.

앞 글은 끝에서 시스템 모델에 몇 가지 가정을 세웠고 이 글의 해법은 모두 그 가정 위에 서 있습니다.

• 부분 실패에는 타임아웃을 가정해야 하고 보통 부분 동기 모델(원문 표기 半同步)을 둡니다. 평소에는 지연이 정상이고 고장이 나면 편차가 아주 커지는 모델입니다. 상편의 반동기 복제(semi-synchronous replication, 상편 원문 표기 半步复制)와 이름이 비슷해 보일 뿐 서로 다른 개념입니다.
• 노드 고장은 죽었다가 돌아오는 크래시-복구(crash-recovery) 모델로 가정합니다.
• 분산 시스템의 두 보장 가운데 안전성(Safety)을 먼저 지킵니다. 안전성은 어겨진 시점을 짚을 수 있고 어긴 뒤에는 되돌릴 수 없는 성질입니다. 활성(Liveness)은 지금은 성립하지 않아도 언젠가 성립하길 바라는 성질이고 일정한 전제가 있어야 만족합니다.

이 글의 소개

앞 글을 읽으면 풀어야 할 문제가 무엇인지 알게 됩니다. 원문의 하편은 위의 가정을 하나씩 받아서 그 문제를 푸는 보장 장치를 소개합니다. 트랜잭션, 일관성, 합의입니다.

구성은 세 단계입니다. 먼저 이 장치들이 하는 일과 서로의 관계를 설명합니다. 다음으로 Kafka 복제 설계를 되돌아보며 실제 시스템이 이 이론의 패턴을 그대로 쓸 수 있는지 봅니다. 마지막으로 업계가 분산 알고리즘을 검증하는 도구와 프레임워크를 소개합니다.

트랜잭션과 외부 일관성

트랜잭션이라고 하면 ACID 특성과 여러 가지 격리 수준이 먼저 떠오릅니다. 원문은 이 둘이 트랜잭션이 풀어야 하는 문제라는 점을 인정하고 이 장에서 둘이 어떻게 이어지는지를 차례대로 보겠다고 합니다. 이 장 제목의 외부 일관성은 원문이 트랜잭션이 지키는 연산 사이의 일관성에 붙인 이름입니다. DDIA에는 데이터베이스 트랜잭션의 구체적 구현이 많이 나오는데 원문은 이를 줄입니다. 문제 자체를 파악한 뒤에 해법을 찾을 때 설계를 보는 편이 효과가 좋다는 이유입니다.

트랜잭션의 탄생

원문은 저장 시스템이나 데이터베이스에 접근할 때 마주칠 수 있는 문제를 다섯 가지로 듭니다.

• 프로그램 아래의 운영체제나 하드웨어는 언제든 고장 날 수 있고 연산이 반쯤 실행된 때도 마찬가지입니다.
• 애플리케이션도 연산이 반쯤 실행된 때를 포함해 언제든 죽을 수 있습니다.
• 네트워크가 언제든 끊겨 클라이언트와 서버 사이 또는 데이터베이스 사이의 연결이 잘릴 수 있습니다.
• 여러 클라이언트가 동시에 서버에 접근해 같은 데이터를 고치면서 서로를 덮어쓸 수 있습니다(임계 구역 문제입니다).
• 클라이언트가 낡은 데이터를 읽을 수 있습니다. 연산이 반쯤 실행되다 애플리케이션이 죽은 경우가 한 예입니다.

이 문제가 저장소 접근마다 나온다면 개발자는 애플리케이션을 만들면서 처리 비용을 따로 크게 치러야 합니다. 트랜잭션은 이 문제를 대신 풀어 주려고 있습니다. 트랜잭션이 자기 층에서 보증하는 안전성 덕에 사용자는 저장소에 접근할 때 자기 쓰기와 질의 로직에만 집중하고 부수적인 예외 처리는 맡길 수 있습니다. 이 보증을 만드는 수단이 널리 알려진 ACID 특성입니다.

번거롭더라도 다시 짚는 ACID 특성

ACID 네 글자는 다들 외우고 있지만 원문은 DDIA가 내린 정의가 서로의 관계를 이해하는 데 더 낫다고 보고 하나씩 설명합니다.

원자성(Atomicity)은 한 클라이언트가 여러 연산을 묶어 실행할 때 거는 제약입니다. 여기서 원자는 쪼갤 수 없다는 뜻입니다. 연산 집합 {A,B,C,D,E}를 실행한 결과는 한 클라이언트가 연산 하나를 실행한 것과 같아야 합니다. 이 제약에서 두 가지가 나옵니다.

• 연산 쪽에서 보면 어떤 고장이 나도 집합의 중간 결과가 보이면 안 됩니다. C까지 실행하다 고장이 났다면 트랜잭션을 다시 시도해 끝까지 실행하거나 A를 실행하기 전의 상태로 복구해야 합니다.
• 연산이 닿는 서버 쪽에서 보면 어떤 고장이 나도 서버에 부수 효과를 남기면 안 됩니다. 그래야 클라이언트가 안전하게 재시도할 수 있습니다. 재시도할 때마다 서버에 부수 효과가 남으면 클라이언트는 재시도하지 못합니다.

그래서 DDIA는 원자성을 이상이 생겼을 때 연산을 버리고 끝낼 수 있고 서버에 부수 효과가 없어서 안전하게 재시도할 수 있는 성질로 설명하고 중단 가능성(abortability)이 더 나은 이름일지 모르지만 관례를 따라 원자성이라고 쓴다고 적습니다.

일관성(Consistency)은 이름이 여러 곳에 붙어 있어서 문맥마다 뜻이 다르고 서로 얽혀 있어 혼란을 부릅니다.

• 데이터 복제에서 말하는 복제본 사이의 일관성은 앞 글에서 본 복제본 상태의 일치입니다.
• 일관된 해싱(consistent hashing)은 분할 알고리즘이고 원문 저자의 이해로는 어떤 상황에서도 해시가 일관되게 동작하게 하려는 것입니다.
• CAP 정리의 일관성은 복제본 사이의 일관성(내부 일관성) 가운데 특별한 하나인, 뒤에서 볼 선형 일관성입니다.
• ACID의 일관성은 데이터에 대한 어떤 진술이 반드시 성립해야 한다는 불변식(invariant), 곧 좋은 상태를 가리킵니다. 알고리즘의 루프 불변식과 비슷해서 바깥 환경이 바뀌어도 이 불변식은 성립해야 합니다.

DDIA는 ACID의 일관성을 대체로 사용자의 애플리케이션이 지켜야 한다고 강조합니다. 불변식이 무엇인지 아는 쪽이 사용자뿐이기 때문입니다. 원문의 예는 Kafka입니다. 메시지를 append하는데 내용이 2인 메시지가 두 개 있을 때 추가 정보가 없으면 클라이언트가 고장 후 재시도해서 두 번 보낸 것인지 정말 같은 데이터가 둘인 것인지 알 수 없습니다. 구분하려면 사용자 프로그램이 소비한 뒤 자체 중복 제거 로직을 돌리거나 Kafka 쪽에서 클라이언트가 보낼 때 메시지마다 고유 번호를 매기는 단계를 두면 됩니다. 후자는 이후 버전의 Kafka 트랜잭션이 구현한 대략의 발상이고 이렇게 하면 엔진 자체가 불변식을 어느 정도 설정할 능력을 갖춥니다. 더 복잡한 경우에는 사용자 프로그램과 호출 대상 서비스가 함께 유지해야 합니다.

격리성(Isolation)은 트랜잭션의 중심이고 가장 갈래가 많습니다. 여러 트랜잭션이 같은 데이터에 동시에 작용할 때의 동시성 문제를 풀기 때문입니다. 동시성의 본질은 시간 순서의 불확실성이고 불확실한 순서의 작용 범위가 겹치면(경쟁, race) 갖가지 문제가 생깁니다. 다중 스레드 프로그래밍과 닮았지만 여기서 하나의 연산은 컴퓨터 명령 하나보다 훨씬 오래 걸려서 문제가 더 심각하고 다양합니다.

구체적인 예로 클라이언트 둘이 DB의 counter를 동시에 고치는 경우를 봅니다. User2가 counter를 읽은 시각이 User1이 갱신하는 도중이라 오래된 값을 읽고 User2의 갱신도 같은 식으로 어긋납니다. 기대한 최종 값은 44인데 두 사람이 본 counter는 모두 43이었습니다. 두 스레드가 동시에 value++을 하는 것과 같습니다.

가장 엄격한 격리는 각 트랜잭션이 보기에 시스템에 자기만 일하고 있는 것 같고 시스템 전체로 보면 동시에 온 트랜잭션들이 하나씩 차례로 실행되어 트랜잭션이 하나뿐인 것 같은 상태입니다. 이 격리를 직렬화 가능성(Serializability)이라고 합니다. 이런 격리는 비용이 크기 때문에 여러 격리 수준이 생겨 상황마다 다른 요구를 채웁니다. 수준별로 어떤 문제를 푸는지는 뒤의 약한 격리 수준에서 봅니다.

지속성(Durability)은 이해하기 쉬워 보입니다. 트랜잭션이 끝났다면 어떤 문제가 생겨도 데이터를 잃으면 안 된다는 한 가지입니다. 이론상 단일 머신 데이터베이스라면 데이터가 비휘발성 저장소에 적혀야 하고 최소한 WAL에는 내려가야 합니다. 분산 시스템이라면 데이터가 각 복제본에 복제되고 복제본의 Ack를 받아야 합니다. 하지만 실제로는 100% 지속성을 보장하지 못하는 경우도 있습니다. 이 부분은 DDIA에 자세히 나오므로 원문은 옮겨 적지 않고 트랜잭션이 보장하는 지속성이 대개 어떤 균형 위에서 나온 결과라는 점만 짚습니다.

네 특성 가운데 문제가 가장 다양하고 복잡한 쪽이 격리성입니다. 직렬화만 고집하면 받아들이기 어려운 성능 비용이 따르기 때문입니다. 그래서 원문은 직렬화 가능보다 약한 격리 수준을 중심으로 이어 갑니다.

트랜잭션의 연산 대상 구분과 안전한 커밋 재시도

뒤로 가기 전에 짚을 것이 둘 있습니다. 트랜잭션이 다루는 대상(단일 객체와 다중 객체)과 트랜잭션의 커밋과 재시도입니다.

단일 객체 쓰기에 대해 DDIA는 두 가지 사례를 줍니다.

• 하나는 트랜잭션 하나가 오래 걸리는 쓰기를 하는 경우입니다. 20KB짜리 JSON 객체를 쓰다가 10KB에서 끊기면 무슨 일이 생길까요. 데이터베이스에 파싱할 수 없는 10KB의 깨진 데이터가 남는지, 복구한 뒤 이어서 쓸 수 있는지, 다른 클라이언트가 이 문서를 읽을 때 복구된 최신 값이 보이는지 깨진 문자가 보이는지를 따져야 합니다.
• 다른 하나는 앞의 예처럼 카운터를 자동 증가시키는 경우입니다.

이런 트랜잭션은 보통 로그 재생(원자성), 잠금(격리성), CAS(격리성) 같은 수단으로 보장합니다.

다중 객체 트랜잭션은 훨씬 복잡합니다. 일부 분산 시스템에서는 연산 대상이 스레드와 프로세스와 파티션을 넘어 시스템까지 넘나듭니다. 이 경우 앞 글에서 본 분산 시스템 고유의 문제보다 더 많은 문제를 마주치고 처리도 어렵습니다. 어떤 시스템은 이 부담을 사용자에게 넘기고 애플리케이션이 직접 처리하게 합니다. 원자성이 없어 생기는 중간 결과와 격리성이 없어 생기는 동시성 문제를 직접 다뤄야 한다는 뜻입니다. 이른바 분산 트랜잭션을 구현한 시스템도 있고 구체 수단은 뒤에서 봅니다.

또 하나 강조할 점이 재시도입니다. 트랜잭션의 핵심 성질은 오류가 났을 때 클라이언트가 안전하게 재시도할 수 있고 서버에 부수 효과가 없다는 것입니다. ACID를 제대로 구현한 전통적인 데이터베이스라면 이 의미를 따라야 합니다. 그러나 실제로 안전한 재시도는 어떻게 보장할까요. DDIA는 일어날 수 있는 문제와 해법을 이렇게 줍니다.

• 트랜잭션은 커밋됐는데 서버가 Ack를 보내다 네트워크가 끊겼을 때 클라이언트가 재시도하면 데이터가 중복됩니다. 서버나 애플리케이션이 메시지의 유일성을 구분할 속성을 따로 줘야 하고 서버에 내장된 트랜잭션 ID나 업무 자체의 속성 필드가 그 예입니다.
• 부하가 너무 커서 커밋이 실패했을 때 무작정 재시도하면 시스템 부담이 더 커집니다. 클라이언트 쪽에서 지수 백오프를 쓰거나 재시도 횟수를 제한하거나 클라이언트 시스템의 자체 큐에 넣는 제한을 둘 수 있습니다.
• 재시도하기 전에 판단하여 일시적 오류일 때만 재시도합니다. 애플리케이션이 이미 정해진 제약을 어겼다면 재시도는 의미가 없습니다.
• 트랜잭션이 다중 객체 연산이고 시스템에 부수 효과가 남을 수 있다면 2단계 커밋 같은 메커니즘으로 커밋해야 합니다. 이는 합의 절의 2단계 커밋에서 다룹니다.

약한 격리 수준

트랜잭션 격리가 푸는 것은 동시성 문제이고 여기에는 시간 순서와 경쟁이라는 두 가지 논점이 있습니다. 트랜잭션들이 같은 객체를 두고 경쟁하는 관계이고 동시 트랜잭션 사이의 시간 순서가 불확실해서 경쟁하는 객체에 갖가지 이상한 결과가 나옵니다.

상황마다 시간 순서를 얼마나 엄격하게 지켜야 하는지가 다르고 격리 수준은 이 요구를 서로 다른 비용으로 채우려는 시도입니다. 각 격리 수준을 어떻게 구현하는지는 몰라도 수준마다 어떤 문제를 푸는지는 분명히 알아야 수준과 비용 사이에서 편하게 균형을 잡습니다. 원문은 동시 트랜잭션이 일으킬 수 있는 문제를 먼저 설명한 뒤 수준별로 어떤 문제를 푸는지 소개합니다. DDIA는 격리 수준부터 나열합니다.

더티 리드

더티 리드는 아직 커밋되지 않은 트랜잭션의 결과가 다른 사용자에게 보이는 현상입니다. User1의 트랜잭션이 x=3과 y=3을 차례로 설정하는데 커밋하기 전에 User2가 get x를 호출하면 User1이 아직 커밋하지 않았으므로 이전 값 2를 돌려줘야 합니다. 이것이 더티 리드가 없을 때 지켜야 할 약속입니다.

더티 리드를 막는 의미는 두 가지입니다.

• 단일 객체 트랜잭션에서는 클라이언트가 곧 롤백될지 모르는 값을 봅니다. 그 값을 근거로 결정을 내리면 결정이 틀릴 가능성이 큽니다.
• 다중 객체 트랜잭션에서는 클라이언트가 여러 시스템에 접근할 때 일부 데이터는 갱신되고 일부는 갱신되지 않은 상태를 볼 수 있습니다. 사용자가 어찌할 바를 모르게 됩니다.

더티 라이트

한 클라이언트가 다른 클라이언트가 아직 커밋하지 않은 쓰기를 덮어쓰는 현상을 더티 라이트라고 합니다.

중고차 거래가 예입니다. 거래를 하려면 데이터베이스를 두 번 고쳐야 합니다. 판매 목록과 청구서입니다. 두 사용자가 동시에 거래할 때 더티 라이트를 막지 않으면 판매 목록에는 거래가 Bob의 것으로 나오는데 청구서는 Alice에게 발송될 수 있습니다. 두 트랜잭션이 두 데이터의 같은 레코드를 서로 덮어썼기 때문입니다.

리드 스큐(반복 불가능 읽기)

Alice는 은행 계좌 두 개에 합쳐 1,000을 갖고 있고 계좌마다 500입니다. 한 계좌에서 다른 계좌로 100을 이체하는 동안 두 계좌를 계속 지켜보려 합니다. 하필 첫 계좌는 이체가 일어나기 전에 조회하고 다른 계좌는 이체가 끝난 뒤에 조회해서 합이 정확히 100 모자랐습니다. 100을 잃은 것처럼 보입니다.

이것만이라면 일시적인 현상입니다. 나중에 다시 조회하면 올바른 값을 얻기 때문입니다. 그러나 이 조회를 근거로 다른 일을 하면 문제가 생길 수 있습니다. 예를 들어 DB가 죽을 때를 대비해 이 레코드를 Select해서 백업한다고 해 봅니다. 이후 정말 죽어서 이번에 조회한 데이터로 복구하면 그 100은 영영 사라질 수 있습니다. 이런 상황에서 반복 불가능 읽기는 받아들일 수 없습니다.

갱신 손실

앞에서 본 두 사용자가 같은 옛 값을 근거로 카운터를 동시에 갱신하는 예가 그대로 대표적인 갱신 손실입니다. 두 갱신 가운데 하나가 사라져 43이 남습니다.

쓰기 스큐와 팬텀 리드

쓰기 스큐는 트랜잭션의 쓰기가 앞서 내린 판단에 기대는데 다른 동시 트랜잭션이 그 판단의 근거를 바꾸는 경우입니다.

원문의 예는 당직 의사 Alice와 Bob이 퇴근해도 되는지 정하는 경우입니다. 결정의 전제는 지금 당직 의사가 둘 이상인지이고 그렇다면 안전하게 쉬고 당직 의사 정보를 고칩니다. 스냅샷 격리(뒤에서 설명합니다)를 쓰기 때문에 두 트랜잭션이 돌려받은 결과가 모두 2였고 둘 다 수정 단계로 들어갔습니다. 두 트랜잭션이 모두 커밋되어 당직 의사가 한 명도 남지 않고 최소 한 명은 당직이어야 한다는 요구를 어깁니다.

이 문제의 근본 원인은 팬텀이라는 현상입니다. 동시에 실행되는 두 트랜잭션 가운데 하나가 다른 트랜잭션의 질의 결과를 바꾸는 현상이며 이런 질의는 보통 count, max, min 같은 집계 결과에 대한 것입니다. 이런 문제는 아래 상황에서 나옵니다.

• 회의실 예약
• 다중 접속 게임에서 위치 갱신
• 유일한 사용자 이름

여기까지가 트랜잭션 동시성이 일으킬 수 있는 문제이고 이어서 격리 수준마다 푸는 문제를 봅니다. 아래 표는 원문의 표를 옮겼습니다. 원문에 범례가 없어서 Y는 막는다, N은 막지 못한다로 읽었습니다.

이 표를 Berenson 등의 1995년 논문, PostgreSQL과 MySQL 문서, DDIA 초안과 대조했습니다. 읽기 커밋 행과 직렬화 가능 행은 맞습니다. 읽기 커밋의 N들은 Berenson 등의 표에서 읽기 커밋이 갱신 손실, 반복 불가능 읽기, 리드 스큐, 쓰기 스큐를 허용한다는 것과 일치합니다. 고칠 곳은 넷이고 범례가 없는 것은 위에서 짚었으며 나머지 셋은 아래와 같습니다.

• 반복 읽기 행의 Maybe는 구현에 따라 갈린다는 뜻으로는 맞는데 독자가 어느 구현에서 어느 쪽인지 알 수 없습니다. PostgreSQL의 반복 읽기는 스냅샷 격리 기법으로 구현되어 있고 먼저 갱신한 쪽이 커밋하면 나중 트랜잭션이 “could not serialize access due to concurrent update” 오류로 롤백됩니다. 갱신 손실이 막힙니다. MySQL InnoDB의 반복 읽기는 갱신 손실을 자동으로 감지하지 않는다고 DDIA 2판 초안이 적습니다. InnoDB 문서의 일관된 읽기 절은 스냅샷이 SELECT에 적용될 뿐 DML에는 반드시 적용되지 않고 다른 동시 트랜잭션이 막 커밋한 행을 UPDATE나 DELETE가 건드릴 수 있다고 설명합니다. 이 문서에 lost update라는 단어가 쓰인 문장은 찾지 못했으므로 InnoDB에서 갱신 손실이 가능하다는 결론은 이 문서와 DDIA 서술에서 추론한 것입니다. 이 경우에는 원자적 UPDATE나 SELECT FOR UPDATE가 필요합니다.
• 괄호 안의 CAS는 애플리케이션이 갱신 손실을 피하려고 따로 쓰는 수단입니다. DDIA 2판 초안은 원자적 연산, 명시적 잠금, 자동 감지와 나란히 CAS를 별도 항목으로 올립니다. 반복 읽기와 스냅샷 격리를 같은 줄에 둔 것도 DDIA가 이름 혼란(naming confusion)이라고 부르는 지점이어서 원문 표 제목에는 DB마다 다르다는 단서가 필요합니다.
• 마지막 열 쓰기 스큐(팬텀)는 두 현상을 한 열로 묶었습니다. Berenson 등은 쓰기 스큐(A5B)와 팬텀(P3)을 열로 나누고 스냅샷 격리에서 쓰기 스큐는 가능, 팬텀은 때로 가능으로 적습니다. PostgreSQL 문서는 반복 읽기에서 직렬화 이상을 뺀 표의 모든 현상이 막힌다고 합니다. 반복 읽기 행의 N은 쓰기 스큐에는 맞고 팬텀은 구현에 따라 다릅니다.

트랜잭션 장의 정리

트랜잭션은 ACID 특성으로 사용자에게서 오류 처리의 일부를 가려 줍니다. 원자성은 안전하게 재시도할 수 있고 해당 시스템에 부수 효과가 남지 않는 환경을 줍니다. 일관성은 프로그램이 불변식을 어느 정도 만족하게 합니다. 격리성은 서로 다른 격리 수준으로 서로 다른 상황의 트랜잭션 동시성 현상을 풉니다. 수준마다 푸는 문제도 드는 비용도 달라서 사용자가 필요에 따라 결정해야 합니다. 지속성은 사용자가 마음 놓고 데이터를 우리가 설계한 시스템에 적게 합니다.

종합하면 트랜잭션이 보장하는 것은 서로 다른 연산 사이의 일관성입니다. 이상적인 트랜잭션 구현은 사용자가 보기에 트랜잭션이 하나만 일하고 매번 원자 연산 하나만 실행한 것처럼 보이게 합니다. 그래서 원문은 트랜잭션이 푸는 것을 연산의 일관성으로 보고 이 장 제목에 외부 일관성이라는 이름을 붙였습니다. 이 장은 대체로 단일 머신 범위의 트랜잭션을 이야기했습니다. 다음 장은 문제의 범위를 넓힙니다. 분산 시스템에도 이런 문제가 있고 복제 지연이라는 비슷한 문제가 더해집니다. 객체 하나를 다루는 듯 보여도 복제본이 여럿이라 마주하는 문제가 더 복잡해지므로 다음 장은 또 다른 일관성 문제와 그 해법을 중심으로 합니다.

내부 일관성과 합의

복제 지연의 문제

앞 글에서 본 복제 지연으로 돌아갑니다. 지연이 낳는 가장 눈에 띄는 문제는 복제가 진행되는 동안 클라이언트가 읽기를 요청하면 클라이언트마다 읽는 데이터가 다를 수 있다는 점입니다. DDIA는 이를 세 종류의 일관성 문제로 보여 주고 원문은 사례를 하나씩 들어 설명합니다.

첫째 사례는 사용자가 먼저 갱신하고 그 결과를 확인하는 사례입니다. 사용자가 블로그 글에 댓글을 달았고 이 서비스의 DB는 순수한 비동기 복제를 씁니다. 데이터가 리더에 쓰이면 댓글이 성공했다고 응답하므로 사용자는 페이지를 새로 고쳐서 자기 댓글이 얼마나 공감을 얻고 답글이 달렸는지 보려 합니다. 이때 질의가 팔로워로 가면 방금 쓴 댓글이 감쪽같이 사라져 보입니다. 시스템이 이런 상황을 막는다면 쓴 직후 읽기 일관성(read-your-writes)을 구현했다고 말합니다.

둘째 사례는 다른 경우입니다. 같은 댓글 모듈이 여전히 순수 비동기 복제를 쓰는데 이번에는 다른 사용자가 봅니다. 처음 새로 고칠 때는 User1234의 댓글이 보였다가 다음에 새로 고치면 그 댓글이 사라집니다. 시계가 뒤로 돌아간 것 같습니다. 시스템이 이런 일이 없도록 보장한다면 단조 읽기 일관성을 구현한 것입니다(원문은 텐센트 스포츠의 점수 화면과 상세 화면을 예로 듭니다).

셋째 사례는 더 엉뚱해 보입니다. 쓰는 클라이언트가 둘 있습니다. Mr. Poons가 질문을 하고 Mrs. Cake가 대답합니다. 순서로는 Mrs. Cake가 Mr. Poons의 질문을 본 뒤에 대답했습니다. 그런데 질문과 대답이 데이터베이스의 서로 다른 파티션(Partition)에 놓였습니다. 아래의 Observer에게는 Partition1 리더의 지연이 Partition2의 지연보다 훨씬 커서 대답이 먼저 보이고 질문이 나중에 보입니다. 자연의 법칙을 거스르는 일입니다. 이를 막을 수 있다면 시스템이 일관된 접두사 읽기(consistent prefix reads)를 구현했다고 말합니다.

앞 글에서 이런 인과를 검출할 수 있는 방법을 소개했습니다. 그래도 종합하면 복제 지연의 결과는 시스템이 최종 일관성만 갖춘다는 점이고 이 최종 일관성이 사용자 경험을 크게 해칠 수 있습니다. 세 사례는 서로 다른 일관성을 나타내지만 공통점은 복제 지연에서 온다는 점입니다. 복제의 정의대로 여러 클라이언트, 심지어 한 클라이언트가 여러 복제본을 읽고 쓸 때 생기는 문제입니다. 원문은 이런 일관성 문제를 내부 일관성(메모리 일관성)이라고 부릅니다. 여러 복제본을 읽고 쓰는 시간 순서 때문에 데이터가 어긋나는 문제를 나타냅니다.

내부 일관성 개요

내부 일관성은 분산 시스템에만 있는 문제가 아닙니다. 멀티코어 분야에서는 메모리 일관성이라고 부르고 여러 프로세서가 협력하는 방식을 약속하려는 것입니다. 프로세서들이 특정 일관성을 만족하면 프로세서들이 다루는 데이터와 연산 순서에 일정한 약속을 할 수 있고 애플리케이션 개발자는 그 약속을 믿고 시스템을 가정할 수 있습니다.

CPU 논리 코어마다 독립된 레지스터와 L1, L2 캐시가 있습니다. 그래서 동시성 프로그래밍에서 각 스레드가 메인 메모리 주소의 변수를 고치면 먼저 자기 캐시를 고치기 쉽고 변수를 읽을 때도 캐시를 먼저 봅니다. 분산 시스템에서 여러 클라이언트가 여러 복제본을 읽고 쓰는 현상과 닮았습니다. 다른 점은 분산 시스템에서는 연산이 단위이고 프로세서에서는 명령이 단위라는 것입니다. 원문은 이어서 다중 프로세서 메모리 일관성의 흔한 모델 몇 가지를 소개하지만 모델 이름은 본문에 적혀 있지 않아서 여기서도 옮기지 않습니다.

본문이 짚는 것은 이 모델들을 가르는 기준 하나입니다. 일관성 제약의 핵심 차이는 동시성이 생겼을 때 순서를 어떻게 제약하는지에 있습니다. 전문 용어로 말하면 원문은 선형 일관성만 전순서(total order)를 정해야 하고 나머지 일관성은 부분 순서(partial order)라고 설명합니다. 일부 동시 연산 사이에서는 순서를 비교하지 않고 가능한 모든 순열 조합대로 실행하도록 허용한다는 뜻입니다. 다만 이 구분은 느슨합니다. 순차 일관성도 Lamport가 1979년에 모든 연산을 하나의 순차 순서로 늘어놓은 것과 결과가 같아야 한다고 정의했으므로 전순서를 요구하고 선형 일관성과 갈리는 곳은 그 순서가 실제 시간의 순서를 지켜야 하느냐입니다.

멀티코어에서 미루어 보는 분산 시스템의 내부 일관성

분산 시스템의 내부 일관성은 크게 네 부류입니다. 선형 일관성, 순차 일관성, 인과 일관성, 프로세서 일관성의 순서로 점점 약해집니다. 전순서와 부분 순서로 나누면 강한 일관성(선형 일관성)과 최종 일관성으로 나뉩니다.

강한 일관성 아래 단계의 내부 일관성은 원문에 여러 가지가 나옵니다. 아무 제한 없는 최종 일관성은 부분 순서에 대한 보장이 없는 반면 이 일관성들은 각각 부분 순서에 어떤 제한을 두기 때문에 더 강한 보장을 가집니다. 이 일관성들의 구체적인 사례는 중국어 책 『大数据日知录』(빅데이터 일지록) 2장에 비교적 분명히 나옵니다. 원문은 이 장에서 강한 일관성에 집중합니다.

흔히 강한 일관성이라 부르는 선형 일관성

선형 일관성을 만족하는 시스템은 복제본이 하나뿐인 것처럼 느껴지게 합니다. 그래서 어느 복제본에서든 안심하고 데이터를 읽어 애플리케이션을 이어 갈 수 있습니다. 제약을 예로 보겠습니다. 클라이언트 셋이 같은 키 x를 동시에 다룹니다. DDIA는 이 키를 레지스터(Register)라고 부르며 연산은 둘입니다.

• write(x, v) => r은 x를 v로 갱신하려 시도하고 결과 r을 돌려줍니다.
• read(x) => v는 x를 읽고 값 v를 돌려줍니다.

클라이언트 C가 x를 0에서 1로 갱신하는 동안 A와 B가 최신 값을 반복해 조회한다고 해 봅니다. 확실하게 정해지는 결과가 있습니다. ClientA의 첫 read(x)는 ClientC가 x를 갱신하기 전이므로 반드시 0입니다. ClientA의 마지막 읽기는 ClientC가 갱신에 성공한 뒤이므로 반드시 1입니다. 나머지 읽기는 write(x,1)과의 순서가 불확실하므로(동시이므로) 0이나 1이 모두 나올 수 있습니다. 선형 일관성에는 이런 규칙이 붙습니다. 선형 일관성 시스템에서는 쓰기를 호출한 뒤 응답하기 전 사이에 어느 한 시점이 있고 그 시점부터 read가 새 값을 읽습니다. 새 값을 읽은 뒤의 모든 읽기는 새 값을 돌려줘야 합니다. 원문은 이 연산들을 엄격한 순서로 늘어놓은 예도 듭니다. ClientA read, ClientB read, ClientC write, ClientA read, ClientB read, ClientA read 순서입니다.

명확히 하려고 DDIA는 연산을 하나 더합니다.

• cas(x, v_old, v_new) => r은 지금 값이 v_old이면 x를 v_new로 갱신하고 갱신 결과를 돌려줍니다.

연산마다 효력이 생긴 시점을 시간 순서대로 이었을 때 그 선은 앞으로만 나아가야 하고 뒤로 돌아가면 안 됩니다. 선형 일관성은 이것을 요구합니다.

선형성에 기대야 하는 때

포럼 댓글의 선후나 스포츠 경기 페이지를 새로 고칠 때 값이 오락가락하는 정도라면 치명적인 해는 없어 보입니다. 하지만 시스템이 선형이 아니면 더 심각한 결과가 나오는 상황이 있습니다.

• 잠금과 선출: 단일 리더 복제 모델에서는 모든 쓰기를 받는 명확한 리더 노드가 있어야 하고 이 선출은 보통 잠금으로 구현합니다. 기대는 잠금 서비스가 선형 저장을 지원하지 않으면 값이 뒤로 튀어서 스플릿 브레인이 생길 수 있고 이 현상은 절대 받아들일 수 없습니다. 그래서 선출에 쓰는 분산 잠금 서비스의 저장 모듈은 선형 일관성을 만족해야 합니다. 일반적으로 메타데이터 저장도 선형 저장이어야 합니다.
• 제약과 유일성 보장: 유일한 ID, 기본 키, 이름 같은 곳은 쉽게 떠올릴 수 있습니다. 선형 저장이 약속하는 엄격한 순서가 없으면 유일성 제약이 쉽게 깨져 이상한 현상과 결과가 많이 나옵니다.
• 여러 시스템에 걸친 순서 의존: 서비스가 여러 시스템에 걸치면 시스템 사이에서 연산이 갖는 순서에도 제한이 필요합니다. DDIA의 예는 이렇습니다. 사용자가 이미지를 올리면 백엔드 저장 서비스가 원본 크기 이미지로 저해상도 이미지를 만들어 사용자 경험을 좋게 합니다. MQ는 이미지 같은 큰 바이트 스트림을 보내기에 맞지 않아서 원본 이미지는 백엔드 저장 서비스에 직접 보내고 축소 이미지 생성 요청은 MQ로 백그라운드에서 비동기로 실행합니다. 그렇다면 원본이 올라가는 파일 저장 서비스가 선형화 가능한 저장이어야 합니다. 그렇지 않으면 저해상도 이미지를 만들 때 원본을 찾지 못하거나 이미지의 절반만 읽을 수 있고 이는 분명히 원하는 결과가 아닙니다.

잠금과 선출을 선형 저장소에 올려도 남는 문제가 하나 있습니다. 잠금을 쥔 클라이언트가 멈춘 사이에 잠금이 만료되는 경우입니다. 잠금 서비스는 잠금을 내줄 때마다 하나씩 올린 번호(펜싱 토큰)를 함께 건넵니다. Martin Kleppmann의 예시에서 클라이언트 1은 토큰 33으로 잠금을 얻은 뒤 오래 멈춰 있고 그사이 잠금이 만료됩니다. 클라이언트 2가 토큰 34로 잠금을 얻어 저장소에 씁니다. 깨어난 클라이언트 1이 토큰 33으로 쓰려 하면 저장소는 34를 이미 처리했으므로 거절합니다.

합의로 만든 잠금 서비스에도 펜싱 토큰이 필요합니다. 분산 시스템에 고장을 넣어 일관성을 시험하는 프로젝트 Jepsen은 etcd 3.4.3을 분석해 키와 값을 읽고 쓰는 연산은 엄격한 직렬성을 지키는 것으로 보이고 잠금은 근본적으로 안전하지 않다고 결론 냈습니다. 엄격한 직렬성은 트랜잭션들이 실제 시간 순서대로 하나씩 실행된 것처럼 보이는 성질입니다.

etcd locks are fundamentally unsafe

분석에 따르면 여러 클라이언트가 같은 잠금을 동시에 쥘 수 있었고 고장을 넣지 않은 시험에서도 같은 일이 났습니다. Jepsen은 잠금을 쥔 쪽이 하는 연산마다 펜싱 토큰을 함께 보내는 방법을 들었고 etcd에서는 잠금 키의 리비전을 토큰으로 쓸 수 있다고 적었습니다.

원문은 이 절을 이렇게 맺습니다. 선형화는 경쟁을 피하는 유일한 방법이 아닙니다. 트랜잭션 격리 수준처럼 동시 순서에 대한 요구도 상황에 따라 엄격함이 달라서 내부 일관성 수준이 여러 가지로 나뉘었고 수준마다 비용도 달라 사용자가 스스로 결정해야 합니다.

선형화 시스템의 구현

선형화 시스템이 어디에 쓰이는지 보았으니 이제 구현을 생각합니다. 선형화의 정의에 따르면 이런 시스템은 밖에서 보기에 복제본이 하나입니다. 그렇다면 가장 쉽게 떠올리는 방법은 복제본을 정말 하나만 두는 것입니다. 이는 분산 시스템을 만든 취지와 어긋납니다. 복제본을 여럿 두는 큰 이유가 장애 허용이고 다중 복제본의 구현 방식이 복제이기 때문입니다. 그러면 앞 글에서 본 흔한 복제 방식이 선형 시스템을 만들 수 있는지 하나씩 봅니다.

• 단일 리더 복제(일부 가능): 동기 복제를 쓰면 시스템은 실제로 선형입니다. 다만 극단적인 경우에는 선형성을 어길 수 있습니다. 구성원 변경 중의 스플릿 브레인 때문에 소비가 이상해지는 경우가 한 예입니다. 비동기 복제를 쓰면 장애 조치 때 트랜잭션 특성의 지속성과 내부 일관성의 선형성을 함께 어깁니다.
• 합의 알고리즘(선형): 뒤에서 자세히 봅니다. 단일 리더 복제와 비슷하지만 더 엄격한 협상 메커니즘으로 구현해서 단일 리더 복제 위에서 나올 수 있는 스플릿 브레인 같은 문제를 피하고 선형 저장소를 비교적 안전하게 구현합니다.
• 다중 리더 복제(선형화 불가능).
• 리더 없는 복제(선형화가 안 될 수 있음): 구체적인 쿼럼 설정과 강한 일관성을 어떻게 정의하느냐에 달렸습니다. 원문은 엄격한 쿼럼을 만족하는데도 선형성을 만족하지 못하는 사례가 있다고 하며 그 내용은 도판에만 있습니다.

선형화의 대가, CAP 정리

CAP 정리가 나설 차례입니다. 앞 글에서 분산 시스템의 네트워크가 믿을 수 없다고 했습니다. 네트워크가 끊기면(P) 복제본 사이의 상태가 선형 일관성에 이르지 못합니다. 이때 서비스를 계속하되 옛 값을 줄 수 있는 쪽(A)을 택할지, 네트워크가 복구될 때까지 기다려 상태의 선형 일관성을 지킬지(C)가 그 유명한 CAP입니다.

원문은 CAP의 정의가 비교적 좁다고 덧붙입니다. C는 선형 일관성뿐이고 P는 네트워크 분할뿐인데 그 사이에 절충이 많아서 우리 시스템의 요구를 충분히 채울 수 있으니 이 이론을 맹신하지 말고 실제 상황에 맞춰 분석하라는 것입니다. 이 방향은 DDIA 2판 초안의 “CAP is best avoided”와 같습니다. 두 곳을 고쳐야 합니다.

• 원문은 P를 완전히 끊어진 분할로 한정하고 지연은 아니라고 적습니다. Gilbert와 Lynch의 2002년 논문은 분할 허용을 모델링하려고 네트워크가 한 노드에서 다른 노드로 보낸 메시지를 임의의 수만큼 잃을 수 있게 한다고 적습니다. 또 어떤 메시지 손실 패턴이든 메시지를 잃는 바로 그 순간에 통신하는 노드를 갈라놓은 일시적 분할로 모델링할 수 있다고 덧붙입니다. Brewer는 2012년에 분할을 통신의 시간 제한(time bound)이라고 보았습니다. Kleppmann은 분할이 유한하고 잃은 패킷이 재전송되는 한 분할도 큰 패킷 지연으로 모델링할 수 있다고 씁니다. 지연은 해당하지 않는다는 구절만 맞지 않습니다.
• C가 선형 일관성이라는 말은 Gilbert와 Lynch의 정리에서만 정확합니다. Kleppmann에 따르면 Fox와 Brewer는 C를 단일 복사본 직렬성(1SR)으로 정의했고 두 정의는 같지 않지만 꽤 비슷합니다.

이 선택을 etcd에서 확인했습니다. etcd 3.5.17 세 대를 띄우고 노드 사이에만 편도 5ms의 지연을 넣었습니다. 팔로워 한 대를 나머지 두 대와 끊었습니다. 노드의 프로세스는 살려 두고 노드 사이 네트워크에서만 떼어 냈으므로 클라이언트의 요청은 끊긴 노드에도 닿습니다. 그 뒤 남은 두 대에서 값을 v1에서 v2로 바꾸고 끊긴 노드에 읽기와 쓰기를 보냈습니다. 표에서 직렬 읽기는 물어본 노드가 자기가 가진 값을 바로 돌려주는 읽기이고 선형 읽기는 최신 값을 보장하는 읽기입니다.

리더를 끊었을 때도 끊긴 옛 리더의 결과는 같았습니다. 직렬 읽기는 옛 값을 돌려줬고 선형 읽기와 쓰기는 약 7초 뒤 실패했습니다. 남은 두 대는 선형 읽기에 v2로 답했습니다.

끊긴 노드는 옛 값이라도 답하거나 답하지 않거나 둘 가운데 하나를 골라야 합니다. CAP 정리가 말하는 선택이 바로 이 둘이고 etcd는 요청마다 고르게 해 두었습니다. etcd 문서는 이렇게 설명합니다. 클라이언트가 요청의 일관성 모드를 serializable로 설정하면 과반에 대해 낡은 데이터를 볼 수 있고 그 대신 합의에 기대느라 생기는 선형 접근의 성능 손실이 없습니다.

clients can configure a request’s consistency mode to serializable, which may access stale data with respect to quorum, but removes the performance penalty of linearized accesses’ reliance on live consensus.

캐시처럼 낡은 값을 받아도 되는 조회에는 직렬 읽기를, 잠금과 리더 선출처럼 낡은 값이 사고로 이어지는 조회에는 선형 읽기를 씁니다. 기본값은 선형 읽기입니다.

PingCAP은 TiDB 5.0의 릴리스 노트에 트랜잭션의 일관성을 낮췄을 때 줄어드는 지연을 실었습니다. 선형 일관성을 인과 일관성으로 바꾸면 Sysbench 쓰기 시험(64스레드)의 평균 지연이 11.86ms에서 11.19ms로 5.6% 줄었다고 합니다. 인과 일관성은 원인이 된 쓰기와 그 결과의 순서만 지키는 수준입니다. 같은 문서에 따르면 이때 서로 의존하지 않는 트랜잭션들은 전역으로 일관된 순서를 갖지 못합니다.

한 겹씩 쌓아 올리는 선형화 시스템 구현

선형 일관성의 정의에서 순서를 검출하는 것이 선형화 시스템을 구현하는 열쇠임을 알 수 있습니다. 원문은 DDIA의 흐름을 따라 한 걸음씩 갑니다. 이 동시 트랜잭션들의 순서를 어떻게 정할 수 있을까요.

a. 인과관계의 포착

앞 글의 내용과 비슷하게 동시 연산에는 두 종류가 있습니다. 연산 사이에 논리적으로 자연스러운 인과가 있는 것이 있고 확정할 수 없는 것이 있습니다. 먼저 인과가 있는 연산을 포착해 인과 일관성을 구현해 보겠습니다. 이를 포착하려면 데이터베이스(시스템) 연산의 모든 인과 관계를 저장해야 하고 버전 벡터 같은 방식을 쓸 수 있습니다. 기억이 흐려졌다면 앞 글에서 두 사람이 장바구니를 동시에 고치던 예시를 다시 보면 됩니다.

b. 포착에서 지정으로, 순서를 직접 정하기

위처럼 아무 제한 없이 일어난 인과를 사후에 포착하면 실행 비용(메모리와 디스크)이 큽니다. 이 관계는 디스크에 영속화할 수 있어도 분석할 때는 메모리에 올려야 합니다. 그래서 연산에 표지를 달아 인과 관계를 직접 정의하자는 생각이 나옵니다.

가장 간단한 방법은 전역 번호 발급기를 만들어 연산 사이의 인과를 정의하는 순번을 발급하는 것입니다. A가 B보다 먼저 일어나야 하면 A의 전순서 ID가 B보다 앞서도록 하면 됩니다. 다른 동시 연산의 순서는 강하게 제한하지 않습니다. 프로세서에서 연산끼리의 상대 순서는 바뀌지 않으므로 이렇게 하면 인과 일관성을 구현하면서 그 제한을 한층 강화합니다.

c. Lamport 타임스탬프

이 방식은 단일 리더 복제 모델에서는 쉽게 구현되지만 다중 리더나 리더 없는 복제 모델에서는 전역 순번 발급기를 설계하기가 어렵습니다. 유일한 순번을 만들려고 DDIA가 내놓는 방법은 다음과 같습니다.

• 노드마다 각자 순번을 만듭니다.
• 연산마다 타임스탬프를 붙입니다.
• 파티션마다 만들 순번 범위를 미리 할당합니다.

그러나 이 방법들은 모두 인과 관계의 부분 순서 약속을 깨뜨릴 수 있습니다. 노드마다 부하가 다르고 시계가 다르고 기준 틀이 다르기 때문입니다.

시각으로 번호를 만드는 위험은 메이퇀의 ID 발급기 Leaf에도 있었고 메이퇀은 그 처리를 공개했습니다. Leaf에는 ID에 밀리초 시각을 넣는 snowflake 방식이 있습니다. 시계가 거꾸로 가면 같은 ID가 다시 나올 수 있어서 이 방식은 발급할 때마다 직전에 발급한 시각과 견줍니다. 글에 실린 코드는 거꾸로 간 폭이 5ms 이하면 그 두 배를 기다렸다가 다시 보고 여전히 거꾸로면 예외를 던져 발급을 거절합니다. 메이퇀은 2017년 윤초 때 일부 기계의 시계가 거꾸로 갔고 이 처리 덕분에 서비스에 영향이 없었다고 밝혔습니다.

여기서 동시성의 대가 Lamport가 등장합니다. 원문은 그가 만든 Lamport 논리 타임스탬프가 위 문제를 말끔히 푼다고 합니다. 원문 저자는 대학원 분산 시스템 수업에서 Lamport 타임스탬프를 처음 접했을 때 무슨 말인지 몰랐고 이제 맥락을 알고 다시 보니 조금 이해가 된다고 적습니다. 간단히 말하면 논리 변수로 의존 관계를 정의한 것입니다. 순서쌍 <Counter, NodeId>를 두고 비교 방식을 정합니다.

• 먼저 Counter를 비교하고 Counter가 큰 쪽이 나중에 일어난 것입니다(엄격한 부분 순서를 약속한다고 원문은 설명합니다).
• Counter가 같으면 NodeId를 바로 비교하고 큰 쪽이 나중에 일어난 것으로 정의합니다(동시 관계입니다).

이 두 비교만으로는 인과 부분 순서가 깨지는 문제가 풀리지 않습니다. 이 알고리즘의 다른 점은 노드의 Counter 값을 요청의 응답 본문에 실어 보낸다는 것입니다. 예를 들어 클라이언트 A가 Node2에 갱신을 요청해 Node2의 현재 Counter 5를 돌려받으면 클라이언트는 로컬 Counter를 5로 올립니다. 다음 요청에는 1을 더합니다. 이렇게 노드들의 Counter가 각 복제본에서 변수의 부분 순서 관계를 유지합니다. 두 Node에 동시에 쓰면 곧바로 동시 행위로 정의하고 NodeId로 순서를 정합니다.

원문의 Counter 비교 규칙에는 바로잡을 곳이 있습니다. Lamport의 1978년 논문이 보장하는 것은 사건 a가 b보다 먼저 일어났다면 a의 시각이 b보다 작다는 한 방향이고 역은 성립하지 않습니다. Counter가 더 크다는 사실만으로 나중에 일어났다고 말할 수 없습니다. 같은 번호이면 동시라는 서술은 맞습니다. <Counter, NodeId> 쌍은 1978년 논문에 나오지 않고 DDIA식 표현입니다. 논문은 동률을 깨려고 프로세스 사이의 임의의 전순서를 쓰고 모든 메시지(요청과 응답)에 타임스탬프를 실으며 받은 쪽이 자기 시계를 받은 값보다 크게 올립니다. 원문이 든 응답에 싣는 예는 그 가운데 한 경우입니다.

노드 A의 시계가 3초 빠르다고 두고 쓰기 세 개의 순서를 손으로 계산했습니다. Lamport 번호는 노드마다 하나씩 올리는 번호이고 다른 노드의 번호를 받으면 자기 번호를 받은 번호보다 크게 올립니다.

x=1과 x=2 가운데 시계의 시각이 큰 쪽을 남기면 x=1이 남습니다. x=2는 x=1을 본 뒤에 쓴 값인데 버려집니다. Lamport 번호가 큰 쪽을 남기면 x=2가 남습니다. 표의 셋째 줄에서 x=3은 실제로 가장 늦게 쓰였는데 번호는 1입니다. 원인이 결과보다 작은 번호를 받는다는 한 가지만 보장되고 서로를 모르는 쓰기들 사이에서는 번호의 순서와 실제 시각의 순서가 어긋날 수 있습니다. 번호가 큰 쪽이 나중에 일어났다는 설명에 x=3이 반례입니다. 번호만으로는 선형성을 얻지 못하는 까닭도 같습니다. 실제 시각의 순서까지 지키려면 뒤의 전순서 브로드캐스트와 합의가 필요합니다.

d. 선형화로 가는 전순서 브로드캐스트

여기까지 Lamport 타임스탬프로 인과 일관성은 구현할 수 있습니다. 그래도 선형화는 되지 않습니다. 전순서를 모든 노드에 알려야 하기 때문입니다. 알리지 않으면 결정을 내리지 못할 수 있습니다. 유일한 사용자 이름 시나리오가 예입니다. A, B, C가 시스템에 같은 사용자 이름을 동시에 등록하려 합니다. Lamport 타임스탬프로는 세 동시 요청 가운데 가장 먼저 제출한 것이 성공하고 나머지는 실패합니다. 그런데 A, B, C가 있다는 것은 글을 읽는 우리만 아는 전지적 시점의 사실이고 요청이 전송될 때는 다른 요청이 있는지 모릅니다. 요청들이 서로 다른 노드로 갈 수 있기 때문입니다. 그러면 시스템이 이를 모으는 일을 해야 하고 코디네이터 같은 존재가 각 노드에 그런 요청이 있는지 계속 물어야 합니다. 질문하는 도중 한 노드가 고장 나면 시스템은 각 요청의 응답 결과를 안심하고 정하지 못합니다. 그래서 시스템이 이 순서를 각 노드에 브로드캐스트해 노드들이 순서를 실제로 알게 하고 곧바로 결정을 내리게 하는 편이 낫습니다.

CPU가 하나뿐이면 자연히 전순서입니다. 지금 필요한 것은 멀티코어, 멀티머신, 분산 환경에서 이 전순서를 브로드캐스트하는 일이고 도전이 둘 있습니다. 하나는 여러 대의 기계이고 다른 하나는 분산 환경입니다.

여러 대의 기계에서 전순서 브로드캐스트를 구현하는 가장 간단한 방법은 단일 리더 복제를 쓰는 것입니다. 모든 연산의 순서를 리더 노드가 정하고 같은 순서로 각 팔로워에게 브로드캐스트합니다. 분산 환경에서는 부분 실패를 다뤄야 합니다. 리더가 고장 나면 리더 구성원 변경을 처리해야 합니다. 이를 DDIA가 어떻게 푸는지 아래에서 봅니다. 여기서 말하는 전순서는 보통 파티션 안의 전순서이고 파티션을 넘나드는 전순서에는 별도 작업이 필요합니다.

DDIA는 전순서 브로드캐스트에 불변식 두 개를 줍니다.

• 신뢰할 수 있는 전달: 메시지가 all-or-nothing으로 전달되어야 합니다(앞 장의 원자성을 떠올리면 됩니다).
• 엄격한 순서: 메시지가 모든 노드에 완전히 같은 순서로 전달되어야 합니다.

위 불변식에 맞춰 간단한 구현 아이디어를 봅니다. 먼저 신뢰할 수 있는 전달에는 두 가지 의미가 있습니다.

• 메시지를 잃지 않습니다.
• 메시지가 일부만 전달되지 않습니다.

메시지를 잃지 않는다는 것은 일부 노드가 고장 난 뒤 재시도가 필요하다는 뜻이고 안전하게 재시도하려면 브로드캐스트 자체가 실패한 뒤에 시스템에 부수 효과를 남기면 안 됩니다. 그렇지 않으면 메시지가 일부 노드에만 전달되는 문제가 생깁니다. 앞 장의 트랜잭션 원자성이 풀던 문제입니다. 여기서 트랜잭션의 발상을 가져온다는 생각이 나옵니다. 다만 이 경우는 분산 시스템이고 메시지가 여러 노드로 가므로 분산 트랜잭션이어야 하고 귀에 익은 2PC가 반드시 등장합니다.

다른 하나는 엄격한 순서입니다. 순서를 보장하는 자료구조가 필요하고 연산이 시간순으로 append-only 구조에 쌓이므로 Log가 이 문제를 풉니다. 여기서 자주 거론되는 복제 상태 기계(replicated state machine)가 나옵니다. 원문 저자는 Raft 논문에서 이 개념을 보았다고 합니다. 초기 값이 a일 때 같은 순서로 연산 A, B, C, D, E를 실행하면 결과가 반드시 같다는 개념입니다. 그러므로 전순서 브로드캐스트의 최종 구현에는 Log라는 자료구조가 쓰일 수밖에 없습니다.

e. 선형 시스템의 구현

이제 전순서 브로드캐스트가 있다고 가정하고 목표인 선형 저장을 향해 한 걸음 더 갑니다. 먼저 분명히 할 것은 선형화가 전순서 브로드캐스트와 동치가 아니라는 점입니다. 분산 시스템 모델에서 보통 쓰는 비동기나 부분 동기 모델은 전순서 관계가 다른 노드에 언제 전달될지를 명확히 약속하지 않습니다. 선형 시스템을 실제로 구현하려면 전순서 브로드캐스트 위에 무언가를 더해야 합니다.

DDIA는 여기서도 유일한 사용자 이름 예를 듭니다. 선형화된 CAS 연산으로 구현할 수 있고 사용자가 이름을 만들 때 old 값이 비어 있을 때에 한해 쓰기를 허용합니다. 이런 선형 CAS를 구현하는 방법은 전순서 브로드캐스트에 로그를 더하는 것입니다.

• 로그에 등록하려는 사용자 이름을 알리는 메시지를 씁니다.
• 로그를 읽고 모든 노드에 브로드캐스트한 뒤 응답을 기다립니다(동기 복제).
• 이 이름의 첫 등록을 알리는 응답이 현재 노드에서 왔다면 이 로그를 커밋하고 성공을 돌려줍니다. 응답이 다른 노드에서 왔다면 클라이언트에게 바로 실패를 돌려줍니다.

이 로그 항목들은 같은 순서로 모든 노드에 브로드캐스트됩니다. 동시 쓰기가 생기면 모든 노드가 등록을 받아들일지, 이 사용자 이름을 어느 노드의 것으로 인정할지를 정해야 합니다. 이렇게 선형 CAS 쓰기의 선형 일관성을 구현했습니다. 그러나 읽기 요청은 로그를 비동기로 갱신하는 방식이어서 클라이언트가 옛 값을 읽을 수 있고 읽기의 선형화를 보장하려면 추가 작업이 필요합니다.

• 선형화된 방식으로 현재 최신 메시지의 위치를 얻고 그 위치 앞의 메시지를 모두 읽은 것을 확인한 뒤에 읽습니다(ZK의 sync()입니다).
• 로그에 메시지를 하나 넣고 응답을 받았을 때 실제로 읽습니다. 메시지가 로그에서 차지하는 위치가 읽기가 일어나는 시점을 정합니다.
• 동기로 갱신되는 복제본에서 데이터를 읽습니다.

ZooKeeper는 선형 읽기를 기본값으로 두지 않았습니다. 공식 문서는 두 클라이언트가 어느 순간에나 같은 데이터를 본다고 보장하지 않으며 최신 값이 필요하면 읽기 전에 sync()를 부르라고 안내합니다. 원문이 선형 읽기의 예로 든 것이 이 sync()입니다. 공식 문서에는 sync() 뒤의 읽기를 선형 읽기라고 적은 문장이 없고 순차 일관성(Sequential Consistency) 같은 말로 보장을 적습니다. sync()로 선형 읽기가 된다는 서술은 DDIA의 해석을 따른 것입니다.

etcd에서는 요청마다 선형 읽기와 직렬 읽기 가운데 하나를 고를 수 있고 기본은 선형 읽기입니다. 선형 읽기는 읽기마다 과반(세 대라면 두 대)과 통신하므로 읽기에 노드 사이 왕복이 붙고 과반과 끊긴 노드는 선형 읽기에 답하지 못합니다. 이 비용은 앞의 etcd 세 대에서 쟀습니다. 노드 사이 ping 왕복은 평균 12.7ms(10.4~14.8ms)였고 클라이언트와 노드 사이는 0.06ms였습니다. 같은 키를 500번씩 세 차례 읽어 차례마다 중앙값을 냈고 표에는 세 중앙값의 가장 낮은 것과 높은 것을 실었습니다. 쓰기는 300번씩 세 차례입니다.

두 열 모두 선형 읽기의 범위가 쓰기의 범위와 겹칩니다. 리더는 읽기에 답하기 전에 자기가 아직 리더인지를 과반에게 확인하고 이 확인에 노드 사이 왕복이 한 번 듭니다. 팔로워에 보낸 읽기에는 팔로워가 리더에게 묻는 왕복이 한 번 더 붙습니다. etcd의 raft 라이브러리 README는 이를 이렇게 적습니다. 리더는 읽기 전용 질의를 처리하기 전에 쿼럼에 확인하고 Raft 로그를 거치지 않으며 팔로워는 리더에게 안전한 읽기 위치를 받아 옵니다. etcd 사이트 문서가 선형 읽기가 Raft 합의 과정을 거친다고 한 것은 단순화한 표현이고 위 세 가지 가운데 로그에 메시지를 넣는 방식과는 경로가 다릅니다. 직접 만든 Raft에서 이 확인을 구현한 기록은 DB 내부 ⑩의 6장에 있습니다.

앤트그룹의 Raft 구현 SOFAJRaft에는 선형 읽기가 두 방식으로 들어 있습니다. 기본은 읽기마다 과반에 확인하는 ReadIndex입니다. 다른 하나인 Lease Read는 리더의 리스, 곧 정해 둔 시간 동안 리더 자격을 인정하는 약속에 기대어 그 확인을 건너뜁니다. 문서에 실린 두 방식의 성능 차이는 15%쯤이고 코드 주석에는 Lease Read가 시계에 기댄다는 경고가 달려 있습니다.

합의

앞에서 선형화 시스템을 구현하는 동안 합의의 모습이 이미 드러났습니다. 여러 노드가 어떤 제안에 동의해야 하고 한번 동의하면 철회할 수 없다는 점입니다. 현실의 많은 문제가 합의 문제와 같은 문제입니다.

• 선형화 가능한 CAS
• 원자적 트랜잭션 커밋
• 전순서 브로드캐스트
• 분산 잠금과 리스(lease)
• 구성원 조정
• 유일성 제약

이 가운데 어느 것에든 해법을 찾았다면 합의를 구현한 셈입니다.

2단계 커밋

DDIA는 원자적 커밋을 실마리로 합의를 이야기합니다. 책의 설명에서 2단계 커밋(2PC)도 합의 알고리즘의 하나입니다. 현실에서는 2PC를 더 나은 합의 알고리즘을 구현하는 수단이자 분산 트랜잭션의 핵심 구현 방법으로 보는 쪽이 낫다고 원문은 말합니다. 원문은 Raft 같은 합의 알고리즘에도 2PC와 비슷한 의미가 있다고 쓰는데 표현이 지나칩니다. DDIA는 합의의 투표 과정이 겉으로는 2PC와 많이 닮았다고 하면서 가장 큰 차이로 둘을 짚습니다. 2PC의 조정자(커밋을 지휘하는 쪽)는 선출로 정해지지 않습니다. 2PC는 모든 참가자(데이터를 실제로 고치는 DB나 파티션)의 찬성표를 요구하는 반면 내결함 합의는 과반의 표만 있으면 됩니다. DDIA는 합의 알고리즘이 새 리더를 뽑은 뒤 노드가 일관된 상태로 들어가는 복구 절차도 정의한다고 덧붙입니다.

a. 구현

알고리즘은 단순합니다. 정보를 모으고 결정을 내리는 조정자가 하나 있고 두 단계를 거칩니다.

• 조정자가 참가자에게 준비 요청을 보내 커밋할 수 있는지 묻습니다. 참가자가 예라고 답하면 그 메시지나 트랜잭션을 반드시 커밋하겠다고 약속한 것입니다.
• 조정자가 모든 참가자의 확인을 받으면 둘째 단계에서 그 트랜잭션을 커밋합니다. 한 곳이라도 아니라고 답하면 트랜잭션을 중단합니다.

정상 커밋보다 준비 단계 하나가 더 있을 뿐인 평범한 알고리즘인데 어떻게 원자적 커밋을 구현할까요. 알고리즘에 들어 있는 약속 때문입니다. 흐름을 더 잘게 나눕니다.

• 분산 트랜잭션을 시작할 때 조정자에게 트랜잭션 ID를 요청합니다.
• 애플리케이션이 각 참가 노드에서 단일 노드 트랜잭션을 실행하고 이 ID를 연산에 붙입니다. 읽기와 쓰기는 모두 단일 노드에서 끝나므로 문제가 생기면 안전하게 중단할 수 있습니다(단일 노드 트랜잭션의 보장입니다).
• 애플리케이션이 커밋할 준비가 되면 조정자가 모든 참가자에게 Prepare를 보냅니다. 요청 가운데 하나라도 오류가 나거나 시간이 초과되면 트랜잭션을 중단합니다.
• 참가자는 요청을 받으면 트랜잭션 데이터를 영속 저장소에 쓰고 위반이 있는지 확인합니다. 이때 첫 번째 약속이 나옵니다. 참가자가 조정자에게 예를 보냈다면 그 트랜잭션을 더는 철회하지 않는다는 뜻입니다.
• 조정자가 모든 참가자의 답을 받으면 답에 따라 결정합니다. 전원이 찬성표를 냈으면 커밋하겠다는 결정을 자기 로컬 영속 저장소에 씁니다. 여기서 두 번째 약속이 나옵니다. 조정자는 이 트랜잭션을 성공할 때까지 반드시 커밋합니다.
• 커밋 과정에서 이상이 생기면 조정자가 성공할 때까지 계속 재시도해야 합니다.

2PC가 원자성을 이루는 근거가 위의 두 약속입니다. PostgreSQL에서는 참가자 쪽의 첫 단계가 PREPARE TRANSACTION이고 둘째 단계가 COMMIT PREPARED입니다.

b. 한계

• 조정자가 상태를 저장해야 합니다. 조정자는 커밋하기로 결정한 뒤 그 트랜잭션을 반드시 커밋하겠다고 보증해야 하므로 결정을 영속화해야 합니다.
• 조정자가 단일 장애점입니다. 조정자에게 문제가 생기고 복구하지 못하면 시스템은 커밋할지 롤백할지 알지 못하고 관리자가 처리해야 합니다.
• 2PC의 준비 단계는 모든 참가자가 찬성표를 내야 진행합니다. 참가자가 많으면 트랜잭션이 실패할 확률이 높아집니다.

준비했다고 답한 참가자는 혼자서 취소할 수 없고 조정자의 지시를 기다려야 합니다. 그래서 조정자가 멈추면 참가자는 잠금을 쥔 채 멈춥니다.

PostgreSQL 16으로 이 한계를 직접 재 보니 조정자가 자리를 비운 만큼 다른 쓰기가 막혔습니다. 조정자 노릇을 하는 세션이 행 하나를 고치고 PREPARE TRANSACTION까지 한 뒤 연결을 끊었습니다. 조정자가 준비 단계 뒤에 죽은 상황입니다. 그동안 다른 세션이 같은 행을 고치려 했고 조정자가 돌아와 COMMIT PREPARED를 할 때까지 막힌 시간을 쟀습니다.

같은 행을 읽는 SELECT는 막히지 않았고 준비 전의 값을 돌려줬습니다. 쓰기에 lock_timeout을 500ms로 걸면 501ms 뒤 오류가 났습니다.

준비된 트랜잭션은 재시작 뒤에도 남고 다른 테이블의 정리까지 막았습니다. 준비된 트랜잭션을 끝내지 않고 둔 채로 세 가지를 더 실행했습니다. 표는 각 실행의 결과입니다.

셋째 줄이 2PC가 막으려던 상태입니다. 조정자가 한쪽만 커밋하고 죽으면 누군가 남은 쪽을 끝낼 때까지 두 DB의 합이 맞지 않고 그 행은 잠겨 있습니다.

이 실험을 다시 돌리다가 남은 준비된 트랜잭션에 직접 막혔습니다. 스크립트의 앞 단계가 준비된 트랜잭션 하나를 남긴 채 다음 단계가 그 테이블에 DROP TABLE을 실행했고 이 명령이 4분 45초 동안 기다렸습니다. 남은 트랜잭션을 ROLLBACK PREPARED로 끝내자 바로 풀렸습니다.

PostgreSQL 문서는 PREPARE TRANSACTION에 주의 문단을 달아 두었습니다. 준비된 상태로 오래 두면 VACUUM이 공간을 되찾지 못하고 트랜잭션이 잠금을 계속 쥔다는 내용입니다.

It is unwise to leave transactions in the prepared state for a long time. This will interfere with the ability of VACUUM to reclaim storage, and in extreme cases could cause the database to shut down to prevent transaction ID wraparound (see Section 25.1.5). Keep in mind also that the transaction continues to hold whatever locks it held.

회사들은 2PC를 쓰지 않거나 참가자를 복제하거나 둘째 단계를 미뤘습니다. 메이퇀은 2016년의 메시지 큐 설계 글에서 2PC를 쓰지 않기로 한 이유를 적었습니다. 조정자가 죽거나 한 곳이 고장 나는 경우를 두고 2PC는 거의 풀 수 없는 블랙홀이라고 썼습니다. 메이퇀이 고른 것은 데이터를 고치는 로컬 트랜잭션 안에서 보낼 메시지를 같은 DB에 저장하고 발송이 실패하면 다시 보내는 방식입니다. 이 방식에서는 같은 메시지가 두 번 갈 수 있어서 받는 쪽이 중복을 견뎌야 합니다.

OceanBase는 2PC를 유지하면서 참가자를 Paxos로 복제되는 그룹으로 두었습니다. 조정자의 상태는 따로 저장하지 않고 조정자가 죽으면 참가자들이 가진 상태로 다시 만듭니다. 논문에 따르면 이 설계로 커밋 한 번에 드는 Paxos 동기화가 세 번에서 두 번으로 줄었습니다. 조정자 쪽을 복제하는 방법은 Gray와 Lamport가 Paxos Commit이라는 이름으로 제안했습니다. 조정자를 2F+1대로 두고 F+1대가 살아 있으면 진행합니다.

TiDB는 커밋의 둘째 단계를 응답 뒤로 미뤘습니다. 5.0에 들어간 비동기 커밋은 첫 단계가 성공하면 클라이언트에 결과를 돌려주고 둘째 단계를 뒤에서 실행합니다. 릴리스 노트의 수치로는 64스레드에서 인덱스를 갱신하는 시험의 평균 지연이 12.04ms에서 7.01ms로 41.7% 줄었습니다.

합의 알고리즘의 일반적인 정의

2PC라는 특수한 사례를 보았으니 DDIA가 정리한 합의 알고리즘의 성질을 정의로 옮겨 적습니다.

• 협상 일치성(uniform agreement): 어떤 두 노드도 다르게 결정하지 않습니다.
• 성실성(integrity): 노드는 한번 결정하면 마음을 바꿔 다른 값을 결정할 수 없습니다. 한 제안에 서로 다른 결정을 두 번 내릴 수 없습니다.
• 유효성(validity): 값 v가 결정됐다면 그 v는 어떤 노드의 제안에서 나온 것입니다.
• 종료성(termination): 죽지 않은 노드는 반드시 결정에 이릅니다.

원문은 첫 성질을 모든 노드가 같은 제안을 받아들이는 것이라고 쓰는데 DDIA의 성질은 결정한 값이 같다는 것입니다. 제안은 서로 달라도 됩니다.

이 성질로 2PC를 견주면 2PC도 합의 알고리즘이라고 볼 수 있다고 원문은 말하고 그 점은 중요하지 않다며 이 성질이 우리에게 주는 시사점을 보자고 넘어갑니다. 원문도 조정자가 멈추면 진행하지 못한다는 한계를 따로 적었지만 이 문장과 잇지는 않았습니다. DDIA는 2PC가 합의 알고리즘이기는 하지만 좋은 합의가 아니라고 덧붙이고 이유는 종료성을 지키지 못한다는 것입니다. 조정자가 멈추면 끝나지 않으므로 2PC는 고장을 견디는 합의가 못 됩니다. Gray와 Lamport는 논문 초록에서 이렇게 적습니다.

The classic Two-Phase Commit protocol blocks if the coordinator fails.

앞의 세 성질은 안전성(Safety)을 규정합니다. 내결함 제약이 없다면 강한 리더(Strong Leader)를 사람이 정해 조정자 노릇을 맡기면 됩니다. 그러나 2PC의 한계에서 보았듯 조정자에게 문제가 생기면 시스템이 앞으로 나아가지 못해서 이 변경을 처리할 추가 메커니즘이 필요하고 이 메커니즘이 다시 합의에 기댑니다. 넷째 성질은 활성(Liveness)을 정합니다. 앞 글에서 안전성을 먼저 지켜야 하고 활성은 전제가 있어야 보장한다고 했습니다. DDIA는 여기서 결론을 곧바로 줍니다. 종료성이 성립하는 전제는 노드의 과반이 정상으로 동작하는 것입니다.

이 조건의 출처는 DDIA의 각주가 가리키는 Chandra와 Toueg의 1996년 논문입니다. 불확실한 고장 감지기를 쓰는 모델에서 과반이 정상이어야 한다는 요건이 필요하다고 증명합니다. Fischer, Lynch, Paterson(FLP)의 1985년 결과는 층이 다릅니다. 완전한 비동기 모델에서는 노드 하나가 알림 없이 죽어도 견디는 합의 프로토콜이 없다는 결과입니다. DDIA는 타임아웃으로 노드의 고장을 의심할 수 있으면 합의가 풀린다고 설명합니다. 과반이 정상이어야 종료한다는 조건은 FLP를 타임아웃으로 비껴간 모델 위에 붙는 조건입니다.

합의 알고리즘과 전순서 브로드캐스트

실제로 알고리즘을 설계해 구현할 때는 전순서 브로드캐스트를 씁니다. 메시지마다 앞의 네 성질로 합의를 한 번씩 거치게 하지는 않습니다. 전순서 브로드캐스트는 메시지를 같은 순서로 각 노드에 정확히 한 번 보낸다고 약속하므로 합의를 여러 라운드 하는 것과 같습니다. 라운드마다 노드들이 다음에 보낼 메시지를 제안하고 다음 메시지의 전순서를 정합니다. 전순서 브로드캐스트로 합의를 구현하면 한 번만 합의하는 것보다 효율이 높습니다(ZAB, Raft, Multi-Paxos가 그 예입니다).

둘이 동치라는 말에는 조건이 붙습니다. Chandra와 Toueg는 7절에서 합의와 원자적 브로드캐스트가 크래시 고장이 있는 비동기 시스템에서 서로 같다는 것을 한쪽을 다른 쪽으로 환원해 보입니다. 원문은 조건 없이 동등하다고 썼습니다.

더 생각할 거리

이 주제에는 더 이야기할 거리가 있습니다. 구현 쪽에서 보면 단일 리더 복제 모델은 합의 알고리즘에 특히 알맞습니다. 그러나 앞서 단일 리더 복제를 소개할 때 보았듯 단일 리더 모델만으로는 합의 문제를 풀기에 부족합니다. 이유가 두 가지입니다.

• 리더가 죽으면 새 리더를 어떻게 정하는지
• 스플릿 브레인을 어떻게 막는지

이 두 문제를 풀 때 다시 합의를 씁니다. 합의 알고리즘은 리더가 바뀔 때마다 올라가는 번호인 에포크(epoch)로 논리적 시간을 나타냅니다. Raft의 Term과 Paxos의 Ballot number와 Kafka의 리더 에포크가 그 예입니다. 선출 뒤에 두 노드가 동시에 자기가 리더라고 주장하면 더 새로운 에포크를 가진 노드가 당선됩니다.

받는 쪽이 지금까지 본 가장 큰 에포크를 기억해 두면 물러난 줄 모르는 옛 리더의 요청을 번호만 보고 거절할 수 있습니다. Google은 합의 알고리즘 Paxos로 잠금 서비스 Chubby를 만들면서 에포크를 넣었습니다. 논문에 따르면 요청을 받은 복제본이 처리 도중에 리더 자리를 잃거나 잃었다가 되찾을 수 있어서 리더가 줄곧 리더였는지를 확인할 수단이 필요했습니다. Chubby의 에포크는 한 복제본이 리더 자리를 지킨 동안에만 같은 번호로 남습니다.

리더는 결정을 내리기 전에도 더 높은 에포크의 노드가 동시에 결정하고 있지 않은지 확인해야 합니다. 있다면 충돌이 생길 수 있습니다(초기 Kafka에서는 Controller만 이런 표지를 가졌고 이후 버전에서는 데이터 파티션도 비슷한 표지를 갖습니다). 이때 노드는 자기 정보만으로 아무것도 결정하지 못하고 Quorum 노드에서 표를 모아야 합니다. 리더가 제안을 모든 노드에 보내 Quorum 노드의 응답을 기다리며 더 높은 에포크의 리더가 없다는 것을 확인했을 때만 노드가 현재 제안에 표를 던집니다.

자세히 보면 투표가 두 번 일어납니다. Quorum을 쓰는 것은 겹침을 이용하는 것입니다. 어떤 제안이 통과했다면 투표한 노드 가운데에는 가장 최근 리더 선출에 참가한 노드가 있습니다. 그러므로 리더가 바뀌지 않았다고 판단하고 이 리더의 제안에 안전하게 표를 던질 수 있습니다.

한편 합의 알고리즘에도 치르는 대가가 있습니다.

• 합의가 결정을 내리기 전 노드의 투표는 동기 복제입니다. 원문은 이 때문에 합의에 메시지를 잃을 위험이 있다고 쓰는데 DDIA는 위험의 자리를 다르게 적습니다. 장애 조치 때 이미 커밋된 데이터를 잃을 수 있다고 DDIA가 말하는 곳은 성능을 위해 많은 시스템이 고르는 비동기 복제이고 합의의 투표는 동기 복제입니다. 합의가 치르는 대가는 성능과 선형 일관성 사이의 선택이고(CAP입니다) 앞에서 본 etcd의 끊긴 노드가 그 한 예입니다.
• 과반 합의는 고정된 노드 집합을 전제합니다. 구성원을 마음대로 동적으로 바꿀 수 없고 시스템을 깊이 이해한 뒤에야 동적 구성원 변경을 할 수 있습니다. 구성원 변경을 외주로 돌린 시스템도 있을 것이라고 원문은 덧붙입니다.
• 합의는 네트워크에 극도로 민감하고 보통 타임아웃으로 고장을 감지합니다. 네트워크가 흔들리면 영문 모를 쓸모없는 리더 선출이 일어나고 시스템이 쓸 수 없는 상태에 빠지기도 합니다.

셋째 대가를 etcd에서 재 봤습니다. 앞의 etcd 세 대에서 남은 노드 한 대에 시험용 쓰기 요청을 0.1초마다 보냈습니다. 요청은 서로 기다리지 않게 따로 보냈고 요청마다 12초까지 기다렸습니다. 이 시험 요청(탐침)을 보내기 시작하고 4초 뒤에 리더를 나머지 두 대와 끊었습니다. 다섯 번 되풀이했습니다.

새 리더가 뽑혀 쓰기를 다시 받기까지는 1.2~1.7초였습니다. etcd의 선출 제한 시간은 기본 1초여서 남은 노드는 리더의 소식이 끊기고 1초쯤 지나야 선출을 시작합니다. 알아채는 시간과 뽑는 시간을 따로 재지는 않았습니다. 그사이에 보낸 66건 가운데 65건은 약 7초를 기다린 뒤 실패했고 1건만 1.2초 뒤 성공했습니다. 구간이 지난 뒤에 보낸 요청은 모두 0.2초 안에 성공했고 회차마다 낸 평소 요청의 중앙값은 14~28ms였습니다.

표의 실행보다 한 시간 앞선 첫 실행에서는 요청을 하나씩 이어서 보내면서 응답을 1.5초만 기다리고 한 번 다시 보내게 했습니다. 다섯 번 모두 끝내 실패한 요청은 없었고 성공한 요청 사이의 가장 긴 공백은 1.2~1.6초였습니다. 다섯 번 가운데 세 번의 값은 제한 시간 1.5초에 평소 요청 시간을 더한 크기였습니다. 응답을 선출 구간과 비슷한 시간만 기다리고 다시 보내면 7초를 기다리지 않고 끝날 수 있다는 뜻입니다. 제한 시간이 구간보다 짧으면 다시 보낸 요청도 구간 안에 들어갑니다. 독립 요청 탐침의 2회차에서는 첫 정상 요청이 1.7초 뒤에 나왔습니다. 제한 시간과 재시도 횟수를 바꿔 가며 재지는 않았습니다. 다시 보낼 때는 앞선 요청이 적용됐는지 알 수 없으므로 두 번 적용돼도 결과가 같은 요청이어야 합니다.

선출 제한 시간을 줄이면 이 구간은 짧아질 수 있고 네트워크가 느려진 순간에 살아 있는 리더를 바꾸는 일이 늘 수 있습니다. 실행은 기본값으로만 했습니다. 앞 글에서 본 제한 시간의 딜레마가 합의 안에도 그대로 있습니다. 위챗의 저장소 PaxosStore는 리스에 기대는 리더를 두지 않는 쪽을 골랐습니다. 리스에 기대는 합의는 리더가 바뀌는 동안 서비스를 하지 못한다고 논문은 이유를 듭니다. 리더가 없으면 쓰기끼리 충돌할 수 있어서 PaxosStore는 요청을 정해진 복제본으로 보냅니다.

합의 외주

위 설명대로 합의 알고리즘을 직접 구현할 수도 있지만 비용이 클 수 있습니다. 가장 좋은 방법은 아마 이 기능을 외주로 맡겨 성숙한 시스템이 합의를 구현하게 하는 것입니다. 정말 직접 구현해야 한다면 검증된 알고리즘으로 구현해야 하고 알고리즘을 새로 고안해서는 안 됩니다. ZK와 etcd 같은 시스템이 이런 서비스를 제공합니다. 이 시스템들은 합의로 자신의 선형 저장소를 구현하고 합의의 의미를 밖으로도 제공해서 우리가 이를 이용해 여러 요구를 구현할 수 있습니다.

• 선형화 CAS
• 연산의 전순서
• 장애 감지
• 설정 변경

직접 구현하는 비용은 Google이 Chubby를 만든 경험을 “Paxos Made Live”로 남겨 보여 줍니다. 의사코드 한 쪽으로 설명되는 알고리즘이 완성된 구현에서는 C++ 수천 줄이 됐다고 합니다.

While Paxos can be described with a page of pseudo-code, our complete implementation contains several thousand lines of C++ code.

늘어난 까닭으로 논문은 디스크 손상, 리더의 리스, 구성원 변경을 듭니다. 디스크가 손상되어 기록을 잃은 복제본은 자기가 한 약속을 어길 수 있습니다. 구성원 변경은 문헌에 자세한 절차와 정확성 증명이 없어서 직접 채웠다고 합니다.

외주한 합의 저장소에도 위험이 있습니다. Roblox는 2021년 10월 28일부터 73시간 동안 서비스가 멈췄습니다. 사후 분석에 따르면 합의 기반 저장소 Consul에서 새로 켠 스트리밍 기능이 읽기와 쓰기가 몰린 상황에서 경합을 일으켰고 Consul이 로그 저장에 쓰는 BoltDB에서도 성능 문제가 함께 났습니다. Roblox는 서비스 디스커버리, 상태 점검, 세션 잠금, 키와 값 저장을 모두 이 Consul에 맡기고 있었습니다. 사후 분석은 Consul이 단일 장애점이었고 그 Consul이 건강하지 않았다고 정리합니다.

the system failed because Consul was a single point of failure, and Consul was not healthy.

합의가 견디는 고장은 노드 몇 대가 죽는 경우입니다. 저장소 전체가 느려지는 고장에는 합의가 도움이 되지 않고 그 저장소에 기대는 시스템들이 함께 느려집니다.

내부 일관성과 합의 장의 정리

이 장은 분산 시스템의 또 다른 일관성 문제인 내부 일관성을 길게 다뤘습니다. 이 문제는 주로 복제 지연에서 생깁니다. 먼저 문제의 기원을 소개한 뒤 분산 시스템에 대응시켜 일관성을 분류했습니다.

그 가운데 강한 일관성은 정의, 쓰임새, 구현까지 자세히 살폈습니다. 이 과정에서 전순서와 부분 순서와 인과 관계의 포착과 정의(Lamport 타임스탬프), 전순서 브로드캐스트, 2PC를 거쳐 합의에 이르렀고 이 일관성을 푸는 일이 얼마나 복잡한지 알 수 있습니다.

분산 시스템 다시 이야기하기

여기까지 복제라는 주제에서 출발해 분산 시스템의 복제 모델, 어려움, 트랜잭션, 합의를 이야기했습니다. 원문은 두 편의 내용을 모아 분산 시스템을 더 세밀하게 기술합니다. 먼저 특성과 문제를 서술하고 이어서 특정한 해법을 줍니다.

• 단일 머신 시스템처럼 분산 시스템에도 여러 클라이언트가 동시에 갖가지 연산을 합니다. 연산 하나가 건드리는 객체는 하나일 수도 여럿일 수도 있습니다. 이 클라이언트들의 동시 연산이 정확성 문제를 일으킬 수 있습니다.
• 장애 허용을 위해 분산 시스템의 데이터는 보통 여러 개로 백업됩니다. 복제본 사이는 복제로 맞춥니다.
• 흔한 복제 모델에는 단일 리더, 다중 리더, 리더 없음이 있습니다.
• 응답 시점과 선형 일관성의 관점에서는 동기 복제와 비동기 복제로 나눕니다.
• 비동기 복제에는 지연 문제가 있을 수 있고 여러 내부 일관성 문제로 이어집니다.
• 분산 시스템은 단일 머신 시스템과 달리 고유한 특징이 둘 있습니다. 부분 실패와 전역 시계의 부재입니다.

이렇게 문제가 많을 때 성능과 다른 비용을 따지지 않는다면 이상적인 분산 데이터 시스템은 이런 모습일 것입니다.

• 시스템의 데이터가 밖에서 보기에 복제본 하나뿐이라서 사용자는 어떤 상태를 바꿀 때 불일치를 걱정하지 않아도 됩니다(선형 일관성).
• 시스템에 클라이언트 하나만 일하고 있는 것 같아서 다른 클라이언트와 동시에 연산할 때의 충돌을 걱정하지 않아도 됩니다(직렬화).

그래서 선형 일관성과 직렬화는 서로 직교하는 두 갈래입니다. 원문은 이를 외부 일관성에서 가장 높은 수준과 내부 일관성에서 가장 높은 수준이라고 쓰는데 순서가 뒤바뀌어 있습니다. 원문 자신의 정의에서 트랜잭션 쪽(직렬화)이 외부 일관성이고 복제본 쪽(선형 일관성)이 내부 일관성이므로 선형 일관성은 내부 일관성의 최고 수준이고 직렬화는 외부 일관성의 최고 수준입니다. 두 수준을 정말 구현하면 사용자가 시스템을 쓰기 아주 편해집니다. 안타깝게도 두 방향에서 최고 수준에 이르는 데는 모두 큰 비용이 들어서 이 두 갈래에서 갖가지 내부 일관성과 외부 일관성이 파생됩니다.

원문은 Jepsen 사이트의 정의로 말하면 내부 일관성은 단일 연산이 단일 객체의 서로 다른 복제본에 하는 연산에 시간 전순서를 요구하고 외부 일관성은 여러 연산이 여러 객체에 하는 연산을 제약한다고 설명합니다. 이 구분의 내용은 맞지만 Jepsen의 페이지를 열어 보면 용어가 다릅니다.

두 축은 맨 위에서 엄격한 직렬성으로 만나고 Jepsen은 엄격한 직렬성이 두 계열을 합친다고 적습니다. “외부 일관성”은 Spanner 논문이 트랜잭션의 실제 시간 순서를 지키는 보장에 쓰는 말이어서 격리 수준 전체를 가리키는 이름으로 쓰기에는 맞지 않습니다. 두 축으로 나누는 것 자체는 원문과 Jepsen이 같습니다. 한편 Jepsen이 internal과 external이라는 이름을 붙이는 곳은 직렬성의 형식화이고 뜻이 다릅니다. 트랜잭션 안에서 읽기가 그 트랜잭션의 최근 쓰기를 본다는 성질이 internal consistency이며 앞선 쓰기가 없는 읽기가 보이는 트랜잭션이 쓴 상태를 본다는 성질이 external consistency입니다. 복제본과 트랜잭션을 가르는 내부와 외부는 원문 필자가 세운 분류입니다.

Java 동시성 프로그래밍에 비유하면 내부 일관성은 volatile 변수나 Atomic 변수가 여러 스레드의 같은 변수에 대한 연산을 제약하는 것과 같습니다. 외부 일관성은 synchronized나 AQS의 여러 잠금이 코드 블록(여러 연산, 여러 객체)에 대한 여러 스레드의 접근이 프로그래머의 기대에 맞도록 보장하는 것과 같습니다.

다만 분산 시스템에서 이 둘은 완전히 따로 놀지 않습니다. 보통 합의 알고리즘으로 선형 일관성을 구현하고 합의 알고리즘을 구현하는 과정에서도 연산 하나가 여러 객체를 건드리는 문제가 생길 수 있습니다. 분산 시스템의 연산은 흔히 여러 복제본에 작용하기 때문입니다. 2PC 같은 분산 트랜잭션이 합의 문제를 푸는 데 쓰이는 이유입니다(책은 2PC도 합의라고 부르지만 실제로는 트랜잭션 원자성 비슷한 연산을 제공합니다). synchronized 메서드 안에서 volatile 변수를 쓰기도 하는 것과 같습니다.

2PC가 분산 트랜잭션의 전부는 아닙니다. 파티션을 넘나드는 어떤 트랜잭션은 한 객체에 대한 연산의 일관성을 만족시키려고 선형 일관성에 기댄 연산을 쓰기도 합니다. 분산 시스템을 완전하게 구현하려면 이 두 일관성이 서로 의지하고 보완해야 합니다. 원문은 두 일관성의 핵심 역할을 충분히 알아야 이 메마른 용어들을 실전에서 능숙하게 쓸 수 있다고 맺습니다.

새 눈으로 다시 보는 Kafka

앞에서 정리한 일관성 개념으로 Kafka의 복제를 다시 봅니다. 원문은 복제 모델, 내부 일관성, 외부 일관성의 관점에서 봅니다.

Kafka에서 복제 모델과 관련한 설정은 복제 팩터(복제본 수)와 min.insync.replicas와 acks입니다. 사용자는 먼저 acks로 복제 방식을 대강 압니다. 원문은 acks=1이나 0이면 완전한 비동기 복제이고 acks=all이면 완전한 동기 복제라고 설명합니다. 비동기 복제를 고르면 단일 파티션이 선형 일관성을 보장하지 못합니다. 복제 지연 때문에 리더가 바뀌면 이미 커밋된 메시지를 잃을 수 있고 이것이 선형 일관성의 요구를 깨기 때문입니다. acks=-1은 순수한 동기 복제를 뜻하고 이때 min.insync.replicas 제한이 없으면 복제본 하나만 문제여도 활성을 희생한다고 원문은 말합니다. 장애 허용을 위한 다중 복제본이 오히려 복제본 하나의 고장에 시스템이 멈추는 결과를 부릅니다. min.insync.replicas가 사용자에게 균형을 잡을 여지를 주며 단일 파티션 선형 일관성을 보장하려면 과반의 노드가 정상이어야 하므로 min.insync.replicas를 과반으로 둔다고 원문은 설명합니다.

이 설명은 Kafka 문서와 세 군데에서 어긋납니다.

• acks=all은 지금 동기화된 복제본(ISR) 전부의 확인을 기다리는 설정입니다. 문서는 복제본이 둘인 토픽에서 하나가 고장 나 ISR이 하나만 남아도 acks=all 쓰기가 성공하고 남은 복제본마저 고장 나면 그 쓰기를 잃을 수 있다고 설명합니다. acks=0은 프로듀서가 서버의 응답을 기다리지 않는 설정이고 acks=1은 리더가 자기 로그에 쓰고 팔로워의 확인을 기다리지 않고 응답하는 설정입니다. 두 값이 정하는 것은 프로듀서가 응답을 기다리는 범위입니다.
• min.insync.replicas는 acks=all일 때 쓰기가 성공하는 데 필요한 동기화된 복제본의 최소 수이고 기본값은 1입니다. 제한이 없는 구성에서는 ISR이 리더 하나로 줄어도 조건을 채우므로 쓰기가 계속 성공합니다. 약해지는 것은 지속성입니다. 활성을 내주는 것은 이 값을 올렸을 때입니다. ISR의 수가 값에 못 미치면 프로듀서가 NotEnoughReplicas 예외를 받습니다.
• min.insync.replicas를 과반으로 두면 단일 파티션이 선형이 된다는 문장은 공식 문서에 없습니다. 문서는 복제 팩터 3, min.insync.replicas 2, acks=all 구성을 쓰기가 성공했다고 보기 전에 과반이 영속화하는 구성으로만 설명합니다. 설계 문서는 Kafka가 동기화된 복제본 집합(ISR)을 동적으로 유지하는 방식으로 쿼럼을 정하고 복제본 f+1개로 f번의 고장을 커밋된 메시지를 잃지 않고 견딘다고 적습니다. 소비자는 기본적으로 리더에서 읽지만 replica.selector.class로 팔로워 읽기를 허용할 수 있고 팔로워에서 읽으면 선형 읽기가 아닙니다.

복제를 구현하면서 Kafka는 부분 실패의 처리인 구성원 변경을 외주로 돌렸습니다. 데이터 노드의 리더 교체는 Controller에 맡겨 Controller가 새 리더 복제본을 지정합니다. Controller 노드 자신은 외부의 선형 저장소 ZK에 그 책임을 맡겨 ZK가 주는 잠금과 리스 서비스로 합의를 구현하고 리더를 선출합니다. 이후 버전에서는 Kafka가 외부 합의 서비스를 없애고 합의 알고리즘으로 Controller 선출을 스스로 구현합니다. ZK에 기대던 메타데이터도 Kafka 자체의 KRaft가 구현한 선형 저장소에서 스스로 관리합니다.

시기는 세 문서에 나뉘어 있습니다. KRaft는 3.3에서 새 클러스터에 대해 프로덕션 준비 상태로 선언됐다고 KIP-833이 적습니다. Kafka 4.0은 ZooKeeper 없이 도는 첫 메이저 릴리스라고 Kafka 4.0 발표문이 밝힙니다. ZooKeeper에서 KRaft로 옮기려면 브리지 릴리스를 거쳐야 하고 마지막 브리지 릴리스는 3.9라고 Kafka 운영 문서가 적습니다.

외부 일관성의 범주에서 초기 Kafka에는 트랜잭션 비슷한 기능이 없어서 다중 객체 트랜잭션을 지원하지 못합니다. 이후 버전에서 트랜잭션 구현이 추가되었습니다(원문은 “blog”라는 링크로 다른 글을 가리킵니다). 객체가 여러 기계에 걸치므로 2PC를 구현해야 하며 TransactionCoordinator를 도입해 조정자를 맡게 했습니다. 위의 2PC 기본 흐름을 참고하라고 원문은 말합니다.

원문이 그리는 대략의 구현 흐름은 이렇습니다. 먼저 조정자에게서 트랜잭션 ID를 얻습니다. 그다음 참가자에게 그 ID를 붙여 커밋 준비를 요청합니다. 참가자는 먼저 로컬에 append하고 성공하면 응답합니다. 조정자가 결정 내용을 영속화한 뒤 결정을 실행하고 참가자가 메시지를 로그에 실제로 씁니다(커밋된 것만 읽는 컨슈머가 읽을 수 있는 끝인 LSO를 갱신하며 이 위치는 하이 워터마크와 다릅니다).

이 흐름은 KIP-98과 세부가 다릅니다. ID(transactional.id)는 사용자가 프로듀서(메시지를 쓰는 클라이언트) 설정에 정하고 조정자는 InitPidRequest에 프로듀서 번호(PID)와 에포크를 돌려줍니다. 이때 같은 ID의 옛 프로듀서는 에포크가 올라 걸러집니다. 프로듀서는 AddPartitionsToTxn으로 파티션을 등록하고 데이터는 일반 쓰기로 해당 파티션의 로그에 곧바로 기록됩니다. 조정자는 PREPARE_COMMIT이나 PREPARE_ABORT를 트랜잭션 로그에 쓰고 사용자 로그에 COMMIT이나 ABORT 마커를 쓰고 마지막에 COMMITTED나 ABORTED를 트랜잭션 로그에 씁니다. 결정을 먼저 기록한다는 순서는 원문과 같습니다. 달라지는 곳은 메시지가 커밋 전에 이미 로그에 있고 커밋 때 쓰이는 것이 마커라는 점입니다. 아래 실행에서 커밋 전 메시지를 기본 설정의 컨슈머(메시지를 읽는 클라이언트)가 1ms 안에 읽었습니다.

2PC에는 문제가 있다고 원문은 앞에서 말했습니다. 먼저 조정자가 단일 장애점인 문제를 Kafka는 간단히 풉니다. 단일 파티션의 동기 복제가 선형 일관성을 보장하는 성질을 이용해 조정자의 상태를 내부 토픽에 저장해 두었다가 조정자가 죽으면 곧바로 옮겨 토픽에서 복구합니다. 토픽은 단일 파티션으로 보면 선형 저장소이기 때문이라고 원문은 설명합니다. 문서가 말하는 것은 트랜잭션 로그가 모든 트랜잭션을 복제해 영속적으로 기록하며 조정자의 상태 저장소라는 점까지입니다. 선형성을 명시한 문장은 없습니다.

또 하나는 2PC의 조정자가 본질적으로 단일 리더 복제 과정이라는 점입니다. TransactionCoordinator는 원래 Broker에 얹혀 있으므로 이 선출도 Controller에 위임되고 2PC의 까다로운 문제를 이렇게 풉니다. 트랜잭션의 격리 수준에서는 Kafka가 읽기 커밋(RC) 수준까지만 구현했다고 원문은 쓰는데 컨슈머의 isolation.level 기본값은 read_uncommitted이고 read_committed는 따로 켜야 합니다. 또 read_committed는 LSO까지만 읽는다는 뜻이어서 DB의 읽기 커밋과 같은 말이 아닙니다.

이 차이를 Kafka 한 대에서 재 보니 트랜잭션이 열려 있는 동안 무관한 메시지도 함께 늦었습니다. Kafka 트랜잭션은 여러 파티션에 쓰는 메시지를 모두 보이게 하거나 모두 안 보이게 합니다. 메시지는 커밋 전에 이미 파티션의 로그에 쓰입니다. 그래서 컨슈머도 커밋된 것만 읽도록 설정해야 하고 그렇게 설정한 컨슈머는 열린 트랜잭션 뒤의 메시지를 전부 기다립니다.

Kafka 3.9 한 대에 파티션 하나짜리 토픽을 만들고 컨슈머 둘을 붙였습니다. 하나는 격리 수준이 기본값인 read_uncommitted이고 다른 하나는 read_committed입니다. LSO(last stable offset)는 read_committed 컨슈머가 읽을 수 있는 끝이고 하이 워터마크는 복제가 끝난 위치입니다.

네 가지 상황을 만들었습니다. 트랜잭션을 열어 메시지 둘을 보내고 다른 프로듀서로 트랜잭션 밖의 일반 메시지 하나를 보낸 뒤 5초 뒤에 커밋하는 경우, 같은 순서로 보내고 5초 뒤에 중단하는 경우, 열린 트랜잭션이 없는 경우, 트랜잭션을 연 프로듀서가 커밋 없이 죽는 경우입니다. 표의 시간은 프로듀서의 전송이 확인된 때부터 각 컨슈머가 그 메시지를 받기까지입니다.

문서에 따르면 LSO는 가장 먼저 열린 트랜잭션의 첫 메시지 바로 앞이고 그 뒤의 메시지는 트랜잭션이 끝날 때까지 보류됩니다. 표의 둘째 줄에서 트랜잭션과 무관한 메시지가 함께 늦은 까닭입니다.

표의 마지막 두 줄은 프로듀서가 죽었을 때입니다. 조정자는 transaction.timeout.ms가 지난 뒤에 주인 없는 트랜잭션을 중단시킵니다. 이 값을 10초로 줄였을 때 read_committed 컨슈머는 11.2초 뒤에 다음 메시지를 받았고 기본값인 60초에서는 69.8초 뒤에 받았습니다. 같은 transactional.id의 프로듀서가 다시 뜨면 조정자가 남은 트랜잭션을 바로 정리하므로 이 시간은 프로듀서가 돌아오지 않을 때의 길이입니다.

표의 셋째 줄은 기본 설정의 결과입니다. read_uncommitted 컨슈머는 중단된 트랜잭션의 메시지를 받았습니다. 프로듀서만 트랜잭션을 쓰고 컨슈머의 설정을 그대로 두면 중단된 메시지가 처리됩니다.

Confluent는 트랜잭션에 드는 비용을 조건과 함께 내놓았습니다. 1KB 메시지를 최대 처리량으로 보내면서 100ms마다 커밋하면 처리량이 3% 줄어듭니다. 메시지가 작거나 커밋 간격이 짧으면 더 줄어든다고 합니다. 커밋 간격을 늘리면 처리량 손실은 줄어들고 위 표에서 본 대로 read_committed 컨슈머가 기다리는 시간이 커밋 간격만큼 늘어납니다.

물러난 프로듀서를 막는 데는 앞에서 본 에포크가 쓰입니다. 같은 transactional.id로 새 프로듀서가 등록하면 조정자가 에포크를 올리고 옛 에포크의 프로듀서가 보내는 요청을 거절합니다.

에포크를 프로듀서 단위로만 올려서는 막지 못하는 경우가 있었습니다. KIP-890에 따르면 네트워크에서 늦게 도착한 메시지 때문에 LSO가 나아가지 못하고 read_committed 컨슈머가 멈추는 일이 실제로 있었습니다. KIP-890이 정한 해법은 커밋이나 중단을 기록할 때마다 프로듀서의 에포크를 올리는 것입니다.

분산 시스템 검증 프레임워크

분산 알고리즘을 검증하는 도구가 업계에 둘 있고 원문은 이 둘을 뛰어난 도구로 소개합니다. 하나는 화이트박스 모델링 도구인 TLA+입니다. 원문은 Lamport의 영상 강의(번역 자막이 있습니다)와 『Specifying Systems』를 권합니다. TLA+는 분산 알고리즘을 넘어 컴퓨터 시스템 전체를 정의할 수 있는 언어이며 수학으로 시스템을 정의하는 능력을 익히면 코드 세부에서 벗어나 상태 기계의 사고로 시스템을 보게 되어 색다른 깨달음을 얻을 수 있다고 합니다. TLA+의 핵심은 집합론과 수리 논리와 상태 탐색으로 시스템의 동작을 정의하는 것입니다. 시스템이나 알고리즘을 올바르게 추상화하고 형식 명세를 준 다음 TLA+로 검증합니다.

TLA+는 가능한 모든 실행 순서를 탐색합니다. Amazon은 2014년 보고서에서 TLA+로 찾은 버그를 소개했습니다. DynamoDB의 고장 대응 알고리즘에서 고장과 복구가 특정 순서로 다른 처리와 겹치면 데이터를 잃는 버그가 나왔고 이 버그를 드러내는 가장 짧은 실행이 35단계였습니다. 보고서는 이 버그가 설계 검토, 코드 검토, 테스트를 모두 통과했다고 덧붙입니다.

The bug had passed unnoticed through extensive design reviews, code reviews, and testing

PingCAP도 Raft와 TiDB의 2PC를 TLA+로 적은 명세를 공개 저장소에 두고 있습니다.

다른 하나는 블랙박스 도구 Jepsen입니다. 핵심 원리는 클라이언트를 여럿 만들어 저장 시스템에 정상적인 읽기와 쓰기를 하게 하고 연산마다 결과를 기록한 뒤 시험 중간에 고장을 넣은 뒤 마지막에 이 연산 이력이 여러 일관성의 규정을 만족하는지 검사하는 것입니다. 원문은 아키텍처를 간단히 본 뒤 사용법을 대략 시연한다고 합니다. Jepsen은 다음 모듈로 구성됩니다.

• DB Node: 엔진 자체의 노드, 곧 저장 노드입니다.
• Control Node: 제어 노드로 클라이언트, 연산, 고장을 생성하고 보통 DB Node와 비밀번호 없는 SSH로 연결됩니다.
• Client: 정상적인 읽기와 쓰기를 하는 클라이언트입니다.
• Generator: 계획을 생성합니다.
• Nemesis: 고장을 만드는 구성 요소입니다.
• Checker: 마지막에 일관성을 검증합니다.

Jepsen은 돌아가는 시스템에 고장을 넣고 기록된 연산들이 선형성 같은 성질을 지켰는지 검사합니다. 앞에서 본 Jepsen의 etcd 분석에서는 한 시스템 안에서도 결과가 갈렸습니다. 키와 값을 읽고 쓰는 연산은 엄격한 직렬성을 지키는 것으로 보였고 잠금은 안전하지 않았습니다. 같은 합의 위에 올린 기능이라도 성질은 기능마다 따로 확인해야 합니다.

원문의 팀은 Jepsen으로 Kafka의 일관성을 시험했다고 합니다. Kafka 클라이언트와 서버 설정은 동기 복제(ack=-1)와 복제 팩터 3(복제본 수)과 최소 가용 복제본 2였으며 이 설정에서 Jepsen에 내장된 고장 주입을 모두 통과했다고 합니다. 설정 이름은 min.insync.replicas이고 원문의 min.insync.isr은 오타입니다. 통과했다는 서술은 팀 내부 시험이라 공개된 근거를 찾지 못했습니다(없다고 단정하지는 않습니다). Jepsen의 분석 목록에서 Kafka를 직접 시험한 글은 2013년에 출시 전 판(0.8 beta)을 다룬 Kyle Kingsbury의 글 하나입니다. ISR이 비어 새 노드를 리더로 뽑으면 리더 사이의 인과 불변식이 깨져 데이터를 잃는다고 그 글은 분석합니다. 그 뒤로는 Kafka와 호환되는 시스템 둘을 분석하면서 Kafka 쪽의 문제를 함께 적었습니다. 2022년 Redpanda 분석은 Kafka의 기본 설정이 디스크에 내려쓰기 전에 쓰기를 확인할 수 있다고 적었습니다. 2024년 Bufstream 분석은 트랜잭션 프로토콜에서 쓰기 유실과 중단된 트랜잭션이 읽히는 문제를 찾아 Kafka 이슈로 올렸습니다. 시험을 통과했다는 말은 시험한 조건 안에서 나온 결과로 읽습니다.

이 글의 실행은 고장 주입을 가장 작게 해 본 것입니다. 실험마다 무엇이 나올지를 먼저 적어 두었습니다. 끊긴 노드의 직렬 읽기는 옛 값을 돌려주고 선형 읽기는 실패할 것, 조정자가 비운 만큼 다른 쓰기가 막힐 것, 열린 트랜잭션이 끝날 때까지 read_committed 컨슈머는 일반 메시지도 받지 못할 것 같은 열네 가지입니다. 열한 가지는 첫 실행 전에 적었고 리더를 끊는 독립 요청 탐침의 세 가지는 앞선 두 탐침의 결과를 본 뒤 그 탐침을 돌리기 전에 적었습니다. 방향이 어긋난 것은 하나였습니다. 끊은 직후에 보낸 쓰기는 7초 뒤 실패하고 그 뒤 새 리더가 뽑히기 전에 보낸 쓰기는 기다렸다가 성공할 것이라고 적었는데 뒤쪽 쓰기도 7초 뒤 실패했고 66건 가운데 성공한 것은 1건이었습니다. 선형 읽기의 시간은 10ms와 20ms 안팎으로 적었고 결과는 12ms와 25ms 안팎이었습니다.

소결

원문은 이 데이터 여행이 여기서 일단락된다며 독자가 일반적인 분산 시스템의 핵심 문제와 이 문제들 앞에서 트랜잭션, 일관성, 합의가 푸는 것과 그 셋이 어떻게 이어지는지를 알게 되길 바란다고 합니다. 또 적절한 때에 검증 도구나 프레임워크로 시스템의 정확성과 활성을 검증할 수 있기를 바라며 그것이 두 편 시리즈의 목적이라고 말합니다.

분산 시스템은 덩치가 커서 부분으로 나눠 하나씩 익혀야 설계를 제대로 장악할 수 있다고 원문은 덧붙입니다. 끝으로 이런 사고를 체계적으로 산출해 낸 팀원들에게 감사하며 팀 안의 기술 공유 문화와 기술을 깊이 파고드는 분위기 덕이라고 말하고 메이퇀 기술팀에 합류하기를 환영한다고 맺습니다. 원문 끝에는 저자 소개가 있습니다. 仕禄은 메이퇀 기초 연구개발 플랫폼 데이터 과학과 플랫폼부의 엔지니어입니다.

원문에서 고쳐 읽을 곳

원문의 서술을 공식 문서와 논문과 이 글의 실행 결과와 대조해 고쳐 적은 곳이 모두 스물여덟 곳입니다. 판정 열의 오류는 원문이 틀린 곳이고 조건 보충은 조건을 덧붙여야 맞는 곳이며 보충은 틀리지는 않았지만 채워 읽을 곳입니다. 오류가 열네 곳, 조건 보충이 아홉 곳, 보충이 다섯 곳입니다. 마지막 열은 고쳐 적은 절입니다.

실행한 조건과 한계

• 모두 Apple Silicon 맥(12코어) 위의 리눅스 가상 머신(CPU 4, 메모리 6GiB) 한 대에서 컨테이너로 실행했습니다. 본문의 수치는 2026년 10월 12일 05:22부터 05:38 사이에 다시 실행한 결과이고 두 스크립트의 시작과 끝에 읽은 맥의 1분 부하 평균은 3.5~5.9였습니다.
• 한 시간 전의 첫 실행에서 가져온 수치가 둘 있습니다. 리더를 끊었을 때 옛 리더에 보낸 요청의 결과와 재시도하는 탐침의 1.2~1.6초입니다. 그 두 수치를 잰 구간이 끝났을 때의 부하 평균은 17.6이었습니다. 첫 실행의 지연, 잠금 대기, Kafka 수치는 다시 실행한 결과와 가까웠습니다. 첫 실행의 재시작 실험은 데이터를 메모리 파일 시스템에 둔 탓에 재시작과 함께 지워져 디스크 볼륨으로 바꿔 다시 실행했습니다.
• etcd는 3.5.17 세 대이고 데이터는 메모리 파일 시스템에 두었습니다. 디스크에 내려쓰는 시간이 실제 디스크에서보다 짧으므로 쓰기와 선형 읽기의 시간에는 네트워크 왕복이 대부분을 차지합니다. 지연은 노드 사이 인터페이스에만 편도 5ms를 넣어 만들었고 요청은 클라이언트 하나가 HTTP 게이트웨이로 보냈습니다.
• 노드를 끊을 때는 한 대를 노드 사이 네트워크에서 떼어 냈습니다. 한 방향만 끊기거나 일부 패킷만 사라지는 경우는 재현하지 않았습니다. 끊긴 노드를 다시 이은 뒤에도 12초 넘게 옛 값을 돌려준 적이 있는데 컨테이너의 네트워크를 다시 붙이는 방식에서 온 시간일 수 있어 본문의 결과에 넣지 않았습니다.
• 리더를 끊는 표에서 리더를 끊은 정확한 시각은 재지 않았습니다. 구간의 시작은 처음 영향받은 요청을 보낸 시각입니다. 처음에는 응답을 1.5초만 기다리고 다시 보내는 탐침으로 쟀고 그 결과를 “쓰기가 1.2~1.6초 멈췄다가 이어졌다”로 읽었습니다. 재시도를 뺀 탐침으로 다시 재서 요청이 7초 뒤 실패한다는 것을 확인했습니다.
• PostgreSQL은 16.15이고 max_prepared_transactions를 10으로 켰습니다. 이 값의 기본은 0이어서 준비된 트랜잭션은 따로 켜야 쓸 수 있습니다. 첫 DB는 재시작 실험 때문에 디스크 볼륨에, 둘째 DB는 메모리 파일 시스템에 두었습니다. 두 DB에 걸친 2PC는 스크립트가 조정자 노릇을 했고 트랜잭션 관리자 제품은 쓰지 않았습니다.
• Kafka는 3.9.0 한 대이고 ZooKeeper 없이 도는 KRaft 방식입니다. 클라이언트는 librdkafka 2.16.0입니다. 브로커가 한 대여서 복제와 조정자 교체는 일어나지 않았습니다. Kafka 표의 “1ms 이내”에는 전송 확인 시각을 적기 전에 컨슈머가 먼저 받아 -1ms로 찍힌 값이 하나 들어 있습니다.
• 원문을 고쳐 적은 근거는 2026년 10월 12일에 받아 읽은 공식 문서와 논문입니다. DDIA는 영어 2판 초안과 1판 중국어 번역의 저장소 사본으로 읽었고 1판 영어 원문은 구하지 못했습니다. MySQL 문서는 Web Archive의 2024년 8.0 스냅샷이고 8.4 문서는 보지 못했습니다. InnoDB 반복 읽기의 갱신 손실은 문서에 그 단어가 쓰인 문장을 찾지 못해 추론으로 적었습니다. Kafka의 설정 표는 3.9 문서를, 설계 문서와 운영 문서는 4.1 문서를 읽었습니다. 원문 팀의 Jepsen 시험은 공개 자료를 찾지 못했습니다.
• 회사 사례의 수치는 각 회사가 공개한 글과 논문에서 가져왔습니다.

참고

원문

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

회사 사례

• Google, Paxos Made Live: An Engineering Perspective (2007)
• Roblox, Roblox Return to Service 10/28-10/31 2021 (2022)
• Amazon, Use of Formal Methods at Amazon Web Services (2014)
• PingCAP, TiDB 5.0 Release Notes, pingcap/tla-plus
• OceanBase: A 707 Million tpmC Distributed Relational Database System (VLDB 2022)
• Tencent, PaxosStore: High-availability Storage Made Practical in WeChat (VLDB 2017)
• 美团, Leaf——美团点评分布式ID生成系统 (2017)
• 美团, 消息队列设计精要 (2016)
• SOFAJRaft 사용 안내
• Confluent, Transactions in Apache Kafka (2017)

논문과 분석

• Gray & Lamport, Consensus on Transaction Commit (2004)
• Lamport, Time, Clocks, and the Ordering of Events in a Distributed System (1978)
• Berenson et al., A Critique of ANSI SQL Isolation Levels (1995)
• Gilbert & Lynch, Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (2002)
• Martin Kleppmann, A Critique of the CAP Theorem (2015)
• Brewer, CAP Twelve Years Later: How the Rules Have Changed (2012)
• Fischer, Lynch, Paterson, Impossibility of Distributed Consensus with One Faulty Process (1985)
• Chandra & Toueg, Unreliable Failure Detectors for Reliable Distributed Systems (1996)
• Martin Kleppmann, How to do distributed locking (2016)
• Jepsen, etcd 3.4.3 (2020)
• Jepsen, Serializable
• Kyle Kingsbury, Call me maybe: Kafka (2013)
• Jepsen, Redpanda 21.10.1 (2022), Jepsen, Bufstream 0.1.0 (2024)
• Jepsen, Consistency Models, Sequential
• Google, Spanner: Google’s Globally-Distributed Database (2012)

공식 문서

• etcd, KV API guarantees, Configuration options (election-timeout), etcd-io/raft README
• ZooKeeper Programmer’s Guide: Consistency Guarantees
• PostgreSQL, Transaction Isolation, PREPARE TRANSACTION (16)
• MySQL 8.0, InnoDB Consistent Nonlocking Reads
• Apache Kafka, Consumer Configs (isolation.level), Producer Configs (acks, transaction.timeout.ms), Topic Configs (min.insync.replicas)
• Apache Kafka 4.0.0 Release Announcement (2025)
• Apache Kafka 4.1 Documentation, Design의 Replication, Operations의 ZooKeeper에서 KRaft로 이전
• KIP-98: Exactly Once Delivery and Transactional Messaging
• KIP-833: Mark KRaft as Production Ready
• KIP-890: Transactions Server-Side Defense
• Martin Kleppmann, Designing Data-Intensive Applications