📚 지식 노트

선형성과 직렬성은 다르다

복제본이 여럿이면 "지금 값"이 복제본마다 다를 수 있다. 일관성 모델은 클라이언트가 볼 수 있는 결과의 범위를 정하는 약속이다. 가장 강한 약속인 선형성(linearizability)은 Herlihy와 Wing의 1990년 논문 「Linearizability: A Correctness Condition for Concurrent Objects」가 정의했다. 각 연산이 시작과 끝 사이 어느 한 순간에 원자적으로 일어난 것처럼 보여야 하고, 그 순간들은 실제 시간 순서를 따라야 한다. 쉽게 말해 복제본이 여럿이어도 사본이 하나뿐인 것처럼 보인다.

• 선형성: 객체(키) 하나에 대한 최신성 보장이다. 끝난 쓰기는 그 뒤 시작한 모든 읽기에 보인다. 리더 선출용 잠금, 유일성 제약(같은 아이디 두 번 가입 막기), 재고처럼 "지금 이 값"이 중요한 곳에 필요하다.
• 직렬성(serializability): 여러 객체를 고치는 트랜잭션들의 결과가 어떤 순서로 하나씩 실행한 결과와 같다는 격리 보장이다. 그 순서가 실제 시간과 같을 필요는 없다. 자세한 것은 동시성 제어 노트에 있다.
• 엄격한 직렬성(strict serializability): 둘을 함께 주는 것이다. Jepsen의 일관성 모델 지도는 엄격한 직렬성이 직렬성과 선형성을 모두 함의한다고 정리하고, 모델마다 분할 중에도 쓸 수 있는지를 색으로 보여 준다.

선형성은 비싸다. 쓰기와 읽기가 과반의 확인을 기다려야 하고, 네트워크가 갈라지면 소수 쪽은 답할 수 없다(복제와 합의 노트의 CAP 절). 그래서 꼭 필요한 곳에만 쓰고 나머지는 더 약한 모델로 지연과 가용성을 얻는다.

인과 일관성과 결과적 일관성

가장 약한 쪽 끝은 결과적 일관성(eventual consistency)이다. 쓰기가 멈추면 언젠가 모든 복제본이 같은 값이 된다는 것만 약속한다. Werner Vogels의 2008년 글 「Eventually Consistent」가 Amazon의 경험으로 이 모델과 그 변형들을 정리했다. "언젠가"가 언제인지, 그 사이 무엇이 보이는지는 말하지 않는다.

그 사이에 있는 실용적인 모델이 인과 일관성(causal consistency)이다. 어떤 쓰기가 다른 쓰기를 보고 일어났다면(원인과 결과), 모든 클라이언트는 원인을 결과보다 먼저 본다. 서로 관계없는 동시 쓰기의 순서는 복제본마다 달라도 된다.

인과 일관성은 분할 중에도 지킬 수 있다는 점이 크다. Jepsen의 Causal 항목에 따르면 클라이언트가 같은 서버에 붙어 있는 한(sticky available) 갈라진 쪽에서도 계속 진행할 수 있다. 2011년 COPS 논문 「Don't Settle for Eventual」은 쓰기마다 그 쓰기가 의존한 버전을 함께 실어 보내고, 다른 데이터센터는 의존한 쓰기가 먼저 적용된 뒤에야 그 쓰기를 보여 주는 방식으로 지역 간 인과 일관성을 구현했다.

세션 보장

사용자 한 명 입장에서 가장 거슬리는 이상 현상은 대개 자기 행동과 관련된 것이다. 1994년 Bayou 프로젝트의 「Session Guarantees for Weakly Consistent Replicated Data」는 이를 한 세션 안의 네 가지 보장으로 나눴다. 전체 시스템은 결과적 일관성이어도 세션마다 이 보장만 지키면 사용자는 대부분 이상함을 느끼지 않는다.

