Designing Instagram

1. 인스타그램이 뭔가요?

인스타그램은 유저들이 사진과 비디오를 올리고 다른 유저들과 공유 할 수 있는 소셜 네트워킹 서비스 이다. 인스타그램 유저들은 정보를 공개/비공개 설정을 할 수 있다. 퍼블릭 으로 공유된 모든것들은 다른 유저에게 보여질 수 있고, private 하게 공유된 컨텐츠는 특정 사람들만 볼 수 있다. 인스타그램은 Facebook, Twitter, Flickr, Tumblr와 같은 다른 sns와 공유하기가 가능하다.

2. 시스템 요구사항

우리는 인스타그램 디자인을 하기위해 다음과 같은 요구사항을 충족시켜야 한다.

Functional Requirements

1. 사용자는 사진을 업로드/다운로드 하고 볼 수 있어야 한다.
2. 사용자는 사진/비디오 제목을 검색할 수 있어야 한다.
3. 사용자는 다른 사용자를 follow 할 수 있어야 한다.
4. 시스템은 사용자의 News Feed를 생성 하여 follower 들의 사진의 최 상단에 보여줘야 한다.

Non-functional Requirements

1. 우리 서비스는 고가용성이어야 한다.
2. News Feed 는 최대 200ms안에 생성 되어야 한다.
3. Consistency can take a hit (in the interest of availability) if a user doesn’t see a photo for a while; it should be fine.(?)
4. 시스템은 매우 안정적이어야 한다. 업로드 된 사진, 영상은 절대 없어지면 안됨.

Not in scope: 사진에 태그 달기, 태그로 검색, 사진에 커멘트 달기, 사진에 사용자 태그, 누구를 follow 할지?

3. 디자인 시 고려사항

이 시스템은 read-heavy 한 시스템이기 때문에, 우리는 사진을 빠르게 검색하는 데 초점을 맞출 것이다.

1. 사용자는 그들이 좋아하는 사진을 많이 올릴 수 있다. 그러므로, 이 시스템을 디자인 할 떈 스토리지를 효과적으로 관리하는 것이 중요하다.
2. 사진을 보고 있는 동안엔 low latency가 보장 되어야 한다.(?)
3. 데이터는 100% 안전해야 한다. 만약 사용자가 사진을 올리면, 시스템은 절대로 사진이 유실될 일이 없다는 것을 보장 해야 한다.

4. 용량 추정과 제약조건

• 500M의 total user가 있다고 가정. dau는 1M
• 2M의 새로운 사진이 매일 업로드 된다. 1초에 23개
• 사진 파일의 평균 사이즈 : 200kb
• 하루 업로드 되는 사진을 위해 필요한 공간 : 2M * 200KB = 400GB
• 10년간 필요한 용량 : 400GB * 365(days a year) * 10 (years) ~= 1425 TB

5. High Level System Design

High-level design을 할 때 우리는 두 가지 시나리오에 대해 살펴봐야 한다. 첫 번째는 사진을 업로드 하는 것, 두 번째는 사진을 검색/보는 것 이다. 우리 서비스는 사진을 저장하기 위해 object storage가 필요하고, 사진에 대한 메타데이터를 저장하기 위한 데이터베이스 서버가 필요 하다.

6. DB 스키마

디비 스키마를 인터뷰 초반에 정의 하는 것은 다양한 구성요소(component) 간의 데이터 flow를 이해하는 데 도움이 되고, 나중에 데이터 파티셔닝으로 안내된다.(?)

우리는 사용자, 그들이 업로드 한 사진, 그들이 팔로우 하는 사용자 정보를 저장 해야 한다. Photo 테이블은 사진과 관련딘 모든 데이터를 저장할 것이고, 최근사진을 먼저 불러오기 위해 PhotoId, CreationDate 에 인덱스를 걸어줄 필요가 있다.

