Deadlock Detection in Service Orchestrator: Real time use case of Algorithms coded from scratch

VenkteshV — Sun, 23 Sep 2018 17:42:31 +0000

I had two courses in my undergraduate course B.E in computer science : Data structures and applications-1 and the following semester a course titled data structures and applications -2. We had a very good professor and we absolutely loved the course and the related labs and mini projects.The textbooks prescribed were also good and the content was well articulated.The reason for the above prologue is that once i graduated and entered the industry I found out that the usage of these sophisticated data structures or even the basic ones like tries(discount arrays) was not satisfactory or nil.This was depressing for me as i had hoped that working in product companies meant crunching large amounts of data and building efficient data structures (leveraging sorry!) like how linkedin uses Bloom filters to avoid unnecessary database hits when it can be retrieved from cache if present or like how they are leveraged for spam filtering etc.But i also realised that i sort of misinterpreted.Of course many so called product companies other than those real tech savy companies don't bother much on innovation,all developers use data structures,it is just that it might be abstracted in form of a library or hiding in plain sight.Well you should be aware of B-Trees for effectively understanding DB queries.If you are wondering how learning about Bipartite graphs will be useful, one concrete example is the assignment of teachers to classes(try guessing the use cases within this application) and i could go on but i hope you get the point.

So why this lengthy intro? So that i get a lengthy post? no to realise the importance of core computer science UG courses and their applications .Ok now let's jump to the topic.

