8. Designing a URL Shortener

URL 단축기 설계

1단계: 문제 이해 및 설계 범위 확정개략적 추정

URL 단축기는 긴 URL을 짧은 URL로 변환하여 사용자가 더 쉽게 공유할 수 있도록 해주는 서비스이다. 이 서비스의 핵심 기능은 다음과 같다:

  1. URL 단축: 긴 URL을 받아서 짧은 URL로 변환한다.

  2. URL 리디렉션: 사용자가 짧은 URL을 요청하면, 원래의 긴 URL로 리디렉션한다.

  3. 고유성 보장: 동일한 URL에 대해 동일한 단축 URL을 반환하거나, 요청에 따라 새 단축 URL을 생성할 수 있어야 한다.

  4. 확장성: 서비스는 대규모 트래픽과 많은 수의 URL을 처리할 수 있어야 한다.

URL 단축기 시스템 설계를 시작하기 전에, 예상 트래픽, 데이터 저장 용량, 성능 요구사항 등을 고려해야 한다. 이는 설계 범위를 확정하고, 서비스의 최종 목표를 명확히 하는 데 중요한 역할을 한다.

예상 트래픽 및 데이터 규모

URL 단축기는 일반적으로 수억 개 이상의 URL을 관리할 수 있어야 한다. 예를 들어, 하루에 1억 개의 URL 단축 요청이 발생하고, 각각의 URL이 데이터베이스에 저장된다고 가정하자. 매일 새로운 URL이 추가되기 때문에, 연간 약 365억 개의 URL을 관리해야 한다. 이 숫자는 서비스의 사용량에 따라 더 증가할 수 있다.

성능 요구사항

사용자는 URL 단축 서비스가 신속하게 동작하기를 기대한다. 즉, 긴 URL을 짧은 URL로 변환하는 과정과 짧은 URL을 원래 URL로 리디렉션하는 과정이 매우 빠르게 이루어져야 한다. 이상적으로는, 요청당 지연 시간이 몇 밀리초 이내여야 한다.

2단계: 개략적 설계안 제시 및 동의 구하기

URL 단축기 시스템을 설계할 때, 다양한 방법을 고려해야 한다. 여기서는 API 엔드포인트, URL 리디렉션, URL 단축의 세 가지 주요 요소를 중심으로 개략적인 설계안을 제시한다.

2.1 API 엔드포인트

URL 단축기 서비스는 외부 시스템이나 사용자와의 통신을 위해 API 엔드포인트를 제공해야 한다. 주요 API 엔드포인트는 다음과 같다:

  • POST /shorten: 긴 URL을 받아서 짧은 URL을 생성한다. 요청 본문에는 단축하고자 하는 원본 URL이 포함되어야 한다. 서버는 이 요청을 처리하여 고유한 단축 URL을 반환한다.

  • GET /{shortURL}: 짧은 URL을 받아서 원본 URL로 리디렉션한다. 사용자가 브라우저에서 짧은 URL을 요청하면, 이 엔드포인트는 원본 URL을 찾아서 해당 URL로 리디렉션한다.

  • GET /stats/{shortURL} (선택 사항): 특정 짧은 URL에 대한 통계 정보를 제공한다. 예를 들어, 해당 URL이 몇 번이나 사용되었는지, 마지막으로 사용된 시간이 언제인지 등을 조회할 수 있다.

2.2 URL 리디렉션

URL 리디렉션은 URL 단축기 서비스의 핵심 기능 중 하나이다. 사용자가 단축된 URL을 요청하면, 서비스는 해당 URL을 원본 URL로 변환하여 사용자를 리디렉션해야 한다. 이 과정은 매우 빠르게 이루어져야 하며, 데이터베이스 조회나 캐싱 메커니즘을 활용하여 성능을 최적화할 수 있다.

  • 데이터베이스 조회: 짧은 URL을 데이터베이스에서 조회하여 원본 URL을 찾는다.

  • 캐싱: 자주 조회되는 URL을 캐싱하여 데이터베이스 조회를 줄인다.

  • 리디렉션 응답: 원본 URL을 찾으면, HTTP 302 상태 코드와 함께 원본 URL로 리디렉션한다.

301 vs 302

  • 301 Permanently Moved

이 응답은 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답이다. 이 뜻은 브라우저가 응답을 캐시하여 다시 방문할시에 저장된 URL로 요청을 보내게 된다.

  • 302 Found

