System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

1. A registered user can create a thread
2. User can comment on others thread
3. Any (authenticated/anonymous) user can view threads and comments of the that thread
4. A user can edit/delete own comment within a time window of 15mins

System Behaviour

1. Each comment is a parent comment
2. Reply to a comment forms a nested comment
3. System organises comments and keeping it in a hierarchical commenting system and displays in reverse chronological order. The comments are well-organised under each comment maintaining a parent-child relationship
4. A comment can have max 5 nested comment.
5. Pagination - comments are lazy loaded, stepping through 100 comments each
6. Users must be authenticated to comment or create a thread

Non-Functional:

List non-functional requirements for the system...

1. Threads and its comments are rendered within 200ms
2. System scales to 100 thousands of threads and its comments
3. Data consistency - the comments should appear in reverse chronological order. the comments might appear with a delay but this eventual consistency is acceptable
4. Security - authenticated users can post comments. Comments are moderated to avoid false language, sanitised to prevent XSS vulnerabilities

CAP

System prioritises availability more than consistency. The comments may appear a bit later but system is available for reads

Capacity estimation

Estimate the scale of the system you are going to design...

1. Total Users = 100M
2. Daily Active Users 10% of Total users = 10M
3. Comments from each user = 15 comments a day = 10M x 15 = 150M comments
4. Spike on viral topic = 20% of 150M = 180M rounded to 200M
5. Each comment is of max 250 chars with additional metadata of 100 chars for threadId, authorId, commentId = 200M x 350 = 70,000, 000, 000 = 7B chars = 70GB per day
6. WPS = 200M/100000 secs per day = 2000 RPS with 700 Bytes payload, with a spike of viral topics 50% = 3000WPS
7. Storage requirements - write only in database
   1. 70GB per day = 70x30 =2TB per month = 2TB x 12 = 24TB per year rounded to 25TB
   2. In a distributed system writes are replicated to 3 nodes making it 70GB x 3 = 210GB per day
8. RPS
   1. Read is greater than writes, average 10 users reads the comments = 200M x 10 = 2B reads/day = 20K RPS average with spike of 50% = 30K RPS
   2. . approximately 10x to 100x more than WPS = 30K RPS to 300K RPS

API design

Define what APIs are expected from the system...

Get Threads

List All Threads

Get a paginated list of threads with parameters,

1. cursor: optional, a timestamp, returns threads after this timestamp
2. limit: optional, a number of threads to return

Create a Thread

Post a comment

Get comments for a thread

get top-level comments of a thread, if cursor is specified then system returns comments after the specified timestamp and steps through 100 comments at a time. If cursor is not specified then first 100 comments with its sub comments

Get nested comments of a comment

Edit a Comment

Delete a Comment

The cursor query parameter may be ISO timestamp or UUID of a comment

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...

Relationship Overview

1. A thread can have many comments
2. A comment can have many nested comments
3. A user can create many threads and post many comments

Core Entities

1. Thread {threadId, title, content, createdOn, updatedOn, authorId, totalComments, isDeleted, lastCommentedOn}
2. Comment {commentId, threadId, parentCommentId, content, createdOn, updatedOn, isDeleted, depth, lastCommentedOn, upVotes, sortOrder, replyCount, threadIdPath, children}
3. Author {userId, name, handle, .....}

Fault Tolerance and Redundancy

System deployed multiple database nodes with replication factor = 3, meaning every write is copied to 2 more nodes, making it 3 copies. When a node goes down, the one or the replica can serve the data. Writes are eventual consistent and synchronised in the background. Helps in,

1. Disaster recovery
2. redundancy
3. high availability

Sharding

Threads are sharded by threadId making it distributed to a database node. "Write Node = hash(threadId) % N nodes" . this evenly distributes data to N nodes

Partitioning

In a node, the data is partitioned by threadId to enable parallel read/writes. Threads and related comments resides in same partition optimising access patterns.

Replication

When a thread/comment is written it's replicated to two more database nodes for redundancy, disaster recovery and high availability .

Hot Spot mitigation and caching

The reads are relatively higher than writes, hence the hot threads are cached. When a thread goes viral, the thread and its comments are cached into in-memory cache memcache distributed to multiple nodes. The data is sharded with threadId. The cache uses LRU eviction strategy and cache is updated asynchronously via a message bus.

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...

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...

Trade offs/Tech choices

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

Tech Choices

1. Database : AWS managed Dynamo DB for fast range queries, sharding and partitioning.
2. Stream Processing : Flink, Aggregates threads/comments details in 1 min to 5 min window to notify user based on the users topic preferences
3. Broker: Kafka to facilitate changed/added threads/comments and let it flow into flink and updates in-memory cache
4. In-memory cache: Memcache, distributed caching, caches threads and comments with LRU eviction strateg.

Trade Offs

1. Eventual consistency: The new/updated threads are visible with a bit of delay, however this ensures the data is consistent.

Failure scenarios/bottlenecks

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

1. Hotspots : When a thread goes viral, the partition in which it resides receives a lot of read requests, however caching helps to reduce the load on database servers. Even cache server might experience the load since the sharding is with threadId
2. Rate Limitter : Some reads might fail or delayed if the system is under heavy load, this is due to the rate limiter, however it helps the system availability and counter spam requests

Future improvements

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

1. Moderate thread and comment contents - remove bad
2. Sentiment analysis - if the thread or comments are harmful for the public or invoke racism, deny those threads
3. ML Analytics - understand which threads are likely to be viral and pre-cache those in memory.