📚 지식 노트

리더-팔로워 복제

같은 데이터를 여러 서버에 두는 복제(replication)는 세 가지를 위해서다. 한 대가 죽어도 버티고(가용성), 읽기를 나눠 받고(확장), 사용자 가까이에 둔다(지연). 가장 흔한 모양은 쓰기를 한 대(리더, primary)만 받고 나머지(팔로워, replica)는 리더가 보내는 변경 기록을 순서대로 적용하는 방식이다. 변경 기록으로는 대개 저장 엔진의 WAL이나 논리적인 행 변경 기록을 쓴다(저장 엔진 노트).

• 동기와 비동기: 모든 팔로워를 동기로 두면 한 대만 느려도 쓰기가 멈춘다. 그래서 보통 하나만 동기(반동기)로 두거나 전부 비동기로 둔다. 비동기에서 리더가 죽으면 팔로워에 아직 안 간 커밋이 사라질 수 있다.
• 복제 지연(replication lag): 비동기 팔로워에서 읽으면 방금 쓴 글이 안 보이거나(자기 쓰기 읽기 위반), 새로 고칠 때마다 다른 팔로워에 붙어 시간이 거꾸로 가는 것처럼 보일 수 있다. 자기가 쓴 데이터는 리더에서 읽거나, 한 사용자를 한 팔로워에 붙여 둔다.
• 장애 조치(failover): 리더가 죽으면 가장 앞선 팔로워를 새 리더로 올리고 나머지가 따르게 한다. 어려운 것은 "죽었다"는 판단이다. 잠깐 느렸을 뿐인 옛 리더가 돌아와 자기가 리더라고 믿으면 두 리더가 각자 쓰기를 받는 분할 뇌(split brain)가 된다. 이를 막으려고 다음 절의 합의를 쓴다.

PostgreSQL 문서의 Comparison of Different Solutions가 공유 디스크, WAL 전송, 논리 복제 등 여러 방식의 장단점을 표로 비교한다.

다중 리더와 리더 없는 복제

여러 데이터센터에서 저마다 쓰기를 받으려면 리더를 여럿 둔다(다중 리더). 지역마다 빠르게 쓰지만 같은 행을 두 곳에서 고치면 충돌이 나고, 마지막 쓰기 승리(last write wins)처럼 한쪽을 버리거나 응용 프로그램이 합쳐야 한다.

아예 리더 없이 아무 복제본에나 쓰는 방식도 있다(리더 없는 복제). Amazon의 2007년 논문 「Dynamo: Amazon's Highly Available Key-value Store」가 알린 설계로, Cassandra 같은 데이터베이스가 따른다. 복제본 N개 중 W개가 쓰기를 확인하면 성공, 읽을 때는 R개에 물어 가장 새 버전을 고른다. R + W > N이면 읽는 집합과 쓴 집합이 반드시 한 곳 이상 겹치므로 최신 쓰기를 만난다.

R + W > N은 최신 쓰기를 "만날" 수 있다는 보장일 뿐, 선형 일관성(모든 연산이 한 줄로 늘어선 것처럼 보이는 성질)까지 주지는 않는다. 쓰기가 일부 복제본에만 닿은 채 실패하거나, 동시에 쓴 두 값의 순서를 시계로 정하거나, 죽은 복제본 대신 임시로 받은 노드(sloppy quorum)가 끼면 옛 값이 보일 수 있다. 어긋난 복제본은 읽을 때 고치거나(읽기 복구) 배경에서 비교해 맞춘다(anti-entropy).

샤딩

복제는 같은 데이터를 늘릴 뿐이라 데이터 자체가 한 대에 안 들어가거나 쓰기가 한 대로 감당이 안 되면 소용없다. 그때는 데이터를 나눠 서버마다 일부만 맡긴다. 이것이 샤딩(sharding, partitioning)이다. 보통 샤드마다 다시 복제를 둔다.

