Design Uber

Problem: Design a highly scalable rideshare service.

Requirements:

1. Functional requirements:

1. Only registered users can request a cab.
• Driver registration is manual and is out of scope here.
2. Driver and user needs to login to request and receive the ride.
3. Driver needs to make himself available to receive the rides.
4. Each driver can be matched to multiple riders depends on users and the occupancy of the car.
5. Price of the ride depends on base flat fee, distance and duration.
• Exact formula is not given and is subject to change
6. We need to minimize the:
1. Wait time of users
2. Distance / Time for drivers to pickup the user.
7. Collect payment information from users.
8. Collect bank information of drivers to pay them.
9. Driver should start/end the trip.
10. For actual payment process, we can use third party services.

2. Nonfunctional requirements:

1. Scalability:
• 100 M to 200 M daily users.
• 100 K to 200 K drivers.
• Peak hours support where demand is 10 times of average.
• Collect driver's location every ~5-10 seconds =~ 3B messages / day
2. Availability:
• 99.99% uptime or higher
3. Performance:
• Match users with drivers 10 seconds at 99 percentile
4. AP over CP:
• Higher availability is required here over consistency.

Design:

Step 1: API Design:

This looks like a very complex system which makes it even more difficult to come up with the all the APIs which are needed for the system to work.

However we will use sequence diagram to make it simple which we are doing in our previous design problems:

Just one thing to notice, given the sequence diagram, we can see the need of having a bidirection connection between server & drivers and also server & riders.

From the sequence diagram we can now have the clear APIs:

Drivers:

• POST /drivers/login
• POST /drivers/{driver_id}/join
• POST /drivers/{driver_id}/location
• POST /trips/{trip_id}/start
• POST /trips/{trip_id}/end

Riders:

• POST /riders/ - Register a rider
• POST /riders/login
• POST /rides

Step 2: Mapping functional requirements to architectural diagram:

1. Only registered users can request a cab.

2. Driver and user needs to login to request and receive the ride.

7. Collect payment information from users.

8. Collect Bank information of drivers to pay them.

To serve these requirements 1, 2,  we can have a single User service. User service will have a SQL DB which contains two tables:

Rider: 

• rider_id
• username
• password
• age
• image_url

Driver:

• driver_id
• username
• password
• license
• vehicle
• image_url

For the profile image we will store the image in object store and put the image url in DB.

To support requirement 7 and 8, we will have a separate service Payment Service which will have it's own SQL DB. This DB will contain the RiderPaymentInfo table and DriverPaymentInfo table.

RiderPaymentInfo:

• user_id
• credit_card
• billing address

DriverPaymentInfo:

• driver_id
• bank_name
• account_number

This payment service will connect with credit card companies / banks for the payment processing.

Here is how our architectural diagram looks like:

3. Driver needs to make himself available to receive the rides:

For this Driver needs to call join API and keep sending it's location. We need to have a new service say Driver Service which will create a bidirection connection using web sockets when Driver call the join API. This will have following benefits:

• Driver needs to send location very frequently so it will remove the overhead of TCP connection every time.
• Server can also push message to driver such as pick_up rider etc.

To record these location we will use a new service say Location Service. Driver service will continue to queue these locations to Location service. We will use a write performant LSM tree based NoSQL DB to store these locations updates. This will contain driver_id and location like lat and long and we continue to update this record until the driver is booked for a trip.

6. Rider can request the ride and the driver must be matched with minimum wait time:

4. Each driver can be matched to multiple riders depends on users and the occupancy of the car:

To request a ride, we will have a new service called Rider Service. Upon requesting the ride, a bidirectional websocket connection has been stablished between rider and this service as we need to send the updates to the riders. 

To match a rider to a driver we will have a new service Matching Service. Let's double click into this matching service to see how to match a driver.

First approach which directly comes into our mind is simple:

• Take the lat, long of rider. 
• Draw a circle centered at rider's location of radius of 2-3 KM and try to find drives within this circle
• Given the location of drivers is already present in Location Service DB, we can use this DB to get the list of drivers.
• Take the driver with the least distance.

