728x90
문제 이해 및 설계 범위
면접관에게 질문해서 파악한 설계 요구사항
- 쓰기연산: 매일 1억 개의 단축 URL 생성
- 초당 쓰기 연산: 1억개 / 24/ 3600 = 1160
- 읽기 연산: 읽기 연산과 쓰기 연산 비율 10:1
- 초당 읽기 연산: 11,600 회(1160 * 10) 발생
- URL 단축 서비스를 10년간 운영하면 1억 * 365 * 10 = 3650억 개의 레코드를 보관
- 축약 전 URL 평균 길이는 100
- 10년 동안 필요한 저장 용량 3650억 * 100 바이트 = 36.5TB
개략적 설계안
API 엔드포인트, URL 리다이렉션, URL 단축에 대해 살펴본다
API 엔드포인트
클라이언트는 서버가 제공하는 API 엔드포인트를 통해 통신하고, 엔트포인트는 REST API로 설계
아래 두 가지 API를 설계
- URL단축용 엔드포인트
- POST /api/v1/data/shorten
- 인자: {longUrl: longURLstring}
- 반환: 단축 URL
- URL 리다이렉션용 엔드포인트
- GET /api/v1/shortUrl
- 반환: HTTP 리다이렉션 목적지가 될 URL
URL 리다이렉션
단축 URL을 받은 서버는 원래 URL로 바꾸어서 응답의 Location 헤더에 넣어 반환해야 한다.
- 301 Permanently Moved
=> 서버 부하를 줄이고 싶을 때 사용
- 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답
- 영구적으로 이전 되었으므로, 브라우저는 응답을 캐시(cache)한다.
- 추후 같은 단축 URL에 요청을 보낼 필요가 있을 때, 브라우저는 캐시된 원래 URL로 요청을 보내게 된다. - 302 Found
=>트래픽 분석이 중요할 때 사용
- 해당 URL에 대한 HTTP 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리 되어야 한다.
- 클라이언트의 요청은 단축 URL 서버에 먼저 보낸 후, 원래 URL로 리다이렉션 되어야 한다.
URL 단축
긴 URL을 해시 값으로 대응시킬 해시 함수 fx를 찾아야 한다.
해시 함수에는 아래 요구사항을 만족해야 한다.
- 입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야 한다.
- 계산된 해시 값이 원래 입력으로 주어진 URL로 복원될 수 있어야 한다.
상세 설계
데이터 모델, 해시 함수, URL 단축 및 리다이렉션에 관해 설계
데이터 모델
- 해시 테이블에 모든 것을 두었는데, 유한하고 비싼 메모리를 사용하기 때문에 실제 시스템에서는 사용하기 곤란
- 더 나은 방법으로 <단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장하는 것.
- url 데이터 테이블에 id(Primary Key), shortURL, logURL의 세 개 컬럼을 갖는다.
해시함수
해시 함수가 계산하는 단축 URL 값을 hashValue로 표현
해시 값 길이
- [0-9, a-z, A-Z]의 문자들로 구성된다.
- 10 + 26 + 26 = 62개
- 62^n >= 3650억 에서 n의 최소값을 찾아야 hashValue의 길이를 정할 수 있다.
해시 후 충돌 해소
- URL을 줄이려면 해시 함수가 필요
- 해시 함수는 CRC32, MD5, SHA-1 같은 해시 함수를 이용
- 시스템에서 요구하는 7자리보다 길어서 해결방법으로 계산된 해시 값에서 처음 7개만 사용한다.
- 그러나, 해당 방법은 해시 결과가 충돌할 가능성이 있다.
- DB에 단축 URL의 처음 7개 값이 있는지 확인.
- 있을 경우, 정한 문자열을 해시값에 덧붙이고 충돌이 해소될 때까지 반복한다.
- 없을 경우, DB에 저장
- 해당 방법을 사용하면 단축 URL을 생성할 때 한 번 이상 데이터베이스 질의를 해야한다.
- 데이터베이스 대신 블룸 필터를 사용하면 성능을 높일 수 있다,
- 블룸 필터는 어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는 확률론에 기초한 공간 효율이 좋은 기술.
base-62 변환
- 진법 변환 접근 방법
- 수의 표현 방식이 다른 시스템이 같은 수를 공유할 때 유용
- 62진법을 사용하는 이유는 hashValue에 사용할 수 있는 개수가 62개
두 접근법의 차이점
해시 후 충돌 해소 전략 | base-62 변환 |
단축 URL의 길이가 고정됨. | 단축 URL의 길이가 가변적. ID 값이 커지면 같이 길어진다. |
유일성이 보장되는 ID 생성기가 필요치 않음. | 유일성 보장 ID 생성기가 필요 |
충돌이 가능해서 해소 전략이 필요. | ID의 유일성이 보장된 후에야 적용 가능한 전략이라 충돌은 아예 불가능. |
ID로부터 단축 URL을 계산하는 방식이 아니라서 다음에 쓸 수 있는 URL을 알아내는 것이 불가능. | ID가 1씩 증가하는 값이라고 가정한다면 다음에 쓸 수 있는 URL이 무엇인지 쉽게 알아낼 수 있어서 보안상 문제가 될 소지가 있음 |
URL 단축기 상세 설계
62진법 변환 기법을 사용해서 적용하는 순서.
예시)
- 입력된 URL: https://en.wikipedia.org/wiki/Systems_design (1번)
- 해당 URL에 대해 ID 생성기가 반환 ID는 2009215674938 (4번)
- 해당 ID를 62진수로 변환하면 zn9edcu (5번)
URL 리다이렉션 상세 설계
- 사용자가 단축 URL을 클릭
- 로드밸러서가 해당 클릭으로 발생한 요청을 웹 서버로 전달
- 단축 URL이 캐시에 있는 경우 바로 클라이언트에 전달
- 캐시에 URL이 없는 경우, 데이터베이스에서 꺼낸다. 데이터베이스에 없다면 사용자가 잘못된 URL을 입력한 경우
- 데이터베이스에 꺼낸 URL을 캐시에 넣은 후, 사용자에게 반환
마무리
- 처리율 제한 장치: 엄청난 양의 URL 단축 요청이 밀려오면 무력화될 수 있는 문제가 있다.
- 웹 서버의 규모 확장: 웹 계층은 무상태 계층이므로,웹 서버를 자유로이 증설하거나 삭제할 수 있다.
- 데이터베이스의 규모 확장: 데이터베이스를 다중화하거나 샤딩하여 규모 확장
- 데이터 분석 솔루션: URL 단축기에 데이터 분석 솔루션을 통합해 두면 어떤 링크가 얼마나 많은 사용자가 클릭했는지 중요한 정보를 알 수 있다.
- 가용성, 데이터 일관성: 대규모 시스템을 성공적으로 운영되기 위해서는 반드시 갖추어야하는 속성
'읽은 책 > [책] 가상 면접 사례로 배우는 대규모 시스템 설계 기초 1권' 카테고리의 다른 글
10장. 알림 시스템 설계 (0) | 2024.07.15 |
---|---|
9장. 웹 크롤러 설계 (0) | 2024.07.14 |
7장. 분산 시스템을 위한 유일 ID 생성기 설계 (0) | 2024.07.11 |
6장. 키-값 저장소 설계 (0) | 2024.07.09 |
5장. 안정 해시 설계 (0) | 2024.07.09 |