Instagram system design(generating news feed)

드디어 인스타그램을 시스템적으로 디자인해보는 케이스를 다뤄보게 되었다. 참고로 시스템 디자인 아이디어는 내 아이디어는 아니고, 기존의 레퍼런스를 잘 정리(?) 하면서 나의 학습을 위한 것이다. 우선 내가 아는 부분이 별로 없으니, 좋은 사례들을 학습하는 것이다.

1. 인스타그램?(what is Instagram?)
   • 다들 잘 아시리라 생각한다. 2번 아래 항목을 참고해서 풀자.
2. 요구사항과 시스템의 목표(Requirements and Goals of the System)
   • Functional Requirements
     • Photo 업로드, 다운로드, 뷰
     • Photo/video title로 검색을 할 수 있게
     • 유저들이 다른 유저들을 팔로우할 수 있게
     • 시스템은 해당 유저가 팔로우하고 있는 모든 사람들의 top photo로 구성되어있는 New Feed를 생성할 수 있어야 하고, 보여줄 수 있어야 한다.
   • Non-functional Requirements
     • 서비스는 Highly Available 해야 함(즉, 고가용성)
     • News Feed Generation 을 하는데 허용 가능 지연 시간은 200 ms 이내로.
     • Consistency(일관성) 에 약간의 타격을 받아도 된다. 만약 유저가 사진을 잠시동안 보지 않다면 말이다.(즉, 유저가 당장 사용을 안하는 경우에, 꼭 피드 등의 데이터를 최신으로 갱신할 필요가 없는 것이다.)
     • 시스템은 Highly Reliable 해야한다.(즉 높은 수준으로 신뢰할 수 있어야 한다.) 어떠한 업로드된 사진이나 비디오도 절대 데이터가 손실되어서는 안된다.(Not in scope: 사진에 태그달기, 태그로 사진 검색하기, 사진에 코멘트 달기, 포토에 유저 태깅하기, 누구를 팔로우 하는지 등등)
3. 시스템 디자인 관련 고려 사항(Some Design Considerations)
   • 시스템 디자인은 read-heavy 하며, 우리는 사진들을 빠르게 검색할 수 있는 시스템을 만드는 것에 집중해야 한다.
   • 실질적으로, 유저들은 그들이 좋아하는 만큼의 많은 사진들을 업로드할 수 있다. 스토리지의 효율적인 관리도 시스템 디자인에 있어서 중요한 팩터다.
   • 사진을 보는 동안은 Low Latency 가 되야 한다.(즉, 사진을 보는 핵심 서비스에서는 빨라야 한다.)
   • 데이터는 100% 신뢰가능해야 한다(reliable). 만약 유저가 포토를 업로드한다면, 시스템은 이것이 절대 소실되지 않을 것을 보장해야 한다.
4. 사용량 예상 측정과 제약 사항(Capacity Estimation and Constraints)
   • 500M(5억) 토탈 유저가 있다고 가정하고, MAU는 1M 이라고 하자.
   • 2M(200만)의 새 사진들이 매일 올라오고, 초당 23 개의 새로운 사진들이 올라온다.
   • 평균 포토 사이즈 => 200KB
   • Total space required for 1 day of photos is 2M * 200KB = 400GB
   • 10 년동안 사진을 적재할 예상 공간은 400gb * 365 days * 10 years = 1,425TB
5. 하이레벨 시스템 디자인(High Level System Design)
   • High-level 단의 디자인에서, 우리는 두 가지 시나리오를 생각해야 한다. 첫 번쨰는 사진을 업로드 하는 것, 두 번쨰는 다른 사람이 사진을 view/search 하는 것이다. 서비스는 또한, object 스토리지가 필요하다.(사진 저장을 위한) 그리고, 사진에 대한 메타 데이터를 저장하기 위한 데이터베이스 서버도 필요할 것이다.
6. 데이터베이스 스키마 설계(Database Schema)
   • 초반에 데이터베이스 스키마 설계를 하는 것이 중요하다. 이유는, 다양한 컴포넌트간 데이터 플로우를 스키마 정의를 명확히 함으로써 이해하기 좋고, 추후에 데이터 파티셔닝에 대한 아이디어로 이어지기 때문이다.
   • Users, 그들이 upload한 사진들, 그리고 그들이 follow 하는 사람들을 데이터로 저장해야 한다. 포토 table은 사진과 관련된 모든 데이터를 저장한다; photoid, creation data 위에 index가 필요하다. 왜냐하면 우리는 최근의 사진을 먼저 갖고 와야 하기 때문이다.(fetch)
