Sunday, 14 February 2021

Microservices and Observability

 

1. Log Aggregation - In  a typical microservice architecture, there may be hundreds of servers involved and looking at the logs from relevant servers to debug a failure would be nearly impossible. Typically all the logs from various servers are aggregated to a centralized logging service with searching capability such as ELK stack (Elastic Search, Logstash and Kibana). There can be namespaces to identify the origin of the logs.

2. Distributed tracing - In a microservice architecture, a request could be spread across many microservices and for debugging any issues, we may have to check the logs from multiple services.

A tracing id is to be generated typically by the gateway and passed as a request header to all the services and is to be sent back in the response header. The tracing id can be picked from the response header of the request or any of the log message to identify the remaining part of logs in different services. 

3. Metrics and Alarms - Metrics from the application can be loaded to a centralized metric service. This can be further utilized for setting up alarm notifications for getting the immediate attention based on the severity. Tools like grafana provides a configurable dashboard for the metrics to get an overall picture of how the application has been performing. Typically a canary test also would be deployed along with each services that will generate failure or trigger alarms so that owner of the service will be alerted even before customer faces the issue.

4. Audit Logging - User actions are typically logged for any future auditing purpose like compliance, security, customer support etc.

5. Health Check API - A micro service may have health check API which typically check connections to infrastructure services like DB connection pool, disk space etc. This API is periodically called by a service registry or loadbalancer to identify the healthy service instances.

6. Log Deployment changes - Every deployment changes to production may be logged to identify if a particular issue started occurring after a certain production deployment.

7. Exception Tracking - All exceptions can be reported to a centralized exception tracking service which can notify the developers about failures.

Saturday, 13 February 2021

Refactoring monolithic application into Microservices

 

strangler pattern - Monolithic application is incrementally modernized by extracting services from the application untill the monolithic application shrinks to no existence or becomes one of the service in the microservice architecture.

This will ensure that the business served  by the application will not get impacted when the application is being cut over to a microservice architecture. 

Strategies for refactoring a monolith to microservices:

1. Implement new features as services (stop monolith from growing)

While this will help the monolith from growing further and gives the microservice benefits of faster development/deployment, a new feature may not always qualify as a separate service.

API gateway is the minimum requirement for introducing new service as it needs to be in front of the monolith application and the new service so that the request can be routed appropriately.

REST/domain message interactions between the new service and monolithic application is required for getting the data for the new service. 

2. Separate presentation tier and backend

Move the presentation tier to a separate application using Single Page Application frameworks like Angular/React. This will allow the UI development to be decoupled from backend and also tests the REST APIs which are to be directly exposed to the end user.

3. Break up monolith by extracting services based on the business capabilities



Friday, 12 February 2021

Microservices - Handling partial failures and Circuit breaker


Circuit Breaker pattern - If a large number of requests are failing or timing out, then trip the circuit breaker so that requests are immediately failed without being forwarded to the particular microservice for a timeout period.

Because making further requests to the service is pointless and will result in consuming valuable resources like threads in the calling application.

After the timeout period allow the requests to the service and if the requests are succeeding, close the circuit breaker.

Netflix Hysterix/Resilence4J are java libraries that implements circuit breaker pattern.

Using circuit breaker is just a part of handling the dependent service failure and we still need to return an appropriate response to the client.

Handling partial failure for an unresponsive service - Returning a cached version of data if available is one way to handle the scenario. For a critical piece of information for the API, if the service is not available, the API need to return an error and for a less critical information for the API, it can be chosen to omit the fields or return cached data if available.


Microservices and Service Discovery

 

Service Discovery pattern - The service instances in a microservice architecture could dynamically change with auto-scaling, failure, upgrade etc. A service discovery pattern is used for identifying the instances corresponding to a microservice.

Key component of service discovery is a service registry which is a database of network locations of instances for a given service.

Service Discovery is achieved using the following patterns:

1. Self registration - A service instance typically registers itself with a service registry and service registry invokes a health check API periodically on the service instance to make sure the service instance is Up and Running. Service instances may also be required to invoke a heartbeat API of the service registry inorder to avoid its lease from expiring.

2. Client side discovery - The client service queries a service registry to get the list of available instances and do the client side load balancing across them using frameworks such as Ribbon in netflix OSS.

3. Server side discovery - When making a request to the service, client makes the request via a router, typically a loadbalancer that also acts as a service registry. The router then forwards the request to available service instance.The router takes care of service registration, discovery and the request routing with load balancing.


Spring-boot Eureka

For implementing Service Registry in spring-boot, one of the option is to use netflix eureka server.

From start.spring.io, the dependency for eureka server can be added for a service registry server.

Use @EnableEurekaServer annotation for enabling eureka service discovery server.

