URL 단축기 설계

1. URL 단축 시스템의 기본 기능

1. URL 단축

   • 주어진 긴 URL을 훨씬 짧은 URL로 변환

2. URL 리디렉션

   • 단축 URL로 HTTP 요청이 들어오면 원래 URL로 안내

3. 비기능 요구사항

   • 높은 가용성
   • 높은 규모 확장성
   • 장애 감내

---

2. 요구사항

2.1 쓰기 연산

• 매일 1억 개의 단축 URL 생성

초당 평균 쓰기 연산:

1억 ÷ 24 ÷ 3,600
≈ 1,160회/초

2.2 읽기 연산

• 읽기와 쓰기의 비율을 10:1로 가정
• 초당 평균 읽기 연산:

1,160 × 10
= 11,600회/초

2.3 저장할 레코드 수

• 10년간 운영한다고 가정

1억 × 365 × 10
= 3,650억 개

• 10년 동안 약 3,650억 개의 레코드 보관 필요

2.4 저장 용량

• 단축 전 URL의 평균 길이를 100바이트로 가정

3,650억 × 100바이트
= 36.5TB

• 10년 동안 필요한 저장 용량은 약 36.5TB

---

3. API 엔드포인트

클라이언트는 서버가 제공하는 API 엔드포인트를 통해 URL 단축 시스템과 통신함.

이번 설계는 REST 스타일로 구성함.

3.1 URL 단축 엔드포인트

• 새로운 단축 URL을 생성하기 위한 엔드포인트
• 클라이언트는 단축할 URL을 요청에 담아 POST 방식으로 전송

POST /api/v1/data/shorten

3.2 URL 리디렉션 엔드포인트

• 단축 URL 요청을 원래 URL로 리디렉션하기 위한 엔드포인트

GET /api/v1/shortUrl

---

4. URL 리디렉션 응답 절차

1. 클라이언트가 단축 URL 서버에 요청 전송
2. 단축 URL 서버가 단축 URL에 대응하는 원래 URL 조회
3. 원래 URL을 HTTP 응답의 Location 헤더에 포함
4. 클라이언트가 Location 헤더에 지정된 원래 URL로 이동
5. 원래 URL 서버 방문

---

5. HTTP 301과 302의 차이

두 상태 코드는 모두 리디렉션에 사용되지만 의미와 활용 방식에 차이가 있음.

5.1 301 Moved Permanently

• 해당 URL의 요청 처리 위치가 Location 헤더의 URL로 영구적으로 변경되었음을 의미
• 브라우저나 중간 캐시에 리디렉션 정보가 저장될 가능성이 높음
• 이후 같은 단축 URL을 요청할 때 단축 URL 서버를 거치지 않고 원래 URL로 직접 이동할 수 있음
• 단축 URL 서버의 부하를 줄이는 데 유리

5.2 302 Found

• 요청이 현재는 Location 헤더에 지정된 다른 URL에서 임시로 처리됨을 의미
• 일반적으로 301보다 장기적으로 캐시될 가능성이 낮음
• 요청할 때마다 단축 URL 서버를 거쳐 원래 URL로 이동할 가능성이 높음
• 단, 명시적인 캐시 정책에 따라 캐시될 수도 있음

5.3 선택 기준

301이 적합한 경우

• 리디렉션 대상이 영구적으로 유지됨
• 단축 URL 서버의 부하를 줄이는 것이 중요함
• 모든 클릭 요청을 직접 추적할 필요가 적음

302가 적합한 경우

• 클릭 수와 접속 위치 등의 트래픽 분석이 중요함
• 단축 URL의 목적지가 나중에 변경될 수 있음
• 요청이 단축 URL 서버를 거치도록 유지할 필요가 있음

---

6. URL 리디렉션 구현

URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것임.

해시 테이블에는 다음과 같은 쌍을 저장함.

<단축 URL, 원래 URL>

원래 URL 조회:

