Replication, Partitioning & Sharding Strategies

1. Overview

복제, 파티셔닝, 그리고 샤딩 전략(Replication, Partitioning & Sharding Strategies)은 트래픽 폭풍 속에서 웹 서버는 무한히 늘릴 수 있지만 결국 모든 병목이 모이는 최후의 종착지인 **"데이터베이스(Data Tier)"**를 어떻게 찢고 복제하여 살아남을 것인지 해부합니다.

학습자는 단일 마스터의 SPOF(단일 장애점)를 없애기 위해 똑같은 데이터를 슬레이브로 복사해 읽기 트래픽을 분산하는 복제(Replication) 메커니즘을 뜯어봅니다. 나아가 읽기(Read)뿐만 아니라 쓰기(Write) 트래픽조차 단일 마스터가 감당하지 못할 때, 테이블을 논리적/물리적으로 갈기갈기 찢어 여러 DB 서버에 흩뿌리는 **샤딩(Sharding)과 파티셔닝(Partitioning)**의 잔혹한 아키텍처 개조 과정을 해부합니다. 마지막으로, 샤딩의 꽃이라 불리는 파티션 키(Partition Key/Shard Key) 설계 전략과 특정 샤드에 트래픽이 쏠리는 핫스팟(Hotspot) 현상을 해결하는 극한의 데이터 분산 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• Replication (복제): Master-Slave(Primary-Replica) 구조, 동기(Sync) vs 비동기(Async) 복제 복제 지연(Replication Lag).
• Partitioning (파티셔닝): 하나의 DB 내에서 거대한 테이블을 잘게 쪼개는 논리적 분할 (Range, Hash, List).
• Sharding (샤딩): 파티셔닝된 데이터를 물리적으로 서로 다른 DB 서버(인스턴스)에 찢어놓는 수평적 분할.
• Shard Key Design (샤드 키 설계): 데이터 분산의 핵심, 핫스팟 방지, Consistent Hashing (안정 해시).

Out-of-Scope

• CAP 정리와 다중 마스터(Multi-Master): 분산 DB 일관성 제약 $\rightarrow$ 07-02-01 Theorems & Consistency Dynamics로 이관.
• 분산 트랜잭션 롤백 (Saga): 샤딩된 DB 간의 원자성 붕괴 $\rightarrow$ 07-02-04 Distributed Transactions 영역으로 위임.

Boundaries

• Replication(복제) vs Sharding(샤딩): 데이터베이스가 느려질 때 무턱대고 샤딩을 도입하는 것은 최악의 안티 패턴입니다. 대부분의 웹 서비스는 읽기(Read) 트래픽이 쓰기(Write) 트래픽보다 10배 이상 많습니다. 따라서 읽기 전용 복제본(Read Replica)을 여러 대 띄워 쿼리 로드 밸런싱(Replication)을 하는 것만으로도 성능의 90%가 해결됩니다. 샤딩은 마스터 서버의 쓰기(Write/Insert) 한계마저 박살 나거나, 단일 서버의 디스크(HDD/SSD) 용량이 100TB를 넘어가 터지기 직전일 때 꺼내 드는, JOIN 쿼리를 포기해야 하는 '악마의 거래'임을 명확히 경계 짓습니다.

3. Counterexample

