4. instagram // Flickr // Picasa

1. instagram 이란?

• 사용자가 자신의 사진과 동영상을 업로드하고 다른 사용자와 공유할 수 있는 소셜 네트워크

 

2. 시스템 요구 사항

• 사용자는 사진을 업로드 / 다운로드 / 볼 수 있어야 한다
• 사용자는 사진 / 비디오 제목을 기반으로 검색을 수행 할 수 있다
• 사용자는 다른 사용자를 팔로우 할 수 있다
• 시스템은 사용자가 팔로우하는 모든 사람들의 인기 사진으로 구성된 사용자의 뉴스 피드를 생성하고 표시해야 한다

 

3. 디자인 고려사항

• 사용자는 원하는 만큼 사진을 업로드 할 수 있다. 따라서 스토리지의 효율적인 관리가 중요하다
• 데이터는 100 % 신뢰할 수 있어야 한다. 사용자가 사진을 업로드하면 시스템은 사진이 손실되지 않도록 보장해야 한다

 

4. 용량 추정

• 총 사용자가 5억 명이고 일일 활성 사용자가 1백만 명이라고 가정
• 매일 2 백만장의 새로운 사진 == 초당 23 장의 새로운 사진 2000000/(606024) == 23.411
• 평균 사진 파일 크기는 200KB로 한다.
• 1일 사진 저장에 필요한 총 공간 2000000 * 200KB ~= 400GB
• 10년 동안의 총 공간 400GB * 365 * 10 ~= 1425TB

 

5. 대략적인 시스템 설계

두 가지 시나리오를 지원해야 한다.

1. 사진을 업로드
2. 사진을 보거나 검색하는 것

서비스는 사진을 저장하기 위한 스토리지 서버와 사진에 대한 메타 데이터 정보를 저장하기 위한 데이터베이스가 필요하다

6. 데이터 베이스 스키마

사용자, 업로드 한 사진 및 팔로우하는 사람들에 대한 데이터를 저장해야 한다.

Photo 테이블은 사진과 관련된 모든 데이터를 저장한다. 최근 사진을 먼저 가져와야 하므로 (PhotoID, CreationDate)에 대한 인덱스가 필요하다

위의 스키마를 저장하는 간단한 방법은 조인이 필요하므로 MySQL과 같은 RDBMS를 사용한다.

 

대략적인 테이블 관계도

그러나 관계형 데이터베이스에는 특히 확장 시 문제가 발생한다.

위의 스키마를 NoSQL key-value에 저장하여 NoSQL의 확장에 대한 이점을 누릴 수 있다.

NoSQL 데이터베이스를 사용하는 경우 누가 어떤 사진을 소유하고 있는지 알기 위해 사용자와 사진 간의 관계를 저장할 추가 테이블이 필요하다. (조인을 할 수 없으므로, 하나의 도큐먼트에 한꺼번에 저장해야 한다.)

 

 

7. 데이터 크기 추정

각 테이블에 들어갈 데이터 양과 10 년 동안 필요한 총 스토리지 양을 추정

 

user 테이블 :

User ID (4 바이트)

name (20 바이트)

email (32 바이트)

DateOfBirth (4 바이트)

CreationDate (4 바이트)

LastLogin (4 바이트)

 

총 68 바이트

5억 명의 사용자가 있는 경우 총 저장 용량 32GB가 필요하다.

5 억 * 68 ~= 32GB

 

 

photo 테이블:

PhotoID (4 바이트)

UserID (4 바이트)

PhotoPath (256 바이트)

PhotoLatitude (4 바이트)

PhotoLongitude (4 바이트)

UserLatitude (4 바이트)

UserLongitude (4 바이트)

CreationDate (4 바이트)

 

총 284 바이트

매일 2 백만 장의 새 사진이 업로드되는 경우 하루 동안 0.5GB의 저장 용량.

2M * 284 바이트 ~ = 0.5GB / 일

10 년 동안 1.88TB의 스토리지가 필요.

 

UserFollow 테이블:

UserFollow 테이블의 각 행은 8 바이트로 구성. 5억 명의 사용자가 있고 평균적으로 각 사용자는 500 명의 사용자를 팔로우로 가정. UserFollow 테이블을 위해 1.82TB의 스토리지가 필요하다.

5 억 명의 사용자 * 500 명의 팔로워 * 8 바이트 ~ = 1.82TB

10 년 동안 모든 테이블에 필요한 총 공간은 3.7TB

32GB + 1.88TB + 1.82TB ~ = 3.7TB

 

 

 

8. 구성 요소 디자인

사진 업로드는 디스크로 이동해야 하므로 속도가 느릴 수 있지만 읽기는 특히 캐시가 제공된다면 빠르게 할 수 있다.

