URL 단축기 시스템 디자인

서론
요구사항
개략적 추정
API 엔드포인트 설계
상세 설계
장애 상황
- Cache 서버 장애 및 핸들링
- Database 서버 장애 및 핸들링
추가 요구 사항
- 특정 URL로의 요청 증가
- Shorten URL 만료 + 물리적 삭제
참고

서론

긴 URL을 짧은 URL로 변환하여 리디렉션해주는 서비스을 설계하는 글을 작성해보려고 한다.

해당 주제는 가상 면접 사례로 배우는 대규모 시스템 설계 기초를 참고하였다.

글 후반부에는 요구 사항을 추가하여 설계된 서비스를 고도화 해보려고 한다.

요구사항

요구사항은 아래와 같다.

매일 1억개의 Shorten URL 생성할 수 있어야 함
- 숫자(0~9), 영문자(a~z, A~Z)로 구성되어야 함
- Shorten URL은 짧으면 짧을수록 좋음
Shorten URL은 삭제하거나 업데이트할 수 없음
생성된 URL로 접속하면 원래 URL로 리다이렉트 되어야 함
높은 가용성(A), 장애 감내(P)를 보장해야함
Scalable 해야함

개략적 추정

매일 1억개의 Shorten URL을 생성할 수 있어야하고, 서비스를 10년간 운영한다고 가정해보자.

쓰기 연산과 읽기 연산의 비율은 10:1로 가정한다.

이를 통해 아래와 같이 연산 속도와 저장 용량을 추정할 수 있다.

초당 쓰기 연산: 1억 / (24 * 3600) = 1157
초당 읽기 연산: 1157 * 10 = 11570
최소 저장 용량: 3650억 * 100bytes = 36.5TB
- 생성된 URL 개수: 1억 * 365 * 10 = 3650억 개
- 축약 전 URL 길이: 100bytes
네트워크 대역폭:
- Input: 1157 * 100bytes = 115.7KB/s
- Output: 11570 * 100bytes = 1.157MB/s

API 엔드포인트 설계

URL 단축용 엔드포인트: POST /api/v1/shorten
- 요청 바디: { "url": "https://en.wikipedia.org/wiki/system_design" }
URL 리디렉션 엔드포인트: GET /api/v1/{shortenUrl}
- 원래의 URL로 302 응답 코드로 반환

상세 설계

데이터 모델링

데이터베이스에 저장할 데이터는 아래와 같다.

Shorten URL(Unique Key)
Original URL

데이터베이스 선택

10년간 서비스를 저장하기 위해서 필요한 최소 저장 용량은 36.5TB이다. 이 많은 데이터를 휘발성 메모리에 저장할 수 없기 때문에 영속성을 제공하는 데이터베이스에 저장해야 한다.

이는 하나의 서버로는 저장할 수 없는 양이다. 초반에는 RDB, NoSQL 모두 읽기 성능이 크게 차이가 없겠지만 데이터가 쌓였을 때 샤딩이 필요할 것이다. 샤딩이 아니더라도 트래픽을 분산하기 위해서 트래픽을 받는 서버가 여러대가 필요하다. 마스터-슬레이브로 동작하게 한다고 하면, 마스터 서버가 장애가 나면 승격 과정이 필요한데 이 과정에서 다운 타임이 발생한다. 또한 데이터를 동기화하는 방식도 고려를 해야한다. 비동기, 반동기 방식을 고려해야 하는데, 이 과정 또한 데이터 정합이 깨질 수도 있다.

여러 가지 관점에서 샤딩을 하는 것이 더 나을 것 같다. 데이터 모델을 보면 정규화를 할 필요가 없기 때문에 조인이 필요로 하지 않는다. 하지만, 재샤딩을 해야한다는 점, 핫스팟이 발생할 수 있다는 점이 단점이 될 수 있다. 재샤딩 전략, 핫스팟 대응 전략을 세워야 하는데 이것에 대해서 글을 한 번 작성해봐야겠다.