가장 단순한 접근은 MySQL 같은 RDBMS를 사용하는 것이다. Join을 해야 하기 떄문에. 그러나 관계형 데이터베이스는 스케일 아웃을 하기가 힘들다. 자세한 사항은 SQL vs. NoSQL(돈내야되네...) 을 보라.

우리는 사진을 HDFS나 S3 같은 분산 파일 시스템에 저장 할 수 있다.

우리는 위의 스키마를 분산 key-value 저장해 NoSQL의 장점을 누릴 수도 있다. 사진에 관련된 모든 메타데이터는 PhotoID 를 key로 가지고 있는 테이블로 가면 될 것이고, value로는 PhotoLocation, UserLocation, CreationTimestamp 등이 있다.

NoSQL 저장소는 일반적으로 안정성을 위해 몇개의 replicas를 더 운영 한다. 또한, NoSQL저장소는 삭제가 즉시 반영 되지 않는다. 데이터는 삭제 되기 전에 정해진 며칠 간 보관된다.

7. Data Size 추정

각각의 테이블은 어느 정도의 저장하게 될 것인가, 10년동안 보유 하면 어느 정도의 크기가 될까 알아보면

Users: int와 dateTime이 4byte, 'User' 테이블은 각 row가 68bytes가 될것이다.

• UserID (4 bytes) + Name (20 bytes) + Email (32 bytes) + DateOfBirth (4 bytes) + CreationDate (4 bytes) + LastLogin (4 bytes) = 68 bytes

만약 우리가 5억 유저가 있다면 우리는 32GB가 필요하다.

• 500 million * 68 ~= 32GB

Photo: Photo 테이블의 각 row는 284bytes가 될것이다.

• PhotoID (4 bytes) + UserID (4 bytes) + PhotoPath (256 bytes) + PhotoLatitude (4 bytes) + PhotoLongitude(4 bytes) + UserLatitude (4 bytes) + UserLongitude (4 bytes) + CreationDate (4 bytes) = 284 bytes

만약 매일 2M개의 새 사진이 업로드 된다면, 우리는 하루에 추가적으로 0.5GB가 필요하게 된다.

• 2M x 284 bytes ~= 0.5GB per day

10년 동안 쌓는 다면 1.88TB의 용량이 필요하다.

UserFollow: 각 row는 8byte로 구성 되어 있다. 만약 우리의 유저 수가 5억명 이고 각각 어림잡아 500명을 팔로우 한다고 가정 하면, 우리는 1.82TB의 테이블이 필요하다.

• 500 million users * 500 followers * 8 bytes ~= 1.82TB

총 용량은 3.7TB의 용량이 필요하다.

8. Component Design

사진 업로드(혹은 쓰기)는 디스크에 저장된다면 느릴 수 있다. 반면, 읽기는 빠를 텐데, 특히 캐싱되어 있다면 더 빨라진다.

업로드 하는 유저는 가능한 모든 연결을 업로드 할 떄 쓸 수 있다. 업로드는 느리기 때문이다. 이는 서버가 'write' 요청으로 바쁠 땐 'read'요청은 처리할 수 없다는 얘기다. 우리는 우리의 시스템을 디자인 하기 전에 웹서버는 가질 수 있는 connection의 제한이 있다는 것을 알고 있어야 한다. 만약 우리의 서버가 언제나 최대 500개의 connection을 가질 수 있다고 가정 한다면, 우리는 upload / read 요청을 동시에 최대 500개 까지 밖에 맺지 못한다. 이 bottleneck을 처리하기 위하여 우리는 read / write를 각기 다른 서버로 분리 할 수 있다. 이렇게 분리된 '전용 서버'를 둠으로서 업로드가 시스템을 hog(?) 하지 않도록 할 수 있다.

9. 안정성 및 이중화

우리 서비스는 사진데이터를 잃어버리면 안된다. 그러므로 우리는 각 파일을 복사 저장 하여 한 서버가 죽을 때를 대비 한다. 다른 스토리지 서버에 있는 다른 복사본에서 사진을 검색할 수 있다.

