Classic Design Problems
Design Twitter / News Feed
A news feed system aggregates content from followed users into a personalized stream for each viewer. It is a fundamental architectural challenge because it requires balancing high-throughput write operations with low-latency read requests at massive scale. You reach for this design whenever you need to implement social discovery or personalized content distribution mechanisms.
The Feed Generation Model
The core of the news feed is how we determine what a user sees. There are two primary strategies: 'pull' (fan-out-on-load) and 'push' (fan-out-on-write). A pull-based model computes the feed at request time by querying the databases of all followees, which is memory-efficient but slow for users following many accounts. Conversely, a push-based model pre-calculates the feed for every follower whenever a new post is created, storing the result in a dedicated cache. For high-profile users (celebrities), pushing content to millions of followers creates a 'hot key' problem and massive write amplification. Therefore, modern systems adopt a hybrid approach: they push updates for most users but pull updates from celebrities at read time. Understanding this trade-off is critical because it dictates how you partition your databases and manage your cache eviction policies to maintain performance during peak traffic spikes.
def generate_feed_hybrid(user_id, followees, is_celebrity):
# If the author is a celeb, fetch at read-time (Pull)
if is_celebrity:
return query_recent_posts(author_id=user_id)
# Otherwise, fetch pre-computed feed from cache (Push)
return cache.get(f'feed:{user_id}') # O(1) retrievalDatabase Schema Design
Designing the database requires separating data by concern to ensure individual table operations remain performant. We typically require three core tables: Users, Tweets, and Relationships. The User table stores profile data, the Tweet table handles content and metadata, and the Relationship table maps followers to followees. Because social media involves massive read-to-write ratios, we often favor a relational database like PostgreSQL for transactional consistency when writing tweets, while offloading the news feed to a specialized NoSQL store like Cassandra. Cassandra excels here because its wide-column architecture allows us to store an entire user's pre-computed feed in a single partition, minimizing disk seeks. Furthermore, sharding based on UserID ensures that all of a specific user's posts are localized, which is vital when performing massive fan-outs to follower lists during the push process.
CREATE TABLE user_feeds (
user_id UUID PRIMARY KEY,
tweet_ids list<uuid>, -- Ordered list of pre-computed posts
updated_at timestamp
);
-- Cassandra partitioning by user_id ensures fast feed retrieval.Handling Fan-out at Scale
Fan-out is the process of distributing a single tweet to the timelines of all followers. When a user with one million followers tweets, performing one million individual write operations to user feed databases in a synchronous manner would result in a massive latency penalty. To handle this, we utilize a message queue to decouple the post creation from the fan-out distribution. The service publishes a message representing the new tweet to a broker, and multiple worker threads consume these messages in parallel, performing the database updates asynchronously. This allows the author to receive an immediate 'success' response while the backend system propagates the update across the distributed storage layer. By controlling the concurrency of these workers, we prevent database overloading and ensure that the system remains responsive, even during viral events that trigger cascading fan-out jobs.
def on_tweet_posted(tweet):
# Push to message queue for asynchronous distribution
message_broker.enqueue('tweet_fanout_topic', {
'tweet_id': tweet.id,
'author_id': tweet.author_id
})
return 'Tweet accepted'Caching and Read Latency
Caching is the primary mechanism for meeting the sub-100ms latency requirements of a modern feed. We implement a multi-layered caching strategy: local memory caches for hot user profiles and a distributed key-value store like Redis for storing the most recent N items in a user's feed. Because we cannot store every tweet for every user in memory indefinitely, we employ an LRU (Least Recently Used) eviction policy, ensuring that only active users have their feeds readily available. When a user logs in, the service first checks Redis; if the feed isn't found (a 'cache miss'), it reconstructs the feed from the primary database and lazily populates the cache. This lazy loading approach is powerful because it prevents the system from wasting memory on inactive users who are not currently viewing their news feeds, thereby optimizing resource allocation.
def get_feed(user_id):
feed = redis.get(f'feed:{user_id}')
if not feed:
# Cache miss: fallback to DB and populate cache
feed = db.fetch_user_feed(user_id)
redis.setex(f'feed:{user_id}', ttl=3600, value=feed)
return feedMedia Storage and Delivery
The News Feed involves more than just text; it frequently includes images and videos, which place a massive burden on the network and storage infrastructure. We do not store these heavy assets directly in the database. Instead, we use the database to store a URI that points to a Content Delivery Network (CDN) URL. When a user uploads a file, it is saved directly to Object Storage, and a background process generates thumbnails or compressed variants to support mobile and desktop viewing. By serving this media through edge-cached CDN nodes, we reduce the geographic distance between the data and the user, significantly decreasing load times. This architectural separation ensures that the core feed service remains lightweight and dedicated solely to indexing and delivering feed metadata rather than managing binary blobs of large media files.
class MediaService:
def upload_media(file):
url = s3.upload(file) # Push to object storage
cdn_url = f'https://cdn.example.com/{url}'
return cdn_url # Return only the URI to the databaseKey points
- A hybrid fan-out model effectively balances celebrity bottlenecks with standard user performance requirements.
- Decoupling feed propagation via message queues prevents the system from collapsing during high-volume tweet creation.
- Relational databases are preferred for source-of-truth metadata, while wide-column stores optimize for large-scale feed retrieval.
- Lazy loading into a distributed cache ensures that system memory is reserved for the most active and engaged users.
- Sharding strategies must prioritize UserID to minimize cross-node communication during the critical fan-out phase.
- CDNs are essential for offloading binary assets and reducing latency for global content distribution.
- The trade-off between read-time computation and write-time pre-computation defines the responsiveness of the news feed.
- LRU eviction policies provide a sustainable way to manage limited memory resources in a high-traffic environment.
Common mistakes
- Mistake: Pulling all tweets from every followed user upon request. Why it's wrong: This creates a massive fan-out bottleneck and high latency for users with thousands of followers. Fix: Use a pre-computed feed (Fan-out on write) for most users.
- Mistake: Storing feed data in a relational database. Why it's wrong: Relational databases struggle with the high-concurrency read/write requirements of a global feed. Fix: Use a specialized cache like Redis or a distributed NoSQL key-value store.
- Mistake: Ignoring the special case of 'celebrity' users. Why it's wrong: Fan-out on write for a user with millions of followers causes millions of database operations. Fix: Use a hybrid approach; pull celebrity tweets during request time and push others to caches.
- Mistake: Calculating feed freshness based solely on time. Why it's wrong: It ignores engagement metrics and relevancy, which users expect in modern feeds. Fix: Incorporate a ranking service that balances recency with engagement scores.
- Mistake: Over-relying on a single database shard. Why it's wrong: It creates hot shards and limits scalability. Fix: Use consistent hashing to distribute data across multiple shards based on UserIDs.
Interview questions
What are the core functional requirements for designing a news feed system?
To design a news feed, we must first define the scope. The core functional requirements include the ability for a user to post status updates, follow other users, and view a personalized feed of posts from those they follow. Additionally, we need to support pagination so that a user can fetch their feed in chunks. These requirements prioritize high read-availability and low-latency delivery, ensuring that a user's timeline stays updated as their connections publish new content.
How would you design the data schema for storing users, posts, and follows?
For a scalable system, I would use a relational database for user information due to its ACID properties. For posts, a relational database is also suitable, storing the user_id, content, and timestamp. For 'follows', a mapping table storing the follower_id and followee_id is necessary. To handle the scale, we would index the followee_id for fast lookups. The schema would look like: Table Users {id, name}, Table Posts {id, user_id, text, timestamp}, and Table Follows {follower_id, followee_id}.
Compare the 'Pull' (Fan-out-on-load) versus 'Push' (Fan-out-on-write) approaches for generating a news feed.
The 'Pull' model fetches posts from followed users at read time, which is efficient for celebrities with millions of followers but creates high latency for the reader. Conversely, the 'Push' model writes new posts directly into the pre-computed feed caches of all followers. Push is better for active users because read time is near zero, but it causes the 'celebrity problem' where writing a post triggers millions of database updates. A hybrid approach, using Push for regular users and Pull for celebrities, is generally the most performant strategy.
How do you handle the 'celebrity problem' where a user has millions of followers?
The celebrity problem happens when a Push model attempts to write a post to millions of follower feeds simultaneously, causing significant system lag. My approach is to treat celebrities differently by not pushing their updates. Instead, I store the celebrity's posts in a separate service. When a user requests their feed, the system fetches the user's cached feed and then merges it with the latest posts from any celebrities they follow. This prevents a single post from overwhelming the write queue.
What caching strategy would you implement to optimize the performance of the news feed?
I would implement a multi-layered caching strategy using an in-memory key-value store. First, I would cache the user's feed objects so that the most recent posts are retrieved in milliseconds. Second, I would cache user profiles and social graph data to reduce database hits. Using a Least Recently Used (LRU) eviction policy ensures that we only keep the active users' data in memory, maximizing cache hit ratios while managing memory constraints effectively across our distributed infrastructure.
How would you ensure high availability and reliability when a major event causes a massive spike in traffic?
To handle traffic spikes, I would implement horizontal scaling at the load balancer level and distribute incoming requests across a cluster of application servers. I would use database sharding based on user_id to prevent any single partition from becoming a bottleneck. Additionally, I would use message queues like Kafka to buffer writes during the spike, ensuring that the system processes posts asynchronously. This architecture ensures that even if one component is overloaded, the core service remains functional for the majority of users.
Check yourself
1. When designing a fan-out strategy, why is 'push-on-write' generally preferred for most users?
- A.It minimizes the load on the database during read requests.
- B.It reduces the amount of storage required for the system.
- C.It eliminates the need for a cache layer entirely.
- D.It simplifies the schema requirements for relational databases.
Show answer
A. It minimizes the load on the database during read requests.
Push-on-write moves the computational cost to the time of writing, making reads extremely fast (O(1)). Option 1 is wrong because it doesn't reduce storage. Option 2 is wrong because caching is still necessary. Option 3 is wrong because the model doesn't negate the need for persistent storage.
2. How should a system handle the 'Celebrity Problem' in feed generation?
- A.Ignore the user's follower count and use a single approach.
- B.Force celebrity updates to happen via background batch jobs only.
- C.Pull celebrity tweets at request time while pushing others.
- D.Increase the hardware capacity of a single shard for celebrities.
Show answer
C. Pull celebrity tweets at request time while pushing others.
Mixing pull and push models allows the system to remain responsive. Option 0 is wrong because a push model for celebrities creates massive spikes. Option 1 is wrong because batch jobs don't provide real-time updates. Option 3 is wrong because vertical scaling has strict limits.
3. What is the primary benefit of using a distributed key-value store for feed storage?
- A.It enforces strict ACID compliance for all operations.
- B.It allows for high horizontal scalability and low-latency access.
- C.It automatically optimizes the ranking algorithm for the user.
- D.It prevents data duplication across the cluster.
Show answer
B. It allows for high horizontal scalability and low-latency access.
Distributed key-value stores excel at scaling horizontally and providing low latency, which is essential for feed reads. Option 0 is wrong because feed systems often favor eventual consistency over strict ACID. Option 2 is wrong because ranking is an application layer concern. Option 3 is wrong because data is often intentionally replicated for availability.
4. In a feed system, what is the trade-off of maintaining a 'Feed Cache' per user?
- A.Increased write latency for post creation.
- B.Decreased availability of historical tweets.
- C.Lower storage efficiency due to redundancy.
- D.Elimination of the need for a persistent database.
Show answer
C. Lower storage efficiency due to redundancy.
Caching feeds requires storing the same tweet IDs across many user-specific caches, which is redundant. Option 0 is incorrect as writes are usually asynchronous. Option 1 is false because caches hold recent items, not necessarily historical ones. Option 3 is incorrect as the database remains the source of truth.
5. Why is 'request-time merging' inefficient for a global-scale social platform?
- A.It requires high memory overhead on the client device.
- B.It forces the system to perform heavy aggregation across multiple sources on every read.
- C.It prevents the use of database indexes.
- D.It results in data loss for tweets that arrive late.
Show answer
B. It forces the system to perform heavy aggregation across multiple sources on every read.
Merging feeds during the request involves gathering data from all followed users, which is computationally expensive for high-volume readers. Option 0 is wrong as this happens on the server. Option 2 is wrong because indexes are still usable. Option 3 is wrong because late arrival is a sync issue, not a merging issue.