시스템을 설계하기 전에 웹 서버에 연결 제한이 있음을 명심해야 한다. 웹 서버가 언제든지 최대 500 개의 연결을 가질 수 있다고 가정하면 동시 업로드 또는 읽기가 500개를 초과할 수 없다. 이 병목 현상을 처리하기 위해 읽기와 쓰기를 별도의 서비스로 분할 할 수 있다. 업로드가 시스템을 방해하지 않도록 읽기 전용 서버와 쓰기용 서버를 다르게 설계해야 한다.

사진의 읽기 및 쓰기 요청을 분리하면 이러한 각 작업을 독립적으로 확장하고 최적화 할 수 있다.

 

 

9. 데이터 저장 서버 샤딩

A. UserID를 기준으로 분할한다고 가정.

하나의 DB 샤드가 1TB인 경우 3.7TB의 데이터를 저장하려면 4개의 샤드가 필요 더 나은 성능과 확장성을 위해 10 개의 샤드를 유지한다고 가정

따라서 UserID % 10으로 샤드 번호를 찾은 해당 디비에 데이터를 저장. 시스템에서 모든 사진을 고유하게 식별하기 위해 각 PhotoID와 함께 샤드 번호를 추가

각 DB 샤드는 PhotoID에 대한 자체 자동 증가 시퀀스를 가질 수 있으며 각 PhotoID와 함께 ShardID를 추가하므로 시스템 전체에서 고유하게 만들 수 있다

해당 파티션의 문제점은?

1. 많은 팔로우를 가진 사용자를 어떻게 처리해야 하는가? 유저는 인기 있는 사용자를 팔로우하고 다른 많은 사람들은 인기 있는 사용자가 업로드 한 사진을 봐야 한다.
2. 일부 사용자는 다른 사용자에 비해 많은 사진을 보유하므로 저장 공간이 균일하지 않게 배포된다.
3. 하나의 샤드에 사용자의 모든 사진을 저장할 수 없으면 어떻게 될까? 
   사용자의 사진을 여러 샤드에 배포하면 지연 시간이 증가하는가?
4. 사용자의 모든 사진을 하나의 샤드에 저장하면 해당 샤드가 다운된 경우 모든 사용자 데이터를 사용할 수 없거나 높은 로드를 제공하는 경우 지연 시간이 길어지는 등의 문제가 발생할 수 있다.

 

B. PhotoID를 기반으로 분할하기

먼저 고유 한 PhotoID를 생성 한 다음 "PhotoID % 10"을 통해 shard 번호를 찾을 수 있다면 위의 문제는 해결될 것이다. (n%10은 무조건 10으로 떨어지기 때문에 서버 구성이 쉬워진다) 이 경우 PhotoID는 시스템 전체에서 고유하므로 ShardID에 PhotoID를 추가할 필요가 없다.

 

PhotoID를 어떻게 생성 할 수 있는가?

여기서는 PhotoID가 저장될 샤드를 찾기 위해 먼저 PhotoID를 알아야 하기 때문에 각 샤드에 자동 증가 시퀀스를 가질 수 없다. 한 가지 해결책은 자동 증가 ID를 생성하기 위해 별도의 데이터베이스 인스턴스를 사용하는 것. PhotoID가 64 비트에 맞으면 64 비트 ID 필드만 포함하는 테이블을 정의 할 수 있다. 따라서 시스템에 사진을 추가하고 싶을 때마다 이 테이블에 새 행을 삽입하고 해당 ID를 새 사진의 PhotoID로 사용할 수 있다.

 

키를 생성하는 DB가 단일 실패 지점이 아닐까?

YES,  이에 대한 해결 방법은 두 개의 데이터베이스를 정의하는 것입니다. 하나는 짝수 번호의 ID를 생성하고 다른 하나는 홀수 번호를 생성합니다.

이 두 데이터베이스 앞에로드 밸런서를 배치하여 두 데이터베이스 간에 라운드 로빈하고 다운 타임을 처리 할 수 있다. 이 두 서버는 동기화되지 않아 한 서버가 다른 서버보다 더 많은 키를 생성 할 수 있지만 이로 인해 시스템에 문제가 발생하지 않는다.

 

10. 순위 및 뉴스 피드 생성

특정 사용자에 대한 뉴스 피드를 만들려면 사용자가 팔로우하는 사람들의 최신의 가장 인기 있고 관련성 있는 사진을 가져와야 한다.

간단하게 사용자의 뉴스 피드에 대한 상위 100장의 사진을 가져와야 한다고 가정한다면,

1. 애플리케이션 서버는 먼저 사용자가 팔로우하는 사람 목록을 가져온 다음
2. 각 사용자의 최근 100장의 사진에 대한 메타 데이터 정보를 가져온다.
3. 서버는 이러한 모든 사진을 순위 알고리즘에 제출하여 상위 100개의 사진 (최신, 유사성 등을 기준으로)을 결정하고 사용자에게 리턴한다.

이 접근 방식의 가능한 문제는 여러 테이블을 쿼리하고 결과에 대해 정렬/병합/순위를 지정해야 하므로 지연 시간이 길다. 효율성을 높이기 위해 뉴스 피드를 미리 생성하여 별도의 테이블에 저장할 수 있다

 

