URL Shortener
출처: https://medium.com/@sandeep4.verma/system-design-scalable-url-shortener-service-like-tinyurl-106f30f23a82
제약 조건
- URL 은 만료되는 기한이 있나요?
- No. -> 데이터는 추가만 될 뿐 삭제 또는 업데이트 기능은 없음.
- URL 을 Customize 할 수 있나요?
- Yes. URL 인코딩 과정없이 사용자가 지정한 URL 로 생성하는 기능 추가.
- URL 의 최대 길이는?
- [스토리지 제약] 서비스는 얼마나 지속되나요?
- 100년이라고 하면 하나의 데이터가 500 byte (long_url, short_url, created_date) 라고 가정하고, 1달에 100만개가 들어오면 총 60 TB 의 스토리지가 필요.
- [트래픽 제약] 1초에 몇 개 또는 한 달에 몇 개의 request 가 들어온다고 가정을 할까?
- 한달에 1억번의 요청이 들어온다고 가정하고, 200:1 의 비율로 read:write 된다고 가정하면 평균 초당 40개를 생성 (write), 8000개의 URL 을 read 한다고 볼 수 있음.
- [메모리 제약] 캐싱을 위해서 얼만큼의 메모리가 필요할까?
- Pareto Principle 에 따라서 80:20 이라고 하면 (80%의 요청은 20%의 데이터를 접근한다) read 요청은 초당 8000건이기 때문에 하루에 7억건의 read 요청이 들어올 수 있고, 이는 70 GB (7억 x 500 byte * 0.2 20%) 의 메모리를 요구한다.
- URL redirection count 에 대한 metrics 도 갖고 가장 많이 방문하는 사이트에 대한 정보도 갖고있어야 할까요?
기능적 제약사항
- Long url를 short url로 변환
- Short url을 long url 로 redirect
- Link 는 짧으면 짧을수록 좋음
- 최대 16자의 custom url 을 만들 수 있음
- 한번 시스템에 등록된 URL 은 제거되지 않음
-
- 가장 많이 클릭한 링크와 같은 metrics 정보를 수집해야함
비기능적 제약사항
- 서비스는 24시간 내내 사용 가능해야함
- URL redirection 은 빨라야하고, peak load 가 있어도 성능이 저하되는 일은 없어야함
- 서비스는 REST API 형태로 제공되어 3rd party app 이 사용할 수 있도록 해야함.
Naïve Design
- Single server: Single Point Of Failure (SPOF) 가 발생할 수 있음
- 시스템이 확장 가능하지 않다
- 데이터 베이스 하나가 초당 8000건의 요청을 처리하기에 충분하지 않음
- 위의 naïve 한 디자인을 개선하기 위해서는 web server 쪽에 load balancer 를 추가해야되고, 샤딩을 통해서 데이터베이스를 확장해야하고, DB 에 대한 부하를 줄이기 위해서 캐시 시스템을 사용해야하는 것이 좋아보임.
REST API 설계
- [POST] /create: Param 으로는 변환할 long_url 과 API 에 대한 접근 권한이 필요하다고 하면 api_key 가 필요하다. 사용자가 원하는 URL 을 생성하기 위해서 선택적으로 custom_url 을 인자로 받을 수 있다.
- [GET] /short_url: param 으로는 short_url 이고 반환은 302 http redirection response 이다. 301은 URL 이 완전히 제거되었다라는 것을 의미하고, 302는 일시적으로 URL 을 redirect 시킨다라는 의미이기 때문에 302로 반환한 결과에 대해서 분석을 하면 redirect 된 것의 횟수를 계산할 수 있다.
Shortening algorithm
- URL 을 줄이는 알고리즘에는 크게 2가지가 있다.
- URL 인코딩
- Random Generation
- Base62 Conversion
- MD5 URL 인코딩
- Key Generation Service
- URL 인코딩 알고리즘에는 2가지가 있다 (1) base 62 의 URL 인코딩 (2) MD5 의 URL 인코딩
- Base62는 0-9, a-z, A-Z 를 지원하는 62진수라고 볼 수 있다. 따라서, 62^5 만 되어도 약 9억개의 URL 을 생성할 수 있다. 조건 중에 총 1200억개의 URL 을 만들 수 있다고 했기 때문에 7 자리를 사용하면 총 3조5천억개를 만들 수 있으므로 넉넉하다. 그러면 어떻게 인코딩 할 수 있을까?
- 인코딩 방법 1)은 7자리의 값을 62가지 조합중에서 랜덤으로 선택해서 만든 다음에 db 에 있는지 확인해본다. 존재하면 다시 랜덤하게 뽑고 반복하며, 존재하지 않는다면 그 조합의 URL을 사용한다.
- 인코딩 방법 2) 는 62진수를 사용하여 표현하는 방법이 있다. 각 char 를 숫자에 맵핑해서 변환한 값을 62진수로 처리하며 된다. 예를 들어, 첫번째 데이터에는 십진수 10000000000을 맵핑한다고 하면 이를 62진수로 변환한 값을, 그 다음 데이터는 10000000001을 62진수로 변환한 값을 shortened URL 로 사용한다.
- 인코딩 방법 3) 은 MD5 해싱을 사용하는 건데, 128 bit 의 hash bit 를 생성하는 hash function 이라고 한다.
DB 설계
- User table : user_id, name, email, created_date
- Link table : short_url, long_url, user_id
- 어떤 데이터베이스를 사용할 것인가
인코딩 방법 1) 랜덤한 char 로 구성하는 경우
- MongoDB 를 사용한다면 short_url 을 shard key 로하여 hashed sharding 을 적용할 수 있다. 따라서, mongodb 는 자동적으로 short_url 에 대한 hash 를 적용하여 query 를 날릴 수 있다.
- 즉, application 이 랜덤으로 생성한 char에 대해서 별도의 hash function 을 수행할 필요가 없다. 만약에 shard key로 사용한 key 가 업데이트 된다고 하면 shard key 로 사용할 수 없다. 하지만, 한번 생성된 short_url 은 업데이트될 일이 없기 때문에 shard key 로 사용해도 된다. 이를 기반으로 데이터는 고르게 분산된다
- 여기서 read 속도를 더 높이기 위해서는 short_url 에 인덱싱을 사용하면 된다. 추가로 캐시 기능을 활용해서 속도를 더 높일 수 있다. 캐싱에 대해서는 아래에서 다룰 예정이다.
인코딩 방법 2) base 62 를 활용한 short url
- 큰 counter 변수가 존재하고, 이를 62진수로 변환을 하는 방법이다. 따라서 counter 는 요청이 들어올때마다 1씩 계속 증가해야한다.
- SQL에서 제공하는 auto increment 와 sharding 을 통해 확장성을 높이는 방법을 사용하면 구현할 수 있다. Id 를 auto increment 하는 방법은 NoSQL 에서는 존재하지 않기 때문에 RDBMS를 사용하는 것이 유리하다고 볼 수 있다.
- Sharding 은 거대한 데이터를 쪼개서 서로 다른 RDBMS 서버에 저장하고, 이를 분산시켜 데이터를 조회하는 방식이다. 그러나 이런 식의 partitioning 은 sharding key 를 선택하는 문제나, 스키마 디자인에 대한 문제나 application rewrite, 인프라 유지보수등의 문제가 있다.
- RDBMS 가 샤딩되기 전에 몇가지 design decision 이 선행되어야 하는데, 예를 들면 sharding key, 스키마 변경 (schema change) 그리고 sharding key, shard (database) 그리고 물리 서버 간 맵핑 관계가 필요하다. 예를 들어, 샤딩키를 auto increment 로 해서 하나의 데이터베이스에서는 1~1000만, 다른 하나에서는 1001만 1 ~ 2천만 으로 지정할 수 있다.
- DB 인스턴스가 죽는 것을 방지하기 위해서 100개 정도의 인스턴스를 띄워놓을 수 있고, 하나의 서버의 스토리지가 꽉차거나 index 가 max 를 찍게 되면 (ex. 1000만) 다른 인스턴스가 역할을 전달받아서 수행할 수 있다.
- 데이터에서 발생하는 deadlock 이나 race condition, particle failure 를 방지하기 위해서 Zookeeper 와 같은 분산 서비스 시스템을 사용할 수 있다. Zookeeper 는 기본적으로 여러 개의 호스트가 존재할 때 distributed coordination service 를 제공하는 오픈소스이다. 예를 들면, 서버의 이름, active database 의 개수, 죽은 서버의 개수 등의 정보를 관리한다. 그리고 여러 서버간 sync 를 유지하고 coordination 을 하기 위한 기능을 제공한다. 즉, 서버 간 데이터를 주고 받을 수 있는 환경을 설정할 수 있다.
- 만약에 하나의 데이터베이스 서버가 죽었다고 하면, 다른 데이터베이스 (master to slave) 에 데이터를 복사해서 서비스를 하도록 복구시킬 수 있다. 그리고 해당 범위에 있는 데이터만 영향을 받기 때문에 다른 데이터베이스의 인스턴스가 떠있다면 다른 인스턴스들은 영향을 받지 않는다. 만약에 하나의 데이터베이스 용량 (또는 범위)가 max 를 찍었다면, 다른 인스턴스로 전환해서 계속 데이터를 저장할 수 있다.
- Short_url 을 요청받았을 때 이게 어떤 서버의 데이터베이스에 저장되어있다고 알 수 있을까? 먼저 이 short_url 은 62진수이기 때문에 이를 10진수로 변경하고 zookeeper 를 통해서 이 번위 안에 있는 서버를 알아내고, 마지막으로 그 서버에서 조회를 해보면 된다.
인코딩 방법 3) MD5 Hashing
- Tech 1 과 같은 방법을 사용할 수 있고, MongoDB 대신에 Cassandra 를 사용할수 있다. Cassandra 는 shard key 를 사용하는 대신에 partition key 를 사용할 수 있다.
Tech 4) Key Generation Service
- KGS (Key Generation Service)를 사용하면 7글자의 랜덤한 문자열을 출력하고 이를 key 로 활용하여 key-value database 에 저장할 수 있다. 따라서 short_url 을 생성하고 싶으면 존재하는 generated key 를 활용해서 데이터를 저장하면 된다. 이 방법을 사용하면 URL 을 인코딩 할 필요도 없고, 중복이나 충돌에 대한 문제는 없어진다.
- 이 방법은 concurrency problem 은 없을까? 만약에 서로 다른 서버들이 key 를 동시에 읽는다면 concurrency problem 이 발생하지 않을까?
- 이러한 concurrency problem 을 해결하기 위해서, KGS에서 key 가 사용되면 db 상에 바로 체크가 되고 다시는 사용되지 않는다. 서버들은 read/mark key 를 데이터베이스에서 사용할 수 있다. KGS 는 키를 저장하기 위해서 2개의 테이블을 사용하는데, 하나는 아직 사용하지 않은 키, 다른 하나는 이미 사용한 키를 관리한다.
- 따라서, 특정 키가 사용되면 unused table 에서 used table 로 바로 이동하게 되고, 이는 서버가 unique 한 key 를 갖게되는것을 보장한다. 이는 lock 을 사용하여 여러 서버에서 동일한 키를 가지고 갈 수 있는 것을 방지할 수있다.
- 그리고 이 key 관련된 것은 메모리에 관리되어 빠르게 처리할 수 있도록 한다. 서버에 키를 할당하기 전에 KGS 가 죽게 되면, 그 키들을 사용할 수 없게 되는 문제점이 있다. 즉, single point failure 가 발생할 수 있다. 이를 방지하기 위해서 보조 서버를 추가로 둘 수 있다.
캐싱
- 스토리지를 방문하기 전에 캐시를 거칠 수 있다. 여기서 필요한 캐시 크기는 70GB 였는데, 요즘 서버들은 256 GB 메모리까지 나오기 때문에 하나의 서버면 될 것으로 보인다. 캐시가 꽉 차면, 어떤 정책으로 cache replace 를 할 수 있을까? LRU 가 가장 적합한 것으로 보인다. 가장 오랫동안 참조되지 않은 것이 빠지는 LRU 알고리즘이 적합하다고 볼 수 있다.
로드밸런싱
- 시스템에서 3군데에 로드밸런싱을 적용할 수 있다.
- Client 와 application server
- Appilcation server 와 database server
- Application server 와 cache 서버.
- 로드밸런싱의 가장 기본적인 방법은 Round Robin 방법을 사용한다. 이것은 백엔드 서버에서 들어오는 요청들을 동일하게 분산시키는 방법이다. 예를 들어, 4개의 서버가 있으면 1번 요청은 1번 서버에, 2번 요청은 2번 서버에 할당하는 방식이다. Round Robin 방식의 장점으로는 서버가 죽으면 로드밸런싱은 죽은 서버 쪽으로 트래픽을 보내는 일을 하지 않는다.
- 하지만, Round Robin 방식의 로드밸런싱의 문제점은 서버 부하는 고려하지 않는다는 점이다. 즉, 서버에 얼마나 많은 부하가 몰리지는 고려하지 않고 정해진 순서대로 할당하기 때문에, 이를 해결하기 위해서 특정 서버가 느려지거나 부하가 많이 걸리는지 지속적으로 부하 여부를 체크하고 적절하게 트래픽을 조절하는 로드밸런서를 사용할 필요가 있다.
로드밸런싱의 종류
출처: https://velog.io/@kimjiwonpg98/Nginx-로드밸런싱-개념-및-구축
- 소프트웨어에서의 로드밸런싱은 reverse proxy 를 기반으로 한다. Nginx 의 경우 nginx plus 를 사용해야지 특정 알고리즘 기반의 로드밸런싱 기능을 사용할 수 있다. 그렇지 않으면 기본적으로는 round robin 기반의 로드밸런싱을 사용한다. Nginx config에 round robin을 위해서 사용할 특정 알고리즘을 적어주고, 어떤 서버들을 로드 밸런싱 대상의 서버로 사용할 것인지 nginx config 파일에 지정할 수 있다. 만약에 10개의 서버가 로드밸런서에 의해서 관리되면 10개를 적으면 된다.
- 또다른 로드밸런싱 알고리즘 중
least_conn
은 각 요청을 서버에 할당된 가중치를 고려하여 연결 수가 가장 적은 서버로 전송한다. Least_time
이라는 것은 연결 개수가 최소이면서 평균 응답시간이 가장 적은 것을 선택한다는 알고리즘이다. 단, 이러한 세세한 기능들은 nginx plus 에서만 사용 가능하다. Ip_hash
라는 알고리즘은 클라이언트 IP 주소로 해싱을 하고, 한번 요청 받은 서버가 있을 때 해당 서버에만 요청을 분배해주는 역할을 한다.