System Design: Availability Patterns

1. Fail Over: Basically the fail over is kind of following:

But it is really more complex than above. If we double click a little, failover is:

The complete fail back is as follows:

2. Replication: There are two kind of replications:

• Active Replication: Based on PUSH model, we will discuss multiple approaches for this.
• Passive Replication: Based on PULL model. Whenever a node see that it does not have the requested data, it just read from peer and stores it locally. This strategy works well with timeout based caches.

Active Replications:

Master-Slave Replication:

Tree Replication:

 

Master - Master Replication:

Buddy Replication:

Now what happens if a node dies, say Node A crashes:

System Design: The numbers everyone should care

Before moving to the actual design we should scope the design problem. To scope the problem we must come up with the load, storage required, qps needs to be supported. For all these the following numbers can be really helpful.

1 second = 10^9 nano seconds

[Coinbase] Get Resource with max frequency of every 5 minutes interval

Problem: You are given the logs in [timestamp, user, resource] format which indicates the timestamp  when user access a resource. You need to provide the most accessed resource of every 5 minute window. You can say the timestamp is representing minutes here.

Example:

Input: logs = ["1", "user_1", "resource_1"],
["3", "user_2", "resource_2"],
["4", "user_1", "resource_3"],
["7", "user_2", "resource_3"],
["8", "user_1", "resource_3"]
Output: [resource_1, resource_3, resource_3]

Approach: If you see this problem is similar to designing data structure with increment, decrement, max and min at constant time. We can mix sliding window approach with it to solve this problem.

Implementation in C#:

    private static void PrintMaxOfEvery5Mins(Log[] logs)

    {

        Array.Sort(logs, (l1, l2) => {

           return l1.Timestamp.CompareTo(l2.Timestamp);

        });

      

        Dictionary<string, LinkedListNode<int>> resourceToFreqNodeMap = new Dictionary<string, LinkedListNode<int>>();

        Dictionary<int, HashSet<string>> freqToResourcesMap = new Dictionary<int, HashSet<string>>();

        LinkedList<int> frequenciesList = new LinkedList<int>();

        Queue<Log> queue = new Queue<Log>();

        

        foreach(var log in logs)

        {

            if (queue.Count > 0 && log.Timestamp - queue.Peek().Timestamp >= 5)

            {

                Console.WriteLine(GetMaxOf5Mins(freqToResourcesMap, frequenciesList));

                while (queue.Count > 0 && log.Timestamp - queue.Peek().Timestamp >= 5)

                {

                    DecrementCount(queue.Dequeue().Resource, resourceToFreqNodeMap, freqToResourcesMap, frequenciesList);

                }

            }

            queue.Enqueue(log);

            IncrementCount(log.Resource, resourceToFreqNodeMap, freqToResourcesMap, frequenciesList);

        }

        

        if (queue.Count > 0)

        {

            Console.WriteLine(GetMaxOf5Mins(freqToResourcesMap, frequenciesList));

        }

    }

    

    private static void IncrementCount(string resource,

                                      Dictionary<string, LinkedListNode<int>> resourceToFreqNodeMap,

                                      Dictionary<int, HashSet<string>> freqToResourcesMap,

                                      LinkedList<int> frequenciesList)

    {

        if (!resourceToFreqNodeMap.ContainsKey(resource))

        {

            AddResource(resource, resourceToFreqNodeMap, freqToResourcesMap, frequenciesList);

        }

        else

        {

            IncResourceCount(resource, resourceToFreqNodeMap, freqToResourcesMap, frequenciesList);

        }

    }

    

    private static void AddResource(string resource,

                                      Dictionary<string, LinkedListNode<int>> resourceToFreqNodeMap,

                                      Dictionary<int, HashSet<string>> freqToResourcesMap,

                                      LinkedList<int> frequenciesList)

    {

        if (!freqToResourcesMap.ContainsKey(1))

        {

            freqToResourcesMap[1] = new HashSet<string>();

            frequenciesList.AddFirst(1);

        }

        

        freqToResourcesMap[1].Add(resource);

        resourceToFreqNodeMap[resource] = frequenciesList.First;

    }

    

    private static void IncResourceCount(string resource,

                                      Dictionary<string, LinkedListNode<int>> resourceToFreqNodeMap,

                                      Dictionary<int, HashSet<string>> freqToResourcesMap,

                                      LinkedList<int> frequenciesList)

    {

        var freqNode = resourceToFreqNodeMap[resource];

        int currCount = freqNode.Value;

        int newCount = currCount + 1;

        if (!freqToResourcesMap.ContainsKey(newCount))

        {

            freqToResourcesMap[newCount] = new HashSet<string>();

            frequenciesList.AddAfter(freqNode, newCount);

        }

        freqToResourcesMap[newCount].Add(resource);

        freqToResourcesMap[currCount].Remove(resource);

        resourceToFreqNodeMap[resource] = freqNode.Next;

        if (freqToResourcesMap[currCount].Count == 0)

        {

            frequenciesList.Remove(freqNode);

            freqToResourcesMap.Remove(currCount);

        }

    }

    

    private static void DecrementCount(string resource,

                                      Dictionary<string, LinkedListNode<int>> resourceToFreqNodeMap,

                                      Dictionary<int, HashSet<string>> freqToResourcesMap,

                                      LinkedList<int> frequenciesList)

    {

        var freqNode = resourceToFreqNodeMap[resource];

        int currCount = freqNode.Value;

        int newCount = currCount - 1;

        if (newCount > 0)

        {

            if (!freqToResourcesMap.ContainsKey(newCount))

            {

                freqToResourcesMap[newCount] = new HashSet<string>();

                frequenciesList.AddBefore(freqNode, newCount);

            }

            freqToResourcesMap[newCount].Add(resource);

            resourceToFreqNodeMap[resource] = freqNode.Previous;

        }

        

        freqToResourcesMap[currCount].Remove(resource);

        if (freqToResourcesMap[currCount].Count == 0)

        {

            frequenciesList.Remove(freqNode);

            freqToResourcesMap.Remove(currCount);

        }

        if (newCount == 0)

        {

            resourceToFreqNodeMap.Remove(resource);

        }

    }

    

    private static string GetMaxOf5Mins(Dictionary<int, HashSet<string>> freqToResourcesMap,

                                      LinkedList<int> frequenciesList)

    {

        if (frequenciesList == null)

        {

            return string.Empty;

        }

        return freqToResourcesMap[frequenciesList.Last.Value].First();

    }

}