뉴스피드 사전 생성 : 사용자의 뉴스피드를 지속적으로 생성하여 'UserNewsFeed'테이블에 저장하는 전용 서버를 가질 수 있다. 따라서 사용자가 뉴스피드에 대한 최신 사진이 필요할 때마다 이 테이블을 쿼리하고 결과를 사용자에게 반환한다.

이러한 서버가 사용자의 뉴스 피드를 생성해야 할 때마다 먼저 UserNewsFeed 테이블을 쿼리를 수행하여 해당 사용자에 대한 뉴스 피드가 마지막으로 생성된 시간을 찾는다. 그런 다음 위에서 언급 한 단계에 따라 그 시간부터 새로운 뉴스 피드 데이터가 생성된다.

 

사용자에게 뉴스 피드 콘텐츠를 보내는 방법에는 어떤 것이 있습니까?

1. pull: 클라이언트는 정기적으로 또는 필요할 때마다 수동으로 서버에서 뉴스 피드 콘텐츠를 가져올 수 있다. 이 접근 방식의 가능한 문제는 다음과 같습니다.

a) 클라이언트가 pull 요청을 실행할 때까지 새 데이터가 사용자에게 표시되지 않을 수 있다.

b) 대부분의 경우 새 데이터가 없으면 pull 요청이 빈 응답을 생성한다.

 

2. push : 서버는 새로운 데이터가 사용 가능 할 때 즉시 사용자에게 푸시 할 수 있다. 이를 효율적으로 관리하기 위해 사용자는 업데이트 수신을 위해 서버에 Long Poll 요청을 유지해야 한다. 이 접근 방식의 가능한 문제는 많은 사람을 팔로우하는 사용자 또는 수백만 명의 팔로워를 보유한 유명인 사용자이다. 이 경우 서버는 업데이트를 매우 자주 푸시해야 합니다.

 

3. 하이브리드 : 하이브리드 접근 방식을 채택 할 수 있습니다. 팔로어 수가 많은 모든 사용자를 pull 기반 모델을 사용하고 수백 (또는 수천) 팔로어를 가진 사용자에게만 데이터를 푸시 할 수 있다. 또 다른 접근 방식은 서버가 특정 빈도 이하로 모든 사용자에게 업데이트를 푸시하고 팔로워/업데이트가 많은 사용자가 정기적으로 데이터를 가져올 수 있도록 하는 것이다.

 

 

11. 뉴스 피드 생성

특정 사용자에 대한 뉴스 피드를 생성하기 위한 가장 중요한 요구 사항 중 하나는 사용자가 팔로우하는 모든 사람들로부터 최신 사진을 가져오는 것이다.  이를 위해 사진이 생성된 시점에 사진을 분류하는 메커니즘이 필요하다. 이를 효율적으로 수행하기 위해 사진 생성 시간을 PhotoID의 일부로 만들 수 있다. PhotoID에 대한 기본 색인이 있으므로 최신 PhotoID를 빠르게 찾을 수 있다.

이를 위해 epoch(유닉스) 시간을 사용할 수 있다. PhotoID에 두 부분이 있다고 가정해 본다.

첫 번째 부분은 epoch 시간을 나타내고 두 번째 부분은 자동 증가 시퀀스로 한다. 따라서 새 PhotoID를 만들기 위해 현재 epoch 시간을 가져와서 키 생성 DB에서 자동 증가 ID를 추가 할 수 있다. 이 PhotoID (PhotoID % 10)에서 샤드 번호를 알아내고 사진을 저장할 수 있다.

 

PhotoID의 크기는?

향후 50년 동안 초 수를 저장하는 데 얼마나 많은 비트가 필요할까?

86400 초 / 일 * 365 (1 년에 일) * 50 (년) => 16억 초

이 숫자를 저장하려면 31 비트가 필요. 평균적으로 초당 23장의 새 사진을 예상하므로 자동 증가 시퀀스를 저장하기 위해 9비트를 추가로 할당 할 수 있다

 

 

12. 캐시 및 부하 분산

서비스는 전 세계에 분산된 사용자에게 서비스를 제공하기 위해 대규모 사진 전송 시스템이 필요. 우리의 서비스는 지리적으로 분산 된 수많은 사진 캐시 서버를 사용하여 콘텐츠를 사용자에게 더 가깝게 푸시하고 CDN을 사용해야 한다

데이터베이스 데이터를 캐시 하기 위해 메타 데이터 서버용 캐시를 도입 할 수 있다. Memcache를 사용하여 데이터를 캐시 할 수 있으며 데이터베이스에 도달하기 전에 애플리케이션 서버는 캐시에 원하는 행이 있는지 신속하게 확인할 수 있다. LRU (Least Recent Used)는 시스템에 대해 합리적인 캐시 제거 정책이 된다.

 

 

 

 

 

참고

https://techtakshila.com/system-design-interview/chapter-4/

https://www.youtube.com/watch?v=da7mdMz0g0g&ab_channel=TechTakshila