8-URL 단축기 설계

문제 이해 및 설계 범위 확정

기본적 기능
- URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다.
- URL 리다이렉션: 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
- 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨
개략적 추정
- 쓰기 연산: 매일 1억 개의 단축 URL 생성
- 초당 쓰기 연산: 1억/24/3600 = 1160
- 읽기 연산: 읽기 연산과 쓰기 연산 비율을 10:1이라고 하면 초당 11600회 발생한다.
- URL 단축 서비스를 10년간 운영한다고 가정하면 3650억개의 레코드를 보관해야 한다.
- 축약 전 URL의 평균 길이는 100이라고 하자.
- 따라서 10년 동안 필요한 저장 용량은 3650억 * 100 바이트 = 36.5 TB이다.

URL 단축용 엔드 포인트: POST /api/v1/data/shorten
- 인자: {longUrl: longURLstring}
- 반환: 단축 URL

301 Permanently Moved: 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환되 ㄴURL로 이전되었다는 응답이다.
- 영구적으로 이전되었으므로, 브라우저는 이 응답을 캐시한다.
- 장점: 서버 부하를 줄일 수 있다.
302 Found: 해당 URL로 요청이 일시적으로 lOcation 헤더가 지정하는 URL에 의해 처리되어야 한다.
- 클라이언트는 요청을 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리다이렉션 되어야 한다.
- 장점: 트래픽 분석이 중요할 때 클릭 발생률이나 발생 위치를 추적하는 데 유리하다.

단축 URL이 www.tinyurl.com/{hashValue} 같은 형태다.
해시 함수 요구 사항
- 입력으로 주어진 긴 URL이 다른 값이면 해시 값도 달라야 한다.
- 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야한다.

해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰인다.
해시 값 길이: [0-9, a-z, A-Z] 문자로 구성되기 때문에 문자의 개수는 62개다.
- hashValue의 길이를 정하기 위해서는 62^n>=3650억인 의 최소값을 찾아야한다.
- 아까의 추정치에 따르면 n=7이면 3.5조개의 URL을 만들 수 있어서 충분하다.
해시 함수 구현 2가지 방법
- 해시 후 충돌 해소
- base-62 변환
해시 후 충돌 해소
- CRC32, MD5, SHA-1 같이 잘 알려진 해시 함수롤 이용한다.
- 해시 값에서 처음 7개 글자만 이용하지만, 이는 해시 결과가 충돌할 확률이 높아진다.
- 충돌이 실제로 발생했을 때는, 충돌이 해소될 때까지 사전에 정한 문자열일 해시값에 덧붙인다.
- 단점: 단축 URL을 생성할 때 한 번 이상 데이터베이스 질의를 해야 하므로 오버헤드가 크다.
  - 데이터베이스 대신 브룸 필터를 사용하면 성능을 높일 수 있다.
base-62 변환
- ID를 기준으로 62진법으로 변환한다.
해시 후 충돌 해소 vs base-62 변환

예시) 입력된 URL이 https://en.wikipedia.org/wiki/Systems_design
- ID 생성기가 반환한 ID는 2009215674938dlek.
- 이 ID를 62진수로 변환하면 zn9edcu를 얻는다.