8

김키핑·6일 전
가상 면접 사례로 배우는 대규모 시스템 설계 기초씨스터디

가상 면접 사례로 배우는 대규모 시스템 설계 기초

목록 보기
8/8
post-thumbnail

씨스터디를 떠나기 전, 마지막으로(?) 8장을 살펴봤다.
아디오스! 씨스터디 혹은 시스터디!!!

프로그램에서 URL 가독성 등을 위해 URL 단축기 설계를 알아두면 좋다.

1단계 문제 이해 및 설계 범위 확정

이전 장과 마찬가지로, 시스템을 성공적으로 설계해 내려면 질문을 통해 모호함을 줄이고 요구사항을 알아내야 한다. 교재에서 질문 및 답변은 아래와 같다.

지원자: URL 단축기가 어떻게 동작해야 하는지 예제를 보여주실 수 있을까요?
면접관: https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long 입력으로 주어졌다고 해 봅시다. 이 서비스는 https://tinyurl.com/y7ke-ocwj 같은 단축 URL을 결과로 제공해야 합니다. 이 URL에 접속하면 원래 URL로 갈 수도 있어야 하죠.

지원자: 트래픽 규모는 어느 정도일까요?
면접관: 매일 1억(100million) 개의 단축 URL을 만들어 낼 수 있어야 합니다.

지원자: 단축 URL의 길이는 어느 정도여야 하나요?
면접관: 짧으면 짧을수록 좋습니다.

지원자: 단축 URL에 포함될 문자에 제한이 있습니까?
면접관: 단축 URL에는 숫자(0부터 9까지)와 영문자(a부터 z, A부터 Z까지)만 사용할 수 있습니다.

지원자: 단축된 URL을 시스템에서 지우거나 갱신할 수 있습니까?
면접관: 시스템을 단순화하기 위해 삭제나 갱신은 할 수 없다고 가정합시다.

질문과 답변을 통해 아래와 같은 시스템을 정의하였다.

1. URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다.
2. URL 리디렉션(redirection): 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
3. 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구

정의된 시스템 정의를 토대로 URL 단축기 설계를 위한 개략적 추정을 하자.

1. 트래픽 추정 (Traffic)
• 쓰기 연산 (URL 단축)
  - 매일 1억(100 million) 개의 단축 URL 생성
  - 초당 쓰기 연산(TPS): 100,000,000 / (24 × 3,600) = 1,160 TPS
• 읽기 연산 (URL 리디렉션)
  - 쓰기 연산과 읽기 연산의 비율을 1 : 10으로 가정
  - 초당 읽기 연산(TPS): 1,160 × 10 = 11,600 TPS

2. 저장 용량 추정 (Storage)
• 10년 기준 총 레코드 수
  - 1억 개/일 × 365일 × 10년 = 3,650억(365 billion) 개 레코드
• 필요 저장 용량
  - 축약 전 URL 평균 길이를 100 Byte로 가정
  - 10년간 저장 용량: 3,650억 개 × 100 Byte = 36.5 TB

3. 시스템 설계 시 시사점
• 읽기 연산이 초당 11,600회로 압도적이기 때문에 캐시(Cache) 레이어 도입 필수
• 10년간 축적될 36.5 TB 데이터와 높은 QPS 처리를 위해 NoSQL(Key-Value Store) 활용 및 DB 샤딩(Sharding) 고려

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

이번절에서는 URL 단축키 설계를 위한 API 엔드포인트(endpoint), URL 리디렉션, 그리고 URL 단축 플로에 대해 살펴보겠다.

세 가지 요소를 가장 먼저 정의하는 이유는 아래와 같다.

정의할 요소결정하는 내용먼저 정의하는 이유
API 엔드포인트외부와의 소통 규약클라이언트와 서버 간 통신 방식을 정해 전체 설계의 기준점 마련
301 vs 302 리디렉션리디렉션 및 캐시 전략캐시 동작과 서버 요청량에 영향을 주므로 시스템 아키텍처 방향 결정
단축 플로우입력 → 단축 → 저장 → 조회 → 리디렉션전체 처리 흐름을 확정해야 해시 충돌, DB 샤딩 등의 상세 설계 가능

API 엔드포인트

클라이언트는 서버가 제공하는 API 엔드포인트를 통해 서버와 통신한다.
URL 단축기는 기본적으로 두 개의 엔드포인트를 필요로 한다.

(1) URL 단축용 엔드포인트

  • 새 단축 URL을 생성하고자 하는 클라이 언트는 이 엔드포인트에 단축할 URL을 인자로 실어서 POST 요청을 보내야 한다. 
예시

POST /api/vl/data/shorten

• 요청 본문(인자): { longUrl: string }
• 응답 본문(반환): { shortUrl: string }