• 범위 샤딩: 키 구간마다 샤드를 정한다. 범위 질의가 한두 샤드에서 끝나지만, 시간이나 증가하는 번호를 키로 쓰면 새 쓰기가 마지막 샤드에 몰린다. 구간이 커지면 둘로 갈라 옮긴다.
• 해시 샤딩: 키의 해시로 샤드를 정한다. 고르게 퍼지지만 범위 질의는 모든 샤드에 물어야 한다. 그래서 (사용자 id, 시각)처럼 앞 열은 해시로 나누고 같은 샤드 안에서는 뒤 열로 정렬하는 복합 키가 흔하다.
• 뜨거운 키: 해시로도 못 푸는 쏠림이 있다. 유명인 계정 하나에 쓰기가 몰리면 그 키가 든 샤드는 늘 뜨겁다. 키 뒤에 임의의 숫자를 붙여 여러 샤드로 쪼개고 읽을 때 모으는 식으로 응용 쪽에서 푼다.
• 보조 인덱스: 샤드 키가 아닌 열로 찾으려면 샤드마다 자기 데이터의 인덱스를 두고 모두에 묻거나(지역 인덱스), 인덱스 자체를 따로 나눠 둔다(전역 인덱스). 전역 인덱스는 쓰기 하나가 여러 샤드를 고치는 일이 된다.

일관된 해싱과 재분배

해시 샤딩을 hash(키) mod N으로 하면 서버 수 N이 바뀔 때 거의 모든 키의 자리가 바뀐다. 1997년 Karger 등의 「Consistent Hashing and Random Trees」가 내놓은 일관된 해싱은 키와 노드를 같은 해시 공간(링)에 올리고, 키를 시계 방향으로 처음 만나는 노드에 맡긴다. 노드를 더하면 그 노드 바로 앞 구간만 옮겨진다.

노드마다 점이 하나뿐이면 구간 길이가 들쭉날쭉해 어떤 노드는 두 배 넘게 맡는다. 그래서 노드 하나를 링 위 여러 점(가상 노드)으로 찍어 구간을 고르게 한다. 다른 해법은 처음부터 샤드를 노드 수보다 훨씬 많이(예: 노드 10대에 샤드 1,000개) 만들어 두고, 노드가 늘면 샤드를 통째로 옮기는 것이다. 키→샤드 대응은 그대로라 옮기는 단위가 단순하다. 어느 쪽이든 재분배 중에는 옮기는 데이터만큼 네트워크와 디스크를 쓰므로 자동으로 하기보다 사람이 확인하며 진행하는 경우가 많다.

합의와 Raft

장애 조치에서 "누가 리더인가"를 여러 서버가 하나로 합의해야 분할 뇌가 생기지 않는다. 이런 문제를 합의(consensus)라 한다. 오랫동안 Paxos가 표준 해법이었지만 이해하고 구현하기 어렵기로 유명했다. 2014년 Ongaro와 Ousterhout의 「In Search of an Understandable Consensus Algorithm」이 이해하기 쉬움을 목표로 설계한 것이 Raft다. etcd, CockroachDB, TiKV 같은 시스템이 쓴다.

1. 임기(term): 시간을 번호 붙은 임기로 나눈다. 임기마다 선거가 한 번 있고 리더는 많아야 하나다. 더 높은 임기를 본 서버는 곧바로 팔로워로 물러난다.
2. 선거: 팔로워는 하트비트가 끊기면 무작위로 정한 시간 뒤 임기를 올려 후보가 되고 표를 청한다. 서버는 임기마다 한 표만 주고, 후보의 로그가 자기만큼 최신일 때만 준다. 과반을 얻으면 리더다. 시간이 무작위라 동시에 후보가 되는 일이 드물고, 표가 갈리면 다음 임기에 다시 한다.
3. 로그 복제: 클라이언트 명령은 리더의 로그 끝에 붙고 AppendEntries로 팔로워에 간다. 과반이 받으면 커밋되고, 그때 상태 기계에 적용하고 답한다.
4. 안전성: 커밋은 과반에 있고, 새 리더는 과반의 표를 얻어야 하며, 표는 로그가 뒤지지 않은 후보에게만 간다. 두 과반은 반드시 겹치므로 새 리더는 모든 커밋된 항목을 가지고 있다.

