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

Functional Requirement

• https://some-commerce-system.com/soLongUrl?key1=val1&key2=val2... 와 같이 긴 url 을 짧은 URL 으로 단축시켜 제공해야 한다.
• shortened url 은 원천 url 으로 리다이렉트 시켜야 한다.
• 한번 생성된 shortened url 은 영구적으로 원천 url 에 1:1 대응되어 쓰여야 한다.
• shortened url 에는 숫자와 영어 대소문자 조합만 허용한다. (특수문자는 허용하지 않는다.)

Non-Functional Requirements

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

Estimates

• 매일 1억개의 고유한 shortened url 생성 필요

→ 쓰기 요청 : 1억 / 60 / 60 / 24 = 약 1,157 TPS

• 단축 URL 생성 요청 수 대비 읽기 요청 수는 10배 정도

→ 매일 10억개의 shortened url 방문

→ 읽기 요청 : 10억 / 60 / 60 / 24 = 약 11,157 TPS

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

Number of characters in shortened url

• 알파벳 대소문자 + 숫자 → 62개
• 62 ^ N ≥ 3,650억 을 만족하는 최소 N = 7

→ 따라서 shortened url 의 길이 = 7

예) input → <progress> → output X1yE2z3

길이가 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

• url shortening 서비스는 쿠버네티스에서 서빙하는 것을 가정
• consistent hashing-ring 으로 확장 가능한 data persistance 구축
• 빈번하게 발생하는 동일한 요청은 redis 캐싱 디비에서 담당

💡 10.return 단계에서 클라이언트에게 상태코드 몇 번을 주는 게 적절할까?

애플리케이션의 리소스를 절약하려면 301 또는 308, 원천 url 요청에 대한 별도의 데이터분석을 요구한다면 307 이 적절

How to generate shortened url

후보1) 해싱 함수 활용

해싱 함수 : MD5, SHA

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

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

base62 기반으로 shortened url 만드려면 42 비트 필요

→ snowflake ID 는 64 비트로 구성

→ 앞에 42 비트 잘라서 쓰면 분산처리 환경에서는 collision 발생하므로 snowflake ID 는 적절하지 않음

collision 을 보완하는 수단 : bloom filter

해싱 알고리즘 또는 snowflake ID 단독으로만 적용해서는 collision 을 피할 수 없다

→ collision 을 방지하는 다른 수단이 필요하다

• bloom filter : 시간복잡도 O(1) 에 달하는 멤버십 체크로 collision 방지 가능하나, false-positive
• false-positive : 없는데 있다고 오판 (collision 이 없으나 있다고 판단 가능)
• consistent hashing ring : shard scale-out 으로 인한 해싱 미스 방지

ID generating service

• 길이가 7인 문자열을 만드는 데 필요한 42bit (=ID) 를 생성하는 서비스
• 각 파드에서 ID 생성 & 블룸필터 셋에 ID 저장
• 만약 생성한 ID 가 블룸필터 셋에 이미 있다고 판단하면 random bit 를 더해 ID 재생성 후 필터링 재시도
• 고가용성 유지를 위해 블룸필터 셋을 관리하는 스토리지는 다른 AZ 에 복제 인스턴스를 여러 개 둔다

참고하기 좋은 기술 사례

• BloomFilter는 언제 쓰나요?
• 자바의 HashMap 은 어떻게 동작하는가?

기타 레퍼런스

• 레이턴시 추산할 때 참고 할 만한 레퍼런스
• Redirections in HTTP
• Which redirection code should I use for short url
• URL shortening system design
• bloom filter
• consistent hashing
• Implementing bloom filters in Redis