(2) URL 리디렉션용 엔드포인트
단축 URL에 대해서 HTTP 요청 이 오면 원래 URI로 보내주기 위한 용도의 엔드포인트.
다음과 같은 형태를 띤다.

예시

GET /api/vl/shortUrl

• 응답 본문(반환): HTTP 리디렉션 목적지가 될 원래 URl

URL 리디렉션

사용자가 요청한 URL 대신 서버가 지정한 다른 URL로 클라이언트를 이동시키는 기능

예시

① 사용자가 단축 URL 접속

https://tinyurl.com/qtj5o
          │
          │ GET
          ▼
② TinyURL 서버
          │
          │ 301 응답
          │
          │ Location:
          │ https://www.amazon.com/...
          ▼
③ 브라우저가 Location의 URL로 다시 요청
          │
          ▼
④ Amazon 페이지 접속

이 때, 301 응답과 302 응답의 차이점을 유의하여 확인하여야 한다.
둘다 리디렉션 응답이긴 하지만 차이가 있다.

구분301 Moved Permanently302 Found
의미요청한 URL이 영구적으로 다른 URL로 이동했음을 의미요청한 URL이 일시적으로 다른 URL에서 처리됨을 의미
리디렉션 방식Location 헤더에 원래 URL을 담아 전달Location 헤더에 원래 URL을 담아 전달
캐시브라우저가 리디렉션 결과를 캐시할 수 있음일반적으로 매번 단축 URL 서버에 요청한 후 리디렉션
서버 부하낮출 수 있음. 캐시된 경우 단축 URL 서버를 거치지 않을 수 있음상대적으로 높음. 요청마다 단축 URL 서버를 거침
트래픽 분석이후 요청이 서버에 도달하지 않을 수 있어 추적에 불리요청이 서버를 거치므로 클릭 수, 접속 위치 등 분석에 유리
적합한 상황서버 부하 감소가 중요한 경우트래픽 분석 및 사용자 행동 추적이 중요한 경우

URL 단축 플로

긴 URL → 짧은 문자열로 바꾸려면 "변환기"가 필요하다.
이 변환기 역할을 하는 게 바로 해시 함수(hash function) fx

이 해시 함수는 다음 요구사항을 만족해야 한다.
• 입 력으로 주어지는 긴 URL이 다른 값이 면 해시 값도 달라야 한다.
• 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야한다.

이 해시 함수에 대한 상세 설계는 다음 절에서 살펴볼 것이다.

3단계 상세 설계

URL을 단축하는 서비스를 구현하려면 고려해야 할 사항이 많다.
따라서 이를 구체적으로 구현하기 위한 상세 설계가 필요하며,
데이터 모델, 해시 함수, URL 단축 로직, 리디렉션 로직 등을 구체적으로 설계하고 고려해야 한다.

데이터 모델

개략적 설계를 진행할 때는 모든 것을 해시 테이블에 두었었다. 이 접근법은 초기 전략으로는 괜찮지만 대규모 시스템에 쓰기에는 곤란한데, 메모리는 용량이 제한되어있고, 비싸기 때문이다. 때문에 대규모시스템에서는 해시테이블이 아닌 관계형 데이터베이스를 채택하는 것이 더 나은 선택일 수도 있다.

관계형 데이터베이스에서는 〈단축 URL, 원래 URL〉의 순서쌍을 저장한다.

해시 함수

앞에서도 잠시 언급했듯, 해시 함수(hash function)는 원래 URL을 단축 URI로 변환하는 데 쓰인다.

“짧은 URL을 몇 글자로 만들면 충분할까?”
[0-9, a-z, A-Z]의 문자들로 구성된다. 따라서 사용할 수 있는 문자의 개수는 10+ 26+ 26 = 62개다.

누군가 무수히 많은 url을 단축하려고 한다고 가정해보자.
1글자로 압축하려고 한다면, 62개의 문자가 있으니 최대 62개로 압축할 수 있다.
2글자라면? 첫 번째 자리에도 62개를 넣을 수 있고, 두 번째 자리에도 62개를 넣을 수 있으니
62 × 62 = 62² = 3,844개 를 만들 수 있다.

이와 같은 논리를 우리에게도 적용해보자.
책에서는 이 시스템이 최대 3650억 개의 서로 다른 URL을 단축할 것으로 추정했으니
필요 이상으로 URL을 길게 만들지 않기 위해서 , 62ⁿ ≥ 3650억을 만족하는 가장 작은 n을 찾아야 한다.

이제 필요한 단축 URL의 길이를 정했으므로, 실제로 원래 URL을 이 길이의 단축 URL로 변환하는 방법을 살펴보자.
단축할 URL 글자를 구하면, ‘해시 후 충돌 해소’ 과 ‘base-62 변환’으로 해시함수를 구현할 수 있다.