7. 데이터 사이즈 측정(Data Size Estimation)
   • 10년 동안, 스토리지에 저장할 용량을 측정해보자.
   • 먼저 아래는 User table에 row 당 저장될 용량이다. 참고로 date 자료형의 저장은 보통 4바이트다.(첫 2바이트는 year, 다음 1바이트는 월, 다음 1바이트는 일)
   • User table
     • UserId(4bytes), Name(20bytes), Email(30bytes), DateOfBirth(4bytes), CreationDate(4bytes), LastLogin(4bytes) = 68Bytes per row.
     • 500M people * 68 Bytes = 32GB
   • Photo table
     • photoid(4bytes), Userid(4bytes), PhotoPath(256bytes), PhotoLatitude(4bytes), PhotoLongitude(4bytes), UserLatitude(4btyes), CreationDate(4bytes) = 284 Btyes.
     • 사진이 매일 2M(200백만개) 업로드 되서 db 에 적재된다고 가정하면, 2M * 284 bytes = 0.5 gb per day -> 0.5gb * 365days * 10years = 대략 1.8tb
   • UserFollow
     • Userfollow table의 각 row는 8bytes 임. (아마 following userid, follower userid 두 가지 row로 되어 있으므로)
     • 500M 유저가 있고, 각 유저들은 각각 평균적으로 500users를 follow 한다고 가정하자. 그렇다면,
     • 500M users * 500 user follows * 8 bytes = 약 2tb
   • 즉 위의 user, photo, userfollow 테이블 토탈 3.8tb 가 필요함
8. 컴포넌트 디자인(Component Design)
   • 포토 업로드는 느려도 ok, 근데, 사진을 읽어들이는 속도는 빨라야함(유저들이 봐야 하므로) 그래서, read 를 위한 caching 작업이 필요하다.
   • 그리고, web 서버는 항상 언제든 500 개의 max connection을 맺을 수 있다고 가정하자. 여기서 커넥션은 클라이언트와 서버간 커넥션을 얘기한다.(http 방식의 통신이 보통이므로 tcp connection 이겠다.) 이말인즉슨, 500개 이상의 동시 upload or reads는 처리할 수 없는 걸 의미한다. 이런 병목현상을 제거하기 위해, read 용 서버와 write용 전용 서버(dedicated Servers)를 따로 구성해야 한다.
   • 사진의 read 와 upload 요청을 분리하는 것은 또한, 향후 scale 시 용이할 거고 이런 operation들을 독립적으로 최적화 할 수 있게 해줄것이다.(read 최적화/ upload 최적화 이런식으로)
9. 신뢰성과 불필요한 중복(Reliability and Redundancy)
   • 절대 사진 파일이 소실되면 안되므로, 각 파일 당 여러개의 카피를 갖고 있어야 함. 그러면 스토리지 서버 한 대 정도가 죽더라도 다른 스토리지 서버에 있는 카피로부터 사진을 되찾을 수 있다. 즉, high availability 를 갖기를 원한다면, 시스템 복제를 떠놓아야 한다.
