8. URL 단축기 설계

문제 이해 및 설계 범위 확정

• 시스템 설계 면접 문제는 의도적으로 어떤 정해진 결말을 갖지 않도록 만들어진다.

• 면접장에서 시스템을 성공적으로 설계해 내려면 질문을 통해 모호함을 줄이고 요구사항을 알아내야 한다.

설계 범위(요구 사항)

• URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다.

• URL 리디렉션(Redirection): 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내

• 높은 가용성과 규모 확장성, 장애 감내 요구

개략적 추정

• 쓰기 연산: 매일 1억 개의 단축 URL 생성

• 초당 쓰기 연산: 1억(100,000,000) / 24 / 3,600 = 1,160번

• 읽기 연산: 읽기 연산과 쓰기 연산 비율은 10:1, 읽기 연산은 초당 11,600회 발생

• URL 단축 서비스를 10년간 운영한다고 가정하면 1억 * 365 * 10 = 3,650억개의 레코드를 보관해야 함

• 축약 전 URL의 평균 길이는 100 Byte 라 가정

• 10년 동안 필요한 저장 용량은 3,650억 * 100 Byte = 36.5TB

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

API 엔드포인트

• 클라이언트는 서버가 제공하는 API 엔드포인트를 통해서 서버와 통신

• REST 스타일로 API 설계

URL 단축용 엔드포인트

• 새 단축 URL을 생성하고자 하는 클라이언트는 해당 엔드포인트에 단축할 URL을 인자로 실어서 POST 요청

• API Method: POST

• URL: /api/v1/data/shorten

• Body: {“longUrl”: URL}

• Status Code: 201

• Response: 단축 URL

URL 리디렉션용 엔드포인트

• 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트

• API Method: GET

• URL: /api/v1/shorturl

• Status Code 301

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

URL 리디렉션

301 Permanently Moved

• 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답

• 영구적으로 이전되었으므로, 브라우저는 이 응답을 캐싱한다.

• 추후에 같은 단축 URL에 요청을 보낼 필요가 있을 때 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.

• 브라우저의 캐싱을 사용해 서버의 부하를 줄이는 것이 중요하다면 사용

302 Found

• 주어진 URL로의 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답이다.

• 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리디렉션 되어야 한다.

• 트래픽 분석이 중요한 경우 사용

리디렉션 구현

• URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것

• 단축 URL: 원래 URL

• 원래 URL: hashTable.get(단축 URL)

• 301 또는 302 응답을 Location 헤더에 원래 URL를 넣은 후 전송

URL 단축

중요한 것은 긴 URL을 해시 값으로 대응 시킬 해시 함수 F(x)를 찾는 일이 될 것

해시 함수 요구사항

• 입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야 한다.

• 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원 될 수 있어야 한다.

상세 설계

데이터 모델

• 해시 테이블은 초기 전략으로는 괜찮지만, 설계 시스템에서는 메모리적으로 비싸기 때문에 대규모 시스템에는 적합하지 않다.

• 관계형 데이터베이스에 URL 순서쌍을 저장하는 것으로 해시 테이블을 대체한다.

해시 함수

해시 값 길이

• 구해지는 해시 값(HashValue)는 [0–9, a-z, A-Z]의 문자들로 구성

• 사용할 수 있는 문자의 개수는 10 + 26 + 26 = 62

• 해시의 길이를 정하기 위해서는 62 ** n ≥ 3,650억 인 n의 최솟값을 알아야 한다.

• n = 7이면 3.5조 개의 URL을 생성 가능하고, 요구사항을 만족시킨다.

해시 후 충돌 해소

• 해시 함수를 만드는 손쉬운 방법은 CRC32, MD5, SHA-1 같은 잘 알려진 해시 함수를 이용하는 것

• 해시 함수를 사용한 문자열이 기존 저장된 문자열과 충돌이 날 경우, 충돌이 해소될 때까지 지정된 문자열을 사용하여 해소

• 해당 방법은 많은 양의 데이터베이스 질의를 해야 할 수 있기 때문에 오버헤드가 크다.

• 블룸 필터를 DB 대신 사용하는 방법으로 문제점을 해결한다. 블룸 필터는 어떤 집합에 특정 원소가 있는 지 검사할 수 있도록 하는 확률론에 기초한 공간 효율이 좋은 기술

base-62 변환

• 진법 변환은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나

• 수의 표현 방식이 다른 두 시스템이 같은 수를 공유해야 하는 경우에 유용하다.

• 62진법을 쓰는 이유는 해시 함수에 사용할 수 있는 문자의 개수가 62개이기 때문이다.

URL 단축기 상세 설계

• 시스템의 핵심 컴포넌트이므로, 그 처리 흐름이 논리적으로 단순해야 하고, 기능적으로는 언제나 동작하는 상태로 유지되어야 한다.

단축기 동작 흐름

1. 입력으로 긴 URL를 받는다.

2. DB에 해당 URL이 있는지 검사한다.

3. DB에 URL이 있다면, 단축 URL를 만든 적이 있는 것이다. 따라서 DB에서 단축 URL를 가져와서 클라이언트에게 반환한다.

4. DB에 없는 경우, 해당 URL은 새로 접수된 것이므로 유일한 ID를 생성한다. 이 ID는 DB의 기본 키로 사용된다.

5. 62진법 변환을 적용, ID를 단축 URL로 만든다.

6. ID, 단축 URL, 원래 URL로 새 DB 레코드를 만든 후 단축 URL를 클라이언트에게 전달한다.

URL 리디렉션 상세 설계

• 쓰기보다는 읽기를 더 자주하는 시스템이기 때문에, <단축 URL, 원래 URL> 쌍을 캐시에 저장하여 성능을 높혔다.

다만, 캐시에는 TTL을 사용하여 주기적으로 사용하지 않는 URL를 지워주는 방법도 좋을 것

로드벨런서 동작 흐름

1. 사용자가 단축 URL를 클릭한다.

2. 로드벨런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달한다.

3. 단축 URL이 이미 캐시에 있는 경우에는 원래 URL을 바로 꺼내서 클라이언트에게 전달한다.

4. 캐시에 해당 단축 URL이 없는 경우에는 DB에서 꺼낸다.

5. DB에서 꺼낸 URL를 캐시에 넣은 후 사용자에게 반환한다.