However the direct distance of two points is not good measure because of road structures, traffic etc.

Given that the ETA calculation is complex and is not our functional requirement, we can use a third party ETA calculation service. With this third party service here is how our flow changes:

• Matching service sends the rider location to Location service.
• Location service finds all the closed drivers as per our previous approach of 2-3 KM radius circle.
• Location service now sends the list of pairs {user location, driver location} to third party service.
• Third party service sends the ETA of every pair of locations to Location service.
• Location service send these pairs {driver_id, ETA} back to Matching service to make the final decision.

There are few considerations for matching the driver based on that we can match the driver:

• Match driver with the lowest ETA
• Math the driver who is about to finish the trip nearby rider.
• Allow multiple riders to share a ride
• Prioritize drivers whose rating is high for high rated rider.
• Permium service
• Prioritize drivers who have earned very less.

Once the Matching service matches the driver, it needs to store this info somewhere. For this we will have new service say Trip service with it's own SQL DB which will contain source and destination, user_id, driver_id, fare, start_time, end_time, distance etc. Here are the next set of steps: 

• Create a new Trip using the Trip service. Get the trip_id in response.
• Send the signal to Location service to tell it that Driver is booked. It will also send the trip_info. The trip_info will contain trip_id and rider_id for sure.
• Location service will add two new columns: Driver state and Trip Info. 
• Matching service now send the trip info and driver details including location to Rider service which will push this info to Rider.
• Similarly Matching service send the trip info and rider details including location to Driver service which will push this info to driver
• Now when driver send the location to Driver service, Location service append this record to it's DB and also send this location update to Rider service which will update the rider.

You can see how much this web socket connection is useful in these scenarios.

9. Driver should start/end the trip:

Upon reaching the source/destination or where the user wants a drop, driver will start/end the trip by calling the APIs. This will be redirected to trip service. Now Trip service will notify Location Service to change the status of driver as In_Trip / Free. 

Trip service can get the details of locations from Location Service to calculate the distance and everything else for the payments etc.

5. Price of the ride depends on base flat fee, distance and duration:

10. For actual payment process, we can use third party services:

Let's come to the Post trip part where we need to collect the payment from rider and send driver fee to driver account. We also need to send this info as an Email to rider and driver.

Here is the flow:

• Trip servivce will calculate the ride cost and driver fee.
• Trip service will queue the trip_info including user_id, driver_id and payment_info to Payment Service.
• Payment service will interact with third party service to mak the payment.
• Once the payment is successful, It will queue two messages; one for user and one for driver including trip info and their corresponding payment_info to new service Notification Service.
• Notification service will send email to driver and user.

That's all about the functional requirements 

Step 3: Mapping non functional requirements to architectural diagram:

1. Scalability:

Given the traffic we need to run multiple instances of every service. Even the notification service is not public facing service but still at the time of peak, we might need to scale up this service too.

Now the problem is about the Driver service and Rider service as these are having web socket persistent connections. How the location service will come to know which instance to connect to send driver location to rider or how Matching service will know which instance to connect to send trip info to driver.

To solve this issue, we will have a new service called Connection Manager which will have its very efficient key value pair NoSql DB like Redis to maintain this mapping. Now Location Service or Matching Service can query Connection Manager Service to get the right instance.

2. Availability:

For this we just need to add replica of our DBs in order to achieve availability.

3. Performance:

We need to match Rider to Driver with 10 seconds. Let's see what are major steps we have for match:

1. Get the closest drivers list to the rider.
2. Get the ETA of these drivers from third party service.
3. Take the Driver with the lowest ETA.

If you see we can't do anything about step 2 and step 3 is fairly simple. Let's see how we can get the list of closest drivers.

We need to calculate the distance of every free/in_trip driver with the user's location which is fairly expensive. Say somehow we are able to apply certain index on Location DB over Lat and Long (I am not sure how we will use it), it still be very expensive.

Also these floating point calculations are little time consuming for computers. It looks like we won't able to achieve our ETA.

