가상 면접 사례로 배우는 대규모 시스템 설계 기초 8장: URL 단축기 설계

가상 면접 사례로 배우는 대규모 시스템 설계 기초 8장: URL 단축기 설계를 읽고 정리합니다.

 

개략적 설계안

API 엔드포인트

클라이언트는 서버가 제공하는 API 엔드포인트를 통해 서버와 통신합니다. 이 글에선 엔드포인트를 REST 스타일로 설계합니다. URL 단축키는 기본적으로 두 개의 엔드포인트를 필요로 합니다.

1. URL 단축용 엔드포인트: 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 실어서 POST 요청을 보내야 합니다. 이 엔드포인트는 다음과 같은 형태를 띕니다:
   POST /api/v1/data/shorten
   - 인자: {longUrl: longURLstring}
   - 반환: 단축 URL
2. 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 단축기는 시스템의 핵심 컴포넌트이므로, 처리 흐름이 논리적으로 단순해야 하며 기능적으로 언제나 동작하는 상태로 유지되어야 합니다. 

1. 입력으로 긴 URL을 받습니다.
2. 데이터베이스에 해당 URL이 있는지 검사합니다.
3. 데이터베이스에 있다면 해당 URL에 대한 단축 URL을 만든 적이 있는 것입니다. 따라서 데이터베이스에서 해당 단축 URL을 가져와서 클라이언트에게 반환합니다.
4. 데이터베이스에 없는 경우에는 해당 URL은 새로 접수된 것이므로 유일한 ID를 생성합니다. 이 ID는 데이터베이스의 기본 키로 사용합니다.
5. 62진법 변환을 적용하고, 단축 URL을 만듭니다.
6. ID, 단축 URL, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 클라이언트에게 전달합니다.

이 URL 생성기의 주된 용도는 단축 URL을 만들 때 사용할 ID를 만드는 것입니다. 또한 이 ID는 전역적 유일성이 보장되어야 합니다.

 

URL 리디렉션 상세 설계

아래 그림은 리디렉션 메커니즘의 상세한 설계를 나타냅니다. 쓰기보다 읽기를 더 자주 하는 시스템이기 때문에 <단축 URL, 원래 URL>의 쌍을 캐시에 저장하여 성능을 높였습니다.

 

URL 리디렉션 설계 이후 아래의 사항에 대해서도 이야기 할 수 있습니다.

• rate limiter
• 웹 서버의 규모 확장: 웹 서버는 stateless 하므로 자유롭게 확장이 가능합니다.
• 데이터베이스의 규모 확장: 데이터베이스를 다중화하거나 샤딩할 수 있습니다.
• 데이터 분석 솔루션: URL 단축기에 데이터 분석 솔루션을 통합해두어 어떤 링크를 얼마나 많은 사용자가 클릭했는지 추적할 수 있습니다.
• 가용성, 데이터 일관성, 안정성