가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 8장 ) URL 단축기 설계

 

 

 

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

• 요구 사항 
  • URL 단축 : 주어진 긴 URL을 훨씬 짧게 줄임
  • URL 리디렉션 : 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내 
  • 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨 
  • 트래픽 파악 
    • 매일 1억개의 단축 URL을 만들어 낼 수 있어야 함 
• 개략적 추정 
  • 쓰기 연산 
    • 매일 1억개의 단축 URL 생성 
  • 초당 쓰기 
    • 1억 / 24 / 3600 = 1160 
  • 읽기 연산 
    • 읽기 연산과 쓰기 연산의 비율을 10: 1로 가정 
    • 읽기 연산은 초당 11600회 발생 
  • 저장 용량 
    • URL 단축 서비스를 10년간 운영한다고 가정하면 1억 x 365 x 10 = 3650억 개의 레코드를 보관해야 함 
    • 축악전 URL의 평균 길이는 100바이트로 가정 
    • 10년동안 필요한 저장 용량은 3650억개 x 100바이트 = 36.5TB 

 

 

 

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

• API 엔드포인트 
  • URL 단축용 엔드포인트 
    • 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인에 단축할 URL을 인자로 실어서 POST 요청 
    • POST /api/v1/data/shorten
      • body : {"longUrl" : "longURLString"}
      • response: {"shortenUrl" : "단축 URL"}
  • URL 리다이렉션 엔드포인트
    • 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트 
    • GET api/v1/{shortUrl}
      • response: {"redirectionUrl" : "HTTP 리다이렉션 목적지가 될 원래 URL"}
• URL 리다이렉션 
  • 단축 URL을 받으면 서버는 그 URL을 원래 URL로 바꾸어서 응답 
  • 응답 헤더 
    • 301 Permanently Moved 
      • 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 뜻 
      • 영구적 이전이므로 브라우저는 이 응답을 캐시 
      • 추후 동일한 URL로 요청을 보내야 할 때 브라우저는 캐시된 원래 URL로 요청을 보냄 
      • 처음 요청만 단축 URL 서버로 전달되기 때문에 서버의 부하를 줄일 수 있음 
    • 302 Found 
      • 해당 URL로의 요청이 일시적으로 Location 헤더에 반환된 URL에 의해 처리되어야 한다는 뜻 
      • 클라이언트 요청은 언제나 단축 URL 서버에 먼저 보내진 후 응답 받은 원래 URL로 리다이렉션 
      • 트래픽 분석이 중요할 때 사용 
        • 클릭 발생률이나 발생 위치를 추적하는데 좀 더 유리 
  • 저장 방법 
    • 해시테이블 
      • <단축 URL, 원래 URL>
      • 원래 URL = hashTable.get(단축 URL) 
• URL 단축 
  • 긴 URL을 해시 값으로 대응 시킬 해시 함수를 찾아야 함 
  • 요구 사항 
    • 입력으로 주이진 긴 URL이 다른 값이면 해시 값도 달라야 함 
    • 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 함 

 

 

 

3단계 상세 설계 

• 저장 방법  
  • 해시테이블의 경우 메모리는 유한하고 비싸기 때문에 권장되지 않음 
  • 관계형 데이터 베이스에 저장하는게 좋음 
• 해시 함수 
  • 원래 URL을 단축 URL로 변환하는데 사용됨 
  • hashValue = 해시 함수가 계산하는 단축 URL 길이값 
    • 해시값은 0-9, a-z, A-Z의 총 62개의 문자로 이루어짐 
  • 요구 사항에 부합하는 해시값 구하기
    • 해시값길이를 정하기 위해서는 62^n > = 3650억인 n의 최솟값 (= 7)을 구해야 함 
  • 구현 방법 
    • 해시 후 충돌 해소 
      • 해시 함수의 손쉬운 방법 
        • CRC32, MD5, SHA-1같이 잘 알려진 해시 함수를 사용 
        • -> 가장 짧은 해시값 조차도 7보다는 길다 
          • 해결 방법 
            •  계산된 해시 값 중에서 7자리만 이용
              • 해시 결과가 충돌할 확률이 높아짐 
              • 충돌이 실제로 발생했을 때는 충돌이 해소될 때 까지 사전에 정한 문자열을 해시값에 덧붙임 
              • => 단축 URL을 생성할 때 한번 이상 데이터 베이스를 질의해야 하므로 오버헤드가 큼 
                • 데이터베이스 대신 블룸 필터를 사용하면 성능을 높일 수 있음 
                  • 블룸 필터는 어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는 확률론에 기초한 공간 효율이 좋은 기술 
    • base-62 변환 
      • 진법 변환 
        • 수의 표현 방식이 다른 두 시스템이 같은 수를 공유해야 하는 상황에 사용됨 
        • 62진법을 쓰는 이유는 문자 개수가 62개이기 때문
        • 62진법은 수를 표현하기 위해 총 62개의 문자를 사용하는 진법

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

 

• URL 단축기 상세 설계 
  
  • 원래 URl이 입력되면 데이터베이스에 단축 URL이 있다면 반환, 없다면 ID 생성기를 사용해서 새로운 아이디를 생성해서 반환하고 데이터 베이스에 저장 
  • ID 생성기 
    • 단축 URL을 만들 때 사용할 ID를 말하며 전역적 유일성이 보장되어야 함 
• URL 리다이렉션 상세 설계 
  • 캐시를 사용해서 원래 URl을 조회하게 함으로서 성능을 올릴 수 있음 

 

 

 

4단계 마무리 

• 추후 논의해볼 수 있는 주제 
  • 처리율 제한 장치 
    • 많은 양의 요청이 한번에 밀려들면 무력화 되어 잠재적 보안 결함이 있기 때문에 필터링 규칙 등을 이용해 요청을 걸러내야 함 
  • 웹 서버의 규모 확장 
    • 웹 계층은 무상태 계층이므로 웹 서버를 자유로이 증설 / 삭제가 가능
  • 데이터베이스의 규모 확장 
    • 데이터 베이스를 다중화 하거나 샤딩을 통해 규모 확장가능 
  • 데이터 분석 솔루션 
    • 데이터 분석 솔루션을 사용하면 사용자가 링크를 얼마나 클릭했는지 등의 정보를 추적하여 서비스를 확장하는데 사용 가능 
  • 가용성, 데이터 일관성, 안정성