Simple and efficient way to Designing a Fault tolerant, Distributed System Using Game Theory Technique

Scale – One important aspect to design a system either technical or non-technical, it helps business grow. Business or technology comes at a juncture where without scaling each other one cannot move forward without other. Scale means building systems that could cater to the business needs for a certain period of time. There is no point in building a system for 1000 people when your target is 100 from 10. Scale is a time dependent variable and changes constantly. Similarly in technology, you scale up or down and that’s how the cloud is leveraged. There may are many tools, techniques designs available. One simple technique that I came across techniques which very simple and efficient that could be leveraged is the use of Game Theory based Job allocation/load balancing in Distributed System . This paper uses a technique of ‘Nash Equilibrium’ which states that in games, if there are several players; the move of one should benefit every other person or should not be a disadvantage to others. Either there is a benefit or no benefit but there is no loss. Using this technique, a very simple processes could be set up that could scale up to few millions of records.

The set up consists of a configuration file, a job allocation process, the main process which processes the document and a reallocation process.

·         Configuration

·         Job Allocation (Job Distribution)

·         Main Process  - That processes the document for example : parsing a  document

·         Re allocation or redistribution of jobs

These could be written using any of the languages (Java, Perl, Python etc.) and has been tested for crawling half a million records in less than 2 hours. The process could further be improved to less than 10 minutes using Pareto principle and could be used to run frequently the crawler. The allocation process allocates jobs to the machines according to machine ids. The main process processes the document and the reallocation process reallocates the jobs at regular interval of time. The allocation and reallocation process is scheduled on every machine at different intervals of time so that even if one machine fails it is processed after some time on a different machine. The main process is run at regular interval of time on every machine. This is the differentiator from the master slave architecture.

Advantages of using this system

1.    Scalable : The system could be easily scaled by adding a machine  within 5 minutes

2.   Optimization: The system was using all the resources (RAM & CPU) at maximum efficiency all the time.

3.    Distributed and Fault tolerant: It works on distributed model.

4.    Technology:  No advanced technology is required.

Problem Statement

Let us say we have few millions of rows and we need to process these data which are independent of each other. 

For example:

· Let us assume we have X machines (for simplicity let’s say 4 – M1, M2, M3, M4)

· On each machine, max Y processes can be run (Y can be different on each Machine. Let’s assume constant for each machine say 10)

· Max Number of processes that can be run simultaneously = Sum of (Y_i) (40 in this case)

·We have say thousands or lakhs of rows of documents (Assume 1000 rows). These documents need to be processed on different machines. 

1. Basic Configuration

·  On each machine, a configuration is set for

            i.MAXPROCESS -the maximum number of processes that shall be run simultaneously. This needs to be done based on the memory consumption by doing some random experiments on the machine by executing the code.

             ii. MACHINEID – Machine ID allocated to that machine.

2.   Allocation

o  Divide the number of rows with the number of machines. (1000/4=250 in this case)

o  Each of the rows (document) has varying length. It is assumed that the length of the document is also stored while allocating to the machines.

o  Allocation is done by assigning a machine id to each of the document, it will be uniform among the number of machines i.e 250 per machine (Figure 1)

o  Execute this process every 15 minutes on the four machines only if the allocated processes have completed their job. This ensures even if 1 machine fails, it will get executed after 15 minutes on another machine.

3.   Process Execution

·Execute the document processes every minute or two.  When executing ensures that you read the documents as per the sorted order - descending.

·Ensure that the maximum processes are running on each machine as per the configuration. As soon as one of the processes gets over, the other process kicks off as it is executed every minute.  This ensures maximum utilization of the servers.

4.   Redistribution(Re – Allocation)

· As the time progresses, due to varying length of the document, network latency, slowness on servers due to unforeseen circumstances, the number of documents varies for each machine. (As shown in figure 2)

· Due to this redistribution of documents need to be done. This is done as follows

                     i.Take the number of documents allocated per machine at that time. Let’s say M1 – 100, M2 -150, M3-175, M4-200

                    ii. Select 2 machines that has the lowest and highest number of documents pending to process  – Here it is M1 & M4, sum the count and divide it by two, = (100+200)/2 = 150. So M1 & M2 should get 150 each. This needs to be done removing the 20 documents by ascending order and allocating it to M1 ( As shown in figure)

                       iii. Similarly for M2 & M3  - 162 each

