문제 이해 및 설계 범위 확정
시스템 설계 면접 문제는 정해진 결말을 없다. 그래서 질문을 통해 모호함을 줄이고 요구사항을 알아내야 한다.
기본적 기능
- 긴 URL 단축 기능
- URL redirection
- 높은 가용성과 규모 확장성 그리고 장애 감내
개략적 추정
- 쓰기 연산: 매일 1억 개의 단축 URL 생성
- 초당 쓰기 연산: 1억/24/3600 = 1160
- 읽기 연산: 읽기 연산과 쓰기 연산 비율은 10:1이라고 하면 읽기 연산은 초당 11600회 발생
- URL 단축 서비스를 10년간 운영한다고 하면 1억 x 365 x 10 = 3650억 개
- 축약전 URL 평균 길이는 100
- 저장 용량은 3650억 x 100 바이트 = 36.5TB
개략적 설계안 제시 및 동의 구하기
API 엔드 포인트
- url 단축용 엔드포인트
- POST /api/v1/data/shorten
- 인자: {longUrl: longURLstring}
- 반환: 단축 URL
- url 리다렉션용 엔드포인트
- GET /api/v1/{shortUrl}
- 반환: HTTP 리다렉션 목적지가 될 원래 URL
URL 리다렉션
- 브라우저에 단축 URL 입력 (/api/v1/{shortUrl}) -> 301에 location 헤더에 원래 url 반환
- 301 (permanerntly moved) vs 302 (found)
- 301은 영구적으로 책임이 반환된 url로 이전되었다는 뜻. 그래서 브라우저는 응답을 캐싱하고 있다가 단축 URL에 요처을 보낼 필요가 있으면 캐시된 원래 URL로 요청을 보낸다.
- 302는 일시적으로 지정하는 url에 의해 처리다 되어야 한다는 뜻. 그래서 클라이언트 요청은 언제나 단축 URL서버에 먼저 보내진 후에 원래 URL로 리다렉션 되어야 한다.
- 301은 서버 부하를 줄일 수 있으나 302는 발생 위치를 추적하는데 좀더 유리하다.
- URL 리다이렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는것
URL 단축
- 긴 URL을 이 해시 값으로 대응시킬 해시 함수 fx를 찾는 일이다.
- 해시 함수는 다음 요구사항을 만족 해야 한다.
- 입력으로 주어진 긴 URL이 다른 값이면 해시 값도 달라야 한다.
- 계산된 해시 값은 원래 입력으로 주어진 긴 URL로 복원될 수 있어야 한다.
상세 설계
데이터 모델
- 개략적 설계를 진행할 때 처럼 해시 테이블을 메모리에 두고 관리하는 방법은 실제 시스템에서 쓰기 곤란하다. 왜냐하면 메모리는 유한한데다 비싸기 때문이다.
해시 함수
- 원래 URL를 단축 URL로 변환하는데 사용
해시 값 길이
- [0-9. a-z, A-Z]의 문자로 구성된다. (62개)
- 시스템은 3650억개의 URL을 만들어야한다. 즉 최소 62^7은 되어야 요구 사항을 만족 시킬수 있다.
- 고로 길이는 7
해시 후 충돌 해소
- 긴 URL을 7자 문자열로 줄이는 해시함수가 필요
- CRC32, MD5, SHA-1과 같이 잘알려진 해시 함수 이용가능 하지만 가장 짧은 해시값 조차도 7보다 길다.
- 해시 값의 처음 7글자만 이용하는 것으로 해결가능 하나 이러면 충돌 확률이 높아진다.
- 충돌이 해소 될 때까지 사전에 정한 문자열을 본 URL뒤에 덧붙이고 다시 해시를 구한다.
- 이방법은 단축 URL 생성시마다 해시 값이 중복 되었는지를 디비에 질의해야 함으로 오버헤드가 크다. 하지만 블룸 필터를 사용하면 성능을 높일 수 있다.
base-62변환
- 숫자기반 UUID를 생성해서 62 진법으로 변환해서 사용하는 버
해시 후 충돌 해소 vs base-62변환
해시 후 충돌 해소
- 단축 URL이 고정됨
- 유이성이 보장되는 ID 생성기 필요치 않음
- 충돌 해소 전략 필요
- 다음에 쓸 URL 추측 불가
base-62
- 단축 URL의 길이가 가변적 ID가 커지면 같이 길어짐
- 유일성 보장 ID 생성기 필ㅇ
- 충돌은 일어나지 않음
- ID가 1씩 증가하면 다음에 쓸 URL 추측 가능
URL 단축기 상세 설계
62진법 변환 기법 사용
1. 입력으로 긴 URL을 받는다.
2. 데이터베이스에 해당 URL이 있는지 검사한다.
3. 데이터베이스에 있다면 단축URL를 만든 적이 있는것으로 데이터베이스에서 검색된 결과를 반홚한다.
4. 데이터 베이스에 없는경우 새로운 URL임으로 UUID를 생성한다.
5. 62진법을 적용해서 단축 URL를 만든다.
6. UUID (DB id로 사용), 단축 URL, 원래 URL로 레코드를 만든후 디비에 저장하고 단축 URL를 클라이언트에 반환한다.
URL 리다렉션 상세 설계
쓰기보다 읽기를 자주 하는 시스템임으로 단축 URL, 원래 URL을 쌍으로 캐시하여 성능을 높인다.
1. 사용자가 단축 URL을 클릭
2. 로드밸런서가 해당 클릭으로 발생한 요청을 웹서버에 전달
3. 캐시에 단축 URL이 있는경우 원래 URL로 바로 응답
4. 캐시에 없는 경우 데이터베이스에서 꺼낸다. 데이터베이스에도 없다면 사용자가 단축URL를 잘못 입력한 경우이다.
5. 데이터베이스에서 꺼낸 URL를 캐시에 넣은 후 사용자에게 반환
마무리
처리율 제한장치
많은 단축 요청이 밀려들 경우 무력화 될 수 있다. 그래서 처리율 제한 장치를 통해 요청을 걸러낼 수 있다.
웹서버 규모 확장
무상태 계층이므로 웹 서버를 자유로이 증설 또는 삭제할 수 있다.
데이터베이스 규모 확장
데이터베이스 다중화 또는 샤딩을 하여 규모 확장성을 달성할 수 있다.
데이터 분석 솔루션
데이터 분석 솔루션을 통해 어떤 링크를 얼마나 많은 사용자가 클릭 햇는지 주로 언제 클릭 햇는지 등 중요 정보를 알아낼 수 있다.
가용성, 데이터 일관성, 안정성
질문
- 해시 충돌 해결시 해시값뒤에 사전에 정한 문자열을 붙이는건가 본래 URL에 붙이는건가? 해시값 뒤에 붙이는 건가?
- 사전에 정의한 값이라면 +문과 같이 url에 영향을 안주는??
- 디비에 저장시 사전에 정한 문자열이 붙은 걸 저장 아니면 본래 URL 저장?
- 본래 URL 저장시면 단축 url로 사용할 해시값이 본래 url 기반이 아니여서 문제가 없나?
- 사전에 정의한 문자열을 붙인 url를 넣으면 디비에 해당 url이 존재하는지 검사시 like문 또는 replace등 을 통해 조회하고자 하는 url과 사전에 정의한 문자열이 붙인 형태까지 검사해야 할 것 같다.