10. 데이터 샤딩(Data Sharding)
    • 메타 데이터 샤딩을 위한 스킴에 대해 얘기하면,
    • 유저 id 기반 파티셔닝: UserId 에 기반하여 샤딩한다고 가정하면, 우리는 유저의 모든 사진들을 같은 샤드에 둘 수 있다. 만약 어떤 한 db shard 가 1tb 라면, 우리는 3.7 tb 데이터를 저장하기 위해 4개의 shard가 필요할 것이다. 이때, 우리가 10개의 shards를 갖고 있을 때, 가장 좋은 퍼포먼스와 scalability를 가진다고 가정해보자. 그래서 우리는 shard number를 UserID % 10 연산으로 찾을 것이고, 각 매핑되는 shard에 데이터를 저장할 것이다.
    • 어떻게 photoid를 만들수 있을까 ? : 각 db shard는 각 샤드 마다 photoid에 대해 auto-increment 시퀀스를 갖고 있고, 이는 shard id 와 pair로 매핑되어 유니크한 값을 갖을 수 있다.
    • 이런 파티셔닝 스킴과는 다른 이슈들은?
      • 어떻게 hot user들을 다룰 것인가? Hot user는 팔로우 하는 사람이 많은 유저로 많은 사람들이 그들이 업로드하는 사진을 볼 것이다.
      • 어떤 유저들은 다른 것들에 비해 더 많은 사진들을 올렸을 것이고, 그러므로 스토리지 분배가 균일하지 않게 일어날 것이다.
      • 만약 우리가 하나의 샤드에 한 유저의 모든 사진들을 저장할 수 없다면 어떻게 될 것인가? 만약 우리가 한 유저의 사진들을 여러 개의 샤드에 분산시킨다면 더 큰 latency를 일으킬 것인가?
      • 하나의 shard에 한 유저의 모든 사진들을 저장하는 것은 unavailability 와 같은 이슈를 일으킬 수 있다 만약 저장을 한 shard가 다운되거나 높은 지연을 갖고 있다면, 만약 이것에 높은 부하가 걸린다면.
        • Partitioning based on PhotoID: 만약 우리가 유니크한 포토 id를 먼저 만들고 photo_id % 10 을 통해 저장할 shard를 찾는다면, 위에서 언급한 문제는 해결될 것이다. 우리가 포토 id 와 shard id를 합칠 필요가 없다면
        • 어떻게 photoid를 생성할 것인가? :포토 id를 샤드마다 생성은 할 수 없을 것이다. (Auto incrementing 시퀀스 규칙을 적용할 수 없기 때문이다. 왜냐하면, 우리는 찾을 photo id를 먼저 알아야 하고, 그것이 저장되어있는 샤드를 그때마다 찾아야 하기 때문이다..) 이를 해결하기 위한 솔루션으로는 아예 auto-incrementing id를 생성하기 위한 별도의 db 인스턴스를 구축하는 것이다. 우리는 오직 64 bit의 id 필드만으로 구성되어 있는 테이블을 정의할 수 있다. 그래서 우리가 사진을 시스템에서 추가할 때마다 우리는 insert new row 하여 photoid 를 갖고 올 수 있을 것이다.
        • 그럼 이러한 키 생성 db는 단일 장애가 일어나지 않는것인가? : 물론 장애가 일어날 수 있다. 해결책으로는 두개의 db를 정의하는 것이 될 수 있다. 첫번째는 짝수 id만 생성하는 db, 두 번째는 홀수 id만 생성하는 db인 것이다. 그래서 로드밸런서를 통해 round robin 로직으로 디비에 쿼리를 날린다.
