URL 단축기 설계 면접 퀴즈

URL 단축기는 기능이 둘뿐입니다. 긴 주소를 짧은 키로 바꾸고, 짧은 키로 원래 주소로 보내는 것입니다. 두 기능의 무게가 100배 다른 것이 이 설계의 출발점입니다.

기능 요구사항과 범위 밖

같은 주소에 같은 키를 주지 않기로 한 것이 중요합니다. 재사용하려면 키를 만들기 전에 "이 주소가 이미 있는지" 를 찾아봐야 하고, 누적 300억 개 규모에서 그 조회는 값싸지 않습니다.

포기하면 쓰기 경로가 조회 없이 끝납니다. 같은 주소에 키가 여러 개 생기는 것은 저장 공간을 조금 더 쓰는 문제일 뿐입니다.

두 경로의 무게

조회가 생성의 100배입니다. 그래서 최적화 대상이 분명합니다. 쓰기가 조금 느린 것은 괜찮고 읽기가 조금 느린 것은 안 됩니다.

이 비율은 서비스의 성질에서 나옵니다. 링크는 한 번 만들어 여러 번 공유되고, 인기 있는 링크는 수만 번 열립니다.

숫자가 정하는 것

키 길이가 곧 서비스 가치다

단축기의 존재 이유는 주소가 짧아지는 것입니다. 키가 길어지면 서비스의 값이 떨어집니다.

그런데 짧게 만들수록 담을 수 있는 개수가 줄어듭니다. 이 상충이 이 설계의 첫 계산이고 다음 단계에서 다룹니다.

조회 수 세기를 기능에 넣은 이유

리디렉션은 우리 서버를 지나갑니다. 그 순간에 세면 추가 비용이 거의 없습니다. 그런데 뒤에서 보듯 리디렉션 응답을 어떻게 고르는지에 따라 이 기능이 동작하지 않을 수 있습니다.

기능 하나가 다른 결정에 묶여 있는 예입니다. 요구사항에 적어 두면 그 결정을 할 때 놓치지 않습니다.

키 7자 이하 에 누적 300억 개 을 담아야 합니다. 이 두 숫자로 길이를 계산합니다. 감으로 정하지 않습니다.

문자 집합과 길이

숫자 10개와 대문자 26개와 소문자 26개를 쓰면 자리마다 62가지입니다. 길이가 하나 늘면 개수가 62배가 됩니다.

7자를 고릅니다. 6자로도 개수는 담기지만 그것이 왜 위험한지가 다음 이야기입니다.

절반이 차면 무슨 일이 생기나

키를 무작위로 뽑는다면 이미 쓰인 키를 뽑을 확률이 곧 사용률입니다.

6자에 300억을 담으면 사용률이 약 53퍼센트
새 키를 뽑을 때 절반은 이미 쓰인 것과 겹친다

겹치면 다시 뽑아야 하고, 다시 뽑을 때마다 이미 있는지 확인하는 왕복이 듭니다. 사용률이 올라갈수록 평균 시도 횟수가 늘어납니다.

7자는 사용률이 1퍼센트 미만이라 겹칠 일이 거의 없습니다. 키 공간의 여유는 충돌 처리 비용을 낮추기 위한 것입니다.

문자 집합을 줄이면

읽기 쉽게 만들려고 헷갈리는 문자를 빼는 경우가 있습니다. 숫자 0과 대문자 O, 숫자 1과 소문자 l 같은 것입니다.

개수가 40퍼센트 줄지만 여전히 충분합니다. 사용률이 1퍼센트대에서 1.4퍼센트대로 오를 뿐입니다. 사람이 손으로 옮겨 적는 링크라면 이 교환이 이득입니다.

대소문자를 쓸 수 없는 경우

주소의 일부를 대소문자 구분 없이 다루는 환경이 있습니다. 그러면 자리당 36가지가 되고 7자는 약 780억입니다. 누적 300억 개 을 담으면 사용률이 38퍼센트라 6자와 비슷한 상황이 됩니다.

그때는 8자로 늘려야 합니다. 이렇게 문자 집합이 길이를 정하므로 두 값을 함께 결정합니다.

계산을 문서에 남긴다

키 길이는 한 번 정하면 바꾸기 어렵습니다. 이미 발급한 키가 남아 있기 때문입니다.

그래서 어떤 가정으로 이 길이를 골랐는지 적어 둡니다. 보관 기간, 하루 생성량, 문자 집합, 목표 사용률입니다. 가정이 달라지면 그 계산을 다시 하면 됩니다.

길이 7자를 정했습니다. 이제 그 7자를 무엇으로 채울지 고릅니다. 방법이 셋이고 각각 다른 대가가 있습니다.

주소를 해시해 앞자리를 쓴다

원래 주소를 해시하고 앞 7자를 씁니다. 같은 주소면 같은 키가 나오므로 재사용이 저절로 됩니다.

문제는 다른 주소가 같은 앞자리를 낼 수 있다는 것입니다. 그러면 저장 전에 이미 있는지 확인해야 하고, 겹치면 뒤에 무언가를 붙여 다시 해시해야 합니다. 확인 왕복이 쓰기 경로에 붙습니다.

그리고 요구사항이 재사용을 요구하지 않으므로 이 방법의 장점을 쓰지 않습니다. 장점 없이 왕복만 남습니다.

번호를 문자로 바꾼다

7장에서 만든 유일한 번호를 62가지 문자로 바꿔 씁니다. 번호가 이미 유일하므로 키도 유일하고 확인이 필요 없습니다.

번호 1,000,000 을 62진법으로 바꾸면 4자
번호가 커지면 자릿수가 늘어난다

두 가지 대가가 있습니다. 번호가 순차적이면 다음 키를 추측할 수 있고, 초기에는 자릿수가 짧아 길이가 들쭉날쭉합니다. 앞자리를 채우면 길이는 고정되지만 추측은 더 쉬워집니다.

무작위로 뽑는다

7자를 무작위로 뽑습니다. 앞 단계에서 계산한 대로 사용률이 1퍼센트 미만이라 겹칠 일이 거의 없습니다.

이 요구사항에서는 무작위를 고릅니다. 재사용을 포기했으므로 해시 방식의 장점이 없고, 추측 가능성이 남는 것보다 확인 한 번이 낫습니다.

번호 변환도 좋은 선택이 될 때

추측이 문제가 되지 않는 곳이라면 번호 변환이 더 좋습니다. 확인 왕복이 아예 없고, 키가 시간순으로 커져 저장소 삽입도 값쌉니다.

요구사항이 방법을 정합니다. 세 방법 모두 실제로 쓰이고, 어느 것이 더 좋다고 말할 수 없습니다.

두 방법을 섞지 않는다

무작위와 번호 변환을 함께 쓰면 같은 키 공간에서 두 규칙이 돌아갑니다. 그러면 무작위로 뽑은 값이 번호 변환의 결과와 겹칠 수 있고, 어느 규칙이 그 키를 만들었는지 알 수 없어 문제를 찾기 어려워집니다.

섞어야 한다면 공간을 나눕니다. 예를 들어 첫 글자로 구분해 규칙마다 다른 영역을 쓰게 합니다.