이 응답은 주어진 URL로의 요청이 일시적으로 Location 헤더에 반환된 URL로 처리되어야한다는 음답이다. 따라서 항상 단축 URL 서버에 요청이 보내진다.

301을 사용하게 되면 응답시간이 빨라진다. 통계 수집이 어렵다. 반대로 302는 응답시간이 느려지지만, 통계 수집이 가능하다.

2.3 URL 단축

긴 URL을 짧은 URL로 변환하는 과정은 주로 해시 함수를 사용하여 이루어진다. URL 단축 알고리즘은 주어진 긴 URL을 일정한 길이의 해시 값으로 변환하고, 이 값을 짧은 URL로 사용한다.

  • 고유성 보장: 해시 충돌을 방지하기 위해, 이미 사용 중인 해시 값이 생성될 경우 추가적인 조치를 취해야 한다.

  • URL의 길이: 생성된 짧은 URL의 길이는 사용성과 고유성 사이의 균형을 유지해야 한다. 너무 짧은 URL은 충돌 가능성을 높이고, 너무 긴 URL은 사용 편의성을 떨어뜨릴 수 있다.

  • 해시 함수의 선택: MD5, SHA-1 등 강력한 해시 함수가 일반적으로 사용되지만, 필요에 따라 커스텀 해시 함수를 설계할 수도 있다.

3단계: 상세 설계

이제, 위에서 제시한 개략적 설계안을 바탕으로 URL 단축기 시스템의 상세 설계를 진행한다. 상세 설계에서는 데이터 모델, 해시 함수, URL 단축기 및 URL 리디렉션의 구체적인 구현 방법을 다룬다.

3.1 데이터 모델

URL 단축기 시스템의 핵심 데이터는 단축된 URL과 원본 URL 간의 매핑 정보이다. 이 매핑 정보를 저장하기 위한 데이터 모델은 다음과 같다:

  • URL Mapping Table:

    • Short URL: 짧은 URL 문자열을 저장한다. 기본 키로 설정하여 고유성을 보장한다.

    • Original URL: 원본 URL을 저장한다.

    • Creation Date: URL이 생성된 날짜와 시간을 기록한다.

    • Access Count: 해당 짧은 URL이 몇 번 조회되었는지를 기록한다.

    • Last Accessed: 마지막으로 접근된 시간을 기록하여, 자주 사용되지 않는 URL을 정리하는 데 활용할 수 있다.

이 테이블은 기본적으로 관계형 데이터베이스에서 관리되지만, 대규모 시스템에서는 NoSQL 데이터베이스나 분산 데이터베이스를 사용할 수도 있다. 선택한 데이터베이스에 따라 데이터의 분산 저장, 샤딩(Sharding) 등의 방법을 사용하여 성능을 최적화할 수 있다.

3.2 해시 함수

URL을 해시로 변환하는 과정은 URL 단축기의 핵심 알고리즘이다. 해시 함수는 긴 문자열(원본 URL)을 고정된 길이의 문자열(해시 값)로 변환하며, 이 값이 곧 단축된 URL로 사용된다.

3.2.1 해시 값 길이

해시 값의 길이는 충돌 가능성을 최소화하면서도, 짧은 URL을 유지할 수 있도록 적절히 설정해야 한다. 예를 들어, 6자리의 해시 값을 사용할 경우, 최대 62^6 = 약 56억 개의 고유 URL을 생성할 수 있다(base-62 인코딩 사용 시).

해시 값의 길이를 정하기 위해ㅐ서는 62^n >= 3650억(10년치) n의 최소값을 찾아야한다. 개략적으로 계산해보면 n=7 일때 3.5조 개의 URL을 만들 수 있다.

  • 장점: 비교적 짧은 URL을 생성할 수 있어 사용자가 쉽게 기억할 수 있다.

  • 단점: URL 개수가 많아지면 충돌 가능성이 증가할 수 있다.

3.2.2 해시 후 충돌 해소

해시 충돌은 두 개의 다른 URL이 동일한 해시 값을 가질 때 발생한다. 이를 해결하기 위해, 충돌 발생 시 재해시(rehashing)를 하거나, 충돌 발생 시 해시 값에 추가 정보를 덧붙이는 등의 방법을 사용할 수 있다.

  • 재해시(Rehashing): 충돌이 발생할 경우, 다른 해시 함수나 해시 알고리즘을 사용하여 새로운 해시 값을 생성한다.

  • 추가 정보 덧붙이기: 원본 URL에 특정한 접미사나 접두사를 추가한 후 해시 함수를 다시 적용하여 충돌을 피한다.