쓰기 연산보다 읽기 연산이 월등하게 많다는 점, HA와 FT를 보장해야 한다는 점, Scalable 해야 한다는 점, 샤딩 작업이 필요하다는 점을 고려하여 NoSQL 데이터베이스를 선택하기로 결정했다.

쓰기 전략

URL을 단축하는 방법이 서비스의 핵심이다.

URL을 짧은 URL로 단축 알고리즘에 대해서 생각을 해봐야한다.

해시함수(ex: CRC32, MD5, SHA-1) 또는 변환/압축 알고리즘(ex: Base64, LZW, Huffman)을 사용하여 shortURL을 생성할 수 있다.

해시와 압축 알고리즘을 비교해보면

해시 함수	변환/압축
단축 URL의 길이를 고정시킬 수 있다	단축 URL의 길이가 가변적이다. 원래 URL이 길어지면 같이 길어진다
유일성을 보장하는 ID 생성기가 필요치 않음	유일성 보장 ID 로직이 필요하다
충돌 처리가 필요하다	유일성이 보장되므로 충돌 처리가 필요하지 않다
다음 shortURL을 유추할 수 없다	다음 shortURL을 유추할 수 있다

초당 1157개의 쓰기 연산을 처리해야 하는데, 해시함수를 사용할 경우 충돌이 발생할 가능성이 있다. 해시 함수의 경우 유니크를 보장하기 위해서 DB에 쿼리를 날려야 하고 이 과정이 DB에 부하가 발생할 수 있고, 충돌 발생 시 핸들링하는 전략을 세워야하고, 응답 시간을 늦어질 수 있다. 따라서 변환 알고리즘을 사용하는 것이 적합하다.

유일성을 보장하는 ID를 생성하는 ID 생성기를 사용하고, 생성된 ID를 변환 알고리즘을 사용하여 단축 URL을 생성한다. 이렇게 함으로써, DB에 부하를 줄일 수 있고 응답 시간을 빠르게 할 수 있다.

쓰기 연산에 대한 시퀀스를 그려보면 아래와 같다.

Screenshot 2024-01-08 at 13 24 27

ID 생성 로직

ID 생성기에서 유일성이 보장된 ID를 생성해줘야한다. ID 생성기에서 가장 중요한 것은 Scalable ,유일성 보장, DB 독립적, 빠르게 생성해줘야 한다는 것이다. ID를 생성해주는 서버는 따로 두지 않는다. 만약 ID Generator 서비스를 따로 두게 된다면, ID Generator 서비스에 장애가 발생하면 쓰기 연산이 중단될 수 있다. 이러한 이유로 ID 생성기는 서비스 내부에 두고, 간단하고 생성할 수 있는 ID 로직을 짜야된다.

UUID
Snowflake

위 두가지 방법으로 ID를 생성할 수 있는데, UUID는 128bit의 길이를 가지고 있고, Snowflake는 64bit의 길이를 가지고 있다. 길이에 따라 shortURL의 길어지기 때문에 Snowflake를 사용하는 것이 적합하다. UUID는 길이가 길기 때문에 16bytes이기 때문에 저장 공간 차원에서 Snowflake를 사용하는 것에 비해 비효율적이며, UUID는 랜덤하게 생성되기 때문에 DB에 쿼리를 날려서 유니크를 보장해야 하고, Snowflake는 시퀀스를 사용하기 때문에 DB에 쿼리를 날릴 필요가 없다.

여러가지 관점에서 Snowflake를 사용하는 것이 적합하다. Snowflake는 8bytes로 구성되어 있고, Scalable, 유일성 보장, DB 독립적, 빠르게 생성해야한다는 요구사항을 만족한다. Snowflake id 방식은 아래와 같다.

1비트(사인 비트) + 타임스탬프(41비트) + 데이터센터 ID(5비트) + 워커 ID(5비트) + 시퀀스(12비트)

