1단계. 문제 이해 및 설계 범위 확정
1. URL 단축기의 동작
1-1. 단축 URL 제공 기능
https://www.example.com/q=chatsystem&c=loggedin&v=3&l=long이라고 입력이 주어진 경우- 서비스에서
https://www.tinyurl.com/y7ke-ocwj와 같은 단축 URL을 결과로 제공해야 함
1-2. URL 리디렉션 기능
- 해당 단축 URL을 통해 원래 URL로 갈 수도 있어야 함
2. 트래픽 규모
- 매일 1억 개의 단축 URL 생성 가능
3. 단축 URL의 길이는?
- 짧을 수록 좋음
4. 단축 URL 포함 문제에 대한 제한
- 숫자(0-9)와 영문자(a-z, A-Z)만 사용 가능
5. 단축URL을 삭제하거나 갱신하는 기능
- 시스템 단순화를 위해 삭제나 갱신 기능은 없다고 가정
6. 높은 가용성과 규모 확장성, 장애 감내가 요구됨
2단계. 개략적 설계얀 제시 및 동의 구하기
1. API 엔드포인트
- URL 단축기는 기본적으로 두 개의 엔드포인트를 필요로 함
- URL 단축용 엔드포인트
- URL 리디렉션용 엔드포인트
2. URL 리디렉션
2-1. 리디렉션 응답 비교
- 서버부하를 줄이는 것이 중요하다면 301
- 트래픽 분석이 중요할 때는 302
2-2. 301 vs 302
| 구분 | 301 Moved Permanently | 302 Found (또는 Moved Temporarily) |
|---|---|---|
| 의미 | 영구적인 리디렉션 (URL이 완전히 변경됨) | 임시적인 리디렉션 (일시적으로 다른 URL로 이동) |
| 용도 | 사이트 이전, 구조 변경, 영구 URL 교체 등 | 트래킹, 테스트, 로그인 후 리디렉션 등 |
| 브라우저 동작 | 응답을 캐싱 이후 요청에서도 새 URL로 직접 접근 | 원래 URL로 계속 요청함 (서버가 계속 리디렉션 지시) |
| 검색엔진 처리(SEO) | 링크 가치(Link juice)를 새 URL로 이전 | 링크 가치 유지되지 않음 (임시로 간주) |
| 캐싱 | 캐시될 수 있음 (영구이므로) | 일반적으로 캐시하지 않음 |
| HTTP 응답 코드 | 301 Moved Permanently | 302 Found (이전엔 “Moved Temporarily”) |
| Location 헤더 | 새 URL을 지정 (필수) | 새 URL을 지정 (필수) |
| 브라우저 히스토리 영향 | 새 URL로 교체될 수 있음 | 원래 URL 유지 |
| 주요 사용 사례 | 도메인 변경, HTTPS 전환, 슬러그 변경 | 로그인/세션 리디렉션, A/B 테스트, 추적 URL |
2-3. URL 리디렉션 구현
원래 URL = hashTable.get(단축 URL)
301 또는 302 응답 Location 헤더에 원래 URL을 넣은 후 전송3. URL 단축
- 단축 URL이
www.tinyurl.com/{hashValue}와 같은 형태일 때, - 결국 중요한 것은 긴 URL을 해시 값으로 대응시킬 해시 함수를 찾는 일
3-1. 해시 함수가 만족해야 하는 요구사항
- 입력으로 주어지는 URL이 다른 값이면 해시 값도 달라야 함
- 계산된 해시값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 함
3단계. 상세 설계
1. 데이터 모델
- <단축 URL, 원래 URL>의 순서쌍을 관계형 DB에 저장
2. 해시 함수
- hashValue는 [0-9, a-z, A-Z]의 문자들로 구성됨(10+26+26=62개)
- hashValue의 길이를 정하기 위해서는 62^n>=3650억인 n의 최솟값을 찾아야 함
- n이 7일 때 62^7=3.5조 개의 URL 생성 가능하므로 hashValue의 길이는 7로 결정
2-1. 해시 후 충돌 해소 기법
- 긴 URL을 줄이기 위해서 원래 URL을 7글자 문자열로 줄이는 해시함수가 필요함
1) 해시 함수
- 비암호학적 해시 함수: MurmurHash, CRC32, FNV-1a 등 (빠르고 단순)
- 암호학적 해시 함수: SHA-1, SHA-256, MD5 등 (보안적 목적 시)
| 알고리즘 | 해시 길이 | 특징 | 단축 URL 관점 |
|---|---|---|---|
| CRC32 | 32bit (약 4.3×10⁹개 경우) | 매우 빠름, 단순 체크용 | 빠르지만 충돌 확률 높음 |
| MD5 | 128bit | 균등 분포, 널리 사용 | 속도와 품질 균형 좋음 |
| SHA-1 | 160bit | 충돌 매우 희박, 보안성 높음 | 단축 URL엔 다소 과하지만 안정적 |
2) 해시 재계산 방식(Rehashing with Salt)
- URL을 해시한 후 이미 존재하는(=충돌한) 단축 코드라면, 미리 정한 문자열(또는 숫자)을 붙여 다시 해시
- 해시 공간을 바꿔서 서로 다른 해시 결과를 강제로 생성하는 방식
hash("https://example.com/a") → "A7xPqL2" 이미 존재함 → 충돌 발생! hash("https://example.com/a" + "1") → "bK0RzTf" 새 키 확보
3) Bloom Filter
- 확률적 집합 존재 여부(“이 값이 이미 등록되었는가?”) 를 빠르게 판별하기 위한 비트 배열 기반 데이터 구조
- 충돌 이전에 “이 값이 이미 존재할 가능성이 있나?”를 빠르게 추정하는 확률적 필터
- 여러 개의 서로 다른 해시 함수를 사용 (k개)
- 입력값을 각각 해시 → 비트 배열의 인덱스로 사용 → 비트들을 1로 설정
- 새 값이 들어올 때 → 동일한 해시로 검사 → 해당 비트가 모두 1이면 “이미 존재 가능성이 있음”
2-2. base-62 변환
-
hashValue에 사용할 수 있는 문자 수가 62개이기 때문에 base62 변환
-
문자 매핑 가능
-
값 문자 값 문자 값 문자 0–9 '0'–'9'10–35 'A'–'Z'36–61 'a'–'z'
-
-
base-62 변환 원리
2-3. 해시 후 충돌 해소 전략 vs base 62 변환
| 하하하 | 해시 후 충돌 해소 | base-62 |
|---|---|---|
| 단축 URL의 길이 | 고정 | 가변적. ID 값이 커지면 같이 길어짐 |
| 유일성이 보장되는 ID 생성기 | 필요 없음 | 필요 |
| 충돌 여부 | 충돌 가능. 해소 필요 | ID의 유일성이 보장된 적용가능하기 떄문에 충돌 자체가 불가능 |
| 단축 URL 예측 가능 여부 | 불가능 | ID가 1씩 증가하는 값이라고 가정한다면 다음에 쓸 수 있는 URL 유추 가능 |
3. URL 단축 및 리디렉션
- 사용자가 단축 URL 클릭
- 로드 밸런서가 해당 클릭으로 발생한 요청 웹 서버에 전달
- 단축 URL이 이미 캐시에 있는 경우에는 원래 URL을 바로 꺼내서 클라이언트에 전달
3-1. 캐시 미스의 경우 DB에서 꺼내서 전달. DB에도 없다면 사용자가 잘못된 단축 URL을 입력한 것
3-2. DB에서 꺼낸 URL을 캐시에 넣은 사용자에게 반환
