가정
- 특정 URL에 대한 단축 URL을 결과로 제공하고, 이 URL로 접속하면 원래 URL로 갈 수 있어야 함
- 매일 1억개의 단축 URL을 생성해야 함
- 단축 URL의 길이는 짧을수록 좋음
- 숫자와 영문자만 사용
- 단축 URL 삭제나 갱신은 할 수 없다고 가정
- 기본적인 기능
- URL 단축
- URL 리디렉션
- 높은 가용성과 규모 확장성, 장애 감내
개략적 추정
- 쓰기 연산: 매일 1억개의 단축 URL 생성
- 초당 약 1160회
- 읽기 연산: 읽기:쓰기 비율이 10:1일 경우, 읽기는 초당 약 11600회
- 10년간 운영한다고 가정하면 3650억개의 레코드를 보관
- 단축 전 URL 평균 길이가 100이라면, 필요한 저장 용량은 36.5TB
개략적인 설계
API 엔드포인트
- REST 스타일
- URL 단축용 엔드포인트
- 클라이언트는 단축할 URL을 인자로 POST 요청
- POST/a pi/vi/data/shorten
- 단축 URL 반환
- 클라이언트는 단축할 URL을 인자로 POST 요청
- URL 리디렉션용 엔드포인트
- 단축 URL에 대한 HTTP 요청이 오면 원래 URL을 보내주기 위한 엔드포인트
- GET/a pi/vi/shortUrl
- 리디렉션 목적지가 될 원래 URL 반환
- 단축 URL에 대한 HTTP 요청이 오면 원래 URL을 보내주기 위한 엔드포인트
URL 리디렉션
- 단축 URL을 받은 서버는 그 URL을 원래 URL로 바꿔 301 응답의 Location 헤더에 넣어 반환
- 301(Permanently Moved)
- URL에 대한 HITP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답
- 브라우저는 이 응답을 캐시(cache)
- 같은 단축 URL에 요청을 보낼 필요가 있을 때 브라우저는 캐시된 원래 URL로 요청
- URL에 대한 HITP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답
- 302(Found)
- 주어진 URL로의 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답
- 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리디렉션
- 주어진 URL로의 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답
- 301(Permanently Moved)
- 서버 부하를 줄이는 것은 301이, 트래픽 분석은 302가 유리
- URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것
URL 단축
- 해시 함수 요구사항
- 입력 URL이 다르면 해시 값도 달라야 함
- 해시 값으로 원래 입력된 URL을 복원할 수 있어야 함
상세 설계
데이터 모델
- 해시 테이블은 메모리의 유한성 및 비용 때문에 실제로 적용하기 곤란
- RDB 적용
- id(PK), short_URL, long_URL
해시함수
- 사용 가능한 문자는 62개
- $62^n \ge 365billion$ 인 n의 최솟값을 찾아야 함
- 대략 7
- 따라서 hashValue의 길이는 7로 설정
- 손 쉬운 방법은 CRC32, MD5, SHA-1같이 잘 알려진 해시 함수를 사용하는 것
- 그러나 해시값이 7보다 길게 나오게 된다
- 해결법
- 해시 후 충돌 해소
- 해시 함수 적용 후 첫 7글자만 사용
- 해시 충돌이 발생했을 경우
- longURL 뒤에 사전에 정한 문자열 추가 후 다시 해시
- 해시 충돌이 없어질 때까지 반복
- DB 쿼리가 한 번 이상 발생하므로 오버헤드가 큼
- DB 대신 블룸 필터를 사용하면 성능을 높일 수 있음
- 해시 후 충돌 해소
- base-62 변환
- 사용 가능 문자 개수가 62개이므로, 62진법 변환(base conversion) 적용
- 십진수 11157을 변환한다고 할 때
- 0은 0으로 , 9는 9로 , 10은 a로 , 11은 h로 , … 35는 z로 , 36은 A로 , … 61은 Z로 대응
- 그럼 2TX로 변환 가능
| 해시 후 충돌 해소 | base-62 변환환 |
|---|---|
| 단축 URL 길이 고정 | 단축 URL 길이 가변적(ID값 크기에 비례) |
| 유일성이 보장되는 ID 생성기 필요 X | 유일성이 보장되는 ID 생성기 필요 X |
| 충돌 해소 전략 필요 | ID 유일성 보장으로 인해 충돌 X |
| 다음에 쓸 수 있는 URL 예상 불가 | ID가 1씩 증가한다고 가정하면 다음에 쓸 수 있는 단축 URL 추론 가능해 보안상 문제 |
URL 단축기 상세 설계
- 처리 흐름
- 긴 URL 입력 받음
- DB에 해당 URL 있는지 검사
- 없다면, 유일한 ID 생성(DB의 PK)
- ID를 base-62로 단축 URL로 변환
- 해당되는 단축 URL 클라이언트에 반환
URL 리디렉션 상세 설계
- 읽기가 더 많은 시스템이라, <단축 URL, 원래 URL>을 캐싱
- 로드밸런서의 동작 흐름
- 사용자가 단축 URL 클릭
- 로드밸런서가 요청을 WS로 전달
- 단축 URL이 캐시에 있는 경우, 원래 URL을 클라이언트에 반환
- 캐시에 없는 경우, DB에서 찾아오고 캐싱한 후 반환
추가적으로 생각해볼 것
- 처리율 제한 장치
- 엄청난 양의 URL 단축 요청이 들어올 경우 시스템이 마비될 수 있음
- 처리율 제한 장치로, IP 주소를 비롯한 필터링 규칙을 이용
- WS의 규모 확장
- 본 설계의 웹 계층은 stateless 계층이므로 증설/삭제가 자유로움
- DB의 규모 확장
- DB를 다중화하거나 샤딩해 규모 확장성 달성
- 데이터 분석 솔루션
- URL 단축기에 데이터 분석 솔루션을 통합해 비즈니스에 필요한 정보를 알아낼 수 있음
- 가용성, 데이터 일관성, 안정성