Raft 누리집 raft.github.io에서 서버를 직접 끄고 켜며 선거와 복제를 보는 시각화를 돌려 볼 수 있다. 다섯 대 클러스터는 두 대까지 죽어도 버티고, 쓰기는 과반의 확인을 기다리므로 가장 느린 두 대를 뺀 나머지 중 가장 느린 서버만큼 걸린다.

CAP과 PACELC

CAP 정리는 Eric Brewer가 2000년에 추측으로 내놓고 2002년 Gilbert와 Lynch가 「Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services」에서 증명했다. 정확히 말하면 이렇다. 네트워크가 갈라져 메시지가 사라질 수 있는 시스템에서, 모든 읽기가 가장 최근 쓰기를 보는 선형 일관성(C)과, 살아 있는 모든 노드가 모든 요청에 결국 답하는 가용성(A)을 분할이 일어난 동안 함께 가질 수는 없다.

• 흔한 오해: "셋 중 둘을 고른다"가 아니다. 네트워크 분할은 고르는 것이 아니라 일어나는 일이라, 실제 선택은 분할이 났을 때 C와 A 중 무엇을 포기하느냐다. Brewer 자신도 2012년 글 「CAP Twelve Years Later」에서 이 단순화가 오해를 낳았다고 정리했다.
• C와 A의 뜻: CAP의 C는 선형 일관성이라는 좁은 뜻이라 ACID의 C(제약 조건 지키기)와 다르고, A는 "모든 살아 있는 노드가 답한다"는 강한 뜻이라 흔히 말하는 99.99% 가용성과 다르다. Raft 클러스터는 소수 쪽이 쓰기를 거절하므로 CAP의 A는 아니지만, 실무에서는 충분히 가용성이 높다.
• PACELC: Daniel Abadi는 「Consistency Tradeoffs in Modern Distributed Database System Design」(2012)에서 분할이 없는 평소가 더 중요하다고 짚었다. 분할(P)이면 A와 C 사이, 그렇지 않으면(E) 지연(L)과 C 사이에서 고른다. 동기 복제는 PC/EC, Dynamo식 저장소는 기본 설정이 PA/EL에 가깝다.

분산 트랜잭션과 2단계 커밋

샤드 두 곳의 행을 한 트랜잭션으로 고치려면 두 샤드가 함께 커밋하거나 함께 취소해야 한다. 고전적인 방법이 2단계 커밋(two-phase commit, 2PC)이다. 조정자가 모든 참여자에게 "커밋할 수 있나"를 묻고(준비), 참여자는 변경을 디스크에 기록한 뒤 "예"라고 약속한다. 모두 "예"면 조정자는 커밋 결정을 기록하고 알린다. 하나라도 "아니오"면 모두 취소한다.

2PC의 약점은 막힘(blocking)과 비용이다. 왕복이 두 번이고 준비 기록마다 디스크 쓰기가 필요하며, 가장 느린 참여자만큼 기다린다. 그래서 요즘의 분산 SQL 데이터베이스는 참여자 각각을 Raft 그룹으로 만들고 조정자의 결정도 합의로 복제해, 한 대가 죽어도 결정이 사라지지 않게 한다. PostgreSQL도 외부 조정자가 쓰도록 PREPARE TRANSACTION을 제공하지만, 준비된 채 남은 트랜잭션이 잠금과 VACUUM을 막으므로 조정자 없이 쓰지 말라고 경고한다. 여러 서비스에 걸친 작업은 2PC 대신 단계마다 커밋하고 실패하면 보상 작업으로 되돌리는 사가(saga) 패턴을 쓰기도 한다. 이 노트의 주제 전반은 Martin Kleppmann의 『Designing Data-Intensive Applications』가 한 권으로 깊게 다룬다.