url 단축기 설계하기

1단계 문제 이해 및 설계 범위 확정

어떤 url에 대하여 단축된 결과를 제공해야 한다. 그리고 이 url에 접속하면 원래 url로 갈 수도 있어야한다.

요구사항

1. URL 단축 — 주어진 긴 URL을 훨씬 짧게 줄인다.
2. URL 리디렉션 — 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내한다.
3. 높은 가용성과 규모 확장성, 장애 감내가 요구된다.

개략적 추정

항목	값	계산
일일 쓰기	1억 건	가정
초당 쓰기	약 1,160 QPS	1억 ÷ 24 ÷ 3600
읽기:쓰기 비율	10:1	가정
초당 읽기	11,600 QPS	1,160 × 10
10년간 레코드 수	3,650억 개	1억 × 365 × 10
URL 평균 길이	100바이트	가정
10년간 저장 용량	36.5TB	3,650억 × 100바이트

2단계 개략적 설계안 제시 및 동의 구하기

API 엔드포인트, URL 리디렉션, URL 단축 플로에 대해 살펴보자.

API 엔드포인트

클라이언트는 서버가 제공하는 API 엔드포인트를 통해 통신하며, 여기서는 REST 스타일로 설계한다. URL 단축기에는 기본적으로 두 개의 엔드포인트가 필요하다.

1. URL 단축용

새 단축 URL을 만들려는 클라이언트가 단축할 URL을 인자로 실어 POST 요청을 보낸다.

POST /api/v1/data/shorten

• 인자: { longUrl: longURLString }
• 반환: 단축 URL

2. URL 리디렉션용

단축 URL로 HTTP 요청이 오면 원래 URL로 보내주는 용도다.

GET /api/v1/{shortUrl}

• 반환: HTTP 리디렉션 목적지가 될 원래 URL

URL 리디렉션

단축 URL을 받은 서버는 그 URL을 원래 URL로 바꿔 301 응답의 Location헤더에 넣어 반환한다.

301 vs 302 응답의 차이

둘 다 리디렉션 응답이지만 캐시 동작이 다르다.

• 301 Permanently Moved — 해당 URL에 대한 요청 처리 책임이 Location 헤더의 URL로 영구히 넘어갔다는 뜻이다. 브라우저가 이 응답을 캐시하므로, 이후 같은 단축 URL에 접근하면 단축 URL 서버를 거치지 않고 캐시된 원래 URL로 바로 요청한다.
• 302 Found — 일시적으로 Location 헤더의 URL이 처리한다는 뜻이다. 캐시되지 않으므로 요청은 매번 단축 URL 서버를 먼저 거친 뒤 리디렉션된다.

	301	302
캐시	브라우저가 캐시	캐시하지 않음
서버 부하	첫 요청만 도달 → 낮음	매 요청 도달 → 높음
트래픽 분석	이후 클릭을 못 봄	클릭률·발생 위치 추적 유리

서버 부하 감소가 중요하면 301, 클릭 분석이 중요하면 302를 쓴다.

리디렉션 구현

가장 직관적인 방법은 <단축 URL, 원래 URL> 쌍을 해시 테이블에 저장하는 것이다.

1. 원래 URL = hashTable.get(단축 URL)
2. Location 헤더에 원래 URL을 담아 301 또는 302로 응답

URL 단축

URL 단축

단축 URL이 www.tinyurl.com/{hashValue} 형태라고 하면, 결국 문제는 긴 URL을 hashValue로 대응시킬 해시 함수 fx를 찾는 일이 된다.

이 해시 함수가 만족해야 할 요구사항은 두 가지다.

• 입력으로 주어지는 긴 URL이 서로 다르면 해시 값도 달라야 한다 (충돌 없음)
• 계산된 해시 값에서 원래의 긴 URL을 복원할 수 있어야 한다

---

3단계 상세 설계

이제 데이터 모델, 해시 함수, URL 단축 및 리디렉션에 관한 구체적인 설계안을 만들어보자

데이터 모델

앞에서는 모든 것을 해시 테이블에 두었지만, 메모리는 유한하고 비싸므로 실제 시스템에는 곤란하다. 더 나은 방법은 <단축 URL, 원래 URL> 순서쌍을 관계형 데이터베이스에 저장하는 것이다.

테이블은 단순화하면 세 개의 칼럼을 갖는다. (실제로는 더 많은 칼럼이 있을 수 있다.)

칼럼	설명
id	PK
shortURL	단축 URL의 해시 값
longURL	원래 URL

해시 함수

해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰인다. 편의상 그 결과값을 hashValue라 부른다.

해시 값 길이

hashValue는 [0-9, a-z, A-Z]로 구성되므로 사용 가능한 문자는 10 + 26 + 26 = 62개다. 앞선 추정치대로 3,650억 개의 URL을 만들 수 있어야 하므로, 62ⁿ ≥ 3,650억을 만족하는 n의 최솟값을 찾으면 된다.

n	만들 수 있는 URL 개수
1	62
2	3,844
3	238,328
4	14,776,336
5	916,132,832
6	56,800,235,584
7	3,521,614,606,208 (약 3.5조)
8	218,340,105,584,896

n = 7이면 약 3.5조 개를 만들 수 있어 요구사항을 충분히 만족한다. 따라서 hashValue의 길이는 7로 정한다.

해시 함수 구현 기술로는 두 가지를 살펴본다.

• 해시 후 충돌 해소
• base-62 변환

해시 후 충돌 해소

원래 URL을 7글자로 줄이려면 CRC32, MD5, SHA-1 같은 잘 알려진 해시 함수를 쓰면 된다. https://en.wikipedia.org/wiki/Systems_design을 축약한 결과는 다음과 같다.

