-1. 단어 설명
상태 머신 복제(State Machine Replication)
같은 초기 상태에서 시작해 같은 명령들을 같은 순서로 실행하면 항상 같은 결과 상태에 도달하는 결정적(deterministic) 시스템
데이터베이스가 대표적으로 빈 DB에 "x=1 쓰기 → y=2 쓰기 → x 삭제"를 순서대로 적용하면 언제나 결과는 일치한다.
Paxos: 합의(consensus) 알고리즘
- 안전성: 일부 서버가 죽거나 메시지가 유실 / 지연되어도, 서로 다른 서버가 서로 다른 값에 합의하는 일은 절대 없다.
- 과반수(quorum) 원리: 전체 복제본의 과반수만 살아 있으면 진행할 수 있다. 5대 중 2대가 죽어도 나머지 3대로 쓰기가 계속 되며 반드시 겹치는 서버가 하나는 있기 때문에 이전 합의 내용이 유실되지 않는다
0. 핵심요약
구글은 Bigtable로 대규모 분산 저장을 실현했지만, 광역 복제 환경에서의 강한 일관성과 행 간 트랜잭션이 부족했다. 이를 해결하기 위해 TrueTime 기반의 Spanner를 구현하여, 전 지구적 규모에서 외부 일관성을 갖춘 분산 트랜잭션과 락 없는 읽기 전용 트랜잭션을 세계 최초로 지원했다.
1. 기존 문제점
Bigtable의 한계: 확장성은 뛰어나지만 광역 복제 환경에서 강한 일관성을 제공하지 못하며(최종적 일관성만 지원), 행 간(cross-row) 트랜잭션이 없어 사용자 불만이 많았음
Megastore의 한계: 반관계형(semi-relational) 데이터 모델과 동기식 복제를 지원해 구글 내 300개 이상의 애플리케이션이 사용했지만, 쓰기 처리량이 매우 낮았습니다. Bigtable 위에 얹혀 있어 통신 비용이 크고 장수(long-lived) 리더가 없어 여러 복제본의 쓰기가 Paxos에서 항상 충돌했기 때문입니다.
분산 시스템의 근본 난제: 지리적으로 분산된 노드들 간에 시계를 완벽히 동기화할 수 없기 때문에 전역적으로 트랜잭션의 순서를 보장(외부 일관성)하는 것이 사실상 불가능하다고 여겨짐. 실제 사례로, F1(구글 광고 백엔드)의 전신인 샤딩된 MySQL은 리샤딩 한 번에 2년 이상이 걸림
2. 해결 방안
(1) TrueTime API
시간을 하나의 값이 아니라 불확실성이 포함된 구간(TTinterval)으로 표현합니다. TT.now()는 절대 시간이 반드시 포함되는 [earliest, latest] 구간을 반환하고, TT.after(t)/TT.before(t)로 특정 시각의 경과 여부를 확실하게 판다. 데이터센터마다 GPS 마스터와 원자시계 마스터(Armageddon master)를 두어 서로 다른 실패 모드를 상호 보완. 불확실성 오차 ε은 평균 4ms 수준으로 유지됨
(2) 아키텍처
데이터를 전 세계 데이터센터의 Paxos 상태 머신 집합에 샤딩. 각 spanserver가 태블릿을 관리하고, 태블릿마다 Paxos 그룹으로 복제.
단일 그룹 트랜잭션은 Paxos + 락 테이블로 처리하고 여러 그룹에 걸친 트랜잭션은 Paxos 위에서 2단계 커밋(2PC)을 수행해 2PC의 가용성 문제를 완화.
디렉터리(공통 접두어를 가진 연속 키 집합)를 데이터 배치 / 이동의 단위로 삼아 애플리케이션이 복제 위치와 지역성을 세밀하게 제어
(3) 동시성
Start: 커밋 타임스탬프 s를 TT.now().latest 이상으로 부여.
Commit Wait: TT.after(s)가 참이 될 때까지(평균 2ε) 기다린 후 커밋 결과를 노출
-T1이 커밋된 후 T2가 시작했다면 T1의 타임스탬프 < T2의 타임스탬프가 전역적으로 보장됨
각 복제본이 안전 시간(t_safe)을 추적하므로 읽기 전용 트랜잭션과 스냅샷 읽기는 락 없이 최신 데이터 검색
3. 결론
Spanner는 데이터베이스 진영의 장점(반관계형 스키마, SQL 유사 질의어, 범용 트랜잭션)과 분산 시스템 진영의 장점(확장성, 자동 샤딩, 장애 허용, 동기식 복제, 광역 분산)을 하나의 시스템으로 결합했다.
4. 나의 생각
일종의 MVCC의 범지구적인 스케일로 확장한 데이터베이스로 생각하면 된다.
문제를 소프트웨어가 아닌 하드웨어로 푼 발상의 전환 (데이터센터마다 원자 시계 설치로 시간 측정..)
CAP 정리 이후 업계가 일관성을 포기하는(NoSQL) 방향으로 갔던 것과 달리, 구글은 GPS/원자시계라는 물리적 인프라 투자로 불확실성 자체를 줄여 강한 일관성을 유지함
