Algorithm for distributed load balancing of batch processing

Just for reference this algorithm doesn't work in practice. The problem is that nodes under heavy load tend to be too slow to answer to hold on to their leases causing partitions to jump between hosts. I have moved on to another algorithm that I might write up at some point if I get time. just a fair warning to anybody who was thinking of implementing this.

I recently played around a little bit with the Azure EventHub managed service which promises high throughput event processing at relatively low cost. At first it seems relatively easy to use in a distributed matter using the class EventProcessorHost and that is what all the online examples provided by Microsoft are using too.

My experience is that the EventProcessorHost is basically useless. Not only does it not contain any provision that I have found to provide a retry policy to make its API calls fault tolerant. It also is designed to only checkpoint its progress at relatively few intervals meaning that you have to design your application to work properly even if events are reprocessed (Which is what will happen after a catastrophic failure). Worse than that though once you fire up more than one processing node it simply falls all over itself constantly causing almost no processing to happen.

So if you want to use the EventHub managed service in any serious way you need to code directly to the EventHubClient interface which means that you have to figure out your own way of distributing its partitions over the available nodes.

This leads me to an interesting problem. How do your evenly balance the load of work evenly over a certain number of nodes (In the nomenclature below the work is split into one or more partitions) which can at any time have a catastrophic failure and stop processing without a central orchestrator.

Furthermore I want the behavior that if the load is completely evenly distributed between the nodes the pieces of the load should be sticky, meaning that the partitions of work currently allocated to a node should stay allocated to that node.

The algorithm I have come up with requires a Redis cache to handle the orchestration and it uses only 2 hash tables and two subscription for handling the orchestration. But any key value store that provides publish and subscribe functionality should do.

The algorithm have 5 time spans that are important.

• Normal lease time. I'm using 60 seconds for this. It is the normal time a partition will be leased without generally being challenged.
• Maximum lease time. Must be significantly longer than the normal lease time.
• Maximum shutdown time. The maximum time a processor has to shut down after it has lost a lease on a partition.
• Minimum lease grab time. Must be less than the normal lease time.
• Current leases held delay. Should be relatively short. A second should be plenty (I generally operate in the 100 to 500 millisecond range). This is multiplied by the number of currently processing partitions. It can't be too low though or you will run into scheduler based jitter of partitions jumping between partitions.

Each node also should listen to two Redis subscriptions (Basically notifications to all subscribers). Each will send out a notification that is the partition being affected.

• Grab lease subscription. Used to signal that the leas of a partition is being challenged.
• Allocated lease subscription. Used to signal that the lease of a partition has ended when somebody is waiting to start processing it.

There are also two hash keys in use to keep track of things. Each one contains the hash field of the partition and will contain the name of the host currently owning it.

• Lease allocation. Contains which nodes currently is actually processing which partition.
• Lease grab. Used to race and indicate which node won a challenge to take over processing of a partition.

This is the general algorithm.

