# Design Instagram

Similar: Twitter/Facebook feeds

## Scenarios

### Use cases, i.e. functional requirements ( 2-3 min)

* Users can send a new post: image/video + description
* Users can follow other users
* Users can view a feed of posts from following users
* Non-goals: search user/post, hashtag, location, mention others, visibility, trending, etc.

#### Non-functional requirements

* high availability, near 0 downtime
* reliable, no lost data
* latency: 200ms for loading feed
* security & privacy

### Estimations (2 min)

#### user scale:

* 100m DAU
* **Read** feeds:
  * every user open app 3 times, in total 10 requests to server
  * 100m \* 10 / 24h = 12k qps -> peak: \*3 = 36k qps
* **Write**(post) feeds:
  * 1m posts every day
  * 12 qps -> peak: 36 qps

#### storage

* photo size: 200kb -> \~200GB everyday
* Next 5 years: 200G \* 365 = 71T \* 5 = 350TB

memory(cache)

networking

## Services

* User service(register, login, profile)
* Relationship service
* **Feed service(read)**
* **Post service(write)**
* **Media service(serve read/write)**
* Advance: fanout, search, recommendation, trending, notification, logging, monitoring, analysis

![Simple version](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-68381c47268fe0feaa80a8a81956d4d1f5d97de8%2Fimage.png?alt=media)

![Optimized version](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-54488be26467ac7ebf9d24e8793b4ee96af9d99e%2Fimage.png?alt=media)

### Media Service

Topic: design file systems

* <https://medium.com/@narengowda/system-design-dropbox-or-google-drive-8fd5da0ce55b>

### Feed generation service

* Store N(500) posts in memory. Fine tune the N. If a user request more than that, generate more on demand.
  * Use LRU cache to pre-generate feed for active users. Smarter: based on usage pattern to pre-generate feeds, e.g. a user usually active on Friday night.
* Pull model
  * cons
    * high latency
    * heavy read on hot users
    * resources wastage if there is no new data in some users/nodes.
* Push model
  * cons
    * celebrity user cause heavy load on fanout service
    * waste resources for generating feeds for inactive users
* Hybrid model
  * Fanout for non-celebrity users, push posts to follower's feed table.
  * Pull celebrity posts when generating feeds for a user.
* Feed ranking
  * Simple: creation\_time
  * Advance: ranking score, sort feed by score + time desc.

## Storage

Table schemas, DB choices

* Post table
  * schema: `post_id, user_id, content, creation_time`
    * PK on `post_id`, secondary on `user_id`
  * shard on user\_id
    * pros: faster query
    * cons: hot spot
  * shard on post\_id
    * pros: has to query all servers -> high latency
  * shard on post id and creation time
    * post\_id: timestamp + auto-increase id
* Feed table
  * Schema: `user_id, post_id, owner_id, content, post_creation_time`
    * PK: `user_id`, secondary: `post_creation_time`
  * Handle mutable post: mark old post invalid, Feed Generator delete/invalid post in Feed Table, Feed service send tombstone to client.
  * Alternative schema: don't store content, `user_id, post_id, post_creation_time`
    * pros:
      * smaller data, no duplicate data stored, maybe fit in memory?
      * tolerate mutable post
    * cons:
      * need to fetch posts by list of post\_id, then merge. lost the benefit of Feed table.
* Relationship table
  * Graph DB
  * MySQL: A follows B,`user_id, following_user_id`
    * Composite PK on both columns.
* User table

## Scalability

* DB replicas
  * Replicate to next 2 nodes in consistent hash ring
  * Leader-follower pattern
    * leader election
    *
* Data sharding
  * Global unique ID generator
  * Hot spot issue
  * shard on PostId
    * latency issue
  * shard on UserId
    * hot spot
    * availability: single point of failure
  * plan for growth: consistent sharding
* Server replicas, redundancy

## Advanced topics

### Like count

* API: likePost(postId)
* Like Table schema: `id, userId, postId, timestamp`
* Process: 1) send to Like service; 2) check if user already liked it before by querying DB or cache in memory. 3) periodically update \<postId, count> to Post table.
* Scalability
  * shard on userId.
  * quick response: maintain cache \<userId, list of historical liked post>. or bloom filter + DB query.
  * every 1s/10s, aggregate \<postId, likeCount>, send to Message Queue.
  * another aggregation service listen to the queue. maintain cache \<postId, likeCount>, periodically batch update Post table.
  * Key point: buffered aggregator to reduce the load on DB.
* Reference
  * <https://redditblog.com/2017/05/24/view-counting-at-reddit/>
  * <https://www.youtube.com/watch?v=bUHFg8CZFws>

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-959a854d266557319caf0bf00dc23f64efd80002%2Fimage.png?alt=media)

### Follow & unfollow

## Reference

* <https://www.acecodeinterview.com/instagram/>
* [Design Instagram](https://www.educative.io/courses/grokking-the-system-design-interview/m2yDVZnQ8lG) grokking-the-system-design-interview
* [Facebook news feed](https://www.educative.io/courses/grokking-the-system-design-interview/gxpWJ3ZKYwl) grokking-the-system-design-interview
* <https://www.educative.io/courses/grokking-the-system-design-interview/m2G48X18NDO>