대규모 시스템 설계 기초 책 정리 : 8 URL 단축키 설계

laply park·2025년 1월 31일

URL 단축키 대규모 시스템 설계 기초 시스템설계

대규모 시스템 설계 기초

목록 보기

8/12

읽을때 마다 새로운 지식을 알게되는 책이지만, 다음 챕터로 넘어 갈수록 너무 어려워져서 손이가지 않는 책으로 최대한 많이 이해하고 완독을 목표로 정리를 하기위해서 글을 작성하게 되었다.

처음에는 2부 부터 읽다가 왜 1을 읽지 않느냐는 질문을 받고 1부를 읽게되었고 1부 부터 읽는게 필수라고 할정도로 난이도 차이가 있다.

잘근잘근 씹어먹듯, 많은 지식을 남길 수 있도록 열심히 정리해보자!
가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 예스24

URL 단축키 설계

URL 단축키는 다음과 같은 방법으로 동작한다.
길이가 긴 URL을 단축한 URL로 변환 생성해서 접근할 수 있도록 단축URL 을 만들어 주는 서버로 해당 서버는 API 를 통해 생성하고 길이가 긴 URL 을 쉽게 접근할수 있도록 만들어준다.

먼저 같이 볼 수 있는 부분은 API 엔드포인트 이다.

API Endpoint

클라이언트는 변환하기 위해 서버의 API Endpoint를 통해 서버와 통신을 진행한다.
각각 두개의 동작API 가 필요한데 자세히 살펴 보자.

URL 단축 엔드포인트

새 단축 URL을 만들고자 하는 클라이언트는 이 엔드포인트에 긴URL 을 인자로 담아 POST 요청을 보낸다.


POST /api/v1/data/shorten

# body
{
	"longUrl": "longURLstring" 
}

# response
단축 URL

URL 리디렉션용 엔드포인트

단축 URL 에 대해 요청이 오면 원래 URL로 리다이렉트 해 주는 용도의 엔드포인트


GET /api/v1/shortUrl

# response 
301, 302 상태코드
Location - longURLstring

아래와 같이 응답 데이터가 전송되어 원래 주소로 리다이렉트 되도록 동작한다.
각각 301, 302 의 상태코드값에 따라 웹 브라우저에서 Location 으로 리다이렉트 된다.

각각 상태코드별 동작 이동 정보

301 Permanently moved

해당 URL 이 요청책임이 location 으로 이전되었다는 응답으로 영구 이전되었다는 말이다. 브라우저는 이 응답을 캐시하고, 다시 같은 URL 요청이 왔을때, 캐시된 원래 URL 로 요청을 보낸다.

302 Found

일시적으로 location 해더가 지정하는 URL 에 의해 처리되어야 한다는 응답이다. 일시적이기 때문에 301과 다르게 항상 기존 URL 로 먼저 이동후 리다이렉트 한다.

각각 301은 부하분한에 좋고, 트래픽 분석이 필수라면 302로 처리되는게 유리하다.

URL 단축

구현을 위한 직관적인 방법은 해시 테이블을 이용하는것이다.
<단축 URL, 원래 URL> 을 매칭한다.

www.tinyurl.com/hashvalue
hashvalue = 단축 URL

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

이 f(x) 는

입력으로 주어지는 긴 URL이 다른 값이면 hash 도 다른 값이다.
계산 hash 값은 원래 입력으로 주어졌던 긴 URL로 다시 복원될 수 있어야 한다.

데이터 구조

단축 URL / 원래 URL 의 순서쌍을 효율적으로 보관하기 위해서는 관계형 DB에 저장한다.
구조는 아래와 같다.

-	컬럼
URL	ID
-	shortUrl
-	longUrl

해시 함수

단축 URL은 0-9, a-z, A-Z 의 문자들로 구성된다.
사용할 수 있는 문자의 갯수는 10+26+26 = 62, 총 62개의 문자를 사용할 수 있다.

URL 의 길이를 정하기 위해서는 $62^n$ 을 기준으로 사용량에 따른 n의 최소값을 찾아야한다.

n	$62^n$	값
1	$62^1$	62
2	$62^2$	3,844
3	$62^3$	238,328
4	$62^4$	14,776,336
5	$62^5$	916,132,832
6	$62^6$	56,800,235,584
7	$62^7$	3,521,614,606,208
8	$62^8$	218,340,105,584,896

n이 7개면 3.5조개의 URL을 만들 수 있다.

해시 구현 함수

각각 해시를 구현 하는 함수는 다음과 같습니다.
1. 해시 후 충돌함수
CRC32, MD5, SHA-1 등 해시 함수로 변환, 각각 변환하면 최소 7자리보다 더 긴 값이 나온다.

7자리만 사용하기 위해 앞에서 부터 7자리를 이용한다.
다만, 충돌 할 확률이 높다.

이를 해결하기 위해 충돌 발생시 사전에 정한 값을 해시값에 더해서 적용한다.

base 62 변환
진법 변환 (base conversion)

62 진법으로 변환하는것으로 문자열이 62개이므로 해당 값으로 변환 한다.
가령 10진수로 11157 인 값을 62 진수로 변환하면 다믕과 같다. $11157_{10}=2*62^2+55*62^1+59*62^0 =[2,55,59]=>[2,T,X]=2TX_{62}$

따라서 단축 URL은 https://tinyUrl.com/2TX 이다.
+숫자로 형성된 ID 값이 11157 이면 유일 값으로 단축 URL 을 생성할 수 있다.

상세설계

URL 단축키 상세설계

동작흐름은 다음과 같다.
1. 입력으로 긴 URL 을 받는다.
2. 데이터베이스에 해당 URL 이 있는지 검사한다.
3. 데이터베이스에 있다면 해당 URL 에 대한 단축 URL 을 만든적이 있는것이라. 별도 만들지 않고 존재하는 정보를 출력한다.
4. 데이터베이스에 없는 경우 해당 URL은 새로 접수 된 것이므로 유일한 ID를 생성한다.
5. 62진법 변환을 적용, ID 는 데이터 베이스의 기본키로 사용한다.
6. ID, 단축 URL, 원래 URL 을 새 데이터 베이스 레코드를 만든후 단축 URL 을 전송한다.

URL 리디렉션 상세 설계

동작흐름은 다음과 같다.
1. 사용자가 단축 URL 을 클릭한다.
2. 로드 벨런서가 해당 클릭으로 발생한 요청을 웹서버에 전달한다.
3. 단축 URL 이 이미 캐시에 있는경우에는 원래 URL 을 바로 꺼내서 클라이언트에게 전달한다.
4. 캐시에 해당 단축 URL 이 없는 경우에는 데이터 베이스에서 꺼낸다. 데이터베이스에도 없다면, 잘못 호출 한 것이다.
5. DB 에서 꺼낸 URL 을 캐시에 넣은 후 사용자에게 반환한다.