·  Execute this process every 5 minutes or so. And, set this up on every machine. So, that even if 1 machine fails, it is taken up on another machine after 5 minutes.

· This ensures load distribution, fault tolerant, scalable and helps to utilize the processes effectively.(Figure 3)

Google is not the only thing !

While Population Explosion was one of the evils in the last couple of decades, Information Explosion is the emerging (or perhaps emerged) evil during this decade and the coming decades. There is ocean of data available on the web and finding the right information given a search query is an enormous and a herculean task. To solve the enigma of search companies like Google, Yahoo, Microsoft have search engines which are continuously tuned with new information coming in round the clock. It is a known fact that the size of the world wide web is increasing rapidly and Google is the father of all search engines that gets you the right information you are looking for !

Remember Osmosis process, where the molecules pass through a semi permeable membrane from a lower concentration to higher concentration. It is this process that I underwent over a decade ago by moving from a Tier 2 city to to the silicon valley of India i.e Bangalore. Definitely, to pass through the semi permeable membrane was the hardest thing. After landing in India's Silicon valley, I learnt that, Google was an answering machine.  Any doubt or Any question in mind? Rather than asking any one, Just ask Google ! I wondered at times that Google should have been named as Guru. Google has taken the place as walking encyclopedia and it has found its place in Oxford dictionary as well.  

After using the Guru aka Google for over a decade, it has now become a Genie - One who fulfills your wish. I have observed for quite some time that whenever I type the first word or second word in Google, there comes the auto suggested words that are more or less the ones that I was looking to search. And, this has happened many a times. Another incidence, that has happened, I looked for Mahindra Scorpio the soon to be launched face lift version. After some time, I saw an ad that suggested about winning a Scorpio by enrolling in to a contest. I had a wishful thinking to buy a Scorpio, here the web suggested me an option to get it. Google might have started reading your mind or rather subconscious mind ;)

A decade of habit of searching for information on Google has led to a strong belief that Google has the answer for everything. Searching has moved away from giving relevant information to predicting what information you are looking for. And, that's what Google is getting better and better day by day. 

Information is available in various forms, the same information might also be scattered on different platforms. We are now in an era of Information Explosion. A midst the plethora of information, searching or predicting what information you need is like searching needle or rather tiny needle in a haystack. And, it is this tiny needle that may get lost during search and even Google may miss it.

With the strong belief that Google can answer my requirement - Noise Cancellation Headphones with mainly the mic that does not transmit the noise to other end and also within a budget of ₹. 1000 . I searched on Google, I did not find the intended result.  I changed my query and tried again (Google) ,  I did try to find on Amazon, Snapdeal but I did not get what I intended in the top results. I gave up my  online search and inquired my friends and also posted on Facebook. None of them gave me a answer that I was looking for, though there were some options posted with the likes of Bose, Senheiser, JBL etc, but not within the budget.

A casual walk to the landmark book store during a weekend, got me what I wanted - Panasonic-RP-HM111PP-W. This product did not turn up online without the word 'Panasonic'  which I realized later. Also, the price that I paid was Rs. 599 and later I learnt the online price was Rs. 479, clearly a discount of over 20% was missed in this deal! Another such instance happened when I was about to buy a Vegetable Cutter  and the online price was around ₹1100 and a chance encounter at a Big Bazaar was ₹ 995.  Finally, it was a zero sum game between the two deals, however the bargaining opportunity was clearly missed by the father of searching engines or any other shopping sites in both the cases.( I do not know if SEO would have helped Panasonic to get me what I wanted). It is evident that the search engines face a gargantuan challenge to get the right product out of millions of product available using a query of few words.

Internet has evolved - world wide web, search engines, online forums, social networks, shopping sites etc.  To get the right information you need to know the right search query and the right platform to search for. Search might be thought to be a solved problem but the huge addition of information everyday makes it unsolved for every query that is searched for. Perhaps, Pranav Mistry's Sixth Sense Project would have helped  to take the search to the next level. And, People would have banned cell phones while entering the shopping zones;). But, Mistry has moved away from the Sixth Sense Project . 

For every query there is definitely Google, but sometimes a walk down to your nearby store makes you realize Google is not the only thing !

What makes a Product Successful?

It is a million dollar question and I wish there was some recipe for it. Unfortunately, there is no one recipe for it.  Nevertheless, after working for over 6 years in 3 start-ups developing and working on some innovative products, there are few key things that will make the product successful which I have outlined below.