We will use Geohash here to divide the earch into geo cells. Now these geo cell ids will be stored in the Location DB as per the driver locations. That means we are going to add a new column geo_cell_id in the Location DB.

Now the circle which we are drawing centered at User's location can have around 3 or 4 geo cells. Here is how the flow looks like for the step 1 of getting the closes drivers:

• Get the geo cell id as per the user's location.
• Get all the geo cell ids which is covered by 2 KM radius circle
• Now the query to DB will be something like SELECT * from Location where geo_cell_ids in [list of geo cells]

To make the above query we can shard the Location DB based on geo_cell_id or create a hash index over it.

That's all about the performance. Now that we have covered every functional and non function requirements, here is our final architectural diagram:

I know the diagram became a bit messy so I'll improve it later!

Design Youtube

Problem: Design a highly scalable video on demand (VOD) streaming platform.

Requirements:

Before we jump into requirements, we should realize we have two different types of users:

• Content creators
• Viewers

If we try to observe how they use our platform, we can see the requirements are different both functional as well as nonfunctional requirements.

1. Functional requirements:

a. Content creators:

1. Upload any format/codec video.
• Once the video is uploaded, it can be deleted but not be modified.
2. Each video should have metadata:
• Mandatory: title, author, description.
• Optional: List of categories / tags.
• Metadata can be updated anytime.
3. Get an email notification when the video is available publically.
4. Live streaming is not supported.

b. Viewers:

1. Only registered users can view the content.
2. Can search using free text in all of video metadata.
3. Can watch vidoes on any kind of device (desktop / phone / TV) and network conditions.

2. Nonfunctional requirements:

a. Content creators:

1. Scalability:
• Thousands of content creators.
• Upload 1video/week per creator
• Average video size ~50 GB (50 TB / week)
2. Consistency:
• We prefer to have consistency here over availability.
3. Availability:
• 99.9 percentile
4. Performance:
• Response time of page load < 500 ms at 99 percentile.
• Video becomes available to view in hours.

b. Viewers:

1. Scalability:
• 100K-200K daily active users
2. Availability:
• 99.99 percentile
3. Performance:
• Search results and page loads < 500 ms at 99 percentile
• Zero buffer time for video play

Design:

Step 1: API design:

As usual, for the api design let's first translate our functional requirements in a sequence diagram which should look like follows:

Now we can easily identify the entities and URIs using above sequence diagram:

• Users
• /users
• Videos:
• /videos
• /videos/{video_id}
• Search:
• /search

Now let's put HTTP method:

• Users:
• POST /users: Create / register user
• POST /users/login: Login a user
• Videos:
• POST /videos: Start upload a data
• PUT /videos/{video_id}/metadata: Create/update metadata of video
• GET /videos/{video_id}: Get the video url
• POST /videos/{video_id}/play: Send the video content to client
• DELETE /videos/{video_id}: Delete a video
• Search:
• GET /search

Step 2: Mapping functional requirements to architectural diagram:

a.1 Content creator can upload any format/codec video:

b.3 Viewers can watch video on any device and at different network conditions:

I am taking both of these requirements together as these are inter related. We need to upload any video in such a manner that it can be supported on any device and adapted to different network conditions to view.

Let's first understand what is a video file. 

The video file is a container which contains:

• Video stream
• Audio stream
• Subtitles
• Metadata like codec, bitrate, resolution, frame rate

The binary representation of these containers like mpg/avi/mp4 can be different based on how these streams are encoded and algos to encode and decode these streams are called codecs like H.264 or AV1 or VP9 etc.

The video captured using a camera is encoded based on lossless compression algorithm which makes it suitable for professional editing but it is too big in size so this kind of codec is not suitable for streaming and storage at scale so the first step is too apply a lossy compression algorirthm. This method of converting a encoded stream to a different encoded stream is called Transcoding.

Size of a video = Bit rate (bits/second) * Video length (seconds)

So this is obvious that we need to reduce the bit rate in order to reduce the size of video but given that we need to support different devices and different network bandwidth. We can't depend on only one bit rate. We need to support multiple outputs file supporting different bit rates which is directly proportonal to resolutions. The standard resolutions are 360p, 640p, 720p, 1080p and 4K.