해당 방법을 사용하게 되면 DB와 통신을 해야하므로 오버해드가 크다. 블룸 필터를 사용하면 성능을 높일 수 있다.

블룸 필터

블룸 필터(Bloom Filter)는 컴퓨터 과학에서 주로 사용되는 확률적 데이터 구조로, 집합에 원소가 포함되어 있는지를 빠르게 확인할 수 있도록 설계되었습니다. 이 필터는 공간 효율성이 뛰어나지만, 특정 조건에서 **거짓 긍정(False Positive)**이 발생할 수 있다는 특징을 가지고 있습니다.

블룸 필터는 비트 배열과 여러 해시 함수로 구성됩니다. 이 데이터 구조는 특정 요소가 집합에 포함되어 있지 않은지를 빠르게 결정할 수 있습니다. 하지만 요소가 포함된 것처럼 보이는 경우가 있을 수 있으며, 이 때 거짓 긍정이 발생합니다. 거짓 긍정이란 요소가 집합에 실제로는 포함되지 않았지만 포함되어 있는 것처럼 잘못 판단하는 경우를 의미합니다. 반면, **거짓 부정(False Negative)**는 발생하지 않습니다. 즉, 블룸 필터는 요소가 집합에 포함되지 않은 경우에만 100% 정확한 답을 제공합니다.

블룸 필터의 구조

블룸 필터는 두 가지 주요 요소로 구성됩니다:

  1. 비트 배열 (Bit Array): 초기화된 고정 길이의 비트 배열로, 모든 비트가 0으로 설정됩니다.

  2. 해시 함수 (Hash Functions): 여러 개의 독립적인 해시 함수가 필요합니다. 각 해시 함수는 입력 값을 받아 비트 배열의 인덱스를 반환합니다.

블룸 필터의 작동 방식

  1. 요소 추가(Addition):

    • 요소를 집합에 추가할 때, 각 해시 함수에 해당 요소를 입력하여 비트 배열에서 인덱스를 얻습니다.

    • 그 인덱스에 해당하는 비트 배열의 비트를 1로 설정합니다.

    • 여러 해시 함수가 있으므로, 하나의 요소는 비트 배열의 여러 위치에 영향을 줍니다.

  2. 포함 여부 검사(Membership Check):

    • 특정 요소가 집합에 포함되어 있는지 확인할 때, 해당 요소를 각 해시 함수에 입력하여 인덱스를 얻습니다.

    • 각 인덱스 위치의 비트가 모두 1로 설정되어 있으면, 해당 요소가 집합에 있을 가능성이 높습니다(하지만 확실하지는 않습니다).

    • 하나라도 0이 있으면, 해당 요소는 집합에 포함되지 않았음이 확실합니다.

블룸 필터의 장단점

장점:

  • 공간 효율성: 블룸 필터는 집합의 크기에 비해 매우 적은 메모리로 동작합니다. 이는 대규모 데이터를 처리할 때 특히 유용합니다.

  • 빠른 연산: 블룸 필터는 해시 함수 연산만 필요하기 때문에 매우 빠릅니다. 검색과 추가 연산이 모두 O(k) 시간복잡도를 가지며, 여기서 k는 해시 함수의 개수입니다.

단점:

  • 거짓 긍정: 블룸 필터는 거짓 긍정 가능성이 있으며, 이는 필터가 꽉 차거나 충돌이 많이 발생할 경우 더 증가할 수 있습니다.

  • 거짓 부정이 없음: 블룸 필터는 거짓 부정이 없는 대신, 거짓 긍정을 허용합니다. 즉, 포함되지 않은 원소가 포함되었다고 잘못 판단할 수 있습니다.

  • 원소 삭제 불가: 블룸 필터는 원소를 추가하는 연산만 지원하며, 삭제는 불가능합니다. 이를 해결하기 위해 **카운팅 블룸 필터(Counting Bloom Filter)**가 사용될 수 있습니다.

블룸 필터의 활용 사례

블룸 필터는 메모리 효율적이고 빠른 검색을 요구하는 다양한 분야에서 활용됩니다:

  • 캐시 시스템: 웹 캐시에서 블룸 필터를 사용하여 데이터가 캐시에 있는지 빠르게 확인합니다.

  • 네트워크: 네트워크 트래픽 필터링, 스팸 필터링 등에 사용됩니다.

  • 데이터베이스: 대규모 데이터베이스에서 존재하지 않는 데이터를 빠르게 거르기 위해 사용됩니다.

  • 분산 시스템: 분산 해시 테이블(DHT)에서 노드 간의 중복을 제거하고, 검색 효율성을 높이는 데 사용됩니다.