시스템의 다른 컴포넌트에도 이와 동일한 principle이 적용된다. 우리가 고가용성을 원한다면 여러개의 복사본을 운영해 몇몇 서버가 죽더라도 서비스가 가능하도록 해야 한다. 이중화는 시스템의 SPOF을 제거한다.

만약 한개의 서버 인스턴스만 필요하다고 해도 우리는 트래픽을 받지 않는 카피본이 필요하다. 만약 원본에 fail over가 발생 하면 자동/수동 으로 교체되도록 해야 한다.

10. 데이터 샤딩

메타데이터의 샤딩에 두가지 다른 스키마를 보자.

UserID로 파티셔닝 하기

UserID로 샤딩한다고 가정 해보자. 우리는 특정 유저의 모든 사진을 한 샤드에 담아놓게 된다. 한 DB의 샤드가 1TB라면 3.7TB를 저장하기 위해선 4개의 샤드가 필요한데, 더 나은 성능과 확장성을 위해 10개의 샤드를 보유하고 있다고 가정해보자.

그렇다면 UserID % 10 으로 샤드 넘버를 정하고 저장하는건 어떨까. 우리 시스템에 있는 모든 사진을 unique하게 식별하기 위해서, photoID에 샤드 넘버를 붙일 수 있다.

PhotoID를 어떻게 생성할 것인가?

각DB 샤드는 PhotoID에 대하여 샤드만의 auto-increment 시퀀스를 가지고 있다. 그리고 거기에 우리는 샤드ID를 뒤에 붙였기 때문에, PhotoID는 전체 시스템에 걸쳐 유니크하게 된다.

이런 식으로 파티셔닝 할 경우 발생할 수 있는 문제점은?

1. 핫유저는 어떻게 대응할 것인가? 많은 유저들이 이 '핫 유저'를 팔로우 할 것이고, '핫 유저'가 업로드 한 사진을 볼것이다.
2. 몇몇 유저는 다른 유저랑 비교해서 많은 사진을 업로드 할 수 있다. 그래서 분산되지 않고 한곳으로 쏠릴 수 있음.
3. 한 유저의 사진을 한 샤드에 모두 저장 하지 못하는 경우는 어떻게 대처해야 할까?
4. 한 유저의 모든 사진을 한 샤드에 저장한다면 그 샤드가 다운되거나 지연이 발생할 경우 다른 모든 유저가 서비스를 이용 못하는 상황이 발생할 수도 있다.

Partitioning based on PhotoID

우리가 Unique한 PhotoID를 생성할 수 있고, 'PhotoID % 10'으로 샤드 넘버를 찾는다면 위에 적은 문제점들은 해결할 수 있다. PhotoId는 전체 시스템에서 unique 하기 때문에 PhotoID에 shard number를 붙일 필요가 없다.

PhotoID를 어떻게 생성할 것인가?

우리는 샤드에서 auto-increment로 사진의 id를 만들기 전에 사진이 어느 샤드에 저장될 것인가를 알아야 하기 떄문에 샤드에서 auto-increment로 id를 결정하는 방법은 사용할 수 없다. 하나의 대안으로는, auto-increment id만 생성 하는 전용 database instance를 생각해볼 수 있다. 만약 PhotoID가 64bit에 딱 들어간다면, 우리는 테이블에 64Bit 짜리 id 컬럼을 생성할 수 있다. 그래서 이 시스템에 사진을 저장할 땐 언제나 이 테이블에 한개의 row를 추가하고 그 id를 업로드 한 사진의 PhotoID로 삼으면 된다.

