100억 개의 레코드를 100ms 이내에 어떻게 쿼리하시겠습니까?

Question

IT Interview Practice · Accepted Answer

**접근 패턴(access pattern)을 먼저** 설계한 뒤, 파티셔닝 + 올바른 index/PK를 선택하여 어떤 단일 쿼리도 작고 제한된 슬라이스만 건드리도록 하십시오 — 100억 row를 절대 스캔하지 않습니다. 100억 레코드에서 100ms 이하는 더 빠른 디스크에 관한 것이 아니라, working set을 아주 작게 만드는 것에 관한 것입니다.

```text
Query ─▶ Router ──▶ Partition (by tenant/time) ──▶ Index/PK lookup ─▶ ~thousands of rows
   │                    (prune 99.9% of data)         (B-tree / sort key)
   └─▶ Cache (Redis) ─▶ hit? return in <5ms
                        miss ▼
                   Columnar store (ClickHouse) for aggregates / scans
```

## 접근 패턴이 모든 것을 좌우한다

기술을 선택하기 전에 물으십시오: **point lookup인가, range/aggregate인가?** "사용자 X의 최근 20개 주문 가져오기"는 point/range 쿼리입니다 — partition과 sort key가 그것에 정확히 맞기를 원합니다. "이번 달 지역별 매출 합계"는 분석 스캔(analytical scan)입니다 — row store는 잘못된 도구입니다. 쿼리를 먼저 모델링하는 것이 작동하는 설계와 그럴듯해 보이지만 full-scan하는 설계를 가릅니다.

## 파티셔닝이 탐색 공간을 가지친다

모든 쿼리에 등장하는 key로 테이블을 분할하십시오 — 보통 **tenant_id + time**. 시간 partition이 있으면 "최근 7일" 쿼리는 7개 partition을 읽고 나머지 3년을 무시합니다. 이것이 *partition pruning*입니다: router가 어떤 index를 참조하기도 전에 데이터의 99.9%를 제거합니다.

## 올바른 index / PK 설계

partition 내에서 **primary key는 쿼리의 필터 컬럼을 앞에 배치(front-load)해야 합니다**. DynamoDB에서: partition key = `tenant`, sort key = `timestamp` → range 쿼리는 O(log n) + 순차 읽기입니다. **ClickHouse** 같은 columnar store에서는 sorting key(`ORDER BY (tenant, ts)`)가 엔진이 granule을 건너뛰고 일치하는 블록만 읽게 합니다. covering index는 추가 row fetch를 완전히 없앱니다.

## 저장소 선택

- **Point lookup, 높은 write:** NoSQL key-value(DynamoDB, Cassandra) — key 기준 O(1)에 가깝고, 수평 확장됩니다.
- **분석/집계:** columnar(ClickHouse, BigQuery) — 필요한 컬럼만 읽고, 벡터화됩니다.
- **hot 1%를 캐시:** 앞단의 Redis가 반복 read를 5ms 이하로 흡수합니다. 100억 row이지만 hot key는 수백만 개뿐입니다.

## 면접 관점

면접관은 당신이 **"어떤 데이터베이스?"보다 "쿼리가 무엇인가?"**를 먼저 말하는지 보고 싶어 합니다. 좋은 지원자는 index에 손을 뻗고, 훌륭한 지원자는 100억 row에 대한 index 자체가 거대하다는 점을 짚습니다 — 그래서 *index가 커버할 범위를 줄이기 위해 먼저 파티셔닝*합니다. row 대 columnar 구분과 cache 계층을 짚는 것이 진짜 규모 경험의 신호입니다.

**흔한 함정:** 하나의 거대한 B-tree index를 답으로 제안하는 것. point lookup에는 도움이 되지만 분석 스캔에는 아무 효과가 없고, 그 write가 수집을 병목시킵니다.

## 트레이드오프 및 실패 모드

- **잘못된 partition key** = cross-partition scatter-gather, latency 폭증. 쿼리에 존재하는 key를 고르십시오.
- **Hot partition:** 유명인 tenant가 하나의 shard를 압도합니다 — salting suffix를 추가하십시오.
- **캐시 staleness:** write 시 무효화하거나 TTL 지연을 받아들이십시오.
- **역정규화 비용:** 접근 패턴별로 데이터를 중복시키는 경우가 많습니다. 저장소는 저렴하지만 10초짜리 쿼리는 그렇지 않습니다.

접근 패턴이 모든 것을 좌우한다

파티셔닝이 탐색 공간을 가지친다

올바른 index / PK 설계

저장소 선택

면접 관점

트레이드오프 및 실패 모드

관련 질문