원래 URL = hashTable.get(단축 URL)

조회한 원래 URL을 HTTP 301 또는 302 응답의 Location 헤더에 넣어 전송함.

---

7. 단축 코드 생성 시 고려할 점

긴 URL을 단축 코드로 변환할 때는 단축 코드가 가능한 한 고르게 분포하도록 해야 함.

다만 고정 길이의 단축 코드를 사용하면 서로 다른 긴 URL이 같은 단축 코드로 변환되는 충돌 가능성을 완전히 없앨 수 없음.

예를 들어 7자리 단축 코드를 사용하면 출력 가능한 코드 수는 유한함.

62⁷ = 약 3.52조 개

따라서 다음 조건이 필요함.

• 단축 코드가 고르게 분포하도록 생성
• 충돌 발생 여부 확인
• 충돌 발생 시 새로운 코드 생성
• 동일한 코드가 중복 저장되지 않도록 데이터베이스 제약 설정

또한 단축 코드에서 원래 URL을 직접 복원하는 방식이 아님.

단축 코드
→ 데이터베이스 또는 캐시 조회
→ 원래 URL 반환

원래 URL은 별도 저장소에 반드시 보관해야 함.

---

구체적인 설계안

8. 데이터 모델

모든 <단축 URL, 원래 URL> 쌍을 메모리의 해시 테이블에 저장하기에는 메모리 용량이 제한적이고 비용도 큼.

따라서 전체 데이터는 관계형 데이터베이스에 영구 저장함.

8.1 데이터베이스 조회 성능

관계형 데이터베이스는 메모리 해시 테이블보다 느리지만, 단축 코드에 인덱스를 설정하면 전체 테이블을 탐색하지 않고 빠르게 조회 가능함.

예시:

SELECT long_url
FROM urls
WHERE short_code = ?;

8.2 캐시 활용

데이터베이스만 사용하는 것이 아니라 Redis 등의 캐시를 함께 사용함.

조회 흐름:

단축 URL 요청
→ 캐시 조회
→ 캐시 적중: 원래 URL 반환
→ 캐시 미스: 데이터베이스 조회
→ 조회 결과를 캐시에 저장
→ 원래 URL로 리디렉션

• 데이터베이스

  • 전체 URL 데이터의 영구 저장 담당

• 캐시

  • 자주 조회되는 URL의 빠른 응답 담당

---

9. 단축 코드 문자 구성

편의상 단축 URL의 고유 코드 부분을 hashValue라고 부름.

hashValue는 다음 문자로 구성함.

• 숫자: 0~9
• 소문자: a~z
• 대문자: A~Z

사용 가능한 전체 문자 수:

10 + 26 + 26
= 62개

---

10. 단축 코드 길이 계산

10년 동안 약 3,650억 개의 URL을 생성할 예정이므로 다음 조건을 만족하는 최소 n을 구해야 함.

62ⁿ ≥ 3,650억

계산 결과:

62⁶ = 56,800,235,584
약 568억

62⁷ = 3,521,614,606,208
약 3.52조

따라서 필요한 최소 길이는 7자리임.

---

11. 단축 코드 생성 방식

단축 코드를 생성하는 방식은 다음 두 가지로 나눌 수 있음.

1. 해시 후 충돌 해소
2. 유일 ID의 Base62 변환

Base62는 해시 함수가 아니라 숫자를 62진수 문자열로 표현하는 인코딩 방식임.

---

12. 해시 후 충돌 해소

12.1 기본 과정

1. 긴 URL에 해시 함수 적용
2. 생성된 해시값에서 필요한 길이만큼 문자 선택
3. 현재 설계에서는 앞의 7글자를 단축 코드로 사용
4. 데이터베이스에서 해당 코드의 존재 여부 확인
5. 충돌하지 않으면 저장
6. 충돌하면 새로운 값을 만들어 다시 해싱

예시:

hash(longURL)
→ 충돌 발생

hash(longURL + "1")
→ 다시 확인

