System requirements

Functional:

1. User should be able to query with multiple filters
2. Filters can support AND and OR capabilities between the filters.
3. My personalized context should already be part of the query
4. User should be able to link people, places, interest and activities together.

Non-Functional:

1. Query should be fast like P90 should be under 200ms
2. System should scale to handle billions of queries per day - be partition tolerant
3. Consistency is desired, eventual consistency should work.

Capacity estimation

1. For a social network with billions of monthly active user, lets assume 100 MM daily active users making 5 queries each. so looking at 500MM queries per day. 500k consistent TPS and 2x at peak time, so looking at approx 1mm TPS readiness
2. lets say we allow attributes like People who are friends of, like places, have interests to searched on. We are looking to store approx, 200 friend IDs, 10 places, 30 interest, 10 activities. So roughly 250 unique attributes per user.
3. Each unique attribute can be represented by 16 Byte UUID. 4KB data per user. 1 B Users, 1MM unique places, 10k interests, 10k activities

= approx 1.2B unique UUIDs * 4 KB = ~5 Tb data.

API design

1. indexEntities(Type, Schema); // people, place etc and may require different schema per entity. Could be 1 API or multiple based on the structure.
2. List <OutputStructure> os = search ("natural language input"); // this can be a GraphQl layer that breaks down the input into system understandable Query input for API below.
3. Response<List<responseIds, queryRequestFields>, nextToken> x = search(Query <list of filters>, SortBy< list of columns, Asc/Desc>, page size, nextToken);
4. Details objectByEntityType = batchGetDetails(responseIDs);
5. Top5Suggestions = intellisenseAPI("inputString"); // to help autocomplete the search.
6. Filter -> column name, expected value as single vs elements of list, operator (=, regex, >,<, ... )

Database design

1. SQL can be considered as the joins could help form the Graph structure on the fly. Multiple indexes can be created on columns to facilitate a faster search. However, the data size is too huge for SQL to scale properly and multiple indexes will increase the storage index.
2. NoSQL like DynamoDb scales well for situation like this. We can have indexes like GSI to filter and sort on multiple fields. however supporting multiple filters can be tricky. it can be solved by having composite filters.
3. Users table: UserIDs, InterestList, FriendList, activityList.
4. InterestTable: InterestId, location, details
5. ActivityTable: AcitivityId, details, description etc.

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

1. Indexing Service listens to updates from various sources like UserData, places of interests, activities etc and stores it in respective tables.
2. A data stream captures all updates in these tables and joins them in a singular row and put into elastic search cluster.
3. all IDs are indexed.
4. Elastic search can handle AND and OR filters when we structure the schema and define the type for indexed columns.
5. Results IDs are returned and supplemented with more details from the respective tables of User, activity and interests.
6. All respective tables can be cached.
7. Activities and interests can be cached based on geographical preferences.

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

1. Endpoint hits load balancer that hits stateless server hosts of Indexing and Search Service.
2. Indexing Service listens to updates from various sources like UserData, places of interests, activities etc and stores it in respective tables.
3. A data stream captures all updates in these tables and joins them in a singular row and put into elastic search cluster.
4. all IDs are indexed.
5. Elastic search can handle AND and OR filters when we structure the schema and define the type for indexed columns.
6. Results IDs are returned and supplemented with more details from the respective tables of User, activity and interests.
7. All respective tables can be cached with service like Redis. We could have LRU as eviction strategy which resonates with keeping most sought entry in cache.
8. Activities and interests can be cached based on geographical preferences. same LRU strategy.
9. To handle the hot partition issue, we can have data sharding.
10. We can have exponential back-off strategy to retry failures to ensure no heavy load during downtime.
11. Given that we have 2 data sources now, We can also have an auditor job that make sure of data consistency between tables and ES cluster.

Trade offs/Tech choices

1. NoSQL for storing first layer of data and ES to store the joined data provides value at the right level
2. GraphQL against an API structure allows natural language processing from User.

Failure scenarios/bottlenecks

1. Internal failures will be handled by exponential backoff.
2. ES writes could be a bottleneck if the data is updated too frequently. writes can be batched if more eventual consistency is acceptable.

Future improvements

1. Sharding of data at geographical level.
2. Replication of data in other regions for disaster recovery.