3.2.3 base-64 변환

생성된 해시 값을 사용하기 전에, URL로 사용 가능한 형태로 변환해야 한다. Base-64 인코딩은 62개의 알파벳과 숫자, 그리고 두 개의 특수 문자를 사용하여 데이터를 인코딩하는 방법이다. 이 방법을 사용하면, 해시 값을 짧고 간결한 형태로 표현할 수 있다.

7장에유일 ID를 생성 후, 해당 ID를 통해서 62진수로 변환한다.

  • 장점: URL의 길이가 줄어들고, 사용자가 쉽게 기억할 수 있는 형태로 변환된다.

  • 단점: 특수 문자가 포함될 수 있으므로, 특정 환경에서는 URL 인코딩을 추가로 적용해야 할 수 있다.

3.2.4 두 접근법 비교

재해시와 추가 정보 덧붙이기는 각기 다른 상황에서 적합할 수 있다. 재해시는 비교적 간단하게 구현할 수 있으며, 충돌 발생 확률이 낮을 경우 유리하다. 반면, 추가 정보 덧붙이기는 충돌 해결 과정에서 약간의 복잡성을 더하지만, 재해시 없이도 충돌을 해소할 수 있는 장점이 있다.

3.3 URL 단축기 상세 설계

URL 단축기의 상세 설계는 다음과 같은 절차로 이루어진다:

  1. URL 입력: 사용자가 단축하고자 하는 긴 URL을 입력하면, 시스템은 해당 URL을 해시 함수에 전달한다.

  2. 해시 생성: 해시 함수는 긴 URL을 고정된 길이의 해시 값으로 변환한다.

  3. 중복 검사: 생성된 해시 값이 이미 존재하는지 데이터베이스에서 확인한다.

    • 존재하지 않을 경우, 이 해시 값을 사용하여 단축된 URL을 생성한다.

    • 존재할 경우, 재해시를 통해 새로운 해시 값을 생성하거나, 충돌을 해결하는 추가적인 방법을 적용한다.

  4. URL 저장: 최종적으로 생성된 단축 URL과 원본 URL의 매핑 정보를 데이터베이스에 저장한다.

  5. 단축 URL 반환: 단축된 URL을 사용자에게 반환한다.

이 설계는 URL 생성 과정에서의 고유성과 충돌 해결을 보장하며, 대규모 데이터 처리에 적합한 구조를 갖추고 있다.

3.4 URL 리디렉션 상세 설계

URL 리디렉션은 단축된 URL을 원본 URL로 변환하여 사용자를 리디렉션하는 과정이다. 이 과정은 다음과 같은 절차로 이루어진다:

  1. 단축 URL 입력: 사용자가 단축된 URL을 요청하면, 서버는 이 요청을 수신한다.

  2. 캐시 / 데이터베이스 조회: 서버는 데이터베이스에서 단축된 URL에 해당하는 원본 URL을 조회한다.

  3. 리디렉션: 원본 URL을 찾으면, HTTP 302 상태 코드와 함께 사용자를 해당 URL로 리디렉션한다.

  4. 통계 업데이트 (선택 사항): 리디렉션이 성공하면, 해당 URL의 조회 횟수를 증가시키거나, 마지막 접근 시간을 갱신하는 등 통계 정보를 업데이트한다.

이 과정에서 성능 최적화를 위해 자주 사용되는 URL은 캐시 메모리에 저장할 수 있으며, 분산 시스템에서는 데이터베이스의 부하를 줄이기 위해 샤딩이나 파티셔닝 기법을 사용할 수 있다.

4단계: 마무리

URL 단축기 설계는 간단해 보이지만, 고유성, 성능, 확장성 등의 다양한 요소를 고려해야 하는 복잡한 작업이다. 적절한 해시 함수의 선택, 충돌 처리, 데이터 모델링 등을 통해 고성능의 URL 단축 서비스를 구현할 수 있다. 또한, 서비스의 확장성과 유지 보수성을 높이기 위해 API 설계와 캐싱 메커니즘, 데이터베이스 설계를 종합적으로 고려해야 한다. 최종적으로, URL 단축기는 단순히 URL을 짧게 만드는 것을 넘어, 대규모 트래픽을 처리할 수 있는 견고한 시스템으로 발전시킬 수 있다.

Previous7. Designing a Unique ID Generator for Distributed SystemsNext9. Designing a Web Crawler

Last updated