11. 랭킹과 뉴스 피드 생성(Ranking and News Feed Generation)
    • 주어진 각 유저에 대한 News Feed를 생성하기 위해서는 해당 유저가 팔로우 하는 사람들의 사진들 중에서도 가장 최근의 사진이고, 가장 인기가 많고 관련있는 사진 순으로 리스팅되게 생성을 해줘야 한다.
    • 예로 들면, 유저의 뉴스피드로 100 개의 사진을 Fetch 해야 한다고 가정해보자. 그럼 우리의 애플리케이션 서버는 처음에 해당 유저가 팔로우하는 사람들의 리스트를 갖고 올 것이고, 이 각 유저로부터 가장 최신의 100 개 사진의 메타 데이터를 Fetch 할 것이다. 그 다음 마지막 단계로는 서버가 이 모든 사진들을 랭킹 알고리즘에 넣을 것이다. (여기서 랭킹 알고리즘은 앞서 받은 100개의 사진들을 recency, likeness 등을 고려하여 sorting 해주는 알고리즘을 얘기한다. )그리고 이것을 유저에게 리턴해준다. 이 과정에서 여러 테이블에 multiple query 를 날리고, sorting/mergin/ranking 을 메기는 과정에서 latency 가 생기는 문제가 있을 것이다. 이것을 개선하기 위해 우리는 뉴스피드를 사전에 생성해두고, 이를 별도 분리된 테이블에 저장해 놓는 것을 생각해 볼 수 있다.
    • Pre-generating news feed: 우리는 계속해서 유저의 뉴스피드만을 생성하는 전용 서버를 가질 수 있다. 그리고, 유저 별 뉴스피드 리스트는 UserNewsFeed 테이블에 별도 저장할 수 있다. 그래서 어떤 유저가 그들의 뉴스피드에서 최신의 사진들이 필요할 때면 언제나, 우리는 간단하게 이 UserNewsFeed 테이블에 쿼리를 날려 이를 유저에게 돌려줄 수 있을 것이다. 이런 서버들이 user의 newsfeed 를 생성할 필요가 있을 때면 항상, 그들은 먼저 UserNewsFeed 테이블에 쿼리를 날려서 마지막으로 생성된 시점을 찾을 것이다. 그러고 나서, 새로운 뉴스피드 데이터가 그 마지막 시간 이후를 기준으로 생성될 것이다. 그럼 뉴스피드 컨텐츠를 유저들에게 보내는 다른 접근 방식은 무엇일까?
      • Pull: 클라이언트는 뉴스 피드 컨텐츠를 서버로부터 그들이 필요할 때마다 pull 로 당겨올 수 있다. 이러한 접근방식에서 있을 만한 문제점으로는 a. 새 데이터가 보이지 않을수 있음(유저가 새로운 pull 요청을 할 때 까지.. 예전 데이터므로..) b. Pull request 하는 대부분의 시간은 빈 응답으로 연산될 것이다.(새 데이터가 없으면 갱신해도 똑같으므로..)
      • Push: 서버는 유저들에게 새로운 데이터를 push 할 수 있다. 효율적으로 이를 관리하기 위해서 유저는 long poll 리퀘스트를 서버와 유지해야할 것이다.(업데이트를 받기 위해서..) 이 때 예기되는 문제점으로는 어떤 유저가 엄청 많은 사람을 팔로우 하거나, 수백만의 팔로워를 거느린 셀럽을 팔로우하고 있다면, 서버는 push update를 매우 자주 해야할 것이다.
      • Hybrid: 우리는 하이브리드로 해결책을 생각할 수 있다.
        • 팔로우 하는 사람들이 많은 유저 : pull-based model 사용
        • 고작 몇백명의 적은 사람들을 팔로우 하는 유저: push model(long poll) 사용
        • 또다른 방법으로는 모든 유저에게 push update를 하는 것인데, 일정 업데이트 주기를 넘지 않으면서 적당히 해주는 것이다. 이는 많은 팔로우가 있거나, 업데이트가 많은 유저들에게 규칙적으로 pull data 하게 해준다.
12. 샤딩된 데이터로 뉴스 피드 만들기(News Feed Creation with Sharded Data)
    • 우리는 사진들을 생성시간 기반으로 정렬하는 메커니즘이 필요하다. 이를 효율적으로 하기 위해서, 우리는 photoid 의 파트로 생성시간을 넣을 수 있다. 우리가 photoid 위에 primary index를 가질 것이기 때문에 효율적으로 최근의 photo id를 찾을 수 있을 것이다. Epoch time을 값으로 생각하자. 그럼 우리는 우리의 photoid가 두 개의 파트가 있다고 말할 수 있다. 첫번째 파트는 epoch time을 나타내는 부분, 두 번째 파트는 자동 증가하는 시퀀스이다. 그래서 새로운 photo id를 만들기 위해서 우리는 현재 epoch time 과 key-gererating db로부터 생성된 자동 증가 id를 합칠 수 있다. 우리는 이 photoid로부터 shard 넘버를 알 수 있을 것이고(shard number = photoid % 10) 포토를 해당 샤드에 저장하면 된다.
    • 그럼 photoid의 사이즈는 어떻게 잡아야 할까? Epoch time을 생각하면 ,
    • Epoch time = 86,400 sec/day * 365(days) * 50 years = 1.6 billion secs
    • 즉 우리는 이 숫자를 저장하기 위해 31비트가 필요하다. 그리고 초당 23개의 새 사진이 생긴다고 가정할 시, 우리는 auto 증가 시퀀스를 저장하기 위해 9비트를 할당해야 한다. 그럼 매초 우리는 (2^9 = 512) 개의 새 사진들을 저장할 수 있다. 우리는 매초마다 자동 증가하는 시퀀스를 리셋할 수 있다.
13. 캐싱과 로드밸런싱(Cache and Load Balancing)
    • 8:2 법칙을 생각해보자. 20% 의 read volume 이 80%의 트래픽을 만들어낸다. 즉, 특정한 사진들이 특히 인기가 있어서 다수의 유저들이 본다. 즉, 우리는 이런 20%의 read가 많이 일어나는 사진들에 대해 캐싱을 해두면 된다.