포스팅에 사용된 그림은 책에서 제공하는 그림들 입니다.
1단계 문제 이해 및 설계 범위 확정
요구사항 도출
- URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다.
- URL 리디렉션: 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
- 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨
개략적 추정
- 쓰기 연산: 매일 1억 개의 단축 URL 생성
- 초당 쓰기 연산: 1억/24/3600 = 1160
- 읽기 연산: 읽기 연산과 쓰기 연산은 10:1이라고 할때 초당 11600회 발생한다
- URL 단축 서비스를 10년간 운영한다고 가정하면 1억36510 개의 레코드를 보관해야 한다.
- 축약 전 URL의 평균 길이는 100이라고 하자.
- 따라서 10년 동안 필요한 필요한 저장 용량은 3650억*100바이트 = 36.5TB이다.
2단계 개략적 설계안 제시 및 동의 구하기
API 엔드포인트
클라이언트가 서버가 제공하는 API 엔드포인트를 통해 서버와 통신한다. 우리는 이 엔드포인트를 REST 스타일로 설계해볼 것이다.
- URL 단축용 엔드포인트: 새 단계에 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 실어서 POST 요청을 보내야 한다. 이 엔드포인트는 다음과 같은 형태를 띤다.
POST /api/v1/data/shorten
- 인자: {longUrl: longURLstring}
- 반환: 단축 URL
- URL 리디렉션용 엔드포인트: 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트, 다음과 같은 형태를 띤다.
GET /api/v1/shortUrl
- 반환: HTTP 리디렉션 목적지가 될 원래 URL
URL 리디렉션
아래 그림은 단축 URL을 입력하면 어떤 일이 발생하는지 보여준다.
축 URL을 받은 서버는 그 URL을 원래 바꿔서 301 응답의 Location헤더에 넣어 반환한다.
아래 그림은 클라이언트와 서버 사이의 통신 절차를 좀 더 자세히 보여준다.
여기서의 차이는 301이냐 아니면 302이냐의 차이다.
- 301: 이 응답은 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답이다. 영구적으로 이전되었으므로, 이 응답을 캐시한다. 따라서 추후 같은 단축 URL에 요청을 보내면 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.
- 302: 이 응답은 주어진 URL로의 요청이 ‘일시적으로’ Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답이다. 따라서 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리디렉션 되어야 한다.
이 두 방법은 각기 다른 장단점을 갖고 있다. 서버 부하를 줄이는 것이 중요하다면 301를 사용하는 것이 좋은데 첫 번째 요청만 단축 URL 서버로 전송될 것이기 때문이다. 하지만 트래픽 분석이 중요할 때는 302를 사용하는 것이 클릭 발생률이나 발생 위치를 추적하는 데 좀 더 좋을 것이다.
URL 리디렉션을 구현하는 가장 직관적이 방법은 해시 테이블을 사용하는 것이다. 해시 테이블에 <단축 URL, 원래 URL>의 쌍을 저장한다면 URL 리디렉션은 다음과 같이 구현될 수 있다.
- 원래 URL = hashTable.get(단축 URL)
- 301 또는 302 응답 Location 헤더에 원래 URL을 넣은 후 전송
URL 단축
아래 그림을 보면
결국 중요한 것은 긴 URl을 해시 값으로 대응시킬 수 있는 fx이다.
해시 함수는 다음과 같은 요구사항을 만족해야 한다.
- 입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야함
- 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야함
3단계 상세 설계
데이터 모델, 해시 함수, URL 단축 및 리디렉션에 관한 구체적인 설계안을 만들어보자.
데이터 모델
그동안은 모든 것을 해시 테이블에 저장했는데, 이는 초기 전략으론 괜찮지만 실제 서비스에 쓰기에는 곤란하다. 메모리는 유한한 데다 비싸기 때문. 더 나은 방법은 <단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장하는 것이다. 아래 그림은 테이블의 간단한 설계 사례다.
해시 함수
해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰인다. 편의상 해시 함수가 계산하는 단축 URL 값을 hashValue라고 지칭하겠다.
해시 값 길이
hashValue는 요구사항에서 [0-9, a-z, A-Z]의 문자들로 구성하므로, 사용할 수 있는 문자의 개수는 10+10+26=62개다. hashValue의 길이는 62의n승>3650억인 n의 최솟값을 찾아야 한다.
아래 표는 hashValue의 길이와 해시 함수가 만들 수 있는 URL의 개수 사이의 관계다.
n=7이면 3.5조개의 URL을 만들 수 있다. 요구사항을 만족시키기 충분한 값이다. 따라서 hashValue는 7개로 하겠다.
해시 함수 구현에 쓰일 기술로는 두 가지 방법을 살펴보자.
- 해시 후 충돌 해소 방법
- base-62 변환 법
해시 후 충돌 해소 방법
긴 URL을 줄이면 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다. 손쉬운 방법은 CRC32, MD5, SHA-1같이 잘 알려진 해시 함수를 이용하는 것이다.
근데 표를 보면 가장 짧은 길이를 가진 CRC32 해시값조차도 길이가 7을 넘는다. 어떻게 줄일 수 있을까?
이 문제를 해결하려면 계산된 해시 값에서 처음 7개 글자만 이용하는 것이다. 하지만이렇게 하면 해시 결과가 서로 충돌할 확률이 높아진다. 충돌이 실제로 발생하면, 미리 정한 문자열을 해시값에 덧붙인다.
이 방법을 쓰면 충돌은 해소할 수 있지만 단축 URL을 생성할 때 한 번 이상 DB질의가 필요하므로 오버헤드가 크다. DB대신 블룸 필터를 사용하면 성능을 높일 수 있다. 블룸 필터는 어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는, 확률론에 기초한 공간 효율이 좋은 기술이다.
base-62 변환
진법 변환은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나다. 이 기법은 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용하다. 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문이다. 그럼 지금부터 base-62 변환이 어떻게 이루어지는지 살펴보자. ex)11157 → 62진수
- 62진법은 수를 표현하기 위해 총 62개 문자를 사용하는 진법이다. 따라서 0은 0으로, 9는 9로, 10은 a로, 11은 b로, … 35는 z로, 36은 A로, … 61은 Z로 대응시켜 표현하도록 할것이다. 따라서 62진법에서 ‘a’는 1010을 나타내고, ‘Z’는 6110을 나타낸다.
두 접근법 비교
URL 단축기 상세 설계
URL 단축기는 시스템의 핵심 컴포넌트이므로, 그 처리 흐름이 논리적으로는 단순해야 하고 기능적으로는 언제나 동작하는 상태로 유지되어야 한다.
- 입력으로 긴 URL을 받는다.
- 데이터베이스에 해당 URL이 있는지 검사한다.
- 데이터베이스에 있다면 해당 URL에 대한 단축 URL을 만든 적이 있는 것이다. 따라서 데이터베이스에서 해당 단축 URL을 가져와서 클라이언트에게 반환한다.
- 데이터베이스에 ㅇ벗는 경우에는 해당 URL은 새로 접수된 것이므로 유일한 ID를 생성한다. 이 ID는 데이터베이스의 기본 키로 사용된다.
- 62진법 변환을 적용, ID를 단축 URL로 만든다.
- ID, 단축 URL, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 클라이언트에 전달한다.
URL 리디렉션 상세 설계
아래 그림은 리디렉션 메커니즘의 상세한 설계를 그리고 있다. 쓰기보다 읽기를 더 자주 하는 시스템이라, <단축 URL, 원래 URL>의 쌍을 캐시에 저장하여 성능을 높였다.
로드밸런서의 동작 흐름은 다음과 같이 요약할 수 있다.
- 사용자가 단축 URL을 클릭
- 로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달
- 단축 URL이 이미 캐시에 있는 경우에는 URL을 바로 꺼내서 클라이언트에게 전달
- 캐시에 해당 단축 URL이 없는 경우에는 DB에서 꺼냄, DB에 없다면 사용자가 잘못된 URL을 입력한 경우 일것이다.
- DB에 꺼낸 URL을 캐시에 넣은 후 사용자에게 반환
4단계 마무리
URL 단축기의 API, 데이터 모델, 해시 함수, URL 단축 및 리디렉션 절차를 설계해 보았다.
그리고, 아래와 같은 것들도 고려해볼 수 있다.
- 처리율 제한 장치
- 웹 서버의 규모 확장
- 데이터베이스의 규모 확장
- 데이터 분석 솔루션
- 가용성, 데이터 일관성, 안정성