해시 함수	해시 결과 (16진수)	길이
CRC32	5cb54054	8
MD5	5a62509a84df9ee03fe1230b9df8b84e	32
SHA-1	0eeae7916c06853901d9ccbefbfcaf4de57ed85b	40

문제는 가장 짧은 CRC32조차 7보다 길다는 점이다.

해결책은 계산된 해시 값에서 앞 7글자만 사용하는 것이다. 다만 이러면 충돌 확률이 올라가므로, 충돌이 나면 longURL 뒤에 사전에 정한 문자열을 덧붙여 다시 해싱하고, 충돌이 사라질 때까지 반복한다.

이 방식은 충돌을 확실히 해소하지만, 단축 URL을 만들 때마다 DB 질의를 최소 한 번은 해야 하므로 오버헤드가 크다. DB 대신 블룸 필터를 쓰면 성능을 높일 수 있다. 어떤 집합에 특정 원소가 있는지를 검사하는, 확률론에 기초한 공간 효율적인 기법이다.

base-62 변환

진법 변환은 URL 단축기 구현에 흔히 쓰이는 접근법으로, 수의 표현 방식이 다른 두 시스템이 같은 수를 공유해야 할 때 유용하다. 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자가 62개이기 때문이다.

문자 대응은 다음과 같다.

값	문자
0 ~ 9	0 ~ 9
10 ~ 35	a ~ z
36 ~ 61	A ~ Z

즉 62진법에서 a는 10, Z는 61을 나타낸다.

예: 11157₁₀을 62진수로 변환

62로 계속 나누면서 나머지를 아래에서 위로 읽는다.

나눗셈	몫	나머지	62진수 표현
11157 ÷ 62	179	59	X
179 ÷ 62	2	55	T
2 ÷ 62	0	2	2

11157 = 2 × 62² + 55 × 62¹ + 59 × 62⁰ = [2, 55, 59] = 2TX

따라서 단축 URL은 https://tinyurl.com/2TX가 된다.

두 접근법 비교

	해시 후 충돌 해소	base-62 변환
단축 URL 길이	고정	가변 (ID가 커지면 길어짐)
ID 생성기	불필요	유일성이 보장되는 ID 생성기 필요
충돌	가능 → 해소 전략 필요	ID 유일성이 전제되므로 불가능
다음 URL 예측	ID로부터 계산하는 방식이 아니라 불가능	ID가 1씩 증가한다면 쉽게 예측 가능 → 보안 문제 소지

URL 단축기 상세 설계

URL 단축기는 시스템의 핵심 컴포넌트이므로 처리 흐름이 논리적으로 단순해야 하고, 언제나 동작하는 상태로 유지되어야 한다. 여기서는 62진법 변환을 사용해 설계한다.

1. 입력으로 긴 URL을 받는다.
2. DB에 해당 URL이 있는지 검사한다.
3. 있다면 이미 단축 URL을 만든 적이 있는 것이므로, DB에서 가져와 클라이언트에 반환한다.
4. 없다면 새로 접수된 URL이므로 유일한 ID를 생성한다. 이 ID는 DB의 기본 키로 쓰인다.
5. 62진법 변환으로 ID를 단축 URL로 만든다.
6. ID, 단축 URL, 원래 URL로 새 레코드를 만든 뒤 단축 URL을 클라이언트에 전달한다.

예시

• 입력 URL: https://en.wikipedia.org/wiki/Systems_design
• ID 생성기가 반환한 ID: 2009215674938
• 이를 62진수로 변환: zn9edcu

ID	shortURL	longURL
2009215674938	zn9edcu	https://en.wikipedia.org/wiki/Systems_design

ID 생성기 주의점

이 ID는 전역적 유일성(globally unique) 이 보장되어야 하는데, 고도로 분산된 환경에서 이런 생성기를 만드는 것은 매우 어렵다. (7장의 분산 ID 생성기 참고)

URL 리디렉션 상세 설계

쓰기보다 읽기가 훨씬 잦은 시스템이므로, <단축 URL, 원래 URL> 쌍을 캐시에 저장해 성능을 높인다.

1. 사용자가 단축 URL을 클릭한다.
2. 로드밸런서가 그 요청을 웹 서버에 전달한다.
3. 단축 URL이 이미 캐시에 있으면 원래 URL을 바로 꺼내 클라이언트에 전달한다.
4. 캐시에 없으면 데이터베이스에서 꺼낸다. DB에도 없다면 사용자가 잘못된 단축 URL을 입력한 경우일 것이다.
5. DB에서 꺼낸 URL을 캐시에 넣은 후 사용자에게 반환한다.

마무리

이 장에서는 URL 단축기의 API, 데이터 모델, 해시 함수, URL 단축 및 리디렉션 절차를 설계했다. 다음 주제는 추가로 논의해보자.

• 처리율 제한 장치(rate limiter) — 지금까지의 시스템은 엄청난 양의 단축 요청이 밀려들면 무력화될 수 있는 잠재적 보안 결함이 있다. 처리율 제한 장치를 두면 IP 주소 등 필터링 규칙으로 요청을 걸러낼 수 있다.
• 웹 서버의 규모 확장 — 웹 계층이 무상태(stateless) 이므로 서버를 자유롭게 증설·삭제할 수 있다.
• 데이터베이스의 규모 확장 — 다중화(replication)나 샤딩(sharding)으로 달성한다.
• 데이터 분석 솔루션 — 어떤 링크가 얼마나 클릭됐는지, 언제 주로 클릭됐는지 등 비즈니스에 중요한 정보를 얻을 수 있다.
• 가용성, 데이터 일관성, 안정성 — 대규모 시스템 운영에 반드시 갖춰야 할 속성들이다.