1. Once every time per normal lease time each node will send out a grab lease subscription notification per each partition that.
• It does not yet own and which does not currently have any value set for the partition in the lease grab hash key.
• If it has been more than the maximum lease time since the last time a lease grab was signaled for the partition (This is required for the case when a node dies somewhere after step 3 but before step 6 has completed). If this happens also clear the lease allocation and lease grab hash for the partition before raising the notification since it is an indication that a node has gone offline without cleaning up.
2. Upon receipt of this notification the timer for this publications is reset (So generally only one publication per partition will be sent during the normal lease time, but it can happen twice if two nodes send them out at the same time. Also when this is received each node will wait based on this formula.
• If the node currently is already processing the partition it will wait the number of active partitions on the node currently held times the current leases held delay minus half of this delay (So basically (Locally active partitions - 1) * current leases held delay).
• If the node currently is not busy processing the partition that is being grabbed the node should wait the local active partitions plus one times the current leases held delay (On so fewer words (Locally active partitions + 0.5) * current leases held delay).
3. Once the delay is done try to set the lease grab hash key for the partition with the conditional transaction parameter of it not being set.
• Generally the node that has the lowest delay from step 2 should get this which also means that the active partitions on each node should distribute evenly among any active nodes since the more active partitions each individual node has the longer it will wait in step 2 and the less likely it is that they will win the race to own the partition lease.
• If a node is currently processing a partition but did not win the race in step 2 it should immediately signal its partition to gracefully shut down and once it is shut down it should remove the lease allocation hash field for the partition. Once this is done it should also publish the allocated lease subscription notification. After that is completed this node should skip the rest of the steps.
4. Check by reading the lease allocation hash value to see if another node than the winner in step 3 is currently busy processing the partition. If this is the case either wait for either the allocated lease subscription notification signaling that the other node has finished from step 3b or if this does not happen wait for a maximum of maximum shutdown time and start the partition anyway.
5. Mark the lease allocation hash with the new current node that is now processing this partition.
6. Also after the minimum lease grab time remove the winning indication in the lease grab hash key for the partition so that it can be challenged again from step 1.

When I run this algorithm in my tests it works exactly as I want it. Once a new node comes online within the normal lease time the workload has been distributed evenly among the new and old nodes. Also an important test is that if you only have one partition the partition does not skip among the nodes, but squarely lands on one node and stays there. And finally if I kill a node without giving it any chance to do any cleanup after roughly maximum lease time the load is distributed out to the remaining nodes.

This algorithm does not in any way handle the case when the load on the different partitions is not uniform, in that case you could relatively easily tweak the formula in step 2 above and replace the locally active partitions with whatever measurement of load or performed work you wish. It will be tricky to keep the algorithm sticky though with these changes.

Antonin Scalia Does Not Believe in Molecular Biology

In an opinion that boggles the mind written by Antonin Scalia on a recent the case regarding the legality of patenting genes he apparently does not believe in anything that he does not have first hand knowledge on or can experience with his own senses.

Although he agrees with the court decision that naturally occurring genes should not be patentable he disagrees in why this is the case. In his views it shouldn't be patentable because he doesn't believe in genes at all. Makes me all fuzzy inside to think that this is the guy that is one of nine final voices in legal matters in the worlds currently only super power.

Americas most epic undertaking started 50 years ago to this day

It is today 50 years ago that John F Kennedy gave his inspiring we choose to go to the moon speech. With this speech started the most epic of scientific achievements probably in the history of mankind to this date.

It is important to remember how the USA was the nation that accomplished this amazing feat as we are slipping in international rankings for math and science educations. It saddens me that we are not still prioritizing this frontier more. For instance we seem poised to spend more than a quarter of the entire NASA budget this year just on the presidential election campaigns. Wouldn't it be better if we had some campaign finance reform to reduce the ridiculous money spent in US politics and use that money more wisely. And in the process we might also end up with politicians that are more interested in the common good than special interest.

I recommend everybody to watch the entire speech below. It is very inspiring and still hugely relevant.

Obama & Romney answer questions on science

In case you haven't already read it check out the current presidential candidates response on scientific questions over at the Scientific American.

Highlights include Mitt Romney still not thinking global warming is serious enough to warrant any actual response. In the same vein Obama is pointing to his huge ($90 billion) investment in renewable energy, however Romney does rightly point out that so far we have precious little to show for it.

This should should be required reading for everybody who plans to vote!

The end of cavities

Scientists have discovered a molecule that when kept in your mouth for 60 seconds will keep your teeth cavity proof for hours. Specifically the molecule kills Streptococcus Mutans and can be added to pretty much any dental product or even candy.

The product still needs FDA approval but once that is hopefully achieved dental care can be changed forever for the better and we will hopefully all be able to keep the teeth we have.

Why I don't believe in God

I've spent a lot of time both studying and thinking about religion, theology and "the big questions" almost all my life and have come to the conclusion that there probably is no god and I just thought I would share some of my reasoning for coming to this conclusion.

First of all with our current understanding of quantum physics we actually have a pretty consistent idea of how the universe works. Even though it is by no means complete, it does in it contain ideas about how the universe was at one point created out of nothing. It is often referred to as the ultimate free lunch. Granted to understand this discussion it requires a basic understanding of how the universe works, but it isn't really past what most people can get if they are interested in it. I recommend two courses from The Teaching Company. The first one is called Understanding the Universe: An Introduction to Astronomy and the second one is called Particle Physics for Non-Physicists: A Tour of the Microcosmos. So with the knowledge that the universe can exist as we perceive it today without a god. Then the nonexistance of god comes from the application of Occam's razor which roughly states that the simplest solution to a problem is probably the right one.

Another way to come to the same conclusion is to consider that the universe is probably around 4.5 billion years old. Humans have existed in more or less their current form for around 200 thousand years and no currently existing religion has been around for more than maybe 5000 years. Also factor in the size of the known universe and the pretty high likelihood of there being other intelligent life in it. It just seems so unlikely that a deity would go through all that trouble just to start nitpicking about what we eat, how we procreate and what we should think about others (Especially others who don't share our beliefs).

Compare both of these arguments to the likelihood of religion being a human invention to help people to cope with the fear of dying, relatives passing away or an otherwise unfair lot in life. Then there are also the huge benefits that seem to generally be bestowed upon those that successfully start or become the leader of religions. And you also have the benefit that in most countries religions are not even taxed on their earnings or holdings. So if you are interested in being wealthy or to have power religion seems to be a great business to be in.

This does not mean that I think that people who have come to different conclusions for these questions than me are stupid. These questions are almost by definition ineffable and unknowable. However given the fact that most people does seem to inherit their religion from their parents, it seem like they don't think that much about the alternatives.

Maybe organic food isn't better for you

If you are like me and have generally assumed that organic food is better for you then we might have all been falling for the marketing. A recent big meta study in the Annals of Internal Medicine examined 17 different studies into the health benefits between eating organic and "normal" food and found no statistically significant changes based on the source of the food.

I'll probably still keep eating the organic food since I just kind of prefer to keep my pesticide and animal growth hormone intake to a minimum regardless of health implications. If all you care about is your health though then at least for now it seems that there are probably other changes to your lifestyle that have a bigger impact on your health. Did you know for instance that regularly flossing your teeth increases your average lifespan with over 6 years.

Scientist might have found a cure for Malaria!

In an awesome development researchers at the University of Cape Town might have found a quick and easy cure for Malaria. Malaria is one of the most common causes of death world wide with an estimated 200 million cases in 2010 and around 1 million deaths. As a comparison this is almost as many deaths as from AIDS with the difference that there are few precautions you can take to protect you against the disease.

Current treatments are complicated, long and have many bad side effects. The new treatment is a pill that needs to be taken only once and so far no side effects have been observed. It is scheduled to enter human trials in 2013 and if successful could save millions of lives in the future, many of them children who are extra susceptible to the disease.

How to open a tricky jar lid

You ever have problem open a tricky jar? This is a nice video that goes through a bunch of different tips and tricks about how to solve this sticky problem.

Source America's Test Kitchen

46% of Americans are creationists according to latest poll

According to a recent gallup poll 46% of Americans believe in creationism. If you include intelligent design the number goes up to a staggering 78%.

If only these people also decided not to enjoying the fruits of the research based on the theory they are rejecting (Meaning most of modern medicine)? Due to Darwin's survival of the fittest it shouldn't take too long until these numbers turned a little bit saner... Since creationists don't believe in that premise (At least not when applied to humans), I can't see them having any moral dilemma with it either.

On a more positive note Richard Leakey predicts that in two to three decades the debate about evolution will be over due to a preponderance of evidence. I'm not so sure that I am that optimistic though since when we are dealing with faith, evidence unfortunately seem to not be in a big demand.

I have to admit I don't understand why it's only in this country that mainstream religion seem to have such a big problem with the theory of evolution? In most other countries it is only fringe nut jobs that are advocating creationism, while in this country we have serious debates over teaching it as science in school. In the end I think it comes down to fundamentalism being scary no matter what religion is practicing it and we just have a lot more Christian fundamentalism in USA compared to most other countries.

The next step in human development?

This video discusses how we have already started and will probably continue using technology to improve human performance. We already started using pace makers and prosthethics that might be better than the real thing.

The next logical step is to start enhancing the performance of our brains. We have already began with implants that can treat epilepsy. Is the next step to help people with concentration difficulty really that far off? Where it goes after that is anybody's guess.

The contents of the video is based on the book Amped by Daniel H Wilson.

Cool interactive info-graphic to calculate the chance of extra terrestrial life

Check out this cool info graphic that lets you play around with the parameters of Drake's equation and see how likely you think it is that we are not alone.

Also just because there might be alien civilizations it still doesn't mean that we will ever run into them. The universe is really big and compared to its size the speed of light is pretty slow.

Check out this video if you missed the landing on Mars last Sunday

This is a really cool video where animations and live recordings from NASA are showing the landing and some subsequent commentary from the people at NASA on this amazing achievement.

I am amazed at how little there has been in the news about this fantastic engineering achievement. To me this is probably the coolest thing that has been done since when we landed on the moon and I don't understand why everybody isn't talking about. Why do people care about the Olympic Games? They happen every 4 years!

Really cool video of how the next Mars rover will land

Check out this awesome video from NASA about how the next rover Curiosity will land on Mars on August 5^th. I hope it works and it is a glimpse at what you can do when you get a bunch of really smart people together and tell them to do something virtually impossible! And all of it sound to a thumping soundtrack.

How much water do you use?

Given that fresh water might be one of the most precious commodities we have soon as population growth continues. Check out this really cool site that shows you how much water is needed to make common things you use every day.

Can you imagine in your wildest dream that it takes more than 2000 liters (~500 gallons) of water to make one burger? How much water does it take to make a pair of jeans? Go to the site and find out!

Private space flight finally takes off

The successful launch, and subsequent docking with the ISS is the starting point of a new era in the human exploration of space. And this week Virgin Galactic got FAA approval to start testing their Spaceship Two for suborbital flights.

Private space flight is finally starting to "get off the ground" and I can't wait for it to start catching on. The prices involved for a private space flight is still out of reach for most, but given that people up until now has paid hundreds of millions of dollars to escape earth the $100k that Virgin Atlantic is charging doesn't seem that bad. And keep in mind that when commercial flight started earlier in the last century it was also only available for the very well off. I would be actually be surprised if the prices hadn't come down to a more reasonable price level that I could afford before I get too old to try the experience and me for one can't wait.

Space exploration is the only way to ensure the long (Granted extremely long) term survival of the human race and I hope that we will get started with more ambitious colonization of our solar system soon. By any luck we'll have both permanent moon & Mars bases before the next century comes along and hopefully a couple of asteroids that we can mine for minerals that are rare on the surface of the earth. I also hope by then we will have a space elevator constructed somewhere which will make leaving the earth gravity well no more complicated than taking a train ride is today.

Even though the first tiny steps taken these last few weeks might seem small I hope for all of ours sake that it is the beginning of a new push for humans to start exploring the world outside our little blue marble that we call home and this time driven by commercial interests instead of national pride because commerce will always be there while national pride comes and goes. It is tragic how it was almost 40 years ago since the last human placed it's feet on another celestial body, let's hope it will not be too many decades before we are aiming outwards again and this time lets hope we don't stop!

Cool visualization about how much water there is on Earth

Did you think most of the Earth was water? Think again!

Check out this really cool visualization of how truly minute amounts of water there is on our little blue green globe. And if we start talking about fresh water there there is so little of it, it might as well be a rounding error.

Source Gozmodo

If you're a parent you should know about Kahn Academy

If I had kids I would give them some kind of indestructible table (For instance a Kindle Fire in a sturdy case) and lock it down to only be able to access Kahn Academy. If you have never heard of this website you should check it out right now as long as you are still interested in learning new things and if you have children I would say it is practically mandatory.

Originally the site started out as with mostly math and science courses and this is still the most developed subjects but it also contains courses in economics and history and tons of other stuff (There are currently over 3000 lectures available on the site). Each individual lecture is never longer than 10 minutes long so it's easy to sneak one in when you have a few minutes left over. There are also practice courses that help you apply what you have learned that are using all the latest "gamification" methods making it really fun to do them (I like doing it myself when bored). The courses start from the very basics and then build on each other onto increasingly advanced topics.

Kahn Academy started out with Salman Kahn realizing that he was spending a lot of time helping to tutor his relatives and friends and started putting short courses on YouTube. It grew into a very popular channel and in the end led to quit his job in finance as a hedge fund analyst at Connective Capital Management and work on it full time. The Bill and Melissa Gates foundation is an enthusiastic backer of the project and Bill at one time was quoted saying "I'd say we've moved about 160 IQ points from the hedge fund category to the teaching-many-people-in-a-leveraged-way category. It was a good day his wife let him quit his job".

Cool video explaining the concept of different magnitudes of infinity

This video goes through and explains the concept of different magnitudes of infinity in a way that is easy to follow, something that can generally be really tricky to grasp intuitively.

If you are interested in what I think is the fascinating world of numbers I can absolutely recommend this very easy to follow Teaching Company course on the subject called Zero to Infinity: A history of Numbers. I listened to it a few months ago and found it fascinating.

Awesome new ketchup bottle technology

This is the biggest innovation in food technology since the invention of the seedless grape. Check out the amazing non stick ketchup bottle of the future.