Zig-Zag World of Algorithm and Data Structures

[LeetCode] All Divisions With the Highest Score of a Binary Array

2026-01-25T21:15:00.002+05:30

Problem: You are given a 0-indexed binary array nums of length n. nums can be divided at index i (where 0 <= i <= n) into two arrays (possibly empty) numsLeft and numsRight:

numsLeft has all the elements of nums between index 0 and i - 1 (inclusive), while numsRight has all the elements of nums between index i and n - 1 (inclusive).
If i == 0, numsleft is empty, while numsright has all the elements of nums.
If i == n, numsleft has all the elements of nums, while numsright is empty.

The division score of an index i is the sum of the number of 0's in numsLeft and the number of 1's in numsRight.

Return all distinct indices that have the highest possible division score. You may return the answer in any order.

Example:

Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,1,0]. The score is 0 + 1 = 1.
- 1: numsleft is [0]. numsright is [0,1,0]. The score is 1 + 1 = 2.
- 2: numsleft is [0,0]. numsright is [1,0]. The score is 2 + 1 = 3.
- 3: numsleft is [0,0,1]. numsright is [0]. The score is 2 + 0 = 2.
- 4: numsleft is [0,0,1,0]. numsright is []. The score is 3 + 0 = 3.
Indices 2 and 4 both have the highest possible division score 3.
Note the answer [4,2] would also be accepted.

Input: nums = [0,0,0]
Output: [3]
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,0]. The score is 0 + 0 = 0.
- 1: numsleft is [0]. numsright is [0,0]. The score is 1 + 0 = 1.
- 2: numsleft is [0,0]. numsright is [0]. The score is 2 + 0 = 2.
- 3: numsleft is [0,0,0]. numsright is []. The score is 3 + 0 = 3.
Only index 3 has the highest possible division score 3.

Input: nums = [1,1]
Output: [0]
Explanation: Division at index
- 0: numsleft is []. numsright is [1,1]. The score is 0 + 2 = 2.
- 1: numsleft is [1]. numsright is [1]. The score is 0 + 1 = 1.
- 2: numsleft is [1,1]. numsright is []. The score is 0 + 0 = 0.
Only index 0 has the highest possible division score 2.

Approach: The problem is simple, we iterate through the the array we need to maintain number of 0s at the left and number of 1s on the right. Now how we can quickly calculate it?

The number of 1s on the right will be the sum of array minus the number of 1s on the left. To calculate the number of 1s quickly we can maintain prefix array sum. Now you can see the calculation:

Number of 0s on the left at index i = i - prefixSum[i - 1]

prefixSum[i - 1] will tell the number of 1s at the left
If we subtract the prefixSum[i - 1] from i, it will tell the number of 0s on the left

Number of 1s on the right at index i = SUM(nums) - prefixSum[i - 1]

Now we just need to calculate the maximum of the sum of above two values at each index i and return all the i's which has the maximum sum.

Implementation in C#:

    public IList<int> MaxScoreIndices(int[] nums)
    {
        IList<int> result = new List<int>();
        int length = nums?.Length ?? 0;
        if (length == 0)
        {
            return result;
        }
        int arrSum = nums[0];
        for (int i = 1; i < length; ++i)
        {
            arrSum += nums[i];
            nums[i] += nums[i - 1];
        }
        int maxScore = arrSum;
        result.Add(0);
        for (int i = 1; i < length; ++i)
        {
            int currScore = i - nums[i - 1];
            currScore += (arrSum - nums[i - 1]);
            if (currScore > maxScore)
            {
                maxScore = currScore;
                result = new List<int>();
                result.Add(i);
            }
            else if (currScore == maxScore)
            {
                result.Add(i);
            }
        }
        int lastScore = length - arrSum;
        if (lastScore > maxScore)
        {
            maxScore = lastScore;
            result = new List<int>();
            result.Add(length);
        }
        else if (lastScore == maxScore)
        {
            result.Add(length);
        }
        return result;
    }

Complexity: O(n)

[LeetCode] Minimum Cost of Buying Candies With Discount

2026-01-25T20:05:00.003+05:30

Problem: A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free.

The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought.

For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.

Given a 0-indexed integer array cost, where cost[i] denotes the cost of the ith candy, return the minimum cost of buying all the candies.

Example:

Input: cost = [1,2,3]
Output: 5
Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free.
The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies.
Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free.
The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.

Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: The way in which we can get the minimum cost is described below:
- Buy candies with costs 9 and 7
- Take the candy with cost 6 for free
- We buy candies with costs 5 and 2
- Take the last remaining candy with cost 2 for free
Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.

Input: cost = [5,5]
Output: 10
Explanation: Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free.
Hence, the minimum cost to buy all candies is 5 + 5 = 10.

Approach: The question is to get the minimum cost possible. Given we can exclude the cost of every third candy, we need to exclude the maximum cost candy possible. Given we can only exclude a candy from the triplet if the cost of other two candies are more or equal to the excluded candy. That means we can exclude 3rd maximum, 6th maximum, 9th maximum and so on.

Given we need to exclude the maximum cost candy possible given the above condition, what we can do is to sort the array in descending order and then it becomes simple to exclude cost[2], cost[5], cost[8] and so on. Remaining sum of the array is our answer.

Implementation in C#:

    public int MinimumCost(int[] cost)
    {
        int length = cost?.Length ?? 0;
        if (length == 0)
        {
            return 0;
        }
        Array.Sort(cost, (i, j) => {
            return j.CompareTo(i);
        });
        int minCost = 0;
        for (int i = 1; i <= length; ++i)
        {
            if (i % 3 == 0)
            {
                continue;
            }
            minCost += cost[i - 1];
        }
        return minCost;
    }

Complexity: O(nlogn)

[LeetCode] Array Partition

2026-01-25T19:40:00.003+05:30

Problem: Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

Example:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Approach: The catch here is to get the maximum sum possible. That means we need to get the maximum n values possible from the array but the problem here is we need to get the minimum value of the pair so what we can get is 2nd maximum, 4th maximum, 6th maximum and so on.

To get this efficiently, we can sort the array and then take nums[0], nums[2], nums[4] and so on. We just need to add these values and return it.

Implementation in C#:

    public int ArrayPairSum(int[] nums)
    {
        int length = nums?.Length ?? 0;
        if (length == 0 || length % 2 != 0)
        {
            return 0;
        }
        Array.Sort(nums);
        int sum = 0;
        for (int i = 0; i < length; i += 2)
        {
            sum += nums[i];
        }
        return sum;
    }

Complexity: O(nlogn)

[LeetCode] Minimum Difference Between Highest and Lowest of K Scores

2026-01-25T19:24:00.002+05:30

Problem: You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.

Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.

Return the minimum possible difference.

Example:

Input: nums = [90], k = 1
Output: 0
Explanation: There is one way to pick score(s) of one student:
- [90]. The difference between the highest and lowest score is 90 - 90 = 0.
The minimum possible difference is 0.