ID를 기준으로 샤딩을 할 수 있다는 점에서 현재 서비스에서 매력적인 것 같다. ID에서 41비트는 시간을 나타내고, 시간은 단방향으로 증가하기 때문에, 일정 시간을 기준으로 샤딩 전략을 세울 수 있다는 점에서 현재 서비스에서 적합 할 것 같다. 그리고 타임스탬프는 41비트로 구성되어있는데 epoch 기준으로 69년 이후까지 시간을 커버할 수 있다. 즉, 2039년까지 비트에 대해서 고민없이 사용할 수 있기 때문에 10년간 사용할 수 있는 서비스에는 적합하다.

    public byte[] generateId() {
        lock.lock();
        try {
            updateState();
            ByteBuffer idBuffer = ByteBuffer.allocate(ID_SIZE_BYTES);
            return idBuffer.putLong(currentTime).put(nodeId).putShort((short) sequence).array();
        } finally {
            lock.unlock();
        }
    }

자바로 이런식으로 만들수 있다. 자세한 구현 코드는 여기를 확인해보자.

읽기 전략

Screenshot 2024-01-08 at 13 34 16

부하 분산을 위해서 로드밸런서, 디스크 I/O 비용을 줄이기 위해서 인메모리 캐시 서버를 도입하는 것이 좋을 것 같다. 인메모리 캐시 서버로 많이 사용되는 Redis 와 Memcached를 비교해보자.

인메모리 캐시 서버에는 Redis, Memcached가 있는데, Redis는 Memcached의 캐시 기능에 저장소의 개념이 추가된 것으로 볼 수 있는데 Redis 만의 특성 때문에 응답 속도가 균일하지 않을 수 있고(메모리 압축), 장애(RDB로 인한 메모리 이슈)가 발생할 여지가 있다.
캐시 서버에 저장할 데이터 모델이 Key-Value로 저장할 수 있기 때문에 특별한 상황이 아니라면 List, Hash, Set, Sorted Set 등 다양한 자료구조를 사용할 필요가 없어보인다.
Redis 와 Memcached 모두 클러스터링을 지원한다.

여러가지 조건을 따져봤을 때 Memcached를 사용하는 것이 서비스에 적합한 것 같다.

로드 밸런서 알고리즘

로드 밸런서에서 적절하게 트래픽을 분산해주는 알고리즘을 선택해야하는데, 어떤 알고리즘을 선택하는게 좋을까?

Round Robin
Weighted Round Robin
Least Connections
Source IP Hash
Least Response Time

현재 서비스의 특징을 보면 쓰기 연산보다 읽기 연산이 10배 많다는 점, 세션이 오래 지속되지 않는다는 점, 경로가 고정되지 않아도 된다는 점, 제공 API가 단순하여 트래픽 처리가 비슷하다는 점 등 여러가지를 고려해보면 라운드 로빈 방식이 가장 적합하다고 생각한다.

장애 상황

장애가 발생할 수 있는 상황을 생각해보자.

Cache 서버 장애 및 핸들링

캐시에 장애가 나면 일차적으로 어떤 상황이 발생하고 어떻게 예방해야할까?

캐시에 장애가 나면 아래와 같은 상황이 발생할 수 있다.

캐시 서버에 저장된 데이터가 모두 사라진다.
캐시 서버에 저장된 데이터가 모두 사라지기 때문에, 캐시 서버에 저장된 데이터를 읽어오기 위해서 DB에 쿼리를 날려야 한다.
일시적으로 DB에 트래픽이 튀기 때문에 DB에 부하가 발생한다.
DB에 부하가 발생하기 때문에 DB에 장애가 발생할 수 있다.
DB에 장애가 발생하면 서비스가 중단될 수 있다.

캐시 서버에서 발생한 장애가 서비스 중단으로 이어질 수 있다. 캐시를 도입하면 부하를 줄일 수 있지만, 그만큼 위험 요소도 존재한다.

이를 위해서 캐시 서버에 장애가 발생하더라도 서비스가 중단되지 않도록 하기 위해서 클러스터링하여야 한다.

파레토 원칙에 따라서 80%의 트래픽은 20%의 데이터에서 발생한다고 가정하겠다. TTL 설정은 어떻게 해야할까? 시간 지역성을 고려하여 TTL을 설정해야할 것 같다. 최근에 생성된 URL에 대해서는 트래픽이 많을 것이고, 오래된 URL에 대해서는 트래픽이 적을 것이다. 따라서, 최근에 생성된 URL에 대해서는 TTL을 길게 설정하고, 오래된 URL에 대해서는 TTL을 짧게 설정하는 것이 좋을 것 같다.

Database 서버 장애 및 핸들링

데이터베이스에 장애가 나면 일차적으로 어떤 상황이 발생하게될까? 캐시 서버가 죽어서 DB에 트래픽이 튀고, 특정 샤드에 트래픽이 몰리는 핫스팟 문제가 있다고 가정해보자. 이러할 경우는 어떻게 해야할까?

Screenshot 2024-01-08 at 21 38 36

위에서 언급했듯, ID를 기준으로 샤딩을 하는 것이 좋을 것 같다. 여러가지 샤딩 전략을 고려해봐야 하는데, ID를 기준으로 레인지 샤딩하는 것은 어떨까? 레인지 기준은 ID의 시간이 될 것이다. 생각해보면, 최근에 생성된 URL에 대해서는 트래픽이 많을 것이고, 오래된 URL에 대해서는 트래픽이 적을 것이다. 따라서, 핫스팟 문제를 해결할 수 있는 근본적인 방법은 아니다.

추가 요구 사항

특정 URL로의 요청 증가

지진이 발생하거나, 월드컵에서 골을 넣었을 때 네이버와 같은 포털 사이트에 30초 동안 6배 이상의 트래픽이 증가된다고 한다. 좀 더 재밌는 상황을 부여해보면 중국에서 어떠한 이벤트가 발생하여 여러 중국 포털 사이트에서 트래픽 사용량이 10배 이상 증가한다고 가정해보자. 이러한 상황에서 현재 서비스가 정상적으로 작동하도록 하려면 어떻게 해야할까?

간단하게 생각해보면 기존 서비스에 읽기 연산이 급증하는 상황이고, 읽기 연산이 캐시 서버로 집중될 것이다. 그렇다면 캐시 서버에서 트래픽을 처리해줘야하는데, 캐시 서버는 WAS에서 호출하는 구조로 되어있다. WAS 서버와 레디스로 요청이 급증하게 되는데, 이를 분산해줄 필요가 있다.

일단 가장 간단하게는 rate limiter를 두어, 특정 시간 동안 트래픽을 제한할 수 있을 것 같다. 하지만, 이러한 방식은 트래픽을 제한하는 것이기 때문에 서비스가 정상적으로 작동하는 것이 아니다. 요청을 메시지 큐에 저장하고 순차적으로 처리하는 방법도 생각해봤는데, 이 방식은 비동기식으로 처리되기 때문에 리디렉션에 적합하지 않다.

별도의 컴포넌트를 구성해봤다.

Screenshot 2024-01-13 at 11 52 07

크게 2가지 기능을 하는 컴포넌트가 필요하다.

트래픽 분석 처리
특정 URL을 위한 서버 할당

일단 특정 URL로 특정 시간 동안 요청이 증가함을 알아야 한다. 모니터링이 가능해야하기 때문에, 대용량 저장 공간이 필요하고, 빠르게 조회 성능을 보장해야한다. Kafka, ElasticSearch, HBase 등을 사용할 수 있을 것 같다. 이 중에서 Kafka와 ElasticSearch를 사용하기로 결정했다. ElasticSearch는 대용량 저장 공간을 제공하고, 빠르게 조회 성능을 보장한다. 모니터링 서버에서 Polling을 통해서 특정 URL로의 요청이 증가하는지 계속 쿼리로 확인한다. 특정 URL로의 요청이 임계치를 넘어서면, Allocator 서버에게 요청을 보낸다.

