실전 설계 예제 1 (Practical Design Examples 1)
실전 설계 예제 1 (Practical Design Examples 1)¶
난이도: ⭐⭐⭐⭐
개요¶
이 장에서는 실제 시스템 설계 면접에서 자주 등장하는 세 가지 시스템을 설계합니다: URL 단축기, 페이스트빈, Rate Limiter. 각 예제는 요구사항 정의, 용량 추정, 고수준 설계, 상세 설계의 순서로 진행됩니다.
목차¶
1. URL 단축기 (URL Shortener)¶
1.1 요구사항 정의¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 기능 요구사항 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 핵심 기능: │
│ 1. URL 단축: 긴 URL → 짧은 URL 생성 │
│ 2. URL 리다이렉션: 짧은 URL → 원본 URL 리다이렉트 │
│ │
│ 추가 기능: │
│ 3. 사용자 지정 단축 URL (선택) │
│ 4. URL 만료 시간 설정 │
│ 5. 클릭 분석/통계 │
│ │
├─────────────────────────────────────────────────────────────────────────┤
│ 비기능 요구사항 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ - 고가용성: 99.9% uptime │
│ - 낮은 지연: 리다이렉션 < 100ms │
│ - 확장성: 수억 URL 저장 │
│ - 보안: 예측 불가능한 단축 URL │
│ │
└─────────────────────────────────────────────────────────────────────────┘
1.2 용량 추정¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 용량 추정 (Back-of-envelope) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 가정: │
│ - 월간 신규 URL: 100M (1억) │
│ - 읽기/쓰기 비율: 100:1 │
│ - URL 보존 기간: 5년 │
│ - 평균 URL 길이: 100 bytes │
│ │
│ 계산: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 쓰기 QPS: │ │
│ │ 100M / 30일 / 24시간 / 3600초 ≈ 40 writes/sec │ │
│ │ │ │
│ │ 읽기 QPS: │ │
│ │ 40 * 100 = 4,000 reads/sec │ │
│ │ │ │
│ │ 5년간 총 URL 수: │ │
│ │ 100M * 12개월 * 5년 = 6B (60억) │ │
│ │ │ │
│ │ 저장 용량: │ │
│ │ 6B * (7 bytes short + 100 bytes long) ≈ 640GB │ │
│ │ │ │
│ │ 대역폭: │ │
│ │ 4,000 reads/sec * 500 bytes = 2 MB/sec │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 단축 URL 길이 결정: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ Base62: [a-zA-Z0-9] = 62 문자 │ │
│ │ │ │
│ │ 6자리: 62^6 = 56.8 billion (충분!) │ │
│ │ 7자리: 62^7 = 3.5 trillion │ │
│ │ │ │
│ │ → 7자리 사용 (여유 있게) │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
1.3 고수준 설계¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 시스템 아키텍처 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌───────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Client │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌─────────────────┐ │ │
│ │ │ Load Balancer │ │ │
│ │ └────────┬────────┘ │ │
│ │ │ │ │
│ │ ┌─────┴─────┐ │ │
│ │ ▼ ▼ │ │
│ │ ┌─────────┐ ┌─────────┐ │ │
│ │ │API Srv 1│ │API Srv 2│ ... │ │
│ │ └────┬────┘ └────┬────┘ │ │
│ │ │ │ │ │
│ │ └─────┬─────┘ │ │
│ │ │ │ │
│ │ ┌─────┴─────┐ │ │
│ │ ▼ ▼ │ │
│ │ ┌─────────┐ ┌─────────────┐ │ │
│ │ │ Cache │ │ Database │ │ │
│ │ │ (Redis) │ │ (MySQL/Mongo)│ │ │
│ │ └─────────┘ └─────────────┘ │ │
│ │ │ │
│ └───────────────────────────────────────────────────────────────────┘ │
│ │
│ API 설계: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ POST /api/shorten │ │
│ │ Body: { "long_url": "https://...", "expiry": "2024-12-31" } │ │
│ │ Response: { "short_url": "https://tinyurl.com/abc123" } │ │
│ │ │ │
│ │ GET /{short_code} │ │
│ │ Response: 301 Redirect to original URL │ │
│ │ │ │
│ │ GET /api/stats/{short_code} │ │
│ │ Response: { "clicks": 1234, "created_at": "..." } │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
1.4 상세 설계: 단축 URL 생성¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 방법 1: Hash + Collision 처리 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ long_url = "https://example.com/very/long/path" │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ MD5(long_url) = "e4d909c290d0fb1ca068ffaddf22cbd0" │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ Base62(first 43 bits) = "abc123d" │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ 충돌 확인 │ │
│ │ │ │ │
│ │ ┌────┴────┐ │ │
│ │ │ │ │ │
│ │ ▼ ▼ │ │
│ │ 없음 있음 │ │
│ │ │ │ │ │
│ │ │ long_url에 salt 추가 │ │
│ │ │ 재해시 │ │
│ │ │ │ │ │
│ │ └────┬────┘ │ │
│ │ ▼ │ │
│ │ 저장 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 장점: 같은 URL → 같은 단축 URL (캐싱 효율) │
│ 단점: 충돌 처리 로직 필요 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────┐
│ 방법 2: ID 생성기 사용 (권장) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ ┌────────────────────────────────────────────────────────────┐ │ │
│ │ │ ID 생성기 │ │ │
│ │ │ │ │ │
│ │ │ 방법 A: Auto-increment (단일 DB) │ │ │
│ │ │ - 단순하지만 SPOF │ │ │
│ │ │ │ │ │
│ │ │ 방법 B: 범위 기반 (Range-based) │ │ │
│ │ │ ┌────────────────────────────────────────────────────┐ │ │ │
│ │ │ │ ZooKeeper/etcd │ │ │ │
│ │ │ │ ┌──────────────────────────────────────────────┐ │ │ │ │
│ │ │ │ │ Server 1: 1-1,000,000 │ │ │ │ │
│ │ │ │ │ Server 2: 1,000,001-2,000,000 │ │ │ │ │
│ │ │ │ │ Server 3: 2,000,001-3,000,000 │ │ │ │ │
│ │ │ │ └──────────────────────────────────────────────┘ │ │ │ │
│ │ │ └────────────────────────────────────────────────────┘ │ │ │
│ │ │ │ │ │
│ │ │ 방법 C: Snowflake ID │ │ │
│ │ │ [timestamp: 41bits][machine: 10bits][sequence: 12bits] │ │ │
│ │ │ │ │ │
│ │ └────────────────────────────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ID = 123456789 │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ Base62(123456789) = "8M0kX" │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 장점: 충돌 없음, 확장 용이 │
│ 단점: 같은 URL도 다른 단축 URL │
│ │
└─────────────────────────────────────────────────────────────────────────┘
1.5 상세 설계: 리다이렉션¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 리다이렉션 흐름 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ GET /abc123 │
│ │ │
│ ▼ │
│ ┌─────────────┐ │
│ │ Load Balancer│ │
│ └──────┬──────┘ │
│ │ │
│ ▼ │
│ ┌─────────────┐ ┌─────────────┐ │
│ │ API Server │────►│ Redis Cache │ │
│ └──────┬──────┘ └──────┬──────┘ │
│ │ │ │
│ │ 캐시 히트? │
│ │ │ │
│ │ ┌──────┴──────┐ │
│ │ │ │ │
│ │ Yes No │
│ │ │ │ │
│ │ │ ┌──────▼──────┐ │
│ │ │ │ Database │ │
│ │ │ └──────┬──────┘ │
│ │ │ │ │
│ │ │ 캐시 저장 │
│ │ │ │ │
│ │ └──────┬──────┘ │
│ │ │ │
│ ▼ ▼ │
│ ┌─────────────────────────────────────┐ │
│ │ HTTP 301 (영구) or 302 (임시) │ │
│ │ Location: https://original-url.com │ │
│ └─────────────────────────────────────┘ │
│ │
│ 301 vs 302: │
│ - 301: 브라우저 캐싱 → 서버 부하 감소, 통계 부정확 │
│ - 302: 매번 서버 경유 → 정확한 통계, 높은 부하 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
1.6 데이터베이스 스키마¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 데이터베이스 설계 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ urls 테이블: │
│ ┌────────────────────────────────────────────────────────────────┐ │
│ │ Column Type Description │ │
│ ├────────────────────────────────────────────────────────────────┤ │
│ │ id BIGINT PK, auto-increment │ │
│ │ short_code VARCHAR(7) UK, indexed │ │
│ │ long_url VARCHAR(2048) 원본 URL │ │
│ │ user_id BIGINT FK, nullable │ │
│ │ created_at DATETIME 생성 시간 │ │
│ │ expires_at DATETIME 만료 시간, nullable │ │
│ │ click_count BIGINT 클릭 수 │ │
│ └────────────────────────────────────────────────────────────────┘ │
│ │
│ 인덱스: │
│ - PRIMARY KEY (id) │
│ - UNIQUE INDEX idx_short_code (short_code) │
│ - INDEX idx_user_id (user_id) │
│ - INDEX idx_expires_at (expires_at) │
│ │
│ click_analytics 테이블 (선택): │
│ ┌────────────────────────────────────────────────────────────────┐ │
│ │ url_id BIGINT FK │ │
│ │ clicked_at DATETIME 클릭 시간 │ │
│ │ ip_address VARCHAR(45) IPv6 지원 │ │
│ │ user_agent VARCHAR(255) 브라우저 정보 │ │
│ │ referrer VARCHAR(2048) 유입 경로 │ │
│ │ country VARCHAR(2) 국가 코드 │ │
│ └────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2. 페이스트빈 (Pastebin)¶
2.1 요구사항 정의¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 기능 요구사항 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 핵심 기능: │
│ 1. 텍스트 붙여넣기 및 URL 생성 │
│ 2. URL로 텍스트 조회 │
│ 3. 만료 시간 설정 │
│ │
│ 추가 기능: │
│ 4. 구문 강조 (Syntax Highlighting) │
│ 5. 비밀번호 보호 │
│ 6. 원타임 조회 (조회 후 삭제) │
│ │
├─────────────────────────────────────────────────────────────────────────┤
│ 제약 조건 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ - 최대 텍스트 크기: 10MB │
│ - 기본 만료: 30일 │
│ - 익명 사용자도 사용 가능 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2.2 용량 추정¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 용량 추정 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 가정: │
│ - 일간 신규 페이스트: 1M │
│ - 읽기/쓰기 비율: 5:1 │
│ - 평균 텍스트 크기: 10KB │
│ - 보존 기간: 1년 │
│ │
│ 계산: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 쓰기 QPS: 1M / 86400 ≈ 12 writes/sec │ │
│ │ 읽기 QPS: 12 * 5 = 60 reads/sec │ │
│ │ │ │
│ │ 일간 저장: 1M * 10KB = 10GB │ │
│ │ 연간 저장: 10GB * 365 = 3.65TB │ │
│ │ │ │
│ │ 대역폭: │ │
│ │ - 쓰기: 12 * 10KB = 120KB/sec │ │
│ │ - 읽기: 60 * 10KB = 600KB/sec │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2.3 고수준 설계¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 시스템 아키텍처 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌───────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Client │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌─────────────────┐ │ │
│ │ │ Load Balancer │ │ │
│ │ └────────┬────────┘ │ │
│ │ │ │ │
│ │ ┌─────┴─────┐ │ │
│ │ ▼ ▼ │ │
│ │ ┌─────────┐ ┌─────────┐ │ │
│ │ │API Srv 1│ │API Srv 2│ │ │
│ │ └────┬────┘ └────┬────┘ │ │
│ │ │ │ │ │
│ │ └─────┬─────┘ │ │
│ │ │ │ │
│ │ ┌────────┼────────┐ │ │
│ │ ▼ ▼ ▼ │ │
│ │ ┌────┐ ┌───────┐ ┌──────────────┐ │ │
│ │ │Cache│ │MetaDB │ │Object Storage│ │ │
│ │ │Redis│ │MySQL │ │S3/MinIO │ │ │
│ │ └────┘ └───────┘ └──────────────┘ │ │
│ │ │ │
│ └───────────────────────────────────────────────────────────────────┘ │
│ │
│ 저장 전략: │
│ - 메타데이터 (ID, 생성일, 만료일): MySQL │
│ - 실제 텍스트 내용: Object Storage (S3) │
│ - 자주 접근하는 텍스트: Redis 캐시 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2.4 상세 설계: 저장 전략¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 데이터 저장 흐름 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 텍스트 저장: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ POST /api/paste │ │
│ │ { "content": "...", "expires_in": "7d" } │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌────────────────────┐ │ │
│ │ │ 1. ID 생성 │ (URL 단축기와 동일 방식) │ │
│ │ │ → paste_abc123 │ │ │
│ │ └─────────┬──────────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌────────────────────┐ ┌─────────────────────┐ │ │
│ │ │ 2. 내용 저장 │────►│ Object Storage │ │ │
│ │ │ 압축 적용 │ │ Key: paste_abc123 │ │ │
│ │ │ (gzip) │ │ Value: [gzipped] │ │ │
│ │ └─────────┬──────────┘ └─────────────────────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌────────────────────┐ ┌─────────────────────┐ │ │
│ │ │ 3. 메타데이터 저장 │────►│ MySQL │ │ │
│ │ │ (원자적) │ │ id, created_at, │ │ │
│ │ │ │ │ expires_at, size │ │ │
│ │ └─────────┬──────────┘ └─────────────────────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ Response: { "url": "https://paste.io/abc123" } │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 캐싱 전략: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ - 인기 페이스트만 캐시 (조회수 기반) │ │
│ │ - LRU 정책 │ │
│ │ - 캐시 크기: 저장소의 20% (약 700GB) │ │
│ │ - TTL: 1시간 (자주 갱신) │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2.5 만료 정책¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 만료 데이터 정리 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 방법 1: Lazy Deletion (게으른 삭제) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ GET /abc123 │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ expires_at < now()? │ │
│ │ │ │ │
│ │ ┌────┴────┐ │ │
│ │ │ │ │ │
│ │ Yes No │ │
│ │ │ │ │ │
│ │ 404 반환 │ │
│ │ + 삭제 큐에 추가 │ │
│ │ │ │
│ │ 장점: 구현 단순, 즉각적 │ │
│ │ 단점: 조회 안된 데이터는 계속 남음 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 방법 2: Background Cleanup │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Cron Job (매 시간): │ │
│ │ │ │
│ │ SELECT id, storage_key │ │
│ │ FROM pastes │ │
│ │ WHERE expires_at < NOW() │ │
│ │ LIMIT 1000; │ │
│ │ │ │
│ │ for each expired: │ │
│ │ 1. Delete from Object Storage │ │
│ │ 2. Delete from MySQL │ │
│ │ 3. Invalidate Cache │ │
│ │ │ │
│ │ 장점: 저장 공간 확보 │ │
│ │ 단점: 피크 시간 피해야 함 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 권장: 두 방법 조합 │
│ - Lazy: 즉각적인 만료 처리 │
│ - Background: 정기적 정리로 저장 공간 확보 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3. Rate Limiter¶
3.1 요구사항 정의¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 기능 요구사항 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 핵심 기능: │
│ 1. 요청 제한: IP, 사용자, API 키별 │
│ 2. 다양한 시간 윈도우: 초당, 분당, 시간당 │
│ 3. 초과 시 429 응답 │
│ │
│ 비기능 요구사항: │
│ - 분산 환경 지원 │
│ - 낮은 지연 (API 호출마다 체크) │
│ - 높은 가용성 │
│ - 정확성 (레이스 컨디션 방지) │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3.2 알고리즘 비교¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Rate Limiting 알고리즘 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. Token Bucket (토큰 버킷) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ ┌───────────────────────────────────────┐ │ │
│ │ │ Bucket │ │ │
│ │ │ Capacity: 10 tokens │ │ │
│ │ │ ┌───┬───┬───┬───┬───┬───┬───┐ │ │ │
│ │ │ │ ● │ ● │ ● │ ● │ ● │ │ │ │ ← 토큰 추가 │ │
│ │ │ └───┴───┴───┴───┴───┴───┴───┘ │ (1/sec) │ │
│ │ │ │ │ │ │
│ │ └────────┼───────────────────────────────┘ │ │
│ │ │ │ │
│ │ ▼ 요청 시 토큰 소비 │ │
│ │ ┌─────────┐ │ │
│ │ │ Request │ │ │
│ │ └─────────┘ │ │
│ │ │ │
│ │ 특징: │ │
│ │ - 버스트 허용 (버킷에 토큰이 있으면) │ │
│ │ - 일정한 속도로 토큰 보충 │ │
│ │ - 메모리 효율적 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 2. Leaky Bucket (누출 버킷) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ │ 요청 유입 │ │
│ │ ▼ │ │
│ │ ┌─────────┐ │ │
│ │ │ Queue │ ← 큐가 가득 차면 요청 거부 │ │
│ │ │ (FIFO) │ │ │
│ │ └────┬────┘ │ │
│ │ │ │ │
│ │ │ 일정 속도로 누출 (처리) │ │
│ │ ▼ │ │
│ │ ┌─────────┐ │ │
│ │ │ Process │ │ │
│ │ └─────────┘ │ │
│ │ │ │
│ │ 특징: │ │
│ │ - 일정한 처리 속도 보장 │ │
│ │ - 버스트 평활화 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 3. Fixed Window │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 시간 ──────────────────────────────────────────────────────► │ │
│ │ │ │
│ │ │◄── Window 1 ──►│◄── Window 2 ──►│◄── Window 3 ──►│ │ │
│ │ │ (limit: 5) │ (limit: 5) │ (limit: 5) │ │ │
│ │ │ ●●●●● │ ●● │ ●●●● │ │ │
│ │ │ count: 5 │ count: 2 │ count: 4 │ │ │
│ │ │ │
│ │ 문제: 경계에서 버스트 │ │
│ │ Window 1 끝에 5개 + Window 2 시작에 5개 = 10개! │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 4. Sliding Window Log │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 각 요청 타임스탬프 저장: │ │
│ │ [12:00:01, 12:00:15, 12:00:32, 12:00:45, 12:01:02, ...] │ │
│ │ │ │
│ │ 현재 시간 - 1분 이내 요청 수 계산 │ │
│ │ │ │
│ │ 장점: 정확함 │ │
│ │ 단점: 메모리 사용량 높음 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 5. Sliding Window Counter (권장) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 현재 윈도우 + 이전 윈도우 가중 평균 │ │
│ │ │ │
│ │ 이전 윈도우: 3 requests │ │
│ │ 현재 윈도우: 5 requests │ │
│ │ 현재 위치: 윈도우의 70% 지점 │ │
│ │ │ │
│ │ 예상 카운트: 3 * 0.3 + 5 = 5.9 │ │
│ │ │ │
│ │ 장점: 메모리 효율 + 정확도 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3.3 고수준 설계¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Rate Limiter 아키텍처 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 미들웨어로 배치 (API Gateway 또는 서비스 레벨) │
│ │
│ ┌───────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Client │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌─────────────────────────────────────────────────────────────┐ │ │
│ │ │ API Gateway │ │ │
│ │ │ ┌───────────────────────────────────────────────────────┐ │ │ │
│ │ │ │ Rate Limiter Middleware │ │ │ │
│ │ │ │ │ │ │ │
│ │ │ │ ┌────────────┐ ┌────────────────────────────┐ │ │ │ │
│ │ │ │ │ Rate Rules │ │ Redis Cluster │ │ │ │ │
│ │ │ │ │ │─────►│ ┌─────┐ ┌─────┐ ┌─────┐ │ │ │ │ │
│ │ │ │ │ - 100/min │ │ │Node1│ │Node2│ │Node3│ │ │ │ │ │
│ │ │ │ │ - 1000/hr │ │ └─────┘ └─────┘ └─────┘ │ │ │ │ │
│ │ │ │ └────────────┘ └────────────────────────────┘ │ │ │ │
│ │ │ │ │ │ │ │
│ │ │ └───────────────────────────────────────────────────────┘ │ │ │
│ │ └─────────────────────────────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ │ 허용 │ 거부 │ │
│ │ ▼ ▼ │ │
│ │ ┌─────────────────┐ ┌─────────────────────┐ │ │
│ │ │ Backend API │ │ 429 Too Many │ │ │
│ │ │ Servers │ │ Requests │ │ │
│ │ └─────────────────┘ │ Retry-After: 60 │ │ │
│ │ └─────────────────────┘ │ │
│ │ │ │
│ └───────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3.4 Redis 구현: Token Bucket¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Redis Token Bucket 구현 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 데이터 구조: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ Key: rate_limit:{user_id} │ │
│ │ Value: HASH │ │
│ │ - tokens: 현재 토큰 수 │ │
│ │ - last_refill: 마지막 보충 시간 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ Lua Script (원자적 실행): │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ local key = KEYS[1] │ │
│ │ local capacity = tonumber(ARGV[1]) -- 버킷 용량 │ │
│ │ local refill_rate = tonumber(ARGV[2]) -- 초당 보충 토큰 │ │
│ │ local now = tonumber(ARGV[3]) -- 현재 시간 (ms) │ │
│ │ local requested = tonumber(ARGV[4]) -- 요청 토큰 수 │ │
│ │ │ │
│ │ local bucket = redis.call('HGETALL', key) │ │
│ │ local tokens = capacity │ │
│ │ local last_refill = now │ │
│ │ │ │
│ │ if #bucket > 0 then │ │
│ │ tokens = tonumber(bucket[2]) │ │
│ │ last_refill = tonumber(bucket[4]) │ │
│ │ end │ │
│ │ │ │
│ │ -- 토큰 보충 │ │
│ │ local elapsed = (now - last_refill) / 1000 │ │
│ │ local refill = elapsed * refill_rate │ │
│ │ tokens = math.min(capacity, tokens + refill) │ │
│ │ │ │
│ │ -- 요청 처리 │ │
│ │ local allowed = 0 │ │
│ │ if tokens >= requested then │ │
│ │ tokens = tokens - requested │ │
│ │ allowed = 1 │ │
│ │ end │ │
│ │ │ │
│ │ redis.call('HSET', key, 'tokens', tokens, 'last_refill', now) │ │
│ │ redis.call('EXPIRE', key, capacity / refill_rate * 2) │ │
│ │ │ │
│ │ return {allowed, tokens} │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3.5 분산 환경 고려사항¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 분산 Rate Limiter 이슈 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 문제 1: Race Condition │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Server 1: GET counter → 99 │ │
│ │ Server 2: GET counter → 99 │ │
│ │ Server 1: SET counter → 100 (허용) │ │
│ │ Server 2: SET counter → 100 (허용!) ← 한도 초과! │ │
│ │ │ │
│ │ 해결: Lua Script로 원자적 실행 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 문제 2: Redis 클러스터 동기화 지연 │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 해결: │ │
│ │ - 같은 사용자는 같은 Redis 노드로 (Consistent Hashing) │ │
│ │ - 또는 약간의 오차 허용 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 문제 3: Redis 장애 │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Fallback 전략: │ │
│ │ 1. 모든 요청 허용 (서비스 가용성 우선) │ │
│ │ 2. 로컬 캐시로 대체 (정확도 저하) │ │
│ │ 3. 모든 요청 거부 (보안 우선) │ │
│ │ │ │
│ │ 권장: 서비스 특성에 따라 선택 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ Rate Limit 규칙 설정: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ { │ │
│ │ "rules": [ │ │
│ │ { │ │
│ │ "key": "user:{user_id}", │ │
│ │ "limit": 100, │ │
│ │ "window": "60s" │ │
│ │ }, │ │
│ │ { │ │
│ │ "key": "ip:{client_ip}", │ │
│ │ "limit": 1000, │ │
│ │ "window": "1h" │ │
│ │ }, │ │
│ │ { │ │
│ │ "key": "api:{api_key}:/expensive-endpoint", │ │
│ │ "limit": 10, │ │
│ │ "window": "1m" │ │
│ │ } │ │
│ │ ] │ │
│ │ } │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
4. 연습 문제¶
연습 1: URL 단축기 확장¶
기존 URL 단축기에 다음 기능을 추가하는 설계를 하세요: - 국가별 다른 URL로 리다이렉트 - A/B 테스트 지원 (50%는 URL-A, 50%는 URL-B) - 하루 100만 클릭 분석 대시보드
연습 2: 페이스트빈 보안¶
다음 보안 요구사항을 만족하는 설계를 하세요: - 비밀번호로 보호된 페이스트 - 조회 후 자동 삭제 (burn after read) - 클라이언트 사이드 암호화 옵션
연습 3: 동적 Rate Limiting¶
다음 요구사항의 Rate Limiter를 설계하세요: - 사용자 티어별 다른 한도 (무료/유료/기업) - 피크 시간 자동 조정 - API 엔드포인트별 세분화된 제한
다음 단계¶
18_Design_Example_2.md에서 뉴스 피드, 채팅 시스템, 알림 시스템을 설계해봅시다!
참고 자료¶
- "System Design Interview" - Alex Xu
- "Designing Data-Intensive Applications" - Martin Kleppmann
- bit.ly, TinyURL 아키텍처 분석
- Stripe Rate Limiting Best Practices
- GitHub API Rate Limiting