key generating DB가 SPOF가 되진 않을까? 충분히 그럴 수 있다. 이를 해결할 수 있는 방법으로, 2개의 database를 사용하는 방법이 있다. 하나는 홀수 id를 생성하고, 다른 하나는 짝수 id를 생성하는 것이다. 우리는 이 두개의 디비 앞에 로드밸런서를 두고, round-robin 방식으로 연결되게 함으로서 downtime에 대응할 수 있다. 두 서버 중 한대가 다른 한대 보다 키를 더 생성해서 sync가 안맞을 수 있는데, 이것은 우리 시스템에 아무 문제가 되지 않는다. 우리는 이러한 디자인을 Users, Photo-Comments 등 우리 시스템의 여러 군데에 적용할 수 있다.

또는 tiny url 같은 URL 단축 서비스 설계에서 논의한 것과 유사하게 key generating scheme를 구현할 수 있다.

미래에 시스템이 확장될 것은 어떻게 대비 할까? 많은 logical partition을 만든다면 데이터의 증가를 대비할 수 있다. 단일 물리 서버에 logical partition을 둘 수 있다. 각각의 데이터 서버는 그 위에 여러개의 데이터베이스 인스턴스를 돌릴 수 있기 떄문에 우리는 logical partition을 위한 데이터베이스를 서버 어디에서나 돌릴 수 있다. 그렇기 떄문에 특정 데이터베이스 서버가 데이터가 많다고 느껴지면 우리는 로지컬 파티션에 저장된 데이터를 다른 서버에 마이그레이션 하면 된다. 우리는 동일한 config file을 사용해서 logical partition을 데이터베이스 서버에 매핑할 수 있기 때문에 파티션을 옮기는 것을 쉽게 해준다.

11. 랭킹과 뉴스 피드 생성

특정 사용자의(any given user)의 뉴스 피드를 생성하기 위해선 사용자가 팔로우 하는 사람들의 최신, 인기있고, 관련 있는 사진들을 가져와야 한다.

간단하게, 특정 유저의 뉴스 피드를 위해 100개의 사진을 가져와야 한다고 가정해보자. 우리의 서버는 특정 유저가 팔로우 하는 다른 유저의 목록을 가져오고 나서 그 유저들의 최신 100개 사진의 메타데이터를 가져올 것이다. 마지막으로, 우리 시스템은 이 100개의 사진을 랭킹 알고리즘으로 소팅할 것이다. 이 접근법에서 발생할 수 있을 만한 문제점은 여러 개의 테이블을 쿼리하고 소팅/머징/랭킹 작업을 해서 결과물을 뽀아내야 하기 떄문에 latency가 발생할 수 있다는 것이다. 이럴땐 뉴스 피드를 pre-generating 하고 분리된 테이블에 저장함으로서 효율성을 증가시킬 수 있다.

뉴스 피드 미리 생성

계속 해서 유저의 뉴스 피드만 생성하고 UserNewsFeed 테이블에 저장 하는 서버를 만들면 된다. 그래서 유저가 뉴스 피드용 사진이 필요할 때 우리는 단순히 이 테이블을 쿼리 하여 결과를 유저에게 리턴해주면 된다.

이 서버들이 특정 유저의 뉴스피드를 생성해야 될 때, 그들은 처음엔 UserNewsFeed테이블을 쿼리하여 그 유저의 생성되어있는 뉴스 피드의 최근 시간을 가져온다. 그러고 나서 그 시간 이후 데이터로 새로운 뉴스 피드를 생성한다.

사용자에게 뉴스 피드를 전달할 다른 접근방식은?

1. pull: client는 interval을 두고 / 필요할 때 마다 pull 해올 수 있다.(client에서 서버에 request) 이렇게 했을 경우 발생할 수 있는 문제점은

   • 유저가 요청하기 전 까지 새로운 데이터가 보여지지 않는다는 점
   • 대부분의 경우 업데이트 된 사항이 없을 때 empty response가 전달된다.
     이렇게 있다.