• 잘못된 샤드 키(Shard Key)의 재앙: 인스타그램 같은 서비스에서 DB를 샤딩하면서 샤드 키를 작성 시간(Timestamp)으로 잡았습니다. 최신 글은 전부 2024년이고 옛날 글은 2018년입니다. 유저들은 최근 게시물만 미친 듯이 읽고 씁니다. 결과적으로 최신 데이터가 몰려있는 '샤드 서버 1번'은 트래픽 폭격(Hotspot)을 맞아 불타버리고, 2018년 데이터가 있는 '샤드 서버 2번'은 0% 점유율로 놀고 있는, 샤딩을 안 하느니만 못한 아키텍처 붕괴입니다. (대안: User ID를 해싱하여 분산).
• 복제 지연(Replication Lag) 무시: 유저가 프로필 수정을 완료했습니다(Master DB 쓰기 완료). 완료 창이 뜨자마자 유저가 0.1초 만에 '내 정보' 화면에 진입했습니다(Slave DB 읽기). 그런데 Master에서 Slave로 데이터가 복사(비동기 복제)되는 데 0.5초가 걸려서 유저 화면에 예전 이름이 뜹니다. 유저는 "버그네!" 하고 다시 수정 버튼을 냅다 누릅니다. 복제 지연을 고려하지 않은 아키텍처 설계가 낳은 끔찍한 UX와 데이터 정합성 파괴입니다.

4. Prerequisites

• RDBMS 인덱스와 B-Tree (Basic): 거대 테이블 조회 성능 저하 원리. (06-01-02 Indexing)
• 해시 함수 (Basic): 값을 무작위의 고른 분포로 흩뿌리는 알고리즘 특성. (04-03 Hashing)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 읽기 부하의 해방, DB 복제 (Replication)

• Why to Learn: 어플리케이션 트래픽의 $90\%$를 차지하는 SELECT 쿼리 병목을 가장 쉽고 안전하게(로직 수정 없이) 해결하는 1차 인프라 스케일링 무기를 장악하기 위함입니다.
• What to Learn:
  • Concepts: Master-Slave (Primary-Replica), Binary Log (Binlog), Asynchronous vs Synchronous Replication, Read/Write Splitting.
  • Skills: 애플리케이션(ORM) 레벨에서 Write 트래픽은 마스터로, Read 트래픽은 슬레이브로 찢는 라우팅 설정.
• How to Learn:
  • 1단계: 마스터와 슬레이브: 쓰기(INSERT/UPDATE)는 무조건 대장(Master) 한 명만 받습니다. 대장은 자기가 쓴 내역을 영수증(Binlog)에 적어 뒤로 던집니다. 여러 명의 부하(Slave)들이 그 영수증을 보고 똑같이 자기 DB에 타이핑(Replay)하여 거울(복제본)을 만듭니다.
  • 2단계: 동기와 비동기: 영수증을 다 베껴 적을 때까지 대장이 기다려주면(동기, Synchronous) 데이터는 완벽하지만 대장의 속도가 박살 납니다. 안 기다려주고 냅다 응답해 버리면(비동기, Asynchronous) 대장은 미친 듯이 빠르지만 부하들에게 0.5초의 복제 지연(Replication Lag)이 발생하여 낡은 데이터를 읽게(Stale Read) 됨을 해부합니다.
• Implement: 복제 지연(Replication Lag) 시뮬레이션. Master_DB 변수에 값을 넣으면 비동기 스레드가 2초 지연 후 Slave_DB 변수로 값을 복사. 클라이언트가 값을 넣자마자 0.5초 뒤에 Slave_DB를 읽었을 때(Read) 구버전(None) 데이터가 나오는 현상 렌더링.

Recommended

Core Topic 02: 천문학적 행(Row)의 절단, 파티셔닝 (Partitioning)

• Why to Learn: 단일 테이블 데이터가 1억 건을 넘어가면 B-Tree 인덱스마저 메모리를 초과하여 SELECT 성능이 곤두박질치는 물리적 한계를 '논리적 쪼개기'로 극복하기 위함입니다.
• What to Learn:
  • Concepts: Vertical Partitioning (컬럼 쪼개기), Horizontal Partitioning (로우 쪼개기), Range / Hash / List Partition.
  • Skills: 날짜(Date) 등 규칙적인 범위 데이터를 활용한 Range 파티션 테이블 설계.