• 구현: 세션이 지금까지 읽고 쓴 버전(또는 쓰기 번호)을 클라이언트가 들고 다니다가 요청에 실어 보낸다. 복제본은 그 버전까지 따라오지 못했으면 기다리거나 다른 복제본으로 넘긴다.
• 흔한 지름길: 방금 쓴 사용자의 읽기는 몇 초 동안 리더로 보내거나, 사용자를 늘 같은 복제본에 붙인다. 다만 사용자가 휴대폰과 노트북을 함께 쓰면 "세션"이 기기를 건너야 해서, 버전을 서버 쪽에 적어 두어야 한다.

믿을 수 없는 시계

서버마다 시계가 있으니 시각으로 순서를 정하면 될 것 같지만, 컴퓨터의 시계는 수정 진동자로 재는 근삿값이라 온도에 따라 빠르거나 느리게 간다. 그래서 NTP로 주기적으로 맞추는데, NTPv4 명세(RFC 5905)는 서버와 클라이언트가 수십 밀리초 안으로 맞는다고 적는다. 거꾸로 말하면 잘 관리해도 서버끼리 그 정도는 어긋날 수 있고, NTP 서버에 닿지 못하거나 설정이 틀리면 훨씬 더 벌어진다.

• 두 종류의 시계: Linux clock_gettime(2)의 CLOCK_REALTIME은 날짜와 시각을 주지만 관리자나 NTP가 값을 바꾸면 불연속으로 뛸 수 있다. CLOCK_MONOTONIC은 그런 점프 없이 늘 앞으로 가므로 시간 초과나 응답 시간처럼 경과 시간을 잴 때 쓴다. 다만 그 절대값은 서버끼리 비교할 수 없다.
• 시간이 거꾸로 가면: Cloudflare는 2017년 새해 윤초 때 DNS 서버가 벽시계로 잰 경과 시간이 음수가 되어 프로그램이 멈춘 사고를 사후 분석으로 공개했다. 경과 시간은 반드시 단조 시계로 재야 한다는 교훈이다.
• 시각으로 순서 정하기: 마지막 쓰기 승리(LWW)는 찍힌 시각이 큰 쪽을 남기는데, 시계가 빠른 노드의 쓰기가 늘 이긴다. 진 쪽은 오류 없이 조용히 사라진다.
• 시각의 오차를 드러내기: Google Spanner의 TrueTime은 시각 하나 대신 "이 구간 안 어딘가"를 돌려주고, 커밋 때 그 구간의 폭만큼 기다려 순서를 보장한다(클라우드 데이터베이스 노트의 Spanner 절).

논리 시계: 램포트와 벡터

순서가 필요할 뿐 실제 시각은 필요 없다면 물리 시계를 버리고 논리 시계를 쓴다. Leslie Lamport의 1978년 논문 「Time, Clocks, and the Ordering of Events in a Distributed System」은 "먼저 일어남"(happened-before)을 정의했다. 같은 프로세스 안의 앞선 사건, 그리고 메시지를 보낸 사건은 받은 사건보다 먼저 일어났고, 이 관계는 이어진다. 어느 쪽으로도 이어지지 않는 두 사건은 동시(concurrent)다.

1. 램포트 시계: 프로세스마다 카운터 하나를 두고 사건마다 1 올린다. 메시지에는 카운터를 싣고, 받은 쪽은 max(내 값, 받은 값) + 1로 맞춘다. a가 b보다 먼저 일어났으면 L(a) < L(b)가 늘 성립한다. 같은 값이면 프로세스 id로 순서를 정해 모든 사건의 전체 순서를 만들 수 있다.
2. 한계: 거꾸로는 성립하지 않는다. L(a) < L(b)여도 둘이 동시일 수 있다. 위 그림의 C2(L=2)와 B2(L=4)가 그런 예다. 그래서 램포트 시계만으로는 "이 두 쓰기가 충돌하는가"를 알 수 없다.
3. 벡터 시계: 프로세스마다 모든 프로세스 몫의 칸을 가진 벡터를 둔다. 사건마다 자기 칸을 올리고, 받을 때는 칸마다 큰 값을 고른 뒤 자기 칸을 올린다. 모든 칸이 작거나 같으면 앞선 사건, 어느 쪽도 아니면 동시다. Friedemann Mattern의 1988년 논문 「Virtual Time and Global States of Distributed Systems」와 같은 해 Colin Fidge가 각각 내놓았다.

