Design URL Shortening Service

요구사항 및 개략적 추정

• URL 입력 받아 단축 URL 생성 및 접속 시 원래 URL로 리다이렉트

• 매일 1억 개 이상 생성 가능

• 숫자 및 영문자(0-9, a-z, A-Z) 62개로 구성된 단축 URL 생성

URL 단축 서비스는 위와 같은 요구사항을 만족해야할 때, 아래와 같이 추정해볼 수 있다.

• 초당 쓰기 연산: 1억 / 24 / 60 / 60 = 1157

• 초당 읽기 연산: (읽기/쓰기 비율 10:1이라 가정)11570

• 레코드 수: (10년 운영 기준) 1억 * 365 * 10 = 3650억

• 저장 용량: (URL 평균 길이 100 가정) 3650억 * 100 = 3650억 * 100B = 36.5TB

기능 정의

클라이언트에게 기능을 제공하기 위해 RESTful API를 사용할 수 있다.

1. URL 단축 생성: 새 단축 URL 생성을 위해 원래 URL을 입력받아 단축 URL을 반환

   • POST /api/v1/data/shorten

   • 인자: {longUrl: longURLstring}

   • 반환: 단축 URL

2. 단축 URL 리다이렉트: 단축 URL을 입력받아 원래 URL로 리다이렉트

   • GET /api/v1/{shortUrl}

   • 반환: 원래 URL 301 응답의 Location 헤더 넣어 반환

301 vs 302 리다이렉트

301과 302 응답 코드 모두 리디렉션 응답이지만, 아래의 차이가 있다.

• 301 Permanently Moved

  • 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전됨을 의미

  • 영구적으로 이전되었으므로, 브라우저는 해당 응답을 캐시하고, 이후에 같은 요청이 발생하면 캐시된 응답을 사용

  • 캐싱으로 인해 서버 부하를 줄일 수 있음

• 302 Found

  • 해당 URL에 대한 HTTP 요청의 처리 책임이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 함을 의미

  • 브라우저는 캐시하지 않고, 항상 단축 URL 서버에 먼저 보내진 후 리다이렉트된 URL로 이동

  • 항상 요청이 오기 때문에, 트래픽 분석이나 로깅에 유용

데이터 모델

URL 단축을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것이지만, 메모리가 유한하기 때문에 실제로 적용하기엔 한계가 있다. 때문에 <단축 URL, 원래 URL> 순서쌍을 관계형 데이터베이스에 저장하는 방법을 사용할 수 있다.

• id: PK

• shortUrl: 단축 URL

• longUrl: 원래 URL

• etc: 생성 날짜, 만료 날짜, 클릭 수 등

해시 함수

URL 단축을 하기 위해 가장 중요한 것은 URL을 특정 해시 값으로 대응시킬 해시 함수를 선택하는 것이다. 해당 해시 함수는 다음과 같은 특징을 가져야 한다.

• 입력으로 주어지는 URL이 다르면 해시 값도 다르게 생성

• 계산된 해시 값은 원래 입력으로 주어진 URL로 복원 가능

해시 값 길이

단축 URL에 사용할 해시 값의 길이는 얼마나 많은 URL을 단축할 수 있는지에 영향을 준다. 사용할 수 있는 문자를 62개(0-9, a-z, A-Z)로 가정하면, n자리 해시 값은 62^n 개의 URL을 단축할 수 있다.(요구사항에 맞게 n을 조절) 해시 함수 구현에 쓰이는 기술로 두 가지가 있는데, 요약하면 아래와 같다.

해시 후 충돌 해소 전략	Base62 변환
단축 URL 길이가 고정됨	단축 URL 길이가 가변적(ID 값 의존)
유일성 보장 ID 생성기 불필요	유일성 보장 ID 생성기 필요
충돌이 가능하여 해소 전략이 필요	ID 유일성이 보장된 후 적용 가능한 전략이기 때문에 충돌 불가능
다음 URL 예측 불가능	ID 기반으로 생성되기 때문에 다음 단축 URL 예측 가능

해시 함수 구현 기술 1 - 해시 후 충돌 해소

긴 URl을 줄이기 위해 해시 함수가 필요한데, CRC32, MD5, SHA-1같이 잘 알려진 해시 함수를 사용할 수 있다.

해시 함수	해시 결과(16진수)
CRC32	5cb54054
MD5	5a62509a84dfee03fe1230b9df8b84e
SHA-1	0eeae7916c06853901d9ccbefbfcaf4de57ed85b

하지만 가장 짧은 해시값도 8글자로, 그 이하의 단축 URL을 생성하기 위해서 아래의 절차를 추가적으로 거쳐야한다.

1. 처음 n개 글자만 이용

2. 해시 결과가 충돌할 수 있으므로 DB에 조회

3. 충돌하는 경우 longURL 뒤에 사전에 정한 문자열 추가

4. 다시 shortURL 생성

위 방법으로 해결을 할 수 있지만, 데이터베이스에 질의를 해야하므로 오버헤드가 커지기 때문에 블룸 필터를 사용해 해결할 수 있다. (블룸 필터 참고)

해시 함수 구현 기술 2 - Base62 변환

진법 변환 방식은 URL 단축기를 구현할 때 흔히 사용되는 방법으로, 62진법을 쓰는 이유는 이번 요구사항에 사용 가능한 문자가 62개이기 때문이다. Base62 변환은 아래와 같이 진행된다.

• 0-9: 0-9, 10-35: a-z, 36-61: A-Z로 대응시켜 표현

• 11157 = 2 * 62^2 + 55 * 62^1 + 59 * 62^0 = 2, 55, 59 = 2TX

이 방법은 ID를 기반으로 생성하기 때문에, 유일성 보장 ID 생성기가 필요하다는 점과, ID가 1씩 증가하는 값이라면 다음 단축 URL을 예측할 수 있어 보안에 취약하다는 단점이 있다.

해당 방식을 통해 URL 단축기를 생성하게 되면, 아래의 처리 흐름을 따르게 된다.

1. 입력으로 긴 URL을 받음

2. 데이터베이스에 해당 URL 존재 여부 확인

3. 존재하는 경우, 해당 URL에 대한 단축 URL 반환

4. 존재하지 않는 경우, 유일 ID 생성

5. 해당 ID를 Base62 변환하여 단축 URL 생성

6. 데이터베이스에 새로운 단축 URL 저장 후 반환

추가 고려 사항

• 캐싱: 쓰기보다 읽기를 더 많은 시스템이므로, <Short URL, Long URL> 쌍을 캐시에 저장하여 읽기 성능을 향상시킬 수 있음

• 처리율 제한 장치: IP 주소를 비롯한 필터링 규칙을 통해 요청 수를 제한하여 한 번에 많은 요청이 들어오는 것을 방지

• 웹 서버 규모 확장: 무상태 계층이므로, 웹 서버를 여러 대 두어 로드 밸런싱을 통해 규모 확장 가능

• 데이터베이스 규모 확장: 데이터베이스다중화나 샤딩을 통해 규모 확장 가능

• 데이터 분석 솔루션: 클릭 수나 사용자 정보를 분석하기 위해 데이터 분석 솔루션을 사용할 수 있음

참고자료

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초