This will partially take care of supporting multiple devices but it won't support varying network conditions like home network getting used by multiple users or the user is travelling. To support this requirement, we will use technique called Adaptive bit rate or Adaptive streaming.

In Adaptive streaming, we break our stream into multiple small chunks of size say 5 seconds or 10 seconds. We put references to all of these streams in a text file called manifest(mpd). When player tries to play the video. It first download this manifest file and then choose a default resolution (say 720p) and play it's say first 4-5 chunks to analyze how the network conditions are. If the network conditions are better it switches to better resolution say 1080p or even 4K. It there are download delays then it goes for lesser resolution chunks. Player keeps analysing the chunks download speed to decide which resolution to go for.

The next step is to fully support every kind of devices. For this we need to package our video content to support different streaming protocols. Different OS / browser supports different protocols. Here we can also apply DRM(Digital Rights Management) to protect our video in order to support FR# b.1 Only registered users can watch the video. Using DRM we can also support subscrption when we want to intoduce it.

Now if you see there are steps which we need to take in order to upload the video and making it available for different devices and different locations / network bandwidth. We will use pipes and filter pattern here to support it. 

We will have a Video service as public interface for this whole activity. This service will have it's own DB which is NoSql DB in order to support fluid schema. So here is the flow of video upload:

1. Content creator call Video service to upload video.
2. Video service will start the upload to object store asynchronously and save the metadata into it's DB and return the confirmation to user with video id.
3. Once the video upload is complete to object store, it queues this message to a new service Transcoding service.
4. Transcoding service first convert this video to 5-10 seconds chunks and transcode each chunk into multiple resolution and upload it into it's object store. It also generates manifest file for adaptive streaming.
5. Transcoding service now queue the message to new service say Packaging service.
6. Packaging service package these streams according to streaming protocols and save it into it's own object store.
7. Package service now queue the video_id and video_url(which is ultimately manifest download) back to Video service and video service updates it's DB using the video_id.  

We can debate over a point on Transcoding service where we can propose a new service to break the uncompressed video in chunks, queue these chunks to let transcoding service just transcode these chunks in parallel. But that's what we can achieve using multithreading in the transcoding service itself. In that way it will be much easiser to debug issues and also much easier to support the restartabilty as all these chunkings and transcoding will happen in just one service.

We can support FR# a.3 Notify creatore when video is publically available here only by adding a new service say Notification service. Video service will queue the video details to this service. Notification service now can send the notification (email) to content creator.

With this knowlege let's see how our architectural diagram looks like.

a.2 Update the video metadata:

a.1 Delete the video:

User can simply call the video service to perform these opeations so now here is how the diagram looks like

b.2 Viewer can search for the video against the video metadata:

To support search we need to have a different service say Search service whose DB is optimized for search like Elastic search. Video service can queue the metadata to this service so you can assume it will also become the part of video upload / update of metdata / deletion of metadata. 

We also need to use pagination here.

b.3. Watch video on any device:

We have already done enough to support this requirement. Client first need to call Video service to get the video_url. Client then downloads the manifest file and then client/player will directly stream the chunks of video from object store as per adaptive streaming which I have already explained.

 So now we are done with every functional requirement we have.

Step 3: Mapping non functional requirements to architectural diagram:

a.1 Content creator scalability:

There is not much to do in terms scalability for the first scalability requirement as the frequency of video upload is not much (1/week/user) That means ~10K video uploads in a week. However it can happen that at a particular time we can get thousands of upload requests. To support those we can have multiple instances of Video service and Web app service. 

To tackle the video size we have already created a pipeline to compress the video size but there is still one problem; 

If we take the whole video content to first video service and then upload it to object store, this whole process will consume lot's of resources and as it can take hours to upload uncompressed video, we might end up scaling video service too much. 

To resolve the problem we can use presigned urls of object store. Presigned urls are the urls with limited permissions and limited time. With presigned urls, the flow of video upload looks like as below:

