System Requirements

Functional:

1. Users should be able to create tweets
2. Users should be able to search tweets by using a text
3. The search text can be one or multiple words. The search result returned by searching using a phrase with multiple words will mean that all words are present in the tweet
4. Users will be able to follow and un-follow other users. A user's feed will prioritize posts from the users it follows. We are not going to be focusing on this functionality here since this pertains to search only

Non-Functional:

1. Availability - Twitter is a global service, hence, availability is of paramount importance
2. Latency - We would like to see search results in 500 ms
3. Scalability - Twitter would have a massive user base, all our services should be scalable
4. Fault Tolerant - Our service should continue to operate even in case of network failure
5. Consistency - We are aiming for eventual consistency here and not strong consistency
6. Privacy - Searches should be private
7. Durability - We cannot lose tweets, hence, they must be replicated

Capacity Estimation

1. We assume 1 billion daily active users
2. Each user makes at least 1 tweet per day
3. Each tweet consumes 1 KB space, or 10^3 bytes
4. Taking all of this into account, we store 1 billion tweets each day, amount of data needed would be 10^ * 10^3 bytes = 1 TB data everyday
5. In a month, we would store 30 TB data
6. In a year, we would store roughly 400 TB data
7. Over 10 years, we would need 4 PB of data
8. Considering replication, over 10 years, we would need at least 20 PB of storage

API Design

1. tweet
   1. POST request
   2. Parameters would be user ID that is posting the tweet and the contents of the tweet
   3. Returns a message with status code 2xx in case of success, 4xx in case of failure
2. follow(followerID, followeeID)
   1. POST
   2. Parameters would be followerID which would be the userID of the person that follows the user with the userID followeeID
   3. Returns a message with status code 2xx in case of success, 4xx in case of failure
3. search
   1. GET
   2. Parameters would be search phrase
   3. Returns a message with status code 2xx in case of success, 4xx in case of failure

Database Design

1. As evident from the capacity estimation, we would need to store a large amount of data
2. We need a database that can handle a large write throughput, pointing towards a database that employs a multi-leader replication scheme where we can write to any of the leaders
3. We will use a non-relational database like Cassandra since it is easy to scale horizontally and can handle a large write throughput
4. We can use services like Elastic Search to efficiently search through our data. Services like Elastic Search are based on Apache's Lucene and employ a reverse index to search through text quickly. The search index can be stored with the Elastic Search service itself
5. The primary data model tweet will have the given structure.
   1. tweet
      1. tweetID
         1. Unique tweet ID
      2. userID
         1. User's ID who made the tweet
      3. content
         1. Contents of the tweet
      4. createdAt
         1. timestamp at which the tweet was created
      5. hashtags
         1. Hashtags mentioned in the tweet
      6. links
         1. Links mentioned in the tweet
      7. users
         1. User IDs of users who where mentioned in the tweet
      8. language
         1. Language of the tweet
6. We would need to replicate data. For our replication scheme, we can use the geo-location as one of the parameters. Data will be replicated at data-centers around the tweet location and also at other locations, where that language may not be so prevalent, for extra data durability
7. We can use the userID to shard our data. Other candidates for sharding would be userID and geo-location ID. We can use a tweetID and geo-location ID composite key to create shards. Using two parameters ensures that
8. Geo-location ID would ensure that tweets that belong to a region are kept close to users of the region.
9. Using tweetID as the sharding scheme would cause a more equally distributed data which the geo-location and userID combo would miss since some users do not tweet at all
10. We also need to take care of the fact that some tweets by certain users that have a lot of followers can become hot spots. We would ideally cache these in something like Redis which would cut down the stress placed on our database. We would employ a LRU policy for our cache
11. We replicate all data, both tweets and index across multiple data-centers

High-Level Design

1. Popular tweets along with static content like. images and videos can be cached in a CDN and served directly to users
2. Our API server will rate limit all requests sent to it and let the users know that they are being rate limit if they are making too many requests
3. Tweet service and search service would be handled by two different servers which all would be horizontally scaled
4. All requests will pass through a load balancer which can balance requests based on average response times of servers
5. A cache ensures that popular tweets are stored there and reduce stress on our servers
6. We can use a message queue like Kafka to decouple our server from our database. When a tweet is handled by a server, it is then added to a message queue and then written to the database from there
7. We can do a similar thing for creating our reverse index as well, add the tweet to a message queue like Kafka and let the index be created by consuming messages from the queue

flowchart TD CL[client] --> CDN[CDN] CDN-->API[API Gateway] API --tweet(), follow(), search() --> TW[Tweet Service] TW --search()--> SE[Search Service] TW -->DB[Database] SE -->SI[Search Index] TW --push-->MQ[Message Queue] IDX[Indexer]--pull-->MQ IDX-->DB TW-->CC[Cache] SE-->CC IDX-->SI

Request Flows

Explained in the high level design above

Detailed Component Design

Tweet search is implemented by two distinct processes:

1. First one is Indexer. It's a streaming process. A message in the message queue would notifier the Indexer that a new tweet arrived. When it receives the message, it reads the tweet from the database, creates an inverted index (i.e. hash map which points from search words to documents). I assume Indexer does this by calling Apache Lucene or Solr library. It then adds the new index to Search Index
2. The second part is when a user searches for search terms. Tweet Service forwards the search query to Search Service, which is most likely a third party search service like Solr or Elastic Search. This will use the inverted index stored in Search Index.
3. Generally speaking, wherever request comes from should be where the tweets and media files should be stored and served from. A notable exception would be a tweet from a famous people. An international star (e.g. a celebrity)'s tweets are viewed from all across the world. Therefore, it would be important for the system (in this system, it would be Indexer's job) to detect such a tweet, and make sure the tweet (including images and videos) will be stored in database and CDNs of all geo locations.
4. To make sure search occurs quickly, Cache (e.g. Redis Cache) plays an important role. When Tweet Service receives a search query, it first checks Cache if the same or similar search terms were queried. Cache remembers commonly used search terms, e.g., "Beyonce", "Super Bowl Ad". For these terms, Cache can quickly return the search result, without using Search Service, greatly enhancing user response time and scalability.

Trade Offs/Tech Choices

1. Since we are opting for eventual consistency, users might not see the tweet from the users it follows immediately, there will be slight delay there

Failure Scenarios/Bottlenecks

1. Components in our design are tightly coupled for the most part. We should decouple them using message brokers to

Future improvements

1. Allowing searches to be more granular, allowing for more filters and letting the user sort on the basis of certain fields
2. Allow users to block certain users
3. Handling deleting tweets and archiving tweets
4. A service that vets tweets for harmful speech and content