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

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.