1. Client send request for video upload to video service.
2. Video service requests presigned url from object store with it's own permissions.
3. Send the presigned url as response of video upload API to the client.
4. Client now directly upload the video to object store using presigned url. 
5. Rest of the pipeline remains same.

With this flow, we can see Video service doesn't have to scale and we will save lot's of resources so now with these changes here is how architecture diagram looks like:

a.2 Content creator availability:

We have already take care of the availabity using the multiple instances of web app and video services. We can use the cloud native services for video transcoding and packaging like AWS Elemental MediaConvert and AWS Elemental MediaPackage to support the availability.

We can replicate the Video service DB to support the availability.

a.3 Content Creator Performance:

We have already taken care of the performance as there is not much to do. However the only problem is when all/many content creators try to upload videos at the same time. In such scenario, we might not able to complete the video upload pipeline in hours. 

We need to parallelize this process. That means we need to have multiple instances of Transcoding service and Packaging service.

a.4 Content Creator CP over AP:

To achieve this we just need to choose the right Video service DB or DB's configuration which supports consistency over availability. That's all!

b.1 Viewers Scalability:

To support this 100K - 200K user visits we have already scale our web app service and video service but to scale the search functionality, we need to have multiple instances of search service. This will take care of the scalabilty of service. 

As elastic search is not cloud native, we can use AWS opensearch / Elastic cloud on AWS which autoscale itself.

b.2 Viewers Availability: 

We have done mostly everything for the availability but as here our availability requirement is high. We can use muti region deployment and a global load balancer too. This will also help with the performance.

b.3. Viewers Performance:

We are using adaptive bitrate streaming for the zero buffer time but as you see still we need to download intial chunks, we need to go to object store which might be expensive so we can use CDN to provide it. We can have initial chunks in the CDN to increase the performance of download and then the client can use adaptive streaming to go for the right chunks.

Please note that we can put the whole video too on the CDN which will definitely improve the performance and the quality of the video but it can be very expensive so I am still opting for initial chunks of videos.

 

b.4. Viewer AP over CP:

We are already using lot's of async operations / message broker which guarantees availability but eventual consistency. For search we are already receiving metadata updates using queue and also Elastic search provides AP over CP so this requirement is already satisfied.

With this we are done with every functional and non functional requirements and here is how our final architectural diagram looks like:

That's all!

* Please note that here we should have a User service to support user login and registration but that's very obvious so I have not discussed it here. Given the user's volume is in hundreds of thousand, we don't need to do many things.

Design Instagram

Problem: Design highly scalabale image sharing social media platform like instagram.

Requirements:

1. Functional Requirements:

1. Only registered user can access the platform. They need to provide following info while registering:
• Mandatory: first name, last name, email, phone number, profile image, password
• Optional: age, sex, location, interests etc.
2. User can share/post only images
• We need to design it in a way to extend it to videos or text.
3. Search a user using different attibutes
4. Unidirectional relationship: User A follows User B does not mean User B also follows User A.
5. Load a timeline of latest images posted by people they follow sorted by recency in descending order

 

2. Non-functional Requirements:

1. Scalability:
• ~1-2 billion active users
• 100-500 million visits / day
• Each user uploads ~1 image / day
• Each image size ~2 MB.
• Data processing volume: ~1 PB / day
2. Availability: Prioritize availability over consistency as it is okay even if user does not see the latest data. We are targetting 99.99% here.
3.  Performance: 
• Response time < 500 ms at 99 percentile.
• Timeline load time <1000 ms at 99 percentile.

Design:

Step 1: API design:

For the api design, let's first translate our functional requirements in a sequence diagram which should look like follows:

Now if you see above, we can easily identify the entities and URIs:

• Users
• /users
• /users/{user-id}
• Images
• /images
• /images/{image-id}
• Search
• /search

Now let's put HTTP methods:

• Users 
• POST /users - Create user / register user
• POST /users/login - Login a user
• POST /users/{user-id}/follow - Follow a user
• DELETE /users/{user-id}/follow - Unfollow a user
• GET /users/{user-id}/timeline - Get user time line. This requires pagination.
• Images
• POST /images - Post an image
• GET /images/{image-id} - Get an image
• Search
• Get /search - Search a user