if you add the dependency for Eureka Discovery Client - for registering to service discovery server, you are all set with a service registry with your microservice registered in it.


HashiCorp Consul - provides a service mesh which takes care of the following:

Consul follows a peer to peer architecture and follows gossip protocal.

1. Service discovery server - service registry which maintains how to connect other services and the health of the service.

2. Configuration Server - for managing any configuration across for different microservices. 

3. Segmentation - managing connection between the microservices - using service graph to decide which service can access which service.

it also provides a side car proxy and maintain TLS certificates which enables mTLS communication between two services.

This will make sure data in transit is also encrypted inside a microservice architecture.


Thursday, 11 February 2021

Decomposing Application into microservices

 

Decompose by business capability

A business capability is something that a business does in order to generate value.

Capabilities of an online store could include order management, inventory management, shipping, online payment and so on.

It is based on what the business of the organization is.

Each business capability can be thought of as a service and this approach is business oriented.

A business capability or a sub-capability can be a service depending on several factors like whether they are intertwined or represent different phases etc. As the services eveolve, they could be again split into multiple services or even combined.


Decompose by subdomain

This is based on Domain Driven Design (DDD). In DDD, the Software components are mapped to the business domain objects.

This will also help in developing a ubiquitous language that can be used for communication between domain expert, business analyst, software developers and other stake holders. 

A business domain can have several subdomains. Sub domains can be very similar to the business Capabilities.

The domain objects can have different meaning in different subdomains and are limited to a bounded context.

Each subdomains can be mapped to a microservice.


Obstacles for decomposing an application into microservices

1. Network latency - Distributed architecture will result in lot of cross-service calls resulting in  reduced network latency.

2. Synchronous interprocess communication reduces availability - If one of the dependent service is unavailable, it could result in no processing of data even when the service is Up.

3. Maintaining data consistency across services - With separate database for each service, the update of a dependent business domain will require updates in other microservices. Transactional Messaging and SAGA patterns can be used for solving this scenario.

4. Obtaining a consistent view of the data - Decomposition into multiple services will raise the challenge of combining the data from across multiple services while presenting the data to the user.

API composition and CQRS are two patterns that can be used in these scenarios.

5. God classes prevent decomposition - the resource that is key for each of the service and are bloated with numerous responsibilities.

Use Domain Driven Design (DDD) to use the domain representation of the resource and split it across services using the bounded context in which the domain objects reside (Decompose by subdomain).




Saturday, 9 January 2021

Microservices - Transactional Messaging and handling 2 phase commit problem

 

In a microservices architecture, when data is updated in one microservice, another service may also require to reflect the updated state or the services may be involved in a SAGA pattern for completing a transactional outcome.

But updating the data in the database and publishing the message is a 2 phase commit problem. The database update could be successful whereas the publishing of the message could fail or vice versa. If one think of storing and republishing the messages only on failure, then this can result in messages going out of order.

The typical way to handle this issue is to use transactional outbox pattern, i.e, store the message to be published in a table every time the data is updated. This would mean that the entire operation can be committed in a single transaction and no 2 phase commit problem is involved.

Now, this message needs to be published from the transactional outbox table to the mesaging broker for the other microservices to take corresponding actions. This can be done via one of the following approaches:

1. Polling publisher: There can be a Polling publisher which frequently checks this transactional outbox table and picks the data in the timeCreated order and publishes the messages in the same order. If the messaging broker is down or not reachable while trying to publish the message, the Polling publisher can do finite retries and quit for the next iteration to publish the message. The message publishing can get delayed slightly with this approach based on the frequency of the Polling publisher. So the frequency of the Polling publisher needs to be adjusted based on the use case. The polling publisher need to delete the data from Transactional Outbox table once the message is published.

2. Transaction Log tailing: There are various connectors available with the messaging brokers like kafka for tailing a source database and publishing the messages and even to a target sink database. Such connectors can be used for tailing the transactional outbox table and the connector can be used for publishing the messages. This approach is reliable but is database specific and a bit complex. So if the minor delay is fine for the use case, polling publisher could be the go to solution.

But Transaction Log tailing may be a requirement for a NOSQL database to handle this scenario. The NOSQL database typically will not be having a transaction and hence to store the messages in a single transaction to the database, the generated message may also be required to be stored in the same table as the one in which domain object is stored. Now the challenge will be to identify the messages that needs to be published for a polling publisher. Using transactional log tailing will help to generate messages for only the newly created/updated data eliminating this challenge. 


Connector frameworks:

Debezium

Linkedin Databus

Dyanamo DB streams

Confluent connectors






Friday, 8 January 2021

Microservices and Software Architecture Styles

  Software Architecture Styles