Idea and Conceptualization:  The foremost thing is to have an idea. Once you have an idea, you need to conceptualize and think through it so that it lasts forever. This is where the vision comes in to picture and you really need to think hard what new things are coming up and how can it be applied to the business problems in the market. The way you present and position it in the market matters, there may be lot of people who are doing the same thing, but the way you position and differentiate will matter the clients the most.

Execution: Having an idea is one thing, executing is another! One of my friend says, Ideas are the cheapest things available so, what matters most is execution. Putting the right people in the right place, making them aware of your goals and ensuring things are going as per your plan. Also, ensuring the team is focused and doesn’t lose its direction on a day to day basis matters a lot.  Just because you are the first one to do it and nobody else has done it, doesn’t mean you will be successful. Remember Google was not the first search engine, but it’s still successful.

Presentation and Usability:  In some conversation, some one said, market needs two things one that works and one that looks good. Both needs to be done in parallel. Unless you have an excellent, clean and uncluttered user interface nobody will use it.  Not just clean interface, but should be easily usable as well. Initially there used to be lot of login forms to be filled before you logged on to the application, but these days you can log on using a simple email id and you start off! Making the application simple and easily usable interface is of foremost importance.

Market: While you are building the product, you need to start capturing the market and understanding it. One of my Prof. Said,  the pulse of the market needs to be understood and you should be able to gauge know what works and what doesn’t. And, getting the right feedback from the clients and implementing it is the key. This should work in an iterative way!

Education:  You may have nice usability and presentation. However, if the client is unaware of how to use it, it would be a disaster. I remember in one of the instance, one of the users used a certain user interface to delete from db. However, he meant to delete it temporarily, but it erased the entire table and hence the information was lost forever. It is vital that the client is educated and sufficient training is provided so that he knows to use it effectively.

Awareness: Well, you might have given proper training and education to the client. However, there may be so many features and it becomes impossible to remember each of the features due to information overload. Every now and then you should make the user to remind him of a feature that is being developed or present. Like some websites, throw a pop up to make the user aware of the feature. Awareness plays a key role to make the product more usable and sustaining it.

Adoption: You have an excellent product and it solves the most challenging problem, but without the adaptability of the people to use the product it would be a failure.  It has been said that only 5% of the products are successful. The inability of the people to adapt to new solution is a hindrance to the growth and hence a debacle to the product. In my initial days at one of the company, any idea that was thrown to the people was thrown in to dust bin literally.  Lack of knowledge,  unwillingness to learn new things,  inability to fore see the future were all making the product to be scrapped. But the commitment from the management ensured it was successful, but it got delayed by over a year due to adoption issues.

Scale: You have solid product, it is usable, and it is adopted. That’s very well done! You may want to relax..! But, in order to continue the momentum and an everlasting product you need a product that’s scalable to different verticals in short period of time. Not just scale of product, scale of team, team management, processes, adopting to change of markets will all play a crucial role so that there is a growth otherwise the product loses its steam and hence needs to be scrapped!

In my little experience that I have gained, these are some of the aspects that are key to make a product successful.  There are several other aspects that might play a key role which are not covered.  

Again, as it is said, success is about being in the right place, at the right time with the right people.

 

Feel Blessed

Feel Blessed,

If you get two squares meal a day, there are millions who does not have food to survive

Feel Blessed,

If you have got some education, there are millions who do not get the opportunity to study.

Feel Blessed,

If you have parents, there are millions where parents have ditched their kids and/or are orphans.

Feel Blessed,

If you have a shelter, there are millions who stay on the roads and are devoid of shelter.

Feel Blessed,

If you have Eyes, Nose, Ears, Voice etc. there are millions without one or more of these.

Feel Blessed,

If you have a job, there are millions without a Job.

Feel Blessed,

If you have drinking water, there are millions where people travel miles to fetch few litres of water.

Feel Blessed,

If you have a vehicle, there are millions without one.

Feel Blessed,

If you can afford to buy clothes, there are millions where these are not on their priority list.

Feel Blessed,

If you are able to travel, there are millions where they have not gone beyond a few kilometres in their life.

Feel Blessed,

If you know internet, there are millions where it is still a luxury for them.

Feel Blessed,

If you have Kids, there are millions without kids.

Feel Blessed,

If you are alive, there are millions who die just after birth or killed in the Womb.

         

Feel Blessed,

And, try to bring some change in one’s life.       