Step 2: Mapping functional requirements to architectural diagram:

Before we move to our main functional requirements, I want to add a service say "Web app service" to serve the html pages since we have support on desktop web browser too.

1. Registering user to our platform:

We will have a User service with it's own DB which will help with login and registration of users. User service database will have following fields as per FR#1:

• user_id
• user_name
• first_name
• last_name
• email
• password
• phone_number
• profie_image_url
• and some optional fields like age, sex, interests, location etc.

If you see we have so many optional fields which can change with time like some optional fields can be removed and some can be added. That means our schema is fluid and that's why we are going with NoSql Document DB. Given we have around ~1-2 billions users, these schma changes become an considerable overhead.

In the schema we are storing the profile image url instead of profile image because DBs are not optimized for blob storage so what we will do is we will store the profile image into a blob store or object store and then save the image url in our DB.

Once the registration is completed, client will get user id and auth token which will help client with further operations.

2. Post an image:

Let's have a post service for this service, we are not calling it as image service so that we can extend it to any type of post. This service will have it's own DB which contains the following fields:

• post_id
• user_id
• post_url
• timestamp
• post_type - This will be by default image but can be extended to video etc.

Since this is a fixed schema, I am going to use SQL DB for storing this info. Here is the flow of image upload:

1. User send the request to Post service to share an image
2. Post service send the image to object store
3. Object store return the url of uploaded image
4. Save the image metdata and url in the DB
5. Return confirmation to user.

3. Search users using different attributes:

We can use the same user service to search the users but if you see this DB is not optimized for search As we don't know in advance what all the attributes are searchable or what kind of search we are going to support, it's better if we use a different service say Search service with DB which is optimized for search scenario like elastic search or other lucene based DB.

So now whenever there is a new user added or there is an update in user's record we can queue it to the search service. Search service will updates it's DB. 

4.: Follow/Unfollow user:

We can create another service to handle follow/unfollow activity but for me it's not that much useful and is unnecessary. We can use existing User service only, we just need to create another collection with following fields:

1. follower_user_id
2. target_user_id 
3. target_user_name

5. Loading the timeline of the user:

That's the most complex problem. Within the current design here is how we can achieve it.

• Client send the request to User service
• User service gets all the users who the user is following.
• It will then query the posts of all the users sorted by timestamps with pagesize of 20-50 using the Post service.
• Send page size number of posts sorted based on timestamp to the client.
• Client can then dowload the images using the post_urls from object store.

This will definitely solve the problem but it is very inefficient. I know we are not solving the non-functional requirements now but we should think about the performance.

To make it efficient, we will use CQRS pattern. We will have a new service called Timeline service. This will have an efficient key value pair DB where key is the user_id and value is the list of post records of all the users followed by the user with user_id(key). Every post record will have {post_url, user_id, timestamp}

Now here is what we do with this new service:

• POST service will queue the new posts containing post_url, user_id, timestamp to Timeline service.
• Timeline service will take the user_id and get it's followers from User service.
• It then add this post to the front of all the followers' list of post records. It can remove the posts if the list is have more records than what we need to show in the timeline.

With this new service, our flow of showing timeline will become straight forward:

• Client requests Timeline service for the timeline.
• Timeline service returns the list of post records from it's key value db with key as requested user's user_id.
• Now client can download the images from object store using post_url.

This will be eventual consistent but that's okay as per our non functional requirements. This will be much efficient than the older design.

Step 3: Mapping nonfunctional requirements to architectural diagram:

1. Scalability: 

If you see we have following scalability requirements here:

