[시스템 디자인 스터디] shortening url

Functional Requirement

• https://some-commerce-system.com/soLongUrl?key1=val1&key2=val2... 와 같이 긴 url 을 짧은 URL 으로 단축시켜 제공해야 한다.

• 단축 url 은 원천 url 으로 리다이렉트 시켜야 한다.

• 한번 생성된 단축 url 은 영구적으로 원천 url 에 1:1 대응되어 쓰여야 한다.

• 단축 url 에는 숫자와 영어 대소문자 조합만 허용한다. (특수문자는 허용하지 않는다.)

Non-Functional Requirements

• 고가용성, 규모 확장성이 가능해야 한다.

Estimates

• 매일 1억개의 고유한 단축 url 생성 필요 → 쓰기 요청 : 1억 / 60 / 60 / 24 = 약 1,157 TPS

• 단축 URL 생성 요청 수 대비 읽기 요청 수는 10배 정도 → 매일 10억개의 단축 url 방문 -> 읽기 요청 : 10억 / 60 / 60 / 24 = 약 11,157 TPS

• 단축 url 서비스를 10년 간 운영한다면 총 3,650억개의 단축 url 생성 필요

number of characters in shortened url

• 알파벳 대소문자 + 숫자 → 62개

• 62 ^ N ≥ 3,650억 을 만족하는 최소 N = 7

Base62

• 바이너리 데이터를 62개 문자(a~z, A~Z, 0-9)로 표현

• 6 bit 씩 끊어서 인코딩한다.
• 이유) bit(이진수)로만 구성된 데이터를 62개 문자들로 표현하려면 2 ^ 6 = 64 → 6 bit 필요
• https://en.wikipedia.org/wiki/Base62
• 예) 101010 111000 000001 → g u 1

• a~z, A~Z, 0-9 으로 구성한 7개의 고유한 문자열을 만들려면 6 bit X 7 = 42 bit 필요
→ 42 bit 짜리 unique ID 를 만들어주는 ID generator 가 필요하다.

Data Persistence

DBMS

• Nosql (MongoDB, Casssandra…)

• 천억 단위의 레코드 저장 & 조회 → data intensive DBMS 필요

Schema

System Design

How to generate shortened url

후보1) 해싱 함수 활용

• MD5 : 인풋에 대해 128bit 짜리 해시값 생성 → 캐릭터 길이가 7인 shortened url 만드려면 앞에서부터 잘라야 함 → collision 발생

• SHA256 : 인풋에 대해 256bit 짜리 해시값 생성 → 캐릭터 길이가 7인 shortened url 만드려면 앞에서부터 잘라야 함 → collision 발생 (MD5 보다 colliision 확률 높음)

후보2) Twitter’s Snowflake ID generator 으로 input key 생성

후보3) token ranging with consistent hashing ring

• consistent hashing ring : shard scale-out 으로 인한 해싱 미스 방지.

• bloom filter : 시간복잡도 O(1) 에 달하는 멤버십 체크로 collision 방지 가능하나, false-positive.