분산 데이터베이스
분산 데이터베이스¶
이전: 13. NoSQL 데이터 모델 | 다음: 15. NewSQL과 현대 트렌드
현대 애플리케이션은 전 세계 사용자를 서비스하고, 대량의 데이터를 생성하며, 하드웨어 장애 시에도 가용성을 유지해야 합니다. 아무리 강력해도 단일 데이터베이스 서버는 이 세 가지 요구사항을 동시에 충족할 수 없습니다. 분산 데이터베이스는 여러 기계에 데이터와 계산을 분산시켜 이 문제를 해결합니다. 이 레슨에서는 모든 분산 데이터베이스 시스템을 뒷받침하는 아키텍처, 알고리즘, 트레이드오프를 데이터 단편화 및 복제부터 합의 프로토콜 및 분산 트랜잭션까지 살펴봅니다.
난이도: ⭐⭐⭐⭐
학습 목표: - Shared-nothing, shared-disk, shared-memory 아키텍처 비교 - 수평, 수직, 하이브리드 단편화 전략 설계 - 동기 vs 비동기 복제 및 쿼럼 기반 프로토콜 분석 - 분산 쿼리 처리 및 최적화 설명 - Two-Phase Commit (2PC) 및 Three-Phase Commit (3PC) 프로토콜 추적 - Paxos 및 Raft 합의 알고리즘을 개념적 수준에서 설명 - 분산 동시성 제어 기술 적용 - 적절한 파티셔닝 전략 선택 (범위, 해시, 일관된 해싱) - 분산 시스템 설계에서 CAP 정리의 함의에 대해 추론
목차¶
- 분산 데이터베이스 아키텍처
- 데이터 단편화
- 데이터 복제
- 분산 쿼리 처리
- 분산 트랜잭션: Two-Phase Commit (2PC)
- Three-Phase Commit (3PC)
- 합의 알고리즘: Paxos와 Raft
- 분산 동시성 제어
- 분산 설계를 위한 CAP 정리의 함의
- 파티셔닝 전략
- 연습문제
- 참고문헌
1. 분산 데이터베이스 아키텍처¶
분산 데이터베이스는 컴퓨터 네트워크에 분산된 논리적으로 상호 연관된 데이터베이스의 집합입니다. 리소스를 공유하는 방법에 따라 구별되는 세 가지 기본 아키텍처가 있습니다.
1.1 Shared-Nothing 아키텍처¶
Shared-nothing 아키텍처에서 각 노드는 자체 CPU, 메모리, 저장소를 가집니다. 노드는 네트워크를 통해서만 통신합니다.
┌─────────────────────────────────────────────────────────────┐
│ Shared-Nothing 아키텍처 │
│ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ Node 1 │ │ Node 2 │ │ Node 3 │ │
│ │ ┌─────┐ │ │ ┌─────┐ │ │ ┌─────┐ │ │
│ │ │ CPU │ │ │ │ CPU │ │ │ │ CPU │ │ │
│ │ ├─────┤ │ │ ├─────┤ │ │ ├─────┤ │ │
│ │ │ RAM │ │ │ │ RAM │ │ │ │ RAM │ │ │
│ │ ├─────┤ │ │ ├─────┤ │ │ ├─────┤ │ │
│ │ │Disk │ │ │ │Disk │ │ │ │Disk │ │ │
│ │ └─────┘ │ │ └─────┘ │ │ └─────┘ │ │
│ └────┬────┘ └────┬────┘ └────┬────┘ │
│ │ │ │ │
│ └──────────────┼──────────────┘ │
│ │ │
│ ┌───────┴───────┐ │
│ │ Network │ │
│ └───────────────┘ │
└─────────────────────────────────────────────────────────────┘
특성: - 각 노드가 독립적으로 작동 - 데이터가 노드 간에 분할됨 - 노드를 추가하여 선형으로 확장 - 단일 장애 지점 없음 (올바르게 설계된 경우) - 네트워크가 병목
예: Cassandra, CockroachDB, Citus (PostgreSQL 확장), Google Spanner, TiDB
장점: - 거의 선형적인 수평 확장성 - 노드 간 리소스 경합 없음 - 비용 효율적 (상용 하드웨어)
단점: - 노드 간 쿼리는 네트워크 통신 필요 - 분산 트랜잭션은 비용이 많이 듦 - 노드 추가/제거 시 데이터 재균형화가 복잡함
1.2 Shared-Disk 아키텍처¶
Shared-disk 아키텍처에서 각 노드는 자체 CPU와 메모리를 가지지만, 모든 노드가 공유 저장소 레이어(일반적으로 SAN 또는 분산 파일시스템)에 액세스합니다.
┌─────────────────────────────────────────────────────────────┐
│ Shared-Disk 아키텍처 │
│ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ Node 1 │ │ Node 2 │ │ Node 3 │ │
│ │ ┌─────┐ │ │ ┌─────┐ │ │ ┌─────┐ │ │
│ │ │ CPU │ │ │ │ CPU │ │ │ │ CPU │ │ │
│ │ ├─────┤ │ │ ├─────┤ │ │ ├─────┤ │ │
│ │ │ RAM │ │ │ │ RAM │ │ │ │ RAM │ │ │
│ │ └─────┘ │ │ └─────┘ │ │ └─────┘ │ │
│ └────┬────┘ └────┬────┘ └────┬────┘ │
│ │ │ │ │
│ └──────────────┼──────────────┘ │
│ │ │
│ ┌───────┴───────┐ │
│ │ Shared Disk │ │
│ │ (SAN/NAS) │ │
│ │ ┌─────────┐ │ │
│ │ │ Disk │ │ │
│ │ │ Array │ │ │
│ │ └─────────┘ │ │
│ └───────────────┘ │
└─────────────────────────────────────────────────────────────┘
특성: - 모든 노드가 동일한 데이터를 봄 (저장소 파티셔닝 불필요) - 쓰기를 조정하기 위해 분산 잠금 관리(DLM) 필요 - 저장소 레이어는 고가용성과 고성능이어야 함 - 컴퓨팅 노드 추가는 쉬움; 저장소가 확장 병목
예: Oracle RAC, Amazon Aurora, Neon
장점: - 더 간단한 데이터 관리 (파티셔닝 로직 없음) - 컴퓨팅 노드 추가 용이 - 저장소 레이어가 내구성과 복제 처리
단점: - 공유 저장소가 병목이 될 수 있음 - 분산 잠금 관리가 복잡성을 추가 - 저장소 레이어가 잠재적 단일 장애 지점 (중복 SAN으로 완화)
1.3 Shared-Memory 아키텍처 (SMP)¶
Shared-memory (대칭 다중 처리) 아키텍처에서 모든 프로세서가 동일한 메모리와 디스크를 공유합니다.
┌─────────────────────────────────────────────────────────────┐
│ Shared-Memory 아키텍처 (SMP) │
│ │
│ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │
│ │ CPU1 │ │ CPU2 │ │ CPU3 │ │ CPU4 │ │
│ └──┬───┘ └──┬───┘ └──┬───┘ └──┬───┘ │
│ │ │ │ │ │
│ └─────────┴────┬────┴─────────┘ │
│ │ │
│ ┌───────┴───────┐ │
│ │ Shared RAM │ │
│ │ (Shared Bus) │ │
│ └───────┬───────┘ │
│ │ │
│ ┌───────┴───────┐ │
│ │ Shared Disk │ │
│ └───────────────┘ │
└─────────────────────────────────────────────────────────────┘
특성: - 가장 간단한 프로그래밍 모델 (모든 CPU가 모든 데이터에 액세스 가능) - 메모리 버스 대역폭으로 제한 - 단일 기계의 한계를 넘어 확장 불가 - 진정으로 "분산"되지 않음 -- 단일 대형 서버
예: 전통적인 엔터프라이즈 데이터베이스 서버 (단일 노드 PostgreSQL, Oracle, SQL Server)
장점: - 가장 빠른 프로세서 간 통신 (공유 메모리) - 데이터 액세스를 위한 네트워크 오버헤드 없음 - 간단한 트랜잭션 관리
단점: - 수직 확장만 가능 - 메모리 버스가 병목이 됨 - 단일 장애 지점
1.4 아키텍처 비교¶
| 기능 | Shared-Nothing | Shared-Disk | Shared-Memory |
|---|---|---|---|
| 확장성 | 우수 (수평) | 좋음 (컴퓨팅) / 제한적 (저장소) | 제한적 (수직) |
| 복잡성 | 높음 (파티셔닝, 분산 트랜잭션) | 중간 (DLM) | 낮음 |
| 장애 허용성 | 높음 | 중간 (저장소에 따라) | 낮음 |
| 비용 | 낮음 (상용 HW) | 중간-높음 (SAN) | 높음 (대형 서버) |
| 네트워크 의존성 | 높음 | 높음 (저장소용) | 없음 |
| 데이터 지역성 | 예 (함께 위치) | 아니오 (저장소로 네트워크) | 예 (공유 메모리) |
2. 데이터 단편화¶
데이터 단편화(파티셔닝 또는 샤딩이라고도 함)는 관계(테이블)를 더 작은 조각으로 나누고 노드에 분산시키는 프로세스입니다.
2.1 수평 단편화¶
수평 단편화는 테이블을 행으로 나눕니다. 각 단편은 어떤 술어를 만족하는 튜플의 부분집합을 포함합니다.
원본 테이블: employees
┌─────┬────────┬────────────┬────────┐
│ id │ name │ department │ salary │
├─────┼────────┼────────────┼────────┤
│ 1 │ Alice │ Engineering│ 95000 │
│ 2 │ Bob │ Marketing │ 72000 │
│ 3 │ Charlie│ Engineering│ 88000 │
│ 4 │ Diana │ Marketing │ 68000 │
│ 5 │ Eve │ Engineering│ 92000 │
│ 6 │ Frank │ Marketing │ 75000 │
└─────┴────────┴────────────┴────────┘
department별 수평 단편화:
Fragment 1 (Node A): Fragment 2 (Node B):
σ(department='Engineering') σ(department='Marketing')
┌─────┬────────┬────────────┬──────┐ ┌─────┬───────┬────────────┬──────┐
│ 1 │ Alice │ Engineering│95000 │ │ 2 │ Bob │ Marketing │72000 │
│ 3 │ Charlie│ Engineering│88000 │ │ 4 │ Diana │ Marketing │68000 │
│ 5 │ Eve │ Engineering│92000 │ │ 6 │ Frank │ Marketing │75000 │
└─────┴────────┴────────────┴──────┘ └─────┴───────┴────────────┴──────┘
정확성 조건:
- 완전성(Completeness): 원본 관계의 모든 튜플은 적어도 하나의 단편에 나타나야 합니다.
-
R = F1 ∪ F2 ∪ ... ∪ Fn -
재구성(Reconstruction): 원본 관계는 단편으로부터 복구 가능해야 합니다.
-
R = F1 ∪ F2 ∪ ... ∪ Fn(수평 단편화의 경우 합집합) -
분리성(Disjointness) (선택적이지만 바람직): 각 튜플은 정확히 하나의 단편에 나타납니다. 이것은 중복을 피합니다.
Fi ∩ Fj = ∅for alli ≠ j
수평 단편화의 유형:
- 주 수평 단편화(Primary horizontal fragmentation): 관계의 자체 속성에 대한 술어 기반.
-
예:
σ(salary > 80000)(employees)및σ(salary ≤ 80000)(employees) -
파생 수평 단편화(Derived horizontal fragmentation): 관련 관계에 대한 술어 기반.
- 예: 어떤 부서가 소유하는지에 따라
projects를 단편화하여employees단편화와 정렬.
2.2 수직 단편화¶
수직 단편화는 테이블을 컬럼으로 나눕니다. 각 단편은 속성의 부분집합과 기본 키(재구성 가능하도록)를 포함합니다.
원본 테이블: employees
┌─────┬────────┬────────────┬────────┬─────────────┬───────┐
│ id │ name │ department │ salary │ ssn │ email │
└─────┴────────┴────────────┴────────┴─────────────┴───────┘
수직 단편화:
Fragment 1 (Node A): Fragment 2 (Node B):
공개 정보 민감 정보
┌─────┬────────┬────────────┐ ┌─────┬────────┬─────────────┐
│ id │ name │ department │ │ id │ salary │ ssn │
├─────┼────────┼────────────┤ ├─────┼────────┼─────────────┤
│ 1 │ Alice │ Engineering│ │ 1 │ 95000 │ 123-45-6789 │
│ 2 │ Bob │ Marketing │ │ 2 │ 72000 │ 234-56-7890 │
│ ... │ ... │ ... │ │ ... │ ... │ ... │
└─────┴────────┴────────────┘ └─────┴────────┴─────────────┘
재구성: π_{id,name,department}(F1) ⋈ π_{id,salary,ssn}(F2) = R
정확성 조건:
1. 완전성: 모든 속성이 적어도 하나의 단편에 나타납니다.
2. 재구성: R = F1 ⋈ F2 ⋈ ... ⋈ Fn (기본 키에 대한 자연 조인).
3. 분리성: 속성(기본 키 제외)이 겹치지 않습니다.
사용 사례: - 보안: 민감한 컬럼(급여, SSN)을 별도의 더 안전한 노드에 - 성능: 자주 액세스되는 컬럼을 함께; 드물게 액세스되는 컬럼은 분리 - 혼합 워크로드: OLTP 쿼리는 몇 개의 컬럼에 액세스; OLAP 쿼리는 많은 컬럼에 액세스
2.3 하이브리드 단편화¶
하이브리드 단편화는 수평 및 수직 단편화를 결합합니다. 먼저 수직으로 단편화한 다음 수평으로 (또는 그 반대).
단계 1: 수직 단편화
R → V1(id, name, dept) + V2(id, salary, ssn)
단계 2: V1의 수평 단편화
V1 → H1(dept='Eng') + H2(dept='Mktg')
결과: 3개의 단편
F1 = H1 (id, name, dept) where dept='Eng' → Node A
F2 = H2 (id, name, dept) where dept='Mktg' → Node B
F3 = V2 (id, salary, ssn) → Node C (안전)
2.4 단편화 투명성¶
이상적으로 분산 데이터베이스는 단편화 투명성을 제공합니다: 사용자는 전역 스키마에 대해 쿼리를 작성하고, 시스템은 자동으로 하위 쿼리를 적절한 단편으로 라우팅합니다.
투명성 수준:
레벨 1: 단편화 투명성
사용자가 봄: "SELECT * FROM employees WHERE dept = 'Engineering'"
시스템 처리: 올바른 단편으로 라우팅
레벨 2: 위치 투명성
사용자는 단편이 존재한다는 것을 알지만 어디에 저장되어 있는지는 모름
사용자 작성: "SELECT * FROM employees_eng"
시스템 처리: employees_eng를 저장하는 노드 찾기
레벨 3: 투명성 없음
사용자가 단편과 위치를 모두 지정해야 함
"SELECT * FROM node_a.employees_eng"
3. 데이터 복제¶
복제는 가용성, 장애 허용성, 읽기 성능을 향상시키기 위해 여러 노드에 데이터 복사본을 유지합니다.
3.1 복제 토폴로지¶
단일 리더 (Master-Slave):
┌──────────┐ ┌──────────┐
│ Leader │────▶│ Follower │ (쓰기는 리더로,
│ (R/W) │ │ (Read) │ 읽기는 팔로워에서)
└──────────┘ └──────────┘
│
└──────────▶┌──────────┐
│ Follower │
│ (Read) │
└──────────┘
다중 리더:
┌──────────┐◀───▶┌──────────┐ (쓰기는 모든 리더에서 수락,
│ Leader 1 │ │ Leader 2 │ 양방향 복제)
│ (R/W) │ │ (R/W) │
└──────────┘ └──────────┘
리더 없음:
┌──────────┐ ┌──────────┐ (쓰기는 모든 복제본으로;
│ Node 1 │◀───▶│ Node 2 │ 여러 복제본에서 읽기)
│ (R/W) │ │ (R/W) │
└──────────┘ └──────────┘
▲ ▲
│ │
└───▶┌──────────┐│
│ Node 3 │┘
│ (R/W) │
└──────────┘
3.2 동기 vs 비동기 복제¶
동기 복제: 리더는 클라이언트에 확인하기 전에 모든(또는 정의된 부분집합의) 팔로워가 쓰기를 승인할 때까지 기다립니다.
Client Leader Follower 1 Follower 2
│ │ │ │
│──WRITE──▶ │ │ │
│ │──replicate──▶│ │
│ │──replicate──────────────────▶│
│ │ │ │
│ │◀──ACK────────│ │
│ │◀──ACK────────────────────────│
│◀──OK───────│ │ │
│ │ │ │
타임라인: 클라이언트는 모든 팔로워가 승인할 때까지 대기
보장: OK 후 데이터는 모든 복제본에서 내구성 있음
위험: 느린 팔로워 하나가 전체 쓰기를 차단
비동기 복제: 리더는 즉시 클라이언트에 쓰기를 확인한 다음 백그라운드에서 복제합니다.
Client Leader Follower 1 Follower 2
│ │ │ │
│──WRITE──▶ │ │ │
│◀──OK───────│ │ │
│ │ │ │
│ │──replicate──▶│ │ (백그라운드)
│ │──replicate──────────────────▶│ (백그라운드)
│ │ │ │
│ │◀──ACK────────│ │
│ │◀──ACK────────────────────────│
타임라인: 클라이언트는 즉시 OK를 받음
보장: OK 시점에 데이터는 리더에서만 내구성 있음
위험: 복제 전 리더 크래시 → 데이터 손실
준동기 복제: 리더는 최소한 하나의 팔로워가 승인할 때까지 기다립니다 (MySQL 준동기, PostgreSQL synchronous_standby_names에서 사용).
Client Leader Follower 1 Follower 2
│ │ │ │
│──WRITE──▶ │ │ │
│ │──replicate──▶│ │
│ │──replicate──────────────────▶│
│ │◀──ACK────────│ │
│◀──OK───────│ │ │ (F2 ACK 나중에 도착)
│ │◀──ACK────────────────────────│
타임라인: 클라이언트는 최소한 하나의 팔로워가 승인할 때까지 대기
보장: 데이터는 리더 + 한 팔로워 장애를 견딤
균형: 전체 동기보다 빠르고, 비동기보다 안전
3.3 쿼럼 기반 복제¶
쿼럼 프로토콜은 동기/비동기 트레이드오프를 일반화합니다.
N개의 복제본이 주어지면 다음을 정의합니다: - W = 쓰기를 승인해야 하는 복제본 수 (쓰기 쿼럼) - R = 읽기에 응답해야 하는 복제본 수 (읽기 쿼럼)
강한 일관성 조건: W + R > N
이것은 모든 읽기 쿼럼이 모든 쓰기 쿼럼과 겹치도록 보장하여, 읽기 집합의 최소 하나의 복제본이 최신 값을 가지도록 합니다.
예: N=3, W=2, R=2
쓰기 쿼럼 (W=2): 읽기 쿼럼 (R=2):
3개 중 2개에 쓰기 3개 중 2개에서 읽기
N1 ✓ N1 ✓
N2 ✓ N2 ✓
N3 (선택) N3 (선택)
겹침: 최소한 하나의 노드 (N1 또는 N2)가 최신 쓰기를 가짐.
읽기는 가장 높은 타임스탬프/버전의 값을 선택.
일반적인 구성:
| N | W | R | W+R > N? | 동작 |
|---|---|---|---|---|
| 3 | 3 | 1 | 4 > 3 ✓ | 강한 읽기, 느린 쓰기 |
| 3 | 1 | 3 | 4 > 3 ✓ | 빠른 쓰기, 느린 읽기 |
| 3 | 2 | 2 | 4 > 3 ✓ | 균형 (가장 일반적) |
| 3 | 1 | 1 | 2 > 3 ✗ | 최종 일관성 (빠르지만 잠재적으로 오래됨) |
| 5 | 3 | 3 | 6 > 5 ✓ | 높은 가용성 (2개 장애 허용) |
느슨한 쿼럼과 힌트 핸드오프:
일부 복제본에 연결할 수 없을 때, 느슨한 쿼럼은 다른 노드(지정된 복제본이 아님)가 쓰기를 수락하고 "힌트"로 저장할 수 있게 합니다. 원본 복제본이 복구되면 힌트가 전달됩니다. 이것은 잠재적 일관성 위반을 대가로 가용성을 향상시킵니다.
3.4 충돌 해결¶
다중 리더 및 리더 없는 시스템에서 동일한 키에 대한 동시 쓰기는 충돌을 생성할 수 있습니다.
충돌 해결 전략:
| 전략 | 설명 | 사용처 |
|---|---|---|
| Last-Writer-Wins (LWW) | 가장 높은 타임스탬프를 가진 쓰기가 승리; 다른 것들은 버려짐 | Cassandra, DynamoDB |
| 버전 벡터 | 인과 히스토리 추적; 진짜 충돌 감지 (동시 쓰기) | Riak, Dynamo |
| CRDT | 충돌 없이 자동으로 병합되는 데이터 구조 (Conflict-free Replicated Data Types) | Riak, Redis (CRDT 모듈) |
| 애플리케이션 수준 | 모든 충돌 버전을 애플리케이션에 반환; 결정하게 함 | CouchDB, DynamoDB (선택적) |
| Operational Transform | 일관성을 유지하기 위해 동시 작업을 변환 (협업 편집에 사용) | Google Docs |
예: 버전 벡터
노드 A와 노드 B가 모두 키 "cart"를 값 ["item1"]로 보유
1. 사용자가 노드 A에 쓰기: cart = ["item1", "item2"]
버전: {A:1}
2. 사용자가 노드 B에 쓰기: cart = ["item1", "item3"]
버전: {B:1}
3. 노드 A와 B 동기화:
A는 {A:1}, B는 {B:1} 가짐
어느 것도 지배하지 않음 → 충돌 감지
해결 옵션:
a. 병합: cart = ["item1", "item2", "item3"] (합집합)
b. 사용자에게 둘 다 제시: "어떤 카트를 원하세요?"
c. LWW: 더 높은 타임스탬프를 가진 것 선택 (하나의 쓰기 손실)
4. 분산 쿼리 처리¶
4.1 개요¶
데이터가 노드 간에 단편화되면 쿼리가 여러 노드의 데이터에 액세스해야 할 수 있습니다. 분산 쿼리 프로세서는 다음을 수행해야 합니다:
- 전역 쿼리를 각 단편에 대한 하위 쿼리로 분해
- 데이터 전송을 최소화하기 위해 실행 계획 최적화
- 가능한 경우 하위 쿼리를 병렬로 실행
- 최종 결과 조립
4.2 쿼리 분해¶
전역 쿼리:
SELECT e.name, d.dept_name
FROM employees e JOIN departments d ON e.dept_id = d.id
WHERE e.salary > 80000;
가정:
- employees는 dept_id로 Node A와 Node B에 걸쳐 수평 단편화됨
- departments는 모든 노드에 복제됨
분해:
Node A (dept_id = 1..50):
SELECT e.name, d.dept_name
FROM employees_frag_A e JOIN departments d ON e.dept_id = d.id
WHERE e.salary > 80000;
Node B (dept_id = 51..100):
SELECT e.name, d.dept_name
FROM employees_frag_B e JOIN departments d ON e.dept_id = d.id
WHERE e.salary > 80000;
Coordinator:
UNION ALL 결과를 Node A와 Node B에서
4.3 비용 요소¶
분산 쿼리 처리의 지배적 비용은 네트워크를 통한 데이터 전송입니다. 로컬 I/O 및 CPU 비용은 부차적입니다.
비용 모델:
총 비용 = Σ(각 노드의 로컬 I/O 비용)
+ Σ(각 노드의 CPU 비용)
+ Σ(네트워크 전송 비용)
↑
이것이 지배적!
데이터 전송을 최소화하기 위한 최적화 전략:
-
선택과 투영을 푸시 다운: 결과를 보내기 전에 각 노드에서 필터링 및 투영하여 전송되는 데이터 양 감소.
-
세미 조인 감소: 조인을 위해 전체 관계를 전송하는 대신 조인 컬럼 값만 전송한 다음 일치하는 튜플 요청.
세미 조인 없이:
Node A가 전체 employees 테이블을 조인을 위해 Node B로 전송
전송: |employees| 행 × row_size 바이트
세미 조인과 함께:
단계 1: Node B가 π_{dept_id}(departments)를 Node A로 전송 (작음!)
단계 2: Node A가 employees ⋉ dept_ids 계산 (로컬 필터)
단계 3: Node A가 일치하는 employees만 Node B로 전송 (훨씬 작음)
-
블룸 필터 최적화: 실제 조인 키를 보내는 대신 컴팩트한 블룸 필터를 보냅니다. 거짓 양성이 몇 개 추가 행을 보내지만 필터 크기는 극적으로 작습니다.
-
병렬 실행: 다른 노드에서 하위 쿼리를 동시에 실행.
4.4 분산 조인 전략¶
| 전략 | 설명 | 사용 시기 |
|---|---|---|
| Ship-whole | 하나의 전체 관계를 다른 쪽 노드로 전송 | 하나의 관계가 매우 작음 |
| Semi-join | 조인 키 교환, 그런 다음 일치하는 튜플 전송 | 선택적 조인 (매치가 적음) |
| Hash partitioned join | 두 관계를 조인 키로 해시 파티션하고 로컬에서 조인 | Large-large equi-join |
| Broadcast join | 작은 테이블을 모든 노드에 복제 | Small-large join |
| Collocated join | 두 테이블이 조인 키로 파티션됨 → 전송 없이 로컬 조인 | 테이블이 함께 파티션됨 |
Collocated join 예제:
orders와 order_items가 모두 order_id로 파티션되었다면:
Node 1: orders (order_id 1-1000) + order_items (order_id 1-1000)
Node 2: orders (order_id 1001-2000) + order_items (order_id 1001-2000)
Node 3: orders (order_id 2001-3000) + order_items (order_id 2001-3000)
JOIN orders o ON o.order_id = order_items.order_id
→ 각 노드가 로컬에서 조인을 실행할 수 있음 (네트워크 전송 없음!)
이것이 올바른 파티션 키를 선택하는 것이 중요한 이유입니다: 어떤 조인이 함께 위치할 수 있는지를 결정합니다.
5. 분산 트랜잭션: Two-Phase Commit (2PC)¶
5.1 문제¶
트랜잭션이 여러 노드에 걸쳐 있을 때, 모든 노드가 커밋 또는 중단에 동의해야 합니다. 부분 커밋(일부 노드는 커밋, 다른 노드는 중단)은 원자성을 위반합니다.
트랜잭션 T: Account A (Node 1)에서 Account B (Node 2)로 $100 이체
Node 1: UPDATE accounts SET balance = balance - 100 WHERE id = 'A';
Node 2: UPDATE accounts SET balance = balance + 100 WHERE id = 'B';
Node 1이 커밋하지만 Node 2가 크래시하면 어떻게 되나요?
→ $100이 사라집니다! 원자성 위반.
5.2 Two-Phase Commit 프로토콜¶
2PC는 지정된 코디네이터와 참여하는 노드(참가자)를 사용합니다.
Phase 1: Prepare (투표)
Coordinator Node 1 Node 2
│ │ │
│───── PREPARE ──────────▶│ │
│───── PREPARE ─────────────────────────────────▶ │
│ │ │
│ (로컬에서 txn 실행, │
│ 잠금 획득, │
│ WAL에 쓰기) │
│ │ │
│◀──── VOTE YES ──────────│ │
│◀──── VOTE YES ────────────────────────────────── │
│ │ │
각 참가자: 1. 로컬에서 트랜잭션 실행 (하지만 커밋하지 않음) 2. WAL(Write-Ahead Log)에 prepare 레코드 작성 3. VOTE YES(커밋 가능한 경우) 또는 VOTE NO(불가능한 경우)로 응답
Phase 2: Commit/Abort (결정)
모든 참가자가 YES로 투표한 경우:
Coordinator Node 1 Node 2
│ │ │
│ (COMMIT을 코디네이터 │ │
│ WAL에 쓰기) │ │
│ │ │
│───── COMMIT ───────────▶│ │
│───── COMMIT ──────────────────────────────────▶ │
│ │ │
│ (로컬에서 커밋, │
│ 잠금 해제, │
│ WAL에 commit 쓰기) │
│ │ │
│◀──── ACK ───────────────│ │
│◀──── ACK ─────────────────────────────────────── │
│ │ │
참가자가 NO로 투표한 경우:
Coordinator Node 1 Node 2
│ │ │
│ (ABORT를 코디네이터 │ │
│ WAL에 쓰기) │ │
│ │ │
│───── ABORT ────────────▶│ │
│───── ABORT ───────────────────────────────────▶ │
│ │ │
│ (로컬에서 롤백, │
│ 잠금 해제) │
│ │ │
│◀──── ACK ───────────────│ │
│◀──── ACK ─────────────────────────────────────── │
5.3 상태 기계¶
Coordinator Participant
┌─────────────────┐ ┌─────────────────┐
│ INITIAL │ │ INITIAL │
└────────┬────────┘ └────────┬────────┘
│ PREPARE 전송 │ PREPARE 수신
▼ ▼
┌─────────────────┐ ┌─────────────────┐
│ WAITING │ │ READY │
│ (투표 대기) │ │ (YES 투표함) │
└────────┬────────┘ └────────┬────────┘
│ │
┌────────┴────────┐ ┌────────┴────────┐
│ all YES │ any NO │ COMMIT │ ABORT
▼ ▼ ▼ ▼
┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐
│ COMMITTED│ │ ABORTED │ │ COMMITTED│ │ ABORTED │
└──────────┘ └──────────┘ └──────────┘ └──────────┘
5.4 장애 분석¶
2PC는 다양한 장애 시나리오를 처리해야 합니다:
경우 1: 참가자가 투표 전에 크래시
Coordinator는 투표 대기 시간 초과 → 트랜잭션 ABORT
Participant 복구 → WAL 확인 → prepare 레코드 없음 → 중단을 알게 됨
경우 2: 참가자가 YES 투표 후 크래시
Coordinator는 YES 수신 → 정상 진행
Participant 복구 → WAL 확인 → prepare 레코드 확인 → 결정을 위해 코디네이터에 연락
이것이 "의심스러운(in-doubt)" 상태: 참가자는 YES로 투표했지만 결과를 모름
경우 3: 코디네이터가 투표 수집 후 크래시
이것이 2PC의 중요한 문제입니다!
참가자들은 READY 상태(YES로 투표)이고 진행할 수 없음:
- COMMIT할 수 없음: 코디네이터가 ABORT를 결정했을 수 있음
- ABORT할 수 없음: 코디네이터가 COMMIT을 결정했을 수 있음
- 다른 참가자에게 물어볼 수 없음: 그들도 READY 상태일 수 있음
결과: 참가자들은 코디네이터가 복구될 때까지 차단되어야 함.
이 차단 문제는 2PC의 근본적인 약점입니다. 최악의 경우, 참가자는 잠금을 무한정 보유하여 다른 트랜잭션을 차단합니다.
5.5 최적화¶
Presumed Abort: 코디네이터가 로그에 결정을 쓰지 않고 크래시하면 복구 시 ABORT를 가정합니다. 이것은 ABORT 결정을 로그에 쓸 필요를 없앱니다.
Read-Only 최적화: 참가자가 트랜잭션이 자신의 사이트에서 어떤 데이터도 수정하지 않았다고 판단하면 READ-ONLY로 투표하고 결정을 기다리지 않고 즉시 리소스를 해제할 수 있습니다.
조정 이전: 원본 코디네이터가 실패하면 참가자가 코디네이터 역할을 인수할 수 있습니다 (나머지 참가자 간 합의 필요).
6. Three-Phase Commit (3PC)¶
6.1 동기¶
3PC는 Dale Skeen이 1981년에 추가 단계를 추가하여 2PC의 차단 문제를 해결하기 위해 제안했습니다.
6.2 프로토콜¶
Phase 1: CanCommit (투표) -- 2PC Phase 1과 동일.
Phase 2: PreCommit -- 새로운 중간 단계.
Phase 3: DoCommit -- 2PC Phase 2와 동일.
Coordinator Node 1 Node 2
│ │ │
│── CAN_COMMIT? ──────▶│ │
│── CAN_COMMIT? ─────────────────────────────▶│
│ │ │
│◀── YES ─────────────│ │
│◀── YES ──────────────────────────────────── │
│ │ │
│── PRE_COMMIT ───────▶│ │ ← 새 단계
│── PRE_COMMIT ──────────────────────────────▶│
│ │ │
│◀── ACK ─────────────│ │
│◀── ACK ──────────────────────────────────── │
│ │ │
│── DO_COMMIT ────────▶│ │
│── DO_COMMIT ─────────────────────────────▶ │
│ │ │
│◀── DONE ────────────│ │
│◀── DONE ─────────────────────────────────── │
6.3 3PC가 차단을 피하는 방법¶
주요 통찰: 3PC에서 참가자가 PreCommit 상태에 있으면 모든 참가자가 YES로 투표했음을 알고 있습니다. 따라서:
- 코디네이터가 PreCommit 중에 크래시하면, PRE_COMMIT을 받은 살아남은 참가자는 코디네이터가 커밋하려고 의도했음을 알고 있습니다. 새 코디네이터를 선출하고 COMMIT으로 진행할 수 있습니다.
- 참가자가 PRE_COMMIT을 받지 못했다면 안전하게 ABORT할 수 있습니다 (코디네이터가 커밋 결정에 도달하지 못했을 수 있기 때문).
Non-blocking 속성: 단일 노드 장애가 나머지 노드를 무한정 차단시킬 수 없습니다.
6.4 3PC의 한계¶
이론적으로 차단 문제를 해결함에도 불구하고, 3PC는 실용적으로 중대한 한계가 있습니다:
- 네트워크 파티션: 3PC는 fail-stop 모델(노드가 크래시하지만 파티션되지 않음)을 가정합니다. 실제 네트워크 파티션에서 3PC는 여전히 일관성을 위반할 수 있습니다:
시나리오:
파티션이 노드를 {Coordinator, Node1}과 {Node2}로 분할
Coordinator가 Node1에 PRE_COMMIT 전송 (수신됨)
Coordinator가 Node2에 PRE_COMMIT 전송 (파티션으로 인해 손실됨)
Coordinator 크래시.
Node1 (PRE_COMMIT 수신함): "Coordinator가 커밋하려 했음" → COMMIT
Node2 (PRE_COMMIT 받지 못함): "타임아웃, PRE_COMMIT 없음" → ABORT
불일치! Node1은 커밋, Node2는 중단.
-
추가 왕복: 3PC는 2PC보다 한 번 더 왕복이 필요하여 지연이 증가합니다.
-
실제로 거의 사용되지 않음: 네트워크 파티션 취약성으로 인해 대부분의 현대 시스템은 타임아웃을 사용한 2PC 또는 Paxos/Raft 기반 합의를 대신 사용합니다.
6.5 비교: 2PC vs 3PC¶
| 속성 | 2PC | 3PC |
|---|---|---|
| 단계 | 2 | 3 |
| 차단 | 예 (코디네이터 크래시) | 아니오 (fail-stop 모델에서) |
| 네트워크 파티션 | 차단됨 | 불일치 가능 |
| 지연 | 2 왕복 | 3 왕복 |
| 복잡성 | 중간 | 높음 |
| 실제 사용 | 광범위함 | 드뭄 |
| 메시지 수 | 4N (prepare + vote + decision + ack) | 6N (더 많은 메시지) |
7. 합의 알고리즘: Paxos와 Raft¶
7.1 합의 문제¶
분산 시스템에서 합의는 여러 노드가 단일 값에 동의하도록 하는 문제입니다. 이것은 다음에 근본적입니다:
- 리더 선출: 어떤 노드가 현재 리더인가?
- 분산 트랜잭션: 커밋 또는 중단해야 하는가?
- 복제된 상태 기계: 다음에 적용할 작업은 무엇인가?
- 구성 관리: 현재 클러스터 구성원은 무엇인가?
형식적 요구사항: 1. 합의(Agreement): 모든 올바른 노드가 동일한 값을 결정. 2. 유효성(Validity): 결정된 값은 어떤 노드에 의해 제안됨. 3. 종료(Termination): 모든 올바른 노드가 결국 결정.
FLP 불가능성 정리 (Fischer, Lynch, Paterson, 1985)는 하나의 결함 있는 노드라도 있는 비동기 시스템에서 합의를 보장하는 것이 불가능함을 증명합니다. Paxos와 Raft 같은 실용적 알고리즘은 타임아웃과 무작위화를 사용하여 이를 극복합니다 (기술적으로 적대적 시나리오에서 종료하지 않을 수 있지만 실제로 잘 작동).
7.2 Paxos¶
Leslie Lamport가 1989년에 발명한 Paxos는 기초적인 합의 알고리즘입니다. 이것은 이해하기가 매우 어렵기로 악명 높습니다 (Lamport는 처음에 그리스의 가상 섬 Paxos의 의회 프로토콜로 설명했습니다).
역할: - Proposer: 값을 제안 - Acceptor: 제안에 투표 - Learner: 결정된 값을 학습
(단일 노드가 여러 역할을 할 수 있음.)
Single-decree Paxos (하나의 값에 합의):
Phase 1: Prepare
Proposer Acceptors (다수 필요)
│ A1 A2 A3
│ │ │ │
│──PREPARE(n=1)──────────────▶│ │ │
│──PREPARE(n=1)──────────────────────▶ │ │
│──PREPARE(n=1)────────────────────────────────▶ │
│ │ │ │
│◀─PROMISE(n=1, null)────────│ │ │
│◀─PROMISE(n=1, null)──────────────── │ │
│◀─PROMISE(n=1, null)─────────────────────────── │
│ │ │ │
각 acceptor의 약속:
- "번호 < 1인 제안을 받아들이지 않겠음"
- acceptor가 이전에 값을 받아들였다면, 그 값을 포함
Phase 2: Accept
Proposer Acceptors
│ A1 A2 A3
│ │ │ │
│──ACCEPT(n=1, v="X")────────▶│ │ │
│──ACCEPT(n=1, v="X")────────────────▶ │ │
│──ACCEPT(n=1, v="X")──────────────────────────▶ │
│ │ │ │
│◀─ACCEPTED(n=1)─────────────│ │ │
│◀─ACCEPTED(n=1)───────────────────── │ │
│◀─ACCEPTED(n=1)──────────────────────────────── │
│ │ │ │
다수가 받아들임 → 값 "X"가 선택됨
주요 통찰: proposer가 이전에 받아들여진 값이 있는 promise를 받으면, 자신의 값이 아닌 그 값을 제안해야 합니다. 이것은 값이 일단 선택되면 변경될 수 없음을 보장합니다.
Multi-Paxos: 안정적인 리더를 선출하여 후속 제안에 대해 Phase 1을 건너뛰는 single-decree Paxos를 확장합니다. 이것은 일반적인 경우에 프로토콜을 단일 단계(Phase 2만)로 줄여 복제된 로그에 실용적으로 만듭니다.
7.3 Raft¶
Raft는 Diego Ongaro와 John Ousterhout가 2014년에 Paxos의 이해 가능한 대안으로 설계했습니다. 동일한 보장을 제공하지만 더 명확한 구조를 가집니다.
주요 아이디어: Raft는 합의를 세 가지 하위 문제로 분해합니다: 1. 리더 선출: 하나의 노드를 리더로 선택. 2. 로그 복제: 리더가 항목을 받아들이고 팔로워에게 복제. 3. 안전성: 커밋된 항목이 손실되지 않도록 보장.
Raft 상태 기계:
┌──────────┐
timeout, │ │ receives vote
start │ Follower │ from candidate
election │ │ with higher term
┌────│ │◀────┐
│ └──────────┘ │
│ ▲ │
│ │ │
▼ │ │
┌──────────┐ │ ┌──────────┐
│Candidate │ │ │ Leader │
│ │───┘ │ │
│ │─────────▶│ │
└──────────┘ wins └──────────┘
election
리더 선출:
Time ──────────────────────────────────────────────────────▶
Term 1 Term 2 Term 3
┌─────────────────────┐ ┌─────────────────────┐ ┌────────
│ Leader: Node A │ │ Leader: Node B │ │ ...
│ Normal operation │ │ Normal operation │ │
└─────────────────────┘ └─────────────────────┘ └────────
↑
Node A crashes,
Node B wins election
선출 프로세스:
1. Follower 타임아웃 (리더로부터 하트비트 없음)
2. Candidate가 되고, term 증가, 자신에게 투표
3. 다른 모든 노드에 RequestVote RPC 전송
4. 다수가 YES로 투표 → 리더가 됨
5. 다른 리더 발견 → follower로 돌아감
6. 타임아웃 → term 증가, 선출 재시작
로그 복제:
Leader Followers
│ F1 F2 F3
│ │ │ │
│ Client: SET x = 5 │ │ │
│ Append to local log │ │ │
│ │ │ │
│──AppendEntries(x=5)─────▶│ │ │
│──AppendEntries(x=5)──────────────▶ │ │
│──AppendEntries(x=5)───────────────────────── ▶│
│ │ │ │
│◀──ACK──────────────────│ │ │
│◀──ACK───────────────────────────── │ │
│ │ │ │
│ 다수 (3 중 2) ACK됨 │ │ │
│ → 항목 커밋 │ │ │
│ → 클라이언트에 응답 │ │ │
│ │ │ │
│──AppendEntries(commit)──▶│ │ │
│──AppendEntries(commit)───────────▶ │ │
│──AppendEntries(commit)────────────────────── ▶│
안전성 속성: 커밋된 항목이 모두 있는 노드만 리더가 될 수 있습니다. Raft는 선출 메커니즘을 통해 이를 보장합니다: 후보는 투표를 받기 위해 투표자의 로그만큼 최신인 로그를 가져야 합니다.
7.4 Paxos vs Raft¶
| 측면 | Paxos | Raft |
|---|---|---|
| 이해 가능성 | 매우 어렵기로 악명 높음 | 명확성을 위해 설계됨 |
| 리더 | 선택적 (Multi-Paxos는 리더 있음) | 필수 |
| 로그 구조 | 간격이 있을 수 있음 | 간격 없음 (순차적) |
| 안전성 증명 | 복잡함 | 간단함 |
| 재구성 | 별도 프로토콜 필요 | Joint consensus 내장 |
| 실제 사용 | Google Chubby, Spanner | etcd, CockroachDB, Consul, TiKV |
| 이론적 기초 | 더 강력함 (더 일반적) | 실제로 동등 |
7.5 데이터베이스의 합의¶
| 데이터베이스 | 합의 알고리즘 | 목적 |
|---|---|---|
| Google Spanner | Multi-Paxos | 각 Paxos 그룹 내 로그 복제 |
| CockroachDB | Raft | 노드 간 Range 복제 |
| TiDB (TiKV) | Raft | Region 복제 |
| etcd | Raft | Kubernetes를 위한 키-값 저장소 |
| ZooKeeper | Zab (Paxos 변형) | 조정 서비스 |
| Cassandra | Paxos (경량 트랜잭션) | Compare-and-set 작업 |
8. 분산 동시성 제어¶
8.1 과제¶
분산 환경에서의 동시성 제어는 단일 노드 시스템에 비해 추가 과제에 직면합니다:
- 전역 시계 없음: 노드가 정확한 시간에 동의할 수 없어 타임스탬프 순서 지정이 어려움.
- 네트워크 지연: 잠금 요청 및 해제가 네트워크 왕복을 발생시킴.
- 분산 교착 상태: 교착 상태 사이클이 여러 노드에 걸쳐 있을 수 있음.
- 부분 장애: 잠금을 보유한 노드가 크래시하여 잠금이 무한정 보유될 수 있음.
8.2 분산 Two-Phase Locking (D2PL)¶
2PL을 분산 환경으로 확장: 각 노드는 로컬 잠금 관리자를 가지며, 트랜잭션은 액세스하는 각 노드에서 잠금을 획득합니다.
트랜잭션 T가 Node 1과 Node 2에 액세스:
Node 1 Lock Manager Node 2 Lock Manager
┌─────────────────┐ ┌─────────────────┐
│ Lock table: │ │ Lock table: │
│ row_A → T (X) │ │ row_B → T (X) │
│ row_C → T (S) │ │ row_D → T (S) │
└─────────────────┘ └─────────────────┘
증가 단계: T가 두 노드에서 잠금 획득
커밋: 2PC가 원자적 커밋 보장
감소 단계: 2PC 결정 후, 모든 노드가 T의 잠금 해제
8.3 분산 교착 상태 감지¶
대기 그래프(Wait-for graph): 각 노드는 로컬 대기 그래프를 유지합니다. 모든 로컬 그래프의 합집합에 사이클이 있으면 전역 교착 상태가 발생합니다.
Node 1 로컬 WFG: Node 2 로컬 WFG:
T1 → T2 T2 → T3
Node 3 로컬 WFG:
T3 → T1
전역 WFG: T1 → T2 → T3 → T1 ← 사이클 = 교착 상태
감지 접근법:
| 접근법 | 설명 | 트레이드오프 |
|---|---|---|
| 중앙집중식 | 하나의 노드가 모든 로컬 WFG를 수집하고 전역 사이클 확인 | 간단하지만 단일 장애 지점 |
| 분산 | 노드가 서로 WFG 엣지를 보냄; 각 노드가 볼 수 있는 사이클 감지 | 단일 장애 지점 없지만 유령 교착 상태 감지 가능 |
| 타임아웃 기반 | 트랜잭션이 임계값보다 오래 기다리면 교착 상태 가정하고 중단 | 간단하지만 교착 상태가 아닌 트랜잭션을 중단할 수 있음 |
유령 교착 상태: 오래된 정보로 인해 감지된 거짓 교착 상태.
Time 1: T1이 Node 1에서 T2를 대기 (WFG edge: T1 → T2)
Time 2: T2가 Node 1에서 완료, 하지만 WFG edge가 아직 제거되지 않음
Time 3: T2가 Node 2에서 T1을 대기하기 시작 (WFG edge: T2 → T1)
교착 상태 감지기가 두 엣지를 동시에 보면:
T1 → T2 → T1 → 유령 교착 상태 (T2가 이미 잠금 해제함)
8.4 분산 Timestamp Ordering¶
트랜잭션에 전역적으로 고유한 타임스탬프를 할당합니다. 과제는 전역 시계 없이 타임스탬프를 생성하는 것입니다.
Lamport 타임스탬프: 부분 순서를 보장하는 논리적 시계.
각 노드가 카운터 C를 유지:
- 각 이벤트 전에: C = C + 1
- 메시지 전송 시: 메시지에 C 첨부
- 타임스탬프 T를 가진 메시지 수신 시: C = max(C, T) + 1
타임스탬프 = (C, node_id) 전체 순서를 위해
TrueTime (Google Spanner): GPS와 원자시계를 사용하여 실제 시간에 대한 제한된 불확실성 구간 [earliest, latest]을 제공합니다. Spanner는 커밋 전에 불확실성을 기다려 외부 일관성(실시간 순서)을 달성합니다.
TrueTime API:
TT.now() → [earliest, latest]
TT.after(t) → t가 확실히 과거인 경우 true
TT.before(t) → t가 확실히 미래인 경우 true
Commit wait:
1. 트랜잭션 T가 커밋 타임스탬프 s = TT.now().latest 획득
2. TT.after(s)가 true가 될 때까지 대기
3. 타임스탬프 s로 커밋
이것은 T1이 T2가 시작하기 전에 커밋되면(실시간),
s1 < s2 (타임스탬프 순서가 실시간 순서와 일치)를 보장.
8.5 분산 MVCC¶
많은 분산 데이터베이스가 Multi-Version Concurrency Control을 사용합니다:
키 "account_balance"에 대한 분산 MVCC:
Node 1 (primary):
Version 1: value=1000, ts=100, committed
Version 2: value=900, ts=150, committed
Version 3: value=850, ts=200, committed
Node 2 (replica):
Version 1: value=1000, ts=100, committed
Version 2: value=900, ts=150, committed
(Version 3은 아직 복제되지 않음)
스냅샷 ts=175로 Node 2에서 읽기:
→ Version 2 반환 (value=900) because ts=150 ≤ 175
스냅샷 ts=175로 Node 1에서 읽기:
→ Version 2 반환 (value=900) because ts=200 > 175
두 읽기 모두 일관됨! (스냅샷 격리)
9. 분산 설계를 위한 CAP 정리의 함의¶
9.1 설계 맥락에서 CAP 재검토¶
레슨 13에서 CAP 정리를 소개했습니다. 이제 분산 데이터베이스의 특정 설계 결정에 적용합니다.
9.2 CP 설계 패턴¶
패턴: 리더를 통한 선형화 가능 읽기
모든 읽기와 쓰기가 리더를 통함:
Client ──▶ Leader ──▶ Followers (복제)
◀── (읽기는 리더에서만 제공)
트레이드오프: 리더에 연결할 수 없으면(파티션), 읽기 실패 (가용성 감소)
사용처: etcd, ZooKeeper, HBase
패턴: 다수 쿼럼
다수에서 읽기, 다수에 쓰기:
클라이언트가 3개 복제본 중 2개에 쓰기 (W=2)
클라이언트가 3개 복제본 중 2개에서 읽기 (R=2)
W + R = 4 > 3 = N → 보장된 겹침
트레이드오프: 파티션 중, 다수에 연결할 수 없으면 작업 실패
사용처: MongoDB (majority read/write concern)
9.3 AP 설계 패턴¶
패턴: 모든 복제본에서 읽기
클라이언트가 사용 가능한 모든 복제본에서 읽기:
Client ──▶ Any Replica (오래된 데이터를 반환할 수 있음)
트레이드오프: 항상 가용하지만, 쓰기 후 오래된 데이터를 읽을 수 있음
사용처: Cassandra (일관성 수준 ONE), DynamoDB (최종 일관된 읽기)
패턴: Hinted handoff
파티션 중, 사용 가능한 노드에 쓰기:
정상: Client ──▶ Replica A, Replica B, Replica C
파티션: Client ──▶ Replica A, Replica D* (hint), Replica E* (hint)
복구: Replica D ──▶ Replica B (힌트된 쓰기 전달)
Replica E ──▶ Replica C (힌트된 쓰기 전달)
* D와 E는 지정된 복제본이 아니지만 쓰기를 "힌트"로 수락
트레이드오프: 쓰기 성공 (가용) 하지만 일관성은 지연됨
사용처: Dynamo, Cassandra, Riak
9.4 일관성 수준 조정¶
많은 분산 데이터베이스가 작업당 일관성 조정을 허용합니다:
Cassandra 일관성 수준:
ONE: 1개 복제본에 쓰기/읽기 (가장 빠름, 가장 덜 일관됨)
QUORUM: 다수에 쓰기/읽기 (균형)
ALL: 모든 복제본에 쓰기/읽기 (가장 느림, 가장 일관됨)
LOCAL_QUORUM: 로컬 DC에서 다수 (다중 데이터센터)
DynamoDB 일관성:
Eventually Consistent Read: 0.5x 비용, 오래된 데이터 반환 가능
Strongly Consistent Read: 1x 비용, 항상 최신 반환
MongoDB read concern:
"local": 로컬 데이터 반환 (빠름, 오래될 수 있음)
"majority": 다수가 승인한 데이터 반환 (일관됨)
"linearizable": 가장 강력, 단일 문서 읽기만
10. 파티셔닝 전략¶
10.1 범위 파티셔닝¶
키 공간의 연속 범위를 각 파티션에 할당합니다.
키 공간: [0, 1000]
Partition 1 (Node A): keys [0, 333]
Partition 2 (Node B): keys [334, 666]
Partition 3 (Node C): keys [667, 1000]
예: 사용자 ID
Node A: users 1-333
Node B: users 334-666
Node C: users 667-1000
장점: - 범위 쿼리가 효율적 (단일 파티션 또는 연속 파티션 스캔) - 이해하고 구현하기 쉬움
단점: - 핫스팟: 키 분포가 편향되면 (예: 최근 타임스탬프가 하나의 파티션에 집중), 하나의 노드가 불균형한 부하를 받음 - 재균형화: 핫 파티션을 분할할 때 데이터를 이동해야 함
사용처: HBase, Spanner, CockroachDB, TiDB
10.2 해시 파티셔닝¶
키에 해시 함수를 적용하고 해시 범위를 파티션에 할당합니다.
해시 함수: h(key) → [0, 2^32)
Partition 1 (Node A): h(key) ∈ [0, 2^32/3)
Partition 2 (Node B): h(key) ∈ [2^32/3, 2*2^32/3)
Partition 3 (Node C): h(key) ∈ [2*2^32/3, 2^32)
예: h("user_42") = 178294 → Partition 1 (Node A)
h("user_43") = 891023 → Partition 2 (Node B)
인접한 키가 다른 파티션에 분산됨.
장점: - 파티션 간 키의 균등한 분포 (무작위 키에 대한 핫스팟 없음) - 모든 키 분포에서 잘 작동
단점:
- 범위 쿼리 불가능: 원본 공간에서 가까운 키가 파티션에 분산됨. SELECT * FROM users WHERE id BETWEEN 100 AND 200는 모든 파티션을 쿼리해야 함.
- 재균형화: 노드를 추가하면 재해싱 및 ~1/N의 모든 데이터 이동 필요.
사용처: DynamoDB, Cassandra (기본 파티셔너)
10.3 일관된 해싱¶
일관된 해싱은 해시 파티셔닝의 재균형화 문제를 해결합니다. Karger 등이 1997년에 도입했습니다.
개념: 키와 노드 모두 원형 해시 링에 매핑됩니다.
0 (= 2^32)
│
│
N3 ──── │ ──── N1
(hash= │ (hash=
300) │ 50)
│
│
│
│
N2 ──── │
(hash= │
180) │
키는 시계 방향으로 첫 번째 노드에 할당:
h("k1") = 30 → N1 (30에서 시계 방향으로 다음은 50의 N1)
h("k2") = 70 → N2 (70에서 시계 방향으로 다음은 180의 N2)
h("k3") = 200 → N3 (200에서 시계 방향으로 다음은 300의 N3)
h("k4") = 310 → N1 (50의 N1로 랩어라운드)
노드 추가: 새 노드와 그 선행자 사이의 키만 이동하면 됩니다.
Before: N1(50), N2(180), N3(300)
위치 120에 N4 추가:
Before:
h("k5") = 100 → N2 (100 다음은 180의 N2였음)
After:
h("k5") = 100 → N4 (100 다음은 이제 120의 N4)
범위 (50, 120]의 키만 N2에서 N4로 이동.
다른 모든 키는 현재 노드에 유지!
가상 노드: 균등한 분포를 보장하기 위해 각 물리적 노드에 여러 "가상" 위치를 할당합니다.
Physical Node A → 위치 50, 120, 240의 가상 노드
Physical Node B → 위치 80, 190, 310의 가상 노드
Physical Node C → 위치 30, 160, 280의 가상 노드
물리적 노드당 더 많은 가상 노드:
- 키의 더 균등한 분포
- 노드 결합/이탈 시 더 부드러운 재균형화
- 더 나은 장애 허용성 (실패한 노드의 부하가 많은 노드에 분산)
사용처: Dynamo, Cassandra, Riak, Memcached, CDN 로드 밸런싱
10.4 파티셔닝 비교¶
| 기능 | Range | Hash | Consistent Hashing |
|---|---|---|---|
| 범위 쿼리 | 효율적 | 불가능 | 불가능 |
| 부하 분산 | 편향될 수 있음 | 균등 | 균등 (vnodes 사용) |
| 재균형화 비용 | 범위 분할/병합 | ~1/N 재해싱 | ~1/N 이동 |
| 핫스팟 | 가능 | 가능성 낮음 | 가능성 낮음 |
| 구현 | 간단 | 간단 | 중간 |
| 순서 | 유지됨 | 손실됨 | 손실됨 |
10.5 복합 파티셔닝¶
일부 데이터베이스는 조합을 사용합니다: 분산을 위해 파티션 키를 해싱한 다음 정렬 키를 사용하여 각 파티션 내에서 범위 순서를 지정합니다.
Cassandra: PRIMARY KEY ((partition_key), clustering_key)
DynamoDB: Partition Key + Sort Key
예: Messages 테이블
Partition Key: conversation_id (해시됨 → 균등 분포)
Sort Key: timestamp (파티션 내 범위 순서)
물리적 레이아웃:
Node A: conversation_123 → [msg at t1, msg at t2, msg at t3, ...] (정렬됨)
Node B: conversation_456 → [msg at t1, msg at t2, ...] (정렬됨)
쿼리: "conversation_123의 지난 1시간 메시지 가져오기"
→ conversation_123 해시 → Node A
→ 파티션 내 timestamp에 대한 범위 스캔 (효율적!)
11. 연습문제¶
연습문제 1: 아키텍처 선택¶
다음 각 시나리오에 대해 분산 데이터베이스 아키텍처(shared-nothing, shared-disk, shared-memory)를 권장하고 선택을 정당화하세요.
- 4개 대륙에 데이터센터가 있고 5억 명의 사용자를 서비스하는 글로벌 전자상거래 회사.
- 20명의 동시 분석가와 함께 10 TB의 데이터에 대한 분석을 실행하는 중간 규모 회사.
- 단일 데이터베이스 서버가 한계에 도달하여 저장소와 독립적으로 컴퓨팅을 확장해야 하는 스타트업.
연습문제 2: 단편화 설계¶
다음 스키마가 주어졌을 때:
CREATE TABLE employees (
id INT PRIMARY KEY,
name VARCHAR(100),
dept_id INT,
salary DECIMAL,
ssn VARCHAR(11),
hire_date DATE
);
CREATE TABLE departments (
id INT PRIMARY KEY,
name VARCHAR(100),
location VARCHAR(50)
);
3개 노드(New York, London, Tokyo에 하나씩)가 있는 분산 데이터베이스를 위한 단편화 전략을 설계하세요. 회사는 세 도시 모두에 부서가 있습니다. 고려사항:
1. employees를 어떻게 수평 단편화하겠습니까?
2. 민감한 데이터를 보호하기 위해 employees를 어떻게 수직 단편화하겠습니까?
3. departments를 복제해야 합니까 아니면 단편화해야 합니까? 왜?
4. 단편에 대한 완전성 및 재구성 조건을 확인하세요.
연습문제 3: 쿼럼 계산¶
N = 5 복제본을 가진 클러스터가 주어졌을 때:
- 어떤 W와 R 값이 강한 일관성을 보장합니까?
- W = 3이고 R = 3이면, 시스템은 읽기를 위해 몇 개의 노드 장애를 허용할 수 있습니까? 쓰기를 위해?
- 쓰기를 빠르게 하려면(W = 1), 강한 일관성을 위해 R은 무엇이어야 합니까? 읽기 지연에 대한 함의는?
- 시스템이 N = 7, W = 4, R = 4를 가집니다. 이것은 강하게 일관됩니까? 몇 개의 장애를 허용할 수 있습니까?
연습문제 4: 2PC 추적¶
다음 시나리오에 대한 2PC 프로토콜을 추적하세요:
트랜잭션 T가 Account A (Node 1)에서 Account B (Node 2)로 $500을 이체합니다.
- 두 노드가 모두 YES로 투표할 때의 메시지 시퀀스를 보이세요.
- Node 2가 NO로 투표할 때의 메시지 시퀀스를 보이세요.
- 코디네이터가 모든 YES 투표를 받은 후 COMMIT 메시지를 보내기 전에 크래시하면 어떻게 됩니까? 참가자들은 어떤 상태에 있습니까? 얼마나 오래 기다릴 수 있습니까?
연습문제 5: 합의 시나리오¶
노드 A가 term 3의 현재 리더인 5-노드 Raft 클러스터(노드 A, B, C, D, E)를 고려하세요.
- 노드 A가 크래시합니다. 리더 선출 프로세스를 단계별로 설명하세요. 어떤 노드가 새 리더가 되고 왜?
- 크래시 전에 노드 A는 로그 항목 [term 3, SET x=5]를 노드 A, B, C에 복제했습니다 (D와 E에는 아님). 이 항목은 커밋되었습니까? 왜 또는 왜 아닙니까?
- 노드 B가 term 4의 새 리더가 되면, 로그에 항목 [term 3, SET x=5]를 포함합니까? 설명하세요.
연습문제 6: 분산 교착 상태¶
두 노드에 걸쳐 세 개의 트랜잭션이 실행됩니다:
Node 1:
T1은 row A에 대한 잠금을 보유, row B에 대한 잠금 대기 (T2가 보유)
T2는 row B에 대한 잠금을 보유
Node 2:
T2는 row C에 대한 잠금 대기 (T3가 보유)
T3는 row C에 대한 잠금을 보유, Node 1의 row A에 대한 잠금 대기 (T1이 보유)
- 전역 대기 그래프를 그리세요.
- 교착 상태가 있습니까? 있다면 사이클을 깨기 위해 어떤 트랜잭션을 중단해야 합니까?
- 중앙집중식 교착 상태 감지기는 이 교착 상태를 어떻게 발견합니까?
- 타임아웃 기반 접근법은 이를 어떻게 처리합니까? 위험은 무엇입니까?
연습문제 7: 파티셔닝 전략¶
소셜 미디어 플랫폼을 위한 분산 데이터베이스를 설계하고 있습니다. posts 테이블은 다음 스키마를 가집니다:
CREATE TABLE posts (
post_id BIGINT,
user_id BIGINT,
content TEXT,
created_at TIMESTAMP,
like_count INT
);
일반적인 쿼리: 1. 특정 사용자의 모든 게시물을 생성 시간순으로 가져오기 (최신순). 2. ID로 특정 게시물 가져오기. 3. 모든 사용자의 최근 게시물 100개 가져오기 (글로벌 타임라인).
각 파티셔닝 전략(user_id로 범위, post_id로 해시, user_id로 일관된 해싱)에 대해: 1. 각 쿼리가 어떻게 실행될지 설명하세요. 2. 잠재적 핫스팟을 식별하세요. 3. 최상의 전략을 권장하고 선택을 정당화하세요.
연습문제 8: 일관된 해싱¶
위치 [0, 360)의 일관된 해싱 링이 주어졌을 때:
노드: A at 45, B at 120, C at 200, D at 310
키와 그 해시 값: - k1 = 30, k2 = 90, k3 = 150, k4 = 210, k5 = 330, k6 = 10
- 각 키에 대해 어떤 노드가 책임이 있습니까?
- 노드 E가 위치 170에 추가됩니다. 어떤 키가 재할당되고 어느 노드로?
- 노드 B가 실패합니다. 어떤 키가 재할당되고 어느 노드로?
- 각 물리적 노드가 3개의 가상 노드를 가지면(예: A at 45, 165, 285), 키 할당을 다시 하세요.
연습문제 9: 복제 충돌 해결¶
두 사용자가 리더 없는 복제 시스템(3개 복제본)에서 공유 문서를 동시에 업데이트합니다:
사용자 X (Replica 1에 연결): SET title = "Draft v2" at time T=100
사용자 Y (Replica 2에 연결): SET title = "Final Draft" at time T=101
네트워크 파티션으로 인해 Replica 3에 연결할 수 없습니다.
- Last-Writer-Wins (LWW)에서 최종 값은 무엇입니까? 데이터가 손실됩니까?
- 버전 벡터에서 충돌이 어떻게 감지되고 표현됩니까?
- 이 시나리오에 대한 애플리케이션 수준 해결 전략을 제안하세요.
- CRDT (구체적으로 Last-Writer-Wins Register)는 이를 어떻게 처리합니까?
연습문제 10: 분산 쿼리 최적화¶
두 노드에 걸쳐 분산된 두 테이블을 고려하세요:
Node 1: orders (10백만 행, 500바이트/행)
컬럼: order_id, customer_id, total, order_date
Node 2: customers (100,000행, 200바이트/행)
컬럼: customer_id, name, city, email
쿼리: SELECT c.name, o.total FROM orders o JOIN customers c ON o.customer_id = c.customer_id WHERE c.city = 'Tokyo';
Tokyo 고객은 전체 고객의 5%입니다 (5,000명). 각 고객은 평균 ~100개의 주문을 가집니다. 네트워크 전송 비용: MB당 1 ms.
다음 전략의 비용을 비교하세요:
1. Ship-whole: 전체 customers 테이블을 Node 1로 전송, 거기서 조인.
2. Ship-whole (reverse): 전체 orders 테이블을 Node 2로 전송, 거기서 조인.
3. Semi-join: Tokyo customer_ids를 Node 1로 전송, 일치하는 주문 가져오기, Node 2에서 조인.
4. Bloom filter: Tokyo customer_ids의 블룸 필터를 Node 1로 전송.
각 전략에 대한 대략적인 데이터 전송량을 MB로 계산하세요.
12. 참고문헌¶
- Ozsu, M. T. & Valduriez, P. (2020). Principles of Distributed Database Systems, 4th Edition. Springer.
- Kleppmann, M. (2017). Designing Data-Intensive Applications. O'Reilly Media. Chapters 5-9.
- Lamport, L. (1998). "The Part-Time Parliament" (Paxos). ACM TOCS.
- Ongaro, D. & Ousterhout, J. (2014). "In Search of an Understandable Consensus Algorithm" (Raft). USENIX ATC.
- Fischer, M., Lynch, N., Paterson, M. (1985). "Impossibility of Distributed Consensus with One Faulty Process" (FLP). JACM.
- Corbett, J. et al. (2013). "Spanner: Google's Globally-Distributed Database." ACM TODS.
- DeCandia, G. et al. (2007). "Dynamo: Amazon's Highly Available Key-Value Store." SOSP.
- Karger, D. et al. (1997). "Consistent Hashing and Random Trees." ACM STOC.
- Skeen, D. (1981). "Nonblocking Commit Protocols." ACM SIGMOD.
- Gray, J. & Lamport, L. (2006). "Consensus on Transaction Commit." ACM TODS.
이전: 13. NoSQL 데이터 모델 | 다음: 15. NewSQL과 현대 트렌드