요구사항

• URL을 입력 받으면 해당 URL에 대한 단축 URL을 만들어 줘야함
• 단축된 URL의 키는 8글자로 생성
• 키 생성 알고리즘은 자유롭게 구현
• 사용자가 단축된 URL로 요청하면 원래의 URL로 리다이렉트 되어야 함
• 원본 URL로 리다이렉트될 때마다 카운트가 증가되어야 하고, 해당 카운트를 조회하는 API를 제공해야함
• DB 없이 컬렉션을 이용해서 데이터 저장
• 기능에 대한 테스트 코드 작성

고려할 부분

키 생성을 어떻게 할 것인지

• 어떤 키 조합을 사용할 것인지
• 중복되지 않는 키를 생성하는 효율적인 방법
  • 겹치는 키가 있는 경우 계속 재생성하게 되기 때문에 CPU 낭비와 지연시간이 걸림

데이터 관리를 어떻게 할 것인지

• URL 매핑 데이터
• 카운팅 데이터

URL Validation 처리

• URL이 아닌 값을 저장하는건 메모리 낭비이기 때문에 URL에 대한 Validation Check가 필요함
• Validation은 어떤 방법으로 처리할 것인지?

메모리 관리

• DB 없이 컬렉션으로 저장하기 때문에 메모리가 제한적임 그렇기 때문에 어떻게 해야 효율적으로 메모리 관리를 할 수 있을지
• 적절한 자료구조 및 데이터 타입 선택

생각한 내용

어떤 키 조합을 사용할 것인지?

• 일단 메모리를 아끼기 위해 바이트 수가 적은 ASCII 값 조합으로 사용하는게 좋아보임
• 키가 8자리이기 때문에 알파벳 조합((소문자 + 대문자) ^ 자릿수 = (26+26)^8)으로도 충분히 넉넉함

중복되지 않는 키를 생성하는 효율적인 방법

• 일단 랜덤한 키를 생성하기 위해 가장 간단한 방법은 키를 구성할 수 있는 문자를 배열에 넣어놓고 배열 사이즈 범위 내에서 Random 함수 사용해서 랜덤 문자로 구성하는 방법
• 위와 같은 방식은 중복을 체크해야하기 때문에 Key와 URL이 매핑된 Map에서 해당 Key가 존재하는지 체크해야한다. 존재하는지 체크하는건 시간복잡도로 O(1) 상수시간이 나오기 때문에 크게 문제가 되지 않는다. 하지만 키를 생성하기 위해 중복된 것이 없을 때까지 8번씩 랜덤 함수를 사용해서 문자를 만들고 중복체크를 해야하기 때문에 등록된 키가 많아질수록 문제가 될 수 있는 설계다.
• 랜덤으로 키를 생성하는 방식 때문에 중복이 발생할 확률이 증가하기 때문에 랜덤으로 키를 생성하지 않으면 된다. 랜덤으로 키를 생성하지않고 순차로 생성하는 방식으로 하면 된다. 이렇게 하면 중복키가 발생하지 않기 때문에 문제가 되지 않는다.
• 순서대로 키를 생성해줄 때 동시에 여러 쓰레드에서 생성하게 되면 중복된 키가 생성 될 수 있기 때문에 이러한 문제를 방지하기 위해 idx 값을 atomic하게 증가시키도록 해야함

URL 매핑 데이터 관리

• Key와 URL를 매핑해주는 Map은 멀티 쓰레드 환경에서 가시성을 보장하기 위해 ConcurrentHashMap을 사용해야함
• 생성될 수 있는 Key의 갯수가 int 범위를 초과하기 때문에 하나의 Map으로 처리 불가능 여러개의 Map을 생성해 배열로 관리 해야함
• 여러개의 Map에 데이터를 적재 해야하는데 이런 경우는 데이터 샤딩을 해야한다. 데이터 샤딩을 하기 위한 샤딩키가 필요한데 간단하게 구현하기 위해 샤딩키는 key의 Hash 값에 Map을 담은 배열의 크기로 나머지 연산한 결과로 설정하는게 좋아 보인다.
• Map을 미리 Key의 경우의 수를 처리 할 수 있는 만큼 생성할 수도 있고 부족할 때 마다 생성하는 방식이 있을텐데 미리 생성하는 경우 간단하지만 불필요한 메모리 낭비가 발생한다. 하지만 미리 생성하기에는 너무 많은 메모리가 필요하다 보니 부족할 때 마다 생성해 리밸런싱 하는게 좋아 보인다.
• 공간이 80%정도 남았을 때 리밸런싱 작업

카운팅 데이터 관리

• Map의 Get을 호출 할 때 마다 해당 키에 대한 호출 횟수를 저장해야하는데 이를 위해 별도의 Map을 만드는건 메모리 낭비가 클 것 같아서 Key와 Value를 저장 할 때 카운팅 데이터도 같이 저장하도록 하는 방식이 좋아보임
• Get을 호출 할 때 마다 카운트 증가를 위해 아토믹 연산을 해줄 수 있는 Map이 필요하다고 생각해서 ConcurrentMap을 이용해 구현하는게 좋아보임

URL Path가 겹칠 수 있는 문제

• 8개의 알파벳으로 구성하고 있다보니 다른 API URL과 겹치는 문제가 생길 수 있기 때문에 Api Path를 겹치지 않도록 설계

URL 리다이렉션 문제

• 악의적인 사용자가 원본 URL을 Short Url하고 동일하게 요청을 하게 되면 redirect 시에 무한정으로 redirect 되서 리다이렉션 루프가 생길 수 있어 서버에 부하가 발생할 수 있기 때문에 Short Url로 들어오는 경우에 대해 유효성 검사가 필요할 것 같고 리다이렉션 횟수 제한을 걸어 놓는 것도 좋아보임