class Log

{

    public int Timestamp {get; private set;}

    public string User {get; private set;} 

    public string Resource {get; private set;}

    

    public Log(string timestamp, string user, string resource)

    {

        this.Timestamp = int.Parse(timestamp);

        this.User = user;

        this.Resource = resource;

    }

}

Complexity: O(n)

[Coinbase] Extract user session from logs

Problem: You are given the logs in [timestamp, user, resource] format which indicates the timestamp  when user access a resource. A user session is defined as the earliest timestamp and the latest timestamp when user accessed any resource.

Extract all the user sessions from the logs.

Example:

Input: logs = ["58523", "user_1", "resource_1"],
["62314", "user_2", "resource_2"],
["54001", "user_1", "resource_3"],
["54060", "user_2", "resource_3"],
["54359", "user_1", "resource_3"]
Output: user_1 -> (54001 - 58523)
user_2 -> (54060 - 62314)

Approach: It's an easy problem to solve by using hashing. You can understand the approach by just looking at the code.

Implementation in C#:

    private static Dictionary<string, List<int>> GetUserSession(Log[] logs)

    {

        Dictionary<string, List<int>> userSessions = new Dictionary<string, List<int>>();

        foreach (Log log in logs)

        {

            if (!userSessions.ContainsKey(log.User))

            {

                userSessions[log.User] = new List<int>();

            }

            // User session is already recorded for this user, update if required

            if (userSessions[log.User].Count == 2)

            {

                // current timestamp is lower than existing session's first timestamp

               // Make current as first timestamp for this user session

                if (log.Timestamp < userSessions[log.User][0])

                {

                    userSessions[log.User][0] = log.Timestamp;

                }

                // current timestamp is greater than existing session's last timestamp

               // Make current as last timestamp for this user session

                else if (log.Timestamp > userSessions[log.User][1])

                {

                    userSessions[log.User][1] = log.Timestamp;

                }

            }

            // current timestamp is lower than first timestamp of this user session.

            else if (userSessions[log.User].Count == 1 && log.Timestamp < userSessions[log.User][0])

            {

                userSessions[log.User].Insert(0, log.Timestamp);

            }

            else

            {

                userSessions[log.User].Add(log.Timestamp);

            }

        }

        return userSessions;

    }

    

    private static void PrintUserSession(Dictionary<string, List<int>> userSessions)

    {

        foreach(var session in userSessions)

        {

            string output = session.Key + " -> (" + session.Value[0] + " - ";

            if (session.Value.Count == 1)

            {

                output += session.Value[0] + ")";

            }

            else

            {

                output += session.Value[1] + ")";

            }

            Console.WriteLine(output);

        }

    }

    class Log

    {

        public int Timestamp {get; private set;}

        public string User {get; private set;} 

        public string Resource {get; private set;}    

        public Log(string timestamp, string user, string resource)

        {

            this.Timestamp = int.Parse(timestamp);

            this.User = user;

            this.Resource = resource;

        }

    }

Complexity: O(n)

Find the element in a sorted array which is equal or just less than given number

Problem: In a given sorted array, find the greatest element which is less than a given number x.

Example:

Input: arr = [7, 12, 16, 20, 24 29], x = 22
Output: 20

Approach: A simple change in binary search will work here.

Implementation in C#:

public static int BinarySearch(int[] arr, int x)

{

        int low = -1, high = arr.Length - 1;

        while(low + 1 < high)

        {

            int mid  = low + (high - low) / 2;

            if(arr[mid] <= x) // the change required

            {

                low = mid;

            }

            else 

            {

                high = mid;

            }

        }

        return arr[low];

    }

Complexity: O(logn)

[Amazon][LeetCode] Rotting Oranges

Problem: You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example:

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

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