• How to Learn:
  • 1단계: 수직 파티셔닝(Vertical): USER 테이블에 가벼운 '이름'과 10MB짜리 '프로필 사진 데이터'가 같이 있습니다. '이름'만 조회해도 디스크 I/O가 쓸데없이 폭발합니다. 무거운 컬럼만 뚝 잘라서 1<1> 매핑된 다른 테이블로 찢어버려 성능을 올리는 기법을 해부합니다.
  • 2단계: 수평 파티셔닝(Horizontal): 10년 치 결제 내역 10억 건이 한 테이블에 있습니다. 이를 '2023년 테이블', '2024년 테이블'로 수평(로우 단위)으로 찢습니다. 개발자 쿼리는 똑같이 SELECT * FROM payment지만, DB 엔진이 알아서 2024년 파일만 뒤져서 인덱스 깊이를 확 줄여버리는 마법을 뜯어봅니다.
• Implement: 수평 파티셔닝 논리 분할 스크립트. 배열에 데이터 1,000건을 넣고 Linear Search. 속도가 느림. 데이터를 1100, 101200 등 10개의 작은 배열(파티션)로 해싱해 찢은 뒤, 조회 시 1개의 파티션(100건)만 뒤지는 $O(N)$ 최적화 모사 데모.

Practical

Core Topic 03: 데이터베이스를 찢어발기다, 샤딩 (Sharding)

• Why to Learn: 파티셔닝(논리)을 넘어, 각 조각을 아예 다른 물리적 컴퓨터(서버)로 던져버림으로써 디스크 용량과 쓰기(Write) TPS의 한계를 영원히 뚫어내기 위함입니다.
• What to Learn:
  • Concepts: Database Sharding, Shared-Nothing Architecture, Routing Tier, Cross-shard JOIN 붕괴.
  • Skills: 애플리케이션 레벨 라우터(Router) 구현 및 샤딩으로 인한 글로벌 트랜잭션 제한 식별.
• How to Learn:
  • 1단계: 물리적 절단: AM으로 시작하는 유저는 서울 서버 1대에, NZ로 시작하는 유저는 부산 서버 1대에 넣습니다. 이제 쓰기(Write) 성능도 2배, 디스크 용량도 2배가 되는 Shared-Nothing 구조를 해부합니다.
  • 2단계: 지옥의 문(Trade-offs): 서울 서버 유저가 부산 서버 유저와 친구를 맺었습니다. 두 유저 정보를 JOIN 하려면? 물리적 서버가 달라서 SQL 쿼리 하나로 불가능합니다. 어플리케이션 서버에서 메모리로 각각 가져와 수동으로 합쳐야(In-memory Join) 하는 끔찍한 오버헤드와 분산 트랜잭션 붕괴를 뜯어봅니다.
• Implement: 샤드 라우터(Shard Router) 미니 서버 구현. 클라이언트가 insert(user_id=15, data)를 보내면 user_id % 2 모듈러 연산을 통해 DB_Server_0 혹은 DB_Server_1 리스트 변수로 정확히 데이터를 물리 분리하여 저장하는 로직 렌더링.

Advanced

Core Topic 04: 트래픽 폭풍의 뇌관, 샤드 키와 안정 해시 (Shard Key & Consistent Hashing)

• Why to Learn: 샤딩의 99%는 "어떤 기준으로 찢을 것인가(Shard Key)"에 달려있으며, 이를 잘못 설계하면 수백억 원짜리 DB가 특정 노드 하나에 불타 없어지는(Hotspot) 참사를 방어하기 위함입니다.
• What to Learn:
  • Concepts: Shard Key, Hash-based Sharding vs Range-based Sharding, Hotspot (Celebrity Problem), Consistent Hashing (안정 해시 알고리즘).
  • Skills: 균등 분포를 강제하는 해시 기반 파티셔닝(Hash Partitioning) 설계 및 노드 증설 시 리밸런싱(Rebalancing) 트래픽 계산.
