URL 단축기 설계

문제 이해 및 설계 범위 확정

이 시스템의 기본적 기능은 아래와 같다.

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

개략적 추정

• 쓰기 연산: 매일 1억 개의 단축 URL 생성
• 초당 쓰기 연산: 1억(100million) / 24 / 3600 = 1160
• 읽기 연산: 읽기 연산과 쓰기 연산 비율은 10:1이라고 하자. 그 경우 읽기 연산은 초당 11,600회 발생한다(1160 × 10 = 11,600).
• URL 단축 서비스를 10년간 운영한다고 가정하면 1억(100million) × 365 × 10 = 3650억(365billion) 개의 레코드를 보관해야 한다.
• 축약 전 URL의 평균 길이는 100이라고 하자.
• 따라서 10년 동안 필요한 저장 용량은 3650억(365billion) × 100바이트 = 36.5TB이다.

 

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

 

1. API endpoint

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

우리는 엔드포인트를 REST 스타일로 설계해보자. RESTful API [1] 

URL 단축기는 기본적으로 두개의 엔드포인트를 필요로 한다.

1) URL 단축용 엔드포인트 : 새 단축 URL 을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 실어서 POST요청을 보내야한다. 이 엔드포인트는 다음과 같은 형태를 띈다.

 

2) URL 디리렉션용 엔드포인트 : 단축 URL에 대해서 HTTP요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트

 

 

2. URL 리디렉션

브라우저에 단축 URL을 입력하면 위와 같은 일이 생긴다. 

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

 

- 301 Permanently Moved :  이 응답은 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답이다. 영구적이전되었으므로, 브라우저는 이 응답을 캐시한다. 추후 같은 URL에 요청을 보낼 필요가 있을때 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.  

-- 서버 부하를 줄여준다. 첫번째 요청만 단축 URL로 전송되기 때문이다. 

 

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

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

-- 트래픽 분석에 용이하다. 

 

해시 테이블에 <단축 URL, 원래URL> 의 쌍을 저장한다고 가정하면, 다음과 같이 URL 리디렉션이 구현될 수 있다. 

 - 원래 URL = hastTable.get(단축 URL)

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

 

 

3. URL 단축 플로

단축 URl이 www.tinyurl.com/{hashValue}  같은 형태로보면, 결국 긴 URl을 이 해시 값으로 대응하는 해시 함수f 를 찾는 일이다. 

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

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

 

상세 설계

데이터 모델

해시 테이블에 모든 개략적 설계를 두는건실제 시스템에 쓰긴 곤란하다. 너무 비싸기 때문이다.

<단축 URL, 원래URL>의 순서쌍을 관계형 데이터 베이스에 저장하는것이다. 

 

해시 함수

해시 함수(hash function)는 원래 URL을 단축 URL로 변환할때 쓴다. 해시 함수가 계산하는 단축 URL 값을 hashValue라고 한다. 

 

해시 값 길이

hashValue [0-9, a-z, A-Z] 로 구성된다. 10+26+26=62개 문자 개수다. 길이는 62^n >= 3650억(365 billion)인 n의 최솟값을 찾는다. 이 시스템은 3650개의 url을 만들어 낼 수 있어야 한다. 

-hashValue의 길이와, 해시 함수가 만들어 낼 수 있는 URL개수 사이의 관계  예시로, n=7은 3.5조개 URL을 만들 수 있다. 

해시 함수 구현에 쓰이는 기술 2가지, 해시 후 충돌 해소 방법. 다른 하나는 base-62 변환 방법

1. 해시 후 충돌 해소

긴 URl을 줄이려면, 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다. 아래는 https://en.wikipedia.org/wiki/Systems_design을을 축약한 결과이다.

충돌하면, 해시 결과가 충돌이 안발생할때까지, 사전에 정한 문자열을 해시에 덧붙인다.  블룸 필터[2] 확률론에 기초한 공간 효율이 좋은 기술이다. 

 

2. base-62 변환 방법

진법 변환(base conversion) 은 URL 단축기 구현시 흔히 사용되는 방법이다. 

 URL 단축기 상세 설계

URL 단축기는 시스템의 핵심 구성임으로 처리 흐름이 논리적으로 단순하고, 기능적으로 언제나 동작해야한다. 62진법 변환 기법을 사용해 설계할 것이다. 

긴걸 받는다. 

db에 해당 url있는지 체크 

db에 있으면 해당 url에 대한 단축 url을 만든적이 있는 것이다. 그러니 db에서 단축url을 가져와서 클라이언트에게 반환한다.

db에 없으면, 해당 url은 새로 접수한것으로 유일한 ID를 생성한다. ID는 db의 기본키로 사용된다. 

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

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

 

이 ID는 단축 URL을 만들때 사용할 ID를 만들고, 전역적유일성이 보장되어야 한다. 

고도 분산된 환경에서 이런 생성기는 어렵지만, 7장을 다시 확인해보면된다. 

 

 

URL 리디렉션 상세 설계

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

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

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

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

캐시에 해당 URL단축이 없으면 DB에서 꺼낸다. DB에 없다면 잘못된 단축 URL을 입력한 경우일 것이다.

DB에서 꺼낸 URL을 캐시에 넣은 후 클라이언트에게 반환한다.

 

 

마무리 

• 처리율 제한 장치(rate limiter): 지금까지 살펴본 시스템은 엄청난 양의 URL 단축 요청이 밀려들 경우 무력화될 수 있다는 잠재적 보안 결함을 갖고 있다. 처리율 제한 장치를 두면, IP 주소를 비롯한 필터링 규칙(filtering rule)들을 이용해 요청을 걸러낼 수 있을 것이다. 처리율 제한 장치에 대해서는 4장에서 다룬 바 있다. 기억이 가물가물하다면 다시 한번 살펴보도록 하자.
• 웹 서버의 규모 확장: 본 설계에 포함된 웹 계층은 무상태(stateless) 계층이므로, 웹 서버를 자유로이 증설하거나 삭제할 수 있다.
• 데이터베이스의 규모 확장: 데이터베이스를 다중화하거나 샤딩(sharding)하여 규모 확장성을 달성할 수 있다.
• 데이터 분석 솔루션(analytics): 성공적인 비즈니스를 위해서는 데이터가 중요하다. URL 단축기에 데이터 분석 솔루션을 통합해 두면 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아낼 수 있을 것이다.
• 가용성, 데이터 일관성, 안정성: 대규모 시스템이 성공적으로 운영되기 위해서는 반드시 갖추어야 할 속성들이다. 이에 대해서는 1장에서 자세히 다루었다. 기억을 되살리고 싶다면 다시 한번 읽어보도록 하자.

이번 장도 성공적으로 마친 여러분, 축하한다. 멋지게 마무리한 스스로를 마음껏 격려하도록 하자!

참고문헌

[1] A RESTful Tutorial: https://www.restapitutorial.com/index.html

[2] Bloom filter: https://en.wikipedia.org/wiki/Bloom_filter