Approach: This is another BFS problem. We treat this matrix as graph where a cell is connected to another cell if they are neighbour of each other (except diagonal neighbours). We start our BFS with all the initial rotten oranges (grid[x][y] == 2) cells enqueued in a queue.

We keep incrementing the number of minutes at every iteration and make all the fresh oranges neighbours 2 (rotten). Once the BFS ends, we just need to check if there is a cell with fresh orange, if yes then we will return -1 otherwise we return the number of minutes.

Implementation in C#:

    public int OrangesRotting(int[][] grid) {

        int rows = grid?.Length ?? 0;

        if (rows == 0)

        {

            return 0;

        }

        int cols = grid[0].Length;

        Queue<int[]> queue = new Queue<int[]>();

        int numOfFreshCells = this.GetFreshCellsAndAddRottenCellsToQueue(grid,

                                                                         queue);

        if (numOfFreshCells == 0)

        {

            return 0;

        }

        int minutes = 0;

        while (queue.Count > 0)

        {

            int size = queue.Count;

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

            {

                var cell = queue.Dequeue();

                this.AddNeighbourFreshCellsToQueue(cell,

                                                   grid,

                                                   queue,

                                                   ref numOfFreshCells);

            }

            if (queue.Count > 0)

            {

                ++minutes;

            }

        }

        return numOfFreshCells != 0 ? - 1 : minutes;

    }

    private bool IsFreshCellRemaining(int[][] grid)

    {

        for (int i = 0; i < grid.Length; ++i)

        {

            for (int j = 0; j < grid[0].Length; ++j)

            {

                if (grid[i][j] == 1)

                {

                    return true;

                }

            }

        }

        return false;

    }

    private void AddNeighbourFreshCellsToQueue(int[] cell,

                                               int[][] grid,

                                               Queue<int[]> queue,

                                               ref int numOfFreshCells)

    {

        // Left cell

        if (this.IsValidAndFreshCell(cell[0], cell[1] - 1, grid))

        {

            grid[cell[0]][cell[1] - 1] = 2;

            queue.Enqueue(new int[] {cell[0], cell[1] - 1});

            --numOfFreshCells;

        }

        // Right cell

        if (this.IsValidAndFreshCell(cell[0], cell[1] + 1, grid))

        {

            grid[cell[0]][cell[1] + 1] = 2;

            queue.Enqueue(new int[] {cell[0], cell[1] + 1});

            --numOfFreshCells;

        }

        // Up cell

        if (this.IsValidAndFreshCell(cell[0] - 1, cell[1], grid))

        {

            grid[cell[0] - 1][cell[1]] = 2;

            queue.Enqueue(new int[] {cell[0] - 1, cell[1]});

            --numOfFreshCells;

        }

        // Down cell

        if (this.IsValidAndFreshCell(cell[0] + 1, cell[1], grid))

        {

            grid[cell[0] + 1][cell[1]] = 2;

            queue.Enqueue(new int[] {cell[0] + 1, cell[1]});

            --numOfFreshCells;

        }

    }

    private bool IsValidAndFreshCell(int row, int col, int[][] grid)

    {

        return row >= 0 &&

               row < grid.Length &&

               col >= 0 &&

               col < grid[0].Length &&

               grid[row][col] == 1;

    }

    private int GetFreshCellsAndAddRottenCellsToQueue(int[][] grid,

                                                      Queue<int[]> queue)

    {

        int numOfFreshCells = 0;

        for (int i = 0; i < grid.Length; ++i)

        {

            for (int j = 0; j < grid[0].Length; ++j)

            {

                if (grid[i][j] == 1)

                {

                    ++numOfFreshCells;

                }

                else if (grid[i][j] == 2)

                {

                    queue.Enqueue(new int[] {i, j});

                }

            }

        }

        return numOfFreshCells;

    }

Complexity: O(m x n) where m is number of rows and n is number of columns.

[LeetCode] 3 Sum

Problem: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: nums = []
Output: []

Input: nums = [0]
Output: []

Approach: We can use sorting here. Once we sort the array, We can use approach of two pointers low and high. For every nums[i], we check if there are two elements in nums[i + 1.... n] whose sum is -nums[i].

To avoid duplicate we can move i till nums[i] == nums[i + 1] and we can move high till nums[high] == nums[high - 1]. That's all!

Implementation in C#:

    public IList<IList<int>> ThreeSum(int[] nums) 

    {

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

        Array.Sort(nums);

        for (int i = 0; i < nums.Length; ++i)

        {

            if ( i > 0 &&  nums[i] == nums[i - 1])

            {

                continue;

            }

            int low = i + 1, high = nums.Length - 1, sumToCheck = -nums[i];

            while (low < high)

            {

                if (high < nums.Length - 1 && nums[high] == nums[high + 1])

                {

                    --high;

                    continue;

                }

                if (nums[low] + nums[high] == sumToCheck)

                {

                    result.Add(new List<int> { nums[i], nums[low], nums[high] });

                    ++low;

                    --high;

                }

                else if (nums[low] + nums[high] < sumToCheck)

                {

                    ++low;

                }

                else

                {

                    --high;

                }

            }

        }

        return result;

    }

Complexity: O(n^2)