Once we have the high-level design, we can focus on specific parts of the system to look for deep dive opportunities. For example, if we add caching, we could decide on an eviction policy like LRU or LFU and choose a tool like Redis or Memcached based on what the system needs. If algorithms are involved, we should think about which one fits best, like using consistent hashing for load balancing or token bucket for rate limiting, and weigh the pros and cons.

We can also look at other areas, like improving database further using indexing or partitioning, or picking the right message broker for handling events, or ensuring the system can handle failures with retries or leader election. It’s also important to think about logging and monitoring.

Below, we’ll take a closer look at areas we could dive deeper into using our examples.

Since this system is read-heavy, caching becomes a crucial component for improving performance and scalability. Let’s explore caching, partitioning, and short URL generation in more detail.

Caching

To optimize the performance of the redirectURL() API, which is vital for this system, we employ a two-level caching strategy. Given the natural locality of access for requests, caching is particularly effective.

At the edge, Content Delivery Networks (CDNs) will store mappings from short URLs to long URLs for the most frequently requested links. For example, if a celebrity shares a short URL on social media, this mapping should be available in the CDN. CDNs, hosted at Internet Exchange Points (IXPs), provide ultra-low latency responses to clients. Their limited storage space focuses on high-demand mappings, ensuring scalability and fault tolerance by handling significant traffic without overloading the API Gateway.

In the data center, we use a caching node such as Redis. With multiple Redis nodes offering hundreds of GBs of memory, a larger set of mappings can be cached compared to the CDN. This approach improves performance by reducing the need to query the database directly. Both CDN and Redis caches use a Least Recently Used (LRU) eviction policy to ensure the cache contains the most relevant mappings.

Partitioning

To ensure scalability, the database and cache layers are partitioned. The short URL is the ideal partitioning key for several reasons. The system primarily performs lookups based on the short URL, making it a natural choice for directing requests to the appropriate cache or database node. Additionally, since short URLs are randomly generated, they are evenly distributed across nodes, preventing hotspots and ensuring balanced load distribution.

Other potential partitioning keys, such as the long URL or user ID, are less effective. Long URLs are not commonly used for lookups, and user IDs may create uneven distribution, leading to hotspots in specific partitions.

Short URL Generation

There are two main approaches to generating short URLs: hashing and random generation.

• Hashing (e.g., using MD5 or SHA-2) creates a deterministic mapping of long URLs to short URLs. While it avoids the need for random number generation, it introduces a higher risk of collisions, particularly because the generated hash (20 bytes or more) must be truncated to fit within the shorter 8-character length of the short URL.
• Random generation minimizes the likelihood of collisions by randomly selecting strings for short URLs. If a collision occurs, the system can simply regenerate another random string. Though this approach requires computational resources for random number generation, modern operating systems like Linux provide efficient random generation through tools like /dev/urandom, making the overhead negligible.

For this system, we will pick random generation as our choice due to its lower collision risk and simplicity in handling potential conflicts.

For twitter, we can explore how the Home Feed Generator interacts with the cache, the type of cache employed, and algorithms for ranking tweets. Additionally, we’ll consider trade-offs, sharding strategies, and bottleneck scenarios.

Home Feed Service

The Home Feed recommends the top K most interesting tweets for a user, ranked by a scoring algorithm. A possible formula for the score is:

Given that pre-generation has been chosen for better performance, we can analyze the storage requirements to determine the appropriate technology and cost. To store the 20 most interesting tweets for 500 million Daily Active Users (DAU), we would need:

Modern caching systems, like Redis, are well-suited for handling this scale. For example:

• Redis servers with 128 GB of memory each could store these mappings efficiently.
• To meet the 5.12 TB requirement, approximately 40 servers would be needed.

This calculation ensures the system is scalable and cost-effective while maintaining low-latency access to precomputed feeds.

Home Feed Generator

The Home Feed Generator pulls new tweets from a message queue, calculates their scores, and updates the top-K tweets for each user. Using Redis Sorted Sets (backed by a skip list) is an efficient approach for this task. Sorted Sets allow quick insertions and retrievals of the top K items without destroying the list, unlike a heap, where items must be popped repeatedly to retrieve the list.

Trade-offs and Technology Choices

To ensure scalability and performance, sharding plays a key role:

1. Tweets Database: Tweets should be sharded by Tweet ID. This evenly distributes the load because Tweet IDs are uniformly generated. A common query pattern, such as looking up tweets by hashtag, remains performant because hashtags can store references to relevant Tweet IDs, directing the query to the correct shard.
2. Redis Cache for Home Feed: The cache storing the Home Feed should be sharded by user_id. Since Home Feeds for all users are roughly the same size, sharding by user ensures an even load across cache servers and allows the system to quickly locate the correct shard for a user’s feed.

Handling Bottlenecks and Failure Scenarios

The current design handles typical workloads well but could face challenges in high-impact scenarios, such as when a celebrity with millions of followers posts a tweet. In such cases:

• A celebrity’s tweet could dominate the top-K lists of millions of users, overwhelming the cache system with updates.
• To mitigate this, the Home Feed Generator should avoid adding tweets from users with a very high follower count (e.g., > 1,000) directly to individual feeds. Instead, such tweets can be added to a dedicated cache or feed for popular users.
• The Home Feed Service can periodically pull from this popular feed (e.g., every 5 minutes) and merge it with individual user feeds, reducing the load on the system while still including relevant content.

Another scalability challenge arises with the number_of_likes field in the Tweet document, particularly when a tweet from a highly-followed user goes viral. For instance, if millions of users press the "Like" button simultaneously, the number_of_likes field in the database becomes a hot spot, creating a bottleneck and potentially overwhelming the system.

To address this issue, we can implement a sharded counter service for users with a significant number of followers (e.g., more than 1,000). This service would handle the counting in a distributed manner:

1. Sharding the Counter: Instead of a single counter, the system would use multiple subcounters (e.g., 100 shards) for a single tweet. Each shard stores part of the number_of_likes value in a high-performance key-value store like Redis. This distributes the load, preventing a single counter from becoming a bottleneck.
2. Periodic Aggregation: The service periodically aggregates the values from the subcounters (e.g., every 5 minutes) and writes the total back to the number_of_likes field in the Tweet document stored in the database. This reduces the write frequency to the database while ensuring the count remains reasonably up-to-date.
3. Efficient Reads: For real-time applications, such as displaying the number of likes on the client side, the total can be fetched dynamically by summing up the values of the subcounters in Redis. Alternatively, for slightly stale but faster reads, the periodically updated value in the database can be used.

This sharded counter approach minimizes contention and ensures that the system can handle viral tweets from highly-followed users without performance degradation. It balances scalability, performance, and accuracy, ensuring the system remains responsive even under high load.

While there are countless areas to explore during a deep dive, this course focuses on a few common patterns and components introduced during the initial design. Even at the deep dive stage, new opportunities frequently emerge to add components or optimize existing ones, further enhancing scalability, reliability, and overall performance. This iterative approach not only strengthens your design but also allows you to drive the system design interview by articulating your thought process clearly and confidently. At senior and higher levels, this ability to drive the discussion of deep dive topics is expected.