Reminisicing the Beloved , Dedicated and Inspiring Teachers'

God could not be everywhere that’s why he created mother. Mother who gives an unconditional love, affection to her child is the First Guru also known Aadi Guru to the child. It is the mother’s voice that reaches the child first and there starts journey of learning of the good, bad and ugly of life. Search Google for the word Guru and you shall find over 0.4 billion results with various meanings of the Guru. Guru - means Teacher in Sanskrit, imparter of knowledge, It also means one who dispels darkness of ignorance. On the eve of Teachers’ day, this blog is a tribute to the teachers in my life and a special thanks to them for making me what I am today. A Teacher plays a very important role in one’s life. The significance of the Guru and Shishya is very much evident from Mahabharata, where Krishna is the Guru and Arjuna the Disciple. It is Krishna who guides and navigates Arjuna through various conundrums that Arjuna faces.                                                         

Teachers’ Day – A day dedicated to teachers’ and their accomplishments. Different countries celebrate this day on different days, mainly as a celebration to their accomplishments and their effort to nurture and make the students life bright and prosperous. In India, it is celebrated on 5^th September to commemorate the Birth Anniversary of Dr. Sarvapalli Radhakrishnan. Dr.Radhakrishan was the first Vice President and the Second President of India. He was a great Scholar and a Philosopher too. One of his best quotes was “When we think we know we cease to learn”. He was awarded Bharat Ratna in 1954.

Painting by: Amit Shah

The school days are the best days in life and are filled with fun, naughtiness, learning, mischief etc. And, everyone wants to go back to those days. You can write any number of incidences in your school. One such incidence is my first speech and if I remember it correctly it was on Teachers’ Day. The first speech is always scary, nervous and especially when you have a stage fear you tend to forget few words or lines. And, same thing happened to me, But, a very low voice from behind was helping me to recollect the words and lines. Guess who it was, it was my English Teacher :). Gone are the days of the stage fear and now I am confident of giving even extempore. The name of the school is named after Swami Vivkenand known as Shri Vivekanand English Medium School. And, who can forget his message from Swami Vivekand – Arise, Awake and Stop not till the goal is reached.

 

Another incidence in the school was during the send off ceremony as we were about to complete 10^th standard. Our Maths teacher gave us some valuable message as follows.‘Dear Students, You are like my children. So many days you were with us and we were protecting you from all evils. You were swimming in a pond; you shall soon start swimming in ocean.  The depth of ocean is never known, ocean is beautiful, you get fins to swim like a fish and there are no boundaries. But it has sharks, dolphins and many other creatures. You have to swim carefully and cautiously and be successful in life’. It was a great message; most of us have followed them and are trying to be as successful as possible. 

After completing 10^th and 12^th, I landed up at Engineering at BVB College of Engineering and Technology, Hubli. During one of our class in the morning, Our Prof. asked us “What are the news headlines for the day”? My friend said “We don't read the news for the day as  we get late to reach college in the morning?”. Prof gave a witty reply “What is yesterday’s headline?” The message was loud and clear that emphasize to keep updated about the happenings around the world. The Prof. was a mentor to me and also guide to our final year project. I got an opportunity to assist in his PhD Thesis by implementing a C program to simulate the Robotics model he had proposed. 

After Engineering I had break in between and then Pursued M. Tech at IIIT-B. During one of the lecture events at IIIT-B, I had been to invite one of the Prof. for the event; the reply was ‘I am what I am’. The message is clear, follow your own path and be what you want to be! At another incidence during the Open House, two Profs started debating about a certain model used in the project, soon scores of students started surrounding which was one of the great discussion to listen. Knowledge is like Honey, you just get attracted to it. True to the punch line of the college ‘Jnanam Uttamam – Knowledge is supreme.'

The incidences at each of the institutes I studied are endless. ‘Alma mater’ as it is known as, which means ‘nourishing mother’ in Latin has made me what I am today and given me a way of life. At every step there were teachers’ who guided and nurtured me.  Guru, Teacher, Mentor – call them whatever you like. They are the important people who are needed at every age of your life. Teachers’ are the most revered people on earth; they guide you, mentor you and help you navigate the intricacies. Even in professional life at every place I went there was someone who guided me to navigate the nuances of work life.  Teachers' are the most revered persons forever and in every one’s life. You might not have met your teachers' since ages, but definitely you remember them and they are in your hearts always. Wishing all the teachers ‘A Very Happy Teachers Day’.