2. pastebin ( text storage site )

페이스트빈?

텍스트 쉐어링 웹사이트

사용자가 플레인 텍스트를 저장할 수 있는 웹 애플리케이션을 의미한다. 깃허브는 버전 관리 기능을 가진 페이스트빈 서비스를 제공한다. 한마디로 텍스트 공유 플랫폼

예제 사이트 : https://pastebin.com/

 

 

1. 기능 요구 사항

• 사용자는 텍스트를 입력하거나 텍스트 파일을 업로드하고 고유한 short URL을 얻을 수 있다.
• 만료 시간이 제공되면 URL은 일정 기간이 지나면 만료된다.
• short URL이 주어지면 사용자는 원본 콘텐츠에 액세스 할 수 있어야 한다.
• 서비스는 REST API로 통신할 수 있어야 한다.
• 텍스트 최대 사이즈는 1MB로 제한한다.
• 읽기 요청이 쓰기 요청보다 100배 더 많다!! (읽기:쓰기 == 100:1)

 

 

2. 추정 및 제약사항

한달에 1 억 개의 새 요청을 읽기: 쓰기 == 100:1 비율로 수신한다고 가정한다면

총 읽기 요청 수 :

100 * 100M = 10000M 또는 10B

총 쓰기 요청 수 :

1 * 100M = 100M

10년 동안 총 쓰기 요청 건수

100M * 12 (월) * 10 (년) = 12B 쓰기 요청

쓰기 텍스트의 최대 크기를 10MB라 한다면

매월 데이터 크기 =  100M(쓰기) * 1MB =  100TB / 월 or 0.1PB / 월

연간 데이터 크기 = 0.1PB * 12 = 1.2PB  / 년

10 년 전체 데이터 = 1.2PB * 10 = 12 PB  (1.2조)

 

 

3. 서버 및 API 설계

읽기와 쓰기의 요청이 100: 1이기 때문에 해당 요청에 처리를 위한 서버를 분리해야 한다.

API 설계

create_paste ( api_key, text, 만료 날짜 )

method :  post

파라미터

• api_key : 사용자에 제공되는 고유한 API 키
• text : 사용자가 붙여넣고 자하는 실제 콘텐츠
• 만료 날짜 : 콘텐츠가 만료되어야 하는 시간입니다. 예 : 주, 월, 연도

return  : short_url

 

read_paste ( short_url )

method :  get

파라미터

• short_url : 콘텐츠에 액세스하기 위해 create_paste 메서드에서 제공하는 URL

return  : 원본 콘텐츠 or URL이 잘못된 경우 오류 코드

 

 

 

4. 단축 URL 생성 알고리즘

사용자가 텍스트를 추가 했을때 (쓰기 요청) 고유한 short URL을 반환해야 한다.

 

4.1 URL 인코딩

인코딩은 Base36 (허용되는 문자 [az] [0-9]) 또는 Base62 (허용되는 문자 [AZ] [az] [0-9]) 또는  Base64 (허용되는 문자 [AZ] [az] [0 -9], '+', '/'). Base64의 모든 문자는 URL에서 사용 가능한 문자이므로 인코딩 기술로 Base64를 선택한다.

URL 길이 계산 – Base64 인코딩 사용일 경우

 

길이가 6 인 URL은 64 ^ 6 = ~ 68.7억개의 URL을 제공
길이가 7 인 URL은 64 ^ 7 = ~ 4.3조개의  URL을 제공
길이가 8 인 URL은 64 ^ 8 = ~ 281조 개의 URL을 제공

 

이미 12B(1.2조) URL을 저장할 것으로 예상했으므로 짧은 URL을 7자 길이로 안전하게 선택할 수 있습니다.

이제 고유 한 단축 URL을 생성하기 위해 붙여 넣은 콘텐츠의 MD5 해시와 사용자 IP 주소를 계산하여 128 비트 해시 값을 생성할 수 있다. 이제 MD5 결과를 Base64  인코딩으로 인코딩하면 결과 문자열의 길이는 22 자이다.

알고리즘의 문제 : 이 방법을 사용하여 생성 된 URL은 반복될 수 있다.

이 문제를 극복하기 위해 KGS 또는 키 생성 서비스를 사용한다.

 

4.2 키 생성 서비스(KGS)

키 생성 서비스 (KGS) 는 미리 임의의 7자 문자열을 생성하여 데이터베이스에 저장한다. 짧은 URL을 원할 때마다 이미 생성된 키 중 하나를 사용하여 사용한다. URL을 인코딩하지 않을 뿐만 아니라 중복이나 충돌에 대해 걱정할 필요가 없습니다. KGS는 key-DB에 삽입된 모든 키가 고유한지 확인한다.

자세한 사항은 tinyURL을 참조한다.

 

 

5. 스토리지

여기에 실제 텍스트 기반 콘텐츠 (붙여 넣기)를 저장하고 있으므로 각 붙여 넣기 크기에 대한 제한은 1MB이다. 위에서 계산 한 것처럼 서비스가 10 년 동안 실행되면 결국 12PB의 데이터가 누적되어 데이터베이스에 저장하기에는 너무 많은 양이다.

따라서 우리는 AWS S3 와 같은 Object Storage 서비스를 사용하여 테스트를 파일 형태로 저장한다.

콘텐츠는 S3 버킷에 저장하고 저장된 파일의 paste-path(file URL)를 데이터베이스에 저장한다.

 

6. 테이블 디자인

user 테이블