• How to Learn:
  • 1단계: 셀럽 문제(Celebrity Problem): 국가별(Range)로 샤딩했습니다. 한국 유저가 천만 명인데 아프리카 유저는 백 명입니다. 한국 샤드 서버 1번은 CPU 100%로 터지고 아프리카 서버는 놉니다(Hotspot). 이를 막기 위해 유저 ID를 MD5 해싱하여 무작위(Uniform Distribution)로 흩뿌리는 Hash Sharding을 해부합니다.
  • 2단계: 안정 해시(Consistent Hashing): DB 서버가 3대라 ID % 3으로 데이터를 예쁘게 분배해 놨습니다. 트래픽이 폭발해 서버를 4대로 늘렸더니 공식이 ID % 4로 바뀝니다. 전 세계 수십억 개 데이터의 위치가 모조리 틀어져 DB 전체 마이그레이션이 발생합니다. 이를 링(Ring) 구조로 풀어, 노드가 늘어나도 단 $1/N$의 데이터만 이동하게 막아내는 안정 해시 알고리즘의 기적을 뜯어봅니다.
• Implement: 일반 모듈러 연산 vs 안정 해시(Consistent Hashing) 노드 증설 비교 데모. 1만 개 해시 키를 3대의 버킷에 나눔(key % 3). 노드를 4대로 늘렸을 때(key % 4), 이동하는 키의 개수가 $75\%$(재앙)에 달하는 모듈러의 문제와, 안정 해시 링 배치를 통해 재이동 키를 $25\%$로 최소화하는 수학적 최적화 스크립트.

7. Terminology

8. References

Primary

• [P1] CS2023 - Data Management (DM) - Distributed Databases (Replication & Partitioning)
• [P5] SFIA - Database Design (DBDS) - Scaling Strategies

Secondary

• [Designing Data-Intensive Applications] Martin Kleppmann - Replication, Partitioning, and Distributed Data
• [High Performance MySQL] Baron Schwartz - Replication and Scaling

Industry

• [AWS Database Blog] - Sharding strategies with Amazon RDS and DynamoDB
• [Discord Engineering Blog] - How Discord Stores Billions of Messages (Cassandra Sharding)

9. Final Checklist

Primary

• 마스터-슬레이브 복제(Replication)에서 비동기(Asynchronous) 방식을 채택했을 때 얻는 성능적 이점과, 필연적으로 발생하는 '복제 지연(Replication Lag)'의 리스크를 비교할 수 있는가?
• 10억 건의 결제 데이터를 '수평 파티셔닝(Horizontal Partitioning, 연도별 쪼개기)' 했을 때, 쿼리의 인덱스 탐색 속도(B-Tree Depth)가 수학적으로 어떻게 비약적으로 상승하는지 증명할 수 있는가?

Secondary

• 샤딩(Sharding)을 도입하는 순간 기존 RDBMS의 가장 큰 장점인 두 테이블 간의 복잡한 JOIN 쿼리와 외래키(Foreign Key) 제약조건이 왜 완전히 박살나는지 물리적으로 해부할 수 있는가?
• 유명인(Celebrity) 계정에 트래픽이 몰리는 인스타그램에서 레인지 샤딩(Range Sharding) 대신 해시 샤딩(Hash Sharding)을 사용하여 핫스팟(Hotspot) 붕괴를 어떻게 방어하는지 논증할 수 있는가?

Industry

• 노드가 3대인 해시 샤드 환경(id % 3)에서 노드를 1대 추가하여 4대가 되었을 때 기존 데이터의 $75\%$가 이동해야 하는 대재앙을, 안정 해시(Consistent Hashing)가 어떻게 이동량을 $25\%$로 억제하는지 아키텍처 관점으로 설계할 수 있는가?
• 읽기 트래픽 폭주와 쓰기 트래픽 폭주 상황이 발생했을 때, 각각 1) Read Replica 확장 2) Caching 도입 3) Sharding 적용 중 어떤 카드를 먼저 빼들어야 하는지 비용(Complexity) 트레이드오프로 저울질할 수 있는가?