The purpose of this post is to explain a deadlock detector i implemented for detecting circular dependencies in a config file specifying the services to invoke fed to a orchestrator( of course in true microservice architecture you wouldn't introduce a single point of failure but just consider this use case).

the link to the npm package i have published is : https://www.npmjs.com/package/deadlock-detector

Well now to the code and explanation.The approach I have used to detect cyclic calls to services is a recursive depth-first graph-coloring algorithm in which nodes are marked as "visiting" or "visited". If, when visiting a node, you find it is already in the "visiting" state, you have a cycle. Nodes marked as "visited" can be skipped.

const states = { Visited : 'Visited', Visiting: 'Visiting', NotVisited: 'NotVisited' };

A node can be in 3 states.It can be marked as Visited if already visited.Or visiting if the node is being vsisited(helps in detecting the cycle) or default state (not-visited).

const Equal = (parents,node) => {   
    var result = false;
    _.forEach(parents,(parent) => {

            result =   _.isEqual(parent,node) || result;
    })
    return result;}


` const depthFirstSearch = (services,node,edges,parents,visited,cycles) => {
    var state = visited[node] || '';
    if (state == states.Visited)
    return;
    else if(state == states.Visiting)
    {      
        if(Equal(parents,node)){      
        cycles.push(_.concat(parents,node));
    }
    }
    else
    {   
        visited[node] = states.Visiting;
        parents.push(node);
        _.forEach(services[node],(child) => {
            depthFirstSearch(services,child, edges, parents, visited, cycles);

        });

        parents.splice(parents.length - 1,1);

        visited[node] = states.Visited;
    }
}`



 `const findCycles = (services) => {
    const nodes = Object.keys(services);
    var visited = {};
    var parents = new Array();
    var cycles = new Array();
    _.forEach(nodes,(node) => {
        const edges = services[node];
        depthFirstSearch(services,node,edges,parents,visited,cycles);
    })
    return cycles;
};
module.exports=findCycles;`

Example Usage:  Input is specified in following format.Use the following snippet of code to test the above package I have published.

`const findCycles = require('deadlock-detector'); 
const services = { 
"A": ["A"], 
"L":["M","N"], 
"N":["L"], 
"B":["C","D"], 
"D":["E"], 
"E":["F","Q"],
 "F":["D"] };
 const cycles = findCycles(services);
 console.log(cycles);

In the above example  cycles are [ [ 'A', 'A' ], [ 'L', 'N', 'L' ], [ 'B', 'D', 'E', 'F', 'D' ] ].`

Following is the flow of above methods.

Findcycles initializes an empty parent array and an array that will hold the output(cycles detected) and iterates over the input and calls the depth first search for each node.

In depth first search we check for various states(colors).If the node is already visited we do nothing and return if it is in Visiting state then hold on something's fishy we check if it is same as any of the nodes marked as parents and if true the cycle chain is formed by concatenating the parents( nodes marked as "visiting" before this node) and the node and the cycle is reported. A node is marked visited when all it's child nodes have been explored.Debug the code by cloning the library in local for clear visualization.

Conclusion:
That's it folks if you need a c# implementation feel free to drop in comments.Suggestions to improve the npm package are welcome.

AVOIDING IF_ELSE HELL

VenkteshV — Thu, 10 May 2018 17:03:03 +0000

All developers at some point are faced with a dilemma. They are asked to Fit in a variety of scenarios and hence end up writing if-else conditionals and reach a point where code becomes messy. Weeks later the dev may not even understand the code he wrote. Well if at some point you have felt the if else ladder you wrote is obnoxious or haunting welcome to the club.In this post I would like to humbly represent one instance where I was able to avoid the if-else hell by applying an existing pattern and a library.

There was a requirement in our application to update a status history table where we maintain the various status of document processing like upload, download etc.We maintain various states like extracted, uploading,downloading,uploaded etc. and hence we needed a validation logic to make sure the states are not updated in wrong order so we had to establish a small validation system to ensure other developers don't break the order as it would lead to serious cascading failures in the big picture. So I decided not to write conditional and wrap it up this time.When I stared at the acceptance criteria and the states I realized a pattern. After all these are states a document goes through and voila I got a solution,State Machine. And since the app was in .net core I decided to use the "Stateless" package to achieve the same. So let's jump to the example.

    public ProcessState Status
    {
        get
        {
            return _stateMachine.State;
        }
    }


         public StatelessStateMachine(ProcessState state)
    {
        _stateMachine = new StateMachine<ProcessState, ProcessStateTransitionTriggers>(state);
        _stateMachine.Configure(ProcessState.Extracted)
            .Permit(ProcessStateTransitionTriggers.moveToQueuedForDownload, ProcessState.QueuedForDownload);

        _stateMachine.Configure(ProcessState.QueuedForDownload)
            .Permit(ProcessStateTransitionTriggers.moveToDownloading, ProcessState.Downloading);

        _stateMachine.Configure(ProcessState.Downloading)
           .Permit(ProcessStateTransitionTriggers.moveToDownloaded, ProcessState.Downloaded);

        _stateMachine.Configure(ProcessState.Downloaded)
         .Permit(ProcessStateTransitionTriggers.moveToQueuedForUpload, ProcessState.QueuedForUpload);

    }

Explanation :
_statemachine.State returns the current status.
Next the first line in the function below is used to instantiate the List of states and the triggers(ProcessState and ProcessStateTransitionTriggers are enums containing the list of states and triggers respectively).So when a trigger is fired depending on the state specified in the permit true or false will be returned to indicate if the state transition is valid or not.

{
_stateMachine.Configure(ProcessState.Extracted)
.Permit(ProcessStateTransitionTriggers.moveToQueuedForDownload, ProcessState.QueuedForDownload);
}

For example in the above code translates to if the current state is Extracted then permit the transition to state "QueuedForDownload" if the transition trigger is moveToQueuedForDownload

{_stateMachine.CanFire(trigger)}

The above line will fire the validation and if it returns true the update can be performed using

{_stateMachine.Fire(trigger)}

In the above example "trigger" will be "moveToQueuedForDownload".

Conclusion:

Hence a lot of common obnoxious code we force ourselves to write can be avoided by relating to existing patterns.

DEV Community: VenkteshV

Deadlock Detection in Service Orchestrator: Real time use case of Algorithms coded from scratch

AVOIDING IF_ELSE HELL