• Number of users: We have 1-2 billion users data which will be huge so we can't rely on just one DB instance so we have to shard the User service DB. We can shard using hashing technique:
• User DB: Shard on the basis of user_id.
• Follower DB: Shard based on target_user_id as our main case is to get the followers which is a call from Timeline service.
• For search we are already using elastic search and we can shard it too.
• Number of visists: To support these number of visits, we have to run multiple instances of different services behind load balancer.
• Number of posts: This has two parts:
1. Data in the DB: This will be huge also so we have to shard Post DB as well as Timeline DB. Post DB can be sharded using post_id and Timeline DB using user_id.
2. Image Data: As per requirement we need to save petabytes of data because we are getting uncompressed image. Not only these images will take lots of space but also these are not optimized for viewing on Mobile device or browser. We can introduce an async image processing pipeline like AWS severless image handler to compress these images which will convert this petabytes of data into TBs or even GBs.

2. Availability:

By using multiple instances of our services behind load balancer, we have almost achieved the availability. We can have replicas of our DBs to achieve the availability requirements. Additionally we can do multi region deployement and have a global load balancer in case one region is down. It will also increase the performance.

3. Performance:

We have two performance benchmarks:

• 500 ms for every page load: To achieve it we can use CDNs to store html pages, CSS and post images.
• 1 second for timeline page load: We have already made a decision to use CQRS pattern and made Timeline service to serve the timeline page. This will take care of the performance part but it will create a different problem. There are few thousands of users whom we call celebrity / influencers and millions of users follow them. In case if a celebrity user makes a post, millions of entries of Timeline service DB will be updated which might slow down the DB and hence the performance. To tackle this situation we can make following steps:
1. Define which user is celebrity; Say a celebrity has 1 M followers.
2. Make a column in User DB - IsCelebrity which will tell if the user is a celebrity or not.
3. When celebrity post an image and Timeline serivec calls User service to get the followers list. Instead of returning followers list, User service will return IsCelebrity = true.
4. Another Key-Value pair say Celebrity POST DB will be added to Timeline service DB which where key is celebrity_user_id and value is sorted list of post records.
5. When Timeline service receive IsCelebrity as true. It just add the post into Celebrity POST DB.
6. While loading the Timeline, Time line service get the list of celebrities from User service which the user is following using new REST endpoint on User service say GET /users/{user-id}/celebrity.
7. Timeline service then merge the sorted results it gets from celebrity key value pair and user key value pair and returns it to user.

And that's all about the performance. Now that we have addresses every requirement functional or non functional, here is our final architecture diagram:

Have fun!

[LeetCode] Snapshot Array

Problem: Implement a SnapshotArray that supports the following interface:

• SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
• void set(index, val) sets the element at the given index to be equal to val.
• int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
• int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

Constraints:

• 1 <= length <= 5 * 10^4
• 0 <= index < length
• 0 <= val <= 10^9
• 0 <= snap_id < (the total number of times we call snap())
• At most 5 * 10^4 calls will be made to set, snap, and get.

Approach: First thing in the problem we can notice that we can't save full array, every time we take the snapshot as the length of the array could be 5 * 10 ^ 4 and snap can be called 5 * 10 ^ 4 times.

What we can do is we only store the updates which happened in the current snapshot. In this way for every index we will have a list of snapshot id and the value updates so now when we try to get the value given the snapshot we can do following:

• If no modification i.e. list of updates at the input index will be  null or if no snapshot is taken i.e. current snapshot id is still 0 then we can simply return 0.
• Else we find the upper bound of snap_id using binary search and return the stored value.

That's all!

Implementation in C#:

public class SnapshotArray

{

    public SnapshotArray(int length)

    {

        this.snapshots = new List<Tuple<int, int>>[length];

        this.currSnapId = 0;

    }

   

    public void Set(int index, int val)

    {

        if (this.snapshots[index] == null)

        {

            this.snapshots[index] = new List<Tuple<int, int>>();

        }

        int length = this.snapshots[index].Count;

        if (length > 0 &&

            this.snapshots[index][length - 1].Item1 == this.currSnapId)

        {

            this.snapshots[index].RemoveAt(length - 1);

        }

        this.snapshots[index].Add(new Tuple<int, int>(this.currSnapId,

                                                      val));

    }

   

    public int Snap()

    {

        ++this.currSnapId;

        return this.currSnapId - 1;

    }

   

    public int Get(int index, int snap_id)

