System requirements
Functional:
- Recommend entities to a user
- Do not recommend entities that a user has already seen.
Non-Functional:
- The recommendations should be pretty fast - low latency.
- The read latency should be as fat as possible
- Cache should be populated pretty quickly to never exhaust the recommendations.
- The recommendations must be accurately based on user preferences and interaction history.
- The system shouldn't exhaust of recommendations, meaning when the user scrolls through, they should find more recommendations.
Capacity estimation
- Let's assume we have 100 M daily active users.
- User Interaction Metadata - Purchases History, Likes, Clicks etc.
- Assuming for each user we store combined metadata - user emtadata let's say 500 bytes, and like/views/interaction metadata of 1KB.
- Assume every user makes 50 interactions per day. So 50*1 = 50 KB, for a year that will be 50*365 ~ for all users 1825000 ~ 2000000 ~ 2 GB of data .
API design
- Get/api/V2/user/{id}/recommendation
- Post/api/v2/user/{id}/purchase - uploads the user purchase history into the database.
- Post/api/v2/user/{id}/interaction - Uploads the user entity interaction into the database.
- Post/api/v2/user/{id}/preferences - Puts the user preferences into the system
- Get/api/v2/user/{id}/preferences - Gets the user preferences for a user id.
Database design
1) User Metadata - Realtional databse - information like user _id, user_name, created_on, status, etc.
2) Entity Database - entity id, embedding for that entity - a key value store
3) User Entity history Database - user_id, purchased_on, product_purchased, amount paid, - Mongo DB.
4) User Interaction database - user_id, liked_on, viewd_product, etc - Mongo DB
In order to keep it simple, let's use MongoDB for User Metadata, User Entity History Data and User Interaction Data.
5) Recommendation cache - Can be Redis
High-level design
- Recommendation Servers - These will be responsible for actually rendering the recommendations to the user.
- Entitity/Purchase History Database - This will be the database where all the user entity history is stored.
- Entity Database - All the entity related information , which also stores the embeddings - Embeddings is a vector representation of the entity.
- Kafka Queues - This will be the queues to listen to the Change Data capture and there might be a Flink Consumer to consume the data/history and send it to a batch job to process the recommendations.
- Batch / Job scheduler - this will periodically generate the recommedations and dump into a recommendation cache. The cache will maintain recommendations per user.
- Entity Interaction Database - This will store all the user entity interaction like Likes/Views/Comments etc.
- Load Balancers and Rate limiters.
- Bloom filters - to filter out already seen videos.
Request flows
- User purchases a product.
- the product purchase is uploaded to the user-entity history database.
- There is a recommendation request made to the recommendation service,
- The service looks up the recommendation cache for the recommendations and returns it.
- In the background these recommendations are filled by retrieving the last x entities purchased by the user, and the y most similar entities similar to the product. this is done by the Similar products mapper and the TopXproducts retriever, these are the two different methods within the recommendation service.
- The job scheduler runs in the background to generate the recommendations and periodically dump them in the cache.
- To filter out the recommendations that have already been watched we can use a bloom filter to deterministically tell us what hasn't been seen yet.
- The state of the bloom filter is saved onto S3.
Detailed component design
1) Embedding Model and embedding generator -Whenever an entity (product) is uploaded into the system, we should generate an embedding of the same. An embedding is a vector representation of the product, and will be used to compare similar products. We maintain these embeddings in a Entity database which holds entity-embedding for this product.
The embedding model can be generated offline - it's better to do this not on the fly but maybe a job scheduler which runs periodically to populate the embedding database.
2) The recommendation service will consist of two important parts - Retrieval of the last x products purchased by the user, and fetching y similar products for all those x products.
Ranking and Sorting those xy products to generate a list of recommendations.
3) Retrieving the last x products will be from the user-purchase history database , we can cache the top x in a cache, and query from there.
Fetching the similar entities for those , we will have to build kind of a neighbour index entry for each of the entities.
In short, we have to fetch the nearby vectors for a given vector. We could implement and put a vector database for this, which is essentially similar to a geohash index. Similar vectors will be living on the same partition.
1) Convert each vector to a geohash
2) Run linear scans on the bounding boxes for the above geohash to find at least z elements close to this vector.
3) Compute distance to our entity for which we need to fetch recommendations .
4) Sort the above vectors based on their distances relative to the input vector, and keep top y entries.
This relationship of entity- neighbouring vectors can actually be stored in a neighbour index entry, and can be read from there, instead of computing every time.
When a new entity is added, and let's say the neighbour-index entry will need to be changed for many entities - In order to do this easily, we maintain the distances for the vectors - entity in a max heap, so the new entity can be inserted into the head in O(N log n) time.
4) Ranking and Scoring the Entities generated in the above step - We have x different sorted lists, with y different neighbours, we need to merge these lists, the complexity will be o(y log x)
We can assign some scoring now to all these entities based on some entity interactions for these products ( which will be stored in the entity interaction database already). We can compute a scaling function which will be a function of various entity interactions and apply those to the entities. This will generate the final scores and then we need to sort them.
Trade offs/Tech choices
- Vector database will work well for embeddings and calculating neighbour indexes - mostly because its geospatial - Range partitioning in vector databases. similar vectors with simlar boxes bound land in the same parition.
- Neighbour Indexes are partitioned first by the vector hash, and because the index update might result in hot partitions, ( for example similar products falling into one partition and another product for the same cateogry is loaded, that will be updated in the same partition -) for example changes falling under one partition only, we can have the changes flow into read replicas via CDC and partition those read replicas by entity id hash. The recommendation server can read from these replicas, return a bunch of sorted lists (candidates) to the server.
- MongoDB for all the other metadata because it works well for the structure we have.
Failure scenarios/bottlenecks
- Load balancers for all services.
- Replication and partioning for all the databases, to be fault tolerant.
- Caching for the user recommendation and periodically updating them in order to serve fast responses.
- Bloom filter state is saved onto S3.
Future improvements
- using more ML techniques to get user preferences and generate better scoring/ranking of entitites.