시스템 설계 면접의 공통 문법

URL 단축기를 설계하다 보면 키-값 저장소의 문제와 닮아 있고, 웹 크롤러를 설계하다 보면 Rate Limiter의 구조와 겹친다. 이 반복이 우연일까? 아니면 분산 시스템 설계에는 몇 가지 공통 문법이 있는 걸까?

쓰기 경로: 충돌 없는 식별자를 어떻게 만드는가

모든 시스템은 결국 무언가에 이름을 붙여야 한다. URL 단축 키, 분산 ID, 크롤링 대상 URL — 각기 다른 문제처럼 보이지만 핵심 질문은 같다. 분산 환경에서 중복 없이, 예측 불가능하게, 빠르게 식별자를 생성하는 방법은?

URL 단축 서비스에서 랜덤 Base62 7자를 선택한 이유는 단순하다. 62⁷ ≈ 3.5조 개의 공간에 4.7억 개를 채우면 충돌 확률이 0.013% 이하다. 재시도 비용이 충돌 확률보다 훨씬 저렴하다.

분산 ID 생성기에서는 이 문제가 더 날카롭다. 여러 서버가 동시에 ID를 생성하면 타임스탬프만으로는 충돌을 막을 수 없다. Snowflake ID의 64비트 구성은 이 문제를 비트 분리로 해결한다.

Bit:  63      62~22          21~12       11~0
     ┌──┬──────────────┬──────────┬──────────┐
     │ 0│ 타임스탬프    │ 서버ID   │ 시퀀스   │
     │  │ (41비트)     │ (10비트) │ (12비트) │
     └──┴──────────────┴──────────┴──────────┘

타임스탬프가 상위 비트에 있으므로 ID는 자동으로 시간 순서로 정렬된다. 같은 밀리초 안에서는 서버 ID와 시퀀스 번호가 충돌을 막는다. 서버당 초당 400만 ID — 락 없이.

읽기 경로: 뜨거운 데이터를 어디서 차단하는가

리디렉션 지연시간 10ms 이하, 자동완성 응답 100ms 이하 — 이 숫자들을 DB 직접 조회로 달성할 수 없다. 모든 시스템이 캐시를 두지만, 어디에, 어떤 형태로 두느냐가 설계의 핵심이다.

URL 단축 서비스의 읽기 경로는 단순하다. Redis에서 Cache-Aside로 단축 키를 조회하고, 미스 시 MySQL에서 읽어 다시 캐싱한다. 인기 URL 20%가 트래픽 80%를 차지하므로 160MB 캐시로 충분하다.

검색 자동완성은 한 단계 더 나아간다. Trie 각 노드에 Top-K 결과를 미리 계산해 저장하면, “sys” 입력 시 sys 노드까지 O(접두사 길이)로 이동한 뒤 결과를 O(1)로 반환할 수 있다. 탐색 비용을 쓰기 시점으로 앞당기는 전략이다.

확률적 자료구조: 정확성을 일부 포기하면 얻는 것

웹 크롤러는 10억 URL의 방문 여부를 추적해야 한다. HashSet이면 64GB 메모리가 필요하다. Bloom Filter를 쓰면 1.2GB로 같은 문제를 해결한다 — 단, False Positive 1% 이하를 허용하는 대가로.

이 선택이 합리적인 이유는 오판의 비용이 비대칭이기 때문이다. 방문한 URL을 미방문으로 판단하는 False Negative는 없다. 미방문 URL을 방문했다고 오판하는 False Positive는 해당 URL을 한 번 크롤링 안 하는 결과를 낳는다 — 치명적이지 않다.

키-값 저장소의 일관성 모델도 같은 논리를 따른다. W=1, R=1로 설정하면 쓰기 직후 읽기에서 오래된 값을 볼 수 있다. 하지만 AP 시스템을 목표로 설계했다면 이 비일관성의 비용을 의도적으로 수용한 것이다.

비동기 분리: 무엇을 동기로 할 것인가

알림 시스템에서 결제 완료 이벤트가 발생했을 때, API가 FCM/APNs 호출까지 기다린다면 결제 응답이 외부 서비스 지연에 직접 노출된다. Kafka로 비동기 분리하면 API는 즉시 응답하고, Worker가 알림 발송을 책임진다.

이 패턴은 웹 크롤러의 통계 수집, 자동완성의 빈도 업데이트에서도 반복된다. 검색어 빈도를 실시간으로 Trie에 업데이트하면 읽기 잠금이 병목이 된다. 1시간 배치로 분리하면 읽기 성능을 완전히 유지한다 — 최신성을 1시간 포기하는 대가로.

확장: 단일 서버에서 분산으로 가는 순서

Rate Limiter는 초당 100만 요청에서 Redis 단일 서버가 병목이 될 수 있다. 그 전에 먼저 Lua Script로 원자성을 확보하고, 이후 로컬 카운터(L1) + Redis(L2) 2단계로 확장한다. 키-값 저장소는 일관성 해싱으로 서버를 추가할 때 평균 K/N개의 키만 이동하도록 설계한다.

설계 문서들이 공통으로 제시하는 확장 순서가 있다. 먼저 캐시 히트율을 높이고, 다음으로 읽기 복제본을 추가하고, 마지막으로 샤딩한다. 처음부터 샤딩으로 시작하는 설계는 대부분 과설계다.

정리

• 충돌 없는 식별자 생성은 비트 분리(Snowflake) 또는 **충분히 큰 확률 공간(Base62)**으로 해결한다.
• 읽기 경로 최적화는 결과를 쓰기 시점으로 앞당기는 것이다 — Trie의 Top-K 사전 계산이 대표적이다.
• 확률적 자료구조(Bloom Filter)와 약한 일관성(W=1)은 오판의 비용이 비대칭일 때 합리적인 선택이다.
• 비동기 분리는 항상 멱등성 설계를 수반한다.

시스템 설계 면접에서 “왜 이 선택을 했는가”라는 질문의 답은 거의 항상 트레이드오프다. 다음 글에서는 대용량 서비스 — 비디오 스트리밍과 뉴스피드 — 로 이동해, 이 패턴들이 수십억 사용자 규모에서 어떻게 변형되는지 추적한다.