1. Layered Architecture - Application is classified into multiple layers like presentation layer, business layer, persistence layer in a 3 tier architecture.

2. Hexagonal Architecture - Business logic is kept independent of other layers with communications happening via inbound/outbound adapters (Interfaces).

3. Microservices Architecture - The application is divided into multiple services based on domain/maintainability etc and other factors, each service of a microservice architecture typically follows hexagonal architecture.


Advantages of microservices

1. Enables continous delivery and deployment of large complex application via independent services.

2. Independent scaling

3. Fault isolation

4. Independent technology stack and can easily update to latest tech stack

5. Independent CI/CD pipeline and faster deployment/release

6. Smaller services are be easily maintainable

7. Enables teams to be autonomous

Drawbacks of microservices architecture

1. Finding the right set of services is challenging

2. Features spanning multiple services requires careful co-ordination:

 a. how to handle transaction across services (Saga)

 b. how to query data from multiple microservices (CQRS/API Composition)

 c. may require careful rollout plan with involved microservices to not break backward compatibility etc.

3. Testing and deployment can be difficult when multiple services are involved.


SOA Vs microservices

SOA uses SOAP based webservices where as the microservices use lighter REST based or gRPC based calls.

SOA used to integrate large monolithic applications where as services are broken down as multiple micro services in a microservice architecture.

SOA based architecture have single shared database for the entire application where as microservices have its own database.


Thursday, 7 January 2021

Write a program to print longest sequence of each numbers in a given array

 

Sample input array: {1,1,2,2,2,3,3,2,2,2,2,3,3,3,4,1,1,1}


Expected output:

1 occurred 3 times max in sequence

2 occurred 4 times max in sequence

3 occurred 3 times max in sequence

4 occurred 1 times max in sequence


https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm


package com.test.algorithm;

import java.util.HashMap;
import java.util.Map;

public class MaxRepeatingOccurrence {

public static void main(String[] args) {
int[] nums = new int[]{1, 1, 2, 2, 2, 3, 3, 2, 2, 2, 2, 3, 3, 3, 4, 1, 1, 1};

printMaxRepeatingOccurrences(nums);
}

private static void printMaxRepeatingOccurrences(int[] nums) {
Map<Integer, Integer> numOccurrenceMap = new HashMap<>();
int currentSequenceCount = 0;
for (int i = 0; i < nums.length; i++) {
currentSequenceCount = currentSequenceCount + 1;
if (i == nums.length - 1 || nums[i] != nums[i + 1]) {
if (numOccurrenceMap.get(nums[i]) == null || currentSequenceCount > numOccurrenceMap.get(nums[i])) {
numOccurrenceMap.put(nums[i], currentSequenceCount);
}
currentSequenceCount = 0;
}
}
for (Map.Entry<Integer, Integer> numOccurrenceEntry : numOccurrenceMap.entrySet()) {
System.out.println(numOccurrenceEntry.getKey() + " occurred " + numOccurrenceEntry.getValue() + " times max in sequence");
}
}
}

Write a program to print combination of numbers in an array that gives a target sum

 

A set of unique sorted numbers are given as an input like - {1,2,4,6,9,10}

Write a program to print all combination of numbers that gives a target sum, say 15

In this case, the answer should be:

10 4 1

9 4 2

9 6


https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/recursion


package com.test.algorithm.recursion;


public class FindSumCombinations {

public static void main(String[] args) {
int[] nums = new int[]{1,2,4,6,9,10};
int target = 15;

printCombinations(nums, target);
}

private static void printCombinations(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= target && printCombinations(nums, target - nums[i], i+1)) {
System.out.print(nums[i]);
System.out.println();
}
}
}

private static boolean printCombinations(int[] nums, int target, int startIndex) {
for (int i = startIndex; i < nums.length; i++) {
int newTarget = target - nums[i];
if (newTarget > 0) {
if (printCombinations(nums, newTarget, i+1)) {
System.out.print(nums[i] + " ");
return true;
}
} else if (newTarget == 0) {
System.out.print(nums[i] + " ");
return true;
} else {
return false;
}
}
return false;
}
}

Friday, 18 December 2020

Write a program to group given set of numbers by even and odd

 

Write a program to group given set of numbers by placing all the even numbers first and then all odd numbers with O(n) time complexity and O(1) space complexity.

https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm

package com.test.algorithm;

public class GroupByEvenAndOdd {
public static void main(String[] args) {
int[] numArray = new int[]{4,2,5,8,12,11,10};
groupNumsByEvenAndOdd(numArray);
for (int i=0; i< numArray.length; i++) {
System.out.println(numArray[i]);
}
}

private static void groupNumsByEvenAndOdd(int[] numArray) {
int newEvenIndex = 0;
for (int i=0; i< numArray.length; i++) {
if(numArray[i]%2 == 0) {
if (i != newEvenIndex) {
// swap
int temp = numArray[newEvenIndex];
numArray[newEvenIndex] = numArray[i];
numArray[i] = temp;
}
newEvenIndex++;
}
}
}
}