2. push: 새 데이터가 생성되면 서버에서 유저에게 push 해 주는 방법이 있다. 효과적으로 관리 하기 위해서, 유저는 업데이트를 받기 위해여 서버와 Long Poll request를 유지 해야 한다. 이런 경우에는 사용자가 많은 팔로우를 하거나 millions의 follower를 가진 유명인을 팔로우를 한다면 서버는 업데이트된 내용을 자주 push 해야 한다.

3. Hybrid: 우리는 두 가지 접근법을 섞어서 사용 할 수 있다. 많은 팔로워를 가진 유저는 pull-based 모델을 사용 하고 얼마 안되는(수백~ 수천) 팔로워를 가진 유저는 pull-based 모델을 사용할 수 있다. 또 다른 방법으로는 모든 사용자에게 특정 횟수 만큼만 push 하고, 업데이트가 많은 유저는 정기적으로 pull을 하도록 하는 방법이 있을 수 있다.

12. Sharded Data로 뉴스 피드 생성하기

특정 사용자가 follow 하는 모든 유저의 사진을 가져와 뉴스 피드를 생성 하는 것은 요구사항 중 가장 중요한 요구사항 이다. 이를 위해서, 우리는 사진의 생성 시간에 따라 소팅 하는 매커니즘이 필요하다. 효과적으로 하기 위해서, 우리는 PhotoID의 일부분에 생성시간을 집어넣을 수 있다. 우리는 PhotoID에 primary index를 걸어놓을것이기 떄문에 최신PhotoID를 빠른 시간안에 찾을 수 있을것이다.

이러한 접근법에선, epoch time을 쓸 수 있다. 우리의 PhotoID가 두 부분으로 이루어져 있다고 가정해 보자. 첫번째 부분은 epoch time을 나타낸다. 두 번째 부분은 auto-increment 가 생성한 부분이 될 것이다. 그러므로, 새로운 PhotoID를 만들기 위해선, epoch time 뒤에 key-gen db에서 생성한 시퀀스 값을 붙이면 된다. 우리는 이 PhotoID에서 %10을 하여 샤드 넘버를 알 수 있고 해당하는 샤드에 저장할 수 있다.

PhotoID의 사이즈는 어떻게 될까? 지금 부터 50년 동안 데이터가 쌓인다고 가정해보자. 얼마나 많은 bit가 필요할까?

• 86400 sec / day * 365(days of year) * 50(years) ~= 1.6 billion seconds
  우리는 이 숫자를 저장 하기 위해 31bit가 필요 하다. 그리고 우리는 매 초 23개의 새로운 사진이 업로드 될 것으로 예상하는데, auto-increment로 추가로 9개의 bit를 할당할 수 있다. 그래서 매 초, 512개의 새로운 사진을 업로드 할 수 있다. 우리가 예상했던 것 보다 많이 올려도 된다. we are doing this to get a full byte number (as 40 bits = 5 bytes)(???) 우리는 매 초 auto-increment를 리셋 할 수 있다.

13. 캐시와 로드밸런싱

우리의 서비스는 전 세계에 분산된 사용자들에게 서비스를 제공하기 위해 대규모의 사진 전송 시스템이 필요할 것이다. 당사의 서비스는 지리적으로 분산된 다수의 포토 캐시 서버를 사용하여 사용자에게 콘텐츠를 더 가깝게 전달해야 하며 CDN을 사용해야 합니다(자세한 내용은 캐싱 참조).(번역기돌림ㅎ...)

We can introduce a cache for metadata servers to cache hot database rows. We can use Memcache to cache the data, and Application servers before hitting the database can quickly check if the cache has desired rows. Least Recently Used (LRU) can be a reasonable cache eviction policy for our system. Under this policy, we discard the least recently viewed row first.

How can we build a more intelligent cache? If we go with the eighty-twenty rule, i.e., 20% of daily read volume for photos is generating 80% of the traffic, which means that certain photos are so popular that most people read them. This dictates that we can try caching 20% of the daily read volume of photos and metadata.