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)