Write a program to print nearest greater number along with each number in a given list

   github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/stack

Nearest greater number is not the next greater number.

For example - for a given input - {4,2,5,8,12,11,10}

output will be like:

2 -> 5

4 -> 5

5 -> 8

8 -> 12

10 -> -1

11 -> -1

12 -> -1


package com.test.algorithm.stack;

import java.util.Stack;

public class NearestGreaterNumber {

public static void main(String[] args) {
int[] numArray = new int[]{4,2,5,8,12,11,10};
printNumWithNearestGreaterNumber(numArray);
}

private static void printNumWithNearestGreaterNumber(int[] numArray) {
Stack<Integer> numStack = new Stack<>();
for (int i=0; i< numArray.length; i++) {
while (!numStack.isEmpty() && numStack.peek() < numArray[i]) {
System.out.println(numStack.pop() + " -> " + numArray[i]);
}
numStack.push(numArray[i]);
}
while (!numStack.isEmpty()) {
System.out.println(numStack.pop() + " -> -1");
}
}
}

Write a program to print left view of a binary tree

  github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree

A left view of a binary tree is the left most elements at each level a binary tree.


package com.test.algorithm.tree;

import java.util.LinkedList;
import java.util.Queue;

public class LeftView {

public static void main(String[] args) {
TreeNode root = new TreeNode(4);
root.setLeft(new TreeNode(2));
root.getLeft().setRight(new TreeNode(3));
root.getLeft().setLeft(new TreeNode(1));

root.setRight(new TreeNode(6));
root.getRight().setRight(new TreeNode(7));
root.getRight().setLeft(new TreeNode(5));

printLeftView(root);
}

private static void printLeftView(TreeNode root) {
Queue<TreeNode> queue1 = new LinkedList<>();
queue1.add(root);
Queue<TreeNode> queue2 = new LinkedList<>();
while (!queue1.isEmpty() || !queue2.isEmpty()) {
boolean isQueue1LeftPrinted = false;
boolean isQueue2LeftPrinted = false;
while (!queue1.isEmpty()) {
TreeNode node = queue1.poll();
if (!isQueue1LeftPrinted) {
System.out.println(node.getData());
isQueue1LeftPrinted = true;
}
if (node.getLeft() != null) {
queue2.add(node.getLeft());
}
if (node.getRight() != null) {
queue2.add(node.getRight());
}
}
while (!queue2.isEmpty()) {
TreeNode node = queue2.poll();
if (!isQueue2LeftPrinted) {
System.out.println(node.getData());
isQueue2LeftPrinted = true;
}
if (node.getLeft() != null) {
queue1.add(node.getLeft());
}
if (node.getRight() != null) {
queue1.add(node.getRight());
}
}
}
}
}

Write a program to print right view of a binary tree

 github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree

A right view of a binary tree is the right most elements at each level a binary tree.

package com.test.algorithm.tree;

import java.util.LinkedList;
import java.util.Queue;

public class RightView {

public static void main(String[] args) {
TreeNode root = new TreeNode(4);
root.setLeft(new TreeNode(2));
root.getLeft().setRight(new TreeNode(3));
root.getLeft().setLeft(new TreeNode(1));

root.setRight(new TreeNode(6));
root.getRight().setRight(new TreeNode(7));
root.getRight().setLeft(new TreeNode(5));

printRightView(root);
}

private static void printRightView(TreeNode root) {
Queue<TreeNode> queue1 = new LinkedList<>();
queue1.add(root);
Queue<TreeNode> queue2 = new LinkedList<>();
while (!queue1.isEmpty() || !queue2.isEmpty()) {
while (!queue1.isEmpty()) {
TreeNode node = queue1.poll();
if (queue1.size() == 0) {
System.out.println(node.getData());
}
if (node.getLeft() != null) {
queue2.add(node.getLeft());
}
if (node.getRight() != null) {
queue2.add(node.getRight());
}
}
while (!queue2.isEmpty()) {
TreeNode node = queue2.poll();
if (queue2.size() == 0) {
System.out.println(node.getData());
}
if (node.getLeft() != null) {
queue1.add(node.getLeft());
}
if (node.getRight() != null) {
queue1.add(node.getRight());
}
}
}
}
}

Monday, 7 December 2020

MongoDB Basics


Stores JSON objects in BSON format. 

Javascript based. Allows to query in javascript style.


Master-Slave architecture - shards and replicasets

There is a router with a table of contents and shard keys using which it decides where to query the data and in some cases multiple shards.

mongos - process which manages cluster

client connects to mongos


> use recipe

switched to db recipe

> show dbs

admin   0.000GB

config  0.000GB

local   0.000GB

recipe  0.000GB


db.<collectionName>.insertOne({<entire json document to be inserted>}) -> this will dynamically create a collection


db.<collectionName>.find({"fieldToQuery":"valueOfFieldToQuery"}, {"filedstLimitOutput": 1})

.sort("fieldToSortBy": 1).limit(1).skip(1)


> show collections

recipe


> db.recipe.find({}, {"title": 1});

{ "_id" : ObjectId("5f8c85634e5ccd1948fb7611"), "title" : "Zucchini Brownies" }

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }


> db.recipe.find({"title" : "Pancakes"}, {"title": 1});

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }


> db.recipe.find({},{"title": 1}).sort({"title":1});

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }

{ "_id" : ObjectId("5f8c85634e5ccd1948fb7611"), "title" : "Zucchini Brownies" }


> db.recipe.find({},{"title": 1}).sort({"title":1}).limit(1);

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }


> db.recipe.find({},{"title": 1}).sort({"title":1}).limit(1).skip(1);

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }


# nested objects can also be queried

> db.recipe.find({"ingredients.name" : "egg"}, {"title" : 1});

{ "_id" : ObjectId("5f8c85634e5ccd1948fb7611"), "title" : "Zucchini Brownies" }

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }


# querying arrays

> db.recipe.find({"tags" : "easy"}, {"title" : 1});

{ "_id" : ObjectId("5f8c85634e5ccd1948fb7611"), "title" : "Zucchini Brownies" }

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }


# match both entries in an array

> db.recipe.find({"tags" : {$all: ["easy","mexican"]}}, {"title" : 1});

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }


# match either entries in an array

> db.recipe.find({"tags" : {$in: ["easy","mexican"]}}, {"title" : 1});

{ "_id" : ObjectId("5f8c85634e5ccd1948fb7611"), "title" : "Zucchini Brownies" }

{ "_id" : ObjectId("5f8c88a94e5ccd1948fb7612"), "title" : "Chicken Soft Tacos" }


#using expression

> db.recipe.find({$and :[{"ingredients.name" : "egg"}, {"ingredients.name" : "milk"}]}, {"title" : 1});

{ "_id" : ObjectId("5f8c88ee4e5ccd1948fb7613"), "title" : "Pancakes" }



$regex - for doing a regex search on a field


can store arrays, nested documents


comparison operators:

$eq, $lt, $lte, $gt, $gte, $ne, $in, $nin


logical operators:

$and, $or, $not


evalution:

$exists - to match documents with specified field


$where - documents satisfying javascript expression


it even have geospatial evaluation operators - $geoWithin, $geoIntersects etc


db.<collectionName>.updateOne({"fieldToQuery":"valueOfFieldToQuery"}, {$set :{"filedstLimitOutput": 1}});


> db.recipe.updateOne({"title" : "Zucchini Brownies" }, {$set: {"title" : "Zucchini Browniesss" }});

{ "acknowledged" : true, "matchedCount" : 1, "modifiedCount" : 1 }


$push $pull can be used for updating data in an array


# for getting the execution statistics, explain("executionStats") can be used

db.recipe.find({"tags" : {$in: ["easy","mexican"]}}, {"title" : 1}).explain("executionStats");


Reference documentation - https://docs.mongodb.com/manual/reference


sample_json = {

   "title":"Zucchini Brownies",

   "calories_per_serving":271,

   "comments": [{

      "body": "This is really gross.",

      "date": {

          "$date": "2020-09-07T18:42:30.000Z"

      },

      "name": "Caderyn Jenkins",

      "user_id": 1

  }, {

      "body": "Who thought of this? It's so bad.",

      "date": {

          "$date": "2000-02-03T18:42:30.000Z"

      },

      "name": "Grace Hopper",

      "user_id": 2

  }],

   "cook_time":32,

   "desc":"Don't worry, they won't turn out green",

   "directions":[

      "Combine brownie mix with other ingredients",

      "Bake as it says on box",

      "Don't actually make or eat this."

   ],

   "ingredients":[

      {

         "amount":{

            "quantity":1,

            "unit":"cup"

         },

         "name":"butter"

      },

      {

         "amount":{

            "quantity":2,

            "unit":null

         },

         "name":"egg"

      },

      {

         "amount":{

            "quantity":0.75,

            "unit":"cup"

         },

         "name":"plain yogurt"

      },

      {

         "amount":{

            "quantity":0.75,

            "unit":"cup"

         },

         "name":"shredded zucchini"

      },

      {

         "amount":{

            "quantity":0.75,

            "unit":"cup"

         },

         "name":"chocolate chips (semisweet)"

      },

      {

         "amount":{

            "quantity":3,

            "unit":"lbs"

         },

         "name":"creamy peanut butter"

      },

      {

         "amount":{

            "quantity":1,

            "unit":null

         },

         "name":"brownie mix"

      }

   ],

   "prep_time":12,

   "rating":[

      1,

      1,

      1,

      1,

      5

   ],

   "rating_avg":1.8,

   "servings":12,

   "tags":[

      "sweets",

      "easy"

   ],

   "type":"Dessert"

}


db.recipe.insertOne(sample_json);


Start/Stop mongod services in Mac:

brew services start mongodb-community@4.4

brew services stop mongodb-community@4.4



Microservices Authorization, JWT, OAuth 2.0 and SSO

 

In a microservices architecture, once the user logs in, the identity of the user needs to be communicated to all the services that handles the requests to the application and each service needs to know that this is an authenticated user and need to check whether the user have privileges for requested operation. 

The entry point to a microservice based application is an API gateway which hide the complexity due to multiple services from the end user. The gateway will contact an Authentication and Authorization server which authenticates and logs in the user and returns a JWT access token. This access token is further used in each request to verify the identity of the user from Authorization server.

JWT is a Base64 encoded string which can be decoded into a the following (all separated by "."):

1. a header with an algorithm used for signing the token, 

2. a payload which consists of basic user info like userId and iat (issued at time) and some basic info but not credentials

3. a footer consisting of a signature generated out of header and payload using the algorithm mentioned in the header and a secret key which is held only by the authorization server.

The JWT token is issued to the user based on the login using the credentials and is typically send in the further requests as a bearer token (by placing Bearer <token> in the Authorization header). The JWT token is normally saved in the cookies for the browser to send it in the further requests.

The authorization server generates a signature by extracting header and payload from the bearer token provided to it and compare with the signature in the bearer token for validating the authenticity on subsequent requests.


OAuth 2.0 

Important Terminologies:

Resource owner - The user who owns a resource (e.g. files on a google drive).

Resource server - The server which maintains the resource (e.g. google drive server)

Authorization server - The server which validates authorization to access resource server

Client application - Any client application that wants to access user resource on behalf of the user.

Grant type client credentials

In a microservice architecture, if a microservice needs to access data from another microservice:

1. The Authorization server grants a client credentials access token to the microservice

2. The authorization server validates the requests from the source microservice based on the client credential access token.

3. permission needs to be managed for the client credential access token for restricting the access of the service to APIs in the destination microservice as required. 

Grant type authorization code

If a client application wants to access certain details from a resource server on behalf of an end user:

1. The client application sends a request to authorization server requesting the access for the resource.

2. The authorization server redirects to the end user asking him to allow the client application to access the resource on his behalf, the user has to login if he has not already logged in to the authorization server.

3. Once the user gives consent for the client application to access the resource, the authorization server will send an authorization code/token to the client application.

4. The client application may store the same and calls the authorization server with the authorization code to get an access token.

5. The client application uses this access token for communicating with the resource server.

Grant type device code

OAuth 2.0 extension that enables devices with no browser or limited input capability to obtain an access token.

Grant type refresh token

This is used for getting a new access token when the original access token is expired. The original access token will have an expiry time when refresh token is required.


Handling SSO using OAuth 2.0

Although OAuth was meant for authorization, this model is extended to implement Single Sign On using grant type authorization code flow:

1. The client application sends a request to authorization server requesting the profile information of the user.

2. The authorization server redirects to the end user asking him to allow the client application to access his profile information, the user has to login if he has not already logged in to the authorization server.

3. Once the user gives consent for the client application to access his profile info, the authorization server will send an authorization code/token to the client application.

4. The client application may store the same and calls the authorization server with the authorization code to get an access token.

5. The client application uses this access token for communicating with the resource server and gets the profile info.

6. The client application trusts the authorization server and since authorization server validated the user, the user is considered valid by the client application

6. The user profile info is then set in the security context of the client app and will proceed. 

Saturday, 28 November 2020

Write a program to create forest from a tree by deleting set of input nodes

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree


package com.test.algorithm.tree;

import java.util.*;

public class MakeForest {
public static List<TreeNode> makeForestByDeletingNodes(TreeNode root, int[] toDeleteValueList) {
List<TreeNode> forestNodes = new ArrayList<>();
boolean isRootDeleted = false;
for (int i=0; i<toDeleteValueList.length; i++) {
if (root.getData() == toDeleteValueList[i]) {
isRootDeleted = true;
}
List<TreeNode> childNodes = searchAndDeleteNodeAndReturnChildren(root, toDeleteValueList[i]);
forestNodes.addAll(childNodes);
}
if (!isRootDeleted) {
forestNodes.add(root);
}
return forestNodes;
}

public static List<TreeNode> searchAndDeleteNodeAndReturnChildren(TreeNode root, int toDeleteValue) {
if (root == null) {
return null;
}

List<TreeNode> childNodes = null;
if(root.getData() == toDeleteValue) {
childNodes = new ArrayList<>();
if (root.getLeft() != null) {
childNodes.add(root.getLeft());
}
if (root.getRight() != null) {
childNodes.add(root.getRight());
}
return childNodes;
}
if(root.getLeft() != null && root.getLeft().getData() == toDeleteValue) {
childNodes = new ArrayList<>();
if (root.getLeft().getLeft() != null) {
childNodes.add(root.getLeft().getLeft());
}
if (root.getLeft().getRight() != null) {
childNodes.add(root.getLeft().getRight());
}
root.setLeft(null);
return childNodes;
}
if(root.getRight() != null && root.getRight().getData() == toDeleteValue) {
childNodes = new ArrayList<>();
if (root.getRight().getLeft() != null) {
childNodes.add(root.getRight().getLeft());
}
if (root.getRight().getRight() != null) {
childNodes.add(root.getRight().getRight());
}
root.setRight(null);
return childNodes;
}
childNodes = searchAndDeleteNodeAndReturnChildren(root.getLeft(), toDeleteValue);
if (childNodes == null) {
childNodes = searchAndDeleteNodeAndReturnChildren(root.getRight(), toDeleteValue);
}
return childNodes;
}


public static void main(String args[] ) throws Exception {
TreeNode root = makeTree();
List<TreeNode> forest = makeForestByDeletingNodes(root, new int[]{3,5});
for (TreeNode node : forest) {
printTree(node);
System.out.println();
}
}

private static void printTree(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.getData() + " ");
printTree(node.getLeft());
printTree(node.getRight());
}

private static TreeNode makeTree() {
TreeNode root = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
TreeNode node9 = new TreeNode(9);
TreeNode node10 = new TreeNode(10);

root.setLeft(node2);
root.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
node3.setRight(node7);
node6.setRight(node8);
node7.setLeft(node9);
node7.setRight(node10);

return root;
}
}


Write a concurrent LRU Cache using ReadWriteLock to allow parallel reads

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/cache

This LRUCache is implemented using ReadWriteLock allowing parallel reads where as only a single write can happen at a time. But caches are meant for read with less write and this approach would help in parallel reads for small scale of data.

This approach has a major disadvantage with respect to time taken for searching an entry if the scale of data to be retained is huge. This is because the ConcurrentLinkedQueue needs to be scanned to re-add after picking up the data every time. For large scale data it is better to use the synchronized LinkedHashMap approach.


package com.test.algorithm.cache;

import java.util.Map;
import java.util.Queue;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class LRUCacheWithReadWriteLock<K, V> {

private final int limit;
private final Map<K, V> internalCache;
private final Queue<K> trackingQueue;

private final ReadWriteLock readWriteLock = new ReentrantReadWriteLock();

public LRUCacheWithReadWriteLock(int limit){
internalCache = new ConcurrentHashMap<>();
trackingQueue = new ConcurrentLinkedQueue<>();
this.limit = limit;
}

public V get(K key) {
this.readWriteLock.readLock().lock();
try {
V value = internalCache.get(key);
if (value != null) {
if (trackingQueue.remove(key)) {
trackingQueue.add(key);
}
}
return value;
} finally {
this.readWriteLock.readLock().unlock();
}
}

public void put(K key, V value) {
this.readWriteLock.writeLock();
try {
if (internalCache.containsKey(key)) {
trackingQueue.remove(key);
}
if (trackingQueue.size() == limit) {
K expiredKey = trackingQueue.poll();
internalCache.remove(expiredKey);
}
internalCache.put(key, value);
trackingQueue.add(key);
} finally {
this.readWriteLock.writeLock().unlock();
}
}

public static void main(String arg[]){
LRUCacheWithReadWriteLock<Integer, String> lruCache = new LRUCacheWithReadWriteLock<>(4);

lruCache.put(1, "Object1");
lruCache.put(2, "Object2");
lruCache.put(3, "Object3");
lruCache.get(1);
lruCache.put(4, "Object4");
System.out.println(lruCache);
lruCache.put(5, "Object5");
lruCache.get(3);
lruCache.put(6, "Object6");
System.out.println(lruCache);
lruCache.get(4);
lruCache.put(7, "Object7");
lruCache.put(8, "Object8");
System.out.println(lruCache);
}

@Override
public String toString() {
return "LRUCacheWithReadWriteLock{" +
"internalCache=" + internalCache +
'}';
}
}

Write a concurrent LRU Cache using LinkedHashMap

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/cache

For handling concurrency, we will have to synchronize the methods of LinkedHashMap being used as LRU Cache.

For better performance, LRU Cache can be implemented using ReadWriteLock, ConcurrentLinkedQueue and a ConcurrentHashMap - refer the implementation

package com.test.algorithm.cache;

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheWithLinkedHashMap<K, V> {

private final Map<K, V> internalCache;

public LRUCacheWithLinkedHashMap(int limit){
internalCache = Collections.synchronizedMap(new LinkedHashMap<K, V>(limit, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > limit;
}
});
}

public V get(K key) {
return internalCache.get(key);
}

public void put(K key, V value) {
internalCache.put(key, value);
}

public V remove(K key) {
return internalCache.remove(key);
}

public static void main(String arg[]){
LRUCacheWithLinkedHashMap<Integer, String> lruCache = new LRUCacheWithLinkedHashMap<>(4);

lruCache.put(1, "Object1");
lruCache.put(2, "Object2");
lruCache.put(3, "Object3");
lruCache.get(1);
lruCache.put(4, "Object4");
System.out.println(lruCache);
lruCache.put(5, "Object5");
lruCache.get(3);
lruCache.put(6, "Object6");
System.out.println(lruCache);
lruCache.get(4);
lruCache.put(7, "Object7");
lruCache.put(8, "Object8");
System.out.println(lruCache);
}

@Override
public String toString() {
return "LRUCacheWithLinkedHashMap{" +
"internalCache=" + internalCache +
'}';
}
}

Write a program to print a Binary Tree in Spiral Order Traversal

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree


package com.test.algorithm.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class SpiralTraversal {

public static void main(String[] args) {
TreeNode root = new TreeNode(4);
root.setLeft(new TreeNode(2));
root.getLeft().setRight(new TreeNode(3));
root.getLeft().setLeft(new TreeNode(1));

root.setRight(new TreeNode(6));
root.getRight().setRight(new TreeNode(7));
root.getRight().setLeft(new TreeNode(5));

printTreeInOrder(root);

printSpirally(root);
}

private static void printSpirally(TreeNode root) {

Stack<TreeNode> rightToLeftStack = new Stack<>();
rightToLeftStack.push(root);
Stack<TreeNode> leftToRightStack = new Stack<>();
while(!rightToLeftStack.isEmpty() || !leftToRightStack.isEmpty()) {
while(!rightToLeftStack.isEmpty()) {
TreeNode node = rightToLeftStack.pop();
System.out.println(node);
if (node.getLeft() != null) {
leftToRightStack.push(node.getLeft());
}
if (node.getRight() != null) {
leftToRightStack.push(node.getRight());
}
}
while(!leftToRightStack.isEmpty()) {
TreeNode node = leftToRightStack.pop();
System.out.println(node);
if (node.getRight() != null) {
rightToLeftStack.push(node.getRight());
}
if (node.getLeft() != null) {
rightToLeftStack.push(node.getLeft());
}
}
}
}

private static void printTreeInOrder(TreeNode root) {
if (root == null){
return;
}
printTreeInOrder(root.getLeft());
System.out.println(root);
printTreeInOrder(root.getRight());
}
}


Write a program to print a Binary Tree in Level Order Traversal

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/tree


package com.test.algorithm.tree;

import java.util.*;

public class LevelOrderTraversal {

public static void main(String[] args) {
TreeNode root = new TreeNode(4);
root.setLeft(new TreeNode(2));
root.getLeft().setRight(new TreeNode(3));
root.getLeft().setLeft(new TreeNode(1));

root.setRight(new TreeNode(6));
root.getRight().setRight(new TreeNode(7));
root.getRight().setLeft(new TreeNode(5));

printTreeInOrder(root);

printInLevelOrder(root);
}

private static void printInLevelOrder(TreeNode root) {

Queue<TreeNode> treeNodeQueue = new LinkedList<>();
treeNodeQueue.add(root);
while(!treeNodeQueue.isEmpty()) {
TreeNode node = treeNodeQueue.poll();
System.out.println(node);
if (node.getLeft() != null) {
treeNodeQueue.add(node.getLeft());
}
if (node.getRight() != null) {
treeNodeQueue.add(node.getRight());
}
}
}

private static void printTreeInOrder(TreeNode root) {
if (root == null){
return;
}
printTreeInOrder(root.getLeft());
System.out.println(root);
printTreeInOrder(root.getRight());
}
}