Up to date

The concept of taking N servers to handle requests and trying to balance evenly in all of them is called  Load Balancing . Good Read Good Read2 Good to watch  Video Take away:  * Load balancing distributes requests across servers. * You can use `hash(r_id) % n_servers` to get the server index for a request `r_id`. -> Drawback: if you add an extra server `n_servers` changes and `r_id` will end up on a different server. This is bad because often we want to map requests with the same ids consistently to the same servers (there could e.g. be cached data there that we want to reuse). * "Consistent hashing" hashes with a constant denominator `M`, e.g. `hash(r_id) % M`, and then maps the resulting integer onto a server index. Each server has a range of integers that map to their index. Consistent Hashing : Good to watch Load Balancing is a key concept to system design. One of the popular ways to balance load in a system is to use the concept of consistent hashing. Con...

import java.util.List; import java.util.ArrayList; import java.util.Stack; class KosarajuSharirSCC { private boolean[] visited; // visited[v] = true if v connected to s private int[] scc; // id[v] = id of component containing v private int count; /** find connected components in G */ public KosarajuSharirSCC(Digraph G) { // initialize data structures this.visited = new boolean[G.V()]; this.scc = new int[G.V()]; this.count = 0; // number of components DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G.reverse()); // run DFS from for topological order of depthFirstOrder.reversePost Stack reversePost_copy = depthFirstOrder.reversePost(); while(!reversePost_copy.isEmpty()) { int v = reversePost_copy.pop(); if(!visited[v]) { dfs(G, v); count++; } } } /** are v and w connected? */ boolean isS...

import java.util.List; import java.util.ArrayList; import java.util.Stack; class DepthFirstOrder { private boolean[] visited; // visited[v] = true if v connected to s private Stack reversePost; // all vertices in reverse DFS porst order public DepthFirstOrder(Digraph G) { // initialize data structures this.visited = new boolean[G.V()]; this.reversePost = new Stack (); for(int v = 0; v reversePost() { return reversePost; } private static Digraph prepareGraph() { int[][] edges = new int[][] { {0, 5}, {0, 2}, {0, 1}, {3, 6}, {3, 5}, {3, 4}, {5, 2}, {6, 4}, {6, 0}, {3, 2}, {1, 4} }; Digraph G = new Digraph(7); // add all edges for(int i = 0; i [] adj; // adjacency lists... 0 to V-1 /** create an empty digraph with V vertices */ public Digraph(int V) { this.V = V; this.ad...

import java.util.List; import java.util.ArrayList; import java.util.Stack; class DepthFirstPaths { private boolean[] visited; // visited[v] = true if v connected to s private int[] edgeTo; // edgeTo[v] = previous vertex on path from s to v private int s; public DepthFirstPaths(Digraph G, int s) { // initialize data structures this.visited = new boolean[G.V()]; this.edgeTo = new int[G.V()]; this.s = s; // find vertices connected to s dfs(G, s); } // is there a path from s to v? public boolean hasPathTo(int v) { return visited[v]; } // path from s to v; null if no such path public Iterable pathTo(int v) { if (!hasPathTo(v)) { return null; } Stack path = new Stack (); int previousVertices = v; while(previousVertices != this.s) { path.push(previousVertices); previousVertices = edgeTo[previousV...

import java.util.List; import java.util.ArrayList; class Digraph { private final int V; // number of vertices private final List [] adj; // adjacency lists... 0 to V-1 /** create an empty digraph with V vertices */ public Digraph(int V) { this.V = V; this.adj = new ArrayList[V]; // create empty graph with V vertices for(int i = 0; i (); } } /** add a directed edge v→w */ public void addEdge(int v, int w) { // add edge v-w adj[v].add(w); } /** Iterator for vertices pointing from v */ public Iterable adj(int v) { return adj[v]; } /** number of vertices */ public int V() { return V; } /** number of edges */ public int E() { int countEdges = 0; for(int v = 0; v maxDegree ? degreeOfV : maxDegree; } return maxDegree; } /** Compute average degree */ public static do...

Graph API program | Directed graph | Dgraph Depth first search (DFS) java program without recursion | Using adjacency list | directed graph | Digraph BSF Topological Sort Write code to find post order and topological order (or) topological sort Strongly connected components Kosaraju Sharir Strongly Connected Component

import java.util.List; import java.util.ArrayList; import java.util.Stack; class DepthFirstPaths { private boolean[] visited; // visited[v] = true if v connected to s private int[] edgeTo; // edgeTo[v] = previous vertex on path from s to v private int s; public DepthFirstPaths(Graph G, int s) { // initialize data structures this.visited = new boolean[G.V()]; this.edgeTo = new int[G.V()]; this.s = s; // find vertices connected to s dfs(G, s); } // is there a path from s to v? public boolean hasPathTo(int v) { return visited[v]; } // path from s to v; null if no such path public Iterable pathTo(int v) { if (!hasPathTo(v)) { return null; } Stack path = new Stack (); int previousVertices = v; while(previousVertices != this.s) { path.push(previousVertices); previousVertices = edgeTo[previousVer...

import java.util.List; import java.util.ArrayList; class ConnectedComponents { private boolean[] visited; // visited[v] = true if v connected to s private int[] id; // id[v] = id of component containing v private int count; /** find connected components in G */ public ConnectedComponents(Graph G) { // initialize data structures this.visited = new boolean[G.V()]; this.id = new int[G.V()]; this.count = 0; // number of components // run DFS from one vertex in each component for(int v = 0; v [] adj; // adjacency lists... 0 to V-1 /** create an empty graph with V vertices */ public Graph(int V, int E) { this.V = V; this.E = E; this.adj = new ArrayList[V]; // create empty graph with V vertices for(int i = 0; i (); } } /** add an edge v-w */ public void addEdge(int v, int w) { // a...

Good to read.  Good to watch. Scalability is  the measure of a system's ability to handle varying amounts of work by adding or removing resources from the system. Horizontal scaling (aka scaling out) refers to adding additional nodes or machines to your infrastructure to cope with new demands. If you are hosting an application on a server and find that it no longer has the capacity or capabilities to handle traffic, adding a server may be your solution. (Or) is is about buying more machines of similar types. Vertical scaling (aka scaling up) describes adding additional resources to a system so that it meets demand. (OR) Optimizing the process and increase the throughput with the same resource, is called vertical scaling. Advantages of horizontal  scaling  1. Scaling is easier from a hardware perspective - It eliminates the need to analyze which system specifications you need to upgrade.  2. Fewer periods of downtime - If done effectively, there may never be a...

Scalability :  Ability to handle increasing load without compromising the performance System Availability: It is a matrix that majors the probability that your system will not goes down when it is intended to be used. Load Balancing: Virtualization:  Resiliency or R esilience:   Resiliency is the  ability of a server, network, storage system, or an entire data center , to recover quickly and continue operating even when there has been an equipment failure, power outage or other disruption. Fault tolerance refers to  the ability of a system  (computer, network, cloud cluster, etc.) to continue operating without interruption when one or more of its components fail. Cron Job: Scheduled job that run at fixed schedule time. It can help to achieve processing of large task in non peak hours. Microservice architecture: A variant of the service-oriented architecture (SOA) structural style – arranges an application as a collection of loosely-coupled services. In a...

import java.util.List; import java.util.ArrayList; import java.util.Queue; import java.util.ArrayDeque; class BreadthFirstPaths { private boolean[] visited; // visited[v] = true if v connected to s private int[] edgeTo; // edgeTo[v] = previous vertex on path from s to v private int[] distTo; // distance from s to v private int s; public BreadthFirstPaths(Graph G, int s) { // initialize data structures this.visited = new boolean[G.V()]; this.edgeTo = new int[G.V()]; this.distTo = new int[G.V()]; this.s = s; // find vertices connected to s bfs(G, s); } private void bfs(Graph G, int s) { int distance = 0; Queue q = new ArrayDeque (); System.out.print(s + "->"); visited[s] = true; q.offer(s); distTo[s] = distance; while(!q.isEmpty()) { distance++; int v = q.poll(); for(int w : G.adj...

import java.util.List; import java.util.ArrayList; import java.util.Stack; class DepthFirstPaths { private boolean[] visited; // visited[v] = true if v connected to s private int[] edgeTo; // edgeTo[v] = previous vertex on path from s to v private int s; public DepthFirstPaths(Graph G, int s) { // initialize data structures this.visited = new boolean[G.V()]; this.edgeTo = new int[G.V()]; this.s = s; // find vertices connected to s dfs(G, s); } // is there a path from s to v? public boolean hasPathTo(int v) { return visited[v]; } // path from s to v; null if no such path public Iterable pathTo(int v) { if (!hasPathTo(v)) { return null; } Stack path = new Stack (); int previousVertices = v; while(previousVertices != this.s) { path.push(previousVertices); previousVertices = edgeTo[previousVer...

import java.util.List; import java.util.ArrayList; class Graph { private final int V; // number of vertices private final List [] adj; // adjacency lists... 0 to V-1 /** create an empty graph with V vertices */ public Graph(int V) { this.V = V; this.adj = new ArrayList[V]; // create empty graph with V vertices for(int i = 0; i (); } } /** add an edge v-w */ public void addEdge(int v, int w) { // add edge v-w (parallel edges and self-loops allowed) adj[v].add(w); adj[w].add(v); } /** vertices adjacent to v */ public Iterable adj(int v) { return adj[v]; } /** number of vertices */ public int V() { return V; } /** number of edges */ public int E() { int countEdges = 0; for(int v = 0; v maxDegree ? degreeOfV : maxDegree; } return maxDegree; } /** Compute average d...

 Graph. Set of vertices connected pairwise by edges Graph API Code Depth first search (DFS) java program | Using adjacency list Depth first search (DFS) java program without recursion | Using adjacency list Breadth first search (BFS) java program | Using adjacency list Connected Component code Some graph problems: