안녕하세요! 개발자 정성훈입니다.

URL 단축기는 ‘가상 면접 사례로 배우는 대규모 시스템 설계 기초’ 같은 유명한 책이나 기초적인 시스템 디자인을 학습할 때 자주 접하는 예제입니다. 보통 책이나 블로그에서는 다음과 같은 방식으로 URL 단축 시스템의 핵심 기능을 구현합니다.

  1. 원본 URL을 해시 함수 등을 이용해 짧은 문자열(단축 URL)로 변환합니다.
  2. 생성된 단축 URL이 이미 존재하는지 확인하기 위해 데이터베이스를 조회합니다. (해시 충돌 방지 및 유일성 보장)

이 방식은 직관적이고 이해하기 쉽다는 장점이 있습니다. 하지만 트래픽이 증가하면 필연적으로 데이터베이스 조회 과정에서 병목 현상이 발생하고, 이는 데이터베이스 부하 증가로 이어져 단일 실패 지점(Single Point of Failure)이 될 가능성이 높습니다.

물론 데이터베이스 부하 분산을 위해 샤딩(Sharding)같은 기법을 도입할 수 있지만, 이는 시스템의 복잡도를 높이고 관리 비용을 증가시키는 요인이 됩니다.

결국, 이 방식의 근본적인 한계는 ‘유일성 확인’을 데이터베이스에 의존한다는 점입니다. 만약 데이터베이스 조회 없이도 유일한 단축 URL을 생성할 수 있다면 어떨까요? 데이터베이스 분산이라는 어려운 문제에서 벗어나, URL 단축 서비스 애플리케이션 자체만으로도 수평적 확장이 용이해지지 않을까요?

저는 이러한 고민 끝에, X(구 트위터)의 Snowflake ID 생성 방식에서 영감을 얻고 Base62 인코딩을 활용하여 데이터베이스 조회 없이 수평적 확장이 가능한 URL 단축 시스템을 고안했습니다.

이번 글에서는 제가 고안한 시스템의 설계 과정과 그 과정에서 마주한 한계점, 그리고 배운 점들을 공유하고자 합니다.

Database에 의존하는 URL 단축의 한계

기존 방식의 문제점을 다시 한번 짚어보겠습니다.

  1. 해시 충돌 처리의 복잡성: 해시 함수는 서로 다른 입력에 대해 동일한 출력을 내는 ‘해시 충돌’ 가능성이 항상 존재합니다. 이를 해결하기 위해 충돌 발생 시 원본 URL에 임의의 문자열을 추가하는 등의 추가 로직이후 다시 충돌 검사가 필요하며, 이는 구현 복잡성을 높입니다.
  2. 데이터베이스 병목 현상: 모든 단축 URL 생성 요청은 데이터베이스 조회를 거쳐야 합니다. 트래픽이 몰릴 경우, 데이터베이스 읽기/쓰기 작업이 시스템 전체의 성능을 저하시키는 병목 지점이 됩니다.
  3. 확장성의 어려움: 데이터베이스 부하를 줄이기 위해 Replication(복제), Sharding(샤딩), Partitioning(파티셔닝) 등을 도입해야 합니다. 이는 시스템 아키텍처를 복잡하게 만들고, 데이터 정합성 유지, 관리 포인트 증가 등 새로운 문제들을 야기합니다. 비용 또한 무시할 수 없습니다.

결국, 데이터베이스에 대한 의존성은 URL 단축 서비스의 확장성과 가용성에 큰 제약을 가합니다.

Database로부터의 독립: 새로운 접근법

그렇다면 데이터베이스 조회 없이 어떻게 유일한 단축 URL을 생성하고 수평적 확장을 달성했을까요? 핵심 아이디어는 미리 정의된 규칙에 따라 충돌 가능성 없이 순차적으로 URL을 생성하는 것입니다.

이러한 데이터베이스 의존성 문제를 해결하기 위해, 저는 트위터의 분산 ID 생성 시스템인 Snowflake에서 영감을 얻었습니다. Snowflake의 핵심 아이디어 중 하나는 ID를 생성하는 각 ‘워커(worker)‘에게 고유한 ID를 부여하고(Worker ID), 각 워커 내에서는 시간 흐름에 따른 순차적인 번호(sequence number)를 사용하여 전체적으로 고유하면서도 정렬 가능한 ID를 만들어내는 것입니다. 특히, 각 워커가 독립적으로 ID를 생성하면서도 전체적인 유일성이 보장된다는 점에 주목했습니다.

저는 이 개념을 차용하여, 각 URL 단축 서비스 애플리케이션 인스턴스를 Snowflake의 ‘워커’처럼 취급하기로 했습니다. 제 설계에서 ‘Prefix’는 Snowflake의 ‘워커 ID’와 유사한 역할을 수행하여 각 애플리케이션 인스턴스를 고유하게 식별합니다. 그리고 인스턴스 내부의 AtomicInteger 카운터는 Snowflake의 ‘시퀀스 번호’처럼 작동하여 해당 인스턴스 내에서 순차적이고 고유한 값을 생성합니다. 이 두 가지 요소를 결합함으로써, 각 인스턴스는 중앙 조정이나 데이터베이스 조회 없이도 자신에게 할당된 범위 내에서 충돌 없이 URL을 생성할 수 있게 됩니다.

다음과 같은 구조로 설계했습니다.

  1. 고정 길이 URL: 단축 URL 길이를 7자리로 고정합니다.
  2. 사용 가능 문자: 각 자리에는 0-9, a-z, A-Z (총 62개) 문자만 사용합니다 (Base62).
  3. URL 구조 분리:
    • Prefix (2자리): 개발자가 애플리케이션 배포 시 미리 지정하는 고정된 두 글자입니다.
    • Suffix (5자리): 애플리케이션 내부에서 순차적으로 생성되는 Base62 인코딩된 다섯 글자입니다.

이 구조를 통해 7자리 URL은 총 62^7 (약 3조 5천억 개)의 조합을 가질 수 있습니다.

Prefix가 왜 필요한가

Prefix를 도입한 가장 중요한 이유는 분산 시스템 환경에서의 손쉬운 수평 확장을 위해서입니다. 각 URL 단축 서비스 애플리케이션 인스턴스마다 고유한 Prefix를 할당합니다.

  • 예시:
    • 애플리케이션 인스턴스 1: Prefix AA 할당 -> AA + 5자리 Suffix 생성 담당
    • 애플리케이션 인스턴스 2: Prefix AB 할당 -> AB + 5자리 Suffix 생성 담당
    • 애플리케이션 인스턴스 3: Prefix AC 할당 -> AC + 5자리 Suffix 생성 담당
    • …

이렇게 하면 각 인스턴스는 자신에게 할당된 Prefix 내에서만 URL을 생성하므로, 다른 인스턴스와의 충돌 가능성이 원천적으로 차단됩니다. 각 인스턴스는 62^5 (약 9억 1천6백만 개)의 단축 URL을 생성할 수 있는 능력이 있습니다.

트래픽 증가 시, 새로운 Prefix를 할당받은 인스턴스를 추가하기만 하면 되므로 매우 간단하게 수평 확장이 가능합니다.

나머지 5자리 Suffix를 생성하는 방법 - AtomicInteger와 Base62

 인스턴스 내부에서는 어떻게 5자리 Suffix를 중복 없이 생성할까요?

  1. 순차적 카운터: Java의 AtomicInteger 클래스를 사용합니다. AtomicInteger는 멀티스레드 환경에서도 원자적인 연산(increment 등)을 보장하여 동시성 문제없이 안전하게 숫자를 증가시킬 수 있습니다. 각 인스턴스는 0부터 시작하는 고유한 카운터를 가집니다.
  2. Base62 인코딩: AtomicInteger로부터 얻은 순차적인 숫자를 Base62 방식으로 인코딩합니다.
    • 사용 문자: 
      • 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
    • 인코딩 방식: 숫자를 62로 나누고 나머지에 해당하는 문자를 할당하는 과정을 반복합니다.(진수 변환 방식)
  3. 고정 길이 유지 (Padding): Base62 인코딩 결과가 5자리보다 짧을 경우, 앞쪽에 ‘0’을 채워(padding) 항상 5자리 길이를 유지합니다. 예를 들어, 숫자 1을 인코딩하면 ‘1’이 되지만, 패딩을 적용하여 ‘00001’로 만듭니다.
  4. 생성 한계 설정: 5자리 Base62로 표현 가능한 최대 숫자는 62^5 - 1 (즉, 916,132,831) 입니다. AtomicInteger 카운터 값이 이 한계(LIMIT)에 도달하면, 해당 인스턴스는 더 이상 URL을 생성할 수 없으므로 예외(OverLimitException)를 발생시킵니다.

구현 코드

핵심: 이 설계에서 데이터베이스(PersistenceClient)는 생성된 shortUrl과 originalUrl의 매핑 정보를 저장하는 역할만 합니다. 단축 URL 생성 시 유일성 검증을 위한 조회(read) 작업이 전혀 필요 없어 조회로 인한 데이터베이스 병목 현상을 해결합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

@Component  
public class ShortUrlGenerator {  
    private static final char[] BASE62_CHARS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();  
    private static final int TARGET_ENCODED_LENGTH = 5;  
  
    @Value("${shorturl.prefix}")  
    private String PREFIX;  
  
    /**  
     * Short URL을 생성합니다.  
     *     * @param number 인코딩할 숫자  
     * @return PREFIX(2자) + 인코딩결과(5자), PREFIX는 개발자가 환경 변수로 설정합니다.  
     */    public String generateShortUrl(int number) {  
        return PREFIX + encodeToBase62(number);  
    }  
  
    /**  
     * 숫자를 지정된 길이의 Base62 문자열로 인코딩합니다. 길이는 5  
     * 길이가 부족하면 앞쪽에 '0'으로 패딩합니다.  
     *     * @param number 인코딩할 숫자  
     * @return 패딩된 Base62 문자열 (5자리)  
     */    private String encodeToBase62(int number) {  
        StringBuilder sb = new StringBuilder();  
  
        while (number > 0) {  
            sb.append(BASE62_CHARS[number % BASE62_CHARS.length]);  
            number /= BASE62_CHARS.length;  
        }  
  
        while (sb.length() < TARGET_ENCODED_LENGTH) {  
            sb.append("0");  
        }  
  
        return sb.reverse().toString();  
    }  
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

@Service  
@RequiredArgsConstructor  
public class ShortenService {  
    private final ShortUrlGenerator shortUrlGenerator;  
    private final PersistenceClient persistenceClient;  
    private final AtomicInteger counter;  
  
    private static final int LIMIT = 916_132_831;  
  
    public ShortenResponse createShortUrl(ShortenRequest shortenRequest) {  
        int currentCount = counter.getAndIncrement();  
  
        if (currentCount >= LIMIT) throw new OverLimitException();  
  
        String shortUrl = shortUrlGenerator.generateShortUrl(currentCount);  
  
        persistenceClient.save(new UrlSaveRequest(shortenRequest.originalUrl(), shortUrl));  
  
        return new ShortenResponse(shortUrl);  
    }  
}

마주한 한계와 개선방법

이 설계는 데이터베이스 의존성을 제거하여 URL 생성 로직의 수평 확장을 용이하게 하지만, 몇 가지 한계점과 고려해야 할 사항들이 있습니다.

한계 1: 인스턴스별 생성 개수 제한과 관리의 번거로움

  • 문제점: 각 애플리케이션 인스턴스(Prefix)는 62^5 (약 9억 개)라는 명확한 생성 한계를 가집니다. 특정 Prefix를 사용하는 인스턴스가 이 한계에 도달하면 더 이상 URL을 생성할 수 없습니다.
  • 운영 및 관리:
    • 모니터링: 각 Prefix별 사용량을 지속적으로 추적해야 합니다.
    • OverLimitException 예외 알림 구축: 한계에 도달하여 OverLimitException이 발생시 Slack 알림 같은 시스템을 구축할 필요가 있습니다.
    • 사전 확장: 특정 Prefix의 사용량이 한계에 가까워지기 전에, 새로운 Prefix를 할당받은 신규 인스턴스를 미리 준비하고 트래픽을 분산시켜야 합니다.
    • 자동화 필요성: 이러한 Prefix 할당, 인스턴스 배포, 사용량 모니터링 과정이 수동으로 이루어진다면 운영 부담이 상당히 커질 수 있습니다. 따라서 Prefix를 동적으로 할당하고 관리하는 자동화된 시스템(쿠버네티스 같은?) 구축을 장기적으로 고려해야 합니다.

한계 2: 예기치 못한 서버 다운 시 상태 유실 문제

  • 문제점: AtomicInteger 카운터는 메모리 내(in-memory) 상태입니다. 만약 URL 단축 서비스를 실행 중인 서버가 예기치 않게 다운되거나 재시작되면, 현재까지 증가했던 카운터 값이 유실되고 기본값(예: 0)부터 다시 시작될 수 있습니다.
  • 결과: 동일한 Prefix를 가진 애플리케이션이 재시작 후 0부터 카운터를 시작하면, 이전에 이미 생성했던 Suffix를 다시 생성하게 됩니다. 이는 동일한 단축 URL이 서로 다른 원본 URL을 가리키게 되는 문제를 초래합니다.

개선 방안 1: 마지막 생성된 URL 디코딩을 통한 카운터 추정

  • 동작 방식:
    1. 조회: 인스턴스 시작 시, 자신의 Prefix(예: AA)를 가지는 단축 URL 중 가장 마지막에 저장된 (예: 생성 시간 기준 또는 Suffix 값 기준 정렬) 레코드를 PersistenceClient를 통해 조회합니다. (예: AAzzzzz 와 같은 URL)
    2. 디코딩: 조회된 단축 URL(AA1234z)의 Suffix(1234z)를 Base62 디코딩하여 숫자(예: 916132830)를 얻습니다.
    3. 초기화: (얻어진 숫자 값+1)으로 AtomicInteger를 초기화하고, 다음 요청 시 그 다음 값부터 시작합니다.

PersistenceClient: Original URL 과 Short(단축) URL 매핑 정보가 영속화된 데이터베이스 접근 위한 클라이언트

개선 방안 2: 카운터 상태의 영속화 (Persistence)

  • 방법
    • 분산 키-값 저장소(Redis): 각 Prefix별 현재 카운터 값을 중앙 집중화된 저장소에 기록합니다. 인스턴스 시작 시 해당 Prefix의 마지막 카운터 값을 읽어옵니다. 이 방식은 비교적 안정적이고 여러 인스턴스 간 상태 공유가 용이합니다.
    • 데이터베이스: 카운터 상태만을 위한 간단한 테이블을 사용할 수도 있습니다. (원래 피하려던 DB 의존성이 일부 생기지만, 유일성 검증 조회가 아닌 상태 저장용이므로 부하는 훨씬 적음!)

카운터 상태 영속화를 도입하면 완전한 Database 비의존은 아니게 됩니다. 하지만 이는 URL 생성 시 유일성 검증을 위한 DB 조회를 피하는 원래 목표는 달성하면서, 시스템의 안정성과 데이터 정합성을 확보하기 위한 방법 중 하나가 될 수 있습니다.

  • 한계: 만약 카운터 값이 증가한 후 분산 저장소에 저장되기 전에 인스턴스가 종료된다면 분산 저장소에 저장된 카운터 값은 못 믿습니다.
  • 개선: 인스턴스 시작 시 초기화된 카운터로 임시 URL을 만들고 이를 데이터베이스에 중복되는지 확인하는 과정을 추가하면 해결 됩니다.

분산 저장소 하나더 추가했을 뿐인데도 복장성이 꽤 증가합니다;

개발 과정에서 느낀 점

얕은 지식들의 연결과 시너지

단순히 ‘데이터베이스 없이 해보자’는 생각에서 출발했지만, 이를 구체화하는 과정에서 다양한 기본 지식들이 필요했습니다. 분산 시스템의 ID 생성 전략(Snowflake), 데이터 인코딩 방식(Base62), 동시성 제어를 위한 Java API(AtomicInteger), 그리고 상태 관리의 중요성 등 개별적으로 알고 있던 개념들을 하나의 목표를 위해 연결하고 조합했을 때 비로소 작동하는 시스템을 만들 수 있었습니다.

깊이 있는 지식도 중요하지만, 때로는 기본적인 개념들을 창의적으로 연결하는 능력이 문제 해결의 실마리가 될 수 있다는 것을 느꼈습니다.

직접 만들어보는 경험의 가치

책이나 블로그에서 시스템 디자인 패턴을 배우는 것과 직접 코드로 구현하고 부딪혀보는 것은 완전히 다른 경험이었습니다. 특히 ‘상태 유실’과 같은 이론적으로 알고 있던 문제점을 실제 설계의 한계점으로 명확히 인지하고, 이를 해결하기 위한 구체적인 방안(카운터 영속화)을 고민하는 과정에서 훨씬 깊이 있는 학습이 이루어졌습니다.

결론

URL 단축 시스템의 데이터베이스 의존성 문제를 해결하기 위해, Prefix와 메모리 내 Atomic Counter, 그리고 Base62 인코딩을 결합하여 데이터베이스 조회 없이 수평 확장이 가능한 URL 생성 방식을 고안했습니다. 이 방식은 URL 생성 단계에서의 데이터베이스 병목 현상을 효과적으로 제거하고, 애플리케이션 인스턴스 추가만으로 간단하게 시스템 전체 처리량을 늘릴 수 있다는 명확한 장점을 가집니다.

하지만 인스턴스별 생성 개수 제한과 메모리 내 카운터의 상태 유실 가능성이라는 중요한 한계점도 존재합니다. 특히 안정적인 운영을 위해서는 카운터 상태를 영속화하고 복구하는 메커니즘을 추가로 고려해야 하며, 이는 시스템의 복잡성과 의존성을 일부 증가시키는 트레이드오프를 수반합니다.

이 경험을 통해 기존 방식의 문제점을 분석하고, 대안적인 설계를 시도하며 그 과정에서 발생하는 새로운 문제들을 해결해나가는 경험을 할 수 있었습니다. 완벽한 시스템은 없으며, 특정 문제를 해결하기 위해 어떤 장점을 취하고 어떤 단점을 감수할지(Trade-off) 결정하는 것이 정말 내공이 필요한 일인것을 깨닫게 되었습니다.