벡터 시계는 리더 없는 복제에서 같은 키에 동시에 들어온 쓰기를 찾아내는 데 쓰인다. 동시인 두 값은 하나를 버리지 않고 둘 다 남겨 응용 프로그램이나 CRDT 같은 병합 규칙이 합치게 한다. 단계 그림의 값은 src/lib/sysdesign/clocks.ts가 계산하고, 테스트가 벡터 비교 결과를 각본에서 직접 구한 먼저 일어남 관계와 대조한다.

리스와 펜싱 토큰

"한 번에 한 클라이언트만 이 파일을 고친다" 같은 규칙은 보통 시간 제한이 붙은 잠금, 곧 리스(lease)로 지킨다. 리스를 쥔 클라이언트가 죽어도 시간이 지나면 다른 클라이언트가 이어받을 수 있다. 문제는 클라이언트가 죽은 것이 아니라 잠깐 멈췄을 때다. 가비지 컬렉션, 가상 머신 일시 정지, 디스크 대기로 몇 초 멈춘 프로세스는 깨어난 뒤에도 자기가 아직 리스를 쥐고 있다고 믿는다.

해법은 잠금을 쥔 쪽의 믿음에 기대지 않고 받는 쪽이 검사하는 것이다. 리스와 함께 단조 증가하는 펜싱 토큰을 주고, 저장소는 요청마다 실린 토큰이 지금까지 본 가장 큰 값보다 작으면 거절한다. Martin Kleppmann은 2016년 글 「How to do distributed locking」에서 이 방식을 설명하며, 시계 가정에 기대는 잠금 알고리즘은 이런 멈춤 앞에서 안전하지 않다고 지적했다. ZooKeeper의 트랜잭션 id나 etcd의 리비전처럼 합의 기반 저장소가 주는 번호는 그대로 펜싱 토큰으로 쓸 수 있다.

전체 순서 브로드캐스트와 합의

여러 노드가 같은 상태를 유지하는 가장 단순한 방법은 모든 노드가 같은 메시지를 같은 순서로 받아 적용하는 것이다. 이것을 전체 순서 브로드캐스트(total order broadcast)라 한다. 데이터베이스 복제 로그, Kafka 파티션 하나, Raft 로그가 모두 이 모양이다. 램포트 시계도 전체 순서를 만들지만, 순서가 확정되는 시점을 모른다는 것이 문제다. 더 작은 번호의 메시지가 아직 오는 중일 수 있기 때문이다.

• 왜 합의가 필요한가: 로그의 다음 칸에 무엇이 들어갈지를 모든 노드가 하나로 정하는 일이 곧 합의다. 반대로 전체 순서 브로드캐스트가 있으면 "먼저 로그에 적힌 제안이 이긴다"로 합의를 만든다. 선형 CAS 레지스터도 같은 힘을 가진다.
• 불가능성: Fischer, Lynch, Paterson의 1985년 논문 「Impossibility of Distributed Consensus with One Faulty Process」(FLP)는 메시지 지연에 한계가 없는 비동기 모델에서는 한 프로세스만 멈출 수 있어도 늘 끝나는 결정적 합의 알고리즘이 없음을 보였다. 그래서 실제 알고리즘은 안전성(틀린 결정은 절대 없음)은 늘 지키고, 진행(언젠가 결정함)은 네트워크가 충분히 안정적일 때만 보장한다.
• 실제 구현: Raft와 Paxos가 이 역할을 한다. 임기, 선거, 과반 복제는 복제와 합의 노트의 Raft 절에서 단계 그림으로 다룬다. 응용 프로그램은 합의를 직접 짜지 않고 etcd나 ZooKeeper 같은 조정 서비스를 빌려 리더 선출, 잠금, 설정 저장에 쓴다.