hash(longURL + "2")
→ 다시 확인

즉, 충돌이 발생하면 원래 URL에 사전에 정한 문자열이나 salt를 추가한 뒤 다시 해싱함.

단축 코드 자체에 문자열을 계속 덧붙이는 방식은 7자리 고정 길이 요구와 맞지 않으므로 사용하지 않음.

12.2 장점

• 별도의 순차적 ID 생성기가 없어도 단축 코드 생성 가능
• 동일한 입력에 대해 일정한 결과를 만들도록 구현 가능

12.3 단점

• 충돌 가능성 존재
• 생성한 코드가 이미 사용 중인지 확인해야 함
• 충돌이 반복되면 데이터베이스 질의와 재시도 증가
• 같은 URL을 중복 생성할지 재사용할지에 대한 정책 필요

---

13. 충돌 검사를 위한 데이터베이스와 블룸 필터

해시 후 충돌 해소 방식에서는 생성한 단축 코드가 이미 존재하는지 확인해야 함.

기본 흐름:

단축 코드 생성
→ 데이터베이스 존재 여부 확인
→ 충돌 시 코드 재생성
→ 다시 데이터베이스 확인

여러 서버가 동시에 같은 단축 코드를 생성할 가능성에 대비해 데이터베이스에 유일 제약을 설정할 수 있음.

UNIQUE(short_code)

13.1 블룸 필터 활용

블룸 필터는 데이터베이스를 완전히 대체하는 것이 아니라 불필요한 데이터베이스 조회를 줄이는 보조 자료구조임.

블룸 필터의 판단 결과:

없음
→ 확실히 존재하지 않음

있음
→ 존재할 수도 있음

처리 흐름:

새 단축 코드 생성
→ 블룸 필터 확인

블룸 필터가 없다고 판단한 경우

• 해당 코드는 확실히 존재하지 않음
• 바로 데이터베이스 저장 시도 가능

블룸 필터가 있을 수 있다고 판단한 경우

• 거짓 양성 가능성 존재
• 데이터베이스에서 실제 존재 여부 확인 필요

따라서 블룸 필터를 사용하면 확실히 존재하지 않는 코드에 대한 데이터베이스 조회를 줄일 수 있음.

---

14. Base62 변환

Base62는 유일한 숫자 ID를 62개의 문자로 구성된 짧은 문자열로 변환하는 방식임.

사용 문자:

0-9
a-z
A-Z

14.1 동작 과정

유일한 숫자 ID 생성
→ 숫자 ID를 Base62로 변환
→ 단축 코드 생성

예를 들어 숫자 ID가 125라면 이를 Base62 문자열로 변환하여 짧은 코드로 표현 가능함.

14.2 Base62를 사용하는 이유

• 한 자리에서 62개의 값을 표현 가능
• 10진수보다 같은 숫자를 더 짧은 문자열로 표현 가능
• URL에 사용하기 적합한 영문자와 숫자로 구성
• 숫자 ID가 유일하면 Base62 결과도 유일함
• 해시 충돌이 발생하지 않음

14.3 단점

• 순차적인 숫자 ID를 사용하면 단축 코드도 어느 정도 예측 가능
• 전체 URL 생성량이나 생성 순서가 외부에 노출될 가능성 존재
• 전역적으로 유일한 ID 생성기가 필요함

---

15. 두 방식 비교

구분	해시 후 충돌 해소	유일 ID의 Base62 변환
입력값	긴 URL	유일 숫자 ID
충돌 가능성	있음	ID가 유일하면 없음
충돌 검사	필요	불필요
DB 조회	충돌 확인을 위해 필요	URL 저장 및 조회에 사용
별도 ID 생성기	불필요	필요
코드 예측 가능성	상대적으로 낮음	순차 ID 사용 시 높음
구현 복잡도	충돌 처리 필요	ID 생성기 관리 필요

---

16. Base62 방식의 처리 흐름