해시 후 충돌 해소

긴 URL을 줄이려면 원래 URL을 7글자의 문자열로 변환하는 해시 함수가 필요하다.

해시 함수란 어떤 데이터를 입력하면 일정한 규칙에 따라 다른 값으로 변환하는 함수를 뜻하며, 잘 알려진 해시 함수로는 CRC32, MD5, SHA-1 등이 있다.

그런데 해시 함수를 사용해 URL을 변환했을 때, 결과값이 우리가 원하는 7글자를 초과한다면 어떻게 해야 할까?

이 문제를 해결하는 첫 번째 방법은 계산된 해시값에서 처음 7글자만 사용하는 것이다. 하지만 이렇게 하면 해시값의 길이가 짧아지면서 서로 다른 URL이 같은 해시값을 갖는 충돌(collision)이 발생할 가능성이 높아진다.

충돌이 발생하면, 충돌이 해소될 때까지 사전에 정한 문자열을 원래 URL에 덧붙여 다시 해시하는 방법을 사용할 수 있다.

→ ✅ 장점: 충돌 해결 가능
→ ❌ 단점: DB 조회가 필요해서 오버헤드 발생
→ 💡 개선: 블룸 필터를 사용해 DB 조회를 줄임

base-62 변환

base-62 변환은 진법 변환(base conversion)이라고도 불린다.
이 기법은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나다.
이 기법은 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용하다.

62진법
을 쓰는 이유는 hashValue에 사용할 수 있는 문자(character) 개수가 62개이기 때문이다.

비교

해시 후 충돌 해소 전략base-62 변환
단축 URL의 길이가 고정됨단축 URL의 길이가 가변적. ID 값이 커지면 같이 길어짐
유일성이 보장되는 ID 생성기가 필요치 않음유일성 보장 ID 생성기가 필요
충돌이 가능해서 해소 전략이 필요ID의 유일성이 보장된 후에야 적용 가능한 전략이라 충돌은 아예 불가능
ID로부터 단축 URL을 계산하는 방식이 아니라서 다음에 쓸 수 있는 URL을 알아내는 것이 불가능ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알아낼 수 있어서 보안상 문제가 될 소지가 있음

URL 단축기 상세 설계

URL 단축기는 핵심 서비스이므로 구조가 단순해야 하고 절대 꺼지면 안 된다.

  1. URL 조회: 입력받은 긴 URL이 DB에 있는지 확인한다.
  2. 기존 URL 반환: 이미 존재한다면 저장되어 있던 단축 URL을 즉시 반환한다.
  3. ID 발급: DB에 없는 새 URL이면, DB Primary Key로 쓸 고유 ID를 생성한다.
  4. Base62 변환: 생성된 ID를 62진법으로 변환해 단축 URL을 만든다.
  5. 저장 및 반환: [ID / 단축 URL / 원본 URL]을 DB에 저장하고, 단축 URL을 반환한다.

URL 리디렉션 상세 설계

교재의 URL 리디렉션(redirection) 메커니즘은 쓰기보다 읽기를 더 자주 하는 시스템이라,〈단축 URL, 원래 URL〉의 쌍을 캐시에 저장했을 때 성능이 높아진다.

동작흐름은 아래와 같다.

  1. 요청 전달: 사용자가 단축 URL을 클릭하면, 로드밸런서가 요청을 웹 서버로 전달한다.
  2. 캐시 확인 (Hit): 캐시에 URL이 있으면 즉시 클라이언트에게 반환한다.
  3. DB 조회 (Miss): 캐시에 없으면 DB에서 조회한다. (없을 경우 오류 반환)
  4. 캐시 저장 및 반환: DB에서 찾은 URL을 캐시에 저장한 뒤 클라이언트에게 반환한다.

4단계 마무리

이외에도 이번 주제와 관련해 가용성과 확장성을 높이기 위한 추가 논점들을 제시할 수 있을 것이다.

주제핵심 논점 및 적용 내용
처리율 제한 장치• 대량 요청 폭주 시 서버 마비를 막기 위한 보안 및 방어 대책
• IP 주소나 사용자 기반 필터링 규칙 적용
웹 서버 규모 확장• 웹 계층을 무상태(Stateless) 구조로 설계하여 자유로운 증설 및 삭제 가능
데이터베이스 규모 확장• DB 다중화 및 샤딩(Sharding)을 통한 읽기/쓰기 성능과 저장 용량 확장
데이터 분석 솔루션• 클릭 수, 클릭 시점, 유저 유입 경로 등 비즈니스 핵심 지표 수집 및 분석 모듈 통합
시스템 기본 속성• 대규모 시스템 운영을 위한 가용성, 데이터 일관성, 안정성 확보 방안
profile
김키핑
양치기소녀
이전 포스트

7

0개의 댓글