Input: nums = [9,4,1,7], k = 2
Output: 2
Explanation: There are six ways to pick score(s) of two students:
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 1 = 8.
- [9,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2.
- [9,4,1,7]. The difference between the highest and lowest score is 4 - 1 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 4 = 3.
- [9,4,1,7]. The difference between the highest and lowest score is 7 - 1 = 6.
The minimum possible difference is 2.

Approach: We have to find the maximum and minimum value of each k size subarray so we can sort the array. Now what we just need to do is to take the subarray in sequence like nums[0...k-1], nums[1...k], nums[2...k+1] etc. Now if you see its easy to find the max and min value of these subarray as 1st value will be the minimum value and last value is the maximum value.

Now we just need to take the difference of these value and get the minimum of these differences which will be our answer.

Implementation in C#:

    public int MinimumDifference(int[] nums, int k)
    {
        int length = nums?.Length ?? 0;
        if (k > length)
        {
            return 0;
        }
        Array.Sort(nums);
        int min = int.MaxValue;    
        for (int i = 0; i + k <= length; ++i)
        {
            if (min > nums[i + k - 1] - nums[i])
            {
                min = nums[i + k - 1] - nums[i];
            }
        }
        return min;     
    }

Complexity: O(nlogn)

[LeetCode] Smallest Number With All Set Bits

2025-10-29T21:06:00.002+05:30

Problem: You are given a positive number n.

Return the smallest number x greater than or equal to n, such that the binary representation of x contains only set bits

Example:

Input: n = 5
Output: 7
Explanation: 
The binary representation of 7 is "111".

Input: n = 10
Output: 15
Explanation: 
The binary representation of 15 is "1111".

Input: n = 3
Output: 3
Explanation: 
The binary representation of 3 is "11".

Approach: One simple way to think about it is we just need to get the number of bits requird to (like 5 is 000...0101 so number of bits are 3 in number 5) represent the current number and get to the number which is having same number of bits with all the bits set.

To get the number of bits, we can simply take the log base 2 of the given number. Say the result is b so the result will be 2^b - 1.

Now say we are not given the log method and also we want to make it more performant using biwise operations.

Key is if the a number has all the bits set then n & (n + 1) will be 0 so what we just need to do is keep setting the unset bit set using n | (n + 1) till we get n & (n + 1) is 0.

Question is how n | (n + 1) will set the bit.? It's because adding 1 to a number will always set the first unset bit so if we OR with the original number, we are setting the next unset bit in the original number.

Implementation in C#:

Approach 1: Using Log2:

    public int SmallestNumber(int n) 
    {
        int numBits = (int)Math.Floor(Math.Log2(n)) + 1;
        return ((int)Math.Pow(2, numBits)) - 1;
    }

Approach 2: Using Bitwise operators:

    public int SmallestNumber(int n) 
    {
        while ((n & (n + 1)) != 0)
        {
            n |= (n + 1);
        }
        return n;
    }

Complexity: O(logn)

[Netflix Tech Blog] Behind the Scenes of Pushy - Netflix’s Real-Time WebSocket Proxy (Part 1)

2025-08-01T21:23:00.003+05:30

In today’s connected world, user experiences are expected to be instant, interactive, and deeply personalized. Whether it’s a mobile notification about a new episode, a voice command to your smart TV, or a prompt to resume your last show; the ability to push messages in real-time has become critical.

At Netflix’s scale, serving hundreds of millions of devices across the globe, building and maintaining a real-time communication layer isn’t just desirable, it’s mission-critical.

That’s where Pushy comes in which is Netflix’s in-house WebSocket proxy, designed to reliably deliver low-latency, bi-directional communication between client devices (TVs, phones, browsers, game consoles) and backend services. Originally created to support use cases like voice search, remote control pairing, casting, and other interactive UI elements, Pushy quickly became a foundational service for Netflix.

But as the streaming giant continued evolving its product and infrastructure, cracks began to appear in Pushy’s original design and some of them are scalability, observability, and operational resilience needed a rethinking.

In this two-part breakdown series, I’ll walk you through:

What Pushy is and why Netflix built it
The original architecture and its role in powering interactive features
What worked well and where it started to show strain
And in Part 2: how Netflix rearchitected Pushy to meet the future head-on

📖 Reference: Pushy to the Limit: Evolving Netflix’s WebSocket Proxy for the Future

Let’s start by understanding the need for Pushy in the first place.

💡 Why Netflix Needed Pushy in the First Place

As Netflix expanded from being a content streaming service to an interactive entertainment platform, the demands on its device communication infrastructure grew rapidly. Simple HTTP-based polling or long-polling mechanisms were no longer sufficient for the level of interactivity users expected.

Here are the emerging use cases that demanded real-time, low-latency communication between Netflix devices and backend services:

Voice Search & Navigation: Smart TVs and streaming devices increasingly support voice commands. Users expect their spoken input to be recognized, interpreted, and acted upon in real-time, requiring a persistent, fast channel between device and service.
Second-Screen Experiences & Remote Control Pairing: Netflix enables pairing between mobile devices and TVs, allowing the phone to act as a remote or companion device. This requires devices to discover each other and exchange information instantly.
Casting: When users cast Netflix content from their phones to another device (like Chromecast or a Smart TV), there’s a need for near-instant coordination between devices.
Interactive UI Elements: Think of countdowns, real-time error reporting, or UI nudges (e.g., "Resume from where you left off") , these need to be delivered to the client immediately and reliably.

To power these experiences, Netflix needed a solution that:

Could maintain persistent, bidirectional connections at scale.
Worked across millions of heterogeneous devices.
Offered low-latency delivery for time-sensitive events.
Could be centrally managed, observed, and extended to future use cases.

That solution was Pushy, a custom-built WebSocket proxy service that sits between client devices and backend systems, managing long-lived connections and ensuring seamless real-time communication.

Here is one example of alexa voice commands where pushy played a vital role:

📡 Pushy’s Original Architecture — End-to-End Overview

Pushy was Netflix’s custom-built WebSocket proxy designed to maintain persistent, low-latency, bidirectional communication between millions of client devices and backend services.

At a high level, Pushy accepted WebSocket connections from clients (TVs, mobile devices, etc.), maintained their sessions, and routed messages to the appropriate backend services over gRPC. However, under the hood, it contained several sophisticated components that enabled it to operate at Netflix scale.

Here’s how it worked, step-by-step:

Client Connection

A client (e.g., a smart TV) initiates a WebSocket connection to Pushy.
Pushy authenticates the client and establishes a session.
It stores routing metadata (e.g., region, app version, device ID) for the session.

Session Registration in Push Registry

Pushy registers the client session in a Push Registry, which acts as an in-memory mapping of client sessions to backend service instances or logical partitions.
This registry is consulted for routing incoming and outgoing messages.
Initially, Netflix used Dynomite (a high-availability Redis wrapper) to back this registry.

Message Ingestion via Queue & Processor

Client sends a message over the WebSocket connection.
The message is queued in an internal Message Queue to absorb bursts and prevent backpressure from backend systems.

Processing via Message Processor

The Message Processor consumes messages from the queue.
It applies session-specific logic, enrichment, or transformation.
Messages are then serialized into gRPC-compatible formats.

Routing to Backend Services

Based on the Push Registry’s mapping and routing rules from the Control Plane, the message is routed to the correct backend service over gRPC.

Outbound Messaging

Backend services can also push messages to clients.
Pushy uses the same registry to identify the client session and deliver the message over the existing WebSocket connection.

🔍 Supporting Control Plane (External)

Pushy constantly syncs with an external Control Plane, which provides:

Dynamic routing rules
Backend service discovery
Deployment topology
Traffic shaping configs

🛡️What is Dynomite

Dynomite is a plugin layer built by Netflix to transform existing, standalone storage engines like Redis or Memcached into a fully distributed, highly available, and multi‑data‑center system. Designed around concepts from Amazon’s Dynamo architecture, it enables:

Active‑active replication across data centers
Auto‑sharding, linear horizontal scalability
Configurable consistency levels, node‑warmup, and backup/restore support

Netflix has used Dynomite in production extensively, up to 1,000+ nodes, serving over a million operations per second at peak, with clusters reaching multiple terabytes in size.

A standard Redis or Memcached instance is a single‑server cache. Dynomite allows Netflix to:

Seamlessly scale to many servers and data centers
Replicate data synchronously across regions for high availability
Avoid a single point of failure while maintaining low latency and consistent behavior under heavy load.

There is also a management tool called Dynomite Manager that helps automate tasks like node replacement and bootstrap, especially useful when deploying via AWS Auto Scaling.

🔁 Scalability and Auto-Panning

To deal with global scale, Pushy’s initial strategy was to scale out WebSocket servers horizontally across availability zones. But this wasn’t enough, some zones still ended up with more load due to device churn and reconnect storms.

Netflix introduced auto-panning, a strategy where incoming connections would be balanced based on current server load and connection counts, not just simple round-robin DNS-based routing.

This was a precursor to what would become a more intelligent, connection-aware load balancing strategy in the evolved architecture.

✅ Summary

Pushy wasn’t just a simple proxy but it was a session-aware, fault-tolerant, scalable message router for real-time device communication. By combining message queuing, smart session routing, and dynamic discovery, it helped Netflix deliver seamless user experiences across millions of connected devices.

⚠️ Challenges with the Original Pushy Architecture

While Pushy’s original design served Netflix well at first, it began to strain under the weight of scale, evolving use cases, and operational demands. As the number of connected devices grew into the millions, and as Pushy became central to real-time features across multiple Netflix applications, a range of technical and architectural issues surfaced.

Let’s break them down:

1. Frequent Reconnect Storms

Netflix devices tend to reconnect all at once:

Power outages, Wi-Fi changes, or Netflix app updates often trigger mass reconnects.
WebSocket servers had to handle a spike of TLS handshakes, registry updates, and message backlog replays and all within seconds.

This led to:

Thundering herd problems
Sudden CPU and memory pressure on specific nodes
Occasional partial outages during large-scale reconnects

2. Push Registry Memory Pressure and Latency

The Push Registry, backed by Dynomite, became a bottleneck:

Every message delivery required low-latency lookups in the registry to identify active sessions.
With millions of devices, memory usage ballooned.
Dynomite’s replication overhead and Redis-like architecture couldn’t scale linearly, resulting in lookup slowdowns and stale data.

3. Limited Fault Isolation

A major issue was no strong isolation between customers or device types:

A bug or reconnection surge in one type of client (say, Android TVs) could affect Pushy performance globally.
Without sharding or tenant separation, a misbehaving device model could overwhelm shared infrastructure.

4. Insufficient Observability and Debuggability

The original message processor had limited metrics and retry intelligence.
Operators lacked visibility into where messages got stuck or which sessions were stale.
Diagnosing delivery failures required deep dives across multiple logs and systems.

This made it hard to:

Guarantee message delivery SLAs
Track end-to-end latency
Quickly respond to production issues

5. Network Topology Challenges

Since WebSocket servers needed to stay globally distributed and session-aware:

Load balancing at the TCP level was tricky (WebSockets aren’t natively friendly to CDN-style routing).
Auto-scaling had to preserve session stickiness.
Edge nodes required careful management of memory, state, and connection churn.

6. New Use Cases Were Outgrowing the Architecture

Pushy started with basic notifications, but:

Features like real-time device sync, voice input responsiveness and cross-device experiences demanded ultra-low latency and higher delivery guarantees.
The original system wasn’t optimized for delivery retry, QoS policies, or global message routing.

🔚 Wrapping Up Part 1: The Rise and Limits of Pushy

In this first part, we explored why Netflix needed a solution like Pushy in the first place and how it enabled seamless, real-time interactivity across devices, from second-screen controls to voice-based commands. We broke down the architecture that powered this WebSocket-based infrastructure, including its registry, message queues, and processors.

Pushy served Netflix exceptionally well for years, supporting a growing range of use cases and hundreds of millions of concurrent connections. But as we saw, scale and diversity came with operational trade-offs. From resource fragmentation to uneven scaling, the cracks began to show, not because Pushy was inadequate, but because Netflix’s needs had fundamentally evolved.

In Part 2, we’ll dive into how Netflix re-architected Pushy to meet these new demands: the innovations they introduced, how they tackled each bottleneck systematically, and what benefits the evolved system now unlocks—including hints of what might come next.

[Deliveroo] Design Swiggy

2025-07-22T12:14:00.013+05:30

Designing a highly scalable food delivery application like Swiggy or Zomato is a complex challenge that involves optimizing for scale, consistency, low latency, and real-time tracking. These apps handle millions of users, orders, and real-time delivery updates across cities, all while ensuring a seamless user experience.

In this post, I’ll walk through a step-by-step architectural design of a food delivery system, starting from functional and non-functional requirements to API design, services, data modeling, and finally addressing performance, availability, and consistency trade-offs.

Requirements:

1. Functional requirements:

It's an app only system.
Only registered users can order food.

Delivery partner registration is manual and out of scope

User and delivery partners need to login to order food and deliver food.
Delivery partners need to make themselves available to receive the delivery order.
Restuarants need to register and upload the menu to receive the food order.
Restaurants need to make themselves available to receive the order.
We need to minimize the:

Wait time for the users
Distance / Time for delivery partners to deliver the food.

User should be able to search the dishes, cuisines and restaurants.
User should be able to see the top rated nearby restaurants on home page.
Collect payment information from user.
Collect bank information from restaurant to pay them
Delivery Partner should be able to mark the order state like in transit, delivered
Users should be able to track their order.
Users should be able to rate restaurants and delivery partners.

2. Non functional requirements:

Scalability

100 M total users.

10 M daily orders. ~ 115 orders / seconds or 1000 - 2000/second during peak hours.

100 K delivery partners
Collect delivery partner's location every 5 seconds i.e. 20 K messages / second.
300 K total restaurants
100 items per restaurant menu so total menu items are 30 M.

Availability

99.99 or higher

Performance

Search < 200 ms
Loading home screen < 500 ms
Loading Menu < 500 ms

CP over AP

Consistency is imporant over availability here.
Can't have older menu or older addresses etc.

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:

Given the sequence diagram, we can see the need of having a bidirection connection between server & delivery partners and also server & users.

We now have clear APIs:

Restaurants:

POST /restaurants
GET /restaurants
GET /restaurants/{restaurant_id}
PUT /restaurants/{restaurant_id}
POST /restaurants/login
POST /restaurants/{restaurant_id}/menu
GET /restaurants/{restaurant_id}/menu
POST /restaurants/{restaurant_id}/join
POST /restaurants/{restaurant_id}/state

Delivery Partners:

POST /dpartners/login
POST /dpartners/{partner_id}/state
POST /dpartners/{partner_id}/location
POST /dpartners/{partner_id}/rate

Users:

POST /users
POST /users/login
PUT /users/<user_id>
GET /users/<user_id>

Order:

POST /orders
GET /orders?restaurant_id=<id>
GET /orders?partner_id=<id>
GET /orders?user_id=<id>
POST /orders/{order_id>/state
GET /orders/{order_id>

Search:

GET /search/restaurants
GET /search/dishes

Step 2: Mapping functional requirments to architectural diagram:

1. User need to register and login to order food, Should be able to update the info

We will have a User service to serve these two requirements. we can collect the payment info while registeration. User service will use a SQL DB which will have two tables:

User:

user_id
user_name
password

User_Profile:

user_id
phone_no
email
address
PIN

User Payment information will be sent to another service that is Payment service from User Service. This service will have its own SQL DB which will have following table:

UserPaymentInfo:

user_id
credit_card
billing_address

2. Restaurant registration, login, upload menu and update these details:

We will have a separate service say Restaurant Service which will have its own SQL DB. It will have following tables:

Restaurants

id
user_name
password
name
location
address
pin
IsActive
menu_id
avg_rating
num_rating

RestaurantMenu

id
restaurant_id
name

RestaurantMenuItem

id
menu_id
item_id
price
IsAvailable
avg_rating
num_rating

MenuItem

id
Name
Description

The payment info will be sent to Payment Service to store the bank details. Payment Service will have another table in its SQL DB to store this info:

RestaurantPaymentInfo

restaurant_id
bank_details

The menu and restaurant metadata will be sent to a new Search service. Search service will store this metadata in it's Elastic Search database.

3. Restaurants need to make themselves available to receive the order.:

Restaurant admin simply call Restarant service. Restaurant service will mark the restaurant's IsActive as True. The diagram for both 2 and 3 FRs is as below:

4. Delivery Partners need to login and make themeselves available to recieve the orders:

To support delivery partners, we will have another service say DPartner Service. This has its own SQL DB to store the delivery partners info. Here are the tables:

DeliveryPartner

id
name
user_name
password
rating
is_active
num_deliveries

Deliver Partners can make themselves available using DPartner Service. It will just change the state in the DeliveryPartner table. Once they made themselves available, DPartner service will create a bidireactional connection using web socket. This will have following benefits:

Delivery Partners need to send location very frequently so it will remove the overhead of TCP connection every time.
Server can also push messages like pick_up order etc.

To record these location we will use a new service say Location Service. DPartner 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 partner_id and location like lat and long and we continue to update this record until the partner is active. Here is the schema of the collection:

partner_id
latitude
longitude
order_id

We are going to have another service say ConnectionManager Service. It will store user_id and connection_id in a highly performant KeyValue pair DB like redis so once the WSS connection is established, DPartner service will call ConnectionManager service to store this info. For now it is not required but it will be required when server push some mesage to delivery partner or user to know which connection to use.

5. When user order the food, system assign the best possible Delivery Partner:

As mention in the functional requirement, user should get the order in minimum time and delivery partner must travel as less as possible.

To order the food, we will have a new service say Order service. Order service will have its own SQL DB. Here are the tables:

Order

id
user_id
restaurant_id
payment_id
dpartner_id

OrderDetails:

order_id
restaurant_menu_item_id

For the order to complete, the payment will be done using Payment Service. Payment Service will connect with credit card company and restaurant's bank to complete the payment using third party payment service.

Once the payment is done, order service queue the message to Notification service and Notification service push the notification to Retaurant. Restaurant then fetch the order details from order service and set the state of order as approved by calling Order Service API.

To match the delivery partner, we will have a new service Matching Service. Let's see what it does to match the delivery partner to an order.

Matching service send the user's and restaurant's location to Location service
Location service finds all the closed available delivery partners by drawing a circle of 2 - 3 KMs. Restaurant could be the center of the circle.
Location service now sends the triplet {partner_location, restaurant_location, user_location} to a third party service.
Third party service sends the ETA for every every triplet.
Location service then send the {partner_id, ETA} to matching service.

Matching service will then match the partner with order based on ETAs and other criterias. Once matched, Matching service will send the Location service {partner_id, order_id} and Location Service will save order_id corresponding to partner_id to indicate that delivery partner is serving an order.

Now Matching Service will send {order_id, partner_id} to Order Service which will update the partner_id corresponding to order_id.

Once the partner_id is saved, Order Service queue another message with order info like restaurant location, user location and order_id to Notification service which pushes these details to delivery partners.

6. User should be able to track their orders

Once the User reaches to order tracking page, user app creates an WSS connection with a new service say Order Tracking Service. Here is the flow:

Once the order is confirmed and delivery partner is assigned, it queues the order_info like order_id, user_id, state, dpartner_id etc to Order Tracking Service.
Whenever restaurant update order state using Order Service API, Order Service also queue this order_info to Order Tracking Service.
Location Service when it sees that and order_id is attached the delivery partner id, then it queues the order_id, location to Order Tracking Service.
Order Tracking Service maintains redis cache to store this info.
When user creates an WSS with Order Tracking Service, it also sends it to Connection Manager Service to store it.
When Order Tracking Service receives any messages, it first checks with Connection Manager to get the connection id and use the connection id to send the update to User.

So this is architectural diagram for order placement and tracking:

7. Delivery partner should be able to mark the order state:

Delivery partners can simply call Order service to mark the order state. With this, this is the compelet flow of Orders:

8. User should be able to rate delivery partners and restaurants:

For this FR we can have another service say Rating service. It will have its own SQL DB. We can have different tables or we can use the same table for both restaurants and delivery partners with one more column say type but I am going to use different tables.

Both tables have the same schema:

RestaurantRating

user_id
restaurant_id
rating
created_at

DPartnerRating

user_id
dpartner_id
rating
created_at

In this way we can also restrict same user to rate restaurants or delivery Partners multiple times. Now we also show restaurant's and delivery partner's rating to users. I know we are not handling NFRs for now but I am handling little performance right now. Otherwise to show details of restaurants or partners we need to make 2 calls (restaurant/dpartner and rating). We are going to use timer jobs at Restaurant Service and DPartner Service which will run at scheduled interval say every 1/2/4/8 hours and fetch the data from Rating service using created_at field and then calculate rating and save it in their own DB.

9. User should be able to search restaurants and menu items.

For this we have already a Search Service which is using Elastic Search. Restaurant Service is already pushing the data there on onboarding or updates.

10. User should be able to see the top rated nearby restaurants on home page:

This is little tricky but we will deal with it during NFRs handling for now, you can see we have every data available at Restaurant Service DB and we can fetch this from its DB only and show it to user.

Step 3: Mapping non functional requirments to architectural diagram:

1. Scalability:

For achieving the scalability we need to have multiple instances of each service and also replicas of DBs.

2. Availabilty:

We have already achieved it using multiple instances and replicas of DBs,

3. Performance:

a. Search < 200 ms

For search performance we already are using Elastic search which should serve the purpose. If required we can add additional details like rating, state in the Elasic Search.

b. Home page load < 500 ms

Here we need to show the Top rated nearby restaurants around the user location but as of now it is not possible as we are storing lat and long.

We can use Geohash here to divide the earch into geo cells. Now these geo cell ids will be stored in the Restaurant DB as per the restaurant's locations. That means we are going to add a new table RestaurantLocation table in the Restaurant DB. Here is the schema:

geo_cell_id
restaurant_id
restaurant_name
restaurant_rating

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 getting the nearby restaurants:

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 this query efficient, we can partition this table based on geo_cell_id.

If it is still required we can cache top restaurnts of geo_cell_ids in the Redis.

* For matching Delivery Partners we will use the same approach of geo hash and a column "geo_hash_id" will be added to Location DB. Just like what we did in design of uber.

c. Menu load < 500 ms

There are four tables; Restaurants, RestarantMenu, RestaurantMenuItem and MenuItems, we need to join if we want to get the whole menu which is making this very inefficient. What we can do is maintain another table, RestaurantMenuCache which will just have following fields:

restaurant_id
menu_blob
last_updated_at

We can partition based on restaurant_ids but on range based method to make it more efficient.

d. CP over AP

We are already using SQL DB where consistency is required.

In this post, we methodically designed a scalable, consistent, and performant food delivery application from scratch. We identified critical services, database designs, WebSocket communication for real-time updates, and employed techniques like Geohashing for efficient geo-based queries.

We also mapped our non-functional requirements (NFRs) like scalability, performance, availability, and consistency across the architecture, ensuring that the system remains robust even at 100M users and 10M daily orders scale.

This design is a strong foundation. In a real-world scenario, we can extend it further by adding observability, security layers, fallback mechanisms and cost optimizations.

[Netflix Tech Blog] Inside Netflix's Ads Event Engine: A Deep Dive (Part 2)

2025-06-20T17:33:00.003+05:30

In Part 1, we explored how Netflix moved from a bloated token model to a more elegant, scalable architecture using a centralized Metadata Registry Service (MRS). That shift allowed Netflix to scale its ad event tracking system across vendors, while keeping client payloads small and observability high.

But Netflix wasn’t done yet.

Netflix built it's own Ad tech platform: Ad Decision Server:

Netflix made a strategic bet to build an in-house advertising technology platform, including its own Ad Decision Server (ADS). This was about more than just cost or speed, it was about control, flexibility, and future-proofing. It actually began with a clear inventory of business and technical use cases:

In-house frequency capping
Pricing and billing for impression events
Robust campaign reporting and analytics
Scalable, multi-vendor tracking via event handler

But this Ad Event Processing Pipeline needed a significant overhaul to:

Match or exceed the capabilities of existing third-party solutions
Rapidly support new ad formats like Pause/Display ads
Enable advanced features like frequency capping and billing events
Consolidate and centralize telemetry pipelines across use cases

Road to a versatile and unified pipeline:

Netflix recognized future ad types like Pause/Display ads that would introduce variant telemetry. That means the upstream telemetry pipelines might vary, but downstream use‑cases remain largely consistent.

So what is upstream and what is downstream in this Netflix event processing context:

Upstream (Producers of telemetry / Events): This refers to the systems and sources that generate or send ad-related telemetry data into the event processing pipeline.

Example of upstream in this context:

Devices (Phones, TVs, Browsers)
Different Ad Types (eg. Video Ads, Display Ads, Pause Ads)
Ad Media Players
Ad Servers

These upstream systems send events like:

Ad Started
Ad Paused
Ad Clicked
Token for ad metadata

These system may:

Use different formats
Have different logging behavior
Be customized per ad type or region

Downstream (Consumers of processed data): This refers to the systems that consume the processed ad events for various business use cases.

Example of downstream in this context:

Frquency capping service
Billing and pricing engine
Reporting dashboards for advertisers
Anlytical systems (like Druid)
Ad session generators
External vendor tracking

These downstream consumers:

Expect standardized, enriched, reliable event data
Rely on consistent schema
Need latency and correctness guarantees

So "upstream telemetry pipelines might vary, but downstream use‑cases remain largely consistent" means:

Even if ad events come from diverse sources, with different formats and behaviors (upstream variation),
The core processing needs (like billing, metrics, sessionization, and reporting) remain the same (downstream consistency).

Based on that they outline a vision:

Centralized ad event collection service that:

Decrypts tokens
Enriches metadata (via the Registry)
Hashes identifiers
Publishes a unified data contract, agnostic of ad type or server

All consumers (for reporting, capping, billing)/read from this central service, ensuring clean separation and consistency.

Building Ad sessions & Downstream Pipelines:

A key architectural decision was "Sessionization happens downstream, not in the ingestion flow" but what does that mean? Lets break it down:

Ingestion flow (Upstream): This is the intial (real time) path where raw ad telemetry events are ingested into the system, like:

Ad started playing
User clicked
25% of video watched

These events are lightweight, real time and are not yet grouped into a meaningful session. Think of it as raw, granular events flying into Kafka or a central service.

Sessionization (Downstream Processing): This is a batch or stream aggregation process where the system:

Looks at multiple ad events from the same ad playback session
Groups them together
Creates a meaningful structure called an "Ad Session"

An Ad session might include:

When did the ad start and end
What was the user's interaction (viewed / clicked / skipped)
Was it complete or partial view
What was pricing and vendor context

So "Sessionization happens downstream, not in the ingestion flow" means:

The ingestion system just collects and stores raw events quickly and reliably.
The heavier work of aggregating these into a complete session (sessionization) happens later, in the downstream pipeline where there is:

More time
Access to more context
Better processiong capabilities

Why it was required?

Separation of concerns: Ingestion stays fast and simple; sessionization logic is centralized and easier to iterate on.
Extensibility: You can add new logic to sessionization without touching ingestion.
Scalability: Real time pipelines stay light; heavy lifting is done downstream.
Consistency: One place to define and compute what an "ad session" means.

They also built out a suite of downstream systems:

Frequency Capping
Ads Metrics
Ads Sessionizer
Ads Event Handler
Billing and revenue jobs
Reporting & Metrics APIs

Final Architecture of Ad Event Processing:

Ad Event Processing Pipeline

Here is the breakdown of the flow:

Netflix Player -> Netflix Edge:

The client (TV, browser, mobile app) plays an ad and emits telemetry (e.g., impression, quartile events).
These events are forwarded to Netflix’s Edge infrastructure, ensuring low-latency ingestion globally.

Telemetry Infrastructure:

Once events hit the edge, they are processed by a Telemetry Infrastructure service.
This layer is responsible for:

Validating events
Attaching metadata (e.g., device info, playback context)
Interfacing with the Metadata Registry Service (MRS) to enrich events with ad context based on token references.

Kafka:

Events are published to a Kafka topic.
This decouples ingestion from downstream processing and allows multiple consumers to operate in parallel.

Ads Event Publisher:

This is the central orchestration layer.
It performs:

Token decryption
Metadata enrichment (macros, tracking URLs)
Identifier hashing
Emits a unified and extensible data contract for downstream use

Also writes select events to the data warehouse to support Ads Finance and Billing workflows.

Kafka -> Downstream Consumers:

Once enriched, the events are republished to Kafka for the following consumers:

Frequency Capping:

Records ad views in a Key-Value abstraction layer.
Helps enforce logic like “don’t show the same ad more than 3 times per day per user.”

Ads Metrics Processor:

Processes delivery metrics (e.g., impressions, completion rates).
Writes real-time data to Druid for interactive analytics.

Ads Sessionizer:

Groups related telemetry events into ad sessions (e.g., full playback window).
Feeds both data warehouse and offline vendor integrations.

Ads Event Handler:

Responsible for firing external tracking pixels and HTTP callbacks to third-party vendors (like Nielsen, DoubleVerify).
Ensures vendors get event pings per their integration needs.

Analytics & Offline Exchange:

The sessionized and aggregated data from the warehouse is used for:

Offline measurement
Revenue analytics
Advertiser reporting

Benefits of design:

Principle	Implementation
Separation of concerns	Ingestion (Telemetry Infra) ≠ Enrichment (Publisher) ≠ Consumption (Consumers)
Scalability	Kafka enables multi-consumer, partitioned scaling
Extensibility	Central Ads Event Publisher emits a unified schema
Observability	Real-time metrics via Druid; sessionized logs via warehouse
Partner-friendly	Vendor hooks via Event Handler + Offline exchange

By centralizing sessionization and metadata logic, Netflix ensures that:

Client-side logic remains lightweight and stable
Backend systems remain flexible to change and easy to audit

Few clarificatons:

1. What is the Key-Value (KV) abstraction in Frequency Capping?

In Netflix’s Ad Event Processing Pipeline, frequency capping is the mechanism that ensures a user doesn’t see the same ad (or type of ad) more than a specified number of times e.g., “Don’t show Ad X to user Y more than 3 times a day.”

To implement this efficiently, Netflix uses a Key-Value abstraction, which is essentially a highly scalable key-value store optimized for fast reads and writes.

How it works:

Key: A unique identifier for the "audience + ad + context"

Example: user_id:ad_id:date

Value: A counter or timestamp that tracks views or interactions

Example: {count: 2, last_shown: 2025-06-20T12:15:30}

Let's understand it by example:

Key	Value
user123:ad789:2025-06-20	{ count: 2, last_shown: 12:15 }
user123:ad456:2025-06-20	{ count: 1, last_shown: 10:04 }

When a new ad event comes in:

Netflix looks up the key
Checks the count
If under the cap (e.g., 3), they allow it and increment the counter
If at or above cap, the ad is skipped or replaced

Why "Abstraction"?

Netflix may use multiple underlying KV stores (like Redis, Cassandra, or custom services), but abstracts it behind a unified interface so:

Ad engineers don’t worry about implementation
Multiple ad systems can share the same cap logic
It can scale across regions and millions of users

Benefits:

Feature	Why it matters
Speed	Real-time lookups for every ad play
Scalability	Handles millions of users per day
Flexibility	Supports different capping rules
Multi-tenancy	Can cap by user, device, campaign, etc.

2. What is Druid and why it is getting used here?

Apache Druid is a real-time analytics database designed for low-latency, high-concurrency, OLAP-style queries on large volumes of streaming or batch data.

It’s built for interactive dashboards, slice-and-dice analytics, and fast aggregations over time-series or event data.

Think of it as a high-performance hybrid of a data warehouse and a time-series database.

Netflix uses Druid in the Ads Metrics Processor and Analytics layer. Here’s what it powers:

Streaming Ad Delivery Metrics

As ads are played, Netflix captures events like:

Impressions
Quartile completions (25%, 50%, etc.)
Clicks, errors, skips

These events are streamed and aggregated in near-real-time via Flink or similar streaming processors
Druid ingests these metrics for interactive querying.

Advertiser Reporting and Internal Dashboards

Ad operations teams and partners want to know:

"How many impressions did Ad X get in Region Y yesterday?"
"What's the completion rate for Campaign Z?"

These queries are run against Druid and return in milliseconds, even over billions of records

Why Nerflix uses Druid (instead of just a data warehouse like Redshift or BigQuery)?

Feature	Why it matters for Netflix Ads
Real-time ingestion	Metrics appear in dashboards within seconds of the event
Sub-second queries	Advertiser reports and internal dashboards need speed
High concurrency	Supports thousands of parallel queries from internal tools
Flexible aggregation	Group by ad_id, region, time, device_type, etc. instantly
Schema-on-read & roll-ups	Druid efficiently stores pre-aggregated data for common metrics

Conclusion:

As Netflix shifted toward building its own advertising technology platform, the Ads Event Processing Pipeline evolved into a thoughtfully architected, modular telemetry platform capable of handling diverse ad formats, scaling globally, and meeting the demands of both real-time analytics and long-term reporting.

This transformation was not just about infrastructure, but about platformization:

A centralized event publisher that abstracts complexity.
A unified schema that serves a wide range of downstream consumers.
A clean separation of concerns that allows rapid innovation in ad types without touching backend logic.
Observability and control, made possible through systems like Druid and the Metadata Registry Service.

With this evolution, Netflix ensured:

Scalability: Handling billions of ad events across regions and devices
Agility: Enabling quick integration of new ad formats like Pause/Display Ads
Partner alignment: Supporting vendor integrations with minimal friction
Business confidence: Powering frequency capping, billing, and reporting with precision

Here is the original Netflix blog.

[Netflix Tech Blog] Inside Netflix's Ads Event Engine: A Deep Dive (Part 1)

2025-06-16T20:12:00.000+05:30

As Netflix steps into the ad-supported streaming world, its engineering backbone must operate with the same level of scale, reliability, and precision that powers its core viewing experience. But building a system that can track billions of ad events like impressions, clicks, quartile views, across diverse devices and ad partners is anything but trivial.

In this two-part series, I’ll dissect the architecture behind Netflix’s Ads Event Processing Pipeline, inspired by their tech blog. Part 1 focuses on the early phase, from ad request initiation to the evolution of encrypted tokens and the eventual need for a Metadata Registry Service. You'll see how Netflix tackled key design challenges such as bandwidth optimization, cross-device compatibility, vendor flexibility, and observability at scale.

If you're interested in distributed systems, real-time telemetry, or just want to peek behind the curtain of Netflix’s ad tech, you’re in the right place.

Let’s dive in!

The Initial System (Pilot) At a Glance:

When a Netflix-supported device is ready to show an ad, it doesn’t pick an ad on its own. Instead, the system goes through the following high-level steps:

Client Ad Request: The device (TV/mobile/browser) sends a request to Netflix’s Ads Manager service when it reaches an ad slot.
VAST Response from Microsoft Ad Server: Ads Manager forwards this request to the Microsoft’s ad server, which returns a VAST XML. This contains the actual ad media URL, tracking pixels, and metadata like vendor IDs and macros.
Encrypted Token Created: Instead of sending this raw VAST data to the device, Ads Manager:

Extracts relevant metadata (e.g., tracking URLs, event triggers, vendor IDs)
Encodes it using protobuf
Encrypts it into a compact structure called a token
Sends this token along with the actual ad video URL to the device

Ad Playback and Event Emission: As the ad plays, the device emits telemetry events like impression, firstQuartile, click etc., attaching the token to each event.
Event Processing via Kafka: These events are queued in Kafka, where the Ads Event Handler service reads them, decrypts the token, interprets the metadata, and fires the appropriate tracking URLs.

Ad Events flow

What is VAST?

VAST stands for Video Ad Serving Template. It’s an XML-based standard developed by the IAB (Interactive Advertising Bureau) to standardize the delivery of video ads from ad servers to video players (like Netflix's video player). In simpler terms:

VAST is a template that tells the video player:
What ad to play
Where to find it
How to track it (e.g., impressions, clicks, view progress)

Key Parts of a VAST Response:

Ad Media URL

Link to the video file
The player will use this to stream the ad.

<MediaFile delivery="progressive" type="video/mp4" width="640" height="360">
    https://adserver.com/path/to/ad.mp4
</MediaFile>

Tracking Events

URLs the player should "ping" (via HTTP GET) when certain things happen:

Impression (ad started)
FirstQuartile (25% watched)
Midpoint (50% watched)
ThirdQuartile (75% watched)
Complete (100%)
Click (User clicked the ad)

<TrackingEvents>
  <Tracking event="impression">https://track.com/imp</Tracking>
  <Tracking event="firstQuartile">https://track.com/q1</Tracking>
  ...
</TrackingEvents>

Click Tracking

URL to notify when the user clicks the ad.
Destination URL (where user is taken on click).

<VideoClicks>
  <ClickThrough>https://brand.com</ClickThrough>
  <ClickTracking>https://track.com/click</ClickTracking>
</VideoClicks>

Companion Ads (Optional)

Static banner or rich media that shows alongside the video ad

Why VAST?

Purpose	How it helps
Standardization	All ad servers speak the same language to video players
Tracking	Advertisers know when/how their ads were shown
Flexibility	Supports linear, companion, and interactive video ad formats
Easy integration	Netflix could plug in with Microsoft without building a custom API

Why Netflix chose protobuf and not Json:

Token size matters on client devices: Protobuf is highly compact, small tokens means less overhead. For example, a JSON payload that’s 1 KB might only be 100–200 bytes in protobuf.
Performance: Ad events are high volume (billions per day). Protobuf parsing is much faster than JSON, both on backend and client.
Encryption efficiency: Netflix encrypted the protobuf payload to create the token. Encrypting a compact binary blob is faster and lighter than encrypting JSON text.
Schema Evolution and Compatibility: Protobuf supports versioning, optional/required fields and backward/forward compatibility. That means Netflix could evolve the ad metadata schema without breaking clients or backend systems. JSON lacks this.

Feature	JSON	Protobuf
Format	Text-based	Binary (compact)
Size	Larger	Much smaller
Parse performance	Slower	Faster
Schema enforcement	No (free-form)	Yes (strongly typed schema)
Encryption impact	Heavier (more bytes to encrypt)	Lighter (smaller encrypted payload)
Tamper resistance	Weaker (can be read/edited)	Stronger (harder to interpret)

Why Kafka over other queues like RabitMQ:

Massive Scale and Parallelism

Kafka can handle billions of events/day, easily.
Partitions allow horizontal scaling of consumers:

e.g., 100 partitions means 100 consumers i.e. massive parallel processing.

RabbitMQ struggles when you need high fan-out and high throughput.

Event Replay and Reliability

Ad tracking must be durable (e.g., billing, audits)
Kafka stores messages on disk with configurable retention (e.g., 7 days)
If a service fails, it can re-read from the last offset i.e. no data lost.
RabbitMQ can lose messages unless you enable heavy persistence (with a perf hit).

Built-in Partitioning and Ordering

Kafka guarantees message ordering per partition.
Ads Event Handler can partition by:

ad_id, device_id, etc.

This ensures all related events are processed in order, by the same consumer.

Topic: ad_events
Partitions: 100
Key: device_id (events from same device always lands in same partition)

Problem in the Pilot System: The Token got too smart

In the pilot, the Ads Manager was:

Extracting all tracking metadata from the VAST (like URLs, vendor IDs, event types)
Packing all of it into a token (as protobuf)
Encrypting and sending this token to the client
The token was self-contained — everything the backend needed to fire tracking URLs was inside it

It worked for small scale but it didn't scale:

As Netflix onboarded multiple ad partners (e.g., Nielsen, DoubleVerify, Microsoft, etc.), each vendor wanted:

Their own tracking logic.
Unique macros to be replaced in URLs
Complex conditional tracking rules
Custom logic based on device type, timing, campaign, etc.

What are these macros we are talking about:

Macros are placeholder variables in tracking URLs that get dynamically replaced with actual values at runtime, before the URL is fired.

They let ad vendors capture contextual information like:

The timestamp when an ad was viewed
The type of device
Whether the user clicked or skipped
The playback position, etc.

Example:

A vendor might provide a tracking URL like:

https://track.vendor.com/pixel?event=impression&ts=[TIMESTAMP]&device=[DEVICE_TYPE]

Here:

[TIMESTAMP] is a macro for when the ad started playing
[DEVICE_TYPE] is a macro for the kind of device (TV, phone, etc.)

Before this URL is fired, those macros must be resolved to actual values:

https://track.vendor.com/pixel?event=impression&ts=1717910340000&device=tv

Why Macros become a problem at scale:

Inconsistent Syntax Across Vendors

Some used [TIMESTAMP], others used %ts%, or even custom placeholders.
Netflix had to implement logic per partner to resolve them correctly.

Dynamic Values Grew

New use cases brought in more macros: region, episode title, ad ID, player version, UI language, etc
Supporting new macros meant:

Updating the token schema
Updating Ads Manager logic
Sometimes even updating clients

Difficult to Test or Validate

Because everything was encrypted in the token, validating whether macros were substituted correctly was hard.
A bug in macro resolution could break tracking silently.

This meant the token payload was growing; more vendors, more metadata, more per-event config.

So to summarize the problems, here is the table:

Problem	Why it hurt
Payload bloat	Token size increased → slower to transmit → harder to encrypt
Hard to evolve	Any schema change required new client logic and re-deployment
No dynamic behavior	Logic was fixed at ad decision time; couldn’t update later
Redundant processing	Every token had repeated config for the same vendors
Hard to debug/troubleshoot	No human-readable registry of how tokens should behave

How did Netflix solve the problem: Meatdata Registry Service (MRS):

To overcome the scaling bottlenecks of self-contained tokens, Netflix introduced a new component: the Metadata Registry Service (MRS).

Its core idea was simple but powerful, separate the metadata from the token. Instead of encoding everything inside the token, Netflix now stores reusable metadata centrally in MRS, and the token merely references it via an ID.

How MRS works:

Ads Manager Gets VAST: Ads Manager still fetches the VAST response from the ad decisioning system (e.g. Microsoft’s ad server).
Metadata Extracted & Stored: Instead of encrypting all metadata into a token, Ads Manager:

Extracts metadata (tracking pixels, macros, event mappings, etc.)
Stores it in Metadata Registry Service (MRS) with a registry key

Token Now Just an Id: The token now just contains:

The registry key
A small payload (e.g. dynamic fields like ad_start_time or session ID)

Device Sends Events with Token: Devices emit telemetry events with this lightweight token.
Backend Looks Up MRS: Ads Event Handler uses the registry key to:

Fetch the tracking metadata from MRS
Apply macros
Fire tracking URLs

Ad Events flow with MRS

So summary of what exactly changed:

Before MRS	After MRS
Token = All tracking logic inside	Token = Just a reference id
Tracking metadata repeated often	Metadata stored once in registry
Hard to update or debug	Dynamic updates via registry
Schema tightly coupled to client	Centralized schema owned by server

Benefits of MRS approach:

Dynamic Metadata Updates

Vendor changes their URLs or macro format? Just update MRS.
No need to redeploy client or regenerate tokens.

Improved Performance

Tokens are smaller means less encryption overhead, less network cost.
Registry entries are cached means fast and efficient.

Better Observability

MRS is a source of truth for all campaign metadata.
Easy to search, debug, and trace logic across vendors and campaigns.

Reusability

Multiple campaigns can reference the same registry entry.
No duplication of tracking logic.

Separation of Concerns

Client focuses on playback and telemetry.
Backend owns tracking logic and event firing.

* You might be thinking there is no logic in client for tokens i.e. the logic to fire tracking pixels was not on the client. The client just played the ad and emitted telemetry events along with the token so why client redeployment is in the picture even without MR. According to me, the protobuf schema can become a bottlenec here as the schema changes, client code also need a change. With MRS we can freeze the client payload schema.

In this first part of our deep dive into Netflix’s Ads Event Processing Pipeline, we traced the evolution from a tightly-coupled, token-heavy system to a more modular and scalable architecture powered by the Metadata Registry Service (MRS).

By decoupling metadata from tokens and centralizing macro resolution and tracking logic, Netflix unlocked:

Smaller, lighter tokens
Faster and safer iteration
Dynamic partner integration
Debuggability at scale

What started as a necessary fix for bloated tokens ended up becoming the foundation for a much more agile and partner-friendly ad tracking ecosystem.

But Netflix didn’t stop there!

In [Part 2], we’ll explore the next big leap: how Netflix brought ad decisioning in-house — giving them end-to-end control over targeting, creative rotation, pacing, and auction logic and how this plugged seamlessly into the MRS-backed pipeline we just explored.

We will learn how they:

Built an Ad Decision Server (ADS) from scratch
Integrated it with the metadata pipeline
Enabled real-time, personalized ad serving on a global scale

Thanks a lot and stay tuned, the story gets even more fascinating.

Design Uber

2024-10-28T20:54:00.000+05:30

Problem: Design a highly scalable rideshare service.

Requirements:

1. Functional requirements:

Only registered users can request a cab.

Driver registration is manual and is out of scope here.

Driver and user needs to login to request and receive the ride.
Driver needs to make himself available to receive the rides.
Each driver can be matched to multiple riders depends on users and the occupancy of the car.
Price of the ride depends on base flat fee, distance and duration.

Exact formula is not given and is subject to change

We need to minimize the:

Wait time of users
Distance / Time for drivers to pickup the user.

Collect payment information from users.
Collect bank information of drivers to pay them.
Driver should start/end the trip.
For actual payment process, we can use third party services.

2. Nonfunctional requirements:

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

Availability:

99.99% uptime or higher

Performance:

Match users with drivers 10 seconds at 99 percentile

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:

Get the closest drivers list to the rider.
Get the ETA of these drivers from third party service.
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

2024-10-28T02:22:00.021+05:30

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:

Upload any format/codec video.

Once the video is uploaded, it can be deleted but not be modified.

Each video should have metadata:

Mandatory: title, author, description.
Optional: List of categories / tags.
Metadata can be updated anytime.

Get an email notification when the video is available publically.
Live streaming is not supported.

b. Viewers:

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

2. Nonfunctional requirements:

a. Content creators:

Scalability:

Thousands of content creators.
Upload 1video/week per creator
Average video size ~50 GB (50 TB / week)

Consistency:

We prefer to have consistency here over availability.

Availability:

99.9 percentile

Performance:

Response time of page load < 500 ms at 99 percentile.
Video becomes available to view in hours.

b. Viewers:

Scalability:

100K-200K daily active users

Availability:

99.99 percentile

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:

Content creator call Video service to upload video.
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.
Once the video upload is complete to object store, it queues this message to a new service Transcoding service.
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.
Transcoding service now queue the message to new service say Packaging service.
Packaging service package these streams according to streaming protocols and save it into it's own object store.
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:

Client send request for video upload to video service.
Video service requests presigned url from object store with it's own permissions.
Send the presigned url as response of video upload API to the client.
Client now directly upload the video to object store using presigned url.
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

2024-10-18T19:52:00.008+05:30

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

Requirements:

1. Functional Requirements:

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.

User can share/post only images

We need to design it in a way to extend it to videos or text.

Search a user using different attibutes
Unidirectional relationship: User A follows User B does not mean User B also follows User A.
Load a timeline of latest images posted by people they follow sorted by recency in descending order

2. Non-functional Requirements:

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

Availability: Prioritize availability over consistency as it is okay even if user does not see the latest data. We are targetting 99.99% here.
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

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

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:

User send the request to Post service to share an image
Post service send the image to object store
Object store return the url of uploaded image
Save the image metdata and url in the DB
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:

follower_user_id
target_user_id
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:

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

Define which user is celebrity; Say a celebrity has 1 M followers.
Make a column in User DB - IsCelebrity which will tell if the user is a celebrity or not.
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.
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.
When Timeline service receive IsCelebrity as true. It just add the post into Celebrity POST DB.
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.
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

2024-10-04T01:43:00.004+05:30

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

2024-10-04T00:37:00.005+05:30

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

2024-10-03T21:06:00.006+05:30

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)

[LeetCode] Search Insert Position

2024-10-03T20:44:00.006+05:30

Problem: Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example:

Input: nums = [1,3,5,6], target = 5
Output: 2

Input: nums = [1,3,5,6], target = 2
Output: 1

Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums contains distinct values sorted in ascending order.
-10^4 <= target <= 10^4

Approach: The problem here is just to find the target itself or just greater element in the array so if you see this is a binary search problem with following changes:

If nums[mid] < target then obviously we need to go to the right side i.e. start = mid + 1
Else end = mid
Return end.

Implementation in C#:

    public int SearchInsert(int[] nums, int target) 
    {
        int start = 0, end = nums.Length - 1 ;
        if (target < nums[start])
        {
            return start;
        }
        if (target > nums[end])
        {
            return end + 1;
        }
        while (start < end)
        {
            int mid = start + (end - start) / 2;
            if (nums[mid] < target)
            {
                start = mid + 1;
            }
            else
            {
                end = mid;
            }
        }    
        return end;
    }

Complexity: O(log(n))

[LeetCode] Find Smallest Letter Greater Than Target

2024-10-03T20:24:00.008+05:30

Problem: You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.

Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters

Example:

Input: letters = ["c","f","j"], target = "a"
Output: "c"
Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'

Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.

Input: letters = ["x","x","y","y"], target = "z"
Output: "x"
Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].

Constraints:

2 <= letters.length <= 10^4
letters[i] is a lowercase English letter.
letters is sorted in non-decreasing order.
letters contains at least two different characters.
target is a lowercase English letter.

Approach: This is a simple binary search problem with following changes:

If letters[mid] <= target then obviously we will search on the right side so start becomes mid + 1.
Else we go to the left to see there is a smaller letter which is greater than target so end becomes mid.
In the end we return letters[end]

Implementation in C#:

    public char NextGreatestLetter(char[] letters, char target)
    {
        int start = 0, end = letters.Length - 1;
        if (target < letters[start] || target >= letters[end])
        {
            return letters[start];
        }
        while (start < end)
        {
            int mid = start + (end - start) / 2;
            if (letters[mid] <= target)
            {
                start = mid + 1;
            }
            else
            {
                end = mid;
            }
        }
        return letters[end];
    }

Complexity: O(log(n))

[LeetCode] 2 Keys Keyboard

2024-08-19T18:18:00.006+05:30

Problem: There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step:

Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
Paste: You can paste the characters which are copied last time.

Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

Example:

Input: n = 3
Output: 3
Explanation: Initially, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Input: n = 1
Output: 0

Approach: We are going to use bottom-up DP here. We can define a 1D array where table[i] tells the minimum number of steps required to display i A's. Obviously table[n] will be our answer.

Now the main logic here is to get the relations between table[i] and table[i-1]...table[1], right? Let's understand it; let's say we had j A's on the screen where 1 <= j < i. Now we can say we can copy these j A's and paste it exactly (i - j) / j times to display i A's so total number of operations will be:

f(i) = f(j) + 1 + (i - j) / j

Why? Let's see:

f(j) - Number of steps to display j A's
1 - Copy All
(i - j) / j - Number of pastes.

Now let's simplify this equation:

f(i) = f(j) + 1 + (i - j) / j

=> f(i) = f(j) + 1 + (i/j) - (j/j)

=> f(i) = f(j) + 1 + (i/j) - 1

=> f(i) = f(j) + i / j

So here is our final relation:

f(i) = f(j) + i / j

We also need to make sure that i should be divisible by j as it's kind of repeated pastes. Now we just need to get the minimum of all such j's where 1 <= j < i and i is divisible by j.

That's all!

Implementation in C#:

    public int MinSteps(int n)
    {
        if (n <= 1)
        {
            return 0;
        }
        int[] table = new int[n + 1];
        for (int i = 2; i <= n; ++i)
        {
            table[i] = int.MaxValue;
            for (int j = 1; j <= i / 2; ++j)
            {
                if (i % j != 0)
                {
                    continue;
                }
                table[i] = Math.Min(table[i], table[j] + i / j);
            }
        }
        return table[n];
    }

Complexity: O(n^2)

Design Stack overflow

2024-08-15T02:43:00.010+05:30

Problem: Design a highly scalable public discussion forum like reddit, quora or Stack Overflow. Here are the features that needs to be supported:

Post questions / news to public
Comments on existing posts
Upvote/downvote posts or comments
Feed of most popular posts.

Requirements:

Functional requirements:

This is browser only application.
A logged in user only can post, comment and vote.
A post contains following:

Title
Tags
Body containing text and image

Any user (logged in) can comment on any post.
Comments are shown as list in descending order by time.
Use can delete his/her own comments or posts.
Any user can vote any post or comment.
A user's home page contains the top popular posts in the last 24 hours where:

Popularity = Upvotes - Downvotes

Non functional requirements:

Scalabilty: Millions of daily users.
Performance: 500 ms response time 99 percentile.
Availability: Priority to availability over consistency as it is ok if the user won't see the latest data.
Durability: Have posts and comments till the user doesn't delete it.

Design: Now that the requirements are clear. We will start with our design.

Step 1: API design:

We will first try to come up with the Rest APIs as per our functional requirements. For this we need to first identify what are the entities in our system and try to map those to URIs

Users:

/users
/users/{user-id}

Posts:

/posts
/posts/{post-id}

Images

/posts/{post-id}/images
/posts/{post-id}/images/{image-id}
/posts/{post-id}/comments/{comment-id}/images
/posts/{post-id}/comments/{comment-id}/images/{image-id}

Comments

/posts/{post-id}/comments
/posts/{post-id}/images/{comment-id}

Votes

/posts/{post-id}/vote
/posts/{post-id}/comments/{comment-id}/vote

Let's see how the post looks like: (response of GET)

{

post_id: string

title: string

tags: List of strings

user_id: string

upvotes: int

downvotes: int

body: json

}

Let's see how the comment looks like: (response of GET):

{

post_id: string

comment_id: string

body: json

user_id:

upvotes: int

downvotes: int

}

Now that we know the entities and URIs, its time to assign the HTTP method which wll ultimately results ino our final APIs:

Users:

POST /users/ - Create/signup a new user
POST /users/login - Login a user

Posts:

POST /posts - Create a new post
GET /posts - View posts. Response of this requires pagination as it can contain even 1 million posts so the parameters can be:

limit
offset
user_id (optional)

GET /posts/post-id - View a post
DELETE /posts/post-id - Delete a post

Comments:

POST /posts/{post-id}/comments - Create new comment
GET /posts/{post-id}/comments - View post's list of comments
GET /posts/{post-id}/comment/{comment-id} - View a comment
DELETE /posts/{post-id}/comment/{comment-id} - Delete a comment

Votes:

POST /posts/{post-id}/vote - Upvote/downvote a post
POST /posts/{post-id}/comments/{comment-id}/vote - Upvote/downvote a comment

Images:

POST /posts/{post-id}/images - Upload a image to a post body
GET /posts/{post-id}/images/{image-id} - Get an image of post
POST /posts/{post-id}/comments/{comment-id}/images - Upload a image to a comment body
GET /posts/{post-id}/comments/{comment-id}/images/{image-id} - Get an image of a comment

Step 2: Mapping functional requirements to architectural diagram:

1. Browser only application: For this we will have web app service which will serve static web pages.

2. User Sign up / login: We will have a user service and this service have its own DB to store user info which we can choose as SQL DB as it's going to be structured data and also its not going to be huge.

3. Create/Delete a post: Again for this we will have another microservice say post service which will have it's own DB. As these number of posts are going to be huge and also post schema, we may want to vary time to time, I am going to use Nosql DB for this.

Given we can upload an image in the post, we can use any blob store to save the imges so if the post contains the image, a request will go to web app service which will upload the image to blob store and then take the image-id and put it in the post body and send a request posts service to save the post

While viewing the post, first we will get the post content using the posts service and then when the browser sees the image url, it can directly fetch from the blob store using the url.

4. Posting comments / Deleting comments:

5. Comments are shown in list in descending order of posting time:

We can use a different microservice Comments with it's own DB but we can merge it with Post service and use the same DB. As you see comments are tightly attached to post and also their schema is almost same except comments will have a post id attached to it. We also need to add a timestamp fields as we need to show comments in sorted order.

We can opt for any approach but I am choosing to have one micro service for posts and comments and calling it Post and Comment service.

If you see we are also satisfying FR 6: Deleting posts and comments here.

7. Upvote or downvote a post or comment: For this functionality, we will have a different service say Votes service with its on DB. Now we have a choice here:

We can just maintain a schema like folllows:

Post Id	count
Comment Id	count

But the problem with the above schema is

We can't restrict user to just vote once for a single post/comment.
FR 7: Can't get popular posts of last 24 hours.

That means we can't go wth the above schema. Hence here is the schema which I am proposing:

Post_id	User_id	Vote (+1 / -1)	Timestamp
Comment_id	User_id	Vote (+1 / -1)	Timestamp

With this we can at least achieve the functinalties including FR 7 too. We will see the performance part when we will address non functional requirements.

8: Home page contains the top popular posts: This is the most trickest functional requirement of this design. If you see the voting data is with Votes service and post content is with Posts service. Getting popular posts when the api call has been made could be very expensive. As this list is there in the home page, we can't risk of having delays in the page load.

To solve this issue we are going to use CQRS pattern. We are now going to introduce a Ranking microservice which will pull voting data from Votes service and post content from Post service. It then sort this data based on ranking and save this data into its own nosql DB. Now whenever the call for popular posts comes, it will be redirected to ranking service.

There are some consideration here:

We know that the sliding window here is 24 hours so rankng service can query only the posts which are kind of active in this window.
Given we don't have to show always the most recent data, we can use batch processing in the ranking service as this operation is heavy.

So here is what ranking service will do at a regular interval:

Get the active votes from voting service for last 24 hours.
Group the votes (upvotes - downvotes) by post_id.
Sort the post_ids in descending order according to votes.
Get the post content from POST service.
Save it in the DB.

So above is the final design of our product which is satisfying all the functional requirements. Now let's move to non functional requirements.

Step 3: Mapping non functional requirements to architectural diagram:

1. Scalablity: Given we are talkng about millions of active users, a single instance of service won't work. Obviously we need to have multiple instances of every services and a load balancer to balance the traffic.

Another scalability issue here is the large data of posts and comments so we are going to shard the Post and comments data.

For posts we can use hash based sharding with hashing on post_id. I know this can be a bottlenect if we have to show all the posts from a particular user as posts might be distributed among multiple shards but this is not even our functional requirement. If it is added then we can still serve it and with little tweaks we can serve it effficiently.

For comments we can't shard based on comment_id as in general the comments will be fetched according to post_id and if you see if we go with comment_id, we might end up retrieving comments from different shards which is a big performance issue.

So what we can do is we can shard the comments based on post_id using hash based sharding. This will work well but it will create problem when a post become popular it starts having too many comments then what will happen that a particular shard will become too big and can become the scalability issue and also performance bottleneck.

To handle such issue we can use a compound key (post_id, comment_id) and we can apply range based sharding. If we use it, mostly we will get data from one shard or at most two shards.

In this way we can handle the scalability.

2. Performance: There are multiple ways to make this system performant.

Image load time can be greater while fetching from the blob store. To avoid that we can use CDNs where we can store images of popular posts. We can also use CDNs to serve the static html pages too.
We can use cache to store the most popular posts and it's content in order to avoid traffic on GET requests of posts which are ultimately be directed to Posts service or Ranking service. Even the cache is not up to date, it is fine as we have chosen availability over consistency so eventual consistency is just fine.
Index on post_id for post collection and compound index(post_id, comment_id) on comment collection really can help on speeding up the Get requests. We can do the similar indexing on other DBs too.
Now another problem is, for a post/comment to load, we also need to show the upvotes and downvotes of the post or comment but votes data are there in Votes service DB so to load the post we need to call two microservice. We can take following steps to make it faster to fetch all post data or comment data including votes from one microservice only:

Two fields will be added to post and comments collection schema:

upvotes_count
downvotes_count

Queue the voting event from Votes service to Posts service so post service worker will fetch the events and can bulk update the DB with upvotes and downvotes count.

I think we are good with the performance point of view and now our system looks like following:

3. Availability: To achieve the availability we can replicate the databases and our services. We can also have our system running and replicated in different regions. This will also boost the performance.

4. Durability: We are already achiving the durability when we replicated the data accross regions. We can still periodically backed up our data to cheaper storage like S3 in order to have backups. This can also help us to cleanup old data from DBs to boost the performance if required.

Now that we have handled our every functional and non function requirements. Here is our final design:

That's all for this system design problem!

[LeetCode] Minimum Number of Pushes to Type Word II

2024-08-07T22:12:00.003+05:30

Problem: You are given a string word containing lowercase English letters.

Telephone keypads have keys mapped with distinct collections of lowercase English letters, which can be used to form words by pushing them. For example, the key 2 is mapped with ["a","b","c"], we need to push the key one time to type "a", two times to type "b", and three times to type "c" .

It is allowed to remap the keys numbered 2 to 9 to distinct collections of letters. The keys can be remapped to any amount of letters, but each letter must be mapped to exactly one key. You need to find the minimum number of times the keys will be pushed to type the string word.

Return the minimum number of pushes needed to type word after remapping the keys.

An example mapping of letters to keys on a telephone keypad is given below. Note that 1, *, #, and 0 do not map to any letters.

Example:

Input: word = "abcde"
Output: 5
Explanation: The remapped keypad given in the image provides the minimum cost.
"a" -> one push on key 2
"b" -> one push on key 3
"c" -> one push on key 4
"d" -> one push on key 5
"e" -> one push on key 6
Total cost is 1 + 1 + 1 + 1 + 1 = 5.
It can be shown that no other mapping can provide a lower cost.

Input: word = "xyzxyzxyzxyz"
Output: 12
Explanation: The remapped keypad given in the image provides the minimum cost.
"x" -> one push on key 2
"y" -> one push on key 3
"z" -> one push on key 4
Total cost is 1 * 4 + 1 * 4 + 1 * 4 = 12
It can be shown that no other mapping can provide a lower cost.
Note that the key 9 is not mapped to any letter: it is not necessary to map letters to every key, but to map all the letters.

Input: word = "aabbccddeeffgghhiiiiii"
Output: 24
Explanation: The remapped keypad given in the image provides the minimum cost.
"a" -> one push on key 2
"b" -> one push on key 3
"c" -> one push on key 4
"d" -> one push on key 5
"e" -> one push on key 6
"f" -> one push on key 7
"g" -> one push on key 8
"h" -> two pushes on key 9
"i" -> one push on key 9
Total cost is 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24.
It can be shown that no other mapping can provide a lower cost.

Constraints:

1 <= word.length <= 10^5
word consists of lowercase English letters

Approach: If you see, we can only use 8 keys (2, 3, 4, ..., 9) in total that means we can type only 8 characters with one push each, then 8 characters with two pushes each and so on so the optimal way to map charaters to keys evenly.

Given the above facts we can see that it's clearly a greedy problem where we need to start with most frequent characters in sorted and try to give the minimum numnber of pushes to those characters so that we can reduce the number of pushes as much as possible.

What we can do is, we can sort the given word as per the frequency of characters in descending order. Now we can use following simple steps:

charsAtCurrLevel = 1
currPushes = 1
totalPushes = 0
i = 0
WHILE i < n:

totalPushes = totalPushes + Count of word[i] * currPushes
charsAtCurrLevel = charsAtCurrLevel + 1
IF charsAtCurrLevel > 8

currPushes = currPushes + 1
charsAtCurrLevel = 1

i = i + Count of word[i]

RETURN totalPushes

This will solve the problem in nlogn time which is good but let's see how we can improve it. As such we can't do anything but what we can do is use of constraint 2 where the string characters are only small lowercase english characters. Let's see how;

Instead of using map for collecting frequency, we can use integer array of size 26. Once we collect all the frequency, we can now sort this frequency array in descending order. Now we know every index in this frequency array is representing a character in word string so we can use following steps to calculate total pushes:

totalPushes = 0
currPushes = 1
FOR i = 0 To 26

IF freqMap[i] == 0

BREAK

IF i % 8 == 0

currPushes = currPushes + 1

totalPushes = totalPushes + freqMap[i] * currPushes

RETURN totalPushes

That's all!

Implementation in C#:

Approach 1: Sort word based on frequency of characters:

    public int MinimumPushes1(string word)
    {
        int length = word?.Length ?? 0;
        if (length <= 8)
        {
            return length;
        }
        var wordArr = word.ToCharArray();
        int[] map = new int[26];
        foreach (char ch in wordArr)
        {
            ++map[ch - 'a'];
        }
        Array.Sort(wordArr, (c1, c2) => {
            if (map[c2 - 'a'] == map[c1 - 'a'])
            {
                return c1.CompareTo(c2);
            }
            return map[c2 - 'a'].CompareTo(map[c1 - 'a']);
        });
        int totalPushes = 0;
        int currReqdPushes = 1;
        int distintCharsAtCurrLevel = 1;
        for (int i = 0; i < length; )
        {
            totalPushes += map[wordArr[i] - 'a'] * currReqdPushes;
            ++distintCharsAtCurrLevel;
            if (distintCharsAtCurrLevel > 8)
            {
                distintCharsAtCurrLevel = 1;
                ++currReqdPushes;
            }
            i += map[wordArr[i] - 'a'];
        }
        return totalPushes;
    }

Approach 2: Sort frequency array:

    public int MinimumPushes(string word)
    {
        int length = word?.Length ?? 0;
        if (length <= 8)
        {
            return length;
        }
        var wordArr = word.ToCharArray();
        int[] map = new int[26];
        foreach (char ch in word)
        {
            ++map[ch - 'a'];
        }
        Array.Sort(map, (i1, i2) => {
            return i2.CompareTo(i1);
        });
        int totalPushes = 0;
        int currReqdPushes = 1;
        for (int i = 0; i < 26; ++i)
        {
            if (map[i] == 0)
            {
                break;
            }
            if (i != 0 && i % 8 == 0)
            {
                ++currReqdPushes;
            }
            totalPushes += map[i] * currReqdPushes;
        }
        return totalPushes;
    }

Complexity: Approach 1: O(nlogn)

Approach 2: O(n)

[LeetCode] Find the City With the Smallest Number of Neighbors at a Threshold Distance

2024-07-27T01:22:00.005+05:30

Problem: There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold.

Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path.

Example:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

Constraints:

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti, distanceThreshold <= 10^4
All pairs (fromi, toi) are distinct.

Approach: This is clearly a Floyd-Warshall problem as we can do BFS here but the complexity will be n^n. Once we get the dist matrix from Floy Warshall algorithm, things becomes simpler. Now we know that we have the shortest path matrix 'dist' with us so we just need to traverse this matrix:

For every node i from 0...n-1:

Check if dist[i][j] <= distanceThreshold then we know j is reachable from i.

Now in this way we just need to calculate the number of cities reachable from every city i and return the city with minimum number of connected cities.

Implementation in C#:

public class Solution 
{
    public int FindTheCity(int n,
                           int[][] edges,
                           int distanceThreshold)
    {
        int[,] dist = this.FloydWarshall(edges, n);
        int minCount = INF;
        int minCity = -1;
        for (int i = 0; i < n; ++i)
        {
            int currCount = 0;
            for (int j = 0; j < n; ++j)
            {
                if (i != j)
                {
                    if (dist[i, j] <= distanceThreshold)
                    {
                        ++currCount;
                    }
                }
            }
            if (currCount <= minCount)
            {
                minCount = currCount;
                minCity = i;
            }
        } 
        return minCity;
    }

    private int[,] FloydWarshall(int[][] edges, int n)
    {
        int[,] dist = this.InitDist(edges, n);
        for (int k = 0; k < n; ++k)
        {
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < n; ++j)
                {
                    if (dist[i, j] > dist[i, k] + dist[k, j])
                    {
                        dist[i, j] = dist[i, k] + dist[k, j];
                    }
                }
            }
        }
        return dist;
    }

    private int[,] InitDist(int[][] edges, int n)
    {
        int[,] dist = new int[n, n];
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                dist[i, j] = i == j ? 0 : INF;
            }
        }
        foreach (var edge in edges)
        {
            dist[edge[0], edge[1]] = edge[2];
            dist[edge[1], edge[0]] = edge[2];
        }
        return dist;
    }

    // Max sum could be 10^4 * 10^2 = 10^6
    private const int INF = 9999999;
}

