Java LLD: Designing a High-Concurrency Twitter Feed

Designing a Twitter-style news feed is a staple of FAANG machine coding interviews. It forces you to demonstrate a deep understanding of read-vs-write trade-offs and thread-safe data structures in a high-scale environment.

I built javalld.com while prepping for senior roles — complete LLD problems with execution traces, not just theory.

The Mistake Most Candidates Make

The Pull Model Trap: Querying the database for all followed users' tweets and sorting them by timestamp on every single read request. This results in $O(N \log N)$ read latency, which kills performance as the social graph grows.
Ignoring Concurrency: Using standard collections like ArrayList or HashMap for feeds, leading to ConcurrentModificationException when one thread posts a tweet while another reads the feed.
Lack of Bound Checks: Failing to implement a sliding window or capacity limit for in-memory feeds, eventually leading to OutOfMemoryError as the system scales.

The Right Approach

Core Mental Model: Use a "Push-based" (Fan-out on Write) architecture where a tweet is delivered to every follower's pre-computed timeline at the moment it is posted.
Key Entities: User, Tweet, FeedService, SocialGraphService, and Timeline.
Why it beats the naive approach: It optimizes for the 99% read-heavy nature of social media by making feed retrieval a simple $O(1)$ memory access, shifting complexity to the asynchronous write path.

The Key Insight (Code)

To maintain a sorted, thread-safe feed that automatically discards old tweets, use ConcurrentSkipListMap. This allows concurrent access while keeping tweets ordered by timestamp.

public class FeedService {
    private final Map<Long, ConcurrentSkipListMap<Long, Tweet>> userFeeds = new ConcurrentHashMap<>();
    private static final int MAX_FEED_SIZE = 200;

    public void fanOut(long authorId, Tweet tweet) {
        Set<Long> followers = socialGraph.getFollowers(authorId);
        for (Long followerId : followers) {
            // Get or create the thread-safe sorted feed
            ConcurrentSkipListMap<Long, Tweet> feed = userFeeds
                .computeIfAbsent(followerId, k -> new ConcurrentSkipListMap<>(Comparator.reverseOrder()));

            feed.put(tweet.getTimestamp(), tweet);

            // Maintain sliding window
            if (feed.size() > MAX_FEED_SIZE) feed.pollLastEntry();
        }
    }
}

Key Takeaways

Fan-out on Write: Always optimize for the most frequent operation; in Twitter's case, viewing a timeline happens orders of magnitude more often than posting.
The Observer Pattern: Decouple the PostTweet logic from the FanOut logic to ensure that a slow feed update doesn't block the user's primary action.
Thread-Safety without Locking: Leverage java.util.concurrent structures like ConcurrentSkipListMap to handle high-frequency updates without the performance bottleneck of synchronized blocks.

Full working implementation with execution trace available at https://javalld.com/problems/twitter-feed