1. ID (pk) : 사용자를 전역 적으로 구별할 수 있도록 하는 고유 한 사용자 ID 또는 API 키
2. name **:**사용자의 이름입니다.
3. password **:**로그인 기능을 사용하기위한 사용자의 비밀번호
4. created date**:** 사용자가 등록 된 날짜입니다.

paste 테이블

1. short URL : 7 자 길이의 고유 한 짧은 URL입니다.
2. paste path**:** 원본 콘텐츠(텍스트)가 저장되는 S3 버킷의 경로
3. expiration date**: short** URL이 무효화되어야 하는 날짜
4. last accessed : 마지막으로 액세스 한 시간입니다. (분석 목적)
5. UserId : 단축 URL을 만든 사용자의 고유 한 사용자 ID

데이터베이스에는

1) 관계형 데이터베이스 (MySQL/postgresql)

2) NoSQL 데이터베이스 ( Cassandra )

두 가지 데이터베이스가 있다.

 

일반적으로 관계형 데이터베이스는 조인과 관련된 복잡한 쿼리가 많으면 좋지만 속도가 느려진다. NoSQL 데이터베이스는 관계형 쿼리를 처리하는데 느리지만 전체 정보를 가져오는 것은 더 빠르다.

해당 서비스는 데이터간에 많은 관계가 필요하지는 않지만 빠른 읽기 및 쓰기 속도가 필요하다. 따라서 우리는 NoSQL 데이터베이스를 선택해야한다. (테이블 간의 조인이 많지 않으므로)

각 행의 키는 전역 적으로 고유하므로 short URL이 될 수 있다.

6.1 데이터베이스 샤딩

데이터베이스를 확장하려면 수십억 개의 URL에 대한 정보를 저장할 수 있도록 데이터베이스를 여러 머신 또는 노드로 분할해야 한다. 따라서 더 많은 머신이나 노드로 인해 더 많은 데이터를 메모리에 저장할 수 있다. 데이터베이스 샤딩의 경우 일관된 해싱 기술을 사용한다

이 기술에서는 저장하려는 단축 URL의 해시를 찾고 일관된 해싱을 사용하여 특정 URL을 저장할 시스템 / 샤드를 결정한다. 

해시 함수는 균일하게 다른 파티션 또는 샤드로 배포한다. 우리가 만들 샤드의 수를 결정한 다음 파티션 / 샤드 번호를 나타내는 임의의 숫자가 적절한 해시 함수를 선택할 수 있다.

 

 

위의 서비스를 그림으로 정의한다면 아래와 같다.

 

 

7. 읽기 작업 속도 향상 (캐싱)

해당 서비스는 테이터가 insert보다 select 가 많을 것이다. 지금까지 쓰기 프로세스의 속도를 높이는 방법을 찾았지만 읽기 속도는 여전히 느리다. 이러한 읽기 과정의 속도를 높일 수 있는 캐싱으로 해결할 수 있다.

Memcached와 같은 캐싱 서비스를 통해 사용자가 자주 액세스 할 URL을 캐시 한다.

 

캐싱을 추가한 후 고려해야 할 사항 :

1. 캐시가 가득 차면 캐시에 있는 URL 삭제해야 한다. 이를 위해 LRU (Least Recent Used) 정책을 사용한다. 가장 적게 참조된 캐시의 URL이 제거된다.
2. 캐시를 원본 콘텐츠와 동기화한다. 사용자가 원본 붙여 넣기 콘텐츠를 업데이트하거나 삭제하면 해당 변경 사항도 캐시에 반영되어야 한다 ( 위의 조건사항에서는 삭제 및 업데이트는 없다 )
3. 캐시도 파티션 할 수 있다. 이것은 우리가 더 많은 서버 분할로 메모리에 더 많은 데이터를 저장하는 데 도움이 될 것입니다. "일관된 해싱"을 사용하여 수행할 수 있는 샤드로 이동할 작업을 결정한다

이제 이것이 우리가 읽기 및 쓰기 요청의 속도를 높이는 방법이지만 여전히 우리 시스템은 네트워크 대역폭 병목 현상과 단일 실패 지점에 취약하다

 

8. 로드 밸런싱

제한된 네트워크 대역폭 및 단일 장애 지점 문제를 극복하기 위해 Load Balancer를 사용한다. Load Balancer는 서버 그룹 간의 트래픽을 웹 사이트 또는 애플리케이션의 응답 및 가용성을 향상한다.

서버 간에 부하를 분산하기 위해 최소 대역폭 방법을 사용한다. 이 알고리즘은 현재 초당 메가비트 (Mbps)로 측정되는 가장 적은 양의 트래픽을 제공하는 서버를 선택한다

로드 밸런서를 다음 사이에 배치할 수 있다.

1. 클라이언트와 서버.
2. 서버와 데이터베이스.
3. 웹 서버 및 키 생성 서비스.

 

 

 

참고

https://www.youtube.com/watch?v=josjRSBqEBI&ab_channel=TechDummiesNarendraL

https://www.youtube.com/watch?v=j1CZ5vSU3CQ&ab_channel=CodingSimplified

https://tannishk.medium.com/designing-pastebin-9960adc3432d

https://medium.com/@eunpyolee0420/system-design-study-designing-pastebin-1a39014da812

https://www.enjoyalgorithms.com/blog/design-pastebin-system-design-interview-question

https://learnsystemdesign.blogspot.com/p/design-pastebin.html

https://nerohoop.gitbooks.io/system-design/content/design-pastebin.html

https://nlogn.in/designing-pastebin-service-system-design-nlogn/