Screenshot 2024-01-13 at 11 54 46

파란색 임계치에 넘어서면, Allocator 작업이 수행되어야한다.

Allocator 서버는 특정 URL에 대해서 서버를 할당해준다. 서버를 가용하고 초기화하는 것이 꽤 오래 걸릴 수 있다고 생각하여, 서버를 미리 초기화해놓고 서버풀에서 대기하도록 했다. Allocator 서버는 API 게이트웨이의 라우팅 테이블을 업데이트하여 일시적으로 트래픽이 급증한 특정 URL로의 요청을 라우팅한다. 이러한 방식으로 트래픽을 분산할 수 있다. 라우팅 테이블을 업데이트하는 것, 서버를 최대한 빠르게 초기화하는것, 트래픽이 정상화되었을 때, 서버를 다시 할당 해제하는 것 등 수 많은 작업이 수행되어야 한다. 상당한 Challenge가 될 것 같다.

Shorten URL 만료 + 물리적 삭제

클라이언트에게 URL 만료 시간과 생성된 ShortLink를 삭제하는 기능을 제공한다고 가정해보자. 이러한 기능을 제공하기 위해서는 어떻게 해야할까?

우선, 데이터 모델에서 expired_at이 추가되어야 한다. 그리고 소프트 삭제 처리를 위해서 deleted_at 필드를 추가하겠다. 소프트 삭제를 하는 이유는 삭제 필드를 업데이트하는 것이 물리적으로 삭제하는 것보다 빠르기 때문이다.

시간 단위로 구성된 샤딩에서 만료된 데이터를 삭제하는 방법을 생각해보자. 만료된 데이터를 삭제하는 방법은 크게 2가지가 있다.

TTL
배치 작업

DB에서 자동으로 삭제해주는 TTL을 사용할 수 있지만, 모든 DB에서 제공해주는 기능은 아니다. 배치 작업을 통해 삭제를 해보자.

만료 처리를 위해서 expired_at 필드를 추가했는데, 이 필드를 시간 순으로 정렬해서 순차적으로 삭제하면 좋을 것 같다. 현재 샤딩 전략은 ID를 기준으로 샤딩을 하고 있는데, 이는 만료 시간과 무관하다. 생성이 먼저 되었다고, 먼저 만료되는 것은 아니기 때문에 만료 시간순으로 정렬된 자료구조가 필요하다. 배치 작업이 수행될 때 마다, 샤딩마다 병렬로 만료 시간순으로 정렬을 수행하여, 만료된 데이터를 삭제하면 될 것 같다.

ID를 기준으로 샤딩된 데이터베이스에 주기적으로 배치 작업이 이뤄줘야한다. 시간 지역성에 따르면 생성이 오래된 URL에 대해서는 트래픽이 적을 것이다. 생성 시간이 오래된 샤딩부터 만료되었거나 삭제된 데이터를 디스크에서 삭제하는 작업을 수행하면 될 것 같다. DB에서 Short Link가 삭제 처리 혹은 만료 처리가 되면 캐시 서버에 업데이트 처리가 같은 트랜잭션으로 실행되어야 한다.

그렇다면 다운 타임없이 언제 배치 작업이 수행되어야할까? 트래픽이 적은 시간 때에 수행되어서 DB 부하를 줄이는 것이 좋겠지만, 현 서비스가 글로벌 서비스라 크게 트래픽 변화가 없다고 가정해보자. ~~이러면 이제 골이 아프다.~~ 달리는 자동차를 멈추지 않고 바퀴를 교체해줘야 하는데, 배치 주기를 짧게 하고 작업 범위를 줄여야 하나 배치 주기를 길게 하고 작업 범위를 넓혀야 하나 고민이다.

참고

https://product.kyobobook.co.kr/detail/S000001033116
https://techblog.woowahan.com/2687/
https://systemdesign.one/url-shortening-system-design/#how-does-a-url-shortener-work
https://systemdesign.one/bloom-filters-explained/