1단계 문제 이해 및 설계 범위 확정
URL 단축기를 설계하기 위해 면접장에서 여러 질문들을 통해 요구사항을 확인하자.
지원자: 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을 시스템에서 지우거나 갱신할 수 있습니까?
면접관: 시스템을 단순화하기 위해 삭제나 갱신은 할 수 없다고 가정합시다.
Plain Text
복사
이렇게 질문을 통해 구체화한 요구사항은 다음과 같다.
•
긴 URL을 짧게 줄인다.
•
축약된 URL로 HTTP 요청이 오면 원래의 URL로 리디렉션(redirection)한다.
•
높은 가용성과 규모 확장성, 장애 감내가 요구된다.
이를 통해 개략적인 규모 추정을 하면,
•
쓰기 연산 : 매일 1억 개의 단축 URL 생성
•
초당 쓰기 연산 : 1억 / 24 / 3600 = 1,160
•
읽기 연산 : 읽기와 쓰기의 비율을 10:1로 잡았을 때, 초당 11,600회
•
저장 용량 :
◦
URL 단축 서비스를 10년간 운영한다고 하면, 1억 * 365 * 10 = 3,650억 개의 레코드 보관
◦
축약 전 URL의 평균 길이 100
◦
10년간 필요한 저장용량 = 3,650억 * 100 byte = 36.5 TB
2단계 개략적 설계안 제시 및 동의 구하기
API 엔드포인드
클라이언트는 서버가 제공하는 API를 통해 통신하는데, RESTful API 스타일로 설계한다고 가정하자. URL 단축기에서는 기본적으로 두 개의 API 엔드포인트가 필요하다.
1.
URL 단축 요청 API : 새 단축 URL을 생성하고자 할 때, 클라이언트에서 단축할 URL을 인자로 넣어 POST 요청을 보낸다.
### request
POST /api/v1/data/shorten
{
"longUrl": longUrlString
}
Plain Text
복사
2.
URL 리디렉션 API : 단축된 URL을 통해 HTTP 요청이 오면 원래 URL로 리디렉트 시켜준다.
### request
GET /api/v1/shortUrl
### response
{
"longUrl": longUrlString
}
Plain Text
복사
URL 리디렉션
위 그림은 단축 URL을 통해 접속하면 발생하게 되는 리디렉션 응답이다.
단축 URL을 받은 서버는 원래 URL로 바꾸어 301 응답의 Location 헤더에 넣어 반환한다. 여기서 302 응답을 사용 할수도 있는데, 서버 부하 측면에서는 301 응답이 좋고 트래픽 분석이 중요하다면 클릭 발생률이나 발생 위치를 추적하는데 유리한 302 응답이 좋다.
이러한 URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하여 <단축 URL, 원래 URL> 쌍으로 저장해두는 것이다.
301 응답과 302 응답의 차이
•
301 Permanently Moved : HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었음을 나타내는 응답으로, 브라우저는 이 응답을 캐시하여 다음 URL 요청 시 사용한다.
•
302 Found : HTTP 요청이 일시적으로 Location 헤더에 반환된 URL로 처리되어야 한다는 응답이다. 브라우저는 캐시하지 않고 항상 요청한 URL 보내진다.
URL 단축
URL 단축기에서 중요한 것은 긴 URL을 해시 값으로 대응시키는 해시 함수를 찾는 것이다.
여기서 해시 함수는 다음의 요구사항들을 만족해야한다.
•
입력으로 주어지는 긴 URL이 다르다면 해시 값도 달라야한다.
•
계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야한다.
3단계 상세 설계
데이터 모델
개략적인 설계를 할 때는 모든 URL을 해시 테이블에 두는 것으로 설계했다. 하지만 메모리는 비싼 자원이라 시스템 설계에서 사용하기에는 곤란하다. 따라서 <단축 URL, 원본 URL> 순서쌍을 RDB에 저장하는 것이 바람직하다.
위에서는 필요한 컬럼만 두었지만, 생성 시점이나 활성 여부 등의 추가적인 컬럼을 둘 수 있다.
해시 함수
해시 함수는 원본 URL을 단축 URL로 변환하는데 사용되는데, 편의상 hashValue라 지칭하자.
해시 값 길이
hashValue는 [0-9, a-z, A-Z]의 문자로 총 62개의 문자를 사용할 수 있다. 이러한 hashValue의 길이는 62^n ≥ 3650억을 만족하는 n의 최소값을 찾아야한다.
위 표를 참고했을 때, 우리의 상황에서 hashValue의 길이는 7이 적합할 것이다.
해시 후 충돌 해소
우리는 원본 URL을 7글자로 줄이는 해시 함수가 필요한데, 손쉬운 방법으로는 CRC32, MD5, SHA-1 같이 잘 알려진 해시 함수를 사용하는 방법이 있다.
/zttps://en.wikipedia.org/wiki/Systems_design URL을 각각의 방법으로 축약하면 위와 같다.
이렇게 얻어진 해시 값을 보면 전부 7글자를 넘는다. 이 문제를 해결하는 첫 번째 방법은 얻어진 해시 값에서 첫 7글자만 이용하는 방법이다.
하지만 이 방법은 해시 결과가 충돌할 확률이 높아지는데, 충돌 시 충돌이 해소될 때까지 사전에 정한 문자열을 해시에 덧붙여 해결할 수 있다.
첫 번째 방법은 데이터베이스 조회가 많아져 오버헤드가 커지므로, 데이터베이스 대신 블룸 필터를 사용하여 성능을 높이는 것이 가능하다.
base-62 변환
진법 변환(base conversion)은 URL 단축기를 구현할 때 자주 사용되는 접근법인데, 숫자로 이루어진 고유한 ID를 생성 후 진법 변환해 hashValue로 사용하는 것이다. 여기에서는 hashValue의 문자 개수와 동일한 62진법을 적용할 수 있다.
•
0 … 9 : 0…9
•
10 … 35 : a…z
•
36 … 61 : A…Z
이렇게 얻어진 값을 해시 값으로 사용하여 단축 URL에 사용하는 것이다.
두 접근법 비교
URL 단축기 상세 설계
URL 단축기는 시스템의 핵심 컴포넌트로, 그 처리 흐름이 논리적으로 단순하고 기능적으로 언제나 동작하는 상태로 유지되어야 한다. 62진법 변환 기법을 사용해 설계해보자.
•
새로운 ID를 생성했을 때 2009215674938가 반환
•
62진수로 변환하여 zn9edcu
•
DB에 저장
여기서 ID를 생성하는 것은 이전 장에서 학습했던 ID 생성기를 참고하여 분산 시스템에서 동작하는 ID 생성기일 것이다.
URL 리디렉션 상세 설계
URL 리디렉션의 메커니즘은 위와 같을 것이고, 여기서 캐시를 추가하여 성능을 높이도록 하였다.
4단계 마무리
URL 단축기의 API 엔드포인트, 데이터 모델 , 해시 함수 , URL 단축 및 리디렉션을 설계해보았다. 시간이 남는다면 추가적으로 논의해볼만한 사안들을 아래에 적어두었다.
•
처리율 제한 장치(rate limiter) : 우리가 설계한 URL 단축 시스템은 엄청난 양의 트래픽이 몰리면 무력화 될 수 있다는 잠재적 보안 결함을 가지고 있다. 처리율 제한 장치를 두어 IP 주소를 비롯한 필터링 규칙을 통해 요청을 걸러내는 것도 좋을 것이다.
•
웹 서버의 규모 확장 : URL 단축기의 웹서버는 무상태(stateless) 계층이므로 자유로이 증설하거나 삭제할 수 있다.
•
데이터베이스의 규모 확장 : 데이터베이스를 다중화하거나 샤딩(sharding)하여 규모 확장성을 달성할 수 있다.
•
데이터 분석 솔루션 : URL 단축기에 데이터 분석 솔루션을 통합해, 어떤 링크를 얼나마 많은 사용자가, 언제 접속했는지 등 중요한 정보를 알아낼 수 있다.
•
가용성, 데이터 일관성, 안정성 : 대규모 시스템이 성공적으로 운영되기 위해서는 가용성과 데이터 일관성, 안정성을 반드시 갖추어야한다.