    {

        // No modification or no snapshot taken

        if (this.snapshots[index] == null || this.currSnapId == 0)

        {

            return 0;

        }

        int snapIndex = this.FindSnapIndex(this.snapshots[index], snap_id);

        return snapIndex == -1 ?

               0 :

               this.snapshots[index][snapIndex].Item2;

    }

    private int FindSnapIndex(List<Tuple<int, int>> snapIds, int snapId)

    {

        int start = 0, end = snapIds.Count - 1;

        if (snapId >= snapIds[end].Item1)

        {

            return end;

        }

        while (start <= end)

        {

            int mid = start + (end - start) / 2;

            int currSnap = snapIds[mid].Item1;

            if (currSnap == snapId)

            {

                return mid;

            }

            else if (currSnap < snapId)

            {

                start = mid + 1;

            }

            else

            {

                end = mid - 1;

            }

        }

        return end;

    }

    private List<Tuple<int, int>>[] snapshots;

    private int currSnapId;

}

Complexity: SnapshotArray: O(1), Set: O(1), Snap: O(1), Get: O(logn) 

[LeetCode] Time Based Key-Value Store

Problem: Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

• TimeMap() Initializes the object of the data structure.
• void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
• String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Example:

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2"

Constraints:

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits.
• 1 <= timestamp <= 10^7
• All the timestamps timestamp of set are strictly increasing.
• At most 2 * 10^5 calls will be made to set and get.

Approach: This is a binary search problem where we need to find the timestamp which is equal to or just smaller than the given timestamp. 

Given the constraint that timestamps are coming in strictly increasing order, we don't have to sort or maintain a sorted data structure. We can simply use a list.

Implementation in C#:

public class TimeMap

{

    public TimeMap()

    {

        this.kvMap = new Dictionary<string, List<Tuple<int, string>>>();

    }

   

    public void Set(string key, string value, int timestamp) {

        if (!this.kvMap.ContainsKey(key))

        {

            this.kvMap[key] = new List<Tuple<int, string>>();

        }

        this.kvMap[key].Add(new Tuple<int, string>(timestamp, value));

    }

   

    public string Get(string key, int timestamp)

    {

        if (!kvMap.ContainsKey(key))

        {

            return "";

        }

        int index = this.GetIndex(kvMap[key], timestamp);

        return index == -1 ?

               "" :

               kvMap[key][index].Item2;

    }

    private int GetIndex(List<Tuple<int, string>> sortedTimestamps,

                         int timestamp)

    {

        int start = 0, end = sortedTimestamps.Count - 1;

        if (start > end || timestamp < sortedTimestamps[0].Item1)

        {

            return -1;

        }

        while (start <= end)

        {

            int mid = start + (end - start) / 2;

            int currTimestamp = sortedTimestamps[mid].Item1;

            if (currTimestamp == timestamp)

            {

                return mid;

            }

            if (currTimestamp < timestamp)

            {

                start = mid + 1;

            }

            else

            {

                end = mid - 1;

            }

        }

        return end;

    }

    private Dictionary<string, List<Tuple<int, string>>> kvMap;

}

Complexity: Set - O(1), Get - O(logn)

[LeetCode] Count Negative Numbers in a Sorted Matrix

Problem: Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Input: grid = [[3,2],[1,0]]
Output: 0

Approach: Given we have a matrix which is sorted row wise and column wise, we can use the approach which we have used in the problem of searching an element in row wise and column wise sorted matrix.

Here, I am going to start from bottom left corner as the matrix is sorted in descending order but we can solve this problem starting from top right corner too.

Implementation in C#:

    public int CountNegatives(int[][] grid)

    {

        int rows = grid?.Length ?? 0;

        if (rows == 0)

        {

            return 0;

        }

        int cols = grid[0].Length;

        int row = rows - 1, col = 0;

        int totalNegNums = 0;

        while (row >= 0 && col < cols)

        {

            if (grid[row][col] < 0)

            {

                totalNegNums += (cols - col);

                --row;

            }

            else

            {

                ++col;

            }

        }

        return totalNegNums;

    }

Complexity: O(m + n)