Complexity: O(n^3)

Floyd Warshall Algorithm

2024-07-27T00:37:00.004+05:30

Description: As per wiki, in computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices.

Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.

Algorithm: Given a graph Graph[][] with nodes 1...N, we need to evaluate the matrix say shortestPathMatrix[][] where shortestPathMatrix[ni][nj] tells the shortest path between nodes ni and nj.

The algorithm uses dynamic programming to evaluate the above matrix. It relies on a obvious thing that the shortest path between n1 and n2 will have a intermediate node say nk:

That means, we can say for every intermediate node k:

shortestPathMatrix[i][j] = MIN (shortestPathMatrix[i][k] + shortestPathMatrix[k][j], shortestPathMatrix[i][j]

So the steps are now simple:

Initialize shortestPathMatrix to Graph.
FOR k = 0 TO n:

FOR i = 0 TO n:

FOR j = 0 TO n:

shortestPathMatrix[i][j] = MIN (shortestPathMatrix[i][k] + shortestPathMatrix[k][j], shortestPathMatrix[i][j])

That's all!

Implementation in C#:

class Graph

{

public Graph(int[,] adjMat)

{

this.adjacencyMatrix = adjMat;

}

public int[,] FloydWarshall()

{

int n = this.adjacencyMatrix?.GetLength(0) ?? 0;

if (n == 0)

{

return null;

}

int[,] dist = this.InitDistance();

for (int k = 0; k < n; ++k)

{

for (int i = 0; i < n; ++i)

{

for (int j = 0; j < n; ++j)

{

if (dist[i, k] + dist[k, j] < dist[i, j])

{

dist[i, j] = dist[i, k] + dist[k, j];

}

return dist;

}

private int[,] InitDistance()

{

int n = this.adjacencyMatrix.GetLength(0);

int[,] dist = new int[n, n];

Console.WriteLine(n);

for (int i = 0; i < n; ++i)

{

for (int j = 0; j < n; ++j)

{

dist[i, j] = this.adjacencyMatrix[i, j] >= 0 ?

this.adjacencyMatrix[i, j] :

Graph.INF;

}

return dist;

}

private int[,] adjacencyMatrix;

private const int INF = 9999;

}

Complexity: O(n^3)

[Microsoft][GFG] Tree Boundary Traversal in anticlockwise direction

2024-07-26T20:16:00.004+05:30

Problem: Given a Binary Tree, find its Boundary Traversal. The traversal should be in the following order:

Left boundary nodes: defined as the path from the root to the left-most node ie- the leaf node you could reach when you always travel preferring the left subtree over the right subtree.
Leaf nodes: All the leaf nodes except for the ones that are part of left or right boundary.
Reverse right boundary nodes: defined as the path from the right-most node to the root. The right-most node is the leaf node you could reach when you always travel preferring the right subtree over the left subtree. Exclude the root from this as it was already included in the traversal of left boundary nodes.

Note: If the root doesn't have a left subtree or right subtree, then the root itself is the left or right boundary.

Example:

Input:
        1 
      /   \
     2     3  
    / \   / \ 
   4   5 6   7
      / \
     8   9
   
Output: 1 2 4 8 9 6 7 3
Explanation:

Input:
            1
           /
          2
        /  \
       4    9
     /  \    \
    6    5    3
             /  \
            7     8

Output: 1 2 4 6 5 7 8
Explanation:













As you can see we have not taken the right subtree.

Approach: We can solve this problem in four steps given the nature of the problem:

Add root to result.
Preorder traversal of left subtree. If left child is available then do not go for right child. Ignore the leaves.
Inorder traversal of leaves if root is not leaf.
Postorder traversal of right subtre. If right child is available then do not go for left child. Ignore the leaves.

That's all!

Implementation in C#:

class BinaryTreeNode

{

public BinaryTreeNode Left {get; set;}

public BinaryTreeNode Right {get; set;}

public int Value {get; set;}

public BinaryTreeNode(int val,

BinaryTreeNode left = null,

BinaryTreeNode right = null)

{

this.Left = left;

this.Right = right;

this.Value = val;

}

class BinaryTree

{

public List<int> BoundaryTraversal()

{

List<int> result = new List<int>();

if (this.Root == null)

{

return result;

}

result.Add(this.Root.Value);

this.TraverseLeftBoundary(this.Root.Left, result);

// Avoid leaf traversing if root itself is leaf

if (this.Root.Left != null || this.Root.Right != null)

{

this.TraverseLeaves(this.Root, result);

}

this.TraverseRightBoundary(this.Root.Right, result);

return result;

}

private void TraverseLeftBoundary(BinaryTreeNode node,

List<int> result)

{

if (node == null ||

(node.Left == null && node.Right == null))

{

return;

}

if (node.Left != null)

{

result.Add(node.Value);

this.TraverseLeftBoundary(node.Left, result);

}

else

{

result.Add(node.Value);

this.TraverseLeftBoundary(node.Right, result);

}

private void TraverseLeaves(BinaryTreeNode node,

List<int> result)

{

if (node == null)

{

return;

}

this.TraverseLeaves(node.Left, result);

if (node.Left == null && node.Right == null)

{

result.Add(node.Value);

}

this.TraverseLeaves(node.Right, result);

}

private void TraverseRightBoundary(BinaryTreeNode node,

List<int> result)

{

if (node == null ||

(node.Left == null && node.Right == null))

{

return;

}

if (node.Right != null)

{

this.TraverseRightBoundary(node.Right, result);

result.Add(node.Value);

}

else

{

this.TraverseRightBoundary(node.Left, result);

result.Add(node.Value);

}

public BinaryTreeNode Root {get; set;}

}

Complexity: O(n)

[LeetCode] Longest Continuous Increasing Subsequence

2024-07-26T18:33:00.003+05:30

Problem: Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

Example:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element 4.

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly increasing.

Approach: It's a simple implementation problem. You can directly look at the implementation to understand the approach.

Implementation in C#:

    public int FindLengthOfLCIS(int[] nums)
    {
        int length = nums?.Length ?? 0;
        if (length <= 1)
        {
            return length;
        }
        int maxCISLength = 1;
        int currCISLength = 1;
        int prevIndex = 0;
        for (int i = 1; i < length; ++i)
        {
            if (nums[i] > nums[prevIndex])
            {
                ++currCISLength;
                if (currCISLength > maxCISLength)
                {
                    maxCISLength = currCISLength;
                }
            }
            else
            {
                currCISLength = 1;
            }
            prevIndex = i;
        }
        return maxCISLength;
    }

Complexity: O(n)

[LeetCode] Shortest Completing Word

2024-07-24T21:22:00.006+05:30

Problem: Given a string licensePlate and an array of strings words, find the shortest completing word in words.

A completing word is a word that contains all the letters in licensePlate. Ignore numbers and spaces in licensePlate, and treat letters as case insensitive. If a letter appears more than once in licensePlate, then it must appear in the word the same number of times or more.

For example, if licensePlate = "aBc 12c", then it contains letters 'a', 'b' (ignoring case), and 'c' twice. Possible completing words are "abccdef", "caaacab", and "cbca".

Return the shortest completing word in words. It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in words.

Example:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"
Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'.
"step" contains 't' and 'p', but only contains 1 's'.
"steps" contains 't', 'p', and both 's' characters.
"stripe" is missing an 's'.
"stepple" is missing an 's'.
Since "steps" is the only word containing all the letters, that is the answer.

Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: "pest"
Explanation: licensePlate only contains the letter 's'. All the words contain 's', but among these "pest", "stew", and "show" are shortest. The answer is "pest" because it is the word that appears earliest of the 3.

Approach: This is a simple problem to solve. We can easily solve it using using two hash maps. Directly look at the implementation to understand the approach.

Implementation in C#:

    public string ShortestCompletingWord(string licensePlate, string[] words)
    {
        var plateCharsMap = new int[26];
        foreach(char ch in licensePlate)
        {
            if (Char.IsLetter(ch))
            {
                ++plateCharsMap[Char.ToLower(ch) - 'a'];
            }
        }
        string result = null;
        foreach (string word in words)
        {
            int length = word.Length;
            var wordCharMap = new int[26];
            foreach (char ch in word)
            {
                ++wordCharMap[ch - 'a'];
            }
            if (this.IsCompleteWord(plateCharsMap, wordCharMap))
            {
                if (result == null || length < result.Length)
                {
                    result = word;
                }
            }
        }
        return result;
    }

    private bool IsCompleteWord(int[] plateCharsMap, int[] wordCharMap)
    {
        for (int i = 0; i < 26; ++i)
        {
            if (plateCharsMap[i] > wordCharMap[i])
            {
                return false;
            }
        }
        return true;
    }

Complexity: O(m*n) where m is number of words and n is length of largest word.