1. 클라이언트가 긴 URL을 전달
2. ID 생성기가 전역적으로 유일한 숫자 ID 생성
3. 숫자 ID를 Base62 문자열로 변환
4. Base62 결과를 단축 코드로 사용
5. 데이터베이스에 새로운 레코드 저장
6. 생성된 단축 URL을 클라이언트에게 반환

기본 레코드:

ID | shortURL | longURL

ID는 전역적으로 유일해야 함.

---

17. 데이터 저장 방식

Base62는 숫자 ID와 단축 코드 사이의 가역적인 변환임.

따라서 두 가지 데이터 모델을 사용할 수 있음.

17.1 단축 코드를 직접 저장하는 방식

ID | short_code | long_url | created_at

조회 과정:

short_code
→ 데이터베이스 조회
→ long_url 반환

17.2 단축 코드를 숫자 ID로 복원하는 방식

ID | long_url | created_at

조회 과정:

short_code
→ Base62 디코딩
→ numeric ID
→ 데이터베이스 조회
→ long_url 반환

이 방식은 short_code를 별도 컬럼으로 저장하지 않아도 됨.

---

18. ID 생성기

Base62 방식에서는 입력으로 사용할 숫자 ID가 전역적으로 유일해야 함.

선택 가능한 방식:

단일 쓰기 데이터베이스

• auto_increment
• 데이터베이스 sequence

여러 데이터베이스 샤드 또는 데이터센터

• Snowflake
• ID 구간 할당
• 별도의 분산 ID 생성기

현재 요구사항은 평균 초당 약 1,160개의 쓰기 요청임.

사용하는 데이터베이스와 하드웨어가 해당 쓰기 부하를 감당할 수 있다면 단일 데이터베이스의 auto_increment나 sequence로도 구현 가능함.

여러 데이터베이스에서 독립적으로 ID를 발급해야 한다면 Snowflake 등의 분산 ID 생성 방식을 고려해야 함.

---

19. 전체 처리 흐름

19.1 URL 생성

클라이언트
→ 긴 URL 전송
→ 유일 ID 생성
→ Base62 변환
→ DB에 ID와 원래 URL 저장
→ 단축 URL 반환

19.2 URL 리디렉션

클라이언트가 단축 URL 요청
→ 캐시에서 원래 URL 조회
→ 캐시 적중 시 즉시 리디렉션
→ 캐시 미스 시 DB 조회
→ 조회 결과 캐시 저장
→ 301 또는 302 응답 반환

---

20. 정리

데이터 저장

• 모든 URL 매핑 정보를 메모리에 저장하기에는 비용과 용량 한계 존재
• 전체 데이터는 데이터베이스에 영구 저장
• 자주 조회되는 URL은 캐시에 저장

단축 코드 길이

• 사용 가능한 문자는 총 62개
• 약 3,650억 개의 URL을 저장하기 위한 최소 코드 길이는 7자리

해시 후 충돌 해소

• 긴 URL을 해싱하여 단축 코드 생성
• 충돌 발생 시 salt 등을 추가하여 다시 해싱
• 데이터베이스 또는 블룸 필터를 이용해 충돌 확인

블룸 필터

• 데이터베이스를 대체하지 않음
• 확실히 존재하지 않는 코드를 빠르게 판별
• 불필요한 데이터베이스 조회 감소

Base62 변환

• 유일한 숫자 ID를 짧은 문자열로 변환
• 숫자 ID가 유일하면 충돌 없음
• 전역적으로 유일한 ID 생성기가 필요함

최종 설계

• 데이터베이스로 전체 URL 매핑 영구 저장
• Redis 등의 캐시로 읽기 성능 향상
• 유일 ID를 생성한 뒤 Base62로 변환하여 단축 코드 생성
• 단축 코드 요청 시 캐시와 데이터베이스를 통해 원래 URL 조회
• 서비스 목적에 따라 301 또는 302 리디렉션 사용