이전 포스트: [ 대규모 시스템 설계 스터디 ] 5장 정리
다음 포스트: [ 대규모 시스템 설계 스터디 ] 7장 정리
6장. 키-값 저장소 설계
키-값 저장소(Key-Value Store)는 데이터를
Key → Value형태로 저장하는 비관계형 데이터베이스다.
예를 들어
"user:1001" → 사용자 정보
"session:abc" → 세션 데이터
"product:15" → 상품 정보처럼 고유한 Key를 이용해 Value를 저장하고 조회한다.
키-값 저장소는 NoSQL의 한 종류다.
Database
│
├─ RDBMS
│ ├─ MySQL
│ ├─ PostgreSQL
│ └─ Oracle
│
└─ NoSQL
├─ Document
│ └─ MongoDB
│
├─ Key-Value
│ ├─ Redis
│ └─ DynamoDB
│
├─ Column-Family
│ ├─ Cassandra
│ └─ HBase
│
└─ Graph
└─ Neo4j이번 장에서는 단순한 Key-Value 저장소에서 출발해, 이를 대규모 분산 환경에서도 동작하는 저장소로 확장하는 과정을 살펴본다.
1. 먼저 요구사항부터 정리
설계할 시스템의 요구사항은 다음과 같다.
- Key-Value 데이터 크기는 10KB 이하
- 많은 데이터를 저장할 수 있어야 함
- 높은 가용성
- 서버 장애가 발생해도 빠른 응답 제공
- 트래픽에 따라 서버를 추가하거나 제거할 수 있는 확장성
- 일관성 수준 조정 가능
- 낮은 Latency
즉 단순하게
put(key, value)
get(key)만 구현하는 것이 아니라,
서버가 여러 대이고 장애가 발생하는 상황에서도 빠르고 안정적으로 데이터를 저장하고 조회할 수 있어야 한다.
2. 단일 서버에서 시작
가장 단순하게는 한 대의 서버 메모리에 Hash Table을 만들 수 있다.
Key
↓
Hash Table
↓
Value메모리 기반이므로 매우 빠르게 데이터를 조회할 수 있다.
하지만 명확한 한계가 있다.
모든 데이터를 한 서버의 메모리에 넣을 수는 없다.
따라서 다음과 같은 방법을 사용할 수 있다.
자주 사용하는 데이터
→ Memory
나머지 데이터
→ Disk또는 데이터를 압축하여 메모리 사용량을 줄일 수도 있다.
하지만 데이터가 계속 증가하면 결국 한 대의 서버로는 감당하기 어렵다.
그래서 여러 서버를 사용하는 분산 Key-Value Store가 필요하다.
3. 분산 시스템에서 가장 먼저 생각할 CAP
여러 서버에 데이터를 저장하게 되면 새로운 문제가 발생한다.
대표적인 것이
Consistency
Availability
Partition Tolerance이다.
이를 설명하는 개념이 CAP 정리다.
Consistency
어떤 서버에서 데이터를 읽더라도 동일한 값을 확인할 수 있어야 한다.
Server A → value = 10
Server B → value = 10
Server C → value = 10즉 사용자가 어느 노드에 접속하든 일관된 데이터를 볼 수 있는 상태다.
Availability
일부 서버에 장애가 발생하더라도 요청에 응답할 수 있어야 한다.
Server A ✕
Server B ○
Server C ○
→ 서비스 계속 제공Partition Tolerance
분산 시스템에서는 서버 간 네트워크 연결에 문제가 생길 수 있다.
Server A ✕──── Server B이처럼 서버끼리 통신할 수 없는 상황을 Network Partition이라고 볼 수 있다.
Partition Tolerance는 이런 상황에서도 시스템이 계속 동작할 수 있는 특성을 의미한다.
4. CP와 AP
분산 환경에서는 네트워크 장애를 완전히 피하기 어렵기 때문에 Partition Tolerance를 고려해야 한다.
따라서 실제 선택은 주로
CP
vs
AP사이에서 이루어진다.
CP
Consistency
+
Partition Tolerance데이터의 일관성을 우선한다.
Partition이 발생하여 최신 데이터를 보장할 수 없다면 일부 요청을 거절할 수도 있다.
AP
Availability
+
Partition Tolerance서비스 응답을 우선한다.
일부 서버 데이터가 아직 최신 상태가 아니더라도 사용자에게 응답을 반환할 수 있다.
이 경우 일시적으로 서로 다른 데이터가 보일 수 있다.
5. 상황에 따라 선택이 달라진다
처음에는 데이터가 항상 최신 상태여야 하므로 CP가 무조건 더 중요하다고 생각했다.
하지만 실제 시스템에서는 서비스 중단 자체가 큰 문제가 될 수 있다.
예를 들어
좋아요 수
조회수
SNS Feed처럼 몇 초 정도 데이터가 다르더라도 큰 문제가 없는 서비스에서는 가용성을 높이고 이후 데이터를 맞추는 방법을 선택할 수 있다.
반면
결제
계좌 잔액
재고 차감처럼 데이터의 정확성이 중요한 영역에서는 더욱 강한 일관성이 필요하다.
결국 핵심은
Consistency와 Availability 중 무엇을 더 중요하게 볼지는 서비스 특성에 따라 결정된다.
6. 분산 Key-Value Store의 구성 요소
이번 장에서 살펴보는 주요 요소는 다음과 같다.
Data Partitioning
Data Replication
Consistency
Conflict Resolution
Failure Detection
Failure Handling
Write Path
Read Path하나씩 연결해서 살펴보자.
7. 데이터 파티션
데이터가 너무 많아서 하나의 서버에 저장할 수 없다면 여러 서버로 나눈다.
전체 데이터
↓
┌───────────────┐
│ Partition 1 │
│ Partition 2 │
│ Partition 3 │
└───────────────┘이때 중요한 조건은 두 가지다.
데이터가 서버에 비교적 균등하게 분산되어야 한다.
특정 서버에 데이터가 몰리면 해당 서버만 병목이 된다.
서버 추가·삭제 시 데이터 이동량이 적어야 한다.
서버 하나가 추가될 때 전체 데이터를 다시 배치하면 비용이 너무 크다.
이 문제를 해결하기 위해 지난 장에서 배운 Consistent Hashing을 사용할 수 있다.
8. Hash Ring 활용
서버와 Key를 Hash Ring에 배치한다.
S0
↗ ↘
S3 S1
↖ ↙
S2Key 위치에서 시계 방향으로 처음 만나는 서버가 해당 데이터를 담당한다.
이 구조의 장점은 서버가 추가되거나 제거되더라도 일부 구간의 데이터만 이동한다는 것이다.
또 Virtual Node를 활용하면 서버별 성능에 따라 담당 범위를 조정할 수도 있다.
예를 들어 고성능 서버에는 더 많은 Virtual Node를 할당할 수 있다.
9. 데이터 다중화 Replication
서버 하나에만 데이터를 저장하면 그 서버가 죽었을 때 데이터를 사용할 수 없다.
따라서 동일한 데이터를 여러 서버에 복제한다.
복제본의 개수를 N이라고 하자.
N = 3
Key A
↓
Server 1
Server 2
Server 3즉 같은 데이터를 세 개의 서버에 저장한다.
10. 어느 서버에 복제할까?
Key를 Hash Ring에 배치하고 시계 방향으로 이동하면서 서로 다른 서버를 선택할 수 있다.
Key
↓
Server 1 → 원본
Server 2 → Replica
Server 3 → ReplicaVirtual Node를 사용한다면 여러 Virtual Node가 같은 실제 서버를 가리킬 수도 있다.
따라서 복제본을 선택할 때는 실제 물리 서버가 중복되지 않도록 확인해야 한다.
또 데이터 센터 장애까지 고려한다면 복제본 일부를 다른 데이터 센터에 저장하는 방법도 사용할 수 있다.
11. 복제했더니 새로운 문제가 생긴다
복제본이 많아지면 가용성은 좋아진다.
하지만 동시에
모든 Replica가 항상 동일한 데이터를 가지고 있는가?
라는 문제가 생긴다.
예를 들어
Server A → value = 10
Server B → value = 10
Server C → value = 9처럼 업데이트가 아직 전달되지 않은 서버가 있을 수 있다.
그래서 읽기와 쓰기를 몇 대의 서버에서 확인해야 할지 결정하는 Quorum 개념이 등장한다.
12. Quorum
주요 값은 세 가지다.
N = 전체 Replica 수
W = 쓰기 성공에 필요한 Replica 수
R = 읽기에 필요한 Replica 수예를 들어
N = 3
W = 2
R = 2라면 데이터는 세 서버에 복제되고,
쓰기 요청은 최소 두 서버가 성공해야 완료로 판단하며,
읽을 때도 두 서버의 값을 확인한다.
13. Coordinator
클라이언트가 모든 Replica를 직접 관리하면 구조가 복잡해진다.
Client
├→ Server A
├→ Server B
└→ Server C서버가 추가되거나 삭제될 때마다 클라이언트가 모든 정보를 알아야 하기 때문이다.
그래서 중간에 Coordinator를 둘 수 있다.
Client
↓
Coordinator
↙ ↓ ↘
S1 S2 S3Coordinator는 클라이언트를 대신하여
- 적절한 노드 탐색
- Read / Write 요청 전달
- 필요한 응답 수 확인
등을 처리한다.
즉 클라이언트와 저장 노드 사이에서 프록시 역할을 한다.
14. N, W, R을 어떻게 정할까?
설정에 따라 읽기와 쓰기의 성능 및 일관성이 달라진다.
빠른 읽기
R = 1
W = N쓰기 시 모든 Replica를 맞추기 때문에 읽을 때 하나만 확인해도 된다.
빠른 쓰기
W = 1
R = N한 서버만 쓰기에 성공해도 완료시킨다.
대신 읽을 때 여러 Replica를 확인해야 할 수 있다.
강한 일관성을 높이고 싶다면
W + R > N이 되도록 설정하는 방법을 사용할 수 있다.
예를 들어
N = 3
W = 2
R = 2와 같은 형태다.
결국
Read 성능, Write 성능, Consistency 요구사항 사이에서 값을 조정한다.
15. 일관성 모델
분산 시스템에서는 데이터가 언제 동일해지는가에 따라 여러 일관성 모델을 생각할 수 있다.
Strong Consistency
읽기 요청은 항상 최신 데이터를 반환한다.
Write
↓
모든 필요한 동기화 완료
↓
Read 허용최신 데이터를 보장하는 대신 가용성이나 성능 측면에서 비용이 발생할 수 있다.
Weak Consistency
읽기 요청이 항상 최신 데이터를 반환한다는 보장이 없다.
Eventual Consistency
약한 일관성의 한 형태다.
Replica들이 즉시 같은 값을 가지지는 않더라도 일정 시간이 지나면 결국 동일한 상태에 도달한다.
t0
A = 10
B = 9
시간 경과
t1
A = 10
B = 1016. 동시에 서로 다른 데이터가 수정된다면?
Replica를 여러 개 운영하면 서로 다른 서버에서 동일한 데이터를 동시에 수정할 수 있다.
예를 들어
D1
↓
Client A → D2
Client B → D3처럼 하나의 데이터에서 서로 다른 버전이 만들어질 수 있다.
어느 값이 최신인지 단순한 Timestamp만으로 판단하기 어려운 상황도 있다.
이를 해결하기 위한 방법 중 하나가 Versioning과 Vector Clock이다.
17. Versioning
데이터가 변경될 때마다 새로운 버전으로 관리한다.
D1
↓
D2
↓
D3각 버전을 독립적으로 관리하면서 어떤 버전이 다른 버전보다 먼저 만들어졌는지 확인할 수 있다.
하지만 동시에 수정되면
D2
↙ ↘
D3 D4처럼 갈라질 수 있다.
이 경우 D3와 D4 사이에 충돌이 존재한다.
18. Vector Clock
Vector Clock은 데이터에
[Server, Version]쌍을 함께 저장하여 데이터의 선후 관계를 추적하는 방식이다.
예를 들어
D1 [(Sx, 1)]에서 Sx가 다시 데이터를 변경하면
D2 [(Sx, 2)]가 된다.
다른 서버 Sy에서 D2를 수정한다면
D3 [(Sx, 2), (Sy, 1)]이 된다.
19. 동시에 수정되면?
D2에서 두 개의 업데이트가 동시에 발생했다고 하자.
D3 [(Sx,2), (Sy,1)]
D4 [(Sx,2), (Sz,1)]두 Vector Clock을 비교하면
D3에는 Sy 버전 존재
D4에는 Sz 버전 존재어느 한쪽이 다른 한쪽을 완전히 포함하지 않는다.
따라서
두 버전 사이에 선후관계를 결정할 수 없는 충돌 상태
라고 판단할 수 있다.
이후 충돌을 해결해 새로운 데이터를 만들면
D5 [(Sx,3), (Sy,1), (Sz,1)]와 같은 새로운 버전으로 저장할 수 있다.
20. Vector Clock의 단점
Vector Clock 역시 완벽하지 않다.
클라이언트 로직이 복잡해진다.
충돌 데이터를 확인하고 병합하는 기능이 필요할 수 있다.
Vector 정보가 계속 증가한다.
(S1,1)
(S2,3)
(S3,5)
(S4,2)
...처럼 서버 정보가 계속 추가될 수 있다.
이를 완화하기 위해 일정 임계치를 정하고 오래된 항목을 제거할 수 있다.
다만 이 경우 일부 정확한 버전 관계를 잃을 수 있다.
즉 여기에도 Trade-off가 존재한다.
21. 장애 처리
분산 시스템에서는 서버 장애가 반드시 발생한다고 가정해야 한다.
장애 처리는 크게
Failure Detection
+
Failure Resolution두 단계로 볼 수 있다.
먼저 어떤 서버가 장애 상태인지 알아내야 한다.
22. 장애 감지
서버 A와 잠시 통신되지 않았다고 해서 곧바로 장애로 판단하는 것은 위험할 수 있다.
네트워크가 순간적으로 느렸을 수도 있기 때문이다.
따라서 여러 노드가 정보를 공유하여 장애 여부를 판단하는 방식을 사용할 수 있다.
노드 수가 많아질수록 모든 서버끼리 서로 상태를 확인하는 방식은 비효율적이다.
이때 사용할 수 있는 방법 중 하나가 Gossip Protocol이다.
23. Gossip Protocol
각 노드는 다른 노드들의 상태 정보를 가진 Membership List를 관리한다.
예를 들어
Server A → Heartbeat 10
Server B → Heartbeat 14
Server C → Heartbeat 9형태다.
각 노드는 자신의 Heartbeat 값을 주기적으로 증가시킨다.
그리고 임의의 다른 노드에 자신이 가진 Membership 정보를 전달한다.
Server A
↓
Server C에게 상태 정보 전달정보를 받은 서버는 더 최신 Heartbeat 값을 반영한다.
24. 장애 판단
특정 서버의 Heartbeat 값이 오랜 시간 동안 갱신되지 않는다면 해당 서버가 비정상 상태일 가능성이 높다고 판단한다.
Server B
Heartbeat = 14
오랜 시간 변화 없음
↓
장애 의심이 정보가 Gossip을 통해 여러 노드로 퍼지면서 전체 클러스터가 장애 정보를 공유할 수 있다.
25. 일시적인 장애라면?
Replica 하나가 잠시 장애가 났다고 가정해보자.
원래 해당 서버에 데이터를 써야 하지만 지금은 사용할 수 없다.
이때 사용할 수 있는 방법이 Sloppy Quorum이다.
정상적인 Replica만 고집하지 않고 Hash Ring에서 현재 사용 가능한 서버를 찾아 요청을 처리한다.
원래 Server B에 저장
Server B 장애
↓
임시로 Server D에 저장그리고 Server D에는
이 데이터는 원래 Server B의 데이터다.
라는 Hint를 남긴다.
26. Hinted Handoff
장애가 복구되면 임시 서버가 데이터를 원래 서버에 전달한다.
Server B 장애
Data
↓
Server D 임시 저장
+ Hint
Server B 복구
Server D
↓
Server B로 데이터 전달이러한 방식을 Hinted Handoff라고 한다.
이를 통해 일시적인 장애 상황에서도 쓰기 요청을 계속 받을 수 있다.
27. 영구적인 데이터 불일치는?
장애가 길어지거나 Replica 데이터 자체가 달라졌다면 서로 다른 서버의 데이터를 비교해야 한다.
이 과정을 Anti-Entropy라고 한다.
하지만 수많은 데이터를 하나씩 전부 비교하면 비용이 너무 크다.
그래서 사용할 수 있는 구조가 Merkle Tree다.
28. Merkle Tree
Merkle Tree는 데이터의 Hash를 이용하여 서버 간 데이터 차이를 효율적으로 찾는 구조다.
먼저 전체 Key 공간을 여러 Bucket으로 나눈다.
Key Space
Bucket 1
Bucket 2
Bucket 3
Bucket 4각 Bucket 내부 데이터에 Hash를 적용한다.
그리고 이 Hash 값들을 다시 묶어 상위 Hash를 만든다.
Root Hash
/ \
Hash A Hash B
/ \ / \
H1 H2 H3 H429. Merkle Tree를 사용하면?
두 서버의 Root Hash부터 비교한다.
Server A Root = X
Server B Root = X같다면 전체 데이터가 동일하다고 볼 수 있다.
반대로
Server A Root ≠ Server B Root라면 하위 노드로 내려가면서 어떤 영역의 데이터가 다른지 확인한다.
즉 전체 데이터를 전부 전송하지 않고 차이가 있는 부분만 찾아 동기화할 수 있다.
30. 데이터 센터 장애
서버 하나가 아니라 데이터 센터 전체에 문제가 생길 수도 있다.
Data Center A ✕따라서 복제 데이터를 여러 데이터 센터에 분산하여 저장하는 방식도 필요하다.
Data Center A
+
Data Center B한 지역에 장애가 발생해도 다른 지역에서 서비스를 이어갈 수 있도록 구성한다.
31. 전체 아키텍처
지금까지의 내용을 연결하면 다음과 같은 분산 Key-Value Store를 생각할 수 있다.
Client
↓
Coordinator
↓
Consistent Hash Ring
↓
┌───────────────┐
│ Server A │
│ Server B │
│ Server C │
│ Server D │
└───────────────┘각 서버는
- 데이터를 저장하고
- Replica를 관리하며
- 장애 정보를 공유한다.
시스템은 특정 하나의 중앙 서버에만 모든 책임을 맡기지 않고 여러 노드로 분산할 수 있다.
32. Write Path
이제 실제 데이터를 저장하는 과정을 살펴보자.
클라이언트가
put(key, value)를 호출한다고 가정한다.
쓰기 요청은 대략 다음 순서로 처리된다.
1. Commit Log 기록
먼저 디스크의 Commit Log에 쓰기 작업을 기록한다.
Write Request
↓
Commit Log장애가 발생했을 때 데이터를 복구하기 위한 기록이다.
2. Memory에 저장
그 다음 데이터를 메모리 영역에 저장한다.
Commit Log
↓
Memory Cache메모리 기반이므로 빠르게 쓰기 요청을 처리할 수 있다.
3. SSTable 생성
Memory 영역이 일정 크기 이상 차면 데이터를 디스크의 SSTable로 저장한다.
Memory Full
↓
SSTable33. SSTable
SSTable은 Sorted String Table의 약자다.
Key-Value 데이터를 Key 기준으로 정렬하여 저장하는 변경 불가능한 파일 형태다.
apple → 10
banana → 20
cat → 30
dog → 40이미 생성된 SSTable의 내용을 직접 수정하는 대신 새로운 데이터를 별도로 기록하는 구조를 사용할 수 있다.
34. Read Path
이번에는
get(key)요청을 생각해보자.
먼저 메모리를 확인한다.
Key 존재?
↓
Memory메모리에 존재한다면 바로 반환할 수 있다.
하지만 메모리에 없다면 디스크의 SSTable을 확인해야 한다.
문제는 SSTable이 여러 개 존재할 수 있다는 것이다.
SSTable 1
SSTable 2
SSTable 3
SSTable 4모든 파일을 하나씩 확인하면 느리다.
이때 Bloom Filter를 이용할 수 있다.
35. Bloom Filter
Bloom Filter는
특정 값이 존재하지 않는다는 것은 확실하게 판단할 수 있지만, 존재한다고 판단해도 실제로는 없을 수 있는 자료구조
다.
즉 결과는 크게 두 가지다.
"없음"
→ 진짜 없음
"있을 수도 있음"
→ 실제 데이터를 확인해야 함이를 이용하면 불필요한 디스크 조회를 줄일 수 있다.
36. Bloom Filter를 이용한 조회 흐름
Key가 메모리에 없다면 Bloom Filter를 확인한다.
Client
↓
Memory 확인
↓
없음
↓
Bloom Filter 확인Bloom Filter가
"이 SSTable에는 절대 없음"이라고 판단하면 해당 파일을 읽지 않는다.
반면
"있을 수도 있음"이라고 판단하면 실제 SSTable을 확인한다.
전체 흐름은 다음과 같다.
GET(key)
↓
Memory 확인
↓
없음
↓
Bloom Filter
↓
가능성 있는 SSTable 확인
↓
Data 조회
↓
Client 반환이를 통해 여러 SSTable을 모두 검색해야 하는 비용을 줄일 수 있다.
전체 흐름 정리
이번 장의 전체 내용을 연결하면 다음과 같다.
Key-Value Store 필요
↓
단일 서버로 구현
↓
데이터 증가
↓
분산 시스템 필요
↓
CAP 고려
↓
Consistent Hashing으로
데이터 파티셔닝
↓
Replication으로
가용성 확보
↓
N / W / R로
일관성 수준 조정
↓
Replica 간 데이터 충돌
↓
Versioning + Vector Clock
↓
서버 장애 발생
↓
Gossip Protocol로 장애 감지
↓
일시 장애
→ Sloppy Quorum
→ Hinted Handoff
↓
영구적인 불일치
→ Anti-Entropy
→ Merkle Tree
↓
Write
→ Commit Log
→ Memory
→ SSTable
↓
Read
→ Memory
→ Bloom Filter
→ SSTable결국 이번 장은 단순한
Key → Value저장 방식을 만드는 이야기가 아니었다.
Key-Value 저장소를 여러 서버로 분산했을 때 발생하는 데이터 분산, 복제, 일관성, 장애와 복구 문제를 어떻게 해결할 것인가
를 다루는 장이었다.
공부하면서 정리한 핵심
처음에는 Key-Value Store라고 하면 Redis처럼
Key
→
Value를 빠르게 조회하는 단순한 데이터베이스 정도로 생각했다.
하지만 데이터가 많아지고 여러 서버를 사용하는 순간부터 이야기가 완전히 달라졌다.
데이터 분산
+
복제
+
일관성
+
동시 수정
+
서버 장애
+
데이터 복구를 전부 고려해야 했다.
특히 지난 장에서 배운 Consistent Hashing이 이번 장의 Data Partitioning에 바로 사용된다는 점이 흥미로웠다.
단순히 안정 해시 하나를 독립적으로 배우는 것이 아니라
Consistent Hashing
→ 서버에 데이터 분산
→ Replication
→ Quorum
→ Consistency처럼 이전 개념이 다음 시스템 설계에 계속 연결되고 있었다.
또 N, W, R 값을 바꾸는 것만으로도 읽기 성능, 쓰기 성능, 데이터 일관성의 특성이 달라진다는 점도 중요하게 느껴졌다.
결국 분산 시스템에서는 모든 것을 완벽하게 얻으려 하기보다
현재 서비스에서 무엇을 더 중요하게 볼 것인지 정하고 적절한 Trade-off를 선택하는 것
이 중요하다는 것을 다시 확인한 장이었다.
