System requirements

Functional:

• Users should be able upload/download/view photos
• users should be able to search for photo from title
• users can follow other users
• personalize user's feed with Top photos from all people user follows

Non-Functional:

• high availability
• latency for news feed generation : 200 ms
• Eventual consistency is fine - user may not be able to see photo for a while, but availability is important
• high reliability - uploaded photo should not be lost

Capacity estimation

• total users : 500 Million
• DAU : 1 Mil
• Photos per day : 2 Mil, photos per second : 23 (uploads)
• avg photo size : 200 kb
• total storage (1 day) : 200 * 2 mil = 400 GB
• total storage(1 year) = 400GB * 365 * 10 = 1425 TB

API design

Define what APIs are expected from the system...

# upload/download photo

uploadPhoto(user_id, photo_content, created_at) -> photo_id

downloadPhoto(photo_id) -> photo_content (bytesIO)

# user searches for specific photo/s

getPhotos(user_id, search_query) -> list of photo_ids matching search criteria

# follow other users

followUser(user_id, target_user_id) -> boolean

unfollowUser(user_id, target_user_id) -> boolean

# personalized feed

getPersonalizedFeed(user_id) -> list of photo_ids

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

Photo table:

• Photo_id : UUID
• Photo_path : string
• User_id: UUID
• Created_at: datetime
• Photo_location: (Latitude, Longitude)
• User_location: (Latitude, Longitude)

User Table:

• User_id: UUID
• Name: string
• Email: string
• Date_of_birth: datetime
• Date_joined : datetime
• Last_login : datetime

UserFollow table:

• Followee_id: UUID
• Follower_id: UUID

Key observations:

• We have relations within tables - photo / created_at, user_follow etc
• Large number of images are uploaded daily - there will be large amount of sharing the content between users
• Read QPS : (for searching the images) = 5 searches per person per day -> 5 million searches / day
• system is read heavy

Decisions:

Relational vs Non-relational

• We can start with RDBMS like MySQL -> supports joining and aggregation of complex and large data
• Also efficient in querying with reduced latency
• However, it is difficult to scale as the data grows (more complex relations)
• make sure data has high consistency but can sacrifice availability - which is not what we want
• Instead, we can use NoSQL DB
• distributed key-value store - low latency
• replicas across multiple regions - redundancy to make sure high availability
• metadata table would look like : key (photo_id) -> value (Object containing photo info like location, creation_timestamp etc)
• provides high reliability by maintaining replicas
• due to distributed nature, efficient to scale

Photo Storage

• User distributed file storage like HDFS or S3
• supports scaling, provides data security, can store large objects

Data Size estimation per table :

• User table : 68 bytes per user -> for 500 mil -> 32 GB
• Photo table : 284 bytes per photo -> for 2 mil -> 0.5 GB per day
• User follow : 8 bytes per row -> 500 mil users with avg 500 followers each -> 1.8 TB

for 10 years, total storage -> 3.7TB

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

flowchart TD

B[client] -- upload image --> IHS(Image Hosting Service)

IHS --> D[(Image Storage)]

IHS --> M[(Image Metadata)]

B[client] -- View/search image --> IHS(Image Hosting Service)

IHS -- search result --> B

R(Recommendation Service) --> D

R(Recommendation Service) --> M

R(Recommendation Service) -- news feed --> B

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Image hosting Service (IHS) :

• Photo uploads can be slow than downloads. Hence uploading can consume all available connections and during this time, downloads may not work. To avoid this -
• Split into read service and write service
• Easily scalable individual service
• Create multiple replicas across distributed network for high availability
• IHS can act as an Reverse Proxy -> providing all benefits
• User multiple IHS spread out over multiple availability zones
• Use load balancers before the IHS for better load distribution during peak hours

CDN :

• Store static content (images) using CDN to image storage
• reduce load and latency

Caching :

• Introduced for all DB tables
• Keep redundant copies distributed to provide high availability and avoid single point of failure
• Introduce a memory cache for data:
• frequently requested content (search query and respective image_id results)
• cache 20% of daily photo and metadata volume as per 80-20 rule.
• session data (user login, queries)
• Tradeoff between cache types:
• In-memory (amazon ElastiCache) : provision EC2 instances that cache objects in memory. Provides reduced latency and increased throughput. But may need to configure the memory limits on EC2 instances continuously as scale increases
• CDN cache (amazon CloudFront) : Caches data from S3 across large set of geographically distributed regions. Provides high availability and reduced latency.
• Decision: Lets use CDN cache.
• Cache for metadata servers -> cache hot DB rows
• example : memcache to cache the data with LRU eviction policy

News Feed ranking:

• get top 100 posts combining most "relevant" posts from all followees of current user
• Two step process :
• candidate generation : get 100 followers of current user, choose all photos from those 100 followers
• Ranking: ranking algorithm to find most relevant 100 photos out of all photo candidates
• Issues : increased latency
• Solution :
• create a pre-generated news feed and store in separate table (DB)
• dedicated servers continuously generating news feed for the user and store them in "UserNewsFeed" table
• client -> login -> generate_news_feed -> serves check when was the last time it is generated in "UserNewsFeed" table -> generated new feed and store along with current timestamp
• How do users interact with news feed service :
• pull -> users pull news feed as necessary
• issue : new data might not be shown
• push -> server push news feed to users as soon as its available
• issue : user need to maintain long poll request with server, user follows celebrity - updated are pushed constantly
• hybrid:
• celebrity -> pull model
• normal users (100 followers) -> push model
• How to get latest photos of every users the current user follows for ranking ?
• sort photos at time of creation
• Photo_id could be combination of {creation_time + '_' + auto_incrementing_ID}
• create primary Index on photo_id -> for faster search
• auto_incrementing_ID could be gathered from separate Key-generation DB
• Store photos in shards :
• shard_numer = (photo_id % 10)

flowchart TD

B[client] -- request --> LB{Load Balancer}

LB --> IHS(Image Hosting Service)

IHS --> readAPI

IHS --> writeAPI

readAPI --> D[(Image Storage)]

readAPI --> M[(Image Metadata)]

writeAPI --> D[(Image Storage)]

writeAPI --> M[(Image Metadata)]

B --> Cache[Cache]

Cache --> CDN(Content Delivery Network)

CDN --> D

B --> R[Recommend service servers]

R --> UNF[(user news feed)]

B -- get latest feed --> UNF

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?