가상 면접 사례로 배우는 대규모 시스템 설계 기초 8장: URL 단축기 설계
301과 302 중 무엇을 쓸지부터 해시 함수 선택과 충돌 처리까지, 단축기 설계를 정리했습니다.
가상 면접 사례로 배우는 대규모 시스템 설계 기초 8장: URL 단축기 설계를 읽고 정리합니다.
개략적 설계안
API 엔드포인트
클라이언트는 서버가 제공하는 API 엔드포인트를 통해 서버와 통신합니다. 이 글에선 엔드포인트를 REST 스타일로 설계합니다. URL 단축키는 기본적으로 두 개의 엔드포인트를 필요로 합니다.
- URL 단축용 엔드포인트: 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 실어서 POST 요청을 보내야 합니다. 이 엔드포인트는 다음과 같은 형태를 띕니다: POST /api/v1/data/shorten - 인자: {longUrl: longURLstring} - 반환: 단축 URL
- URL 리디렉션용 엔드포인트: 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트입니다. 아래와 같은 형태를 띕니다: GET /api/v1/shortUrl - 반환: HTTP 리디렉션 목적지가 될 원래 URL
URL 리디렉션
단축 URL을 받은 서버는 그 URL을 원래 URL로 바꾸어서 301 응답의 Location 헤더에 넣어서 반환합니다. 여기서 유의할 것은 301 응답과 302 응답의 차이입니다.
- 301 Permanently Moved: URL에 대한 HTTP 요청 처리 책임이 영구적으로 Locaiton 헤더에 반환된 URL로 이전되었다는 것을 의미합니다. 영구적으로 이전되었으므로, 브라우저는 이 응답을 캐시합니다.
- 302 Found: 이 응답은 주어진 URL로의 요청이 ‘일시적으로’ Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답입니다. 따라서 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리디렉션 되어야 합니다.
이 두 방법은 각기 다른 장단점을 가지고 있습니다. 서버 부하를 줄이는 것이 중요하다면 301 Permanently Moved를 사용하는 것이 좋습니다. 왜냐면 첫 번째 요청만 단축 URL 서버로 전송될 것이기 때문입니다.
하지만 트래픽 분석이 중요할 때는 302 Found를 쓰는 쪽이 클릭 발생률이나 발생 위치를 추적하는 데 좀 더 유리할 것입니다.
URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 이용하는 방법입니다. 해시 테이블에 <단축 URL, 원래 URL>의 쌍을 저장한다고 가정하면, URL 리디렉션은 다음과 같이 구현됩니다.
- 원래 URL = hashTable.get(단축 URL)
- 301 또는 302 응답 Location 헤더에 원래 URL을 넣은 후 전송
URL 단축
해시 테이블을 사용해 구현한다면, 해시 함수는 아래의 요구사항을 만족해야 합니다.
- 입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야 합니다.
- 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 합니다.
상세 설계
상세 설계 섹션에서 보다 구체적인 설계를 해봅니다.
데이터 모델
위 계략적 설계 당시엔 해시 테이블에 모든 정보를 두었지만, 이 접근법은 초기 전략으로는 괜찮지만 실제 시스템에 쓰기에는 곤란한데, 메모리는 유한하고 비싸기 때문입니다. 더 나은 방법은 <단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장하는 것입니다. 이 관계형베이스 테이블엔 id(PK), shortURL, longURL 세 개의 칼럼이 존재합니다.
해시 함수
해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰입니다. hashValue는 [0-9, a-z, A-Z]의 문자들로 구성됩니다. 따라서 사용할 수 있는 문자의 개수는 10 + 26 + 26 = 62개입니다. hashValue의 길이 n에 따라서 해시 결과는 62^n이 됩니다.
해시 함수 구현에 쓰이는 방법은 ‘해시 후 충돌 해소’ 방법과 ‘base-62 변환’ 방법이 있습니다.
해시 후 충돌 해소
긴 URL을 줄이려면 원래 URL을 문자열로 줄이는 해시 함수가 필요합니다. 쉬운 방법은 CRC32, MD5, SHA-1과 같이 잘 알려진 해시 함수를 이용하는 것입니다. 하지만 이 해시 함수로 나오는 결과보다 더 짧은 URL로 축약하고 싶다면 어떻게 줄일 수 있을까요?
이 문제를 해결할 첫 번째 방법은 계산된 해시 값에서 처음 n개의 글자만 이용하는 것입니다. 하지만 이렇게 하면 해시 결과가 서로 충돌할 확률이 높아집니다. 충돌이 실제로 발생했을 때는, 충돌이 해소될 때까지 사전에 정한 문자열을 해시값에 덧붙입니다.
이 방법을 쓰면 충돌은 해소할 수 있지만 단축 URL을 생성할 때 한 번 이상 데이터베이스 질의를 해야 하므로 오버헤드가 큽니다. 데이터베이스 대신 블룸 필터를 사용하면 성능을 높일 수 있습니다. 블룸 필터는 어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는, 확률론에 기초한 공간 효율이 좋은 기술이라고 합니다.
base-62 변환
진법 변환(base conversion)은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나입니다. 이 기법은 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용합니다. 62진법을 쓰는 이유는 hashValue에 사용하 수 있는 문자 개수가 62개이기 때문입니다.
| 해시 후 충돌 해소 전략 | base-62 변환 |
|---|---|
| 단축 URL의 길이가 고정됩니다. | 단축 URL의 길이가 가변적이며 ID 값이 커지면 같이 길어집니다. |
| 유일성이 보장되는 ID 생성기가 필요치 않습니다. | 유일성 보장 ID 생성기가 필요합니다. |
| 충돌이 가능해서 해소 전략이 필요합니다. | ID의 유일성이 보장된 후에야 적용 가능한 전략이라 충돌은 아예 불가능합니다. |
| ID로부터 단축 URL을 계산하는 방식이 아니라서 다음에 쓸 수 있는 URL을 알아내는 것이 불가능합니다. | ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알아낼 수 있어서 보안상 문제가 될 소지가 있습니다. |
URL 단축기 상세 설계
URL 단축기는 시스템의 핵심 컴포넌트이므로, 처리 흐름이 논리적으로 단순해야 하며 기능적으로 언제나 동작하는 상태로 유지되어야 합니다.
- 입력으로 긴 URL을 받습니다.
- 데이터베이스에 해당 URL이 있는지 검사합니다.
- 데이터베이스에 있다면 해당 URL에 대한 단축 URL을 만든 적이 있는 것입니다. 따라서 데이터베이스에서 해당 단축 URL을 가져와서 클라이언트에게 반환합니다.
- 데이터베이스에 없는 경우에는 해당 URL은 새로 접수된 것이므로 유일한 ID를 생성합니다. 이 ID는 데이터베이스의 기본 키로 사용합니다.
- 62진법 변환을 적용하고, 단축 URL을 만듭니다.
- ID, 단축 URL, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 클라이언트에게 전달합니다.
이 URL 생성기의 주된 용도는 단축 URL을 만들 때 사용할 ID를 만드는 것입니다. 또한 이 ID는 전역적 유일성이 보장되어야 합니다.
URL 리디렉션 상세 설계
아래 그림은 리디렉션 메커니즘의 상세한 설계를 나타냅니다. 쓰기보다 읽기를 더 자주 하는 시스템이기 때문에 <단축 URL, 원래 URL>의 쌍을 캐시에 저장하여 성능을 높였습니다.
URL 리디렉션 설계 이후 아래의 사항에 대해서도 이야기 할 수 있습니다.
- rate limiter
- 웹 서버의 규모 확장: 웹 서버는 stateless 하므로 자유롭게 확장이 가능합니다.
- 데이터베이스의 규모 확장: 데이터베이스를 다중화하거나 샤딩할 수 있습니다.
- 데이터 분석 솔루션: URL 단축기에 데이터 분석 솔루션을 통합해두어 어떤 링크를 얼마나 많은 사용자가 클릭했는지 추적할 수 있습니다.
- 가용성, 데이터 일관성, 안정성
Topics