URL Shortening Service
요구사항 및 개략적 추정
Section titled “요구사항 및 개략적 추정”- 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를 사용할 수 있다.
- URL 단축 생성: 새 단축 URL 생성을 위해 원래 URL을 입력받아 단축 URL을 반환
POST /api/v1/data/shorten- 인자:
{longUrl: longURLstring} - 반환: 단축 URL
- 단축 URL 리다이렉트: 단축 URL을 입력받아 원래 URL로 리다이렉트
GET /api/v1/{shortUrl}- 반환: 원래 URL 301 응답의 Location 헤더 넣어 반환
301 vs 302 리다이렉트
Section titled “301 vs 302 리다이렉트”301과 302 응답 코드 모두 리디렉션 응답이지만, 아래의 차이가 있다.
- 301 Permanently Moved
- 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전됨을 의미
- 영구적으로 이전되었으므로, 브라우저는 해당 응답을 캐시하고, 이후에 같은 요청이 발생하면 캐시된 응답을 사용
- 캐싱으로 인해 서버 부하를 줄일 수 있음
- 302 Found
- 해당 URL에 대한 HTTP 요청의 처리 책임이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 함을 의미
- 브라우저는 캐시하지 않고, 항상 단축 URL 서버에 먼저 보내진 후 리다이렉트된 URL로 이동
- 항상 요청이 오기 때문에, 트래픽 분석이나 로깅에 유용
데이터 모델
Section titled “데이터 모델”URL 단축을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것이지만, 메모리가 유한하기 때문에 실제로 적용하기엔 한계가 있다.
때문에 <단축 URL, 원래 URL> 순서쌍을 관계형 데이터베이스에 저장하는 방법을 사용할 수 있다.
- id: PK
- shortUrl: 단축 URL
- longUrl: 원래 URL
- etc: 생성 날짜, 만료 날짜, 클릭 수 등
URL 단축을 하기 위해 가장 중요한 것은 URL을 특정 해시 값으로 대응시킬 해시 함수를 선택하는 것이다.
해당 해시 함수는 다음과 같은 특징을 가져야 한다.
- 입력으로 주어지는 URL이 다르면 해시 값도 다르게 생성
- 계산된 해시 값은 원래 입력으로 주어진 URL로 복원 가능
해시 값 길이
Section titled “해시 값 길이”단축 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 - 해시 후 충돌 해소
Section titled “해시 함수 구현 기술 1 - 해시 후 충돌 해소”긴 URl을 줄이기 위해 해시 함수가 필요한데, CRC32, MD5, SHA-1같이 잘 알려진 해시 함수를 사용할 수 있다.
| 해시 함수 | 해시 결과(16진수) |
|---|---|
| CRC32 | 5cb54054 |
| MD5 | 5a62509a84dfee03fe1230b9df8b84e |
| SHA-1 | 0eeae7916c06853901d9ccbefbfcaf4de57ed85b |
하지만 가장 짧은 해시값도 8글자로, 그 이하의 단축 URL을 생성하기 위해서 아래의 절차를 추가적으로 거쳐야한다.
- 처음 n개 글자만 이용
- 해시 결과가 충돌할 수 있으므로 DB에 조회
- 충돌하는 경우 longURL 뒤에 사전에 정한 문자열 추가
- 다시 shortURL 생성
위 방법으로 해결을 할 수 있지만, 데이터베이스에 질의를 해야하므로 오버헤드가 커지기 때문에 블룸 필터를 사용해 해결할 수 있다. (블룸 필터 참고)
해시 함수 구현 기술 2 - Base62 변환
Section titled “해시 함수 구현 기술 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 단축기를 생성하게 되면, 아래의 처리 흐름을 따르게 된다.
- 입력으로 긴 URL을 받음
- 데이터베이스에 해당 URL 존재 여부 확인
- 존재하는 경우, 해당 URL에 대한 단축 URL 반환
- 존재하지 않는 경우, 유일 ID 생성
- 해당 ID를 Base62 변환하여 단축 URL 생성
- 데이터베이스에 새로운 단축 URL 저장 후 반환
추가 고려 사항
Section titled “추가 고려 사항”- 캐싱: 쓰기보다 읽기를 더 많은 시스템이므로, <Short URL, Long URL> 쌍을 캐시에 저장하여 읽기 성능을 향상시킬 수 있음
- 처리율 제한 장치: IP 주소를 비롯한 필터링 규칙을 통해 요청 수를 제한하여 한 번에 많은 요청이 들어오는 것을 방지
- 웹 서버 규모 확장: 무상태 계층이므로, 웹 서버를 여러 대 두어 로드 밸런싱을 통해 규모 확장 가능
- 데이터베이스 규모 확장: 데이터베이스다중화나 샤딩을 통해 규모 확장 가능
- 데이터 분석 솔루션: 클릭 수나 사용자 정보를 분석하기 위해 데이터 분석 솔루션을 사용할 수 있음